假设有两个按元素值递增有序排列的线性表A和B,均以单链表作存储结构,请编写算法将A表和B表归并成一个按元素值递减有序(即非递增有序,允许表中含有值相同的元素)排列的线性表C,并要求利用原表(即A表和B表)的结点空间构造C表。
先输入A表的大小,再输入B表的大小,然后输入A表中的元素,再输入B表中的元素。
输出就是将C表中的元素输出。
输入:
5
3
1 3 5 7 8
2 4 6
输出:
8
#include<stdio.h>#include<stdlib.h>#define OK 1#define ERROR 0#define min(a,b) (a>b)?b:atypedef int Elemtype;typedef int status;typedef struct LNode {Elemtype date;LNode* next;}LNode,*LinkList;//创建一个链表,头插法,输入后元素顺序为倒序status CreatList(LinkList& L,int n) {L = (LinkList)malloc(sizeof(LNode));L->next = NULL;LinkList p;for (int i = 0; i < n; i++) {p = (LinkList)malloc(sizeof(LNode));scanf_s("%d", &p->date);p->next = L->next;L->next = p;}return OK;}//合并两个链表status Mergelist(LinkList &Lc, LinkList La, LinkList Lb) {LinkList pa, pb,pc;pa = La->next;pb = Lb->next;pc = La;//Lc = pc;//La的头结点等于Lc的头结点while (pa && pb) {if (pa->date >= pb->date) {pc->next = pa; pc = pa; pa = pa->next;}else {pc->next = pb; pc = pb; pb = pb->next;}}pc->next = pa ? pa : pb;free(Lb);//释放Lb的头结点return OK;}//输出链表中的数status PrintfList(LinkList L) {LinkList p;p = L->next;while (p) {printf("%d ", p->date);p = p->next;}return OK;}//主函数int main() {int a, b;scanf_s("%d%d", &a, &b);LinkList La, Lb,Lc;CreatList(La, a);CreatList(Lb, b);Mergelist(Lc, La, Lb);PrintfList(Lc);return 0;}
7 6 5 4 3 2 1