24 假設有兩個按元素值遞增有序排列的線性表A和B，均以單鏈表作存儲結構，請編寫算法將A表和B表歸並成一個按元素值遞減有序（即非遞增有序，允許表中含有值相同的元素）排列的線性表C，並要求利用原表（即A表和B表）的結點空間構造C表。
001 #define true 1
002 #define false 0
003 #define ok 1
004 #define error 0
005 #define infeasible -1
006 #define overflow -2
007 #include<stdio.h>
008 #include<malloc.h>
009 typedef int ElemType;
010 typedef int Status;
011
012 typedef struct LNode
013 {
014 ElemType data;
015 struct LNode * next;
016 } LNode,*LinkList;
017
018 void CreateList_TailInsert(LinkList *L)//尾插法構造鏈表;
019 {
020 LinkList p,r;
021 int ch;
022 scanf("%d",&ch);
023 r=(*L);//剛開始時,L是一個只有頭結點的空表,r指向該結點,也就是r指向L的尾巴.
024 while(ch!=0)
025 {
026 p=(LinkList)malloc(sizeof(LNode));
027 p->data=ch;
028 r->next=p;//增加p後,將p加到r後面
029 r=p;//重新將r指向L的尾巴;
030 scanf("%d",&ch);
031 }
032 r->next=NULL;
033 }
034 void InitList(LinkList *L)//初始化鏈表,構造帶頭結點的單鏈表;
035 {
036 *L=(LinkList)malloc(sizeof(LNode));
037 (*L)->next=NULL;
038 }
039
040 Status Merger_AandB_toC(LinkList*La,LinkList*Lb,LinkList*Lc)
041 {
042 //利用升序單鏈表A和升序單鏈表B的空間生成降序單鏈表C
043 LinkList pa,pb,qa,qb;
044 (*Lc)->next=NULL;
045 qa=(*La);
046 qb=(*Lb);
047 pa=(*La)->next;
048 pb=(*Lb)->next;
049 while(pa&&pb)
050 {
051
052 if(pa->data<pb->data)
053 {
054 qa=pa;
055 pa=pa->next;
056 qa->next=(*Lc)->next;
057 (*Lc)->next=qa;
058 }
059 else
060 {
061 qb=pb;
062 pb=pb->next;
063 qb->next=(*Lc)->next;
064 (*Lc)->next=qb;
065 }
066 }
067 if(!pa)
068 {
069 while(pb)
070 {
071 qb=pb;
072 pb=pb->next;
073 qb->next=(*Lc)->next;
074 (*Lc)->next=qb;
075 }
076 }
077 if(!pb)
078 {
079 while(pa)
080 {
081 qa=pa;
082 pa=pa->next;
083 qa->next=(*Lc)->next;
084 (*Lc)->next=qa;
085 }
086 }
087 }
088 int main()
089 {
090 LinkList La,Lb,p,Lc;
091 int i;
092 ElemType e;
093 InitList(&La);
094 printf("\n請逐個輸入數字,輸入0的時候結束\n");
095 CreateList_TailInsert(&La);
096 p=La;
097 printf("新建的單鏈表La打印為:\n");
098 while(p->next!=NULL)
099 {
100 printf("%d\t",p->next->data);
101 p=p->next;
102 }
103 InitList(&Lb);
104 printf("\n請逐個輸入數字,輸入0的時候結束\n");
105 CreateList_TailInsert(&Lb);
106 p=Lb;
107 printf("新建的單鏈表Lb打印為:\n");
108 while(p->next!=NULL)
109 {
110 printf("%d\t",p->next->data);
111 p=p->next;
112 }
113 InitList(&Lc);
114 printf("\nLa和Lb合並成為Lc後打印為:\n");
115 Merger_AandB_toC(&La,&Lb,&Lc);
116 p=Lc;
117 while(p->next!=NULL)
118 {
119 printf("%d\t",p->next->data);
120 p=p->next;
121 }
122 return 0;
123 }
畫圖很重要。
