数据结构线性表的顺序表示和实现

数据结构实验报告

实验一线性表的顺序表示和实现

实验人：学号：Xb09620125时间：2011.03.09

一、实验目的

1,掌握线性表的动态分配顺序存储结构

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

二、实验内容

已知顺序线性表La和Lb的元素按值非递减排列，归并La和Lb得到新的

顺序线性表Lc,Lc的元素也按值非递减排列。（算法2.7）

三、实验步骤：

1.创建线性表La和Lbo

2.合并La和Lb得到Lc。

3.输出La、Lb、LCo

四、算法说明

先建立线性表La与Lb,然后合并两线性表。

五、测试结果

六、分析与探讨

合并两线性表时，数据元素按非递减排列。

七、附录：源代码

源代码列在附录中，要求程序风格清晰易理解，有充分的注释。有意义的注释行不少于30%.

#defineTRUE1

#defineFALSE0

#defineOK1

#defineERROR0

#defineINFEASIBLE-2

1

数据结构实验报告

#defineOVERFLOW-2

//Status是函数的类型，其值是函数结果状态代码

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

数据结构实验报告

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

数据结构实验报告

voidmain()

{inti;

〃建立两个元素按值非递减排列的顺序线性表La和Lb,并将它们合并为一个有序顺序

表Lc

〃显示La、Lb和Lc的内容

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