1、實(shí)驗(yàn)報(bào)告三線性表的鏈?zhǔn)酱鎯?chǔ)班級(jí)： 2010XXX 姓名:HoogLe 學(xué)號(hào)： 2010XXXX 專業(yè)： XXXX一、實(shí)驗(yàn)?zāi)康模?1) 掌握單鏈表的基本操作的實(shí)現(xiàn)方法。(2) 掌握循環(huán)單鏈表的基本操作實(shí)現(xiàn)。(3) 掌握兩有序鏈表的歸并操作算法。二、實(shí)驗(yàn)內(nèi)容：(請(qǐng)采用模板類及模板函數(shù)實(shí)現(xiàn))仁線性表鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)及基本操作算法實(shí)現(xiàn)實(shí)現(xiàn)提示(同時(shí)可參見教材p64-p73貝的ADT描述及算法實(shí)現(xiàn)及ppt)函數(shù).類名稱 等可自定義，部分變量請(qǐng)加上學(xué)號(hào)后3位。也可自行對(duì)類中所定義的操作進(jìn)行擴(kuò)展。所加載的庫函數(shù)政常量定義：# i ncl ude < i ostrea m> using n amesp

2、ac e std;(1) 單鏈表存儲(chǔ)結(jié)構(gòu)類的定義：template<class T>class L i nkListp u b I ic:o LinkLi sto； /初始化帶頭結(jié)點(diǎn)空單鏈表構(gòu)造函數(shù)實(shí)現(xiàn)o Li nkList (T a, i nt n) ；/利用數(shù)組初始化帶頭結(jié)點(diǎn)的單鏈表構(gòu)造函數(shù)實(shí)現(xiàn) L i nk L i st ();i nt length ();求單鏈表表長算法T get (int i);獲得單鏈表中第i個(gè)結(jié)點(diǎn)的值算法» int I ocate(T tomp );o void in se r t(i n t i, T t emp) 元素e算法T Del

3、ete(int i);o voi d pr i nt 0;o booI i s Emp tyO;void deIeIeA I I();析構(gòu)函數(shù)，但功能相同)p r i v a t e :Node<T> *head；;(2) 初始化帶頭結(jié)點(diǎn)空單鏈表構(gòu)造函數(shù)實(shí)現(xiàn) 輸入：無前置條件:無動(dòng)作：初始化一個(gè)帶頭結(jié)點(diǎn)的空鏈表輸出：無后置條件：頭指針指向頭結(jié)點(diǎn)。/初始化帶頭結(jié)點(diǎn)空單儺表構(gòu)造函數(shù)實(shí)現(xiàn) tern p la t e<c I a ss T>L i n kL i st<T>: L i nkL i s t () h ea d = new N o de< T>

4、/在帶頭結(jié)點(diǎn)單鏈表的第i個(gè)位置前插入/在帶頭結(jié)點(diǎn)單鏈表中刪除第i個(gè)元素算法/遍歷單鏈表元素算法判單鏈表表空算法刪除鏈裘中所有結(jié)點(diǎn)算法(這里不是數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告三線性表的鏈?zhǔn)酱鎯?chǔ)head >next = NULL ;(3) 利用數(shù)組初始化帶頭結(jié)點(diǎn)的單鏈表構(gòu)造函數(shù)實(shí)現(xiàn)輸入：已存儲(chǔ)數(shù)據(jù)的數(shù)組及數(shù)組中元素的個(gè)數(shù)前置條件：無動(dòng)作：利用頭插或尾插法創(chuàng)建帶頭結(jié)點(diǎn)的單鏈表輸出：無后置條件:頭指針指向頭結(jié)點(diǎn)，且數(shù)組中的元素為鏈表中各結(jié)點(diǎn)的數(shù)據(jù)成員。/利用數(shù)組初始化帶頭結(jié)點(diǎn)的單鏈表構(gòu)造函數(shù)實(shí)現(xiàn)temp I ate<c I ass T>L i nkList<T>: Lin k List

