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

数据结构实验报告姓名学号专业班级指导教师实验时间11月9日实验地占八、计算中心实验二单链表实验1. 实验目标 熟练掌握线性表的链式存储结构。 熟练掌握单链表的有关算法设计。 根据具体问题的需要，设计出合理的表示数据的链式存储结构，并设计相关算法。2. 实验内容和要求I .实验要求 本次实验中的链表结构指带头结点的单链表 单链表结构和运算定义，算法的实现以库文件方式实现，不得在测试主程序中 直接实现；比方存储、算法实现放入文件：lin kedList.h 实验程序有较好可读性，各运算和变量的命名直观易懂，符合软件工程要求； 程序有适当的注释。n.实验内容<1>尾插法创立单链表，打印创立结果<2>头插法创立单链表，打印创立结果<3>销毁单链表。<4>求链表长度。<5>求单链表中第 i 个元素函数，假设不存在，报错。<6>在第 i 个结点前插入值为 x 的结点<7>链表中查找元素值为 x 的结点，成功返回结点指针，失败报错<8>删除单链表中第 i 个元素结点<9>在一个递增有序的单链表L中插入一个值为x的元素，并保持其递增有序 特性<10>将单链表L中的奇数项和偶数项结点分解开元素值为奇数、偶数，分 别放入新的单链表中， 然后原表和新表元素同时输出到屏幕上， 以便对照求解 结果<11>求两个递增有序单链表 L1 和 L2 中的公共元素，放入新的单链表 L3 中<12>删除递增有序单链表中的重复元素，要求时间性能最好<13>递增有序单链表L1、L2,不申请新结点，利用原表结点对 2表进行合并， 并使得合并后成为一个集合，合并后用L1的头结点作为头结点，删除L2的头 结点，要求时间性能最好扩展实验：<1> 递增有序单链表表示集合 A、B，实现：C=A B， C=A B， C=A-BA=A B， A=A B， A=A-B<2> (递增有序)单链表表示集合 A、B,判定A是否B的子集<3>一个带有表头结点的单链表，结点结构如下列图。假设该链表只给出了 头指针 list 。在不改变链表的前提下,请设计一个尽可能高效的算法,查找 链表中倒数第 k 个位置上的结点( k 为正整数)。假设查找成功,算法输出该结 点的 data 值,并返回 1；否那么,只返回 0。L/2<4>(2021) (15 分) 一个长度为L(L>1)的升序序列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;class linkedListpublic :linkedList()；/ 构造函数linkedList()；/<3> 析构函数 , 销毁单链表int length()；/<4> 求链表长度Node *listLocateI(int i); /<5> 求单链表中第 i 个元素bool listInsert(int i,int x); /<6> 在第 i 个结点前插入值为 x 的Node *listLocateX(int x)；/<7> 链表中查找元素值为 x 的结点，成结点功返回结点指针，失败报错bool listDelete(int i)； /<8> 删除单链表中第 i 个元素结点Node *head; ;4. 算法设计<1><8>为书中已经给出的根本算法，<9>.定义一个指针 p 指向头结点，当 p->next != NULL ，循环比拟 p->next->value 与 x 的值之间的大小，假设 p->next->value<x ，就令 p = p->next，当申请新结点，存储x，将新结点插入在p之后，完成插入。<10>.定义两个链表L1, L2,定义指针*p , *u , *r，分别指向L的首元素结 点，L1，L2的头结点上，循环判断，如果 p->value%2!=0，就插入到表L1 中，否那么，就插入到表L2中，然后令p=p->next，直至p!=NULL结束循环， 输出L1，L2,其中L1表示奇结点，L2表示偶结点<11>.定义两个链表L3,定义指针*p，*u，*r，分别指向L3的头结点，L1， L2 的首元素结点上， 循环判断， 如果 u->value=r->value ，就把该值插入到 表 L3 中，如果 u->value>r->value ，让 r=r->next ，否那么让 u=u->next ；当 u=NULL或者r=NULL，结束循环，输出L3;<12>.将元素分为两局部， 一局部是已经处理元素， 和待处理元素。 用 r 指向最后一个已经处理元素，用 u 指向还未处理的元素，如果 u->value <r->value ，就让 u->next=r ，删除中间的重复元素，否那么就令 r=r->next ，当r=NULL结束循环，令 u->next=NULL,输出 L<13>.定义指针*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.扩展实验：<1>.对于采用集合C的运算，将符合要求的元素插入到新链表 C中，对于不 采用链表C的运算，就对链表A中元素进行插入与删除操作。<2>.使用两个指针*u，*r，分别指向A，B的首元素结点，对A中元素按顺序 进行判断，如果出现u->value<r->value ，那么表示A不为B的子集，如果 u->value>r->value ，那么 r = r->next ，如果 u->value=r->value, 那么 u = u->next，r = r->next，如果对A中每个元素进行判断，均可在 B中找到，那么A为B的子集。<3>. 采用两个指针 *u = L.head ， *r = L.head->next ，参加一个计数器 i ， i表示已经经过的结点，r每移动一次，i+，当i>k，u开始移动，当r移动 到表尾时，u即指向倒数第k个位置上的结点；假设u为头结点，那么其未移动， 表示无倒数第 k 个位置上的结点。<4>.因为两个序列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功返回拮盘指针.失盟赭E齬祸启矗开<9>毘播送创立单链表: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 40 50 50 70 80 85 90 100 110 请输入所要插入单链表中元素值：输入-9忻箍出-監入成功，新链表为8 10 20 25 30 40 50 60 70 80 S5 90 10C 110 请输入所要插入单链表中元素值：输人-9忻濾出<10>層霧券贋嘉鶴酱情输入整数，输入£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 2C 30 40 50 60-士丄宀J十卜亠小十<11>黔员元素数据请输入整熱 输入-唤退出：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 '+<12>十数3 建素2为2袁 创元2表2B3=73为6辙入-9999退出；899 -9999<13>输人L1洁猛人元素数据请输入鑿数输入T9的退出 1 2 6 10 15 16 17 18 19 20 -999器献元素勒E请输入鹤乳输A-9999出1 2 3 4 5 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 请桁仟薫绅缜-.扩展实验:<1>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=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<2>雜人A鲁输入元素数据请输入整数.输入-勺999退岀：13 5 6 7 T勺刖转j入号曙蔬入元素数据请输入鑿数，输入叱退岀：<3>豐鑑备输入整数 输入-河9退岀,4 5 e 7 11 12 13 -99刖2A-9999退出賞生留数第1个位置上的结点为: 載餘第z个位置上的结点为: 專胡数第4个位萱上的结点为: 撲带窗数兼个位置上的结点为： 魏愿半，135HH-sohiAk=6<4>1參篆寒WW藏磁蓼潍滎鑿矗枣WO邈齡，鬆霸泰耀蠢題觸爲寶雜艦?館鰹墾勲嚎奏籤惡6. 总结和心得在此次程序编写的过程中，我总结第一次的经验教训，对程序整体先进行了 构建，防止了重复输出的问题。然而，在编写过程中，针对此次实验又出现了不 少新的问题，下面进行相关总结：1. 在重置链表时，开始未将头结点的后继设为 NULL导致输出时出现异常, 花费大量时间才找到这一错误；2. 在完成向新链表中传入元素时，直接采用原来的结点，导致出现原链表 异常，影响实验功能，最后采用创立新结点解决；3. 删除重复元素时，一开始采用逐个删除，时间复杂度过高，后采用两个 结点，一次性删除所有重复元素，提高了时间性能；4. 在处理扩展实验三时，一开始采用先计算表长度，在找结点，过于复杂，之后改为使用两个指针，使二者之间间隔未k,直接在后一结点结束时输出前一结点，提高了时间性能；5. 在实验中，对于个结点之间的逻辑关系有所混淆，导致花费时间较长， 我从中吸取了教训，在以后的实验中，我会先解决逻辑关系的问题，在 完成实际的代码。7. 附录 源代码清单。纸质报告不做要求。电子报告，可直接附源文件，删除编译生成 的所有文件