《2023年数据结构实验报告单链表.pdf》由会员分享，可在线阅读，更多相关《2023年数据结构实验报告单链表.pdf（23页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、2 0 23级数据结构实验报告实验名称：实验一线性表一一题 目1学生姓名：李文超班 级：班内序号：15学号:B期：202 3年11月13日1.实验规定实验目的：根据线性表的抽象数据类型的定义，选择下面任一种链式结构实现线性表，并完毕线性表的基本功能。线性表存储结构（五选一）：1、带头结点的单链表2、不带头结点的单链表3、循环链表4、双链表5、静态链表线性表的基本功能：1、构造：使用头插法、尾插法两种方法2、插入：规定建立的链表按照关键字从小到大有序3、删除4、查找5、获取链表长度6、销毁7、其他:可自行定义编写测试ma i n()函数测试线性表的对的性。2.程序分析2.1存储结构单链表的存储：
2、(1)链表用一组任意的存储单元来存放线性表的结点。这组存储单元既可以是连续的，也可以是不连续的，甚至零散地分布在内存的某些位置。(2)链表中结点的逻辑顺序和物理顺序不一定相同。为了能对的表达结点间的逻辑关系，在存储每个元素值的同时,还要存储该元素的直接后继元素的位置信息，这个信息称为指针或链。结点结构Ada t a域-存放结点值的数据域&|da t a|ne x t|针域A I-1-1 A单链表在内存中的存储示意地址n e x t域一一存放结点的直接后继的地址的指内存单元1000Ha l1OCOH头指针 A 1020H10 8 0.Ha 4.a 21000H.10C OHfro n t。斤2.
3、2关键算法分析1、关键算法：(1)头插法自然语言描述:a :在堆中建立新结点b：将 a i 写入到新结点的数据域c：修改新结点的指针域d：修改头结点的指针域。将新结点加入链表中伪代码描述a：N o d e *s=n e w N o d e b :s-d a t a=a i c:s-n e x t=f r o n t n e x t;d :f r o n t -n e x t=s(2)尾插法自然语言描述：a :在堆中建立新结点：b :将 a i 写入到新结点的数据域：c :将新结点加入到链表中d:修改修改尾指针伪代码描述a:N o d e *s=n e w N o d e b:s-d a t a
4、=a i c:r-n e x t =s;d:r=s(3)遍历打印函数自然语言描述：a ：判断该链表是否为空链表,假如是，报错b:假如不是空链表,新建立一个t e m p指针c:将t e m p指针指向头结点d ：打 印t e m p指针的d a t a域e:逐个往后移动t e m p指针，直 到t emp指针的指向的指针的n e x t域为空伪代码描述a :I f f r o n t-n e x t =N U L LT h r o w ”a n e m p t y 1 i s t ”N o d eT *t e m p=f r o n t -n e x t；b:w h i l e (t e m
5、p-n e x t)c :c o u t d a ta V V ；d:t em p=t em p-n ex t;(4)获取链表长度函数自然语言描述:a:判断该链表是否为空链表，假如是，输出长度0b:假如不是空链表，新建立一个te mp指针，初始化整形数n为。c：将 t e m p 指针指向头结点d:判断t e m p 指针指向的结点的n e x t 域是否为空，假如不是,n加一，否则r et u r n ne：使 t e m p 指针逐个后移,反复d 操作,直到t e m p 指针指向的结点的n ex t域为0,返回n伪代码描述a:if r o n t-n ex t =N U LLb：N o
6、d e *t em p =f r o n t-n ex t;c:w h ile(t em p n ex t)d:t em p =t em p-n ex t;(5)析构/删除函数自然语言描述：a:新建立一个指针，指向头结点b：判断要释放的结点是否存在，c:暂时保存要释放的结点d:移动a 中建立的指针e:释放要释放的指针伪代码描述a：N o d e *p=fr o n tb:w h ile(p)c：f r o n t =pd:p=p-n ex te：del e t e f r o n t(6)按位查找函数自然语言描述：a:初始化工作指针p和计数器j,p指向第一个结点,j =lb:循环以下操作，直到
7、p为空或者j等 于1:P指向下一个结点:j加1c：若P为空,说明第i个元素不存在,抛出异常d:否则，说明p指向的元素就是所查找的元素,返回元素地址伪代码描述a:N o de *p=fr o n t n ex t ；j=l;b:w h i 1 e(p&j !=1)：p =p-n e x t：j+c:i f(!p)t h r o w e r r o r”d:r e t u r n p(7)按位查找函数自然语言描述：a：初始化工作指针p和计数器j,P 指向第一个结点，j=lb：循环以下操作,找到这个元素或者p指向最后一个结点:判断P 指向的结点是不是要查找的值，假如是，返回，否 则 P指向下一个结点
8、，并且j的值加一c:假如找到最后一个结点还没有找到要查找的元素，返回查找失败信息伪代码描述a:N o de *p=fr o n t-n e x t;j=1;b:w hile(p)：if(p-n e x t=x)r e t u r n jp=p -n ex tj+c:r e t u r n “er r o r”(8)插入函数自然语言描述:a:在堆中建立新结点b：将要插入的结点的数据写入到新结点的数据域c:修改新结点的指针域d:修改前一个指针的指针域，使其指向新插入的结点的位置伪代码描述a:N o d e *s=n ew N o d e;b：s-d at a=p-d at ac：s-n ex t
9、=p-n ex td:p-n ex t=se：p-d a t a=x(9)删除函数自然语言描述：a:从第一个结点开始,查找要删除的位数i 前一个位置i -1 的结点b:设 q指向第i 个元素c:将q元素从链表中删除d:保存q 元素的数据e：释放q元素伪代码描述a：q=p-n ex tb：p-n ex t=q n ex tc：x =q-dat ad:dele t e q2、代码具体分析(插入)：(1)从第一个结点开始，查找节点，使它的数据比X大，设p指向该结点:w hile(x p-dat a)p=p n e xt；(2)新建一个节点s,把P的数据赋给s：s -dat a=p-dat a；(3)
10、把s力 口 至Ij p后面:s-n ex t=p n e x t;p-n ex t =s;(4)p节点的数据用x替换:p-dat a=x ;示意图如图所示p-d a t as3、关键算法的时间复杂度：0(1)3.程序运营结果1.流程图：V2、结果截图d:CppvaderDebugvader.exe线性表的长度为：8遍历线性表结果为：12o二，46插入一个值后的线性表为:1I.456 d:CppvaderDebugvader.exe删除一个值后的线性表为：1一，4I第5个位置上的元素地址是:009E5440请按任意键继续.3.测试结论:可以对的的对链表进行插入,删除,取长度，输出操作。且插入任意
11、一个元素后,链表的顺序仍然是由小到大。4、给出代码（文末）4.总结1、问题书中已经给出析构、查找、插入、删除过程代码，遍历以及获取长度代码需要自己写出，刚开始写时一直出现各种基本错误,后来通过不断调试解决了问题。编写ma i n 函数时，调用插入删除等操作的代码一直编写失败,后自行查找资料后解决2、收获这次编程任务完毕地较为艰辛，但做完之后大大加深了自己对书中各个知识点的印象和理解。也学会了一些编写算法的小技巧，要有耐心，多看书复习知识。总之，这次实验使我印象深刻。#inc 1 ude u s in g n a m e s p a c e std；t e mp la t e struct No
12、de(ST data;struct No d e*n e x t;)；t em p 1 ate c 1 ass UnkL i s tp ub 1 i c:SLinkList()/无参构造I3(00front=new No d e；f r o n t-next=N ULL；)SLin k Li s t(T a,i nt n);/头插法0/LinkList(T a,i n t n);尾插法void PrintList()；按顺序遍历B in t Ge t Length();获取线性表的长度N o de *G et(inti)；获取第i个位置上的元素结点的地址S i nt L o c at e(T
13、x);/查找Bvoid I nsertfin t i,T x);插入0T Del e t e(int i);删除吃 Link Lis t()，销毁p r i v a te：0Node *fro n t;)；tempi a te Li n kL i st:L i n kList(T a,i nt n)/头插法fro n t=new N o d e;fron t-next=NULL；f o r(j n t i=n-1：i=0;i-)明Node*s=n ew Node；建立新结点s-da t a=a i;/给新结点数据域赋值团 s-nex t二frontnext;修改新结点的指针域0f r ontn
14、ext=s;修改头指针的指针域0/*t e mp 1 at e L i n kList：L i nkL i s t(T a,i nt n)尾插法(fr o n t=new No d e;Nod e *r=f ro n t;f o r(int i=0；i n；i+)N o de*s=new Node；s-data=a i；r-n e xt=s;r=s;)r-ne x t=N ULL：*/tem p I a te voi d LinkL i s t:Pri n tList()Node*p=fr o nt;0whi 1 e(p-n e x t!=NU L L)(3p=pnext;cout d ata
15、 e nd 1 ；0)temp 1 ate in t LinkList：G e tL e ng t h()(Nod e *p=f r o n t；in t n=0;while(p n e xt!=NULL)p=pnext：n+;I3r e tu r n n;)tem p late No d e *Li n kL i s t:G et(i nt i)(N od e*p=fro n t-next;int j=1;whil e(p&j!=i)p=p-next；S0j+；0 r eturn p;)tem p I a te v o id LinkL i st:：Insert(i n t i,0N o d
16、e*p=fro nt;if(i!=1 )瓯p=Get(i-1)；0i f(p)呢0Node*s=new Node;0 s-d a ta =x;s-n e x t=p-next;0pn e xt=s;0团else thr o w 位置错误;)templa t e T Link L i st:：D e 1 ete(int i)团 N o de *p=f r o nt;Bif(i!=1)p=G e t(i-1)；if(!p&!p-next)throw”位置错误”；Node *q=p n e xt;p-n ext=q-next：T x=q-data；delete q;1 3 r e t u r n x
17、;t em p I a te LinkUst:-LinkLi s t()N o de*p=fro n t；while(p)团 p=p-n e xt；0 del e t e fr o nt;函 fro nt=p;0)i n t mai n()const int n=8;intan=1,2,3,4,5,6,7,8；L in k List list(a,n)；国co u t”线性表的长度为:list.GetLe n g t h()end 1 ;c o u t e n d I;c o u t 遍历线性表结果为：e n d I;团 1 i st.PrintLis t();0 c ou t endl;Be o ut 插入一个值后的线性表为:e ndl;list.Inser t(1,0);团 1 ist.Pr i ntLi s t()：coutendl;0co u t v v 删除一个值后的线性表为:endl：list.Dele t e(l);团 lis t.PrintL i s t();团 c oute n d I;c out 第个位置上的元素地址是：en d I;0 c o ut list.Get(2)end I;0coutendl；list.-LinkLi s t()；syst e m(pau s e)；r eturn 0;)