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

实验一线性表的基本操作实现及其应用一、实验目的1、熟练掌握线性表的基本操作在两种存储结构上的实现。2、会用线性链表解决简单的实际问题。二、实验内容题目一、该程序的功能是实现单链表的定义和操作。该程序包括单链表结构类型以及对单链表操作的具体的函数定义和主函数。其中，程序中的单链表（带头结点）结点为结构类型，结点值为整型。单链表操作的选择以菜单形式出现，如下所示：pleaseinputtheoperation：1.初始化2.清空3.求链表长度4.检查链表是否为空5.检查链表是否为满6.遍历链表（设为输出元素）7.从链表中查找元素8.从链表中查找与给定元素值相同的元素在表中的位置9.向链表中插入元素10.从链表中删除元素其他键退出。。。。。其中黑体部分必做题目二、约瑟夫环问题：设编号为1，2，3，……，n的n(n0)个人按顺时针方向围坐一圈，每个人持有一个正整数密码。开始时任选一个正整数做为报数上限m，从第一个人开始顺时针方向自1起顺序报数，报到m时停止报数，报m的人出列，将他的密码作为新的m值，从他的下一个人开始重新从1报数。如此下去，直到所有人全部出列为止。令n最大值取30。要求设计一个程序模拟此过程，求出出列编号序列。structnode//结点结构{intnumber;/*人的序号*/intcipher;/*密码*/structnode*next;/*指向下一个节点的指针*/};三、实验步骤(一)数据结构与核心算法的设计描述1、单链表的结点类型定义/*预处理命令*/#defineOK1;#defineERROR0;#defineOVERFLOW-1;/*定义DataType,status为int类型*/typedefintDataType;typedefintstatus;/*单链表的结点类型*/typedefstructLNode{DataTypedata;structLNode*next;}LNode,*LinkedList;2、初始化单链表LinkedListLinkedListInit(){//定义并返回头结点L}3、清空单链表voidLinkedListClear(LinkedListL){//L是带头结点的链表的头指针,释放除头结点外的所有内存空间}4．检查单链表是否为空intLinkedListEmpty(LinkedListL){//L是带头结点的链表的头指针,判断头结点的next是否为空,如果空//返回OK，否则返回ERROR}5、遍历单链表voidLinkedListTraverse(LinkedListL){//L是带头结点的链表的头指针,遍历并输出L所有结点（不包括头//结点）的数据}6、求单链表的长度intLinkedListLength(LinkedListL){//L是带头结点的链表的头指针，通过遍历链表用i记录结点个数（不//包括头结点），并返回i}7、从单链表表中查找元素LinkedListLinkedListGet(LinkedListL,inti){//L是带头结点的链表的头指针,返回第i个元素}8、从单链表表中查找与给定元素值相同的元素在链表中的位置（位置）intLinkedListGet1(LinkedListL,DataTypex){//L是带头结点的链表的头指针,返回值为x元素在链表中的位置的//位置}9、从单链表表中查找与给定元素值相同的元素在链表中的位置（指针）LinkedListLinkedListLocate(LinkedListL,DataTypex){//L是带头结点的链表的头指针,返回值为x元素的指针}10、向单链表中插入元素statusLinkedListInsert(LinkedListL,inti,DataTypex){}(二)函数调用及主函数设计图1.主函数流程图(三)程序调试及运行结果分析1．进入选择界面后，先选择7，进行插入：Main函数初始化链表调用菜单函数1.清空2.求链表长度3.检查链表是否为空4.遍历链表5.按位置查找元素6.按值查找元素7.向链表中插入元素8.从链表中删除元素9.退出等待选择，等输入1-9时，调用对应函数，否则退出程序结束输入1-9输入非1-92.选择4，进行遍历，结果为：3.选择2，得出当前链表长度.4.选择3，得出当前链表为.5.选择分别选择5、6进行测试.6.选择8，分别按位置和元素值删除.7.选择9，或非1-8的字符，程序结束.(四)实验总结通过这次实验，我对线性链表有了更深的理解，深入明白了线性存储结构与链式存储结构在内存存储的不同特点，同时我还学会了用这些知识实际解决一些问题，能够更加熟练地将算法转化为实际程序。同时，在写程序和调试程序的过程中，学会了一些书写技巧和调试技巧，这对于自己能在短时间高效的写出正确地程序有很大作用。四、主要算法流程图及程序清单1.主要算法流程图：(1)从单链表表中查找与给定元素值相同的元素在链表中的位置p=p-nextp&&!(p-data==x)true调用函数，传入参数L，xp=L-nextfalse返回p2.程序清单：#includeiostreamusingnamespacestd;#includeconio.h#includestdlib.h/*预处理命令*/#defineOK1;#defineERROR0;#defineOVERFLOW-1;/*单链表的结点类型*/typedefstructLNode{intdata;调用函数，传入参数L，i，x建立新结点s，令s-data=x;p=L-nexti==1p=nullfalseL-next=s;s-next=NULL;trueL-next=s;s-next=p;j=1ji-1&&pp=p-nextj++trueq=p-next;p-next=s;s-next=q;P不为空返回对应值FalseFalsestructLNode*next;}LNode,*LinkedList;/*初始化单链表*/LinkedListLinkedListInit(){//定义并返回头结点LinkedListL;L=(LinkedList)malloc(sizeof(LNode));L-next=NULL;returnL;}/*清空单链表*/voidLinkedListClear(LinkedListL){//释放除头结点外的所有内存空间LinkedListp=L-next,q;L-next=NULL;while(p){q=p-next;free(p);p=q;}cout\t\t\t已清空！endl;}/*检查单链表是否为空*/intLinkedListEmpty(LinkedListL){//判断头结点的next是否为空,如果空返回OK，否则返回ERRORif(!(L-next))returnOK;returnERROR;}/*遍历单链表*/voidLinkedListTraverse(LinkedListL){//遍历并输出L所有结点（不含头结点）的数据LinkedListp=L-next;if(!p){cout\t\t\t链表为空！endl;}cout\t\t;while(p){coutp-data\t;p=p-next;}coutendl;}/*求单链表的长度*/intLinkedListLength(LinkedListL){//通过遍历链表用i记录结点个数（不含头结点），并返回iLinkedListp=L-next;inti=0;while(p){i++;p=p-next;}returni;}/*从单链表表中查找元素*/LinkedListLinkedListGet(LinkedListL,inti){//L是带头结点的链表的头指针,返回第i个元素LinkedListp=L-next;intj=1;while(ji&&p){p=p-next;j++;}if(!p){returnNULL;}returnp;}/*从链表中查找与给定元素值相同的元素在表中的位置,返回位置*/intLinkedListGet1(LinkedListL,intx){//L是带头结点的链表的头指针,返回值为x元素的位置LinkedListp=L-next;inti=1;while(p&&!(p-data==x)){i++;p=p-next;}if(!p){return0;}returni;}/*从单链表表中查找与给定元素值相同的元素在链表中的位置*/LinkedListLinkedListLocate(LinkedListL,intx){//L是带头结点的链表的头指针,返回值为x元素的指针LinkedListp=L-next;while(p&&!(p-data==x)){p=p-next;}if(!p){returnNULL;}returnp;}/*向单链表中插入元素*/intLinkedListInsert(LinkedListL,inti,intx){//L为带头结点的单链表的头指针，本算法//在链表中第i个结点之前插入新的元素xLinkedLists=(LinkedList)malloc(sizeof(LNode));s-data=x;LinkedListp=L-next,q;if(i==1){if(p==NULL){L-next=s;s-next=NULL;returnOK;}else{L-next=s;s-next=p;returnOK;}}intj=1;while(ji-1&&p){p=p-next;j++;}if(!p){free(s);returnERROR;}q=p-next;p-next=s;s-next=q;returnOK;}/*从单链表中删除元素*/intLinkedListDel(LinkedListL,intx){//删除以L为头指针的单链表中值为x结点LinkedListp=L-next,q=L;while(p&&!(p-data==x)){q=p;p=p-next;}if(!p){returnERROR;}q-next=p-next;free(p);returnOK;}intLinkedListDel(LinkedListL,inti,int&x){//删除以L为头指针的单链表中第i个结点,并返回x的值LinkedListp=L-next,q=L;intj=1;while(j=i-1&&p){q=p;p=p-next;j++;}if(!p){x=0;returnERROR;}q-next=p-next;x=p-data;free(p);returnOK;}/*菜单显示*/voidScreenShow(){cout\t\t\t1.清空endl;cout\t\t\t2.求链表长度endl;cout\t\t\t3.检查链表是否为空endl;cout\t\t\t4.遍历链表endl;cout\t\t\t5.从链表中查找元素endl;cout\t\t\t6.从链表中查找与给定元素值相同的元素在表中的位置endl;cout\t\t\t7.向链表中插入元素endl;cout\t\t\t8.从链表中删除元素endl;cout\t\t\t9.退出endl;}/*主函数*/intmain(){//初始化链表inti=1;LinkedListL=LinkedListInit();if(L){cout\t\t\t初始化成功！\nendl;}//显示菜单ScreenShow();//进行选择，当选择为1-8时，进行对应功能函数调用，否则退出程序while(i=1&&i=8){cout\t\t请选择：;cini;switch(i){//1、清空链表case1:Lin