1、重慶交通大學算法與數據結構課程實驗報告班 級：計算機科學與技術2014級2班實驗項目名稱： 線性表的順序儲存結構 實驗項目性質： 實驗所屬課程： 算法與數據結構 實驗室(中心)： B01407 指 導 教 師 ： 魯云平 實驗完成時間： 2016 年 3 月 21 日教師評閱意見： 簽名： 年 月 日實驗成績：1、 實驗目的1、實現線性表的順序存儲結構2、熟悉C+程序的基本結構，掌握程序中的頭文件、實現文件和主文件之間的相互關系及各自的作用3、熟悉順序表的基本操作方式,掌握順序表相關操作的具體實現 二、實驗內容及要求對順序存儲的線性表進行一些基本操作。主要包括：（1）插入：操作方式為在指定元素

2、前插入、在指定元素之后插入、在指定位置完成插入（2）刪除：操作方式可分為刪除指定元素、刪除指定位置的元素等，嘗試實現邏輯刪除操作。（3）顯示數據（4）查找：查詢指定的元素（可根據某個數據成員完成查詢操作）（5）定位操作：定位指定元素的序號（6）更新：修改指定元素的數據（7）數據文件的讀寫操作等。其它操作可根據具體需要自行補充。要求線性表采用類的定義,數據對象的類型自行定義。三、實驗設備及軟件VC6.0四、設計方案 題目線性表的順序存儲結構 設計的主要思路1、 新建SeqList.h頭文件，定義SeqList模板類2、 設計類數據成員，包括：T *data（用于存放數組）、int maxSize

3、（最大可容表項的項數）、int last（當前已存表項的最后位置） 3、 設計類成員函數，主要包括：int search(T& x)const;/搜索x在表中位置，函數返回表項序號int Locate(int i)const;/定位第i個表項，函數返回表項序號bool getData(int i,T& x)const;/去第i個表項的值void setData(int i,T& x)/用x修改第i個表項的值bool Insert(int i,T& x);/插入x在第i個表項之后bool Remove(int i,T& x);/刪除第i個表項，通過x返回表

4、項的值bool IsEmpty();/判表空否，空則返回true；否則返回falsebool IsFull();/判表滿否，滿則返回true；否則返回falsevoid input();/輸入void output();/輸出void ofile();/存儲在文件中void ifile();/讀取文件并顯示 主要功能1、 建立新表2、 對表進行插入（指定元素前、后以及指定位置插入）、刪除（指定元素刪除及指定位置刪除）、修改等操作3、 顯示當前操作表的全部內容4、 存儲在文件中5、 從文件中讀取表五、主要代碼SeqList.h中的主要代碼：1、 類成員聲明部分：protected:T *data

5、;/存放數組int maxSize;/最大可容納表項的項數int last;/當前已存表項的最后位置（從0開始）void reSize(int newSize);/改變data數組空間大小public:SeqList(int sz = defaultSize);/構造函數SeqList(SeqList<T>& L);/復制構造函數SeqList()delete data;/析構函數int Size()constreturn maxSize;/計算表最大可容納表項個數int Length()constreturn last+1;/計算表長度int search(T&

6、x)const;/搜索x在表中位置，函數返回表項序號int Locate(int i)const; /定位第i個表項，函數返回表項序號bool getData(int i,T& x)const/去第i個表項的值if(i>0&&i<=last+1)x=datai-1;return true;else return false;void setData(int i,T& x)/用x修改第i個表項的值if(i>0&&i<=last+1) datai-1=x;bool Insert(int i,T& x);/插入x在第i個

7、表項之后bool Remove(int i,T& x);/刪除第i個表項，通過x返回表項的值bool IsEmpty()return (last = -1)?true:false;/判表空否，空則返回true；否則返回falsebool IsFull()return (last = maxSize-1)?true:false;/判表滿否，滿則返回true；否則返回falsevoid input();/輸入void output();/輸出SeqList<T>operator=(SeqList<T>& L);/表整體賦值void ofile();/存儲在文

