数据结构-实验一

线性表、堆栈和队列的操作与实现

1、线性表的链表实现

(1) 用随机函数生成10个3位整数(100~999)，把这些整数存于链表中； 要求每次运行生成的10个数据都不相同

(2) 输出链表的内容；

(3) 读入一个整数，查看该整数是否在表中，若在，输出其位置(首位置为1)；

(4) 读入一个整数，以及要插入的位置，把该整数插入到链表中，输出链表的内容, 要求判断输入的位置是否合理；

(5) 读入一个整数，若该整数在链表里，删除该整数，输出链表的内容；

(6) 把链表的内容翻转，输出链表的内容，要求不占用新的存储空间。考核重点 其他表达方式：将链表中所有结点的链接方向“原地”逆转，即要求仅利用原表中 的存储空间。

(7) 将两个非递减的有序链表合并成一个非递增的有序链表，要求结果链表仍使用 原来两个链表的存储空间，不占用其他的存储空间，表中允许有重复的数据。

#include<stdio.h>
#include<iostream>
#include<stdlib.h>
#include<time.h>

#define true 1
#define false 0

typedef struct Node
{
    int data;
    struct Node* next;
}Node;
Node* Initializelist() {
    Node* root = (Node*)malloc(sizeof(Node));
    root->data = 0;
    root->next = NULL;
    return root;
}
void Headinsert(Node* root, int data) {
    Node* node = (Node*)malloc(sizeof(Node));
    node->data = data;
    node->next = root->next;
    root->next = node;
    root->data++;
}
int ishavadata(Node* root, int data) {
    Node* node = root->next;
    while (node) {
        if (node->data == data) {
            return true;
        }
        node = node->next;
    }
    return false;
}
void Tailinsert(Node* root, int data) {
    Node* beginroot = root;
    for (int i = 0;i < root->data;i++) {
        beginroot = beginroot->next;
    }
    Node* node = (Node*)malloc(sizeof(Node));
    node->data = data;
    node->next = beginroot->next;
    beginroot->next = node;
    root->data++;
}
void deletedata(Node* root, int data) {
    if (ishavadata(root, data)) {
        Node* prenode = root;
        Node* node = root->next;
        while (node) {
            if (node->data == data) {
                prenode->next = node->next;
                free(node);
                root->data--;
                printf("删除成功!(^_^)");
                break;
            }
            else {
                prenode = node;
                node = node->next;
            }
        }
    }
    else {
        printf("该数据在这个链表中不存在!删除失败!");
    }
}
void checkdata(Node* root, int data) {
    Node* node = root->next;
    int ans = 1;
    while (node) {
        if (node->data == data) {
            printf("存在这个链表中,而且下标为:%d\n", ans);
        }
        node = node->next;
        ans++;
    }
    printf("不存在这个数据在这个链表中!!\n");
}
void insertdata(Node* root, int data, int unmber) {
    Node* node = root->next;
    int ans = 1;
    if (unmber < 0) {
        printf("抱歉!,你输入的下标小于0!不正确!\n");
    }
    else if (unmber == 0) {
        Headinsert(root, data);
        printf("插入成功!\n");
    }
    else if (unmber == root->data) {
        Tailinsert(root, data);
        printf("插入成功!");
    }
    else if (unmber > root->data) {
        printf("你选择插入的链表的位置不正确!超出了链表的长度!!!\n");
    }
    else {
        while (node) {
            if (ans == unmber) {
                Node* newnode = (Node*)malloc(sizeof(Node));
                newnode->data = data;
                newnode->next = node->next;
                node->next = newnode;
                root->data++;
                printf("插入成功!\n");
                break;
            }
            node = node->next;
            ans++;
        }
    }
}
void reverse(Node* root) {
    if (root->data == 0) {
        printf("空链表!");
    }
    else if (root->data == 1) {
        return;
    }
    else {
        Node* fristnode = root->next;
        Node* secondnode = fristnode->next;
        root->data = 1;
        while (secondnode) {
            Node* thirdnode = secondnode;
            Headinsert(root, thirdnode->data);
            fristnode->next = secondnode->next;
            secondnode = secondnode->next;
        }
    }
}
void printnode(Node* root) {
    Node* node = root->next;
    printf("root");
    while (node) {
        printf("->%d", node->data);
        node = node->next;
    }
    printf("\n这个链表的长度是:%d\n", root->data);
}
void mergenode(Node* fristnode, Node* secondnode) {
    Node* pa = fristnode->next;
    Node* pb = secondnode->next;
    Node* pc = fristnode;
    pc->data = fristnode->data + secondnode->data;
    while (pa && pb) {
        if (pa->data >= pb->data) {
            pc->next = pa;
            pc = pa;
            pa = pa->next;
        }
        else {
            pc->next = pb;
            pc = pb;
            pb = pb->next;
        }
    }
    pc->next = (pa) ? pa : pb;
    free(secondnode);
    secondnode = NULL;
}
int main() {
    srand((unsigned int)time(NULL));
    int app = 10;
    Node* root = Initializelist();
    while (app) {
        if (root->data == 0) {
            int numberdata = rand() % 999 + 100;
            Headinsert(root, numberdata);
            app--;
        }
        else {
            int numberdata = rand() % 999 + 100;
            if (ishavadata(root, numberdata)) {
                continue;
            }
            else {
                Headinsert(root, numberdata);
                app--;
            }
        }
    }
    printnode(root);
    reverse(root);
    printnode(root);
    checkdata(root, 234);
    checkdata(root, 667);
    checkdata(root, 112);
    insertdata(root, 30000, 8);
    insertdata(root, 9999999, 45);
    printnode(root);
    Node* rootsortup = Initializelist();
    Node* rootsortdown = Initializelist();
    Headinsert(rootsortup, 9999);
    Headinsert(rootsortup, 345);
    Headinsert(rootsortup, 222);
    Headinsert(rootsortup, 111);
    Headinsert(rootsortup, 23);
    Headinsert(rootsortup, 22);
    Headinsert(rootsortup, 13);
    printf("upsort");
    printnode(rootsortup);
    Tailinsert(rootsortdown, 2);
    Tailinsert(rootsortdown, 23);
    Tailinsert(rootsortdown, 231);
    Tailinsert(rootsortdown, 235);
    Tailinsert(rootsortdown, 300);
    Tailinsert(rootsortdown, 8888);
    printf("downsort");
    printnode(rootsortdown);
    reverse(rootsortup);
    reverse(rootsortdown);
    mergenode(rootsortdown, rootsortup);
    printf("mergesort");
    printnode(rootsortdown);
    return 0;
}

