《2023年数据结构实验报告单链表.docx》由会员分享，可在线阅读，更多相关《2023年数据结构实验报告单链表.docx（18页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、2 0 23级数据结构实验报告实验名称：实验一线性表一一题目1学生姓名：李文超班 级：班内序号：15 号:期：202 3年11月13日自然语言描述:a:在堆中建立新结点b :将要插入的结点的数据写入到新结点的数据域c :修改新结点的指针域d :修改前一个指针的指针域，使其指向新插入的结点的位置伪代码描述a : No de * s=new No d e ;b： s-d ata =p- d atac： s-nex t =p-nextd : p-next=se： p-d a ta= x(9)删除函数自然语言描述：a:从第一个结点开始,查找要删除的位数i前一个位置i - 1的结点b :设q指向第i个元
2、素c :将q元素从链表中删除d :保存q元素的数据e：释放q元素伪代码描述a： q=p-nextb ： p-next=q nextc： x =q-datad:dele t e q2、代码具体分析(插入)：(1)从第一个结点开始，查找节点，使它的数据比x大，设P指向该结点:while (xp-data) p=pn ext； (2)新建一个节点s,把p的数据赋给s： s -dat a =p-data：(3)把 s 力口至 Up后面:s nexl=pn ext; p- n ex t =s;(4) p节点的数据用x替换:p- d at a = x ;p-d a ta3、关键算法的时间复杂度：0(1)3
3、.程序运营结果1.流程图：初始化一个整形数组，作为赋值准备分别运用头插法和尾插法初始化，并且用遍历打印函数来显示数值执行插入函数，之后遍历打印函数来测试是否真的插入执行删除函数，之后遍历打印函数来测试是否真的删执行花侨杳找和带值杳杪函物2、结果截图 d:CppvaderDebugvader.exe线性表的长度为：8 幄历线性表结果为:123456国入一个值后的线性表为: 0123456，d:CppvaderDebugvader.exe删除一个值后的线性表为：146I,第5个位置上的元素地址是: 009E5440请按任意键继续.3 .测试结论:可以对的的对链表进行插入，删除，取长度，输出操作。且
4、插入任意一个元素后, 链表的顺序仍然是由小到大。4、给出代码（文末）.总结1 问题书中已经给出析构、查找、插入、删除过程代码，遍历以及获取长度代码需要自己写 出，刚开始写时一直出现各种基本错误,后来通过不断调试解决了问题。编写ma in函数时，调用插入删除等操作的代码一直编写失败,后自行查找资料后解2、收获这次编程任务完毕地较为艰辛，但做完之后大大加深了自己对书中各个知识点的印象 和理解。也学会了一些编写算法的小技巧，要有耐心，多看书复习知识。总之，这次实验使我 印象深刻。# include using n am e s p a c e std：t e mp 1 a t e struct No
5、de(0T data;struct No d e * next;)：t em p 1 ate c I ass Link Li s t(P ub 1 i c:0LinkList() / /无参构造0(PEfront = new No d e：f r o n t-next = NULL；)0Lin k Li s t( T a, i nt n )；/ / 头插法0/Link L ist(T a, i n t n);尾插法void PrintList )； 按顺序遍历0 i n t Ge t Length();获取线性表的长度N o de * G c t(int i)： 获取笫i个位置上的元素结点的地
6、址i nt L o c at e (T x ) ; / / 查找0void I nsert(in t i, T x);插入0T Del e t e (int i );删除ETUnkListO ；销毁p r i v a te：ENode * fro n t;)；tempi a t e Li n kL i st:L i n kList(T a, i nt n) / /头插法fro n t = new Nod e;fron t -next = NU LL：f o r (i n t i = n - 1； i = 0; i-)0(Node * s = n ew Node;建立新结点s-da t a =
7、a i ;/ /给新结点数据域赋值0 s -nex t =frontnext;修改新结点的指针域闭front next = s; 修改头指针的指针域0)/*t e mp 1 at e Lin kList： ： L i nkL i s t (T a(, i nt n ) 尾插法(fro nt=new Nod 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=NULL；*/tern p I a te voi d LinkL i
8、 s t : Pri n tList ()N ode * p = fr o nt;0whi 1 e(p- n e x t != NU L L) Ep = pnext;cout d ata 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+; r e tu r n n;)tem p late No d e * Li n kL i s t :Get ( i nt i ) (Nod e * p =
9、fr o n t -next;intj= 1;whil e ( p &j != i)(p = P -next：00j+：1 .实验规定实验目的：根据线性表的抽象数据类型的定义，选择下面任一种链式结构实现线性表，并完毕线性 表的基本功能。线性表存储结构（五选一）：1、带头结点的单链表2、不带头结点的单链表3、循环链表4、双链表5、静态链表线性表的基本功能：1、构造：使用头插法、尾插法两种方法2、插入：规定建立的链表按照关键字从小到大有序3、删除 4、查找0 r eturn p;tem p I a te v o id LinkL i st:： Insert (i n t i, T x )N o d
10、e * p = f r o nt;if(i != 1 )03p = G et( i -1)；0i f (P)0(0Node * s = new Node；0s- d ata = x;sn e x t = p -next;p-n e xt = s;即Elelse throw位置错误;templa t e T LinkL i st:： D e 1 ete (int i)(0N o de * p = f r o nt;0if (i != 1 ) p = Get (i- 1)；if(!p & !p-next) throw位置错误”；Node * q = p- n e xt;P - n ext = q
11、-next；Tx = q -data：delete q;0 r e t u r n x;)t em p I a te LinkList:wLinkLi s t()(HN o de * p = fro n t ：w hile (p)0(p = p-n e xt；H del e t e fr o nt;00front = p;0)i n t mai n ()(const int n = 8;int an = 1,2,3,4, 5,6,7, 8)；Link List list(a, n )；0co u t ”线性表的长度为: list.GetLe n g t h ) end 1 ;c o u t e
12、 n d I;c o u t 遍历线性表结果为：Ve n d I;0 1 i st.PrintLis t ();0 c ou t endl;0 c o ut ”插入一个值后的线性表为: V e ndl;list. Inser t (1, 0 );0 1 ist. Pr i ntLi s t()；coutendl;0cou t 删除一个值后的线性表为:endl：list.Dele t e(l);Olis t .PrintL i s t ();0 c oute n d I；c out 第个位置上的元素地址是：en d I;0 c o ut list.Get(2) end I ;0coutendl；
13、Pllist. LinkU s t ()；syst e m (pau s e)：r eturn 0;5、获取链表长度 6、销毁7、其他:可自行定义编写测试ma i n()函数测试线性表的对的性。2 .程序分析2. 1存储结构单链表的存储：(1)链表用一组任意的存储单元来存放线性表的结点。这组存储单元既可以是连续的, 也可以是不连续的，甚至零散地分布在内存的某些位置。(2)链表中结点的逻辑顺序和物理顺序不一定相同。为了能对的表达结点间的逻辑关系, 在存储每个元素值的同时,还要存储该元素的直接后继元素的位置信息，这个信息称为指针 或链。结点结构a 11da ta域-存放结点值的数据域a | da
14、t a | ne x t |next域 存放结点的直接后继的地址的指针域a 114单链表在内存中的存储示意内存单元地址头指针一f rcn42关键算法分析 1、关键算法:（1）头插法自然语言描述:a :在堆中建立新结点b：将ai写入到新结点的数据域c：修改新结点的指针域d：修改头结点的指针域。将新结点加入链表中伪代码描述a： Node * s=new Node b :s-data=aic: s-ne x t = front n e xt;d : f r o n t -n e xt=s(2)尾插法自然语言描述：a :在堆中建立新结点：b :将a i 写入到新结点的数据域：c :将新结点加入到链表中
15、d：修改修改尾指针伪代码描述a: No de * s=new Node b:s-data= a ic:r-ne x t =s;d:r= s(3)遍历打印函数自然语言描述：a ：判断该链表是否为空链表,假如是,报错b:假如不是空链表,新建立一个temp指针c:将lemp指针指向头结点d ：打印t cmp指针的d a ta域e:逐个往后移动tem p指针,直到t emp指针的指向的指针的next域为空伪代码描述a : I f f r ont- n e x t = =NU1. LThrow a n emp t y 1 ist ”NodeT* t e mp= f r o n t -ne x t；b:w
16、hile (temp- n ext)c :cout data next;(4 )获取链表长度函数自然语言描述:a :判断该链表是否为空链表，假如是，输出长度0b:假如不是空链表，新建立一个temp指针，初始化整形数n为。c：将temp指针指向头结点d :判断temp指针指向的结点的ne x t域是否为空，假如不是,n加一，否则re t urn ne ： 使temp指针逐个后移,反复d操作，直到temp指针指向的结点的ne x t 域为0,返回n伪代码描述a: if ront- n ex t =NULLb： No d e* tem p = f r ont-next;w h ile (tem p
17、n ext)c: tem p =temp-n ext;(5)析构/删除函数自然语言描述：a :新建立一个指针,指向头结点b：判断要释放的结点是否存在，c:暂时保存要释放的结点d:移动a中建立的指针e :释放要释放的指针伪代码描述a： Node * p=frontw h ile (p)c： f r on t =pd:p=p-nexte： del e t e f r ont(6)按位查找函数自然语言描述：a:初始化工作指针p和计数器j, p指向第一个结点,j = lb:循环以下操作，直到p为空或者j等于1:P指向下一个结点:j加1c:若p为空,说明第i个元素不存在，抛出异常d:否则，说明p指向的元
18、素就是所查找的元素,返回元素地址 伪代码描述a:Node * p=fron t -nex t ； j=l;b :wh i 1 e(p&j!=l)：P =p-ne x t：j +b: i f (! p) throw ”er rorwd:re t u rn p(7)按位查找函数自然语言描述：a：初始化工作指针p和计数器j, P指向第一个结点，j=lb：循环以下操作，找到这个元素或者p指向最后一个结点:判断P指向的结点是不是要查找的值，假如是，返回j，否则P指向下一个 结点，并且j的值加一c:假如找到最后一个结点还没有找到要查找的元素，返回查找失败信息伪代码描述a: Node * p=fr o nt- n e x t; j= 1 ;b: while(p)： if(p-ne x t=x) re t urn jp= p -nextj+c: r e tur n “error”(8)插入函数