數(shù)據(jù)結構線性表的順序表示和實現(xiàn)

數(shù)據(jù)結構實驗報告

實驗一線性表的順序表示和實現(xiàn)

實驗人：學號：Xb09620125時間：2011.03.09

一、實驗目的

1,掌握線性表的動態(tài)分配順序存儲結構

2.掌握線性表合并算法。

二、實驗內(nèi)容

已知順序線性表La和Lb的元素按值非遞減排列，歸并La和Lb得到新的

順序線性表Lc,Lc的元素也按值非遞減排列。（算法2.7）

三、實驗步驟：

1.創(chuàng)建線性表La和Lbo

2.合并La和Lb得到Lc。

3.輸出La、Lb、LCo

四、算法說明

先建立線性表La與Lb,然后合并兩線性表。

五、測試結果

六、分析與探討

合并兩線性表時，數(shù)據(jù)元素按非遞減排列。

七、附錄：源代碼

源代碼列在附錄中，要求程序風格清晰易理解，有充分的注釋。有意義的注釋行不少于30%.

#defineTRUE1

#defineFALSE0

#defineOK1

#defineERROR0

#defineINFEASIBLE-2

1

數(shù)據(jù)結構實驗報告

#defineOVERFLOW-2

//Status是函數(shù)的類型，其值是函數(shù)結果狀態(tài)代碼

typedefintStatus;

typedefintElemType;〃元素類型定義為整型

#include<iostream.h>

#defineLISTJNIT_SIZE100〃存儲空間的初始分配量

#defineLISTINCREMENT10〃存儲空間的分配增量

typedefstruct{

ElemType*elem;〃指向存儲空間的基地址

intlength;〃線性表的當前長度

intlistsize;〃當前分配的存儲容量

JSqList;

StatusInitList_Sq(SqList&L){//算法2.3

//構造一個空的線性表Lo

L.elem=new(ElemType[LIST_INIT_SIZE*sizeof(ElemType)]);

if(IL.elem)returnOVERFLOW;//存儲分配失敗

L.length=0;//空表長度為0

L.listsize=LISTJNIT_SIZE;//初始存儲容量

returnOK;

}//InitList_Sq

StatusDestroyList_Sq(SqList&L){

if(L.elem)delete(L.elem);〃釋放線性表的存儲空間

L.elem=NULL;

returnOK;

}//DestroyList_Sq

ElemType*realloc(SqListL){〃再申請LISTINCREMENT個空間

ElemType*p,*q,*r;

p=new(ElemType[(L.listsize+LISTINCREMENT)*sizeof(ElemType)]);

if(!p)returnNULL;q=p;r=L.elem;

for(inti=1;i<=L.length;i++){*q=*r;q++;r++;}

deleteL.elem;

returnp;

}

StatusListInsert_Sq(SqList&L,inti,ElemTypee){//算法2.4

//在順序線性表L的第i個元素之前插入新的元素e,

〃i的合法值為l〈WListLength_Sq(L)+l

ElemType*p;

if(i<111i>L.length+l)returnERROR;//i值不合法

if(L.length>=L.listsize){//當前存儲空間已滿，增加容量

ElemType*newbase=realloc(L);

if(!newbase)returnERROR;//存儲分配失敗

L.elem=newbase;//新基址

L.listsize+=LISTINCREMENT;//增加存儲容量

2

數(shù)據(jù)結構實驗報告

ElemType*q=&(L.elem[i-1]);//q為插入位置

for(p=&(L.elem[L.length-1]);p>=q;—p)*(p+l)=*p;

//插入位置及之后的元素右移

*q=e;//插入e

++L.length;//表'1011

returnOK;

}//ListInsert_Sq

StatusListInsert(SqList&L,ElemType

e){if(!L.length)L.elem[0]=e;

inti=L.length;

while(e<=L.elem[i-l]&&i>0){

L.elem[i]=L.elem[i-1];

I

)

L.elem[i]=e;

L.length++;

returnOK;

)

StatusMergeList_Sq(SqListLa,SqListLb,SqList&Lc){//算法2.7

II已知順序線性表La和Lb的元素按值非遞減排列。

//歸并La和Lb得到新的順序線性表Lc,Lc的元素也按值非遞減排列。

ElemType*pa,*pb,*pc,*pa_last,*pb_last;

〃使pa、pb分別指向La和Lb的第一個元素

pa=La.elem;pb=Lb.elem;

〃為Lc申請空間

Lc.listsize=Lc.length=La.length+Lb.length;

pc=Lc.elem=new(ElemType[Lc.listsize*sizeof(ElemType)]);

if(!Lc.elem)

returnOVERFLOW;//存儲分配失敗

〃使pa」ast、pbjast分別指向La和Lb的最后一個元素

pa_last=La.elem+La.length-1;

pbjast=Lb.elem+Lb.length-1;

while(pa<=pa」ast&&pb<=pbjast){〃歸并

if(*pa<=*pb){*pc++=*pa++;}

else*pc++=*pb++;

}

while(pa<=pa_last)*pc++=*pa++;//插入La的剩余元素

while(pb<=pbjast)*pc++=*pb++;//插入Lb的乘U余元素

return(OK);l;

}//MergeList

voidListTraverse_Sq(SqListL)

{inti;

for(i=1;i<=L.length;i++)cout<vLelem"[]<<""；

cout<<endl;

3

數(shù)據(jù)結構實驗報告

voidmain()

{inti;

〃建立兩個元素按值非遞減排列的順序線性表La和Lb,并將它們合并為一個有序順序

表Lc

〃顯示La、Lb和Lc的內(nèi)容

SqListLa,Lb,Lc;ElemTypezl,z2;

InitList_Sq(La);

coutvv”讀入3個元素并插入到順序表La中"vvendl;

for(i=l;i<=3;i++)

{cin>>zl;

Listinsert(La,zl);

}

coutw”順序表La中所有元素如下:"<<endl;

ListTraverse_Sq(La);

InitList_Sq(Lb);

coutvv”讀入3個元素并插入到順序表Lb中"v<endl;

for(i=l;i<=3;i++){

c