《数据结构试验报告--单链表.docx》由会员分享，可在线阅读，更多相关《数据结构试验报告--单链表.docx（14页珍藏版）》请在三一文库上搜索。
1、2 0 16级 数 据 结 构 实 验 报 告实验名称：实验一线性表一一题目1学生姓名:李文超班级：班内序号：15学号：47n期：2021年11月13日1. 实验要求实验目的：根据线性表的抽象数据类型的定义,选择下面任一种链式结构实现线性表, 并完成线性表的根本功能.线性表存储结构五选一：1、带头结点的单链表2、不带头结点的单链表3、循环链表4、双链表5、静态链表线性表的根本功能：1、构造：使用头插法、尾插法两种方法2、插入：要求建立的链表根据关键字从小到大有序3、删除4、查找5、获取链表长度6、销毁7、其他：可自行定义编写测试main.函数测试线性表的正确性.2.程序分析存储结构单链表的存储
2、：1链表用一组任意的存储单元来存放线性表的结点.这组存储单元既可以 是连续的,也可以是不连续的,共至零散地分布在内存的某些位置.2链表中结点的逻辑次序和物理次序不一定相同.为了能正确表示结点间 的逻辑关系,在存储每个元素值的同时,还要存储该元素的直接后继元素的位置 信息,这个信息称为指针或链.结点结构data域-一存放结点值的数据域I data | next |next域-一存放结点的直接后继的地址的指针域|II 9单链表在内存中的存储示意地址 内存单元a31080H al10C0H a 4 a 21000H1000H头指卡L1020H1080H10C0HfroRH I II I -P关键算法
3、分析1、关键算法：(1)头插法白然语言描述：a：在堆中建立新结点b：将ai写入到新结点的数据域c :修改新结点的指针域d:修改头结点的指针域.将新结点参加链表中伪代码描述a:Node * s=new Node b:s-data二ai c:s-next二front-next;d:front-next二s2尾插法自然语言描述：a：在堆中建立新结点：b：将ai写入到新结点的数据域：c：将新结点参加到链表中d：修改修改尾指针伪代码描述a：Node * s=new Node b:s-data二aic:r-next=s;d:r=s3遍历打印函数自然语言描述：a：判断该链表是否为空链表,如果是,报错b:如果
4、不是空链表,新建立一个temp指针 c:将temp指针指向头结点d:打印temp指针的data域e：逐个往后移动temp指针,直到temp指针的指向的指针的next域为空伪代码描述a： If front-next二二NULLThrow an empty list Node* temp二front-next;b:while(temp-next)c:coutdata ；d:temp二temp-next;(4) 获取链表长度函数H然语言描述：a：判断该链表是否为空链表,如果是,输出长度0b:如果不是空链表,新建立一个temp指针,初始化整形数n为0c:将temp指针指向头结点d：判断temp指针指向
5、的结点的next域是否为空,如果不是,n加一,否那么 return ne：使temp指针逐个后移,重复d操作,直到temp指针指向的结点的next域为0,返回n伪代码描述a:if ront-next二二NULL b:Node* temp=front-next;c:while(temp-next)d:temp二temp-next;(5) 析构/删除函数白然语言描述：a：新建立一个指针,指向头结点b:判断要释放的结点是否存在,c:暂时保存要释放的结点d:移动a中建立的指针e：释放要释放的指针伪代码描述a:Node * p二front b：while(p) c:front二pd:p二p-nexte:
6、delete front(6) 按位查找函数自然语言描述：a:初始化工作指针p和计数器j, p指向第一个结点,j=lb:循环以下操作,直到p为空或者j等于1:P指向下一个结点:j加1c:假设p为空,说明第i个元素不存在,抛出异常d:否那么,说明p指向的元素就是所查找的元素,返回元素地址伪代码描述a：Node * p二front-next;j=l;b:while (p&j!=1):p二p-next:j+c:if(!p) throw errorMd:return p(7) 按位查找函数白然语言描述：a：初始化工作指针p和计数器j, p指向第一个结点,j二1b：循环以下操作,找到这个元素或者p指向最
7、后一个结点:判断P指向的结点是不是要查找的值,如果是,返回j,否那么P指向下一个结点,并且j的值加一c：如果找到最后一个结点还没有找到要查找的元素,返回查找失败信息伪代码描述a：Node * p二front-nexb：whilep:ifp-next二二x return jp二p-nextj+c:return error8插入函数自然语言描述：a：在堆中建立新结点 b：将要插入的结点的数据写入到新结点的数据域C：修改新结点的指针域d:修改前一个指针的指针域,使其指向新插入的结点的位置伪代码描述a：Node * s二new Node :b:s-data=p-datac:s-next二p-nextd
8、:p-next二se:p-data=x9删除函数自然语言描述：a：从第一个结点开始,查找要删除的位数i前一个位置i-1的结点b：设q指向第i个元素c：将q元素从链表中删除d：保存q元素的数据e：释放q元素伪代码描述a：q=p-nextb:p-next=q-next c：x=q-datad：delete q2、代码详细分析(插入)：(1) 从第一个结点开始,查找节点,使它的数据比x大,设p指向该结点:while (xp-data) :、p二p-next;(2) 新建一个节点s,把p的数据赋给s：s-data=p-data;(3) 把s加到p后面：s-next二p-next; p-next二s;(
9、4) p节点的数据用x替换：p-data=x;示意图如下图p-data3、关键算法的时间复杂度：0 (1)3. 程序运行结果1 流程图:2、结果截图UM初始化一个对象初始化一个溜形数绢.作为赋值洛各分 1 ml、 1 - Yi r 1、 | 一t f /|、/ r-1 til 、rv* i数曲彳揺入尿脚 丘凉FT；打口 1隔務*涮狀具丕首III试鳧执彳皿Hi刁址盂土b工仃址估盂用刚Zdr rk3. 测试结论：可以正确的对链表进行插入,删除,取长度,输出操作.且插入任意 一个元素后,链表的顺序依然是由小到大.4、给出代码文末4. 总结1、问题书中已经给出析构、查找、插入、删除过程代码,遍历以及获
10、取长度代码需要 自己写出,刚开始写时一直出现各种根本错误,后来经过不断调试解决了问题.编写main函数时,调用插入删除等操作的代码一直编写失败,后自行查找资 料后解决2、收获这次编程任务完成地较为艰辛,但做完之后大大加深了自己对书中各个知识点 的印象和理解.也学会了一些编写算法的小技巧,要有耐心,多看书复习知识.总之,这次实验使我印象深刻.include using namespace std; template struct Node T data;struct Node * next;template class LinkListpublic:LinkList () LinkList();system(p8use);return 0;