![数据结构实验报告单链表_第1页](http://file4.renrendoc.com/view/3ff0ea450d536b0f5fcb4c45f25349c1/3ff0ea450d536b0f5fcb4c45f25349c11.gif)
![数据结构实验报告单链表_第2页](http://file4.renrendoc.com/view/3ff0ea450d536b0f5fcb4c45f25349c1/3ff0ea450d536b0f5fcb4c45f25349c12.gif)
![数据结构实验报告单链表_第3页](http://file4.renrendoc.com/view/3ff0ea450d536b0f5fcb4c45f25349c1/3ff0ea450d536b0f5fcb4c45f25349c13.gif)
![数据结构实验报告单链表_第4页](http://file4.renrendoc.com/view/3ff0ea450d536b0f5fcb4c45f25349c1/3ff0ea450d536b0f5fcb4c45f25349c14.gif)
![数据结构实验报告单链表_第5页](http://file4.renrendoc.com/view/3ff0ea450d536b0f5fcb4c45f25349c1/3ff0ea450d536b0f5fcb4c45f25349c15.gif)
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
集团检集团检数据结构实验报告单链
表小组[Q8QX9QT-X8QQB8Q8-NQ8QJ8-M8QMN]2016级数据结构实验报告实验名称:实验一线性表一一题目1学生姓名:李文超班级:31班内序号:15学号:47日期:2016年11月13日1.实验要求实验目的:根据线性表的抽象数据类型的定义,选择下面任一种链式结构实现线性表,并完成线性表的基本功能。线性表存储结构(五选一):1、带头结点的单链表2、不带头结点的单链表3、循环链表4、双链表5、静态链表线性表的基本功能:1、构造:使用头插法、尾插法两种方法2、插入:要求建立的链表按照关键字从小到大有序3、删除4、查找5、获取链表长度6、销毁7、其他:可自行定义编写测试main。函数测试线性表的正确性。2.程序分析存储结构单链表的存储:(1)链表用一组任意的存储单元来存放线性表的结点。这组存储单元既可以是连续的,也可以是不连续的,甚至零散地分布在内存的某些位置。(2)链表中结点的逻辑次序和物理次序不一定相同。为了能正确表示结点间的逻辑关系,在存储每个元素值的同时,还要存储该元素的直接后继元素的位置信息,这个信息称为指针或链。结点结构I 1 1 data域--存放结点值的数据域Idata|next| next域一-存放结点的直接后继的地址的指针域单链表在内存中的存储示意地址 内存单元-1080Ha[l]10C0Ha[4]1000H头指针"1020Ha[2]1080H1000H10C0H关键算法分析1、关键算法:(1)头插法自然语言描述:a:在堆中建立新结点b:将a[i]写入到新结点的数据域c:修改新结点的指针域d:修改头结点的指针域。将新结点加入链表中伪代码描述a:Node<T>*s=newNode<T>b:s->data=a[i]c:s->next=front->next;d:front->next=s(2)尾插法自然语言描述:a:在堆中建立新结点:b:将a[i]写入到新结点的数据域:c:将新结点加入到链表中d:修改修改尾指针伪代码描述a:Node<T>*s=newNode<T>b:s->data=a[i]c:r->next=s;d:r=s(3)遍历打印函数自然语言描述::判断该链表是否为空链表,如果是,报错b:如果不是空链表,新建立一个temp指针c:将temp指针指向头结点d:打印temp指针的data域e:逐个往后移动temp指针,直到temp指针的指向的指针的next域为空伪代码描述a:Iffront->next==NULLThrow"anemptylist”Node<T>*temp=front->next;b:while(temp->next)c:cout<<temp->data<</,〃;d:temp=temp->next;(4)获取链表长度函数自然语言描述:a:判断该链表是否为空链表,如果是,输出长度0b:如果不是空链表,新建立一个temp指针,初始化整形数n为。c:将temp指针指向头结点d:判断temp指针指向的结点的next域是否为空,如果不是,n加一,否则returnne:使temp指针逐个后移,重复d操作,直到temp指针指向的结点的next域为0,返回n伪代码描述a:ifront->next-NULLb:Node<T>*temp=front->next;c:while(temp->next)d:temp=temp->next;(5)析构/删除函数自然语言描述:a:新建立一个指针,指向头结点b:判断要释放的结点是否存在,c:暂时保存要释放的结点d:移动a中建立的指针e:释放要释放的指针伪代码描述a:\ode<T>*p=frontb:while(p)c:front=pd:p=p->nexte:deletefront(6)按位查找函数自然语言描述:a:初始化工作指针p和计数器j,p指向第一个结点,户1b:循环以下操作,直到p为空或者j等于1:P指向下一个结点:j加1c:若p为空,说明第i个元素不存在,抛出异常d:否则,说明p指向的元素就是所查找的元素,返回元素地址伪代码描述a:\ode<T>*p=front->next;;b:while(p&&j!=1):p=p->next:j++c:if(!p)throw"errorMd:returnp(7)按位查找函数自然语言描述:a:初始化工作指针p和计数器j,p指向第一个结点,户1b:循环以下操作,找到这个元素或者p指向最后一个结点:判断P指向的结点是不是要查找的值,如果是,返回j,否则P指向下一个结点,并且j的值加一c:如果找到最后一个结点还没有找到要查找的元素,返回查找失败信息伪代码描述a:Node<T>*p=front->next;j=l;b:while(p):if(p->next==x)returnjp=p->nextj++c:return“error”(8)插入函数自然语言描述:a:在堆中建立新结点b:将要插入的结点的数据写入到新结点的数据域c:修改新结点的指针域d:修改前一个指针的指针域,使其指向新插入的结点的位置伪代码描述a:\ode<T>*s=newNode<T>;b:s-data=p->datac:s->next=p->nextd:p->next=se:p->data=x(9)删除函数自然语言描述::从第一个结点开始,查找要删除的位数i前一个位置i-1的结点b:设Q指向第i个元素c:将q元素从链表中删除d:保存q元素的数据e:释放q元素伪代码描述a:q=p->nextb:p->next=q->nextc:x=q->datad:deleteq2、代码详细分析(插入):(1)从第一个结点开始,查找节点,使它的数据比x大,设p指向该结点:while(x>p->data){p=p->next;}(2)新建一个节点s,把p的数据赋给s: s->data=p->data;(3)把s加到p后面:s->next=p->next;p->next=s;(4)p节点的数据用x替换:p->data=x;示意图如图所示p、p->data3、关键算法的时间复杂度:0(1)3.程序运行结果1.流程图:初始化一个对象初始化一个整形数组,作为赋值准备分别利用头插法和尾插法初始化,并且用遍历打印函数来执行插人函物.:后遍历打印函加来测试是否直的执行删除函数,之后遍历打印函数来测试是否柏行坊待香抄和将倩香抄雨知任古2、结果截图.测试结论:可以正确的对链表进行插入,删除,取长度,输出操作。且插入任意一个元素后,链表的顺序依然是由小到大。4、给出代码(文末).总结1、问题书中已经给出析构、查找、插入、删除过程代码,遍历以及获取长度代码需要自己写出,刚开始写时一直出现各种基本错误,后来经过不断调试解决了问题。编写main函数时,调用插入删除等操作的代码一直编写失败,后自行查找资料后解决2、收获这次编程任务完成地较为艰辛,但做完之后大大加深了自己对书中各个知识点的印象和理解。也学会了一些编写算法的小技巧,要有耐心,多看书复习知识。总之,这次实验使我印象深刻。#include<iostream>usingnam
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- GB/T 35170-2024水泥窑协同处置的生活垃圾预处理可燃物
- 人教版美术五年级下册《第13课 风筝的魅力》说课稿3
- 除尘设备租用合同范本
- 人教版小学数学四年级上册6.1《纵向复式条形统计图》说课稿
- 人教版部编本五年级上册第1单元《口语交际:制定班级公约》教学设计
- 动物防治员技能理论考试题库大全-下(判断题)
- 人教部编版五年级语文上册 5 《搭石》说课稿
- 人教部编版八年级道德与法治上册:2.1《网络改变世界》说课稿1
- 人教版美术五年级上册《第20课 珍爱国宝──古代陶瓷艺术》教学设计3
- 三年级上册数学教学设计《6.1 蚂蚁做操(2)-》-北师大版
- excel单元格引用PPT优秀课件
- NUDD新独难异失效模式预防检查表
- 宁夏普通高校招生考生综合素质评价表
- 地连墙钢筋笼验收表(终稿)
- 水泥生产过程数值模拟研究
- 学生成长跟踪记录表
- 太阳能热水系统调试记录
- 衢州市新100条
- 夏普数码复印机故障代码及常用维修代码
- 命中率与贡献率
- 从心理学角度探析信访老户的深层心理动力
评论
0/150
提交评论