5、 (T a , int n) head=new Node<T>head->ne x t=NULL;f or ( i nt i =0; j <n; i +)N ode<T> * s =new Nod e<T>s->d at a=a i ;s-> n ext=head->ne x t;head->nex t ;。(4) 在帶頭結(jié)點(diǎn)單鏈表的第i個(gè)位jt前插入元素6算法輸入:插入位置i,待插入元素e前置條件：i的值要合法動(dòng)作：在帶頭結(jié)點(diǎn)的單鏈表中第i個(gè)位JL之前插入元素e輸出：無后置條件：單鏈表中增加了一個(gè)結(jié)點(diǎn)/在帶頭結(jié)點(diǎn)單鏈表的

6、第i個(gè)位置前插入元素e算法t emp I at e<c lass T>void L i n k L ist<T>: i n ser t ( i rrt i, T temp) No d e<T> *p = hea d ;» int co u n t =0；while ( p&&c o uni -1)s p=p >n ext;$ count+;。o if (p=NULL) cout«”i 不合法，越界！ n;o e I s e Node<T> s = new Nod e <T>:s s->d

7、at a = temp;» s->nex t = p->next;p > n ex t = s;(5) 在帶頭結(jié)點(diǎn)單鏈表中刪除第i個(gè)元素算法輸入：刪除第i個(gè)結(jié)點(diǎn)，持存放刪除結(jié)點(diǎn)值變量e前置條件:單鏈表不空，i的值要合法動(dòng)作：在帶頭結(jié)點(diǎn)的單鏈表中刪除第i個(gè)結(jié)點(diǎn)，并返回該結(jié)點(diǎn)的值(由e傳出)。輸出：無后置條件：單鏈表中減少了一個(gè)結(jié)點(diǎn)/ /在帶頭結(jié)點(diǎn)單鏈表中刪除第i個(gè)元素算法tempi ate<cl a$s T>T Lin k Li s t<T>: :Del ete (int i ) 9 Node<T> *p = head;int co

8、unt = 0;» wh i I e(p&&coun t V i-1) p =p->next;count+;9 o 汗 (p=NULL) cout«"i 不合法，越界L;» e I se» N ode<T> *s = p->next;T x= s-> data;» o p->n e xt = s->next；° ret u rn x;。(6) 遍歷單鏈表元素算法綸入：無前置條件：單鏈表不空動(dòng)作:遍歷輸出單鏈表中的各元素。輸出：無后置條件：無/遍歷單鏈表元素算法t e

9、mpla t e <c I ass T>vo i d Li n kL is t <T>: print () o No d e<T> *p = head-> n ext;while ( p) $ co u t« p > d ata«w w;p=p>next;o cout«end I ;(7) 求單璉表表長算法。輸入：無前暨條件:無動(dòng)作：求單鏈表中元素個(gè)數(shù)。輸出：返回元素個(gè)數(shù)后置條件：無/求單鏈表表長算法tern p I a t e<class T>int L i nkL i st<T>:

10、I engt h 0 o Node<T> *p = he ad;» int count = 0;while (p) p= p ->n ext;c o u nt+;return co u nt；(8) 判單鏈表表空算法輸入：無前置條件：無動(dòng)作：判表是否為空。輸出：為空時(shí)返回1,不為空時(shí)返回0后置條件：無判斷非空t empl ate<class T>bool Lin k List<T>: i s Emp t y 0 Nod e<T> * p = h e a d->n e xt;if (p) ret urn t rue;o els

11、eretu r n false;(9) 獲得單鏈表中第i個(gè)結(jié)點(diǎn)的值算法輸入：無前置條件：i不空，i合法動(dòng)作：找到第i個(gè)結(jié)點(diǎn)。輸出：返回第i個(gè)結(jié)點(diǎn)的元素值。后置條件:無/獲得單鏈表中第i個(gè)結(jié)點(diǎn)的值算法temp I ate<c I ass T>T LinkL is t<T>: :get(int i) No d e<T> *p = h ea d ;i nt count =0；wh i I e (p & &co u nt< i ) p=p->next;o 3 count+;i f (p=NULL) c o ut« n i 不合法

