请选择 进入手机版 | 继续访问电脑版

数据结构与算法 基础实验

[复制链接]
孤单 发表于 2021-1-1 18:29:46 | 显示全部楼层 |阅读模式 打印 上一主题 下一主题
数据结构与算法底子实验大合集



实验一 线性表的创建、销毁、插入、删除、遍历等利用的实现:两个有序链表序列的归并

一、 题目

  7-1 两个有序链表序列的归并     已知两个非降序链表序列S1与S2,设计函数构造出S1与S2归并后的新的非降序链表S3。
输入格式:
    输入分两行,分别在每行给出由若干个正整数构成的非降序序列,用−1表现序列的末端(−1不属于这个序列)。数字用空格隔断。
输出格式:
    在一行中输出归并后新的非降序链表,数字间用空格分开,末端不能有多余空格;若新链表为空,输出NULL。
二、 解题思路

    观察链表的底子利用,链表为有序链表,需要定义一个结构体来实现链表数据结构,读入链表后比较当前指针所指的两个结点的值,将小的插入新的链表,指针指向下一个元素,重复上述利用即可。
三、 步伐设计

  1. 声明三个链表并开发空间定义指针p,指向第一个链表第一个结点定义指针q,指向第二个链表第一个结点while (p,q都不为NULL) {    if(p指向的值大于q指向的值)        将q指向的值插入第三个链表        q指向下一个结点    else        将p指向的值插入第三个链表        p指向下一个结点}输出第三个链表
复制代码
四、 步伐详解及运行结果

  1. #includeusing namespace std;struct LNode {    int val;    LNode* next = NULL;};int main() {    LNode* L1;    L1 = (LNode*)malloc(sizeof(LNode));    LNode* L2;    L2 = (LNode*)malloc(sizeof(LNode));    LNode* L3;    L3 = (LNode*)malloc(sizeof(LNode));    int temp;    cin >> temp;    LNode* l1 = L1;    while (temp != -1) {        l1->next = (LNode*)malloc(sizeof(LNode));//每次都要开发空间        l1 = l1->next;        l1->val = temp;        l1->next = NULL;        cin >> temp;    }    cin >> temp;    LNode* l2 = L2;    while (temp != -1) {        l2->next = (LNode*)malloc(sizeof(LNode));        l2 = l2->next;        l2->val = temp;        l2->next = NULL;        cin >> temp;    }    LNode* l3 = L3;    L1 = L1->next;    L2 = L2->next;    while (L1 && L2)    {        if (L1->val val) {            l3->next = (LNode*)malloc(sizeof(LNode));            l3 = l3->next;            l3->val=L1->val;            l3->next = NULL;            L1 = L1->next;        }        else {            l3->next = (LNode*)malloc(sizeof(LNode));            l3 = l3->next;            l3->val = L2->val;            l3->next = NULL;            L2 = L2->next;        }    }    if (L2==NULL) {        while (L1!=NULL) {            l3->next = (LNode*)malloc(sizeof(LNode));            l3 = l3->next;            l3->val = L1->val;            l3->next = NULL;            L1 = L1->next;        }    }    else {        while (L2!=NULL) {            l3->next = (LNode*)malloc(sizeof(LNode));            l3 = l3->next;            l3->val = L2->val;            l3->next = NULL;            L2 = L2->next;        }    }    if (L3==NULL) {        cout next;        while (L3!=NULL) {            cout next;        }        cout 第三个数组    第一个数组->第三个数组    第二个数组->第三个数组}if(第一个数组先空)    第二个数组剩余元素->第三个数组else    第一个数组剩余元素->第三个数组输出第三个数组
复制代码
四、 步伐详解及运行结果

  1. #includeusing namespace std;int main() {    int ans[1001],ji[1001],ou[1001];    int n, tem, aa = 0, o = 0, p = 0, l = 0, u = 0;    cin >> n;    for (int i = 0; i < n; i++) {        cin >> tem;        if (tem % 2) {            ji[o] = tem;            o++;        }        else {            ou[p] = tem;            p++;        }    }    while (n) {        if (u!=o && n) {            ans[aa] = ji[u];            aa++;            u++;            n--;        }        if (u != o && n) {            ans[aa] = ji[u];            aa++;            u++;            n--;        }        if (l != p && n) {            ans[aa] = ou[l];            aa++;            l++;            n--;        }    }    cout  3,3 --> 3,4--> 3,5--> 4,5--> 5,5--> 5,6--> 5,7--> 5,8  
