2024年数据结构实验报告.doc

《数据构造》试验汇报一

试验内容：线性表

学号：??????????????姓名：??梁闪星

一、上机试验的问題和规定（需求分析）

2．线性表合并运算

?两个数据元素按值非递减有序排列的线性表，规定将两者归并為一种新表，新表中的数据元素仍按值非递减有序排列。规定分别采用次序和链式两种存储构造.。

二、程序设计的基本思想，原理和算法描述：

2．若采用次序存储构造，首先动态分派一种线性表Lc，并使pa，pb，pc分别指向La，Lb，Lc的基址，然后算出La，Lb的長度，在pa，pb所指元素都在La，Lb中時，把其中较小的一种插入到Lc中，并使指向较小元素的指针和pc分别加1。直到其中一种线性表中的元素所有插入到Lc中，把另一种线性表中的剩余元素也次序所有插入Lc中。

若采用链式存储构造，首先设置三个指针pa，pb，pc，其中pa,pb分别指向La表和Lb表中目前待比较插入的結点，而pc指向Lc中的目前最终一种結点，若pa-data=pb-data,则将pa所指結点链接到pc所指結点之后，否则将pb所指結点链接到pc所指結点之后。当一种為空時，阐明有一种表的元素已归并完，则只要将另一种表的剩余段链接在pc所指結点之后既可。

三、调试和运行程序过程中产生的问題及采用的措施：

调用函数時，参数传递錯误。通过一步一步调试根据提醒进行修改。

四、源程序及注释

#includestdio.h

#includestdlib.h

#defineINITSIZE100//线性表存储空间的初始分派量

#defineLISTINCREMENT10//线性表存储空间的分派增量

#defineOK1

#defineERROR0

#defineOVERFLOW-1

typedefintElemType;

typedefintStatus;

typedefstruct{

ElemType*elem;//存储空间基址

intlength;//目前長度

intlistsize;//目前分派的存储量（以sizeof(ElemType)為单位）

}SqList;

StatusInitList(SqListL)

{//构造一种空的次序表L.

L.elem=(ElemType*)malloc(100*sizeof(ElemType));

if(!L.elem)exit(OVERFLOW);

L.length=0;

L.listsize=INITSIZE;

return(OK);

}

voidAssign(SqListL)

{//為次序表L的各元素赋值。

inti,N;

printf(PleaseinputtheNumberoftheSqList:);

scanf(%d,N);

printf(Pleaseinputtheelements:);

for(i=0;iN;i++);{

scanf(%d,L.elem[i]);

L.length++;

}

}

voidMergeList(SqListLa,SqListLb,SqListLc){

//已知线性表La和Lb中的数据元素按值非递减排列

//归并La和Lb得到新的线性表Lc，Lc的数据元素也按值非递减排列

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

pa=La.elem;

pb=Lb.elem;

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

pc=Lc.elem=(ElemType*)malloc(Lc.listsize*sizeof(ElemType));

if(!Lc.elem)exit(OVERFLOW);//存储分派失败

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

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

while(pa=pa_lastpb=pb_last){//归并

if(*pa=*pb)*pc++=*pa++;

else*pc++=*pb++;

}

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

while(pb=pb_last)*pc++=*pb++;//插入Lb的剩余元素

}//MergeList_Sq

voidListTraverse(SqListL){

//遍历次序表L

inti;

for(i=0;i=L.length-1;i++);

printf(%d,L.elem[i]);