2023年数据结构实验报告三线性表的链式存储.pdf

实验报告三线性表的链式存储班级：2023X X X 姓名:H oo&L e 学号:20 2 3 X X X X 专业：X X X X一、实验目的：(1)掌握单链表的基本操作的实现方法。(2)掌握循环单链表的基本操作实现。(3)掌握两有序链表的归并操作算法。二、实验内容：(请采用模板类及模板函数实现)1、线性表链式存储结构及基本操作算法实现 实 现 提 醒 (同 时 可 参 见 教 材 p 6 4-p 7 3 页 的 A D T 描述及算法实现及p p t)函数、类名称等可自定义，部分变量请加上学号后3 位。也可自行对类中所定义的操作进行扩展。所加载的库函数或常量定义：#i nc 1 u d e u s i ng n a m e s pa c e s t d ;(1)单链表存储结构类的定义：t e mpl a t e c 1 a s s L i n k L i s t p u b l i c:oL i nk L i s t ()；初始化带头结点空单链表构造函数实现L i n k L i s t (T a ,i nt n);运用数组初始化带头结点的单链表构造函数实现 L i n k L i s t O;i nt l e ng t h ();求单链表表长算法T g e t (i nt i);获得单链表中第i 个结点的值算法i nt 1 o c a t e (T t e m p);v o i d i ns e r t (i nt i,T t e mp);在带头结点单链表的第i 个位置前插入元素e算法T D e 1 e t e (i n t i);法v oi d pr i nt();f i b ool i s E mp t y ();ov oi d d e l e l e Al l ();构函数，但功能相同)pr i v a t e:帆 od e V T *h e a d；(2)初始化带头结点空单链表构造函数实现输入：无前置条件：无动作:初始化一个带头结点的空链表输出：无后置条件：头指针指向头结点。/初始化带头结点空单链表构造函数实现t e mpl a t e L i nk L i s t:：L i nk L i s t ()4i e a d =n e w Nod e；在带头结点单链表中删除第i 个元素算遍历单链表元素算法判单链表表空算法删除链表中所有结点算法(这里不是析4i e a d-ne x t -NU L L;)(3)运用数组初始化带头结点的单链表构造函数实现输入：已存储数据的数组及数组中元素的个数前置条件：无动作：运用头插或尾插法创建带头结点的单链表输出：无后置条件:头指针指向头结点,且数组中的元素为链表中各结点的数据成员.运用数组初始化带头结点的单链表构造函数实现t e mpl a t e L i nk L i s t:：L i nk L i s t(T a ,i n t n)h e a d =ne w N o de;h e a d ne x t=NU L L;f or (i n t i=0;i n；i+)(N o d e *s=n e w Nod e;s-d a t a=a i ;s-n e x t=h e a d -n e x t;h e a d ne x t=s；0(4)在带头结点单链表的第i个位置前插入元素e算法输入：插入位置i,待插入元素e前置条件：i的值要合法动作：在带头结点的单链表中第i个位置之前插入元素e输出：无后置条件：单链表中增长了一个结点在带头结点单链表的第i个位置前插入元素e算法t e m p l a t e v oi d L i nk L i s t：:i ns e r t(i n t i,T t e mp)o d e *p=h e a d;i n t c ou nt =0；w h i l e (p&c ou nt ne x t；oc ou n t +;nf (p=NU L L)c ou t ”i 不合法，越界!”；e 1 s e Nod e *s =ne w N o d e;d s-d a t a =t e m p;s-ne x t =p-ne x t；p-ne x t =s ;)(5)在带头结点单链表中删除第i个元素算法输入:删除第i个结点，待存放删除结点值变量e前置条件:单链表不空，i的值要合法动作:在带头结点的单链表中删除第i个结点，并返回该结点的值(由e传出)。输出：无后置条件:单链表中减少了一个结点在带头结点单链表中删除第i个元素算法t e m p 1 a t e T L i nk L i s t :：D e l e t e (i nt i )Nod e *p=h e a d;i nt co un t=0;a w h i l e (p&c ou nt ne x t ;c ou n t +4-;)i f (p=NU L L)c ou t M i 不合法,越界！”；I s e 。N o d e *s =p-n e x t；，T x=s -d a t a；p-ne x t =s -n e x t;a r e t u r n x；，)(6)遍历单链表元素算法输入:无前置条件：单链表不空动作：遍历输出单链表中的各元素。输出:无后置条件:无/遍历单链表元素算法t e mpl a t e v oi d L i nk L i s t ：:pr i nt ()o d e *p=h e a d -n e x t;w h i l e (p)c ou t d a t a V V op=p-ne x t;c ou t e nd l；(7)求单链表表长算法。输入：无前置条件:无动作:求单链表中元素个数。输出:返回元素个数后置条件:无/求单链表表长算法t e mpi a t e i nt L i nk L i s t :：1 e n g t h()Nod e *p =head；i nt c ou n t =0；ne x t ;o u n t+;r e t u r n c ou nt;)(8)判单链表表空算法输入：无前置条件:无动作:判表是否为空。输出：为空时返回L不为空时返回0后置条件:无/判断非空t e m p 1 a t e b o ol L i nk L i s t:：i s E mpt y()Nod e *p=h e a d ne x t;o i f (p)r e t u r n t r u e;e l s e r e t u r n f a l s e;)(9)获得单链表中第i 个结点的值算法输入:无前置条件:i 不空，i 合法动作:找到第i 个结点。输出:返回第i 个结点的元素值。后置条件：无获得单链表中第i 个结点的值算法t e mpi a t e T L i nk L i s t:get(i nt i )No d e *p=h e a d ;i nt c ou nt =0;w h i l e (p&c ou n t n e x t;c ou n t -H-;)nf (p-NU L L)co ut”i 不合法，越界!e I s e e t u r n p-d a t a;)(10)删除链表中所有结点算法(这里不是析构函数，但功能相同)输入:无前置条件:单链表存在动作：清除单链表中所有的结点。输出：无后置条件:头指针指向空/删除所有元素t e mpl a t e vo id L i nk L i s t:d e l e l e Al 1()N o d e *p =h e a d ;w h i l e (p)a Nod e *t=p；=pn e x t;t -n e x t=NU L L;(11)上机实现以上基本操作，写出ma i n()程序:参考p7 2vo id ma i n()H nt a 10 =1,2,3,4,5,6,7,8,9,0；/测试带参数的构造函数(前端插入！)oL i nk L i s t l i s t l(a,10);/测试插入d i f (l i s t l.i s E mpt y ()c ou t V链表不为空!”V e nd 1;)e l s e ，c ou t V”链表为空!”e nd l;)1 i s t 1.pr i n t ();oc ou t。测试插入*e n d l;4i s t l.i ns e r t (5,20);。1 i s t l.pr i nt();c o u t 测试表长”V e n d l;c ou t l i s t l.l e n g t h ()e n d 1;c ou t“测试删除V e nd l；oc ou t 1 i s t l.D e 1 e t e (5)e n d 1;d i s t 1.pr i nt ()；c ou t 测试得到第5个元素V e n d 1;c ou t 1 i s t 1.g e t (5)e n d l;空ou t V ”测试删除所有元素!V e nd 1 ;1 i s t l.d e l e l e Al 1();o 1 i s t l.p r i nt ();)粘贴测试数据及运营结果:，*D：t e x t c+D e b u g f x g f g f x g.e x e 回.链表不为空，0 9 8 7 6 5 4 3 2 1测试插入0 9 8 7 20 6 5 4 3 2 1测试表长11测试删除200 9 8 7 6 5 4 3 2 1测试得到第5个元素全试删除所有元素，Press any key to continue2,参考单链表操作定义与实现，自行完毕单循环链表的类的定义与相操作操作算法。t e mp 1 a t e c l a s s L i n k L i s t pu b l i e:L i nk L i s t (T a ,i nt n);运用数组初始化带头结点的单循环链表构造函数实现v oi d i ns e r t (i nt i,T t e m p);/在带头结点单循环链表的第i 个位置前插入元素e 算法oT D e l e t e(i n t i);在带头结点单循环链表中删除第i 个元素算法.v oi d p r i nt ();/遍历单循环链表元素算法pr i v a t e：Nod e *h e a d;i nt l e n g t h ;)；(1)运用数组初始化带头结点的单循环链表构造函数实现输入：已存储数据的数组及数组中元素的个数前置条件:无动作:运用头插或尾插法创建带头结点的单循环链表输出:无后置条件：头指针指向头结点，且数组中的元素为链表中各结点的数据成员，尾指针指向头结点。/运用数组初始化带头结点的单循环链表构造函数实现t e m p l a t e L i n k L i s t：L i nk L i s t(T a ,i n t n)h e a d=ne w Nod e；h e a d-n e x t=h e a d ；6 1 e n g t h =0;f or (i n t i =0;i n;i +)(Nod e *s=n e w Nod e;s-d a t a=a i ;岭 一 ne x t =h e a d-n e x t;h e a d-n e x t =s ;d e ng t h +;)(2)在带头结点单循环链表的第i 个位置前插入元素e 算法输入：插入位置i ,待插入元素e前置条件：i 的值要合法动作：在带头结点的单循环链表中第i 个位置之前插入元素e输出：无后置条件:单循环链表中增长了一个结点/在带头结点单循环链表的第i 个位置前插入元素e 算法t e mpl a t e v o i d L i nk L i s t:：i n s e r t (i nt i,T t e mp)空 o u t t h i s-l e ng t h e n d 1;N o d e *p=h e a d；nn t c ou nt =0;i f (i 1 e ng t h)c ou t V i 不合法，越界!”;岭1 s e M ile(c ou n t ne x t;g c ou n t+;6)3 N od e *s =n e w Nod e；e s-d a t a =t e mp;。s-n e x t =pn e x t；p-ne x t =s;)(3)在带头结点单循环链表中删除第i 个元素算法输入:删除第i 个结点，待存放删除结点值变量e前置条件：单循环链表不空,i的值要合法动作：在带头结点的单循环链表中删除第i 个结点，并返回该结点的值（由 e 传出）。输出：无后置条件：单循环链表中减少了一个结点在带头结点单循环链表中删除第i 个元素算法t e mp 1 a t e T L i nk L i s t :D e l e t e (i n t i)Nod e *p=h e a d ;d i n t c o u n t =0;i f (i l e ng t h)c ou t i 不合法，越界！V e nd l；d e l s e w h i l e(c ou n t ne x t；。c o u nt+;)爪 od e V T *s =p-ne x t;o T x=s-d a t a；p-n e x t =s-ne x t；r e t u r n x;)(4)遍历单循环链表元素算法输入:无前置条件:单循环链表不空动作:遍历输出单循环链表中的各元素。输出：无后置条件：无/遍历单循环链表元素算法t e mp 1 a t e v o i d L i nk L i s t ：:pr i n t ()No d e *p=h e a d-ne x t;w h i l e(p!=h e a d )c o u t p d a t a n e x t;oc ou t e nd l;)上机实现以上基本操作,写出ma i n()程序:v o i d ma i n()i nt a 10=1,2,3,4,5,6,7,8,9,0;/测试带参数的构造函数(前端插入!)L i nk L i s t l i s t 1(a,10);l i s t l.p r i nt()；y o u t ”测试插入 H e nd 1;1 i s t 1.i ns e r t (5,20)；d l i s t l.pr i n t ();c ou t V 测试删除操作 e n d 1;l i s t l.D e 1 e t e (5);4 i s t 1.pr i nt ();粘贴测试数据及运营结果:*D：textc+Debugfxgfgfxg.exe0 9 8 7 6 5 4 3 2 1测试插入100 9 8 7 20 6 5 4 3 2 1测试删除操作0 9 8 7 6 5 4 3 2 1Press any key to continue3、采用链式存储方式，并运用单链表类及类中所定义的算法加以实现线性表L a,Lb为非递减的有序线性表，将其归并为新线性表Lc,该线性表仍有序（未考虑相同时删除一反复值)的算法。模板函数：t e mpl a t e vo id L i nk L i s t ：a d d t w o(L i nk L i s t L a ,L i nk L i s t L b)N o d e *pl=L a.h e a d ne x t ;N o d e *p 2=L b.h e a d-ne x t ；i n t nu m=0;d w h i l e (pl&p2)4 f (pl-d ata p2-d a t a )f t t h i s i ns e r t (+nu m,pl-d a t a);s op 1=pl-ne x t;第 e l s e t h i s-i n s e r t (+n u m,p2-d a t a);a p 2=p2-ne x t ；)qi f (!pl)。（pl=p2;)w h i l e(p 1)f t t h i s i ns e r t(+nu m,p 1-d a t a)；pl=pl-ne x t；)v oi d m a i n()i nt a 5 =1,2,5,6,9；n n t b 5 =0,3,4,7,8 ;4,i n kL i s t 1 i s t 1(a ,5);L i nk L i s t 1 i s t 2(b,5);1 i s t 1.p r i nt ()；4 i s t 2.p r i n t ();L i nk L i s t 1 i s t 3；d i s t 3.a d d t w 0(l i s t l,l i s t 2);4 i s t 3.p r i nt()；d s y s t e m(pa u s e ”)；)粘贴测试数据及运营结果：9 6 5 2 18 7 4 3 09 8 7 6 5 4 3 2 1 0睛按任意键继续-al选做题：1、按一元多项式ADT的定义,实现相关操作算法:ADT P No d e isData系数(coef)指数(exp)指针域(next):指向下一个结点Oper a tion暂无e nd ADT P N o d eADT Poly nom i al isDat aP N。d e 类型的头指针。0 p erat i onP o l y nomail初始化值：无动作：申请头结点，由头指针指向该头结点，并输入m项的系数和指数，建立一元多项式。DestroyPolyn输入:无前置条件：多项式已存在动作:消毁多项式。输出:无后置条件:头指针指向空PolyDi s pla y输入:无前置条件：多项式已存在，不为空动作:输出多项式各项系数与指数输出：无后置条件:无AddPoly输入：另一个待加的多项式前置条件:一元多项式p a和 p b 已存在。动作及后置条件：完毕多项式相加运算，（采用pa=p a+pb形式,并销毁一元多项式pb）输出：无end AD T Poly n omi a 12、实现一元多项式的减法，操作描述如下：S u bPo 1 y输入：待减的多项式Pb前置条件:一元多项式p a 和 p b 已存在。动作及后置条件:完毕多项式减法运算，即：P a=p a-p b,并销毁一元多项式p b。输出：无3、参考P 7 4-P79页双向链表的存储结构定义及算法，编程实现双向链表的插入算法和删除算法。三、心得体会：（含上机中所遇问题的解决办法，所使用到的编程技巧、创新点及编程的心得）