8、件中void ifile();/讀取文件并顯示 2、 部分成員函數/搜索函數：在表中順序搜索與給定值x匹配的表項，找到則函數返回該表項是第幾個元素/否則函數返回0，表示搜索失敗template<class T>int SeqList<T>:search(T& x)constfor(int i = 0;i <= last; i+)if(datai = x) return i+1;/順序搜索return 0;/搜索失敗/定位函數：template<class T>int SeqList<T>:Locate(int i)constif(i

9、 >= i&&i <= last+1) return i ;else return 0;/插入函數/將新元素x插入到表中第i（i>=0&&i<=last+1）個表項之后，函數返回插入成功的信息，若/插入成功，則返回true；否則返回false.i=0是虛擬的，實際上是插入的第1個元素位置template<class T>bool SeqList<T>:Insert(int i,T& x)if(last = maxSize-1) return false;/表滿，不能插入if(i<0 | i>la

10、st+1) return false;/參數i不合理，不能插入for(int j = last ;j >=i;j-)/依次后移，空出第i號位置dataj+1 = dataj;datai = x;/插入last+;/最后位置+1return true;/插入成功/刪除函數/從表中刪除第i個表項，通過應用型參數x返回刪除的元素值，函數/返回刪除成功的信息，如刪除成功則返回true，否則返回falsetemplate<class T>bool SeqList<T>:Remove(int i,T& x)if(last = -1 )return false;if(i

11、<1 | i>last+1)return false;x = datai-1;for(int j = i;j <= last;j+)dataj-1 = dataj;last-;return true;/輸入函數/從標準輸入逐個數據輸入，建立順序表template<class T>void SeqList<T>:input()cout<<"開始建立順序表，請輸入表中的元素個數:"while(1)cin>>last;if(last<=maxSize-1) break;cout<<"表元

12、素個數有誤，范圍不能超過"<<maxSize<<":"for(int i = 0;i < last;i+)cout<<"#"<<i+1<<":"cin>>datai;/輸出函數template<class T>void SeqList<T>:output()cout<<"順序表當前元素最后的位置為："<<last<<endl;for(int i = 0;i < l

13、ast;i+)cout<<"#"<<i+1<<":"<<datai<<endl;/存儲在文件中template<class T>void SeqList<T>:ofile()ofstream f1("Test1.txt",ios:out);if(!f1)cout<<"存儲文件失敗！"<<endl;exit(1);for(int i = 1;i < last+1;i+)f1.write(char*) &a

14、mp;datai-1,sizeof(datai-1);cout<<"存儲成功！"<<endl;f1.close();/讀取文件并打印出文件內容template<class T>void SeqList<T>:ifile()ifstream f2("Test1.txt",ios:binary);if(!f2)cout<<"打開文件失敗！"<<endl;exit(1);cout<<"文件內容如下："<<endl;for(in

15、t i = 1;!f2.eof();i+)f2.read(char*)&datai-1,sizeof(datai-1);for(int j = 1;j < i-1;j+)cout<<"#"<<j<<":"<<dataj-1<<endl;f2.close(); 測試主函數1、插入功能，對不同位置的插入通過修改函數Insert(int i,x)第一形參實現,位置可通過成員函數search(x)確定case 3:/指定元素后插入int x,y;cout<<"請輸入指

16、定元素:"cin>>x;cout<<"請輸入要插入的元素:"cin>>y;Seq.Insert(Seq.search(x),y);break; case 4:/指定位置插入int i,x;cout<<"請輸入插入的位置:"cin>>i;cout<<"請輸入要插入的元素:"cin>>x;Seq.Insert(i,x);break; case 5:/按內容刪除指定元素int i,x;cout<<"請輸入要刪除的元素內容:&q

17、uot;cin>>x;i = Seq.search(x);/指定元素位置if(Seq.Remove(i,x) cout<<"刪除成功！"<<endl;else cout<<"刪除失敗！"<<endl;break; 2、刪除功能，指定序號刪除直接調用Remove(i,x)即可實現，指定表項的內容刪除可通過search(x)函數返回得到該表項的序號，再通過Remove(i,x)實現case 5:/按內容刪除指定元素int i,x;cout<<"請輸入要刪除的元素內容:"

18、;cin>>x;i = Seq.search(x);/指定元素位置if(Seq.Remove(i,x) cout<<"刪除成功！"<<endl;else cout<<"刪除失敗！"<<endl;break; case 6:/按位置刪除指定元素int i,x;cout<<"請輸入要刪除的元素序號:"cin>>i;if(Seq.Remove(i,x) cout<<"刪除成功，刪除的元素是:"<<x<<

19、endl;else cout<<"刪除失敗！"<<endl;break; 3、顯示功能，直接調用成員函數output()即可實現。4、查找功能，指定序號的查找通過成員函數getData(i,x)，其中的應用型形參可以返回該序號表項的值；指定表項查找通過成員函數search(x)即可實現case 8:/查找指定序號的元素int i,x;cout<<"請輸入要查找元素的序號:"cin>>i;if(Seq.getData(i,x) cout<<"第"<<i<<

20、;"個元素的值 是:"<<x<<endl;else cout<<"查找失敗！"<<endl;break; case 9:/查找指定內容的元素int x;cout<<"請輸入要查找元素的內容:"cin>>x;if(Seq.search(x) cout<<x<<"在 "<<Seq.search(x)<<" 位！ "<<endl;else cout<<"查找失敗！"<<endl;break; 5、修改功能，調用成員函數setData(i,x)即可實現case 10:/修改指定位置元素的數據int i,x,y;cout<<"請輸入要修改元素的序號:"cin>>i;cout<<"請輸入要替代的元素數據:"cin>>x;Seq.setData(i,x);Seq.getData(i,y);/用y判定修改成