數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告-(00001

1、 單鏈表-數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告 2016級(jí)數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告 實(shí)驗(yàn)一線性表題目1 實(shí)驗(yàn)名稱： 李文超學(xué)生姓名： ： 級(jí) 班 2015661131 15 班內(nèi)序號(hào)： 號(hào)： 學(xué) 2015522147 年 日期： 2016 1113月日 1. 實(shí)驗(yàn)要求 實(shí)驗(yàn)?zā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)鏈表 線性表的基本功能： 1、 構(gòu)造：使用頭插法、尾插法兩種方法 2、 插入：要求建立的鏈表按照關(guān)鍵字從小到大有序 3、 刪除 4、

2、查找 5、 獲取鏈表長度 6、 銷毀 其他：可自行定義 、7 編寫測試main()函數(shù)測試線性表的正確性。 2. 程序分析 2.1 存儲(chǔ)結(jié)構(gòu) 單鏈表的存儲(chǔ)： （1）鏈表用一組任意的存儲(chǔ)單元來存放線性表的結(jié)點(diǎn)。這組存儲(chǔ)單元既可以是連續(xù)的，也可以是不連續(xù)的，甚至零散地分布在內(nèi)存的某些位置。 （2）鏈表中結(jié)點(diǎn)的邏輯次序和物理次序不一定相同。為了能正確表示結(jié)點(diǎn)間的邏輯關(guān)系，在存儲(chǔ)每個(gè)元素值的同時(shí)，還要存儲(chǔ)該元素的直接后繼元素的位置信息，這個(gè)信息稱為指針或鏈。 結(jié)點(diǎn)結(jié)構(gòu) data域-存放結(jié)點(diǎn)值的數(shù)據(jù)域 datanext next域-存 放結(jié)點(diǎn)的直接后繼的地址的指針域 單鏈表在內(nèi)存中的存儲(chǔ)示意 內(nèi)存單元地

3、址 a3108Ha110CHa4 a2 1000H 1000H 頭指針 1020H 1080H 10C0H front 關(guān)鍵算法分析2.2 1、關(guān)鍵算法： （1）頭插法 自然語言描述： a:在堆中建立新結(jié)點(diǎn) b:將ai寫入到新結(jié)點(diǎn)的數(shù)據(jù)域 c:修改新結(jié)點(diǎn)的指針域 d:修改頭結(jié)點(diǎn)的指針域。將新結(jié)點(diǎn)加入鏈表中 偽代碼描述 a:Node * s=new Node b:s-data=ai c:s-next=front-next; d:front-next=s （2）尾插法 自然語言描述： a:在堆中建立新結(jié)點(diǎn)： b:將ai寫入到新結(jié)點(diǎn)的數(shù)據(jù)域： c:將新結(jié)點(diǎn)加入到鏈表中 d:修改修改尾指針 偽代碼描述

4、 a:Node * s=new Node b:s-data=ai c:r-next=s; d:r=s （3）遍歷打印函數(shù) 自然語言描述： a:判斷該鏈表是否為空鏈表，如果是，報(bào)錯(cuò) b:如果不是空鏈表，新建立一個(gè)temp指針 指針指向頭結(jié)點(diǎn)temp將 c: d:打印temp指針的data域 e:逐個(gè)往后移動(dòng)temp指針，直到temp指針的指向的指針的next域?yàn)榭?偽代碼描述 a: If front-next=NULL ?Throw ”an empty list ” ?Node* temp=front-next; b:while(temp-next) c:coutdatanext; (4) 獲取

5、鏈表長度函數(shù) 自然語言描述： a:判斷該鏈表是否為空鏈表，如果是，輸出長度0 b:如果不是空鏈表，新建立一個(gè)temp指0 為n針，初始化整形數(shù) c:將temp指針指向頭結(jié)點(diǎn) d:判斷temp指針指向的結(jié)點(diǎn)的next域是否為空，如果不是，n加一，否則return n e: 使temp指針逐個(gè)后移，重復(fù)d操作，直到temp指針指向的結(jié)點(diǎn)的next域?yàn)?，返回n 偽代碼描述 a:if ront-next=NULL b:Node* temp=front-next; c:while(temp-next) d:temp=temp-next; （5）析構(gòu)/刪除函數(shù) 自然語言描述： a:新建立一個(gè)指針，指向頭

6、結(jié)點(diǎn) b:判斷要釋放的結(jié)點(diǎn)是否存在， 暫時(shí)保存要釋放的結(jié)點(diǎn) c: d:移動(dòng)a中建立的指針 e:釋放要釋放的指針 偽代碼描述 a:Node * p=front b:while(p) c:front=p d:p=p-next e:delete front （6）按位查找函數(shù) 自然語言描述： a:初始化工作指針p和計(jì)數(shù)器j，p指向第一個(gè)結(jié)點(diǎn)，j=1 b:循環(huán)以下操作，直到p為空或者j等于1 ?：p指向下一個(gè)結(jié)點(diǎn) 1 加j：? c:若p為空，說明第i個(gè)元素不存在，拋出異常 d:否則，說明p指向的元素就是所查找 的元素，返回元素地址 偽代碼描述 a:Node * p=front-next;j=1; b:

7、while(p&j!=1) ?:p=p-next ?:j+ c:if(!p) throw ”error” d:return p （7）按位查找函數(shù) 自然語言描述： a:初始化工作指針p和計(jì)數(shù)器j，p指向第一個(gè)結(jié)點(diǎn)，j=1 b:循環(huán)以下操作，找到這個(gè)元素或者p 指向最后一個(gè)結(jié)點(diǎn) ?：判斷p指向的結(jié)點(diǎn)是不是要查找的值，如果是，返回j，否則p指向下 一個(gè)結(jié)點(diǎn)，并且j的值加一 c:如果找到最后一個(gè)結(jié)點(diǎn)還沒有找到要查找的元素，返回查找失敗信息 偽代碼描述 a:Node * p=front-next;j=1; b:while(p) ?: if(p-next=x) return j p=p-next j+

