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

实验一线性表的基本操作实现及其应用实验一线性表的基本操作实现及其应用实验一线性表的基本操作实现及其应用资料仅供参考文件编号：2022年4月实验一线性表的基本操作实现及其应用版本号：A修改号：1页次：1.0审核：批准:发布日期：实验一线性表的基本操作实现及其应用一、实验目的1、熟练掌握线性表的基本操作在两种存储结构上的实现。2、会用线性链表解决简单的实际问题。二、实验内容题目一、该程序的功能是实现单链表的定义和操作。该程序包括单链表结构类型以及对单链表操作的具体的函数定义和主函数。其中，程序中的单链表（带头结点）结点为结构类型，结点值为整型。单链表操作的选择以菜单形式出现，如下所示：pleaseinputtheoperation：1.初始化2.清空3.求链表长度4.检查链表是否为空5.检查链表是否为满6.遍历链表（设为输出元素）7.从链表中查找元素8.从链表中查找与给定元素值相同的元素在表中的位置9.向链表中插入元素10.从链表中删除元素其他键退出。。。。。其中黑体部分必做题目二、约瑟夫环问题：设编号为1，2，3，……，n的n(n>0)个人按顺时针方向围坐一圈，每个人持有一个正整数密码。开始时任选一个正整数做为报数上限m，从第一个人开始顺时针方向自1起顺序报数，报到m时停止报数，报m的人出列，将他的密码作为新的m值，从他的下一个人开始重新从1报数。如此下去，直到所有人全部出列为止。令n最大值取30。要求设计一个程序模拟此过程，求出出列编号序列。structnodeMain函数Main函数初始化链表调用菜单函数1.清空2.求链表长度3.检查链表是否为空4.遍历链表5.按位置查找元素6.按值查找元素7.向链表中插入元素8.从链表中删除元素9.退出等待选择，等输入1-9时，调用对应函数，否则退出程序结束输入1-9输入非1-9程序调试及运行结果分析1．进入选择界面后，先选择7，进行插入： 2.选择4，进行遍历，结果为：选择2，得出当前链表长度.4.选择3，得出当前链表为.选择分别选择5、6进行测试.选择8，分别按位置和元素值删除.选择9，或非1-8的字符，程序结束.实验总结 通过这次实验，我对线性链表有了更深的理解，深入明白了线性存储结构与链式存储结构在内存存储的不同特点，同时我还学会了用这些知识实际解决一些问题，能够更加熟练地将算法转化为实际程序。同时，在写程序和调试程序的过程中，学会了一些书写技巧和调试技巧，这对于自己能在短时间高效的写出正确地程序有很大作用。四、主要算法流程图及程序清单主要算法流程图： (1)从单链表表中查找与给定元素值相同的元素在链表中的位置p=p->nextp&&!(p->data==x)p=p->nextp&&!(p->data==x)true调用函数，传入参数L，xp=L->nextfalse返回p调用函数，传入参数调用函数，传入参数L，i，x建立新结点s，令s->data=x;p=L->nexti==1p=nullfalseL->next=s;s->next=NULL;trueL->next=s;s->next=p;j=1j<i-1&&pp=p->nextj++trueq=p->next;p->next=s;s->next=q;P不为空返回对应值FalseFalse 程序清单：#include<iostream>usingnamespacestd;#include<>#include<>/*预处理命令*/#defineOK1;#defineERROR0;#defineOVERFLOW-1;/*单链表的结点类型*/typedefstructLNode{ intdata; structLNode*next;}LNode,*LinkedList;/*初始化单链表*/LinkedListLinkedListInit(){ 空"<<endl; cout<<"\t\t\t"<<"2.求链表长度"<<endl; cout<<"\t\t\t"<<"3.检查链表是否为空"<<endl; cout<<"\t\t\t"<<"4.遍历链表"<<endl; cout<<"\t\t\t"<<"5.从链表中查找元素"<<endl; cout<<"\t\t\t"<<"6.从链表中查找与给定元素值相同的元素在表中的位置"<<endl; cout<<"\t\t\t"<<"7.向链表中插入元素"<<endl; cout<<"\t\t\t"<<"8.从链表中删除元素"<<endl; cout<<"\t\t\t"<<"9.退出"<<endl;}/*主函数*/intmain(){ 链表长度 case2:{ cout<<"\t\t\t链表长度为："<<LinkedListLength(L)<<endl; getch(); } break; 查链表是否为空 case3:{ if(!LinkedListEmpty(L)) { cout<<"\t\t\t链表不为空！"<<endl; } else { cout<<"\t\t\t链表为空！"<<endl; } getch(); } break; 历链表 case4:{ LinkedListTraverse(L); getch(); } break; 链表中查找元素 case5:{ cout<<"\t\t\t请输入要查询的位置i："; intj; cin>>j; if(LinkedListGet(L,j)) { cout<<"\t\t\t位置i的元素值为："<<LinkedListGet(L,j)->data<<endl; } else { cout<<"\t\t\ti大于链表长度！"<<endl; } getch(); } break; 链表中查找与给定元素值相同的元素在表中的位置 case6:{ cout<<"\t\t\t请输入要查找的元素值："; intb; cin>>b; if(LinkedListGet1(L,b)) { cout<<"\t\t\t要查找的元素值位置为："<<LinkedListGet1(L,b)<<endl; cout<<"\t\t\t要查找的元素值内存地址为："<<LinkedListLocate(L,b)<<endl; } else { cout<<"\t\t\t该值不存在！"<<endl; } getch(); } break; 链表中插入元素 case7:{ cout<<"\t\t\t请输入要插入的值：";intx;cin>>x; cout<<"\t\t\t请输入要插入的位置：";intk;cin>>k; if(LinkedListInsert(L,k,x)) { cout<<"\t\t\t插入成功！"<<endl; } else { cout<<"\t\t\t插入失败！"<<endl; } getch(); } break; 链表中删除元素 case8:{ cout<<"\t\t\t1.按位置删除"<<endl; cout<<"\t\t\t2.按元素删除"<<endl; intd; cout<<"\t\t请选择：";cin>>d; switch(d) { case1:{ cout<<"\t\t\t请输入删除位置："; cin>>d; inty; if(LinkedListDel(L,d,y)) { cout<<"\t\t\t"<<y<<"被删除！"<<endl; } else { cout<<"\t\t\t删除失败！"<<endl; } }break; case2:{ cout<<"\t\t\t请输入删除元素："; inty; cin>>y; if(LinkedListDel(L,y)) { cout<<"\t\t\t"<<y<<"被删除！"<<endl; } else { cout<<"\t\t\t删除失败！"<<endl; } } } getch(); } break; } } return1;}题二约瑟夫环问题算法、思想为了解决这一问题，可以先定义一个长度为30（人数）的数组作为线性存储结构，并把该数组看成是一个首尾相接的环形结构，那么每次报m的人，就要在该数组的相应位置做一个删除标记，该单元以后就不再作为计数单元。这样做不仅算法较复杂，而且效率低，还要移动大量的元素。用单循环链表来解决这一问题，实现的方法相对要简单得的多。首先定义链表结点，单循环链表的结点结构与一般单链表的结点结构完全相同，只是数据域用一个整数来表示位置；然后将它们组成一个具有n个结点的单循环链表。接下来从位置为1的结点开始数，数到第m个结点，就将此结点从循环链表中删去，然后再从删去结点的下一个结点开始数起，数到第m个结点，再将其删去，如此进行下去，直至全部删去为止。代码分析创建单循环链表structLink{ intData; Link*next;};Link*Creat(intn){ Link*head,*s,*r; head=newLink; r=head; for(inti=0;i<n;i++) { s=newLink; cin>>s->Data; r->next=s; r=s; }r->next=head->next; returnhead;}“约瑟夫环”的操作模块；Link*Jose(Link*p,intm){ ints=m; if(p==p->next) returnp;//递归出口即循环链表只剩下一个结点，将该结点指针返回 Link*q=NULL;//指针q用来保存删除结点的前驱 for(intj=1;j<s;j++) { q=p; p=p->next; }//查找要删除结点 q->next=p->next;//删除节点 cout<<p->Data<<"";//输出结点序号 Jose(p->next,s);//递归调用}主程序intmain(){ cout<<"请输入Jose环中人数："; intn,m; cin>>n; cout<<"请输入每个人手中的序号："<<endl; Link*head=Creat(n); cout<<"请输入报数的数值"; cin>>m; Link*p=head->next; cout<<endl; cout<<"离开的序号依次是："; Link*Result=Jose(p,m); cout<<Result->Data<<endl; return0;}测试数据调试分析1、早期程序只写了约瑟夫环的实现部分，没有对输入数据进行筛选，调试的时候会经常出错。比如是输入字母，或者输入0，大于32767溢出；2、早期的循环过程中没有进行优化，导致循环次数过多，浪费时间；3、为了输出时美观，分别在input和main函数主体内做了两次，输入非零的判断，浪费了资源；4、算法的时空分析为了限制在输入过程中不会上溢，只在输入中限定为四个不全为零的数字，但是做的是do……whil