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

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

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

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

4、:int *StartAddress; /數(shù)組起始地址int length; /當前長度int listsize; /當前分配的存儲長度int Increase_storage; /當存儲已滿時，增加存儲容量的值;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) /判斷當前線性表是否為空cout<

5、<"當前線性表為空！"<<endl;exit(0);cout<<"當前線性表的長度為："<<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í)行內(nèi)存擴展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ù)時會的到一個刪除值，便于保存/刪除位置的合法性判斷if(Location>length+1)cout<<"刪除位置非法！"<<endl;/存儲空間利用率的判斷if(length<

8、listsize-length) /如果當前分配的存儲空間利用率小于50%，系統(tǒ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對象，并指定數(shù)據(jù)長度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)/選擇排序法對表進行排序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,