实验一线性表的基本操作实现及其应用.pdf

《实验一线性表的基本操作实现及其应用.pdf》由会员分享，可在线阅读，更多相关《实验一线性表的基本操作实现及其应用.pdf（16页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、实验 一线性表的基本操作实现及其应用一、实验目的1、熟练掌握线性表的基本操作在两种存储结构上的实现。2、会用线性链表解决简单的实际问题。二、实验内容题目一、该程序的功能是实现单链表的定义和操作。该程序包括单链表结构类型以及对单链表操作的具体的函数定义和主函数。其中，程序中的单链表（带头结点）结点为结构类型，结点值为整型。单链表操作的选择以菜单形式出现，如下所示：please input the operation：1.初始化 2.清空 3.求链表长度 4.检查链表是否为空 5.检查链表是否为满 6.遍历链表（设为输出元素）7.从链表中查找元素8.从链表中查找与给定元素值相同的元素在表中的位置9

2、.向链表中插入元素 10.从链表中删除元素其他键退出。其中黑体部分必做题目二、约瑟夫环问题：设编号为 1，2，3，n 的 n(n0)个人按顺时针方向围坐一圈，每个人持有一个正整数密码。开始时任选一个正整数做为报数上限 m，从第一个人开始顺时针方向自 1 起顺序报数，报到 m 时停止报数，报 m 的人出列，将他的密码作为新的 m 值，从他的下一个人开始重新从 1 报数。如此下去，直到所有人全部出列为止。令 n 最大值取 30。要求设计一个程序模拟此过程，求出出列编号序列。struct node函数流程图函数流程图Main 函数(一)程序调试及运行结果分析初始化链表调用菜单函数等待选择，等输入输

3、入 非1进入选择界面后，先选择 7，进行插入：2.选择4，进行遍历，结果为：3.选择 2，得出当前链表长度.5.选择分别选择5、6进行测试.4.选择3，得出当前链表为.6.选择 8，分别按位置和元素值删除.7.选择 9，或非 1-8 的字符，程序结束.(二)实验总结通过这次实验，我对线性链表有了更深的理解，深入明白了线性存储结构与链式存储结构在内存存储的不同特点，同时我还学会了用这些知识实际解决一些问题，能够更加熟练地将算法转化为实际程序。同时，在写程序和调试程序的过程中，学会了一些书写技巧和调试技巧，这对于自己能在短时间高效的写出正确地程序有很大作用。四、主要算法流程图及程序清单1.1.主要