复制代码
    题目包管每个迷宫最多只有一条最短路径。
    请输出该条最短路径,如果不存在任何通路,则输出"NO FOUND".

输入格式:
    第一行,输入M和N值,表现迷宫行数和列数。接着输入M行数值,此中,0表现通路,1表现障碍物。每列数值用空格符隔断。接下来大概输入多组迷宫数据。当输入M的值为-1时竣事输入。
输出格式:
    按行顺序输出路径的每个位置的行数和列数,如 x,y。如果不存在任何路径,则输出"NO FOUND".每组迷宫寻路结果用换行符隔断。
二、 解题思路

    观察运用队列进行广度优先搜索。(也可以用栈进行深度优先搜索求解)
三、 步伐设计

  1. 定义一个队列将起点参加队列while(1)        将当前队列中所有节点向四周的可达节点扩散        记载每一个扩散节点和到达该顶点的步数        if(队列为空)                返回找不到        if(到达终点)                退出循环通过记载的步数找出路径输出路径返回找到了
复制代码
四、 步伐详解及运行结果

  1. #include #include #include #includeusing namespace std;struct Position{        int row;        int col;};Position fx[4];bool findpath(vectorMG, int row, int col){        fx[0].row = 0; fx[0].col = 1;        fx[1].row = 1; fx[1].col = 0;        fx[2].row = 0; fx[2].col = -1;        fx[3].row = -1; fx[3].col = 0;        for (int i = 0; i < row + 2; i++){                MG[i][col + 1] = 1;                MG[i][0] = 1;        }//界限标成 1        for (int i = 0; i < col + 2; i++){                MG[0][i] = 1;                MG[row + 1][i] = 1;        }//界限标成 1        MG[1][1] = 2;        queue road;//用于广搜的队列        Position next;        Position here;        here.col = 1; here.row = 1;        while (1){                for (int i = 0; i < 4; i++){                        next.row = here.row + fx[i].row;                        next.col = here.col + fx[i].col;                        if (MG[next.row][next.col] == 0){                                MG[next.row][next.col] = MG[here.row][here.col] + 1;//记载到每一个顶点的步数                                if ((next.row == row) && (next.col == col))                                        break;                                road.push(next);                        }                }                if ((next.row == row) && (next.col == col))                        break;                if (road.empty())                        return false;                here = road.front();                road.pop();        }        int far = MG[row][col] - 2;        vectorpath(far);        here.row = row;        here.col = col;        for (int i = far - 1; i >= 0; i--){                path[i] = here;                for (int j = 0; j < 4; j++){                        next.row = here.row + fx[j].row;                        next.col = here.col + fx[j].col;                        if (MG[next.row][next.col] == i + 2)                                break;                }                here = next;        }        cout  mg[i][j];                if (findpath(mg, a, b))                        cout > b;        }}
复制代码

五、 问题及办理过程

    输出路径是该题难点,这里我通过标记到达每一个顶点的步数从终点一步步往回找前驱节点存储到数组中,再进行输出。
实验四 树的存储结构 :树的遍历

一、 题目

  7-2 树的遍历     给定一棵二叉树的后序遍历和中序遍历,请你输出其层序遍历的序列。这里假设键值都是互不相等的正整数。
输入格式:
    输入第一行给出一个正整数N(≤30),是二叉树中结点的个数。第二行给出厥后序遍历序列。第三行给出此中序遍历序列。数字间以空格分隔。
输出格式:
    在一行中输出该树的层序遍历的序列。数字间以1个空格分隔,行首尾不得有多余空格。
二、 解题思路

    主要观察树的遍历方法。先通过中序遍历序列和后序遍历序列将树构造出来,然后再输出层序遍历结果。
三、 步伐设计

  1. 声明树的结点结构体先通事后序遍历序列找到跟结点再团结中序遍历将树构架出来声明三个变量标记中序遍历序列与后序遍历序列遍历的当前位置用递归函数造树    if (中序序列遍历完毕)        返回NULL    声明一个结点    将后序序列最后一个值赋给当前结点    r->val = a[end_hou];    在中序序列中找到该结点的值所处位置    在该结点值所处位置左右分别递归该构造树的函数最后利用广度优先搜索将树层序遍历