2、栈的链式存储结构实现

(1) 用随机函数生成 10 个 3 位整数(100~999)，把这些整数应用入栈操作存于堆栈 中，在入栈接口处设置断点①，按“F5”启动调试，按“F10”逐句执行，直到数据全部 入栈。程序暂停时观察栈顶数据和栈顶位置(截图一张即可)；

(2) 应用出栈操作输出堆栈的内容，在出栈接口处设置断点②，按“F5”启动调试， 按“F10”逐句执行，直到所有数据完全出栈，程序暂停时观察栈顶数据和栈顶位置的 变化(截图一张即可)。

#include<stdio.h>
#include<stdlib.h>

typedef struct Node
{
    int data;
    struct Node* next;
}Node;
Node* Initializelist() {
    Node* root = (Node*)malloc(sizeof(Node));
    root->data = 0;
    root->next = NULL;
    return root;
}
void Headinsert(Node* root, int data) {
    Node* node = (Node*)malloc(sizeof(Node));
    node->data = data;
    node->next = root->next;
    root->next = node;
    root->data++;
}
void printnode(Node* root) {
    Node* node = root->next;
    printf("root");
    while (node) {
        printf("->%d", node->data);
        node = node->next;
    }
    printf("\n这个栈的深度是:%d\n", root->data);
}
void outstrak(Node* root) {
    if (root->data == 0) {
        printf("\n这个栈为空!\n");
    }
    else {
        Node* node = root->next;
        int number = node->data;
        root->next = node->next;
        free(node);
        root->data--;
        printf("\n出栈:%d\n", number);
        printnode(root);
    }
}
int main() {
    Node* root = Initializelist();
    Headinsert(root, 123);
    Headinsert(root, 13123);
    Headinsert(root, 4123);
    Headinsert(root, 1);
    Headinsert(root, 42543);
    Headinsert(root, 1211212);
    printnode(root);
    outstrak(root);
    outstrak(root);
    outstrak(root);
    outstrak(root);
    outstrak(root);
    outstrak(root);
    outstrak(root);
    outstrak(root);
    outstrak(root);
    outstrak(root);
    return 0;
}

