style=“margin-bottom: 0px” Text=“用??戶?ì名?”>

style=“margin-left: 9px”>

style=“margin-left: 39px”>

三、實驗步驟

第五篇：北郵數據結構實驗報告 單鏈表

北京郵電大學 數據結構試驗報告

實驗名稱： 實驗一

線性表 學生姓名：

班

級：

班內序號：

學

號：

日

期： 2014年1月3日

實驗目的

? 熟悉C++語言的基本編程方法，掌握集成編譯環境的調試方法 ? 學習指針、模板類、異常處理的使用 ? 掌握線性表的操作的實現方法 ? 學習使用線性表解決實際問題的能力 實驗內容

2.1題目1 根據線性表的抽象數據類型的定義，選擇下面任一種鏈式結構實現線性表，并完成線性表的基本功能。

線性表存儲結構（五選一）：

1、帶頭結點的單鏈表

2、不帶頭結點的單鏈表

3、循環鏈表

4、雙鏈表

5、靜態鏈表

線性表的基本功能：

1、構造：使用頭插法、尾插法兩種方法

2、插入：要求建立的鏈表按照關鍵字從小到大有序

3、刪除

4、查找

5、獲取鏈表長度

6、銷毀

7、其他：可自行定義

編寫測試main()函數測試線性表的正確性。程序分析

3.1 存儲結構 單鏈表的存儲結構：

3.2 關鍵算法分析

一、關鍵算法 1.頭插法

自然語言描述：a.在堆中建立新結點

b.將a[i]寫入到新結點的數據域

c.修改新結點的指針域

d.修改頭結點的指針域,將新結點加入鏈表中 代碼描述： 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 = a[i];

}

} s->next = front->next;front->next = s;時間復雜度：O(n)

2.尾插法

自然語言描述：a.在堆中建立新結點

b.將a[i]寫入到新結點的數據域

c.將新結點加入到鏈表中

d.修改修改尾指針 代碼描述: template LinkList::LinkList(T a[], int n)//尾插法建立 {

front = new Node;front->next=NULL;Node * r = front;for(int i=0;i * s = new Node;

}

} s->data = a[i];s->next = r->next;r->next= s;r=s;時間復雜度：O(n)

3.析構函數

自然語言描述：a.新建立一個指針，指向頭結點

b.移動a中建立的指針

c.逐個釋放指針

代碼描述: template LinkList::~LinkList()//析構函數，銷毀鏈表 {

Node * p = front;while(p){ front = p;p = p->next;

} } delete front;4.按位查找函數

自然語言描述: a.初始化工作指針p和計數器j，p指向第一個結點，j=1

b.循環以下操作，直到p為空或者j等于1

b1：p指向下一個結點

b2：j加1

c.若p為空，說明第i個元素不存在，拋出異常

d.否則，說明p指向的元素就是所查找的元素，返回元素地址

代碼描述: template Node* LinkList::Get(int i)//按位查找 {

Node * p = front;int j=0;while(p){

if(j

} else break;p = p->next;j++;

} if(!p)throw“查找位置非法”;else

return p;} 時間復雜度：O(n)

5.按值查找函數

自然語言描述：a.初始化工作指針p和計數器j，p指向第一個結點，j=1

b.循環以下操作，找到這個元素或者p指向最后一個結點

b1.判斷p指向的結點是不是要查找的值，如果是，返回j;

b2.否則p指向下一個結點,并且j的值加一

c.如果找到最后一個結點還沒有找到要查找的元素，返回查找失敗信息

代碼描述: template int LinkList::Locate(T x)//按值查找 {

Node * p = front->next;int j = 1;while(p){

} return-1;if(p->data == x)return j;else { p = p->next;

j++;} } 時間復雜度：O(n)6.插入函數

自然語言描述： a.在堆中建立新結點

b.將要插入的結點的數據寫入到新結點的數據域

c.修改新結點的指針域

d.修改前一個指針的指針域，使其指向新插入的結點的位置

代碼描述: template void LinkList::Insert(int i,T x)//插入函數 {

Node * p = Get(i-1);if(p){

} else throw“插入位置非法”;Node * s = new Node;s->data = x;s->next = p->next;p->next = s;} 時間復雜度：O(n)7.按位刪除函數

自然語言描述：a.從第一個結點開始，查找要刪除的位數i前一個位置i-1的結點

b.設q指向第i個元素

c.將q元素從鏈表中刪除

d.保存q元素的數據

e.釋放q元素 代碼描述: template T LinkList::Delete(int i)//刪除函數 { Node *p = Get(i-1);Node *q = p->next;

T x=q->data;

} p->next = q->next;delete q;return x;

8.遍歷打印函數

自然語言描述: a.判斷該鏈表是否為空鏈表，如果是，報錯

b.如果不是空鏈表，新建立一個temp指針

c.將temp指針指向頭結點

d.打印temp指針的data域

e.逐個往后移動temp指針，直到temp指針的指向的指針的next域為空

代碼描述: template void LinkList::PrintList()//打印鏈表 {

} Node * p = front->next;while(p){

} cout<data<<' ';p = p->next;9.獲取鏈表長度函數

自然語言描述： a.判斷該鏈表是否為空鏈表，如果是，輸出長度0

b.如果不是空鏈表，新建立一個temp指針，初始化整形數n為0

c.將temp指針指向頭結點

d.判斷temp指針指向的結點的next域是否為空，如果不是，n加一，否則return n

e.使temp指針逐個后移，重復d操作，直到temp指針指向的結點的next域為0，返回n 代碼描述: template int LinkList::GetLength()//分析鏈表長度 {

} Node * p = front;int i=0;while(p){

} return i-1;p = p->next;i++;4 程序運行結果

4.1主函數流程圖

4.2程序運行框圖

實驗心得

1.調試時出現的問題及解決的方法

在編寫按值查找函數時，由于沒有處理好指針類型的原因，導致指針無法正常返回，屢屢報錯。最后意識到c++沒有指針強制類型的轉換機制，經過細致檢查后才改正錯誤使得程序正常運行。2.心得體會

了解了單鏈表的基本的操作函數實現，對鏈式存儲結構有了較好的認識 3.下一步的改進

可以增加完善報錯機制，增強程序的健壯性

完整源代碼

#include using namespace std;

template struct Node {

};

template class LinkList { public:

};

//template //LinkList::LinkList(T a[], int n)//頭插法建立 LinkList(){ front = new Node;front->next = NULL;}//無參構造函數 LinkList(T a[],int n);//構造函數 void Insert(int i,T x);//插入函數 T Delete(int i);//刪除函數

Node* Get(int i);//查找第幾個的元素，返回的是該元素的地址 int Locate(T x);//定位某元素 int GetLength();//分析鏈表長度 ~LinkList();//析構函數 void PrintList();//打印鏈表 Node * front;T data;Node * next;private: //{ // // // // // // // // // //}

template LinkList::LinkList(T a[], int n)//尾插法建立 {

}

template LinkList::~LinkList()//析構函數，銷毀鏈表 {

}

template void LinkList::PrintList()//打印鏈表 { Node * p = front;while(p){

} front = p;p = p->next;delete front;front = new Node;front->next=NULL;Node * r = front;for(int i=0;i

} Node * s = new Node;s->data = a[i];s->next = r->next;r->next= s;r=s;front = new Node;front->next = NULL;for(int i=n-1;i>=0;i--){

} Node* s = new Node;s->data = a[i];s->next = front->next;front->next = s;

} Node * p = front->next;while(p){

} cout<data<<' ';p = p->next;

template Node* LinkList::Get(int i)//按位查找 {

}

template int LinkList::Locate(T x)//按值查找 {

} Node * p = front->next;int j = 1;while(p){

} return-1;if(p->data == x)return j;else

{ } p = p->next;

j++;Node * p = front;int j=0;while(p){

} if(!p)throw“查找位置非法”;else

return p;if(j

} else break;p = p->next;j++;

template void LinkList::Insert(int i,T x)//插入函數 {

}

template T LinkList::Delete(int i)//刪除函數 {

}

template int LinkList::GetLength()//分析鏈表長度 {

}

void main(){ Node * p = front;int i=0;while(p){

} return i-1;p = p->next;i++;Node *p = Get(i-1);Node *q = p->next;p->next = q->next;delete q;return x;Node * p = Get(i-1);if(p){

} else throw“插入位置非法”;Node * s = new Node;s->data = x;s->next = p->next;p->next = s;

T x=q->data;

} int n;cout<<“將要輸入的鏈表長度為：”;cin>>n;int *b=new int[n];cout<<“輸入鏈表中的元素：”;for(int k=0;k>b[k];LinkList a(b,n);a.PrintList();cout<<“鏈表的長度:”<>i;cout<<“被刪除掉的元素是：”<>j;cout<<“要將其插入在哪個位置：”;cin>>i;a.Insert(i,j);cout<<“插入后得到的鏈表是：”;a.PrintList();cout<<“要查找第幾個元素：”;cin>>i;cout<<“要查找的元素為：”<data<>j;cout<<“輸入的元素位置在：”<