Question

两个按元素值递增有序排列的线性表A和B，均以单链表作为存储结构，请编写算法将A表和B表归并成一个

1.假设有两个按元素值递增有序排列的线性表A和B，均以单链表作为存储结构，请编写算法将A表和B表归并成一个按元素值递减有序（即非递增有序，允许表中含有值相同的元素）排列的线性表C，并要求利用原表（即A表和B表）的结点空间构造C表。#include<stdio.h>#include<string.h>#include<malloc.h>typedef struct LNode{int data; struct LNode *next;}LNode,*LinkList;void Creatlist(LinkList L){ LinkList p; int num; printf("输入若干整数，输入-1表示结束\n"); while(scanf("%d ",&num),num!=-1) { p=(LinkList)malloc(sizeof(LNode)); p->data=num; p->next=L->next; L->next=p; }}void PrintList(LinkList L){ LinkList p; p = L->next; while(p) { printf("%d\n",p->data); p=p->next; }}int MergeList(LinkList la,LinkList lb,LinkList lc){ LinkList pa,pb,pc; pa=la->next;pb=lb->next; lc=pc=la; while(pa&&pb) { if(pa->data<=pb->data){ pc->next=pa;pc=pa;pa=pa->next; } else{pc->next=pb;pc=pb;pb=pb->next;} pc->next=pa?pa:pb; free(lb); return lc;}}int main(void){ LinkList LA,LB,LC; Creatlist(LA); Creatlist(LB); MergeList(LA,LB,LC); PrintList(LC); return 0;}这个代码运行时只能输入第一个单链表的数据，

Answer 1

下面大体介绍一下基本思想：
由于是递增的单链表：0->0->0->0 这种结构不能逆向反问；所以直接做操作是很不好实现的；
所以我第一步是将两链表的指针反转，这样就使原来两链表由递增序列变成了递减序列；第二步在根据
合并排序的思想，将两个链合并； 思路比较简单，你一看因该能明白，我用C++实现了一下想法，代码如下：
#include <iostream>

using namespace std;

const int N = 8;

struct Node
{
int data;
Node* next;
Node(int d = 0, Node* n = 0):data(d), next(n){}
};

void Print(Node* p)
{
do
{
cout << p->data << " ";
p = p->next ;
}while(p);
cout << endl;
}

void Create(Node*& List)
{
int i;
Node* tail = 0;

for(i = 0; i < N; i++)
{
Node* q = new Node;
q->data = (rand()%100);

if(tail == 0) tail = q, List = q;
else
{
tail->next = q;
tail = tail->next;
}
}
}

void Sort(Node*& List)
{
for(Node* p = List; p != 0; p = p->next)
{
for(Node* q = p; q != 0; q = q->next)
{
if(q->data < p->data) swap(q->data, p->data);
}
}
}

void Converse(Node*& List) //将链表中指针逆向,实际上就是将递增序列变为递减序列
{
Node* p, *q, *temp;
p = List; //第一个节点
q = p->next; //第二个节点
temp = q->next; //第三个节点
List->next = 0;

while(temp)
{
q->next = p;
p = q;
q = temp;
temp = temp->next;
}
List = q;
q->next = p;
}

void Merge(Node*& List1, Node*&List2, Node*& List3)
{
//这里做法类似归并排序
Node* p, *q, *tail;
p = List1, q = List2;

while(p && q)
{
if(List3 == 0)
{
List3 = p->data > q->data ? p : q;
if(List3 == p) p = p->next;
else q = q->next;
List3->next = 0;
tail = List3;
}
else
{
Node* t = p->data > q->data ? p : q;
if(t == p) p = p->next;
else q = q->next;
tail->next = t;
tail = t;
}
}

//将剩余的直接接过去即可；
if(p == 0) tail->next = q;
else tail->next = p;
}

int main()
{
Node* List1 = 0, *List2 = 0, *List3 = 0;
Create(List1);
Create(List2);

Sort(List1);
Sort(List2);
cout << "两个递增序列如下：" << endl;
Print(List1);
Print(List2);

cout << "反转后的序列如下: " << endl;
Converse(List1);
Converse(List2);
Print(List1);
Print(List2);

Merge(List1, List2, List3);
cout << "合并结果如下：" << endl;
Print(List3);
system("pause");
return 0;
}

追问

谢谢你的热心回答哦，不过这个题目中并非是递增序列，而是“非递减序列”，嗯，就是在数列中错在两个数相等的情况。