設計演算法實現單鏈表歸並

Ⅰ 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;
}