實(shí)驗(yàn)一鏈?zhǔn)浇Y(jié)構(gòu)實(shí)現(xiàn)線性表

1、數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)名稱：實(shí)驗(yàn)一一一鏈?zhǔn)浇Y(jié)構(gòu)實(shí)現(xiàn)線性表學(xué)生姓名：班 級(jí)：班內(nèi)序號(hào)：學(xué) 號(hào)：日 期：1.實(shí)驗(yàn)要求實(shí)驗(yàn)?zāi)康模和ㄟ^選擇下面四個(gè)題目之一進(jìn)行實(shí)現(xiàn)，掌握如下內(nèi)容：?熟悉C+語言的基本編程方法，掌握集成編譯環(huán)境的調(diào)試方法?學(xué)習(xí)指針、模板類、異常處理的使用?掌握線性表的操作的實(shí)現(xiàn)方法?學(xué)習(xí)使用線性表解決實(shí)際問題的能力實(shí)驗(yàn)內(nèi)容：根據(jù)線性表的抽象數(shù)據(jù)類型的定義，選擇下面任一種鏈?zhǔn)浇Y(jié)構(gòu)實(shí)現(xiàn)線性表,基本功能。線性表存儲(chǔ)結(jié)構(gòu)（五選一）：1、帶頭結(jié)點(diǎn)的單鏈表2、不帶頭結(jié)點(diǎn)的單鏈表3、循環(huán)鏈表4、雙鏈表5、靜態(tài)鏈表并完成線性表線性表的基本功能:構(gòu)造：使用頭插法、尾插法兩種方法1 1、插入：要求建立的鏈表按

2、照關(guān)鍵字從小到大有序2 2、刪除3 3、查找4 4、獲取鏈表長度5 5、銷毀6 6、其他：可自行定義編寫測(cè)試 main()main()函數(shù)測(cè)試線性表的正確性。2.程序分析2.12.1 存儲(chǔ)結(jié)構(gòu)2.22.2 關(guān)鍵算法分析算法步驟：1堆中建立新結(jié)點(diǎn)2S-next指向front-next3front-next指向s頭插法示意圖:Frontdatanejct存儲(chǔ)結(jié)構(gòu)：順序表frontNode *s=new Node;s_data=ai; s-n ext=fr ont-n ext; front-n ext=s;時(shí)間復(fù)雜度：0(n)尾插法算法步驟：1堆中建立新結(jié)點(diǎn)Node *s=new Node;2將新結(jié)

3、點(diǎn)加入到鏈表中r-next=front-next3修改尾指針r=s按值查找結(jié)點(diǎn)示意圖:next二二二一ddUElint i=1;Node* p;p=front-next;匕較P指向的元素是否與檢索值相同if(P)while(p)if(p-data=n)cout元素序號(hào)：in ext;i+；elsethrow空鏈表！;時(shí)間復(fù)雜度：0(n)插入操作:算法步驟:1堆中建立新結(jié)點(diǎn)Node *s=new Node;2將新結(jié)點(diǎn)插入到要插入位置后一節(jié)點(diǎn)p的后面，將后一結(jié)點(diǎn)數(shù)據(jù)寫入s3P指向s,在p中寫入新的值s-data=p-data;s-n ext=p-n ext;p_n ext=s;p-data=x;時(shí)

4、間復(fù)雜度：O(1)算法步驟:1從第一個(gè)結(jié)點(diǎn)開始，查找第i-1個(gè)元素，設(shè)為p指向該結(jié)點(diǎn);2設(shè)q指向第i個(gè)元素：q = p-next;3摘鏈，即將q元素從鏈表中摘除：p-next = q-next;4保存q元素的數(shù)據(jù)：x = q-data;5釋放q元素：delete q;刪除結(jié)點(diǎn)示意圖:pq刪除結(jié)點(diǎn)示意圖說明：如果算法比較復(fù)雜， 可以將多句代碼合成一個(gè)步驟進(jìn)行說明。以這樣寫：1從第一個(gè)結(jié)點(diǎn)開始，查找第i-1個(gè)元素，設(shè)為2設(shè)q指向第i個(gè)元素：q = p-next;3摘鏈，即將q元素從鏈表中摘除：p_n ext = q_n ext;x = q-datadelete q;時(shí)間復(fù)雜度：0(n)2.32.3

