/* algo2-13.c 采用鏈表結構實現算法2.2的程序，僅有4句與algo2-2.c不同 */
 #include"c1.h"
 typedef int ElemType;
 #include"c2-2.h" /* 此句與algo2-2.c不同 */
 #include"bo2-2.c" /* 此句與algo2-2.c不同 */

 void MergeList(LinkList La,LinkList Lb,LinkList *Lc) /* 算法2.2,此句與algo2-2.c不同 */
 { /* 已知線性表La和Lb中的數據元素按值非遞減排列。 */
   /* 歸并La和Lb得到新的線性表Lc,Lc的數據元素也按值非遞減排列 */
   int i=1,j=1,k=0;
   int La_len,Lb_len;
   ElemType ai,bj;
   InitList(Lc); /* 創建空表Lc */
   La_len=ListLength(La);
   Lb_len=ListLength(Lb);
   while(i<=La_len&&j<=Lb_len) /* 表La和表Lb均非空 */
   {
     GetElem(La,i,&ai);
     GetElem(Lb,j,&bj);
     if(ai<=bj)
     {
       ListInsert(*Lc,++k,ai);
       ++i;
     }
     else
     {
       ListInsert(*Lc,++k,bj);
       ++j;
     }
   }
   while(i<=La_len) /* 表La非空且表Lb空 */
   {
     GetElem(La,i++,&ai);
     ListInsert(*Lc,++k,ai);
   }
   while(j<=Lb_len) /* 表Lb非空且表La空 */
   {
     GetElem(Lb,j++,&bj);
     ListInsert(*Lc,++k,bj);
   }
 }

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

 void main()
 {
   LinkList La,Lb,Lc; /* 此句與algo2-2.c不同 */
   int j,a[4]={3,5,8,11},b[7]={2,6,8,9,11,15,20};
   InitList(&La); /* 創建空表La */
   for(j=1;j<=4;j++) /* 在表La中插入4個元素 */
     ListInsert(La,j,a[j-1]);
   printf("La= "); /* 輸出表La的內容 */
   ListTraverse(La,print);
   InitList(&Lb); /* 創建空表Lb */
   for(j=1;j<=7;j++) /* 在表Lb中插入7個元素 */
     ListInsert(Lb,j,b[j-1]);
   printf("Lb= "); /* 輸出表Lb的內容 */
   ListTraverse(Lb,print);
   MergeList(La,Lb,&Lc);
   printf("Lc= "); /* 輸出表Lc的內容 */
   ListTraverse(Lc,print);
 }