// algo2-11.cpp 實現算法2.20、2.21的程序
 #include"c1.h"
 typedef int ElemType;
 #include"c2-5.h"
 #include"bo2-6.cpp"

 Status ListInsert_L(LinkList &L,int i,ElemType e) // 算法2.20
 { // 在帶頭結點的單鏈線性表L的第i個元素之前插入元素e
   Link h,s;
   if(!LocatePos(L,i-1,h))
     return ERROR; // i值不合法
   if(!MakeNode(s,e))
     return ERROR; // 結點分配失敗
   InsFirst(L,h,s); //對于從第i個結點開始的鏈表,第i-1個結點是它的頭結點
   return OK;
 }

 Status MergeList_L(LinkList La,LinkList Lb,LinkList &Lc,int(*compare)(ElemType,ElemType))
 { // 已知單鏈線性表La和Lb的元素按值非遞減排列。歸并La和Lb得到新的單鏈
   // 線性表Lc，Lc的元素也按值非遞減排列。（不改變La、Lb）算法2.21
   Link ha,hb,pa,pb,q;
   ElemType a,b;
   if(!InitList(Lc))
     return ERROR; // 存儲空間分配失敗
   ha=GetHead(La); // ha和hb分別指向La和Lb的頭結點
   hb=GetHead(Lb);
   pa=NextPos(ha); // pa和pb分別指向La和Lb的第一個結點
   pb=NextPos(hb);
   while(!ListEmpty(La)&&!ListEmpty(Lb)) // La和Lb均非空
   {
     a=GetCurElem(pa); // a和b為兩表中當前比較元素
     b=GetCurElem(pb);
     if(compare(a,b)<=0)
     {
       DelFirst(La,ha,q);
       InsFirst(Lc,Lc.tail,q);
       pa=NextPos(ha);
     }
     else // a>b
     {
       DelFirst(Lb,hb,q);
       InsFirst(Lc,Lc.tail,q);
       pb=NextPos(hb);
     }
   }
   if(!ListEmpty(La))
     Append(Lc,pa);
   else
     Append(Lc,pb);
   FreeNode(ha);
   FreeNode(hb);
   return OK;
 }

 int comp(ElemType c1,ElemType c2)
 {
   return c1-c2;
 }

 void visit(ElemType c)
 {
   printf("%d ",c); // 整型
 }

 void main()
 {
   LinkList La,Lb,Lc;
   int j;
   InitList(La);
   for(j=1;j<=5;j++)
     ListInsert_L(La,j,j); // 順序插入 1 2 3 4 5
   printf("La=");
   ListTraverse(La,visit);
   InitList(Lb);
   for(j=1;j<=5;j++)
     ListInsert_L(Lb,j,2*j); // 順序插入 2 4 6 8 10
   printf("Lb=");
   ListTraverse(Lb,visit);
   InitList(Lc);
   MergeList_L(La,Lb,Lc,comp); // 歸并La和Lb，產生Lc
   printf("Lc=");
   ListTraverse(Lc,visit);
   DestroyList(Lc);
 }