3、队列的链式存储结构的实现

(1) 用随机函数生成 10 个 3 位整数(100~999)，把这些整数应用入队操作存于队列 中；

(2) 应用遍历操作输出队列的内容；

(3) 把队列的内容翻转，应用出队操作输出队列的内容。

#include<stdio.h>
#include<iostream>
#include<stdlib.h>
#include<time.h>

typedef struct Node
{
    int data;
    struct Node* next;
}Node;
Node* Initializelist() {
    Node* root = (Node*)malloc(sizeof(Node));
    root->data = 0;
    root->next = NULL;
    return root;
}
void Headinsert(Node* root, int data) {
    Node* node = (Node*)malloc(sizeof(Node));
    node->data = data;
    node->next = root->next;
    root->next = node;
    root->data++;
}
bool ishavadata(Node* root, int data) {
    Node* node = root->next;
    while (node) {
        if (node->data == data) {
            return true;
        }
        node = node->next;
    }
    return false;
}
void Tailinsert(Node* root, int data) {
    Node* beginroot = root;
    for (int i = 0;i < root->data;i++) {
        beginroot = beginroot->next;
    }
    Node* node = (Node*)malloc(sizeof(Node));
    node->data = data;
    node->next = beginroot->next;
    beginroot->next = node;
    root->data++;
}
bool deletedata(Node* root, int data) {
    Node* prenode = root;
    Node* node = root->next;
    while (node) {
        if (node->data == data) {
            prenode->next = node->next;
            free(node);
            root->data--;
            return true;
        }
        else {
            prenode = node;
            node = node->next;
        }
    }
    return false;
}
void printnode(Node* root) {
    Node* node = root->next;
    printf("root");
    while (node) {
        printf("->%d", node->data);
        node = node->next;
    }
    printf("\n");
}
void outqueue(Node* root) {
    if (root->data == 0) {
        printf("\n这个队列为空!\n");
    }
    else {
        Node* node = root->next;
        int number = node->data;
        root->next = node->next;
        free(node);
        root->data--;
        printf("\n出队:%d\n", number);
        printnode(root);
    }
}
int main() {
    srand((unsigned int)time(NULL));
    int app = 10;
    Node* root = Initializelist();
    while (app) {
        if (root->data == 0) {
            int numberdata = rand() % 999 + 100;
            Headinsert(root, numberdata);
            app--;
        }
        else {
            int numberdata = rand() % 999 + 100;
            if (ishavadata(root, numberdata)) {
                continue;
            }
            else {
                Tailinsert(root, numberdata);
                app--;
            }
        }
    }
    printnode(root);
    int number = 10;
    while (number--) {
        outqueue(root);
    }
    outqueue(root);
    return 0;
}

4、线性表、栈和队列的应用实现

(1).线性表的应用

用随机函数生成 10 个 3 位整数(100~999)，把这些整数存于单链表中，然后读 入一个整数，以该值为基准把单链表分割为两部分，所有小于该值的结点排在大于或等 于该值的结点之前，不占用新的存储空间，注意时间复杂度。

#include<stdio.h>
#include<iostream>
#include<stdlib.h>
#include<time.h>

typedef struct Node
{
    int data;
    struct Node* next;
}Node;
Node* Initializelist() {
    Node* root = (Node*)malloc(sizeof(Node));
    root->data = 0;
    root->next = NULL;
    return root;
}
void Headinsert(Node* root, int data) {
    Node* node = (Node*)malloc(sizeof(Node));
    node->data = data;
    node->next = root->next;
    root->next = node;
    root->data++;
}
bool ishavadata(Node* root, int data) {
    Node* node = root->next;
    while (node) {
        if (node->data == data) {
            return true;
        }
        node = node->next;
    }
    return false;
}
void Tailinsert(Node* root, int data) {
    Node* beginroot = root;
    for (int i = 0;i < root->data;i++) {
        beginroot = beginroot->next;
    }
    Node* node = (Node*)malloc(sizeof(Node));
    node->data = data;
    node->next = beginroot->next;
    beginroot->next = node;
    root->data++;
}
void printnode(Node* root) {
    Node* node = root->next;
    printf("root");
    while (node) {
        printf("->%d", node->data);
        node = node->next;
    }
    printf("\n");
}
void middledata(Node* root, int data) {
    Headinsert(root, data);
    Node* pa, * pb;
    Node* node = root->next;
    pa = node;
    pb = node->next;
    while (pb) {
        if (pb->data < data) {
            pa->next = pb->next;
            pb->next = root->next;
            root->next = pb;
            pb = pa->next;
        }
        else {
            pb = pb->next;
            pa = pa->next;
        }
    }
}
int main() {
    srand((unsigned int)time(NULL));
    int app = 10;
    Node* root = Initializelist();
    while (app) {
        if (root->data == 0) {
            int numberdata = rand() % 999 + 100;
            Headinsert(root, numberdata);
            app--;
        }
        else {
            int numberdata = rand() % 999 + 100;
            if (ishavadata(root, numberdata)) {
                continue;
            }
            else {
                Tailinsert(root, numberdata);
                app--;
            }
        }
    }
    printnode(root);
    middledata(root, 590);
    printnode(root);
    return 0;
}

