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

《2023年数据结构实验报告三线性表的链式存储.docx》由会员分享，可在线阅读，更多相关《2023年数据结构实验报告三线性表的链式存储.docx（13页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、实验报告三线性表的链式存储班级：2023XXX 姓名: HoogLe 学号: 20 2 3 XXXX 专业：XXXX实验目的：(1)掌握单链表的基本操作的实现方法。(2)掌握循环单链表的基本操作实现。(3)掌握两有序链表的归并操作算法。一、 实验内容：(请采用模板类及模板函数实现)1、线性表链式存储结构及基本操作算法实现实现提醒(同时可参见教材P 64-p7 3页的ADT描述及算法实现及p p t)函数、类 名称等可自定义，部分变量请加上学号后3位。也可自行对类中所定义的操作进行扩展。 所加载的库函数或常量定义：#inc 1 u de u s i ng n a me s pace s t d

2、;(D单链表存储结构类的定义：tempi at e c 1 as s Lin k Lis t p ublic:电inkL ist ()；初始化带头结点空单链表构造函数实现Li n kList (T a , in t n); 运用数组初始化带头结点的单链表构造函数实现Li n kListO ;e i nt length ();求单链表表长算法T get int i);获得单链表中第i个结点的值算法1 nt 1 o ca t e (T temp);v o i d ins e rt (int i, T temp); 在带头结点单链表的第i个位置前插入元素e算法fi D:textc+Debugfxgf

3、gfxg.exe0 j 回膜表不为空，El0987654321测试插入0987 20 654321测试表长年试删除 200987654321测试得到第5个元素 6测试删除所有元素，Press any key to continue2、参考单链表操作定义与实现，自行完毕单循环链表的类的定义与相操作操作算法。temp 1 atec lass L i nkL i s tpub lie:乩inkList (T a口，in t n);运用数组初始化带头结点的单循环链表构造函数实现v oid i nsert (int i, T temp);/在带头结点单循环链表的第i个位置前插入元素e算法oT Dele

4、te(i n t i);在带头结点单循环链表中删除第i个元素算法woid p rint 0 ;/遍历单循环链表元素算法pr i v ate：Nod e * h e ad;int le n g t h ;(1)运用数组初始化带头结点的单循环链表构造函数实现输入：已存储数据的数组及数组中元素的个数前置条件:无动作:运用头插或尾插法创建带头结点的单循环链表输出:无后置条件：头指针指向头结点，且数组中的元素为链表中各结点的数据成员，尾指针指向头结点。/运用数组初始化带头结点的单循环链表构造函数实现temp lat e L i nk List： LinkList(T a , in t n) h e a