12、，越界！ 7» e Ise » return p>da t a;(10) 刪除鏈表中所有結(jié)點(diǎn)算法(這里不是析構(gòu)函數(shù)，但功能相同)輸入：無前矍條件：單鏈表存在動(dòng)作：清除單鏈表中所有的結(jié)點(diǎn)。輸出：無后置條件:頭指針指向空/刪除所有元素temp la t e <c I as s T>void LinkList<T>: deleleAl I () Node<T> *p = h e ad;while (p)Node<T> *t=p;p =p->next;» 3 t->n e xt=NULL；。(11) Ji機(jī)

13、實(shí)現(xiàn)以上基本操作，寫出mainO程序： 參考P72void mainO o int a10=1,2, 3, 4, 5, 6,7,8, 9, 0；/測(cè)試帶參數(shù)的構(gòu)造函數(shù)(前端插入!)L inkLis t < i nt> I ist1 (a, 1 0); /測(cè)試插入i f (Iist 1 < isEmpty 0 ) cout« M鏈表不為空！ M «endI;else » 3 c out«R鏈表為空! M«en d I;I ist1. print();o cout« w 測(cè)試插入 H «en d I;Q I i

14、sth insert (5, 20);o I i st1. p r i nt ();o cout<V”測(cè)試表長n«end I ;c ou t «I i st 1 . I engt h () «e n d I;0 co u t «"«試刪除n«endl; cout«l ist1. De I ete(5)<<endl;» I is 11. pr in t ();cout<< ”測(cè)試得到第5個(gè)元素nVV e nd I ; co u t «l ist1. get (5) &

15、lt;<e n d I ;。cout<V”測(cè)試刪除所有元素!n«end I; listk de I el eAll ();I ist1. pr int ();粘貼測(cè)試數(shù)據(jù)及運(yùn)行結(jié)果： "D:textc+ -rDebugfxgfgfxg.exe"2、矣考單鏈表操作定義與實(shí)現(xiàn)，自行完成單循環(huán)鏈表的類的定義與相操作操作算法。 temp I a t e <c I a s s T> c lass Lin k L ist p ubl i c:Li nkL i st(T a, int n);/利用數(shù)組初始化帶頭結(jié)點(diǎn)的單循環(huán)鏈表構(gòu)造函數(shù)實(shí)現(xiàn) vo i d

16、insert (int i,Tt emp);/在帶頭結(jié)點(diǎn)單循環(huán)鏈表的第i個(gè)位置前插入元素e算法o T De I ete(i nt i ) ;/在帶頭結(jié)點(diǎn)單循環(huán)鏈表中刪除第i個(gè)元素算法vo j d p r i ntO;/遍歷單循環(huán)鏈表元素算法pr ivat e : o N o d e<T> *he a d;int length;(1) 利用數(shù)組初始化帶頭結(jié)點(diǎn)的單循環(huán)鏈表構(gòu)造函數(shù)實(shí)現(xiàn)輸入：已存儲(chǔ)數(shù)據(jù)的數(shù)組及數(shù)組中元素的個(gè)數(shù)前置條件：無動(dòng)作：利用頭插或尾插法創(chuàng)建帶頭結(jié)點(diǎn)的單循環(huán)鏈表輸出：無后置條件：頭指針指向頭結(jié)點(diǎn)，且數(shù)組中的元素為鏈表中各結(jié)點(diǎn)的數(shù)據(jù)成員，尾指針指向頭 點(diǎn)。/利用數(shù)組初始

17、化帶頭結(jié)點(diǎn)的單循環(huán)鏈表構(gòu)造函數(shù)實(shí)現(xiàn)temp lat e <c lass T>Li nkLi st<T>: LinkL i s t (T a, i n t n) he a d= n ew Nod e <T>he a d >n ext = h e ad ;» I e n g th = 0 ;for (i n t i =0: i<n; i+)Node< T > *s=ne w Node<T>s > d at a=a i ;o s-> n e xt = h e ad->ne x t;h e ad>

