c++将两个有序链表合并为一个有序链表

发布网友 发布时间：2022-04-22 06:24

我来回答

共3个回答

热心网友 时间：2022-04-24 04:22

#include<iostream>
#include<cstdlib>
#include<ctime>

using namespace std;

class Node
{
public:
Node()
{
next=NULL;
}
Node(int d):data(d)
{
next=NULL;
}
~Node()
{
if(next)
delete next;
}
int data;
Node *next;
};

class List
{
public:
List()
{
first=NULL;
}
~List()
{
delete first;
cout<<endl;
}
void InitList(int len,int min,int max)
{
int i,data;
Node *tail,*pnew;

data=rand()%(max-min+1)+min;
this->first=tail=new Node(data);
for(i=1;i<len;i++)
{
data=rand()%(max-min+1)+min;
pnew=new Node(data);
tail->next=pnew;
tail=pnew;
}
}
void OutputList() const
{
Node *p=first;

while(p)
{
cout<<p->data;
cout<<(p->next ? "->" : "\n");
p=p->next;
}
}
Node *first;
};

//将数组lists中的len个链表合并到lst中
//asc为true按升序合并，false按降序合并
//不要求lists中的各链表是有序的
//合并后，不会改变lists中的各原链表
void MergeList(List &lst,bool asc,List lists[],int len)
{
int i;
Node *p,*q,*pnext,*pnew=NULL;

lst.first=NULL;
for(i=0;i<len;i++)
{
pnext=lists[i].first;
while(pnext)
{
pnew=new Node();
pnew->next=NULL;
pnew->data=pnext->data;
if(!lst.first)
lst.first=pnew;
else
{
q=NULL;
p=lst.first;
while(p)
{
if((asc && pnew->data<p->data)||
(!asc && pnew->data>p->data))
{
pnew->next=p;
if(!q)
lst.first=pnew;
else
q->next=pnew;
break;
}
q=p;
p=p->next;
}
if(!p)
q->next=pnew;

}
pnext=pnext->next;
}
}
}

int main()
{
//链表节点可取的最小值，最大值，最小链表节点数量，最大链表节点数量
int const MinValue=1,MaxValue=1000,MinLen=2,MaxLen=25;
//最小链表数量，最大链表数量
int const MinListCount=2,MaxListCount=8;
List lst1,lst2,*lists;
int i,c,len;

srand(time(NULL));
c=rand()%(MaxListCount-MinListCount+1)+MinListCount;
lists=new List[c];
cout<<"合并前，各链表："<<endl;
for(i=0;i<c;i++)
{
len=rand()%(MaxLen-MinLen+1)+MinLen;
lists[i].InitList(len,MinValue,MaxValue);
cout<<"list "<<(i+1)<<endl;
lists[i].OutputList();
}
cout<<endl<<endl;
MergeList(lst1,true,lists,c);
MergeList(lst2,false,lists,c);
cout<<"合并后，各链表（不变）："<<endl;
for(i=0;i<c;i++)
{
cout<<"list "<<(i+1)<<"："<<endl;
lists[i].OutputList();
}
cout<<endl<<endl;
cout<<"按升序合并后："<<endl;
lst1.OutputList();
cout<<"按降序合并后："<<endl;
lst2.OutputList();
delete [] lists;
return 0;
}追答

热心网友 时间：2022-04-24 05:40

看着应该不难，多发一些代码。
好久没玩C++了

热心网友 时间：2022-04-24 07:15

你好