将递增单链表A和递增单链表B合并为递减单链表C
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 }
画图很重要。
作者：耀耀