合工大宣城校区数据结构实验报告——单链表

1、数据结构实验报告姓名学号专业班级指导教师实验时间11月9日实验地占八、计算中心实验二单链表实验1. 实验目标 熟练掌握线性表的链式存储结构。 熟练掌握单链表的有关算法设计。 根据具体问题的需要，设计出合理的表示数据的链式存储结构，并设计相关算法。2. 实验内容和要求I .实验要求 本次实验中的链表结构指带头结点的单链表 单链表结构和运算定义，算法的实现以库文件方式实现，不得在测试主程序中 直接实现；比方存储、算法实现放入文件：lin kedList.h 实验程序有较好可读性，各运算和变量的命名直观易懂，符合软件工程要求； 程序有适当的注释。n.实验内容尾插法创立单链表，打印创立结果头插法创立单

2、链表，打印创立结果销毁单链表。求链表长度。求单链表中第 i 个元素函数，假设不存在，报错。在第 i 个结点前插入值为 x 的结点链表中查找元素值为 x 的结点，成功返回结点指针，失败报错删除单链表中第 i 个元素结点在一个递增有序的单链表L中插入一个值为x的元素，并保持其递增有序 特性将单链表L中的奇数项和偶数项结点分解开元素值为奇数、偶数，分 别放入新的单链表中， 然后原表和新表元素同时输出到屏幕上， 以便对照求解 结果求两个递增有序单链表 L1 和 L2 中的公共元素，放入新的单链表 L3 中删除递增有序单链表中的重复元素，要求时间性能最好递增有序单链表L1、L2,不申请新结点，利用原表结

