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

008 #include

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->datadata)

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 }

画图很重要。