線性表的順序儲存結(jié)構(gòu)

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

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

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

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

5、/最大可容納表項(xiàng)的項(xiàng)數(shù)int last;/當(dāng)前已存表項(xiàng)的最后位置（從0開始）void reSize(int newSize);/改變data數(shù)組空間大小public:SeqList(int sz = defaultSize);/構(gòu)造函數(shù)SeqList(SeqList& L);/復(fù)制構(gòu)造函數(shù)SeqList()delete data;/析構(gòu)函數(shù)int Size()constreturn maxSize;/計算表最大可容納表項(xiàng)個數(shù)int Length()constreturn last+1;/計算表長度int search(T& x)const;/搜索x在表中位置，函數(shù)返回表項(xiàng)序號int Locat

6、e(int i)const; /定位第i個表項(xiàng)，函數(shù)返回表項(xiàng)序號bool getData(int i,T& x)const/去第i個表項(xiàng)的值if(i0&i0&i=last+1) datai-1=x;bool Insert(int i,T& x);/插入x在第i個表項(xiàng)之后bool Remove(int i,T& x);/刪除第i個表項(xiàng)，通過x返回表項(xiàng)的值bool IsEmpty()return (last = -1)?true:false;/判表空否，空則返回true；否則返回falsebool IsFull()return (last = maxSize-1)?true:false;/判表滿否

7、，滿則返回true；否則返回falsevoid input();/輸入void output();/輸出SeqListoperator=(SeqList& L);/表整體賦值void ofile();/存儲在文件中void ifile();/讀取文件并顯示 2、 部分成員函數(shù)/搜索函數(shù)：在表中順序搜索與給定值x匹配的表項(xiàng)，找到則函數(shù)返回該表項(xiàng)是第幾個元素/否則函數(shù)返回0，表示搜索失敗templateint SeqList:search(T& x)constfor(int i = 0;i = last; i+)if(datai = x) return i+1;/順序搜索return 0;/搜索失

8、敗/定位函數(shù)：templateint SeqList:Locate(int i)constif(i = i&i =0&i=last+1）個表項(xiàng)之后，函數(shù)返回插入成功的信息，若/插入成功，則返回true；否則返回false.i=0是虛擬的，實(shí)際上是插入的第1個元素位置templatebool SeqList:Insert(int i,T& x)if(last = maxSize-1) return false;/表滿，不能插入if(ilast+1) return false;/參數(shù)i不合理，不能插入for(int j = last ;j =i;j-)/依次后移，空出第i號位置dataj+1 =

9、dataj;datai = x;/插入last+;/最后位置+1return true;/插入成功/刪除函數(shù)/從表中刪除第i個表項(xiàng)，通過應(yīng)用型參數(shù)x返回刪除的元素值，函數(shù)/返回刪除成功的信息，如刪除成功則返回true，否則返回falsetemplatebool SeqList:Remove(int i,T& x)if(last = -1 )return false;if(ilast+1)return false;x = datai-1;for(int j = i;j = last;j+)dataj-1 = dataj;last-;return true;/輸入函數(shù)/從標(biāo)準(zhǔn)輸入逐個數(shù)據(jù)輸入，建立

10、順序表templatevoid SeqList:input()coutlast;if(last=maxSize-1) break;cout表元素個數(shù)有誤，范圍不能超過maxSize:;for(int i = 0;i last;i+)cout#i+1datai;/輸出函數(shù)templatevoid SeqList:output()cout順序表當(dāng)前元素最后的位置為：lastendl;for(int i = 0;i last;i+)cout#i+1:dataiendl;/存儲在文件中templatevoid SeqList:ofile()ofstream f1(Test1.txt,ios:out);

11、if(!f1)cout存儲文件失??！endl;exit(1);for(int i = 1;i last+1;i+)f1.write(char*) &datai-1,sizeof(datai-1);cout存儲成功！endl;f1.close();/讀取文件并打印出文件內(nèi)容templatevoid SeqList:ifile()ifstream f2(Test1.txt,ios:binary);if(!f2)cout打開文件失??！endl;exit(1);cout文件內(nèi)容如下：endl;for(int i = 1;!f2.eof();i+)f2.read(char*)&datai-1,sizeo

12、f(datai-1);for(int j = 1;j i-1;j+)cout#j:dataj-1endl;f2.close(); 測試主函數(shù)1、插入功能，對不同位置的插入通過修改函數(shù)Insert(int i,x)第一形參實(shí)現(xiàn),位置可通過成員函數(shù)search(x)確定case 3:/指定元素后插入int x,y;coutx;couty;Seq.Insert(Seq.search(x),y);break; case 4:/指定位置插入int i,x;couti;coutx;Seq.Insert(i,x);break; case 5:/按內(nèi)容刪除指定元素int i,x;coutx;i = Seq.s

13、earch(x);/指定元素位置if(Seq.Remove(i,x) cout刪除成功！endl;else cout刪除失??！endl;break; 2、刪除功能，指定序號刪除直接調(diào)用Remove(i,x)即可實(shí)現(xiàn)，指定表項(xiàng)的內(nèi)容刪除可通過search(x)函數(shù)返回得到該表項(xiàng)的序號，再通過Remove(i,x)實(shí)現(xiàn)case 5:/按內(nèi)容刪除指定元素int i,x;coutx;i = Seq.search(x);/指定元素位置if(Seq.Remove(i,x) cout刪除成功！endl;else cout刪除失?。ndl;break; case 6:/按位置刪除指定元素int i,x;co

14、uti;if(Seq.Remove(i,x) cout刪除成功，刪除的元素是:xendl;else cout刪除失??！endl;break; 3、顯示功能，直接調(diào)用成員函數(shù)output()即可實(shí)現(xiàn)。4、查找功能，指定序號的查找通過成員函數(shù)getData(i,x)，其中的應(yīng)用型形參可以返回該序號表項(xiàng)的值；指定表項(xiàng)查找通過成員函數(shù)search(x)即可實(shí)現(xiàn)case 8:/查找指定序號的元素int i,x;couti;if(Seq.getData(i,x) cout第i個元素的值 是:xendl;else cout查找失敗！endl;break; case 9:/查找指定內(nèi)容的元素int x;cou

15、tx;if(Seq.search(x) coutx在 Seq.search(x) 位！ endl;else cout查找失??！endl;break; 5、修改功能，調(diào)用成員函數(shù)setData(i,x)即可實(shí)現(xiàn)case 10:/修改指定位置元素的數(shù)據(jù)int i,x,y;couti;coutx;Seq.setData(i,x);Seq.getData(i,y);/用y判定修改成功與否if(y = x) cout修改成功！endl;else cout修改失?。ndl;break;6、存儲與讀取文件，調(diào)用成員函數(shù)ofile()與ifile()即可case 11:/存儲在文件中Seq.ofile();break;case 12:/讀取存儲的文件Seq.ifile();break;六、測試結(jié)果及說明1、新建表及顯示功能設(shè)置值：sz=5，#1=7，#2=4，#3=1，#4=5，#5=62、插入功能在指定元素前插入指定元素x=4，插入值y=3在指定元素后插入，指定元素x=5，插入值2，結(jié)果如左圖在指定位置插入，位置i=4，插入值9，結(jié)果如右圖3、 刪除功能按內(nèi)容刪除，指定刪除x=1，結(jié)果如左圖按序號刪除，指定序號i=2，結(jié)果如右圖4、 查找功能查找指定序號的元素，指定序號i=5，結(jié)果如左圖查找指定元素的序號，指定元素x=2，結(jié)果如右圖5、 修