两线性表的合并数据结构实验报告

1、站昌航空大学卖验报告课程名称：数据结构班级：指导教师评定：签实验名称:学生姓名:名：实验一线性表的顺序存储结构学号:题目：有两张非递减有序的线性学生表A,B,采用顺序存储结构，两张表合并用c表存，要求C仍为非递减有序的，并删除C中值相同的表。一、需求分析用户可以根据自己的需求分别输入两个整型的线性表，有必要的话可以通过源程序改变是否为整型，再进行输入。程序执行的命令包括：构造线性表A(2)构造线性表B(3)求两张表的并(4)删除C中值相同的元素(5)将己合并的线性表进行逆序排列二、概要设计为实现上述算法，需要线性表的抽象数据类型：ADTStack数据对象:D=ai:aiWElemSet,i二1

2、n,n$0数据关系：Rl=|ai-i,aiGD,i=2,n$0基本操作：initlist(&L)操作结果：构造一个空的线性表LListLength(L)初始条件：线性表L已经存在操作结果：返回L中数据元素的个数。LocateElem(List*La,ElemTypee,inttype)初始条件：线性表La已经存在操作结果：判断La中是否有与e相同的元素。MergeList(La,Lb,&Lc)初始条件：非递减线性表La,Lb已经存在操作结果：合并La,Lb得到Lc,Lc仍按非递增有序排列。UnionList(List*La,List*Lb)初始条件：线性表La,Lb已经存在操作结果:将所有在L

3、b而不在La中的元素插入到La中表尾的位置。PrintList(L)初始条件：线性表L已经存在操作结果：打印出表L。Listlnsert(List*L,inti,structSTUe)初始条件：线性表L已经存在，1WiWListLength(&L)+l操作结果：在表L中第i个位置前插入元素e,L的长度加1。ADTList本程序有三个模块：主程序模块mainO初始化；接受命令；显示结果：线性表单元模块：实现线性表抽象数据类型；结点结构单元模块：定义线性表中的结点结构。三、详细设计1元素类型，结点类型typedefstructsqlistint*a;intlength;intlistsize;sq

4、list;sqlistla,lb,lc;sqlistinitlist()sqlist1;1a=(int*)malloc(listinitsize*sizeof(int);if(!l.a)exit(OVERFLOW);1length二0;1.listsize=listinitsize;:return1;2.对抽彖数据类型中的部分基本操作的伪码算法如卞：sqlistaddlist(sqlistla,sqlistlb,sqlistlc)/*合并两顺序表*/inti二1,j=l,k=l;while(i=la1ength&j=lb1ength)if(la.ai=lb.aj)lc.ak=lbai;i+；k

5、+;elselcak=laaj;j+;k+;while(i=lalength)lc.ak=laaLi;k+;i卄；while(j=lblength)lcak=lbaLj;k+;j卄；lc.gth=kl;returnlc;voidprintlist(sqlist1)inti=l;for(i=l;i0)j二0；for(i=l;iLlength;i+)k二0;while(k=j&Lak!=Lai)k+;if(k=j+l)L.aj+=L.ai;Llength二j;returnL;/*删除线性表中的相同的元素*/sqlistchange(sqlist1)inti,t;for(i=l;i#includem

6、alloch#definelistinitsize100#defineOVERFLOW-1/*线性表的定义*/typedefstructsqlistint*a;intlength;intlistsize;sqlist;sqlistla,lb,lc;/*建立一个空表*/sqlistinitlist()sqlist1;1a=(int*)malloc(listinitsize*sizeof(int);if(!l.a)exit(OVERFLOW);1.length二0;1.listsize=listinitsize;return1;sqlistcreatlist(sqlist1,intnum)intj

7、；intp；for(j=l;j=num;j+)scanf&p);laaj二p；la.length+;/*合并两线性表*/sqlistaddlist(sqlistla,sqlistlb,sqlistlc)inti二1,j=l,k=l;while(i=la1ength&j=lb1ength)if(la.ai=lb.aj)lc.ak=lbai;i+；k+;elselc.ak=laaj;j+;k+;while(i=lalength)lc.ak=laaLi;k+;i卄；while(j=lblength)lcak=lbaLj;k+;j+；lc.1己11gth=kl;returnlc;/*打印线性表*/vo

8、idprintlist(sqlist1)inti=l;for(i=l;i0)j二0；for(i=l;iLlength;i+)k二0;while(k=j&L.ak!=L.ai)k+;if(k=j+l)L.aj+=L.ai;Llength二j;returnL;/*将线性表进行逆序排列*/sqlistchange(sqlist1)inti,t;for(i=l;i=l.length/2;i+)t二1ai;1ai二1.allengthi;1.allength一i二t;return1;/*主函数*/mainOintnum,numO;intp；inti,j;la=initlist0;lb=initlist();lc=initlist0;printf(PleaseinputthenumlbersofyouwantalboutLa：);scanf(，z%d，z,&num);printf(n);creatlist(la,num);printf(，znPleaseinputthenumlbersofyouwantalboutLb:);scanf(，z%d，z,&numO);printf(n);creatlist(lb,numO);printf(Thel