设计算法实现单链表归并

Ⅰ C语言单链表合并

Ⅱ 将两个单链表合并为一个单链表

对应这个问题的算法：
voidMergeList(LinkListLa,LinkList&Lb,LinkList&Lc)
{

LinkListpa=La->next,pb=Lb->next,pc;
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);
Lb=NULL;
}
需要全部程序的话私信我

Ⅲ 已知有两个带头的结点的循环单链表LA、LB,编写一个算法，将两个循环单链表合并为一个循环单链表

已知带有头结点的两个单链表 la 和 lb 都是非递增有序序列。

编写好的算法实现将这两个链表合并为新的带有头结点的链表 lc ，使得 lc 的元素仍然是非递增有序排列的序列，如果遇到 la 与 lb 中元素相同，则只取 la 中的元素，去掉 lb 中的元素。已知 la 的元素个数 为 m ， lb 的元素个数为 n。

循环单链表是单链表的另一种形式，其结构特点链表中最后一个结点的指针域不再是结束标记，而是指向整个链表的第一个结点，从而使链表形成一个环。和单链表相同，循环链表也有带头结点结构和不带头结点结构两种，带头结点的循环单链表实现插入和删除操作较为方便。

Ⅳ 编写算法将两个递增单链表合并成一个递减的线性表

/*将两个递增单链表合并成一个递减单链表*/

/*

算法思想：两个链表已经按元素值递增次序排序，将其合并时，均从第一个结点起进行比较，将较小的

结点链入链表中，同时后移工作指针。由于结果链表是递减的，故使用头插法建立新链表。比较结束后，

可能会有一个链表非空，此时用头插法将剩下的结点依次插入新链表中即可。

*/

void Union_List(LinkList& La,LinkList& Lb)

{

LNode *r, *pa = La->next, *pb = Lb->next; //pa,pb分别是La,Lb的工作指针

La->next = NULL; //将La作为结果链表的头指针

while (pa&&pb)

{

if (pa->data <= pb->data)

{

r = pa->next; //r暂存pa的后继结点指针

pa->next = La->next; //头插法插入pa所指结点

La->next = pa;

pa = r;

}

else

{

r = pb->next;

pb->next = La->next;

La->next = pb;

pb = r;

}

}

while (pa) //处理剩下的结点

{

r = pa->next;

pa->next = La->next;

La->next = pa;

pa = r;

}

while (pb)

{

r = pb->next;

pb->next = La->next;

La->next = pb;

pb = r;

}

free(Lb);

}

Ⅳ 假设有两个按元素值递增次序排列的线性表，均以单链表形式存储。请编写算法将这两个单链表归并为一个按元

#include "stdafx.h"
#include "iostream"
using namespace std;

struct Node

{

int num

Node *next

};

Node* Create() //
创建单链表

{

int n=0;

Node *p1,*p2,*head;

p1=p2=new Node;

head=NULL;

while (p1->num!=0)

{

if (n==1)

{

head=p1;

}

else

p2->next=p1;

p2=p1;

p1=new Node;

cin>>p1->num;

if(p1->num<=p2->num&&p1->num!=0)

{

cout<<"
重新输入按递增排序的单链表
:\n";

cin>>p1->num;

}

n++;

}

p2->next=NULL;

return head;

}

void Print(Node *head) //
输出链表

{

Node* p=head;

while (p)

{

cout<<p->num<<" "; p=p->next;

}

cout<<endl;

}

Node *ReverseList(Node *head) //
单链表的逆转

{

Node *p,*q,*r;

p=head;

q=p->next;

while (q)

{

r=q->next;

q->next=p;

p=q;

q=r;

}

head->next=NULL;

head=p;

return head;
}

Node *MergeList(Node *head1,Node *head2) //
合并单链表，降序

{

if(head1==NULL)

return head2;

if(head2==NULL)

return head1;

Node *head;

if(head1->num>=head2->num)

{

head=head1;

head1=head1->next;

}

else

{

head=head2;

head2=head2->next;

}

Node *temp=head;

while ( head1 != NULL && head2 != NULL)

{

if ( head1->num >= head2->num )

{

temp->next = head1

head1 = head1->next

temp =temp->next;

}

else

{

temp->next = head2;

head2 = head2->next

temp =temp->next;

}

}

if (head1 == NULL)

temp->next = head2;

if (head2 == NULL)

temp->next = head1;

return head;
}

int Count(Node *head)//
求表长

{

Node* p=head;

int i=0;

while (p)

{

i++;

p=p->next;

}

return i;
}