18、nex t 二s;» I ength+;(2) 在帶頭結(jié)點(diǎn)單循環(huán)鏈表的第i個(gè)位置前插入元素e算法輸入：插入位置i,待插入元素e前置條件：i的值要合法動(dòng)作:在帶頭結(jié)點(diǎn)的卑循環(huán)鏈表中第i個(gè)位置之前插入元素e輸出：無后置條件：單循環(huán)鏈表中增加了一個(gè)結(jié)點(diǎn)/在帶頭結(jié)點(diǎn)單循環(huán)鏈表的第i個(gè)位置前插入元素e算法tem p lat e<class T>vo i d L in kLi s t<T>: inse r t (i nt i, T t emp)(cout«this->le n gth«endI;Nod e<T> *p = he a d

19、 ;intcount=O;i f (i>l ength) cou t« n i 不合法，越界！” ;» el s e (» whi I e (count<i-1) p=p->next;co u n t+;八» 3 Node<T> *s = new Node<T>、s-> data = t emp;s->n e xt = p>next;p->next = s;(3) 在帶頭結(jié)點(diǎn)單循環(huán)鏈裘中刪除第i個(gè)元素算法輸入：刪除第i個(gè)結(jié)點(diǎn)，待存放刪除結(jié)點(diǎn)值變量e前暨條件：單循環(huán)鏈表不空，i的值要合法動(dòng)作

20、：在帶頭結(jié)點(diǎn)的單循環(huán)鏈表中刪除第i個(gè)結(jié)點(diǎn)，并返回該結(jié)點(diǎn)的值(由e傳出)。 輸出：無后置條件:單循環(huán)鏈裘中減少了一個(gè)結(jié)點(diǎn)/ /在帶頭時(shí)點(diǎn)單循環(huán)鏈表中刪除第i個(gè)元素算法tempi ate<clas s T>T LinkListVT>: Delet e ( i nt i) ® Node<T> *p = head;» int count = 0;»if (i>length) cout«"i 不合法，越界！ "«end I ;» e I sewhile (count<i 1)

21、87; o p=p->nex t ;» co u nt+;。Node<T> *s = p->n e xt;T x二 s >data;p->next = s->next;& ° ret u rn x ;# (4) 遍歷單循環(huán)鏈表元素算法輸入：無前置條件:單循環(huán)鏈表不空動(dòng)作：遍歷輸出單循環(huán)鏈表中的各元素。輸出：無后置條件：無/遍歷單循環(huán)鏈表元素算法tem p I ate< c I as s T>vo i d L i nkL ist<T>: pr i nt () » No d e<T >

22、; *p = head-> n ext;while (p!=h e ad) o o cout«p->data« n n;p = p -> n ext;。» cou e ndl;(5) 上機(jī)實(shí)現(xiàn)以上基本操作，寫出mainO程序：voi d mainO » int a 10 = 1,2,3,4, 5,6,7t8,9,0;/測(cè)試帶參數(shù)的構(gòu)造函數(shù)(前端插入!) LinkList<int> Iist1 (a, 10);I ist1. pr i n t ();c out« R 測(cè)試插入"«end I ;I

23、i s 11 i nse r t 20);» list 1 . p r i nt ();cout< V-測(cè)試刪除操作M «endI;Iist 1 Delete(5);I i s t1. pr i nt ()；3>采用鏈?zhǔn)酱鎯?chǔ)方式，并利用單鏈表類及類中所定義的算法加以實(shí)現(xiàn)線性表La, L b為非遞 減的有序線性表，將其歸并為新線性表Lc,該線性表仍有序(未考慮相同時(shí)刪除一重復(fù)值) 的算法。模板函數(shù)：temp late<class T>voi d L i nkList<T>:addtwo (LinkL ist<T> La,L i

24、n kL i st<T> Lb) » Node< T > *p1=La. hea d ->ne x t;» Node<T> *p2:=Lb head>n e xt;i nt num=O;o whi Ie(p1 &&p2) » i f (p1->d a ta>p2->data)。o o this>i n s e rt (+num, p1 >da t a);s p1=p1->next;this->in s e rt(+n um, p2->da ta);3p2

25、= p 2->next;、汗(！p1)9 whi le(p 1) 3 this-> ins e r t (+nu叫 p1->data);p 1 =p1->next;。void main() i nt a5 =1,2, 5, 6,9;» in t b5 =0, 3,4, 7,8;Lin kL ist<int> I ist1 (a, 5);L i n k L i s t < i nt> I i st 2 (b 9 5); I ist1< p r int();o I ist2 pr i n 10 ;» L i nkL i s t<i nt> I i