http://s4/middle/690e573948f6aae903663&690两个线性表合并的问题" TITLE="第二章 两个线性表合并的问题" />

// algo2-3.cpp 实现算法2.7的程序
 #include"c1.h"
 typedef int ElemType;
 #include"c2-1.h"
 #include"bo2-1.cpp"

 void MergeList(SqList La,SqList Lb,SqList &Lc) // 算法2.7
 { // 已知顺序线性表La和Lb的元素按值非递减排列。
   // 归并La和Lb得到新的顺序线性表Lc,Lc的元素也按值非递减排列
   ElemType *pa,*pa_last,*pb,*pb_last,*pc;
   pa=La.elem;  //直接用指针获取表La的首地址
   pb=Lb.elem;
   Lc.listsize=Lc.length=La.length+Lb.length;//不用InitList()创建空表Lc
   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_last&&pb<=pb_last) // 表La和表Lb均非空
   { // 归并
     if(*pa<=*pb)
       *pc++=*pa++;
     else
       *pc++=*pb++;
   }
   while(pa<=pa_last) // 表La非空且表Lb空
     *pc++=*pa++; // 插入La的剩余元素
   while(pb<=pb_last) // 表Lb非空且表La空
     *pc++=*pb++; // 插入Lb的剩余元素
 }

 void print(ElemType &c)
 {
   printf("%d ",c);
 }

 void main()
 {
   SqList La,Lb,Lc;
   int j;
   InitList(La); // 创建空表La
   for(j=1;j<=5;j++) // 在表La中插入5个元素
     ListInsert(La,j,j);
   printf("La= "); // 输出表La的内容
   ListTraverse(La,print);
   InitList(Lb); // 创建空表Lb
   for(j=1;j<=5;j++) // 在表Lb中插入5个元素
     ListInsert(Lb,j,2*j);
   printf("Lb= "); // 输出表Lb的内容
   ListTraverse(Lb,print);
   MergeList(La,Lb,Lc);
   printf("Lc= "); // 输出表Lc的内容
   ListTraverse(Lc,print);
 }

http://s2/middle/690e573948f6aae7f09d1&690两个线性表合并的问题" TITLE="第二章 两个线性表合并的问题" />

// algo2-4.cpp 修改算法2.7的第一个循环语句中的条件语句为开关语句，且当
 // *pa=*pb时，只将两者中之一插入Lc。此操作的结果和算法2.1相同
 #include"c1.h"
 typedef int ElemType;
 #include"c2-1.h"
 #include"bo2-1.cpp"

 int comp(ElemType c1,ElemType c2)
 {
   int i;
   if(c1<c2)
     i=1;
   else if(c1==c2)
     i=0;
   else
     i=-1;
   return i;
 }

 void MergeList(SqList La,SqList Lb,SqList &Lc)
 { // 另一种合并线性表的方法（根据算法2.7下的要求修改算法2.7）
   ElemType  *pa,*pa_last,*pb,*pb_last,*pc;
   pa=La.elem;
   pb=Lb.elem;
   Lc.listsize=La.length+Lb.length; // 此句与算法2.7不同
   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_last&&pb<=pb_last) // 表La和表Lb均非空
     switch(comp(*pa,*pb)) // 此句与算法2.7不同
     {
       case  0: pb++;
       case  1: *pc++=*pa++;
                break;
       case -1: *pc++=*pb++;
     }
   while(pa<=pa_last) // 表La非空且表Lb空
     *pc++=*pa++;
   while(pb<=pb_last) // 表Lb非空且表La空
     *pc++=*pb++;
   Lc.length=pc-Lc.elem; // 加此句
 }

 void print(ElemType &c)
 {
   printf("%d ",c);
 }

 void main()
 {
   SqList La,Lb,Lc;
   int j;
   InitList(La); // 创建空表La
   for(j=1;j<=5;j++) // 在表La中插入5个元素
     ListInsert(La,j,j);
   printf("La= "); // 输出表La的内容
   ListTraverse(La,print);
   InitList(Lb); // 创建空表Lb
   for(j=1;j<=5;j++) // 在表Lb中插入5个元素
     ListInsert(Lb,j,2*j);
   printf("Lb= "); // 输出表Lb的内容
   ListTraverse(Lb,print);
   MergeList(La,Lb,Lc);
   printf("Lc= "); // 输出表Lc的内容
   ListTraverse(Lc,print);
 }
-------------------------------------

http://s13/middle/690e573948f6abc932c0c&690两个线性表合并的问题" TITLE="第二章 两个线性表合并的问题" />

 

// algo2-5.cpp 实现算法2.11、2.12的程序
 #include"c1.h"
 typedef int ElemType;
 #include"c2-2.h"
 #include"bo2-2.cpp"

 void CreateList(LinkList &L,int n) // 算法2.11   时间复杂度o(n)
 { // 逆位序(插在表头)输入n个元素的值，建立带表头结构的单链线性表L
   int i;
   LinkList p;
   L=(LinkList)malloc(sizeof(LNode));
   L->next=NULL; // 先建立一个带头结点的单链表
   printf("请输入%d个数据\n",n);
   for(i=n;i>0;--i)
   {
     p=(LinkList)malloc(sizeof(LNode)); // 生成新结点
     scanf("%d",&p->data); // 输入元素值
     p->next=L->next; // 插入到表头
     L->next=p;
   }
 }

 void CreateList2(LinkList &L,int n)
 { // 正位序(插在表尾)输入n个元素的值，建立带表头结构的单链线性表
   int i;
   LinkList p,q;
   L=(LinkList)malloc(sizeof(LNode)); // 生成头结点
   L->next=NULL;
   q=L;
   printf("请输入%d个数据\n",n);
   for(i=1;i<=n;i++)
   {
     p=(LinkList)malloc(sizeof(LNode));
     scanf("%d",&p->data);
     q->next=p;
     q=q->next;
   }
   p->next=NULL;
 }

 void MergeList(LinkList La,LinkList &Lb,LinkList &Lc)// 算法2.12
 { // 已知单链线性表La和Lb的元素按值非递减排列。
   // 归并La和Lb得到新的单链线性表Lc，Lc的元素也按值非递减排列
   LinkList pa=La->next,pb=Lb->next,pc;
   Lc=pc=La; // 用La的头结点作为Lc的头结点
   while(pa&&pb)
     if(pa->data<=pb->data)
     {
       pc->next=pa;
       pc=pa;
       pa=pa->next;
     }
     else
     {
       pc->next=pb;
       pc=pb;
       pb=pb->next;
     }
   pc->next=pa?pa:pb; // 插入剩余段
   free(Lb); // 释放Lb的头结点
   Lb=NULL;
 }

 void visit(ElemType c) // ListTraverse()调用的函数(类型要一致)
 {
   printf("%d ",c);
 }

 void main()
 {
   int n=5;
   LinkList La,Lb,Lc;
   printf("按非递减顺序, ");
   CreateList2(La,n); // 正位序输入n个元素的值
   printf("La="); // 输出链表La的内容
   ListTraverse(La,visit);
   printf("按非递增顺序, ");
   CreateList(Lb,n); // 逆位序输入n个元素的值
   printf("Lb="); // 输出链表Lb的内容
   ListTraverse(Lb,visit);
   MergeList(La,Lb,Lc); // 按非递减顺序归并La和Lb,得到新表Lc
   printf("Lc="); // 输出链表Lc的内容
   ListTraverse(Lc,visit);
 }