合并两个非递减有序线性表.doc

/* 实验一（顺序表）：设有非递减有序线性表 LA（3,5,8,11）和LB=（2,6,8,9,11,15,20）,若LA和LB分别表示两个集合A和B，求新集合AAUB(并操作，相同元素不保留)；预测输出：LA=（3, 5, 8, 11, 2, 6, 9, 15, 20） */以下是求集合A=AUB的算法 /*status merge(sqlist &la,sqlist lb)/ 将lb中和la中元素不同的数据元素归并至la中 len=la.length;/la中元素的个数q=la.elem+len;/q为插入位置pa=la.elem;pb_last=lb.elem+lb.length-1;/lb中表尾元素的地址for(pb=lb.elem;pb=pb_last;pb+)for(;pa=la.elem+len-1&*pala.elem+len-1|*pa*pb)/若表中不存在和*pb相等的元素，则插入if(la.length=la.listsize)/若容量不够，增加分配newbase=(int *)realloc(la.elem,(la.listsize+LISTINCREMENT)*sizeof(int);if(!newbase) exit(OVERFLOW);la.elem=newbase;la.listsize+=LISTINCREMENT;q=la.elem+la.length;/q为插入位置/ end if *q+=*pb;(la.length)+;/end if/ end forreturn OK;/merge*/以下是程序#include#include#include#define LISTINCREMENT10#define OK1#define ERROR0#define OVERFLOW-1/* 类型定义 */typedef structint *elem;int length;int listsize; sqlist;typedef int status ;/* 操作 */status creat(sqlist &l)/* 建立含有n个数据元素的顺序表 */int i,n;printf(请输入表中数据元素的个数：);scanf(%d,&n);while(n=0)printf(数值太小，请重新输入!);scanf(%d,&n);l.length=n;/表长为元素个数l.elem=(int *)malloc(n*sizeof(int);if(!l.elem) exit(OVERFLOW);l.listsize=n;printf(请输入%d个元素:n,n);for(i=0;in;i+)/输入n个元素scanf(%d,l.elem+i);scanf(%*c);/消除最后一个元素后回车对后续输入的影响return OK;status merge(sqlist &la,sqlist lb)/* 将lb中和la中元素不同的数据元素归并至la中 */int *pa,*pb,*newbase,*pb_last,len,*q;len=la.length;/la中元素的个数q=la.elem+len;pa=la.elem;pb_last=lb.elem+lb.length-1;/lb中表尾元素的地址for(pb=lb.elem;pb=pb_last;pb+)for(;pa=la.elem+len-1&*pala.elem+len-1|*pa*pb)/若表中不存在和*pb相等的元素，则插入if(la.length=la.listsize)/若容量不够，增加分配newbase=(int *)realloc(la.elem,(la.listsize+LISTINCREMENT)*sizeof(int);if(!newbase) exit(OVERFLOW);la.elem=newbase;la.listsize+=LISTINCREMENT;q=la.elem+la.length;/q为新的插入位置/ end if *q+=*pb;(la.length)+;/ end if/ end for return OK;void print(sqlist l)/ 输出顺序表l中的数据元素 int i;for(i=0;i=l.length-1;i+)printf(%5d,l.elemi);printf(n);void destroy(sqlist &l)free(l.elem);l.elem=NULL;l.length=0;l.listsize=0;void main()sqlist la,lb;int i;char ch,c;for(i=0;i=60;i+) printf(*);printf(ncreat:C print:P merge:M destroy:D exit:En);for(i=0;i=60;i+) printf(*);printf(n);printf(请输入：n);ch=getchar();fflush(stdin);while(ch!=E&ch!=e)switch(ch)case r:case :break;case C:case c:printf(建立表A or B ？请输入A或Bn);scanf(%c,&c);while(c=n|c= ) scanf(%c,&c);fflush(stdin);if(c=a|c=A) creat(la);else if(c=b|c=B) creat(lb);else printf(输入出错!请重新选择操作命令!n);break;case P:case p:printf(输出表A or B ？请输入A或Bn);scanf(%c,&c);while(c=n|c= ) scanf(%c,&c);fflush(stdin);if(c=a|c=A)if(la.elem) print(la);else printf(表A不存在!n);else if(c=b|c=B)if(lb.elem) print(lb);else printf(表B不存在!n);else printf(输入出错!请重新选择操作命令!n);break;case M:case m:if(!la.elem)printf(表A不存在!n);else if(!lb.elem)printf(表B不存在!n);elsemerge(la,lb);printf(归并完毕!n);break;case D:case d:printf(销毁表A or B ？请输入A或Bn);scanf(%c,&c);while(c=n|c= ) scanf(%c,&c);fflush(stdin);if(c=a|c=A)if(la.elem) destroy(la);else printf(表A不存在!n);else