一、问题描述
假设头指针为LA和LB的单链表分别为线性表LA和LB的存储结构，现要归并LA和LB得到单链表LC。
二、问题分析
需设立3个指针pa、pb和pc，其中pa和pb分别指向LA和LB中当前待比较插入的结点，而pc指向LC中当前最后一个结点(LC的表头结点设为LA的表头结点)。通过比较指针pa和pb所指向的元素的值，依次从LA或LB中"摘取"元素值较小的结点插入到LC的最后，当其中一个表变空时，只要将另一表的剩余段链接在pc所指结点之后即可。
三、算法步骤
1.指针pa和pb初始化，分别指向LA和LB的第一个结点。
2.LC的结点取值为LA的头结点。
3.指针pc初始化，指向LC的头结点。
4.当指针pa和pb均未到达相应表尾时，则依次比较pa和pb所指向的元素值，从LA或LB中"摘取"元素值较小的结点插入到LC的最后。
5.将非空表的剩余段插入到pc所指结点之后。
6.释放LB的头结点。
四、算法描述
实现代码
//******************************链式有序表的合并******************************//
#include <stdio.h>
#include <iostream>
#define OK 1
#define ERROR 0
using namespace std;
typedef int Status;
//定义单链表的结构类型
typedef int ElemType;
//------单链表的存储结构-----//
typedef struct LNode
{
ElemType data; //结点的数据域
struct LNode *next; //结点的指针域，指向下一个指针
}LNode,*LinkList; // LNode是结点，LinkList是链表，LinkList为指向结构体LNode的指针类型
//------单链表的初始化-----//
//【算法步骤】//
//1.生成新结点作为头结点，用头指针L指向头结点。
//2.头结点的指针域置空。
Status InitList(LinkList &L)
{
//构造一个空的单链表L
L=new LNode; //生成新结点作为头结点，用头指针L指向头结点 或L=(LinkList)malloc(sizeof(LNode))
L->next=NULL; //头结点的指针域置空
return OK;
}
//------后插法创建单链表-----//
//【算法步骤】//
//1.创建一个只有头结点的空链表。
//2.尾指针r初始化，指向头结点。
//3.根据创建链表包括的元素个数n,循环n次执行以下操作：
//生成一个新结点*P；
//输入元素值赋给新结点*p的数据域；
//将新结点*p插入到尾结点*r之后；
//尾指针r指向新的尾结点*p。
void CreateList_R(LinkList &L,int n)
{
//正位序输入n个元素的值，建立带表头结点的单链表L
L=new LNode; //或L=(LinkList)malloc(sizeof(LNode))
L->next=NULL; //先建立一个带头结点的空链表
LinkList r=L; //尾指针r指向头结点
for(int i=0;i<n;++i)
{
LinkList p=new LNode; //生成新结点*p
cin>>p->data; //输入元素值赋给新结点*p的数据域
p->next=NULL;
r->next=p; //将新结点*p插入到尾结点*r之后
r=p; //r指向新的尾结点*p
}
}
//------单链表的插入-----//
//【算法步骤】//
//将值为e的新结点插入到表的第i个结点的位置上，即插入到结点ai-1与ai之间，具体插入过程如图所示，步骤如下：
//1.查找结点ai-1并由指针p指向该结点。
//2.生成一个新结点*s。
//3.将新结点*s的数据域置为e。
//4.将新结点*s的指针域指向结点ai。
//5.将结点*p的指针域指向新结点*s。
Status ListInsert(LinkList &L,int i,ElemType e)
{
//在带头结点的单链表L中第i个位置插入值为e的新结点
LinkList p=L;
int j=0;
while(p && (j<i-1))
{
p=p->next; //查找第i-1个结点，p指向该结点
++j;
}
if(!p||j>i-1) return ERROR; //i>n+1或者i<1
LinkList s=new LNode; //生成新结点*s
s->data=e; //将结点*s的数据域置为e
s->next=p->next;//将结点*s的指针域指向结点ai
p->next=s; //将结点*p的指针域指向结点*s
return OK;
}
//------链式有序表的合并-----//
//【算法步骤】//
//1.指针pa和pb初始化，分别指向LA和LB的第一个结点。
//2.LC的结点取值为LA的头结点。
//3.指针pc初始化，指向LC的头结点。
//4.当指针pa和pb均未到达相应表尾时，则依次比较pa和pb所指向的元素值，从LA或LB中"摘取"元素值较小的结点插入到LC的最后。
//5.将非空表的剩余段插入到pc所指结点之后。
//6.释放LB的头结点。
void MergeList_L(LinkList &LA,LinkList &LB,LinkList &LC)
{
//已知单链表LA和LB的元素按值非递减排列
//归并LA和LB得到新的单链表LC,LC的元素也按值非递减排列
LinkList pa=LA->next; LinkList pb=LB->next; //pa和pb的初值分别指向两个表的第一个结点
LC=LA; //用LA的头结点作为LC的头结点
LinkList pc=LC; //pc的初值指向LC的头结点
while(pa&&pb)
{
//LA和LB均未到达表尾，依次"摘取"两表中值较小的结点插入到LC的最后
if(pa->data<=pb->data) //"摘取"pa所指结点
{
pc->next=pa; //将pa所指结点链接到pc所指结点之后
pc=pa; //pc指向pa
pa=pa->next; //pa指向下一个结点
}
else
{
pc->next=pb; //将pb所指结点链接到pc所指结点之后
pc=pb; //pc指向pb
pb=pb->next; //pb指向下一个结点
}
}
pc->next=pa?pa:pb;
delete LB;
}
//------单链表的简单选择排序算法-----//
void LinkedListSelectSort(LinkList L)
{
//工作指针，min指向最小结点，p指向当前结点，q为工作指针，用于每轮的遍历
int temp;
for(LinkList p=L->next;p!=NULL;p=p->next)
{
LinkList min=p; //每一轮最小结点指向当前结点
LinkList q=p->next; //从当前结点的下一节点开始比较
while(q)
{
if(q->data<min->data)
{
//如果工作结点比最小值还小
min=q;
}
q=q->next;
}
temp=p->data;
p->data=min->data;
min->data=temp;
}
}
//------打印单链表函数-----//
void PrintList(LinkList L)
{
printf("当前单链表中所有元素为：");
LinkList p=L->next;
if(p==NULL) return;
else
{
while(p!=NULL)
{
if(p->next==NULL)
{
printf("%d",p->data);
}
else
{
printf("%d->",p->data);
}
p=p->next;
}
}
printf("\n");
}
//------创建单链表函数------//
void CreateList_LA(LinkList &L)
{
int n;
printf("请输入要创建的单链表LA的长度：");
scanf("%d",&n);
printf("请依次输入%d个数（空格隔开）：",n);
CreateList_R(L,n);
printf("单链表LA创建成功！\n");
PrintList(L);
}
void CreateList_LB(LinkList &L)
{
int n;
printf("请输入要创建的单链表LB的长度：");
scanf("%d",&n);
printf("请输入依次输入%d个数（空格隔开）：",n);
CreateList_R(L,n);
printf("单链表LB创建成功！\n");
PrintList(L);
}
void CreateList_LC(LinkList &L)
{
int n;
printf("请输入要创建的单链表LC的长度：");
scanf("%d",&n);
printf("请输入依次输入%d个数（空格隔开）：",n);
CreateList_R(L,n);
printf("单链表LC创建成功！\n");
PrintList(L);
}
//------单链表插入函数------//
void InsertList(LinkList &L)
{
int i,e;
printf("请输入要插入的位置：");
scanf("%d",&i);
printf("请输入要在第%d个位置插入的数据元素：",i);
scanf("%d",&e);
bool flag=ListInsert(L,i,e);
if(flag)
{
printf("元素%d插入单链表成功！\n", e);
PrintList(L);
}
else
{
printf("元素%d插入单链表失败！\n",e);
}
}
//------单链表排序函数------//
void Sort(LinkList L)
{
LinkedListSelectSort(L);
printf("当前单链表排序后的数据元素为：\n");
PrintList(L);
}
//------单链表合并函数------//
void MergeList(LinkList LA,LinkList LB,LinkList LC)
{
MergeList_L(LA,LB,LC);
printf("LA和LB合并后得到LC的线性表中数据元素：\n");
PrintList(LC);
}
//------主函数-----//
int main()
{
int n;
LinkList LA,LB,LC;
InitList(LA);
InitList(LB);
InitList(LC);
CreateList_LA(LA);
Sort(LA);
CreateList_LB(LB);
Sort(LB);
MergeList(LA,LB,LC);
} 运行结果
请输入要创建的单链表LA的长度：3
请依次输入3个数（空格隔开）：6 3 9
单链表LA创建成功！
当前单链表中所有元素为：6->3->9
当前单链表排序后的数据元素为：
当前单链表中所有元素为：3->6->9
请输入要创建的单链表LB的长度：4
请输入依次输入4个数（空格隔开）：5 7 4 8
单链表LB创建成功！
当前单链表中所有元素为：5->7->4->8
当前单链表排序后的数据元素为：
当前单链表中所有元素为：4->5->7->8
LA和LB合并后得到LC的线性表中数据元素：
当前单链表中所有元素为：3->4->5->6->7->8->9
--------------------------------
Process exited after 20.44 seconds with return value 0
请按任意键继续. . .
五、算法分析文章来源：https://www.toymoban.com/news/detail-717332.html
算法的时间复杂度为O(m+n)，空间复杂度也为O(1)。文章来源地址https://www.toymoban.com/news/detail-717332.html
到了这里，关于链表有序表的合并的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
