有序表的合并：
- 已知线性表La和Lb中的元素按值非递减有序排列
- 现要求将La和Lb归并为一个新的线性表Lc
- 且Lc中的数据元素仍按值非递减有序排列
一、顺序表实现
#include<iostream>
using namespace std;
#define MAXSIZE 100 //定义最大存储空间
//顺序表的定义
struct SqList
{
int* Elme; //动态数组
int Length; //元素个数
};
//初始化
bool initList_Sq(SqList& L)
{
L.Elme = new int[MAXSIZE]; //为顺序表分配空间
if (!L.Elme)
{
exit(0); //分配失败退出系统
}
L.Length = 0; //空表长度为0
return true; //分配成功返回1
}
//插入
bool Listinsert_Sq(SqList& L, int i, int e)
{
if (i < 1 || i > L.Length + 1) //判断输入的i释放合法
{
return false;
}
if (L.Length == MAXSIZE) //判断空间是否已满
{
return false;
}
for (int j = L.Length - 1; j >= i - 1; j--)
{
L.Elme[j + 1] = L.Elme[j]; //将插入位置及之后的元素后移
}
L.Elme[i - 1] = e; //将元素e放入位置i
L.Length++; //表长加一
return true;
}
//遍历
void ListPrint_Sq(SqList L)
{
for (int j = 0; j < L.Length; j++)
{
cout << L.Elme[j] << " ";
}
cout << endl;
}
//线性表有序表的合并
void MergeList_Sq(SqList La, SqList Lb, SqList& Lc)
{
//指针pa,pb,pc的初值分别指向两个表的第一个元素
int* pa = La.Elme;
int* pb = Lb.Elme;
Lc.Length = La.Length + Lb.Length; //新表长度等于两表之和
Lc.Elme = new int[Lc.Length]; //为新表分配存储空间
int* pc = Lc.Elme;
//pa_last、pb_last分别指向表中最后一个元素
int *pa_last = &La.Elme[La.Length - 1];
int* pb_last = &Lb.Elme[Lb.Length - 1];
//判断两表是否为空，或当其中一表摘取完，则停止循环
while (pa <= pa_last && pb <= pb_last)
{
if (*pa <= *pb) //依次摘取两表中值较小的结点
{
*pc++ = *pa++;
}
else
{
*pc++ = *pb++;
}
}
//如果条件为真，表明Lb表已经到达表尾，将La中剩余元素加入Lc
while (pa <= pa_last)
{
*pc++ = *pa++;
}
//如果条件为真，表明La表已经到达表尾，将Lb中剩余元素加入Lc
while (pb <= pb_last)
{
*pc++ = *pb++;
}
}
int main()
{
SqList La; //创建线性表La
initList_Sq(La); //初始化
//创建数组并把数组中元素插入到La中
int arr1[3] = { 1,7,8 };
for (int i = 1; i <= 3; i++)
{
Listinsert_Sq(La, i, arr1[i - 1]);
}
cout << "合并前La中元素：" << endl;
ListPrint_Sq(La); //遍历La
SqList Lb;//创建线性表Lb
initList_Sq(Lb); //初始化
//创建数组并把数组中元素插入到Lb中
int arr2[6] = { 2,4,6,8,10,11 };
for (int i = 1; i <= 6; i++)
{
Listinsert_Sq(Lb, i, arr2[i - 1]);
}
cout << "合并前Lb中元素：" << endl;
ListPrint_Sq(Lb); //遍历La
SqList Lc;
MergeList_Sq(La, Lb, Lc); //合并La、Lb到Lc中
cout << "合并后Lc中元素：" << endl;
ListPrint_Sq(Lc); //遍历Lc
system("pause");
return 0;
}
二、链表表实现
#include<iostream>
using namespace std;
//结点
struct Lnode
{
int Data; //数据域
Lnode* Next; //指针域
};
typedef Lnode* LinkList; //将LinkList定义为Lnode*类型
//初始化
void Listinit_L(LinkList& L)
{
L = new Lnode;
L->Next = NULL;
}
//插入
bool Listinsert_L(LinkList& L, int i, int e)
{
Lnode* p = L;
int j = 0;
while (p && j < i - 1) //利用循环找到i-1的结点
{
p = p->Next;
++j;
}
if (!(p) || j > i - 1)//判断输入的i是否合法
{
return false;
}
else
{
Lnode* s = new Lnode; //创建新结点s
s->Data = e; //将输入的元素e存入s的数据域
s->Next = p->Next; //s指向第i个结点
p->Next = s; //i-1结点指向s地址
return true;
}
}
//打印
void ListPrint_L(LinkList L)
{
Lnode* p = L->Next; //p指向第一个元素
while (p)
{
cout << p->Data << " ";
p = p->Next;
}
cout << endl;
}
//有序表的合并
void MergeList_L(LinkList La, LinkList Lb, LinkList& Lc)
{
Lnode* pa = La->Next;//pa指向La中第一个元素
Lnode* pb = Lb->Next;//pb指向Lb中第一个元素
Lnode* pc = Lc = La;//使用La的头结点作为Lc的头结点
while (pa && pb) //pa或pb为空时停止循环
{
//判断pa的值是否小于等于pb的值，为真插入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; //利用三目运算插入pa或pb中剩余内容
delete Lb; //释放Lb头结点
}
int main()
{
//1.创建单链表La
LinkList La;
Listinit_L(La); //初始话
//将数组中的数据插入La
int arr1[3] = { 1,7,8 };
for (int i = 1; i <= 3; i++)
{
Listinsert_L(La, i, arr1[i-1]);
}
cout << "合并前La中的数据为：" << endl;
ListPrint_L(La);
//2.创建单链表Lb
LinkList Lb;
Listinit_L(Lb); //初始话
//将数组中的数据插入Lb
int arr2[6] = {2,4,6,8,10,11};
for (int i = 1; i <= 6; i++)
{
Listinsert_L(Lb, i, arr2[i - 1]);
}
cout << "合并前Lb中的数据为：" << endl;
ListPrint_L(Lb);
//3.创建Lc，将La与Lb中的值合并到Lc
LinkList Lc;
MergeList_L(La, Lb, Lc);
cout << "合并后Lc的值为：" << endl;
ListPrint_L(Lc);
system("pause");
return 0;
}
三、最终结果
总结
以上为个人经验，希望能给大家一个参考，也希望大家多多支持。
