数据结构实验报告(2015级)及答案

《数据结构》实验报告专业__信息管理学院______年级__2015级___________学号__________学生姓名___________指导老师____________华中师范大学信息管理系编2I实验要求1．每次实验中有若干习题，每个学生至少应该完成其中的两道习题。2．上机之前应作好充分的准备工作，预先编好程序，经过人工检查无误后，才能上机，以提高上机效率。3．独立上机输入和调试自己所编的程序，切忌抄袭、拷贝他人程序。4．上机结束后，应整理出实验报告。书写实验报告时，重点放在调试过程和小节部分，总结出本次实验中的得与失，以达到巩固课堂学习、提高动手能力的目的。II实验内容实验一线性表【实验目的】1．熟悉VC环境，学习如何使用C语言实现线性表的两种存储结构。2．通过编程、上机调试，进一步理解线性表的基本概念,熟练运用C语言实现线性表基本操作。3．熟练掌握线性表的综合应用问题。【实验内容】1．一个线性表有n个元素（nMAXSIZE,MAXSIZE指线性表的最大长度），且递增有。现有一元素x要插入到线性表的适当位置上，并保持线性表原有的顺序不变。设计程序实现。要求：采用顺序存储表示实现；采用链式存储表示方法实现；比较两种方法的优劣。2.从单链表中删除指定的元素x，若x在单链表中不存在，给出提示信息。要求：①指定的值x由键盘输入；②程序能处理空链表的情况。3．设有头结点的单链表，编程对表中的任意值只保留一个结点，删除其余值相同的结点。要求：①该算法用函数（非主函数）实现；②在主函数中调用创建链表的函数创建一个单链表，并调用该函数，验证算法的正确性。LinkedListExchange（LinkedListHEAD，p）∥HEAD是单链表头结点的指针，p是链表中的一个结点。本算法将p所指结点与其后继结点交换。{q=head-next；∥q是工作指针，指向链表中当前待处理结点。pre=head；∥pre是前驱结点指针，指向q的前驱。while（q!=null&&q!=p）{pre=q；q=q-next；}∥未找到p结点，后移指针。if（p-next==null）printf（“p无后继结点\n”）;∥p是链表中最后一个结点，无后继。else∥处理p和后继结点交换{q=p-next；∥暂存p的后继。pre-next=q；∥p前驱结点的后继指向p的后继。p-next=q-next；∥p的后继指向原p后继的后继。q-next=p；∥原p后继的后继指针指向p。}}∥算法结束。4．已知非空单链表第一个结点由head指出，请写一算法，交换p所指结点与其下一个结点在链表中3的位置。要求：①该算法用函数Reverse(head,p)实现，其中head为表头指针，p指向要交换的结点；②在主函数中调用创建链表的函数创建一个单链表，并调用该函数，验证算法的正确性。5．设有一个单链表，编写能够完成下列功能的算法：①找出最小值的结点，且打印该数值；②若该数值是奇数，则将其与直接后继结点交换；③若该数值是偶数，则将其直接后继结点删除。要求：编写主函数验证算法的正确性。6．在一链表中，已知每个结点含有三个域：data、next和prior，其中prior域为空，设计一个算法，使每个结点的prior指向它的前驱结点，形成双向循环链表。要求：①建立一个结点中含有三个域的单链表；②在主函数中调用此算法，构成双向循环链表；③在主函数中利用正向和逆向两种方式输出链表中的数据，验证算法的正确性。7．用链表建立通讯录。通讯录内容有：姓名、通讯地址、电话号码。要求：①通讯录是按姓名项的字母顺序排列的；②能查找通讯录中某人的信息；提示：可用链表来存放这个通讯录，一个人的信息作为一个结点。成链的过程可以这样考虑：先把头结点后面的第一个数据元素结点作为链中的首结点，也是末结点。从第二个数据开始逐一作为‘工作结点’，需从链表的首结点开始比较，如果‘工作结点’的数据比链中的‘当前结点’的数据小，就插在其前面。否则，再看后面是否还有结点，若没有结点了就插在其后面成为末结点；若后面还有结点，再与后面的结点逐一比较处理。4【实验报告】实习时间：2016/10/14实习地点：实习机号：具体实验内容作了1，2，3，4，5，6题1题采用顺序存储表示实现的算法：主数：运行结果：5算法代码：boolInsert_Sq(SqList&L,ElemTypex){inti;if(L.length=L.listsize){L.elem=(ElemType*)realloc(L.elem,(L.listsize+L.incrementsize)*sizeof(ElemType));if(!L.elem)returnfalse;L.listsize+=L.incrementsize;}for(i=L.length-1;xL.elem[i]&&i=0;i--)L.elem[i+1]=L.elem[i];L.elem[i+1]=x;L.length++;returntrue;}采用链表实现的算法：6主函数：运行结果：7算法代码：voidInsert_L(LinkList&L,ElemTypex){LinkListp,q,m;p=L-next;q=L;while(p){if(xp-data&&p-next){p=p-next;q=q-next;}elseif(xp-data&&!(p-next)){m=(LinkList)malloc(sizeof(LNode));m-data=x;p-next=m;m-next=NULL;return;}else{m=(LinkList)malloc(sizeof(LNode));m-data=x;m-next=p;q-next=m;return;}}}比较两种算法的优劣：顺序表和链表都要和x逐项比较，顺序表找到x应放的位置之后插入，后面的元素都要向后移位，但链表只需修改指针即可，链表相对易操作一些82题算法：主函数：代码：voidDelete_L(LinkList&L){ElemTypex;9cout请输入元素x:;cinx;LinkListp,q;p=L;if(!(p-next)){cout链表不存在endl;return;}while(p-next){if(x==p-next-data&&p-next-next){q=p-next;p-next=q-next;free(q);return;}elseif(x==p-next-data&&!(p-next-next)){q=p-next;p-next=NULL;free(q);return;}p=p-next;}coutx不存在endl;return;}结果：103题算法：主函数：运行结果：11算法代码：voidDeleteRepeat_L(LinkList&L){LinkListp,q,m;p=L-next;while(p-next!=NULL){q=p;while(q-next!=NULL){if(q-next-data==p-data){m=q-next;q-next=m-next;free(m);}elseq=q-next;}p=p-next;}}4题算法：12主函数：头文件并且定义了全局变量：运行结果：算法代码：voidReverse_L(LinkList&head,LinkListp){LinkListq,pre;q=head-next;pre=head;while(q!=NULL&&q!=p){pre=q;q=q-next;}13if(p-next==NULL)cout无后继结点endl;else{q=p-next;pre-next=q;p-next=q-next;q-next=p;}return;}5题算法：14主函数：操作结果：15算法代码：voidfindmin_L(LinkList&L){ElemTypee;LinkListp,q,pre,q_pre;p=L-next;pre=L;e=p-data;while(p){if(ep-data){e=p-data;q=p;q_pre=pre;}p=p-next;pre=pre-next;}cout最小值为：eendl;if(e%2&&!q-next||!(e%2)&&!q-next)cout该最小值结点的后继为空，不进行操作。endl;elseif(e%2&&q-next){LinkListm;m=q-next;q_pre-next=m;q-next=m-next;m-next=q;cout此最小值为奇数，将其与直接后继结点交换。endl;}else{LinkListm;m=q-next;16q-next=m-next;free(m);cout此最小值为偶数，将其直接后继结点删除。endl;}}6题算法：主函数：17头文件及定义的结构体：算法代码：voidbuild_circle(DuLinkList&head){DuLinkListm,n;18m=head;while(m-next-data!=0){m-next-prior=m;m=m-next;}m-next-prior=m;}结果：19程序调试过程程序运行过程出现的错误1题：用顺序表操作比较顺利，但用链表进行比较时，找到相应位置后，插入过程出现错误，编的错误代码使插入的操作变为替换后边的紧邻结点的操作2题：编写过程无错误3题：算法思想是第一个结点的数和后面的依次比较，如果相等，就删掉，然后再从第二个节点继续做和第一个结点一样的事，直到最后为空，但我在编的过程中却不知如何实现此操作，后来百度了一下：让循环套循环，内层的循环让固定一个结点的数依次和后面的比较，相同的删除，内部结束后p=p-next;然后再做相同的操作，直到结点最后。4题：（1）此题定义了全局变量，但是一开始编程序时，却莫名其妙在主函数里又定义了一次，此时，操作的就是主函数里的这个m，而全局变量没有进行任何操作，因而在编的函数里用m时，程序会出现错误。（2）在调换两结点位置时，有发生错误。5题：（1）在求最小值并执行完p=p-next之后,p指向空值，但在初编此程序时，却想当然以为p求出最小值后指向最小值所在结点，因而在后面if(e%2&&!q-next||!(e%2)&&!q-next)中，这个判断条件始终为真，因为此时q=NULL。（2）一开始直接在程序中给a[i]赋值，而不是通过输入给a[i]值，固定的一组数不能全面检验，应该试验多组数，特别是比较刁钻苛刻的数题6：(1)在定义DuLinkListp,q,head,k;后，head=p;建立链表后并p-next=head;为了也给k赋头结点，写成了p-next=head=k;但这样却使head前继后继都变为空了。(2)在循环输入一组整数时，用的是cina;，然后在输入数的时候直接：234567890这样输入，但是由于cin任何类型都可以输入，所以空格也会被输入，因而出现错误，如果用cin输入整数，可以借助数组，inta[5];for(i=0;i5;i++)cina[i];20实习小结在编代码过程中出现的若干错误，有一部分是本来就不知道，有一些事由于不熟练，不熟悉所以导致错误，也有一些是由于马虎。当编码可以通过却无法产生结果时，通过逐步地调试，可以发现出错地方以及出错的原因，我觉得调试的过程就是不断进步，自我纠错的过程。编出代码，运行，改正，再完善---在这个过程中，编写代码的思维就更完善，更熟练，犯得低级错误也会越来越少。实验二堆栈与队列【实验目的】1．学习如何使用C语言实现堆栈与队列。2．熟悉堆栈与队列的基本操作及应用。【实验内容】1．现有一顺序循环队列，其结构描述为：#defineMAX100typedefst