数据结构与算法：已知两个递增单链表ab，合成一个递减的单链表c，要求使用单链表基本操作，伪代码

Question

如题所述

Answer 1

#include<stdio.h>
#include <stdlib.h>

typedef struct node
{
int data;
struct node *next;
}node,*list;
void init(list &head)
{
head=(list)malloc(sizeof(node));
head->next=NULL;
}

void input(list &h)
{
list p,q;
q=h;
printf("输入数据的个数 n : ");
int n;
scanf("%d",&n);
printf("请输入 %d 个有序递增数据:\n",n);
for (int i=0;i<n;i++)
{
// printf("第 %d 个: ",i+1);
p=(list)malloc(sizeof(node));
scanf("%d",&p->data);
p->next=q->next;
q->next=p;
q=p;
}
}

void output(list h)
{
list p;
p=h->next;
printf("输出数据\n");
while(p!=NULL)
{
printf("%d ",p->data);
p=p->next;
}
printf("\n");
}

void combine(list &a,list &b,list &c)
{
list p,q,t;
p=a->next;
q=b->next;
free(b);
b=q;
c=a;
a=p;
c->next=NULL;
while(p&&q)
{
if (p->data<=q->data)
{
a=a->next;
p->next=c->next;
c->next=p;
p=a;
}
else
{
b=q->next;
q->next=c->next;
c->next=q;
q=b;
}
}
if (p!=NULL)
{
while(p)
{
a=a->next;
p->next=c->next;
c->next=p;
p=a;
}
}
if (q!=NULL)
{
while(q)
{
b=q->next;
q->next=c->next;
c->next=q;
q=b;
}
}

}
void main()
{
list a,b,c;
init(a);init(b);
printf("\n输入链表A :\n");
input(a);
printf("\n输入链表B :\n");
input(b);

printf("输出合并后的链表:\n");
combine(a,b,c);
output(c);
}
结果：
输入链表A :
输入数据的个数 n : 3
请输入 3 个有序递增数据:
4 5 9

输入链表B :
输入数据的个数 n : 4
请输入 4 个有序递增数据:
2 3 7 10

输出合并后的链表:
输出数据
10 9 7 5 4 3 2