《合工大宣城校区数据结构实验报告_单链表》由会员分享,可在线阅读,更多相关《合工大宣城校区数据结构实验报告_单链表(7页珍藏版)》请在金锄头文库上搜索。
1、 数据结构实验报告学号专业班级指导教师实验时间11月9日实验地点计算中心实验二 单链表实验1. 实验目标 熟练掌握线性表的链式存储结构。 熟练掌握单链表的有关算法设计。 根据具体问题的需要,设计出合理的表示数据的链式存储结构,并设计相关算法。2. 实验容和要求.实验要求 本次实验中的链表结构指带头结点的单链表 单链表结构和运算定义,算法的实现以库文件方式实现,不得在测试主程序中直接实现;比如存储、算法实现放入文件:linkedList.h 实验程序有较好可读性,各运算和变量的命名直观易懂,符合软件工程要求; 程序有适当的注释。.实验容尾插法创建单链表,打印创建结果。头插法创建单链表,打印创建结
2、果。销毁单链表。求链表长度。求单链表中第i个元素(函数),若不存在,报错。在第i个结点前插入值为x的结点链表中查找元素值为x的结点,成功返回结点指针,失败报错删除单链表中第i个元素结点在一个递增有序的单链表L中插入一个值为x的元素,并保持其递增有序特性将单链表中的奇数项和偶数项结点分解开(元素值为奇数、偶数),分别放入新的单链表中,然后原表和新表元素同时输出到屏幕上,以便对照求解结果求两个递增有序单链表L1和L2中的公共元素,放入新的单链表L3中删除递增有序单链表中的重复元素,要求时间性能最好递增有序单链表L1、L2,不申请新结点,利用原表结点对2表进行合并,并使得合并后成为一个集合,合并后用
3、L1的头结点作为头结点,删除L2的头结点,要求时间性能最好扩展实验:(递增有序)单链表表示集合A、B,实现:C=AB,C=AB,C=A-BA=AB,A=AB,A=A-B(递增有序)单链表表示集合A、B,判定A是否B的子集已知一个带有表头结点的单链表,结点结构如以下图。假设该链表只给出了头指针list。在不改变链表的前提下,请设计一个尽可能高效的算法,查找链表中倒数第k个位置上的结点(k为正整数)。若查找成功,算法输出该结点的data值,并返回1;否则,只返回0。(2011)(15 分)一个长度为L(L1)的升序序列S,处在第 个位置的数称为S 的中位数。例如,若序列S1=(11, 13, 15
4、, 17, 19),则S1 的中位数是15。两个序列的中位数是含它们所有元素的升序序列的中位数。例如,若S2=(2, 4, 6, 8, 20),则S1 和S2 的中位数是11。 现有两个等长升序序列A 和B,试设计一个在时间和空间两方面都尽可能高效的算法,找出两个序列A 和B 的中位数3. 数据结构设计struct Node int value; Node *next; Node(int value = 0, Node *pNext = 0) this-value = value; this-next = pNext; ;class linkedListpublic : linkedList(
5、);/构造函数 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. 算法设计为书中已经给出的基本算法,.定义一个指针p指向头结点,当p-next != NULL,循环比较p-next
6、-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,L2的首元素结点上,循环判断,如果u-value=r-value,就把该值插入到表L3中,如果u-valuer-value
7、,让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=NULL,输出L.定义指针*p1,*p2,*u;p1,p2分别指向L1的头结点和L2的首元素结点,判断p1-next-value与p2-value大小,前者大,则将p2插入到p1后面,后者大则让p1=p1-next,相等则p2=p2-next,p1=p
8、1-next,当p1-next =NULL或p2=NULL完毕循环。若p2 !=NULL,直接将其接到p1之后,删除L2.head,输出L1.扩展实验:. 对于采用集合C的运算,将符合要求的元素插入到新链表C中,对于不采用链表C的运算,就对链表A中元素进行插入与删除操作。.使用两个指针*u,*r,分别指向A,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
9、的子集。.采用两个指针*u = L.head,*r = L.head-next,加入一个计数器i,i表示已经经过的结点,r每移动一次,i+,当ik,u开始移动,当r移动到表尾时,u即指向倒数第k个位置上的结点;若u为头结点,则其未移动,表示无倒数第k个位置上的结点。.因为两个序列A 和B等长升序,故只需按照递增有序的顺序找到第A.length()即可,可以对A,B元素进行排序,到第A.length()完毕即可输出该值为中位数。5. 运行和测试菜单:扩展实验:C=AB,C=ABC=A-BA=ABA=ABA=A-B6. 总结和心得在此次程序编写的过程中,我总结第一次的经验教训,对程序整体先进行了构
10、建,避免了重复输出的问题。然而,在编写过程中,针对此次实验又出现了不少新的问题,下面进行相关总结:1. 在重置链表时,开始未将头结点的后继设为NULL,导致输出时出现异常,花费大量时间才找到这一错误;2. 在完成向新链表中传入元素时,直接采用原来的结点,导致出现原链表异常,影响实验功能,最后采用创建新结点解决;3. 删除重复元素时,一开始采用逐个删除,时间复杂度过高,后采用两个结点,一次性删除所有重复元素,提高了时间性能;4. 在处理扩展实验三时,一开始采用先计算表长度,在找结点,过于复杂,之后改为使用两个指针,使二者之间间隔未k,直接在后一结点完毕时输出前一结点,提高了时间性能;5. 在实验中,对于个结点之间的逻辑关系有所混淆,导致花费时间较长,我从中吸取了教训,在以后的实验中,我会先解决逻辑关系的问题,在完成实际的代码。7. 附录(源代码清单。纸质报告不做要求。电子报告,可直接附源文件,删除编译生成的所有文件) /