4、算法流程图：主要算法流程图：(1)从单链表表中查找与给定元素值相同的元素在链表中的位置调用函数，传入参数 L，xp=L-nextp=p-nexttruep&!(p-data=xfals返回 p建立新结点 s，令s-data=x;i=1falsp=p-nextj=1truejnext=s;L-next=s;Falsq=p-next;p-next=s;返回对应值s-next=p;2.2.程序清单：程序清单：#include#includeusing namespace std;using namespace std;#include#include#include#include/*/*预处理命令

5、预处理命令*/*/#define OK 1;#define OK 1;#define ERROR 0;#define ERROR 0;#define OVERFLOW-1;#define OVERFLOW-1;/*/*单链表的结点类型单链表的结点类型*/*/typedef struct LNodetypedef struct LNode int data;int data;struct LNode*next;struct LNode*next;LNode,*LinkedList;LNode,*LinkedList;/*/*初始化单链表初始化单链表*/*/LinkedList LinkedLis

6、tInit()LinkedList LinkedListInit()空空endl;endl;coutttt2.coutttt2.求链表长度求链表长度endl;endl;coutttt3.coutttt3.检查链表是否为空检查链表是否为空endl;endl;coutttt4.coutttt4.遍历链表遍历链表endl;endl;coutttt5.coutttt5.从链表中查找元素从链表中查找元素 endl;endl;coutttt6.coutttt6.从链表中查找与给定元素值相同的元素在表中的从链表中查找与给定元素值相同的元素在表中的位置位置endl;endl;/*/*主函数主函数*/*/int

7、 main()int main()coutttt7.coutttt7.向链表中插入元素向链表中插入元素endl;endl;coutttt8.coutttt8.从链表中删除元素从链表中删除元素endl;endl;coutttt9.coutttt9.退出退出endl;endl;链表长度链表长度case 2:case 2:couttttcoutttt 链表长度为：链表长度为：LinkedListLength(L)endl;LinkedListLength(L)endl;getch();getch();break;break;查链表是否为空查链表是否为空case 3:case 3:if(!Linked

8、ListEmpty(L)if(!LinkedListEmpty(L)elseelse getch();getch();break;break;历链表历链表couttttcoutttt 链表为空！链表为空！endl;endl;couttttcoutttt 链表不为空！链表不为空！endl;endl;case 4:case 4:LinkedListTraverse(L);LinkedListTraverse(L);getch();getch();break;break;链表中查找元素链表中查找元素case 5:case 5:couttttcoutj;cinj;if(LinkedListGet(L,

9、j)if(LinkedListGet(L,j)couttttcoutttt位位置置i i的的元元素素值值为为：dataendl;dataendl;elseelse getch();getch();break;break;链表中查找与给定元素值相同的元素在表中的位置链表中查找与给定元素值相同的元素在表中的位置coutttticoutttti 大于链表长度！大于链表长度！endl;endl;case 6:case 6:couttttcoutb;cinb;if(LinkedListGet1(L,b)if(LinkedListGet1(L,b)couttttcoutttt要要 查查 找找 的的 元元

10、素素 值值 位位 置置 为为：LinkedListGet1(L,b)endl;LinkedListGet1(L,b)endl;couttttcoutttt要要 查查 找找 的的 元元 素素 值值 内内 存存 地地 址址 为为：LinkedListLocate(L,b)endl;LinkedListLocate(L,b)endl;elseelse getch();getch();break;break;链表中插入元素链表中插入元素couttttcoutttt 该值不存在！该值不存在！endl;endl;case 7:case 7:couttttcoutx;int x;cinx;couttttco

11、utk;int k;cink;if(LinkedListInsert(L,k,x)if(LinkedListInsert(L,k,x)elseelse getch();getch();break;break;链表中删除元素链表中删除元素couttttcoutttt 插入失败！插入失败！endl;endl;couttttcoutttt 插入成功！插入成功！endl;endl;case 8:case 8:coutttt1.coutttt1.按位置删除按位置删除endl;endl;coutttt2.coutttt2.按元素删除按元素删除endl;endl;int d;int d;coutttcout

12、d;cind;switch(d)switch(d)case 1:case 1:couttttcoutd;cind;int y;int y;if(LinkedListDel(L,d,y)if(LinkedListDel(L,d,y)elseelse break;break;couttttcoutttt 删除失败！删除失败！endl;endl;couttttycoutttty被删除！被删除！endl;endl;case 2:case 2:couttttcouty;ciny;if(LinkedListDel(L,y)if(LinkedListDel(L,y)elseelse couttttycout

13、ttty被删除！被删除！endl;endl;couttttcoutttt 删除失败！删除失败！endl;endl;getch();getch();break;break;return 1;return 1;题二题二约瑟夫环问题约瑟夫环问题算法、思想算法、思想为了解决这一问题，可以先定义一个长度为 30（人数）的数组作为线性存储结构，并把该数组看成是一个首尾相接的环形结构，那么每次报 m 的人，就要在该数组的相应位置做一个删除标记，该单元以后就不再作为计数单元。这样做不仅算法较复杂，而且效率低，还要移动大量的元素。用单循环链表来解决这一问题，实现的方法相对要简单得的多。首先定义链表结点，单循环链

14、表的结点结构与一般单链表的结点结构完全相同，只是数据域用一个整数来表示位置；然后将它们组成一个具有 n 个结点的单循环链表。接下来从位置为 1 的结点开始数，数到第 m 个结点，就将此结点从循环链表中删去，然后再从删去结点的下一个结点开始数起，数到第 m 个结点，再将其删去，如此进行下去，直至全部删去为止。代码分析代码分析(一)创建单循环链表struct Linkstruct Link int Data;int Data;Link*next;Link*next;Link*Creat(int n)Link*Creat(int n)Link*head,*s,*r;Link*head,*s,*r;h

15、ead=new Link;head=new Link;r=head;r=head;for(int i=0;in;i+)for(int i=0;is-Data;cins-Data;r-next=s;r-next=s;r=s;r=s;r-next=head-next;r-next=head-next;(二)“约瑟夫环”的操作模块；return head;return head;Link*Jose(Link*p,int m)Link*Jose(Link*p,int m)int s=m;int s=m;if(p=p-next)if(p=p-next)return p;/return p;/递归出口即循

16、环链表只剩下一个结点，将该结点指针返回递归出口即循环链表只剩下一个结点，将该结点指针返回 Link*q=NULL;/Link*q=NULL;/指针指针 q q 用来保存删除结点的前驱用来保存删除结点的前驱 for(int j=1;js;j+)for(int j=1;jnext;p=p-next;/查找要删除结点查找要删除结点 q-next=p-next;/q-next=p-next;/删除节点删除节点 coutData ;/coutDatanext,s);/Jose(p-next,s);/递归调用递归调用(三)主程序int main()int main()cout coutn;cinn;cou

17、t cout请输入每个人手中的序号：请输入每个人手中的序号：endl;endl;Link*head=Creat(n);Link*head=Creat(n);cout coutm;cinm;Link*p=head-next;Link*p=head-next;coutendl;coutendl;cout cout离开的序号依次是：离开的序号依次是：;Link*Result=Jose(p,m);Link*Result=Jose(p,m);coutDataendl;coutDataendl;return 0;return 0;测试数据测试数据调调分分试试析析1、早期程序只写了约瑟夫环的实现部分，没有对

18、输入数据进行筛选，调试的时候会经常出错。比如是输入字母，或者输入 0，大于 32767 溢出；2、早期的循环过程中没有进行优化，导致循环次数过多，浪费时间；3、为了输出时美观，分别在 input 和 main 函数主体内做了两次，输入非零的判断，浪费了资源；4、算法的时空分析为了限制在输入过程中不会上溢，只在输入中限定为四个不全为零的数字，但是做的是 dowhile 循环，复杂度为 o（1）;当 n 大于 1 时：在数据输入中，链表的创建是 for 循环，时间复杂度为 o（n-1）在约瑟夫环实现程序中，为 for 循环。时间复杂度为 o（m%n-1）当 n=1 时，复杂度为 o（1）。实验心得实验心得1、巩固和加深了对数据结构的理解，提高综合运用本课程所学知识的能力。2、培养了我选用参考书，查阅手册及文献资料的能力。培养独立思考，深入研究，分析问题、解决问题的能力。3、通过实际编译系统的分析设计、编程调试，掌握应用软件的分析方法和工程设计方法。4、通过课程设计，培养了我严肃认真的工作作风，逐步建立正确的生产观念、经济观念和全局观念。