1、数据结构实验报告专 业 _信息管理学院_年 级 _2015 级_学 号 _ _学生姓名 _ _ _指导老师 _华中师范大学信息管理系编2I 实验要求1每次实验中有若干习题，每个学生至少应该完成其中的两道习题。2上机之前应作好充分的准备工作，预先编好程序，经过人工检查无误后，才能上机，以提高上机效率。3独立上机输入和调试自己所编的程序，切忌抄袭、拷贝他人程序。4上机结束后，应整理出实验报告。书写实验报告时，重点放在调试过程和小节部分，总结出本次实验中的得与失，以达到巩固课堂学习、提高动手能力的目的。II 实验内容实验一 线性表【实验目的】1熟悉 VC 环境，学习如何使用 C 语言实现线性表的两种
2、存储结构。2通过编程、上机调试，进一步理解线性表的基本概念,熟练运用 C 语言实现线性表基本操作。3熟练掌握线性表的综合应用问题。【实验内容】1一个线性表有 n 个元素（nnext； q 是工作指针，指向链表中当前待处理结点。pre=head； pre 是前驱结点指针，指向 q 的前驱。 while（q!=null p 是链表中最后一个结点，无后继。 else 处理 p 和后继结点交换 q=p-next； 暂存 p 的后继。 pre-next=q； p 前驱结点的后继指向 p 的后继。p-next=q-next；p 的后继指向原 p 后继的后继。 q-next=p ；原 p 后继的后继指针指向
3、 p。 算法结束。4已知非空单链表第一个结点由 head 指出，请写一算法，交换 p 所指结点与其下一个结点在链表3中的位置。要求：该算法用函数 Reverse(head,p)实现，其中 head 为表头指针，p 指向要交换的结点；在主函数中调用创建链表的函数创建一个单链表，并调用该函数，验证算法的正确性。5设有一个单链表，编写能够完成下列功能的算法：找出最小值的结点，且打印该数值；若该数值是奇数，则将其与直接后继结点交换；若该数值是偶数，则将其直接后继结点删除。要求：编写主函数验证算法的正确性。6在一链表中，已知每个结点含有三个域：data、next 和 prior，其中 prior 域为空
4、，设计一个算法，使每个结点的 prior 指向它的前驱结点，形成双向循环链表。要求：建立一个结点中含有三个域的单链表；在主函数中调用此算法，构成双向循环链表；在主函数中利用正向和逆向两种方式输出链表中的数据，验证算法的正确性。7用链表建立通讯录。通讯录内容有：姓名、通讯地址、电话号码。要求：通讯录是按姓名项的字母顺序排列的；能查找通讯录中某人的信息；提示：可用链表来存放这个通讯录，一个人的信息作为一个结点。成链的过程可以这样考虑：先把头结点后面的第一个数据元素结点作为链中的首结点，也是末结点。从第二个数据开始逐一作为工作结点 ，需从链表的首结点开始比较，如果工作结点的数据比链中的当前结点的数据
5、小，就插在其前面。否则，再看后面是否还有结点，若没有结点了就插在其后面成为末结点；若后面还有结点，再与后面的结点逐一比较处理。4【实验报告】实习时间：2016/10/14 实习地点： 实习机号：具体实验内容作了 1，2，3，4，5，6 题1 题采用顺序存储表示实现的算法：主数：运行结果：19算法代码：bool Insert_Sq(SqList if(L.length=L.listsize)L.elem=(ElemType *)realloc(L.elem,(L.listsize+L.incrementsize)*sizeof(ElemType);if(!L.elem) return false
6、;L.listsize+=L.incrementsize;for(i=L.length-1;x=0;i-)L.elemi+1=L.elemi;L.elemi+1=x;L.length+;return true;采用链表实现的算法：20主函数：运行结果：21算法代码：void Insert_L(LinkList p=L-next;q=L;while(p)if(xp-dataq=q-next;else if(xp-datam-data=x;p-next=m;m-next=NULL;return; else m=(LinkList)malloc(sizeof(LNode);m-data=x;m-ne
7、xt=p;q-next=m;return; 比较两种算法的优劣：顺序表和链表都要和 x 逐项比较，顺序表找到 x 应放的位置之后插入，后面的元素都要向后移位，但链表只需修改指针即可，链表相对易操作一些222 题算法：主函数：代码：void Delete_L(LinkList 23coutx;LinkList p,q;p=L;if(!(p-next) coutnext)if(x=p-next-datap-next=q-next;free(q);return ;else if(x=p-next-datap-next=NULL;free(q);return; p=p-next; cout“x 不存在“endl;return; 结果：243 题算法：主函数：运行结果：
