首页 > 代码库 > 有序链表的合并

有序链表的合并

2024-08-03 19:31:53   219人阅读

/*
Name: 有序链表的合并 
Copyright: 
Author: 巧若拙 
Date: 22-11-14 16:13
Description: 
分别用递归和非递归两种方式实现两个有序链表（不含头结点）的合并
*/


#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>


typedef char ElemType;
typedef int Status; //函数类型，其值是函数结果状态代码，如OK等 


typedef struct Node{
ElemType data;//数据域 
struct Node *next;//指针域 
} Node, *LinkList;


void CreatList(LinkList *head);//创建一个不带头结点的单链表 
void DisplayList(LinkList head);//输出单链表的所有结点 
void SortList(LinkList *head);//选择排序法 
LinkList Merge_1(LinkList hA, LinkList hB);//合并有序链表（非递归） 
LinkList Merge_2(LinkList hA, LinkList hB);//合并有序链表（递归） 
int main(void)
{
    LinkList a = NULL;
    LinkList b = NULL;
    LinkList c = NULL;
    
    CreatList(&a);//创建一个不带头结点的单链表
    DisplayList(a);//输出单链表的所有结点 
    SortList(&a);//选择排序法
DisplayList(a);//输出单链表的所有结点 
 
    CreatList(&b);//创建一个不带头结点的单链表
    DisplayList(b);//输出单链表的所有结点 
    SortList(&b);//选择排序法
DisplayList(b);//输出单链表的所有结点 
    
    c = Merge_2(a, b);//合并有序链表 
    DisplayList(c);//输出单链表的所有结点 


    return 0;
}


void CreatList(LinkList *head)//创建一个不带头结点的单链表 
{
int i;
Node *p, *s;

//创建第一个结点  
*head = (LinkList)malloc(sizeof(Node));
if (!*head)
{
printf("Out of space!");
exit(0);
}
p = *head;
p->data = http://www.mamicode.com/rand()%26 + ‘A‘;
p->next = NULL;

for (i=1; i<5; i++)//创建其余的结点 
{
s = (LinkList)malloc(sizeof(Node));
if (!s)
{
printf("Out of space!");
exit(0);
}
s->data = http://www.mamicode.com/rand()%26 + ‘A‘;
s->next = NULL;
p->next = s;
p = p->next;
}
}


void DisplayList(LinkList head)//输出单链表的所有结点 
{
while (head)
{
printf("%c ", head->data);
head = head->next;
}
    printf("\n");
}


void SortList(LinkList *head)//选择排序法 
{
ElemType temp;
Node *p, *pre, *min;

for (min=pre=*head; pre->next; min=pre=pre->next)
{
for (p=pre->next; p; p=p->next)
{
if (p->data < min->data)
min = p;
}

if (min != pre)//交换数据域 
{
temp = min->data;
min->data = http://www.mamicode.com/pre->data;
pre->data = http://www.mamicode.com/temp;
}
}
}


LinkList Merge_1(LinkList hA, LinkList hB)//合并有序链表（非递归） 
{
Node *p, *head;

head = (LinkList)malloc(sizeof(Node)); //先设置一个头结点 
if (!head)
{
printf("Out of space!");
exit(0);
}

p = head;
while (hA && hB)
{
if (hA->data < hB->data)
{
p->next = hA;
p = hA;
hA = hA->next;
}
else
{
p->next = hB;
p = hB;
hB = hB->next;
}
}

p->next = hA ? hA : hB;
p = head->next; //删除头结点 
free(head); 

return p;
}


LinkList Merge_2(LinkList hA, LinkList hB)//合并有序链表（递归） 
{
if (!hA)
return hB;
else if (!hB)
return hA;

if (hA->data < hB->data)
{
hA->next = Merge_2(hA->next, hB);
return hA;
}
else
{
hB->next = Merge_2(hB->next, hA);
return hB;
}
}

有序链表的合并


联系
我们