線性表和鏈式表實驗報告

1、 數(shù)據(jù)結構與算法實驗院 別：計算機科學與信息工程學院年級專業(yè)：2014級空間信息與數(shù)字技術姓 名：楊哲慶學 號：1420012138評語和成績: 2015 年 9月 實驗1 線性表實驗1.1 順序表1.1.1 實驗的主要內容和目的 了解順序存儲的基本思想； 掌握基于順序表基本操作的實現(xiàn)； 掌握計算基于順序表基本操作的時間性能； 認識順序表和鏈表之間的區(qū)別。1.1.2 代碼SeqList.h (SeqList類的聲明)#if !defined(AFX_SEQLIST_H_A502EFF8_79FB_4E5E_96F3_B8C7E03EB41B_INCLUDED_)#define AFX_SEQL

2、IST_H_A502EFF8_79FB_4E5E_96F3_B8C7E03EB41B_INCLUDED_#if _MSC_VER > 1000#pragma once#endif / _MSC_VER > 1000/*=*/#include<iostream>using namespace std;const int MaxSize=100;template<class T>class SeqListpublic:SeqList() length=0;SeqList(T a,int n);/1int getlength() return length;T G

3、et(int i); /2int Locate(T x); /3void Insert(int i,T x);/4T Delete(int i); /5void PrintList(); /6private:T dataMaxSize;int length;/*=*/#endif SeqList.cpp (SeqList類的實現(xiàn))#include<iostream>#include "SeqList.h"using namespace std;template<class T>SeqList<T>:SeqList(T a,int n)if

4、(n>MaxSize) throw "參數(shù)非法，發(fā)生溢出！"for(int i=0;i<n;i+)datai = ai;length = n;template<class T>T SeqList<T>:Get(int i)if(i>length | i<1) throw "查找位置非法"else return datai-1;template<class T>int SeqList<T>:Locate(T x)for(int i=0;i<length;i+)if(datai=x

5、) return i+1;return 0;template<class T>void SeqList<T>:Insert(int i,T x)if(length>=MaxSize) throw "數(shù)據(jù)上溢"if( i>length+1 | i<1 ) throw "參數(shù)非法，不在鏈表的長度范圍內"for(int j=length;j>=i;j-)dataj=dataj-1;datai-1=x;length+;template<class T>T SeqList<T>:Delete(

6、int i)if(length=0) throw "數(shù)據(jù)下溢"if(i>length | i<1) throw"參數(shù)非法，不再鏈表的長度范圍內"int x=datai-1;for(int j=i;j<length;j+)dataj-1=dataj;length-;return x;template<class T>void SeqList<T>:PrintList()for(int i=0;i<length;i+)cout<<datai<<" "cout<&

7、lt;endl;test.cpp(主函數(shù)測試文件)#include<iostream>using namespace std;#include"SeqList.cpp"int main(void)int r5=1,2,3,4,5;SeqList<int> L(r,5);cout<<"執(zhí)行插入操作前的數(shù)據(jù)為："<<endl;L.PrintList();tryL.Insert(2,3);catch(char* s)cout<<s<<endl;cout<<"執(zhí)行插入后

8、的數(shù)據(jù)為："<<endl;L.PrintList();cout<<"值為3的元素位置為："cout<<L.Locate(3)<<endl;cout<<"當前順序表長度為："cout<<L.getlength()<<endl;cout<<"執(zhí)行刪除第一個元素操作，刪除前數(shù)據(jù)為："<<endl;L.PrintList();tryL.Delete(1);catch(char* s)cout<<s<<e

9、ndl;cout<<"刪除后的數(shù)據(jù)為："<<endl;L.PrintList();return 0;1.1.3 總結(1) 實驗過程中碰到了2個比較有意義的錯誤，分別是錯誤a和錯誤b：a.調用了SeqList類的聲明文件SeqList.h卻沒有調用SeqList類的實現(xiàn)文件SeqList.cpp。如圖1-1；圖 a1 改正：將SeqList.cpp中加入代碼：#include "SeqList.h",如圖1-2； 然后再在test.cpp中將#include "SeqList.h"改為#include &quo