(2).栈的应用

假设一个字符串中可以包含三种括号：( )[ ]{}，且这三种括号可以按任意次序 嵌套使用(如：“…[…{…}…[…]…]…(…)” 为合法嵌套，“…[…{… )…[…]…]…(…)”为不合 法嵌套)。编写判别给定表达式中所含括号是否正确配对出现的算法，如果是合法嵌套则 返回为true，如果是不符合法嵌套则返回为false。(增加非括号字符的判断)

#include<stdio.h>
#include<iostream>
#include<string>
#include<stdlib.h>
#include <stdbool.h>
using namespace std;

typedef struct Node {
    char data;
    struct Node* next;
} Node;
Node* Initializelist() {
    Node* root = (Node*)malloc(sizeof(Node));
    root->data = 0;
    root->next = NULL;
    return root;
}
void Headinsert(Node* root, char data) {
    Node* node = (Node*)malloc(sizeof(Node));
    node->data = data;
    node->next = root->next;
    root->next = node;
    root->data++;
}
bool emptysrtack(Node* root) {
    return root->data == 0;
}
char outstrak(Node* root) {
    Node* node = root->next;
    char number = node->data;
    root->next = node->next;
    free(node);
    root->data--;
    return number;
}
char lookstrack(Node* root) {
    if (root->next) {
        return root->next->data;
    }
    return '\0';
}
bool checkpair(char ch, Node* root) {
    if (ch == '(' || ch == '[' || ch == '{') {
        Headinsert(root, ch);
        return true;
    }
    else if (ch == ')') {
        if (!emptysrtack(root) && lookstrack(root) == '(') {
            outstrak(root);
            return true;
        }
    }
    else if (ch == ']') {
        if (!emptysrtack(root) && lookstrack(root) == '[') {
            outstrak(root);
            return true;
        }
    }
    else if (ch == '}') {
        if (!emptysrtack(root) && lookstrack(root) == '{') {
            outstrak(root);
            return true;
        }
    }
    return false; 
}
int main() {
    cout << "请输入一个字符串出来, 判断这个字符串的符号是否符合规范 (输入 # 结束): " << endl;
    Node* _app = Initializelist(); 
    string input;
    cin >> input;
    int flag = 1; 
    for (char ch : input) {
        if (ch != '(' && ch != ')' && ch != '[' && ch != ']' && ch != '{' && ch != '}') {
            continue;
        }
        if (!checkpair(ch, _app)) {
            flag = 0;
            break;  
        }
    }
    if (emptysrtack(_app) && flag) {
        printf("true\n");
    }
    else {
        printf("false\n");
    }
    return 0;
}

(3).队列的应用

用队列求解迷宫问题的最短路径。 设计一个8×8的迷宫, 迷宫入口为(1, 1)，出口为(8, 8)，设计算法，用队列求解从 入口到出口的最短路径。要求： (a) 用矩阵表示一个迷宫，并输出该迷宫； (b) 在存在路径的前提条件下，显示最短路径的移动轨迹；没有路径则报错； (c) 可以尝试使用队列以外的其他方法，结果正确即可。

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
using namespace std;

#define max_size 10

int px[4] = { 0, 0, -1, 1 };
int py[4] = { 1, -1, 0, 0 };

