線性表的C++實(shí)現(xiàn)

1、學(xué) 生 實(shí) 驗(yàn) 報(bào) 告 學(xué) 院： 軟通學(xué)院 課程名稱： 數(shù)據(jù)結(jié)構(gòu)與算法 專業(yè)班級(jí)： 軟件工程125班 姓 名： 周學(xué)文 學(xué) 號(hào)： 0124005 學(xué)生實(shí)驗(yàn)報(bào)告（二）學(xué)生姓名周學(xué)文 學(xué)號(hào)0124005 同組人：無實(shí)驗(yàn)項(xiàng)目線性表Ö必修選修 演示性實(shí)驗(yàn) 驗(yàn)證性實(shí)驗(yàn) Ö操作性實(shí)驗(yàn) 綜合性實(shí)驗(yàn)實(shí)驗(yàn)地點(diǎn)W101 實(shí)驗(yàn)儀器臺(tái)號(hào)D11指導(dǎo)教師嚴(yán)軍勇實(shí)驗(yàn)日期及節(jié)次10.8/ 8,9節(jié)一、實(shí)驗(yàn)綜述 1、實(shí)驗(yàn)?zāi)康募耙竽康模?）復(fù)習(xí)值傳遞與地址傳遞； 2）掌握順序表和鏈表的程序?qū)崿F(xiàn)； 3）理解順序表和鏈表的含義。要求：1）編程：順序表的類實(shí)現(xiàn)及非遞減順序表的合并操作；2）編程：鏈表類的實(shí)現(xiàn)及非遞

2、減鏈表的合并操作 2、實(shí)驗(yàn)儀器、設(shè)備或軟件設(shè)備：PC軟件：VC6二、實(shí)驗(yàn)過程(編程，調(diào)試，運(yùn)行；請(qǐng)寫上源碼，要求要有注釋)1. 編程：順序表的類實(shí)現(xiàn)（多文檔項(xiàng)目編程），及非遞減順序表的合并操作代碼：?jiǎn)挝募a：#include <iostream>#include <string>#include <ctime>using namespace std;class Listpublic:List(int llistsize=100,int IIncrease_storage=50); /構(gòu)建一個(gè)空的線性表,指定默認(rèn)參數(shù)值，void Listout(); /輸出

3、當(dāng)前線性的內(nèi)容void DestroList();/銷毀當(dāng)前線性表int get_Listlength();/利用成語函數(shù)得到length值void ListInsert(int Location,int volume); /在Location位置插入volumeint ListDelete(int Location);/在Location位置刪除volumefriend void Sequence_List(List *L); /對(duì)非空線性表進(jìn)行排序friend void Tableof_merger(List l1,List l2,List *L3); /合并兩個(gè)線性表的內(nèi)容private

4、:int *StartAddress; /數(shù)組起始地址int length; /當(dāng)前長(zhǎng)度int listsize; /當(dāng)前分配的存儲(chǔ)長(zhǎng)度int Increase_storage; /當(dāng)存儲(chǔ)已滿時(shí)，增加存儲(chǔ)容量的值;List:List(int llistsize,int IIncrease_storage)listsize=llistsize;Increase_storage=IIncrease_storage;length=0;StartAddress=new int listsize+1;void List:Listout()if(length=0) /判斷當(dāng)前線性表是否為空cout<

5、<"當(dāng)前線性表為空！"<<endl;exit(0);cout<<"當(dāng)前線性表的長(zhǎng)度為："<<length<<endl;for(int i=1;i<=length;i+) cout<<StartAddressi<<" "cout<<endl;int List:get_Listlength()return length;void List:DestroList()delete StartAddress;cout<<"線性表

6、已銷毀！"<<endl;void List:ListInsert(int Location,int volume)if(Location<1|Location>length+1) /插入位置的合法性判斷cout<<"插入位置非法！"<<endl;exit(0);if(length=listsize) /如果長(zhǎng)度等于分配時(shí)的存儲(chǔ)長(zhǎng)度，則執(zhí)行內(nèi)存擴(kuò)展int *temp=new int listsize+Increase_storage+1;for(int i=1;i<=length;i+) /逐一復(fù)制前線性表P的內(nèi)

7、容tempi=StartAddressi;StartAddress=temp;for(int i=length+1;i>=Location;i-) StartAddressi=StartAddressi-1;StartAddressLocation=volume;length+;int List:ListDelete(int Location) /執(zhí)行此函數(shù)時(shí)會(huì)的到一個(gè)刪除值，便于保存/刪除位置的合法性判斷if(Location>length+1)cout<<"刪除位置非法！"<<endl;/存儲(chǔ)空間利用率的判斷if(length<

8、listsize-length) /如果當(dāng)前分配的存儲(chǔ)空間利用率小于50%，系統(tǒng)自動(dòng)釋放部分空間int *temp=new int listsize-length+1;for(int i=1;i<=length;i+) /逐一復(fù)制前線性表P的內(nèi)容tempi=StartAddressi;StartAddress=temp;/刪除算法int temp=StartAddressLocation;for(int i=Location;i<=length;i+)StartAddressi=StartAddressi+1;length-;return temp;void Tableof_mer

9、ger(List L1,List L2,List *L3) /合并函數(shù)int pa=1;int pa_Last=L1.length;int pb=1;int pb_Last=L2.length;while(pa<=pa_Last&&pb<=pb_Last)if(L1.StartAddresspa<=L2.StartAddresspb)(*L3).ListInsert(*L3).length+1,L1.StartAddresspa);pa+;continue;else(*L3).ListInsert(*L3).length+1,L2.StartAddresspb

10、);pb+;continue;while(pa<=pa_Last)(*L3).ListInsert(*L3).length+1,L1.StartAddresspa);pa+;while(pb<=pb_Last)(*L3).ListInsert(*L3).length+1,L2.StartAddresspb);pb+;void InitList(List *L,int n) /傳入List對(duì)象，并指定數(shù)據(jù)長(zhǎng)度n,在其初始化時(shí)便將其排好順序，默認(rèn)為從小到大for(int i=1;i<=n;i+)int TempListvolume=rand()%100;(*L).ListInse

11、rt(*L).get_Listlength()+1,TempListvolume);Sequence_List(L);void Sequence_List(List *L)/選擇排序法對(duì)表進(jìn)行排序int i,j,k,t;for(i=1;i<(*L).length;i+)k=i;for(j=i+1;j<(*L).length+1;j+)if(*L).StartAddressj<(*L).StartAddressk) k=j;t=(*L).StartAddressk;(*L).StartAddressk=(*L).StartAddressi;(*L).StartAddressi=t;void main()srand(time(0);List L1,L2,L3;InitList(&L1,10);L1.Listout();InitList(&L2,10);L2.Listout();Tableof_merger(L1,