复制代码
四、 步伐详解及运行结果

  1. #include #include#includeusing namespace std;typedef struct node {    int val;    struct node* left;    struct node* right;}node, * tree;vectorans;vectorb(31);vectora(31);queue c;tree Du(int end_hou, int begin_zhong, int end_zhong) {    if (begin_zhong == end_zhong)        return NULL;    tree r = new node();    r->val = a[end_hou];    int i, t = a[end_hou];    for (i = begin_zhong; i < end_zhong; ++i)        if (t == b[i])             break;    r->left = Du(end_hou - (end_zhong - i), begin_zhong, i);    r->right = Du(end_hou - 1, i + 1, end_zhong);    return r;}int main() {    int n, x;    cin >> n;    for (int i = 1; i > a[i];    }    int tem;    for (int i = 1; i > b[i];    }    tree root = Du(n, 1, n + 1);    if (root)        c.push(root);    while (!c.empty())    {        int n = c.size();        for (int i = 0; i < n; i++)        {            tree tem = c.front();            c.pop();            ans.push_back(tem->val);            if (tem->left)                c.push(tem->left);            if (tem->right)                c.push(tem->right);        }    }    cout > t >> tem;        a[t] = tem;        b.push_back(tem);    }    sort(b.begin(), b.end());    int sum = 0;    while (b.size() > 1) {        int temp = b[0] + b[1];        b.erase(b.begin() + 0);        b.erase(b.begin() + 0);        b.push_back(temp);        sum += temp;        sort(b.begin(), b.end());    }    int m;    cin >> m;    char s[1001];    string ss[1001];    for (int i = 0; i < m; ++i) {        for (int j = 0; j < n; ++j) {            cin >> s[j];            cin >> ss[j];        }        int x = 0, flag = 0;        for (int j = 0; j < n; ++j) {            for (int k = j + 1; k < n; ++k) {                int p = min(ss[j].length(), ss[k].length());                if (ss[j].substr(0, p) == ss[k].substr(0, p)) {                    flag = 1;                    break;                }            }            if (!flag) {                auto it = a.find(s[j]);                x += (ss[j].length() * it->second);            }            else                break;        }        if (!flag && x == sum)            cout > x >> y;        a[x][y] = 1;        a[y][x] = 1;    }    cin >> k;    while (k--) {        int h, t;        cin >> h;        if (h != n + 1) {            cout  t;            }            continue;        }        vectorc(N);        vectorb(N, false);        int flag = 1;        cin >> c[0];        b[c[0]] = true;        for (int j = 1; j < h; ++j) {            cin >> c[j];            if (!a[c[j]][c[j - 1]]) {                flag = 0;            }            b[c[j]] = true;        }        if (c[h - 1] != c[0])            flag = 0;        for (int j = 1; j  m;    vector a(n);    for (int i = 0; i < n; i++)        cin >> a[i].kucun;    for (int i = 0; i < n; i++)        cin >> a[i].shoujia;    sort(a.begin(), a.end(), cmp);    for (int i = 0; i < n; i++){        if (m > a[i].kucun){            m -= a[i].kucun;            ans += a[i].shoujia;        }        else{            ans += (a[i].shoujia / a[i].kucun * m);            break;        }    }    printf("%.2f", ans);    return 0;}
复制代码

五、 问题及办理过程

    为制止声明多个数组来存储数据,下标因排序变得杂乱,定义结构体来更高效的存储,排序,处置惩罚数据。
实验八 图的应用 :列出连通集

一、 题目

  7-2 列出连通集
    给定一个有N个顶点和E条边的无向图,请用DFS和BFS分别列出其所有的连通集。假设顶点从0到N−1编号。进行搜索时,假设我们总是从编号最小的顶点出发,按编号递增的顺序访问邻接点。
输入格式:
    <em>输入第1行给出2个整数N(0 l >> r;        b[l][r] = 1;        b[r][l] = 1;    }    for (h = 0; h < n; h++){        if (a[h])            continue;        a[h] = true;        dfs(b, a, n, h);        cout
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则


专注素材教程免费分享
全国免费热线电话

18768367769

周一至周日9:00-23:00

反馈建议

27428564@qq.com 在线QQ咨询

扫描二维码关注我们

Powered by Discuz! X3.4© 2001-2013 Comsenz Inc.( 蜀ICP备2021001884号-1 )