struct postion {
    int x, y;
    int ans = 0; 
};
struct path {
    int x, y;
};
path pre[max_size][max_size];
struct map {
    int m, n;
    int app[max_size][max_size]; 
    bool visited[max_size][max_size] = { false }; 
    int x1, y1; 
    int x2, y2; 
};
struct node {
    postion data;
    struct node* next;
};
class queue {
private:
    node* root;
public:
    queue() {
        root = new node;
        root->next = NULL;
    }
    void push(postion data) {
        node* node1 = root;
        while (node1->next) {
            node1 = node1->next;
        }
        node* node2 = new node;
        node2->data = data;
        node2->next = nullptr;
        node1->next = node2;
    }
    postion front() {
        if (root->next == NULL) {
            return { -1,-1 };
        }
        else {
            postion number = root->next->data;
            return number;
        }
    };
    bool empty() {
        return root->next == NULL;
    }
    void pop() {
        if (root->next == NULL) return; 
        node* node1 = root->next;
        root->next = node1->next;
        free(node1);
    }
    void printnode() {
        node* node1 = root->next;
        printf("队列:");
        while (node1) {
            printf("-->(%d,%d)", node1->data.x, node1->data.y);
            node1 = node1->next;
        }
        printf("\n");
    }
    ~queue() {
        while (root) {
            node* temp = root;
            root = root->next;
            delete temp;
        }
    }
};
void bfs(map& site) {
    postion currentsite;
    postion nextsite;
    currentsite.x = site.x1;
    currentsite.y = site.y1;
    currentsite.ans = 0;
    site.visited[currentsite.x][currentsite.y] = true;
    queue app;
    app.push(currentsite);
    while (!app.empty()) {
        currentsite = app.front();
        app.pop();
        if (currentsite.x == site.x2 && currentsite.y == site.y2) {
            cout << "走出了迷宫!" << endl;
            cout << "共走了: " << currentsite.ans << " 步" << endl;
            path truepath[max_size* max_size];
            cout << "走过的路径为:";
            truepath[0].x = site.x2;
            truepath[0].y = site.y2;
            int number = 1;
            bool istrue = true;
            truepath[number] = pre[site.x2][site.y2];
            while (istrue) {
                if (truepath[number].x == site.x1 && truepath[number].y == site.y1) {
                    istrue = false;
                    break;
                }
                else {
                    number++;
                    truepath[number] = pre[truepath[number - 1].x][truepath[number - 1].y];
                }
            }
            cout << "这个的走过的路径为:";
            for (int i = currentsite.ans;i >= 0;i--) {
                cout << "(" << truepath[i].x << "," << truepath[i].y << ")" << "-->";
            }
            cout << "endl" << endl;
            return;
        }
        for (int i = 0; i < 4; i++) {
            nextsite.x = currentsite.x + px[i];
            nextsite.y = currentsite.y + py[i];
            if (nextsite.x >= 1 && nextsite.y >= 1 && !site.visited[nextsite.x][nextsite.y] && site.app[nextsite.x][nextsite.y] && nextsite.x <= site.m && nextsite.y <= site.n) {
                pre[nextsite.x][nextsite.y].x = currentsite.x;
                pre[nextsite.x][nextsite.y].y = currentsite.y;
                nextsite.ans = currentsite.ans + 1;
                site.visited[nextsite.x][nextsite.y] = true;
                app.push(nextsite);
            }
        }
    }
    cout << "没有走出迷宫" << endl;
}
int main() {
    cout << "请输入这个迷宫的长和宽 m 与 n：" << endl;
    map total;
    scanf_s("%d", &total.m);
    scanf_s("%d", &total.n);
    cout << "请输入这个迷宫的值，1代表可以通过的，0代表不可以通过的：" << endl;
    for (int i = 1; i <= total.m; i++) {
        for (int j = 1; j <= total.n; j++) {
            scanf_s("%d", &total.app[i][j]);
        }
    }
    cout << "请输入起点的值 (x1, y1): ";
    cin >> total.x1 >> total.y1;
    cout << "请输入终点的值 (x2, y2): ";
    cin >> total.x2 >> total.y2;
    if (total.x1 < 1 || total.x1 > total.m || total.y1 < 1 || total.y1 > total.n || total.app[total.x1][total.y1] == 0) {
        cout << "起点不合法!" << endl;
        return 0;
    }
    if (total.x2 < 1 || total.x2 > total.m || total.y2 < 1 || total.y2 > total.n || total.app[total.x2][total.y2] == 0) {
        cout << "终点不合法!" << endl;
        return 0;
    }
    bfs(total);
    return 0;
}