5、 其他程序代碼：#inelude using namespace std;template struct NodeT data;struct Node * next;template class LinkListpublic比如也可p指向該結(jié)點(diǎn);LinkList()front=new Node ;front-next=NULL;LinkList( T a, int n);Li nkList();Node * Get( int i);Node * Locate( int n, Node * s);void Insert( int i,T x);T Delete( int i);int GetLe

6、ngth();void Print();private :Node * front;template LinkList :LinkList( T a, int n)/ 頭插法front= new Node ;front-next=NULL ;for (int i= n-1;i=0;i_)Node *s= new Node ;s-data= ai;s-n ext=fr ont-n ext; front-n ext=s;/*templateLinkList:LinkList(T a,int n)front=new Node;Node *r=fro nt;for(i nti=O;i n ;i+)No

7、de* s=new Node; s-data=ai;r-n ext=s;r=s;r-n ext=NULL;*/ template LinkList :LinkList() Node * p=front;while (p)fron t=p;/尾插法/析構(gòu)函數(shù)p=p-n ext;delete front;template Node * LinkList :Get( int i) Node * p=front-next;int j=1;while (p&j!= i)p=p-n ext;j+;return p;template Node * LinkList :Locate( int i=1;

8、Node * p;p=front-n ext;if(P)while (p)if(p-data= n)COUtvv 元素序號(hào):p=p-n ext;i+;elsethrow 空鏈表！;/*while(p&p-data!=n)int n,Node * s)in ext;return p;t=0;if(p-n ext)Locate( n,p-n ext);elsereturn NULL;*/ template void LinkList :Insert( int i,T x)Node * p=Get( i);if(p)Node * s= new Node ;s-data=p-data;s-n

9、ext=p-n ext;p_n ext=s;p-data= x;elsethrow 輸入有誤;template /T LinkList :Delete( int i)Node * p=front;if(i!=1)p=Get( i-1);Node * q=p-next;p_n ext=q _n ext;T x=q_data;delete q;return x; template int LinkList :GetLength()int i=0;Node * p=front-next;if(P)i+；p=p-n ext;return i; template void LinkList :Print

10、()Node * p=front-next;if(fro nt- n ext)while (p)coutdatan ext; coute ndl;elsethrow 該表沒有元素;void main()int x,y;int a6=1,2,3,4,5,6;LinkList L(a,6);L.Pri nt();coutvv 請(qǐng)輸入要插入的位置和數(shù)值:cin xy;L.ln sert(x,y);L.Pri nt();cout 請(qǐng)輸入要?jiǎng)h除的元素序號(hào)：cinx;L.Delete(x);L.Pri nt();cout 請(qǐng)輸入需要查找的元素序號(hào):cinx;coutdatae ndl;cout 請(qǐng)輸入需要查找的元素：cinx;L.Locate(x, NULL);coutL.GetLe ngth();n3.程序運(yùn)行結(jié)果測(cè)試主函數(shù)流程：流程圖如圖所示打印序列可輸入插入的位置和數(shù)值打印修改后序列4輸入刪除的位置1r打印修改后序列輸入查找的關(guān)鍵值4打印查找關(guān)鍵值的位置1、測(cè)試條件:初始序列為1 2 3 4 5 6插入位置1數(shù)值6是刪除元素序號(hào)3查找元素序號(hào)2查找元素62、測(cè)試結(jié)論初始序列為1 2 3 4 5 6插入位置1數(shù)值6后序列：6 1 2 3 4 5 6是刪除元素序號(hào)3后序列：6 1 3 4 5 6查找元素序號(hào)2后查找到序號(hào)2所對(duì)應(yīng)元素為