5、d=new Node ；head-n e xt= he a d ；1 e n gth = 0;for (i n t i =0; in; i +)(Nod e *s= n ew Node;s -data=a i;岭一ne x t = h ead- n ext;h e ad-n e x t = s ;4engt h +;q(2)在带头结点单循环链表的第i个位置前插入元素e算法输入：插入位置i ,待插入元素e 前置条件：i的值要合法 动作：在带头结点的单循环链表中第i个位置之前插入元素e输出：无后置条件:单循环链表中增长了一个结点/在带头结点单循环链表的第i个位置前插入元素e算法t e mplate

6、void LinkL ist:： in s e r t( i nt i, T temp) oc o utth i s-l e ngt h en d 1;N o d e *p = head；nn t count = 0 ;i f (i 1 e ng t h) co u t Vi 不合法，越界!”；el s e(wh i 1 e (coun t next;g cou n t+;。o Node * s = n e w Node；o s-dat a = t emp;o s-n e xt = pn e xt； p-next = s;)(3)在带头结点单循环链表中删除第i个元素算法输入:删除第i个结点，待

7、存放删除结点值变量e前置条件：单循环链表不空,i的值要合法 动作：在带头结点的单循环链表中删除第i个结点，并返回该结点的值(由e传出)。输出：无后置条件：单循环链表中减少了一个结点在带头结点单循环链表中删除第i个元素算法temp 1 a t e T L inkLis t : :D e let e (in t i) Node *p = head ;i n t c oun t = 0;if (il e ngth)couti 不合法，越界！ * e ndl；lse府h i le(coun t next；a c o u nt+;4Node * s = p-next;。 T x= s- d a ta；o

8、p- n ext = s-next；return x;0)(4)遍历单循环链表元素算法输入:无前置条件:单循环链表不空动作:遍历输出单循环链表中的各元素。输出：无 后置条件：无/遍历单循环链表元素算法temp 1 atevo i d LinkLis t ： :prin t () No d e *p = h e ad-ne x t;while(p! =h e ad ) cou t p da t a n ext;4弟ou tV Vendl;)上机实现以上基本操作，写出m a in ()程序:void mainO int a10= 1, 2, 3,4,5, 6, 7, 8, 9, 0;/测试带参数的

9、构造函数(前端插入!)LinkList lis t 1 (a, 10);listl. p r int()；c o ut“测试插入e n d 1 ;I i st 1 . insert ( 5 , 20)；distl. prin t ();ocou tV”测试删除操作H en dl;II s tl. De 1 ete (5);4 i st 1. print ();粘贴测试数据及运营结果:1- *D:textc+ +Debugfxgfgfxg.exe_ _ o 1 小府 9 87654321二测试插入100987 20 654321测试删除操作”87654321Press any key to co

10、ntinue.3、采用链式存储方式，并运用单链表类及类中所定义的算法加以实现线性表La, Lb为非 递减的有序线性表，将其归并为新线性表Lc,该线性表仍有序(未考虑相同时删除一反复 值)的算法。模板函数：templatevoid LinkL i st： add t wo(LinkList L a , LinkList Lb) Nod e *pl=La. headnex t ;Nod e * p 2 =Lb. h e a d-nex t ；in t num=0;whil e (pl&p2) i f (pl-d ata p2-da t a ) ( this-inse r t (+num, pl-d

11、 a ta);o op 1 =pl-ne x t;aels e t h i s- i n sert (+n u m, p2- d ata); p 2=p2-ne x t ；)4if (! Pl)pl=p2;)while(p1)thisinse r t(+num, p 1 data)；pl=plnext；4void m a i n() i nt a 5 = 1,2,5,6,9；nnt b5 = 0, 3, 4,7, 8 ;oLi nkLis t 1 i s t 1 ( a , 5);L i nkLi s t 1 is t 2(b, 5);1 i s t 1. p r int ()；a1 i st

12、2. p r int ();LinkList 1 i st 3；dis t 3. addtw o (listl, list2);dis t 3. p r int()； s ys t em(*pa u se )；)粘贴测试数据及运营结果：i D:textc + 4-linkedlistDebuglinkedlist.exe9 6 5 2 1B 7 4 3 0 9876543210 请按任意键继续. .选做题：1、按一元多项式ADT的定义，实现相关操作算法:ADT PNo d e isData系数(c oef)指数(exp)指针域(next):指向下一个结点Oper a tion暂无end ADT

13、 PNod eADT Poly nom i al isDat aPN。de类型的头指针。0 p erat i onPol y nomail初始化值：无动作：申请头结点，由头指针指向该头结点，并输入m项的系数和指数，建立一元多项式。DestroyPolyn输入:无前置条件：多项式己存在动作:消毁多项式。输出:无后置条件:头指针指向空PolyDi s play输入:无前置条件：多项式已存在，不为空动作:输出多项式各项系数与指数输出：无后置条件:无AddPoly输入：另一个待加的多项式前置条件:一元多项式pa和p b已存在。动作及后置条件：完毕多项式相加运算，（采用pa=pa+pb形式，并销毁一元多

14、项式pb）输出:无end AD T Poly n omi a 12、实现一元多项式的减法，操作描述如下：S u bPo 1 y输入：待减的多项式Pb前置条件:一元多项式p a和pb己存在。动作及后置条件:完毕多项式减法运算，即：pa=pa-p b,并销毁一元多项式p b。输出：无3、参考P 7 4-P79页双向链表的存储结构定义及算法，编程实现双向链表的插入算法和删 除算法。三、心得体会：（含上机中所遇问题的解决办法，所使用到的编程技巧、创新点及编程 的心得）T De 1 e t e (in t i);法voi d print();ebool i s Em p t y ();void del

15、e leAll ();构函数，但功能相同)priv ate:eNode * h ead；)；(2)初始化带头结点空单链表构造函数实现输入：无前置条件：无动作:初始化一个带头结点的空链表输出：无后置条件：头指针指向头结点。/初始化带头结点空单链表构造函数实现t e mpl a teLinkLis t :： L i nkLis t () ohe a d = n ew Node；在带头结点单链表中删除第i个元素算遍历单链表元素算法判单链表表空算法删除链表中所有结点算法(这里不是析4ie a d-next = NULL;)(3)运用数组初始化带头结点的单链表构造函数实现输入：已存储数据的数组及数组中元