10、t;SeqList.cpp",如圖1-3。圖 a2圖a3b.SeqList的成員函數(shù)用if進行判斷，用“throw”進行拋出一串字符串。而“catch”得到的應該是字符串的首地址，應該是個指針，而不應該如圖b-1所示。圖b-1改正：將錯誤代碼:catch(char s) 改為:catch(char* s)即可，如圖b-2所示。圖b-2(2) 實驗過程使用的主要知識點（ abc編號）a. 順序表按值查找算法Locate.b. 順序表插入算法Insert.c. 順序表刪除算法Delete.(3) 實驗中遇到的不理解或體會比較深的問題（ abc編號）a. 順序表的插入以及刪除操作距離表頭或

11、表尾越近，則程序運行耗時越短。b. 順序表本質還是一個一維數(shù)組。c. 如果需要進行頻繁的查找操作，順序表是一個合適的選擇。1.2 鏈式表1.2.1 實驗的主要內容和目的 了解順鏈接存儲的基本思想； 掌握基于單鏈表基本操作的實現(xiàn)； 掌握計算基于單鏈表基本操作的時間性能； 熟悉單鏈表的基本運算在兩種存儲結構上的實現(xiàn)；1.2.2 代碼LinkList.h (LinkList類的聲明)#if !defined(AFX_LINKLIST_H_B3F42344_7C3F_4313_8B60_09F1F2998D68_INCLUDED_)#define AFX_LINKLIST_H_B3F42344_7C3

12、F_4313_8B60_09F1F2998D68_INCLUDED_#if _MSC_VER > 1000#pragma once#endif / _MSC_VER > 1000template<class T>struct NodeT data;Node<T>* next;template<class T>class LinkListpublic:LinkList();LinkList(T a,int n);virtual LinkList();int getLength();int Locate(T x);void Insert(int i,

13、T x);T Delete(int i);void PrintList();private:Node<T>* first;#endifLinkList.cpp(LinkList類的聲明)#include<iostream>#include "LinkList.h"using namespace std;template<class T>LinkList<T>:LinkList()first=new Node<T>first->next=NULL;template<class T>LinkList&

14、lt;T>:LinkList(T a,int n)Node<T>*r,*s;first=new Node<T>r=first;for(int i=0;i<n;i+)s=new Node<T>s->data=ai;r->next=s;r=s;r->next=NULL;template<class T>LinkList<T>:LinkList()Node<T>*q=NULL;while(first!=NULL)q=first;first=first->next;delete q;templa

15、te<class T>int LinkList<T>:getLength()int count=0;Node<T>*p=first->next;while(p)count+;p=p->next;return count;template<class T>void LinkList<T>:Insert(int i,T x)Node<T>*p=first,*s=NULL;int count=0;while(p!=NULL && count<i-1)p=p->next;count+;if(

16、p=NULL) throw"位置非法"elses=new Node<T>s->data=x;s->next=p->next;p->next=s;template<class T>T LinkList<T>:Delete(int i)Node<T>*p=first,*q=NULL;T x;int count=0;while(p!=NULL && count<i-1)p=p->next;count+;if(p=NULL | p->next=NULL)throw"位

17、置"elseq=p->next;x=q->data;p->next=q->next;delete q;return x;template<class T>int LinkList<T>:Locate(T x)Node<T>*p=first->next;int count=1;while(p!=NULL)if(p->data=x)return count;p=p->next;count+;return 0;template<class T>void LinkList<T>:PrintL

18、ist()Node<T>*p=first->next;while(p!=NULL)cout<<p->data<<" "p=p->next;cout<<endl;test.cpp(主函數(shù)測試文件)#include"LinkList.cpp"using namespace std;int main(void)int r5=1,2,3,4,5;LinkList<int> L(r,5);cout<<"執(zhí)行插入操作前的數(shù)據(jù)為："<<endl;L

19、.PrintList();tryL.Insert(2,3);catch(char* s)cout<<s<<endl;cout<<"執(zhí)行插入后的數(shù)據(jù)為："<<endl;L.PrintList();cout<<"值為5的元素位置為："cout<<L.Locate(5)<<endl;cout<<"當前單鏈表的長度為："cout<<L.getLength()<<endl;cout<<"執(zhí)行刪除第一個元素操作，刪除前數(shù)據(jù)為：