int main(int argc, char* argv[])
{

Node *p1,*p2;

p1,p2=new Node;

cout<<"
创建单链表
1,
递增排序
,0
作为结束符！
\n";

p1=Create();

cout<<"
单链表
1
为
\n";

Print(p1);

cout<<"*********************************************\n";

cout<<"
创建单链表
2
，递增排序，
0
作为结束符！
\n";

p2=Create();

cout<<"
单链表
2
为：
\n";

Print(p2);

cout<<"*********************************************\n";

cout<<"
合并单链表为（降序排列）
：
\n";

Node *p3;

p3=MergeList(ReverseList(p1),ReverseList(p2));

Print(p3);

cout<<"
合并单链表表长为
:"<<Count(p3)<<endl;

system("pause");

return 0；

Ⅵ 如何用c语言实现两个单链表的归并

函数名、变量名出现了一些C语言的关键字，这是不允许的（比如将union作为函数名）

Ⅶ 设计链表合并算法，将两个已排序（升序）的单链表，合并成一个链表而不改变其有序性。用c语言编写。

#include <stdio.h>
#include <malloc.h>
typedef struct node
{
int data;
struct node *next;
}List;
List *create(List *head,int n)//创建链表
{
List *p,*q;
q=(List *)malloc(sizeof(List));
q->data=n;
q->next=NULL;
p=head;
while(p->next!=NULL)p=p->next;
p->next=q;
return head;
}
void print(List *head)//输出链表
{
List *p;
p=head->next;
while(p!=NULL)
{
printf("%d ",p->data);
p=p->next;
}
}
List *LINK(List *head1,List *head2)//连接链表
{
List *p;
p=head1;
while(p->next!=NULL)p=p->next;
p->next=head2->next;
return head1;
}
main()
{
int i;
List *head1,*head2,*link1;
head1=(List *)malloc(sizeof(List));
head1->next=NULL;
head2=(List *)malloc(sizeof(List));
head2->next=NULL;
for(i=1;i<=5;i++)head1=create(head1,i);//输入链表1
printf("链表1:\n");
print(head1);
printf("\n链表2:\n");
for(i=6;i<=10;i++)head2=create(head2,i);//输入链表2
print(head2);
link1=LINK(head1,head2);
printf("\n连接后的链表:\n");
print(link1);
}

Ⅷ 求一个单链表归并排序算法，C语言的源代码，急需！

//MergeSort.cpp

#include <iostream.h>
#include <conio.h>
#define MAXSIZE 20
#define LENGTH 7
typedef int RedType;

typedef struct //SqList structure
{ RedType r[MAXSIZE+1]; //Records Type
int length;
}SqList;
typedef SqList RcdType;

void Merge(RcdType SR,RcdType &TR,int i,int m,int n) //Merge() function
{ int j,k;
for(j=m+1,k=i;i<=m&&j<=n;++k)
{ if(SR.r[i]<=SR.r[j])
TR.r[k]=SR.r[i++];
else
TR.r[k]=SR.r[j++];
}
while(i<=m)
TR.r[k++]=SR.r[i++];
while(j<=n)
TR.r[k++]=SR.r[j++];
}//end of Merge() function

void MSort(RcdType SR,RcdType &TR1,int s, int t) //MSort() function
{ int m;
RcdType TR2;//[LENGTH];
if(s==t)
TR1.r[s]=SR.r[t];
else
{ m=(s+t)/2;
MSort(SR,TR2,s,m);
MSort(SR,TR2,m+1,t);
Merge(TR2,TR1,s,m,t);
}//end of else
}//end of MSort() function

void MergeSort(SqList &L) //MergeSort() function
{
MSort(L,L,1,L.length);
}//end of MergeSort() function

void main() //main function
{ int i;
SqList L;//={{0,49,38,65,97,76,13,27,},LENGTH};
cout<<"MergeSort.cpp"<<endl<<"============="<<endl<<endl;
cout<<"Please input the length of SqList L: <eg. 7> ";
cin>>L.length;

cout<<"Please input the disordered array L.r: <eg. {49,38,65,97,76,13,27,...}>"<<endl;
for(i=1;i<=L.length;i++)
cin>>L.r[i];
MergeSort(L);
cout<<endl<<"The sorted array L.r: ";
for(i=1;i<=L.length;i++)
cout<<L.r[i]<<" ";
cout<<endl;
cout<<"...OK!..."<<endl;
getch();
}//end of main() function我以前的，可以调试的
应该符合你要求，只是很少部分你自己改一下，比如数的个数
输入改为 rand()随即输入,刚才粘贴错了

Ⅸ 使用java设计算法，完成将两个有序递增的单链表合并为一个有序递增的单链表，重复的元素只出现一次。

type
point=^node;
node=record
data:integer;
next:point;
end;
var h1,h2,h:point;
procere prt(p:point); //打印链表
begin
p:=p^.next;
while p<>nil do
begin
write(p^.data,' ');
p:=p^.next;
end;
writeln;
end;
procere creat(var h:point); //建立链表
var x:integer; p,q:^node;
begin
writeln('请输入升序的数，负数结束：');
new(h);
p:=h;
read(x);
while(x>=0)do
begin
new(q);
q^.data:=x;
p^.next:=q;
p:=q;
read(x);
end;
p^.next:=nil;
end;

function merge_link(var p,q:point):point; //升序合并二个升序链表
var h,w:^node;
begin
w:=p; p:=p^.next; dispose(w); //回收一个头结点，p指向首个数据结点
w:=q; h:=q; q:=q^.next; //h:合并后的头结点，q指向首个数据结点
while (p<>nil)and(q<>nil) do //当二个链表都不空时
if(p^.data<q^.data) then //选一个小的结点
begin
w^.next:=p; //把小结点链入
p:=p^.next; //跳过此结点
w:=w^.next; //w指向当前合并后链表的尾结点
end
else
begin //下面三行作用同上
w^.next:=q;
q:=q^.next;
w:=w^.next;
end;
if p<>nil then w^.next:=p; //将未完的链表接入
if q<>nil then w^.next:=q; //将未完的链表接入
merge_link:=h; //返回合并后的链表头指针
end;
begin
creat(h1);
creat(h2);
h:=merge_link(h1,h2);
writeln('合并后的链表：');
prt(h);

Ⅹ 如何将两个递增单链表合并为一个递减单链表，并保留原有节点。求大神给出算法并注释，菜鸟诚心想学习。

/*采用方法：随机创建两个整型数组，再把它们分别按升序排列，然后用数组元素创建两个链表（升序）list1和list2。然后按要求进行合并。最后输出合并结果，销毁链表*/
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
typedef int ElemType;
typedef struct LNode
{ ElemType data;
struct LNode *next;
}NODE,*PNODE, *LinkList;

/*比较函数，用于qsort排序时回调*/
int CompareInt(const void *s1, const void *s2)
{
int x= *(int *)s1;
int y= *(int *)s2;
return(x-y);
}
/*根据数组x中的n个元素排序后创建*/
LinkList CreateLst(int x[], int n)
{
if(x==NULL || n<=0) return NULL;
qsort((void *)x, n, sizeof(int), CompareInt);/*按升序排列数组x的元素*/
int i=n;
PNODE p, head=NULL;
while(i--)
{
p = (NODE *)calloc(1, sizeof(NODE));
p->data = x[i];
if(head==NULL)
{
head = p;
p->next = NULL;
}
else
{
p->next = head;
head = p; //头插法创建链表
}
}
return head;
}
/*销毁链表*/
void DestroyList(LinkList list)
{
if(list == NULL) return;
NODE * p=list;
while(list != NULL)
{
list = list->next;
free(p);
p = list;
}
}
/*打印链表*/
void printList(LinkList list)
{
while(list!=NULL)
{
printf("%d ", list->data);
list = list->next;
}
printf("\n");
return;
}
/*交换两个链表的指针指向，使得list指向的链表表头结点*/
void swapList(LinkList * plist1, LinkList * plist2)
{
if((plist1 == NULL) || (plist2 == NULL)) return ;
LinkList r1 = *plist1;
LinkList r2 = *plist2;
LinkList temp;
if(r1->data >=r2->data)
{
temp = *plist1;
*plist1 = *plist2;
*plist2 = temp;
}

}
/*合并递增链表为递减单链表并保留结点（不用创建新结点）*/
LinkList joinLists(LinkList list1, LinkList list2)
{
LinkList list3, p;

swapList(&list1, &list2);/*交换后list1指向的链表结点值不大于list2指向的链表结点值*/

list3 = list1;
list1 = list1->next;
list3->next = NULL;

while(list1!=NULL && list2 !=NULL)
{
while(list1!=NULL && (list1->data <= list2->data))
{
p = list1;
list1 = list1->next;
p->next = list3;
list3 = p;//采用头插法
}
if(list1 == NULL ) break;
swapList(&list1, &list2);/*交换后list1指向的链表结点值不大于list2指向的链表结点值*/
}
/*把某一个没用完的结点用头插法插入结果链表*/
if(list2 == NULL)
{
while(list1 != NULL)
{
p = list1;
list1 = list1->next;
p->next = list3;
list3 = p;//采用头插法
}
}else if(list1 == NULL)
{
while(list2 != NULL)
{
p = list2;
list2 = list2->next;
p->next = list3;
list3 = p;//采用头插法
}
}

return list3;
}
#define M 2
#define N 4
int main()
{

int x[M], y[N];
int i=0;
LinkList list1, list2, joined;
srand(time(NULL));
while(i<M)
{
x[i++] = rand()%100;
}

i=0;
while(i<N)
{
y[i++] = rand()%100;
}
list1 = CreateLst( x, M );
list2 = CreateLst( y, N );
printf("链表1数据:\n");
printList(list1);
printf("链表2数据:\n");
printList(list2);

joined = joinLists(list1, list2);
printf("合并链表数据:\n");
printList(joined);

DestroyList(joined);
return 0;
}