16、素的个数前置条件：无 动作：运用头插或尾插法创建带头结点的单链表输出：无后置条件:头指针指向头结点，且数组中的元素为链表中各结点的数据成员。运用数组初始化带头结点的单链表构造函数实现t empla t eL i nkList:： L i nkList(T a,int n) hea d =new Node ;he a dnext=NULL;for (i n t i=0; in； i+)(No d e *s=n ew Node;s- d ata=ai;s-n ext =hea d - n ext;h ead next=s；0(4)在带头结点单链表的第i个位置前插入元素e算法输入：插入位置i,待插入

17、元素e前置条件：i的值要合法动作：在带头结点的单链表中第i个位置之前插入元素e输出：无后置条件：单链表中增长了一个结点在带头结点单链表的第i个位置前插入元素e算法tem p latev oid LinkL i st： :insert (in t i, T temp)N o d e *p = head;in t count = 0；w h ile (p&countnext；ac oun t +;)nf (p=NULL) couti 不合法，越界!”；e 1 s e Node * s = new Nod e;岭一data = tem p ;s-next = p-next；p - next = s

18、;0)(5)在带头结点单链表中删除第i个元素算法输入:删除第i个结点，待存放删除结点值变量e前置条件:单链表不空，i的值要合法动作:在带头结点的单链表中删除第i个结点,并返回该结点的值(由e传出)。输出：无后置条件:单链表中减少了一个结点在带头结点单链表中删除第i个元素算法tem p 1 a t e T LinkLi s t:： Delet e (int i ) Nod e *p = h ead;int count = 0 ;while(p& c ountnex t ;c oun t +;i f (p=NULL) cout n i 不合法，越界！；e Ise o N o d e *s = p-

19、n e xt； T x= s - d ata；p-next = s -n ext;ar eturn x；0)(6)遍历单链表元素算法输入:无前置条件：单链表不空动作：遍历输出单链表中的各元素。输出：无后置条件:无/遍历单链表元素算法templa t ev oid L inkLis t ： :print()N o de *p = hea d -n e xt;whil e ( p ) c ou t p-datanext;4c o u t e n dl；(7)求单链表表长算法。输入：无前置条件:无动作:求单链表中元素个数。输出:返回元素个数后置条件:无/求单链表表长算法tempi a tei nt

20、L i nkLi s t:： 1 e n g t h() Nod e *p = head；int cou n t = 0；whi 1 e (p) p=p-nex t ;c o u n t+;)r e turn count;)(8)判单链表表空算法输入：无前置条件:无动作:判表是否为空。输出：为空时返回1,不为空时返回0后置条件:无/判断非空tem p 1 a t eb o ol L i nkList:： i sEmpty() Node *p = headnext; i f (p) ret urnt rue;else ret urn false;)(9 )获得单链表中第i个结点的值算法输入:无前

21、置条件:i不空，i合法动作:找到第i个结点。输出:返回第i个结点的元素值。后置条件：无获得单链表中第i个结点的值算法tempi at e T LinkLi s t: g et (int i) Nod e *p = head ;int c ount = 0 ;owhil e (p&co u n tn e xt;coun t +;)if (p =NULL) couti 不合法，越界!e Is e r e t urn p- d ata;(10)删除链表中所有结点算法(这里不是析构函数，但功能相同)输入:无前置条件:单链表存在动作：清除单链表中所有的结点。输出：无后置条件:头指针指向空删除所有元素te

22、mpiat e void Li nkList: :del e leAl 1 () Nod e *p = head ;while ( p)Node *t=p；p =pn e xt;t- n e x t=NULL;4)(11)上机实现以上基本操作，写出ma in。程序：参考p7 2void mai n () int a10 = 1,2, 3 , 4,5, 6, 7,8, 9,0；/测试带参数的构造函数(前端插入!)eLinkL i st 1 is t 1 ( a , 1 0 );/测试插入nf (li s tl. isEmpty () coutCV”链表不为空！ Vendl ;el s e 。co

23、utV”链表为空!e ndl;1 is t 1. pri n t ();cou t “测试插入 u end 1 ;dis tl. ins e r t (5, 20);o 1 istl. print();c ou t “测试表长”Ve ndl;c ou t listl. length () e n d 1;cout测试删除V e ndl；ocout 1 istl. De 1 e t e ( 5 )en d 1 ;dis t 1. print ()；cout测试得到第5个元素”Xen d 1;cout 1 ist 1 . g et ( 5 ) e ndl;ocout u测试删除所有元素! ”Vend 1 ;1 i stl. d elel e Al 1 ();o 1 istl. p rint ();)粘贴测试数据及运营结果: