原文題是嚴蔚敏同志的數(shù)據(jù)結(jié)構(gòu)習(xí)題中第二章線性表中提出的問題。
原問如下：
2.24 假設(shè)有兩個按元素值遞增有序排列的線性表A和B，均以單鏈表作存儲結(jié)構(gòu)，請編寫算法將A表與B表歸并成一個按元素值遞減有序(即非遞增有序，允許表中含有值相同的元表)排列的線性表C，并要求利用原表(即A表與B表)的結(jié)點空間構(gòu)造C表。
分析：對兩個或兩個以上，結(jié)點按元素值遞增/減排列的單鏈表進行操作時，應(yīng)采用"指針平行移動、一次掃描完成"的策略。且鏈表A與鏈表B的長度大小不一定相等。
代碼：
#include<iostream>
using namespace std;
typedef int ElemType;
//兩個遞增的鏈表合并成遞增的鏈表。
typedef struct LNode
{
ElemType data;
struct LNode *next;
}
LNode;
typedef LNode *LinkList;
void CreatList(LinkList &L,int n)
{
LinkList p,q;
L=new LNode;
L->next=NULL;
q=L;
cout<<"請從小到大輸入鏈表的元素：";
for (int i=1;i<=n;i++)
{
p=new LNode;
cin>>p->data;
p->next=q->next;
q->next=p;
q=q->next;
}
cout<<"所創(chuàng)建得的遞增有序鏈表為：";
p=L->next;
for (int j=1;j<=n;j++)
{
cout<<p->data<<" ";
p=p->next;
}
cout<<endl;
}
void CreatC(LinkList &A,LinkList &B,LinkList &C,int n)
{
LinkList pa,pb,pc,pre=NULL/**//*C結(jié)點的上一個結(jié)點*/,q/**//*t*/;
pa=A->next;
pb=B->next;
// C=t=A;// A
while (pa||pb)
{
if (!pb||((pa&&pb)&&(pa->data<pb->data)))
{
/**/////將A的元素插入新表
pc=pa;
q=pa->next;
pa->next=pre;
pa=q;
}
else
{
pc=pb;
q=pb->next;
pb->next=pre;
pb=q; //將B的元素插入新表
}
pre=pc;
}
cout<<"合并后的遞減有序鏈表為：";
C=A;
A->next=pc;
pa=pc;
for (int j=1;j<=n;j++)
{
cout<<pa->data<<" ";
pa=pa->next;
}
cout<<endl;
getchar();
}
void main()
{
LinkList A,B,C;
int n,m,k;
cout<<"請輸入鏈表***A***的長度：";
cin>>n;
CreatList(A,n);
cout<<"請輸入鏈表***B***的長度：";
cin>>m;
CreatList(B,m);
k=m+n;
CreatC(A,B,C,k);
system(0);
getchar();
}