8、c:return “error” （8）插入函數(shù) 自然語言描述： a:在堆中建立新結(jié)點(diǎn) b:將要插入的結(jié)點(diǎn)的數(shù)據(jù)寫入到新結(jié)點(diǎn) 的數(shù)據(jù)域 c:修改新結(jié)點(diǎn)的指針域 d:修改前一個(gè)指針的指針域，使其指向新插入的結(jié)點(diǎn)的位置 偽代碼描述 a:Node * s=new Node ; b:s-data=p-data c:s-next=p-next d:p-next=s e:p-data=x （9）刪除函數(shù) 自然語言描述： a:從第一個(gè)結(jié)點(diǎn)開始，查找要?jiǎng)h除的位數(shù)i前一個(gè)位置i-1的結(jié)點(diǎn) b:設(shè)q指向第i個(gè)元素 c:將q元素從鏈表中刪除 元素的數(shù)據(jù)q保存 d: e:釋放q元素 偽代碼描述 a:q=p-next

9、b:p-next=q-next c:x=q-data d:delete q 2、代碼詳細(xì)分析（插入）： （1）從第一個(gè)結(jié)點(diǎn)開始，查找節(jié)點(diǎn)，使它的數(shù)據(jù)比x大，設(shè)p指向該結(jié)點(diǎn)： while (xp-data) p=p-next; （2）新建一個(gè)節(jié)點(diǎn)s，把p的數(shù)據(jù)賦給s： s-data=p-data; （3）把s加到p后面：s-next=p-next; p-next=s; （4）p節(jié)點(diǎn)的數(shù)據(jù)用x替換：p-data=x; 示意圖如圖所示p x p-data s 3、關(guān)鍵算法的時(shí)間復(fù)雜度：1) （O 3. 程序運(yùn)行結(jié)果 1. 流程圖： 開始 初始化一個(gè) 初始化一個(gè)整形數(shù)組作 分別利用頭插法和尾插法初始化

10、， 執(zhí)行插入函數(shù)，之后遍歷打印 執(zhí)行刪除函數(shù)之后遍歷打印 執(zhí)行按位查找和按 結(jié)束 、結(jié)果截圖2 3.測試結(jié)論：可以正確的對(duì)鏈表進(jìn)行插入，刪除，取長度，輸出操作。且插入任意一個(gè)元素后，鏈 表的順序依然是由小到大。 4、給出代碼（文末） 4. 總結(jié) 1、問題 ?書中已經(jīng)給出析構(gòu)、查找、插入、刪除過程代碼，遍歷以及獲取長度代碼需要自己寫出，剛開始寫時(shí)一直出現(xiàn)各種基本錯(cuò)誤，后來經(jīng)過不斷調(diào)試解決了問題。 ?編寫main函數(shù)時(shí)，調(diào)用插入刪除等操作的代碼一直編寫失敗，后自行查找資料后解決 2、收獲 這次編程任務(wù)完成地較為艱辛，但做完之后大大加深了自己對(duì)書中各個(gè)知識(shí)點(diǎn)的印象和理要有耐心，也學(xué)會(huì)了一些編寫算法的

11、小技巧，解。 多看書復(fù)習(xí)知識(shí)。總之，這次實(shí)驗(yàn)使我印象深刻。 #include using namespace std; template struct Node T data; struct Node * next; ; template class LinkList public: LinkList() /無參構(gòu)造 front = new Node; front-next = NULL; LinkList(T a, int n);/頭插法 /LinkList(T a,int n);/尾插法 按次序遍歷/ PrintList();void int GetLength();/獲取線性表的長度 N

12、ode * Get(int i);/獲取第i個(gè)位置上的元素結(jié)點(diǎn)的地址 int Locate(T x);/查找 void Insert(int i, T x);/插入 T Delete(int i);/刪除 LinkList();/銷毀 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;/建立新結(jié)點(diǎn) s-data = ai;/給新結(jié)點(diǎn)數(shù)據(jù)域

13、賦值 s-next = front-next;/修改新結(jié)點(diǎn)的指針域 front-next = s;/修改頭指針的指針域 /* template 尾插法 LinkList:LinkList(T a,int n )/ front=new Node; Node * r = front; for(int i=0;in;i+) Node * s = new Node; s-data=ai; r-next=s; r=s; r-next=NULL; */ template void LinkList:PrintList() Node * p = front; while(p-next != NULL) p

14、= p-next; cout data class template int LinkList:GetLength() Node * p = front; int n = 0; while(p-next != NULL) p = p-next; n+; return n; template Node * LinkList:Get(int i) Node * p = front-next; int j = 1; while(p&j != i) p = p-next; j+; return p; template void LinkList:Insert(int i, T x) Node * p

15、= front; if(i != 1) p = Get(i - 1); if(p) Node * s = new Node; s-data = x; s-next = p-next; p-next = s; else throw 位置錯(cuò)誤; template T LinkList:Delete(int i) Node * p = front; if(i != 1) p = Get(i - 1); if(!p & !p-next) throw位置錯(cuò)誤; Node * q = p-next; p -next = q -next; T x = q -data; delete q; return x; template LinkList:LinkList() Node * p = front; while(p) p = p-next; delete front; front = p; int main() const int n = 8; int an = 1, 2, 3, 4, 5, 6, 7, 8 ; LinkList list(a, n); cout線性表的長度為： list.GetLength() endl; cout endl; cout遍歷線性表結(jié)果為：endl; list.Prin