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

1、 單鏈表-數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報告 2016級數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報告 實(shí)驗(yàn)一線性表題目1 實(shí)驗(yàn)名稱： 李文超學(xué)生姓名： ： 級 班 2015661131 15 班內(nèi)序號： 號： 學(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)線性表， 基本功能。 線性表存儲結(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 存儲結(jié)構(gòu) 單鏈表的存儲： （1）鏈表用一組任意的存儲單元來存放線性表的結(jié)點(diǎn)。這組存儲單元既可以是連續(xù)的，也可以是不連續(xù)的，甚至零散地分布在內(nèi)存的某些位置。 （2）鏈表中結(jié)點(diǎn)的邏輯次序和物理次序不一定相同。為了能正確表示結(jié)點(diǎn)間的邏輯關(guān)系，在存儲每個元素值的同時，還要存儲該元素的直接后繼元素的位置信息，這個信息稱為指針或鏈。 結(jié)點(diǎn)結(jié)構(gòu) data域-存放結(jié)點(diǎn)值的數(shù)據(jù)域 datanext next域-存 放結(jié)點(diǎn)的直接后繼的地址的指針域 單鏈表在內(nèi)存中的存儲示意 內(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:如果不是空鏈表，新建立一個temp指針 指針指向頭結(jié)點(diǎn)temp將 c: d:打印temp指針的data域 e:逐個往后移動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:如果不是空鏈表，新建立一個temp指0 為n針，初始化整形數(shù) c:將temp指針指向頭結(jié)點(diǎn) d:判斷temp指針指向的結(jié)點(diǎn)的next域是否為空，如果不是，n加一，否則return n e: 使temp指針逐個后移，重復(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:新建立一個指針，指向頭

6、結(jié)點(diǎn) b:判斷要釋放的結(jié)點(diǎn)是否存在， 暫時保存要釋放的結(jié)點(diǎn) c: d:移動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指向第一個結(jié)點(diǎn)，j=1 b:循環(huán)以下操作，直到p為空或者j等于1 ?：p指向下一個結(jié)點(diǎn) 1 加j：? c:若p為空，說明第i個元素不存在，拋出異常 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指向第一個結(jié)點(diǎn)，j=1 b:循環(huán)以下操作，找到這個元素或者p 指向最后一個結(jié)點(diǎn) ?：判斷p指向的結(jié)點(diǎn)是不是要查找的值，如果是，返回j，否則p指向下 一個結(jié)點(diǎn)，并且j的值加一 c:如果找到最后一個結(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:修改前一個指針的指針域，使其指向新插入的結(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:從第一個結(jié)點(diǎn)開始，查找要刪除的位數(shù)i前一個位置i-1的結(jié)點(diǎn) b:設(shè)q指向第i個元素 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）從第一個結(jié)點(diǎn)開始，查找節(jié)點(diǎn)，使它的數(shù)據(jù)比x大，設(shè)p指向該結(jié)點(diǎn)： while (xp-data) p=p-next; （2）新建一個節(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)鍵算法的時間復(fù)雜度：1) （O 3. 程序運(yùn)行結(jié)果 1. 流程圖： 開始 初始化一個 初始化一個整形數(shù)組作 分別利用頭插法和尾插法初始化

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

11、小技巧，解。 多看書復(fù)習(xí)知識。總之，這次實(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個位置上的元素結(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 位置錯誤; template T LinkList:Delete(int i) Node * p = front; if(i != 1) p = Get(i - 1); if(!p & !p-next) throw位置錯誤; 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