3、点对 2表进行合并， 并使得合并后成为一个集合，合并后用L1的头结点作为头结点，删除L2的头 结点，要求时间性能最好扩展实验： 递增有序单链表表示集合 A、B，实现：C=A B， C=A B， C=A-BA=A B， A=A B， A=A-B (递增有序)单链表表示集合 A、B,判定A是否B的子集一个带有表头结点的单链表，结点结构如下列图。假设该链表只给出了 头指针 list 。在不改变链表的前提下,请设计一个尽可能高效的算法,查找 链表中倒数第 k 个位置上的结点( k 为正整数)。假设查找成功,算法输出该结 点的 data 值,并返回 1；否那么,只返回 0。L/2(2021) (15 分

4、) 一个长度为L(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 = v

5、alue;this-next = pNext;class 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 个元素结

6、点Node *head; ;4. 算法设计为书中已经给出的根本算法，.定义一个指针 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表示偶结点.定义两

7、个链表L3,定义指针*p，*u，*r，分别指向L3的头结点，L1， L2 的首元素结点上， 循环判断， 如果 u-value=r-value ，就把该值插入到 表 L3 中，如果 u-valuer-value ，让 r=r-next ，否那么让 u=u-next ；当 u=NULL或者r=NULL，结束循环，输出L3;.将元素分为两局部， 一局部是已经处理元素， 和待处理元素。 用 r 指向最后一个已经处理元素，用 u 指向还未处理的元素，如果 u-value value ，就让 u-next=r ，删除中间的重复元素，否那么就令 r=r-next ，当r=NULL结束循环，令 u-next=

8、NULL,输出 L.定义指针*p1,*p2,*u ；p1,p2分别指向L1的头结点和L2的首元素结点， 判断p1-next-value 与p2-value大小，前者大，那么将p2插入到pl后面， 后者大那么让 p1=p1-next ，相等那么 p2=p2-next ， p1=p1-next ，当 p1-next =NULL或 p2=NULL吉束循环。假设p2 !=NULL，直接将其接到pl之后，删除 L2.head，输出 L1.扩展实验：.对于采用集合C的运算，将符合要求的元素插入到新链表 C中，对于不 采用链表C的运算，就对链表A中元素进行插入与删除操作。.使用两个指针*u，*r，分别指向A

9、，B的首元素结点，对A中元素按顺序 进行判断，如果出现u-valuevalue ，那么表示A不为B的子集，如果 u-valuer-value ，那么 r = r-next ，如果 u-value=r-value, 那么 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 个

10、位置上的结点。.因为两个序列A和B等长升序，故只需按照递增有序的顺序找到第A.length()即可，可以对A，B元素进行排序，到第 A.length()结束即可输出该值为中位数。5. 运行和测试菜单:程亭:瀾放人新就甲陡表中.議后匣商潇表冗希同时循出剽闻茗出g I. i. I. 4 d I I f | 4 4 -I I* i |i F * 4 M I 4 I M I f I bigiiir： ?： w日.g斗工遗増 q.噫甲馆恙一 叫吏旗皙 J.j跻T中霹曙舌电志进荷合井，幷断吉并姑助T拿奇 合幷JS用LL的头第点作为佚结点U評;删鵜 啟肆血尹低遽.假设不沁檎 魏蛊聶九;矗彰k功返回拮盘指针.

11、失盟赭E齬祸启矗开毘播送创立单链表:WfflATLWt 请输入整熱输人-9沏退岀.； 10 20 30 40 50 60 70 80 90 100 -的旳 输岀单锥表；10 20 30 40 5Q &0 70 80 90 100请输入所要插入单链表中元素值，输人-9的腿出25焉入成功，新错表为；10 20 25 30 40 50 60 70 80 90 100请输入所要插入单链表中元素值，输人-9的腿出85焉入成功，新链表为：10 20 2S 30 40 S0 60 70 SO SB 90 10C倩输入所要插入单链表中元素值：输入-9豹濾出 11CJ辰入成功，新镇表为10 20 25 30 4

12、0 50 50 70 80 85 90 100 110 请输入所要插入单链表中元素值：输入-9忻箍出-監入成功，新链表为8 10 20 25 30 40 50 60 70 80 S5 90 10C 110 请输入所要插入单链表中元素值：输人-9忻濾出層霧券贋嘉鶴酱情输入整数，输入999退岀1 2 3 4 5 6 7 8 9 10 2U 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 2U 30 40 50 60 输出奇数项1 3 5 7 9输出偶数项；2 1 6 S 10

13、2C 30 40 50 60-士丄宀J十卜亠小十黔员元素数据请输入整熱 输入-唤退出：1 3 6 10 15 16 17 1S 19 2Q -9999请输入元素数据请输入整数，输入-99勺勺退岀1 2 3 4 5 6 7 8 9 10 18 20 30 -9999 输出新的单链衾L3；1 3 6 10 18 20I + 亠F- Ki-11 I +十数3 建素2为2袁 创元2表2B3=73为6辙入-9999退出；899 -9999输人L1洁猛人元素数据请输入鑿数输入T9的退出 1 2 6 10 15 16 17 18 19 20 -999器献元素勒E请输入鹤乳输A-9999出1 2 3 4 5

14、6 7 8 9 10 18 20 30 -9999L1单毎龛为；1 2 6 10 15 16 17 18 19 20L 2单話龛为!1 2 3 4 5 6 7 8 9 10 18 20 30输岀合井后的表L11 2 3 4 5 6 7 8 9 10 15 16 17 18 19 20 30 请桁仟薫绅缜-.扩展实验:C=A B,E 91 3 5 7 9 10触岀表BE 3 4 6 7 8 11 2L 输出表C1 2 3 4 5 6 7 8 9 10 11 21 青按任意键継续C=A B1 3 5 7 9 10 输出耘2 3 4 6 7 8 11 21 输出表C3 7请按任意键継续.C=A-BA

15、=A B颔工表A1 2 3 4 5 6 7 8 9 10 11 21输出表2 3 4 6 7 8 11 212圣宀 H 土上為氐1 妊A=A BA=A-B雜人A鲁输入元素数据请输入整数.输入-勺999退岀：13 5 6 7 T勺刖转j入号曙蔬入元素数据请输入鑿数，输入叱退岀：豐鑑备输入整数 输入-河9退岀,4 5 e 7 11 12 13 -99刖2A-9999退出賞生留数第1个位置上的结点为: 載餘第z个位置上的结点为: 專胡数第4个位萱上的结点为: 撲带窗数兼个位置上的结点为： 魏愿半，135HH-sohiAk=61參篆寒WW藏磁蓼潍滎鑿矗枣WO邈齡，鬆霸泰耀蠢題觸爲寶雜艦?館鰹墾勲嚎奏籤惡6. 总结和心得在此次程序编写的过程中，我总结第一次的经验教训，对程序整体先进行了 构建，防止了重复输出的问题。然而，在编写过程中，针对此次实验又出现了不 少新的问题，下面进行相关总结：1. 在重置链表时，开始未将头结点的后继设为 NULL导致输出时出现异常, 花费大量时间才找到这一错误；2. 在完成向新链表中传入元素时，直接采用原来的结点，导致出现原链表 异常，影响实验功能，最后采用创立新结点解决；3. 删除重复元素时，一