《合工大宣城校区数据结构实验报告——单链表精编版.docx》由会员分享，可在线阅读，更多相关《合工大宣城校区数据结构实验报告——单链表精编版.docx（11页珍藏版）》请在三一文库上搜索。
1、最新资料推荐数据结构实验报告姓名学号专业班级指导教师实验时间11月9日实验地占 八、计算中心实验二单链表实验1 .实验目标熟练掌握线性表的链式存储结构。熟练掌握单链表的有关算法设计。 根据具体问题的需要，设计出合理的表示数据的链式存储结构， 并设计相关算 法。2 .实验内容和要求I实验要求 本次实验中的链表结构指带头结点的单链表 单链表结构和运算定义，算法的实现以库文件方式实现，不得在测试主程序中 直接实现；比如存储、算法实现放入文件：linkedList.h 实验程序有较好可读性，各运算和变量的命名直观易懂，符合软件工程要求；程序有适当的注释。U实验内容尾插法创建单链表，打印创建结果 2不插
2、法创建单链表，打印创建结果。 3小肖毁单链表。求链表长度。求单链表中第i个元素（函数），若不存在，报错。在第i个结点前插入值为x的结点 7避表中查找元素值为x的结点，成功返回结点指针，失败报错删除单链表中第i个元素结点在一个递增有序的单链表L中插入一个值为x的元素，并保持其递增有序特性将单链表L中的奇数项和偶数项结点分解开（元素值为奇数、偶数），分别放入新的单链表中，然后原表和新表元素同时输出到屏幕上，以便对照求解结果求两个递增有序单链表L1和L2中的公共元素，放入新的单链表 L3中删除递增有序单链表中的重复元素，要求时间性能最好13增有序单链表L1、L2,不申请新结点，利用原表结点对 2表进
3、行合并，并使得合并后成为一个集合，合并后用L1的头结点作为头结点，删除L2的头结点，要求时间性能最好扩展实验： （递增有序）单链表表示集合 A、B,实现：C=A B, C=A B, C=A-BA=A B, A=A B, A=A-B1 最新资料推荐 (递增有序)单链表表示集合 A、B,判定A是否B的子集已知一个带有表头结点的单链表，结点结构如下图。假设该链表只给出了头指针list o在不改变链表的前提下，请设计一个尽可能高效的算法，查找 链表中倒数第k个位置上的结点(k为正整数)。若查找成功，算法输出该结 点的data值，并返回1;否则，只返回0o八人上L/2(2011) (15分)一个长度为L
4、 (L1)的升序序列S,处在第个位置的数称为S的中位数。例如，若序列S1=(11, 13, 15, 17, 19),则S1的中位数是15。两个序列的中位数是含它们所有元素的升序序列的中位数。例如，若S2=(2, 4, 6, 8, 20),则S1和S2的中位数是11。现有两个等长升序序列A和B,试设计一个在时间和空间两方面都尽可能高效的算法，找出两个序列A和B的中位数3 .数据结构设计struct Nodeint value;Node *next;Node(int value = 0, Node *pNext = 0)this-value = value;this-next = pNext;cl
5、ass linkedListpublic :linkedList()； / 构造函数linkedList() ； /析构函数，销毁单链表int length()； / 求链表长度Node *listLocateI(int i)；/求单链表中第i个元素bool listInsert(int i,int x)；/在第i个结点前插入值为x的结点Node *listLocateX(int x) ； /链表中查找元素值为 x的结点，成功返回结点指针，失败报错。bool listDelete(int i); /删除单链表中第i个元素结点Node *head;4 .算法设计8吻书中已经给出的基本算法，.定义
6、一个指针p指向头结点，当p-next != NULL ,循环比较 p-next-value 与 x 的值之间的大小，若 p-next-valuenext ,当申请新结点，存储x,将新结点插入在p之后，完成插入。.定义两个链表L1, L2,定义指针*p, *u , *r ,分别指向L的首元素结 点，L1, L2的头结点上，循环判断，如果 p-value%2!=0 ,就插入到表L1 中，否则，就插入到表L2中，然后令p=p-next ,直至p!=NULL结束循环， 输出L1, L2,其中L1表示奇结点，L2表示偶结点.定义两个链表L3,定义指针*p, *u, *r,分别指向L3的头结点，L1, L
7、2的首元素结点上，循环判断，如果u-value=r-value ,就把该值插入到 表 L3 中，如果 u-valuer-value ,让 r=r-next ,否贝让 u=u-next ;当 u=NULU者r=NULL结束循环，输出L3;.将元素分为两部分，一部分是已经处理元素，和待处理元素。用r指向 最后一个已经处理元素，用u指向还未处理的元素，如果 u-value value ,就让u-next=r ,删除中间的重复元素，否则就令 r=r-next ,当 r=NULL结束循环，令 u-next=NULL,输出 L.定义指针*p1,*p2,*u ；p1,p2分别指向L1的头结点和L2的首元素结
8、点， 判断p1-next-value 与p2-value大小，前者大，则将p2插入到p1后面, 后者大则让 p1=p1-next ,相等则 p2=p2-next , p1=p1-next ,当 p1-next =NULLl p2=NUL的束循环。若p2 !=NULL,直接将其接到p1之后，删除 L2.head,输出 L1.扩展实验：.对于采用集合C的运算，将符合要求的元素插入到新链表 C中，对于不 采用链表C的运算，就对链表A中元素进行插入与删除操作。.使用两个指针*u, *r ,分别指向A, B的首元素结点，对A中元素按顺序 进行判断，如果出现u-valuevalue ,则表示A不为B的子集
9、，如果 u-valuer-value ，贝U r = r-next , 如果 u-value=r-value, 贝U u = u-next , r = r-next ,如果对A中每个元素进行判断，均可在 B中找到， 则A为B的子集。.采用两个指针*u = L.head , *r = L.head-next ,加入一个计数器i, i 表示已经经过的结点，r每移动一次，i+,当ik, u开始移动，当r移动 到表尾时，u即指向倒数第k个位置上的结点；若u为头结点，则其未移动， 表示无倒数第k个位置上的结点。.因为两个序列A和B等长升序，故只需按照递增有序的顺序找到第A.length()即可，可以对A
10、, B元素进行排序，到第 A.length()结束即可输出该值为中位数。5.运行和测试菜单:慰,若不存在，报错篙二张动返回结点指针，失败报借鼠星:就单播表L珅枭露挈嘉对麻进行合并，并使得合押后成为一个集合.合并后用L1的头结点作为头结点用尾差法）位置上的结点*/*半谷*半*率*率华中牛邛卡串注*率*星推创建单嗨表：甯输关元素数据（请输入整数，输入7999退出）：10 20 30 40 50 60 70 80 90 100 -9999输出单链表！10 20 30 40 50 60 70 30 90 100请输入所要插入单链表巾元素值；（输入T999退出）25强入成功，新链表为10 20 25 3
11、0 40 50 60 70 80 90 100请输入所要插入单链表中元素值 （输入-弱99退出）25插入成功，新链表为：10 20 25 30 40 50 60 70 80 85 90 100请输入所要插入单链表中元素值；（输入-9999退出）110箱人成功，新链表为:10 20 25 30 40 50 60 70 80 85 90 100 110请输入所要插入单链表中元素值；（输入-9999退出）8插入成功，新链表为：W 10 20 25 30 40 50 60 70 80 85 90 100 110请输入所要插入单链表中元素值;（输入Y999退出）5最新资料推荐蜃翦天矍I羲置&输入整数，输
12、入-9999退出）: 1 2 3 4 5 6 7 8 9 10 20 30 40 50 60 -9999 输出单链表：1 2 3 4 5 6 7 8 9 10 20 30 40 50 60输出原链表：1 2 3 4 5 6 7 8 9 10 20 30 40 50 60输出奇数项：13 5 7 9输出偶数项：2 4 6 8 10 20 30 40 50 60WALI借输入元素数据（请输入整数，输入rggg退出）：1 3 6 10 15 16 17 18 19 20 19gg9鬻E元素数据（请输入整数，输入-9999退出）士1 2 3 4 5 6 7 8 9 10 1S 20 30 -9999输
13、出新的单链表L&1 3 6 10 18 20鼠一4- I,kT !尾插法创建单链表:番输关元素数据（请输入整数，输入-9期退出）： 11222334556667899 -9999| o 1 j JI *r 1222334556667899当前单链表为：123456789卜土廿rr w上修4也但III101820 30 -99991单链表为:1819202单链表为；101820 30请输入元素数据（请输入整数，输入-999腿出） 1 2 6 10 15 16 17 18 19 20 -9999输入L2_1234567891 2 6 10 15 16 17123456789 俞出合并后的表L1C=
14、A B,漕输入兀素数据（请输入整数，输入-999诞出）1 3 5 7 9 10输出表B2 3 4 6 7 3 11 21输出表C1 2 3 4 5 6 7 8 9 10 11 21 请按任意键继续. . .C=A B输三表A1 3 5 7 9 10输出表B2 3 4 6 7 8 11 21输出表C3 7请按任意键继续.C=A-BA=A - BA=A BA=A-B:曹输入元素数据（请输入整数，输入-9999退出）： 13 5 6 7 -9999露黑元素数据（请输入整数，输入-999g退出）：1 2 3 5 6 7 8 9 22 111 -9999塌陇壬集1卸上rd0上曲上也心土强医创建单链表：品
15、俞尺元素数据（请输入整数，输入-9999退出）之2 3 4 5 6 7 11 12 13 -9999“人-9999退出WAk=l中倒数第1个位置上的结点为；13 Ak=2中倒数第2个位置上的结点为；12 入k=4n&Z 数第6个位置上的结点为，5前人A情输入元素数据（请输入整数，输入-9999退出）：数第4个位置上的结点为；7111 13 15 17 19 -9999中位数为：11 豳睛蹩续一feltE耆输入元素数据（请输入整数，输入-9999退出）： 2 4 6 8 20 -99996.总结和心得在此次程序编写的过程中，我总结第一次的经验教训，对程序整体先进行了 构建，避免了重复输出的问题。
16、然而，在编写过程中，针对此次实验又出现了不 少新的问题，下面进行相关总结：1 .在重置链表时，开始未将头结点的后继设为 NULL导致输出时出现异常, 花费大量时间才找到这一错误；2 .在完成向新链表中传入元素时，直接采用原来的结点，导致出现原链表 异常，影响实验功能，最后采用创建新结点解决；3 .删除重复元素时，一开始采用逐个删除，时间复杂度过高，后采用两个 结点，一次性删除所有重复元素，提高了时间性能；4 .在处理扩展实验三时，一开始采用先计算表长度，在找结点，过于复杂， 之后改为使用两个指针，使二者之间间隔未k,直接在后一结点结束时输 出前一结点，提高了时间性能；5 .在实验中，对于个结点之间的逻辑关系有所混淆，导致花费时间较长， 我从中吸取了教训，在以后的实验中，我会先解决逻辑关系的问题，在 完成实际的代码。7.附录（源代码清单。纸质报告不做要求。电子报告，可直接附源文件，删除编译生成 的所有文件）11