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

1、2016級(jí)數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)名稱： 實(shí)驗(yàn)一線性表題目1 學(xué)生姓名： 李文超 班 級(jí)： 2015661131 班內(nèi)序號(hào)： 15 學(xué) 號(hào)： 2015522147 日 期： 2016年11月13日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、 查找5、 獲取鏈表長(zhǎng)度6、 銷毀7、 其他：可自行定義編寫

2、測(cè)試main()函數(shù)測(cè)試線性表的正確性。2. 程序分析2.1 存儲(chǔ)結(jié)構(gòu)單鏈表的存儲(chǔ)：（1）鏈表用一組任意的存儲(chǔ)單元來(lái)存放線性表的結(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)的直接后繼的地址的指針域         單鏈表

3、在內(nèi)存中的存儲(chǔ)示意地址 內(nèi)存單元a31080Ha110C0Ha4a21000H1000H頭指針 1020H1080H10C0H front 2.2 關(guān)鍵算法分析1、關(guān)鍵算法：（1）頭插法 自然語(yǔ)言描述： a:在堆中建立新結(jié)點(diǎn) b:將ai寫入到新結(jié)點(diǎn)的數(shù)據(jù)域 c:修改新結(jié)點(diǎn)的指針域 d:修改頭結(jié)點(diǎn)的指針域。將新結(jié)點(diǎn)加入鏈表中 偽代碼描述 a:Node <T> * s=new Node <T> b:s->data=ai c:s->next=front->next; d:front->next=s （2）尾插法 自然語(yǔ)言描述： a:在堆中建立新結(jié)點(diǎn)：

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

5、ty list ” Node<T>* temp=front->next; b:while(temp->next) c:cout<<temp->data<<" " d:temp=temp->next; (4) 獲取鏈表長(zhǎng)度函數(shù) 自然語(yǔ)言描述： a:判斷該鏈表是否為空鏈表，如果是，輸出長(zhǎng)度0 b:如果不是空鏈表，新建立一個(gè)temp指針，初始化整形數(shù)n為0 c:將temp指針指向頭結(jié)點(diǎn) d:判斷temp指針指向的結(jié)點(diǎn)的next域是否為空，如果不是，n加一，否則return n e: 使temp指針逐個(gè)后移，重復(fù)d操作，直

6、到temp指針指向的結(jié)點(diǎn)的next域?yàn)?，返回n 偽代碼描述 a:if ront->next=NULL b:Node<T>* temp=front->next; c:while(temp->next) d:temp=temp->next; （5）析構(gòu)/刪除函數(shù) 自然語(yǔ)言描述： a:新建立一個(gè)指針，指向頭結(jié)點(diǎn) b:判斷要釋放的結(jié)點(diǎn)是否存在， c:暫時(shí)保存要釋放的結(jié)點(diǎn) d:移動(dòng)a中建立的指針 e:釋放要釋放的指針 偽代碼描述 a:Node <T> * p=front b:while(p) c:front=p d:p=p->next e:dele

7、te front （6）按位查找函數(shù) 自然語(yǔ)言描述： a:初始化工作指針p和計(jì)數(shù)器j，p指向第一個(gè)結(jié)點(diǎn)，j=1 b:循環(huán)以下操作，直到p為空或者j等于1 ：p指向下一個(gè)結(jié)點(diǎn) ：j加1 c:若p為空，說(shuō)明第i個(gè)元素不存在，拋出異常 d:否則，說(shuō)明p指向的元素就是所查找的元素，返回元素地址 偽代碼描述 a:Node <T> * p=front->next;j=1; b:while(p&&j!=1) :p=p->next :j+ c:if(!p) throw ”error” d:return p （7）按位查找函數(shù) 自然語(yǔ)言描述： a:初始化工作指針p和計(jì)數(shù)器

8、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)還沒(méi)有找到要查找的元素，返回查找失敗信息 偽代碼描述 a:Node <T> * p=front->next;j=1; b:while(p) : if(p->next=x) return j p=p->next j+ c:return “error” （8）插入函數(shù) 自然語(yǔ)言描述： a:在堆中建立新結(jié)點(diǎn) b:將要插入的結(jié)點(diǎn)的數(shù)據(jù)寫入到新結(jié)點(diǎn)的數(shù)據(jù)域 c:修改新結(jié)點(diǎn)的指針

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

10、a d:delete q 2、代碼詳細(xì)分析（插入）：（1）從第一個(gè)結(jié)點(diǎn)開(kāi)始，查找節(jié)點(diǎn)，使它的數(shù)據(jù)比x大，設(shè)p指向該結(jié)點(diǎn)：while (x>p->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;示意圖如圖所示pxp->data s3、關(guān)鍵算法的時(shí)間復(fù)雜度：O（1)3. 程序運(yùn)行結(jié)果1. 流程圖： 開(kāi)始初始化一個(gè)對(duì)象 初始化一個(gè)整形數(shù)組，作為賦值準(zhǔn)備分別利用頭

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

12、，但做完之后大大加深了自己對(duì)書中各個(gè)知識(shí)點(diǎn)的印象和理解。也學(xué)會(huì)了一些編寫算法的小技巧，要有耐心，多看書復(fù)習(xí)知識(shí)?？傊?，這次實(shí)驗(yàn)使我印象深刻。#include <iostream>using namespace std;template <class T>struct NodeT data;struct Node * next;template <class T>class LinkListpublic:LinkList() /無(wú)參構(gòu)造front = new Node<T>front->next = NULL;LinkList(T a, in

13、t n);/頭插法/LinkList(T a,int n);/尾插法void PrintList();/按次序遍歷int GetLength();/獲取線性表的長(zhǎng)度Node <T> * 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 <T> * front;template <class T>LinkList<T>:LinkList(T a, int n)/

14、頭插法front = new Node<T>front->next = NULL;for(int i = n - 1; i >= 0; i-)Node<T> * s = new Node<T>/建立新結(jié)點(diǎn)s->data = ai;/給新結(jié)點(diǎn)數(shù)據(jù)域賦值s->next = front->next;/修改新結(jié)點(diǎn)的指針域front->next = s;/修改頭指針的指針域/* template <class T> LinkList<T>:LinkList(T a,int n )/尾插法 front=new

15、Node<T> Node <T> * r = front; for(int i=0;i<n;i+) Node<T> * s = new Node<T> s->data=ai; r->next=s; r=s; r->next=NULL; */template <class T>void LinkList<T>:PrintList()Node<T> * p = front;while(p->next != NULL)p = p->next;cout << p->

16、data << endl;template <class T>int LinkList<T>:GetLength()Node<T> * p = front;int n = 0;while(p->next != NULL) p = p->next; n+; return n;template <class T>Node <T> * LinkList<T>:Get(int i)Node<T> * p = front->next;int j = 1;while(p&&j

17、!= i)p = p->next;j+;return p;template <class T>void LinkList<T>:Insert(int i, T x)Node<T> * p = front;if(i != 1)p = Get(i - 1);if(p)Node<T> * s = new Node<T>s->data = x;s->next = p->next;p->next = s;else throw "位置錯(cuò)誤"template <class T>T Lin

18、kList<T>:Delete(int i)Node<T> * p = front;if(i != 1) p = Get(i - 1);if(!p && !p->next) throw"位置錯(cuò)誤"Node <T> * q = p->next; p ->next = q ->next;T x = q ->data;delete q;return x;template <class T>LinkList<T>:LinkList()Node<T> * p = front;while(p)p = p->next;delete front;front = p;int main()const