一、问题描述

线性表合并是程序设计语言编译中的一个最基本的问题，现在有两个线性表LA和LB，其中的元素都是按照非递减有序排列的，要将两个LA和LB归并为一个新的线性表LC，使得LC中的元素仍然是非递减有序的。

本实验的合并方式有两种。第一种是分别取LA和LB的第一个元素，即各自的最小的元素进行比较，选择较小的元素加入LC尾部，然后重复以上步骤；当LA表空了或者LB表空了的时候，将另一个表剩下的元素按照顺序加入LC的尾部，从而保证LC中元素有序。第二种方式是以LA为母表，将LB中的元素向LA中插入，直到LB表空，得到的新的LA表就是最终需要的LC表。

本实验采用线性表实现，采用了链式表示和顺序表示两种实现方式。根据各自的特点，链式表示对应了第二种合并方式，而顺序表示对应了第一种合并方式。

二、数据结构——线性表

1. 链式表示

链式表示的特点是用一组任意的存储单元存储线性表的数据元素，每个元素包括两个域——数据域和指针域。其中数据域是存储数据信息的域，本实验中默认所处理的数据元素都是在整型（int）范围内的数据；指针域中存储一个指针，指向当前元素的下一个元素的地址。n个结点按照如上关系连接起来，形成一个链表，就是线性表的链式表示。

由于链式表示对于数据的插入、删除操作比较方便，而查找一个元素的效率比较低下，于是选择用第二种合并方式，即以LA为母表，将LB中的元素一个一个插入LA中。

首先，每个结点的是一个node型的变量，包含一个int型变量Num和一个node*型的指针变量next。正如上文所描述，Num保存该结点的数值，next保存逻辑上下一个结点的地址。然后定义了一个名叫MyList的类，其中有private型的变量包含线性表自身的基本变量，比如元素个数、首地址等等；还包括public型的线性表的基本操作函数，比如初始化（InitList）、清除（ClearList）、打印(PrintList)等等。

2. 顺序表示

顺序表示是指的用一段地址连续的区域存储一个线性表，用物理存储位置的连续表示线性表的顺序关系。这就要求元素之间维持严格的物理位置关系，在访问变得简单的同时，对线性表的修改操作给线性表的维护带来了很大的麻烦。

由于顺序表示对于数据的操作比较方便，而对线性表的数据进行操作比较麻烦且效率低下，故选择第一种合并方式，即将LA和LB合并到一个新的线性表LC中。

首先，申请一段连续的空间，当空间不够时申请一个更大的空间，再把之前的数据搬过去。基本功能与链式表示基本相同，实现上略有差别。

三、算法的设计和实现

1. 第一种合并方式

（1）建立线性表LA和LB，并读入数据。

（2）建立空线性表LC。

（3）分别选取LA中未读过的最小的元素和LB中未读过的最小的元素，进行比较，将较小的元素加入新的线性表LC中，较大元素视作未读过的元素。

（4）重复步骤（2）直到LA或者LB的元素都被读过了。若LA中的元素都被度过了，则将LB中剩下未读的元素按顺序依次添加到LC的尾部；否则，将LA中的剩下未读的元素按顺序依次添加到LC的尾部。

（5）得到的LC就是最终结果。

2. 第二种合并方式

（1）建立线性表LA和LB，并读入数据。

（2）用aIndex标记LA中读到元素的位置，将其位置的元素与LB中第一个元素进行比较。

（3）若LA中当前元素较小，则aIndex向后移，重复（2）直到LB为空或者LA到末端；否则将LB中的第一个元素插入LA的当前位置，aIndex向后移，删除LB中的第一个元素，重复（2）直到LB为空或者LA到末端。

（4）若LB为空，则LA已经是最终结果；否则，将LB剩下的元素按顺序依次加入LA的末端，得到最终结果。

四、代码示例

本节我以顺序表实现为例，链表实现留给大家当作课后作业。

#include<iostream>

#define maxsize 100

using namespace std;

//定义顺序表 
typedef struct 
{
	int *elem;
	int length;
}list;

//创建顺序表
void cj(list &L)
{
	L.elem=new int[maxsize];
	L.length=0;
} 

//输入顺序表的数据
void sr(list &L,int &n)
{
	int i;
	cout<<"请输入"<<n<<"个数："<<endl;
	for(i=0;i<n;i++)
	{
		cin>>L.elem[i];
	}
	L.length=n;
 } 
 
 //求顺序表的长度
 int cd(list &L)
 {
 	return L.length; 
  } 
  
//求顺序表的第i个元素,并以e返回 
void cz(list &L,int i,int &e)
{
	e=L.elem[i-1];
 }
 
//判断list里有没有e这个元素
bool pd(list &L,int &e)
{
	int i;
	for(i=0;i<L.length;i++)
	{
		if(e==L.elem[i])
		  return true; 
		  else
		  return false;
	}
	
 } 
 
//将e 插入到list的最后
void  cdzh(list &L,int &e)
{
	L.elem[L.length]=e;
	L.length++;
}

//输出list
void sc(list &L)
{
	int i;
	for(i=0;i<L.length;i++)
	{
		cout<<L.elem[i]<<" ";
	}
	cout<<endl;
 } 
 
//线性表的合并（顺序表）
void hb(list &A,list &B)
{
	int len_A,len_B,i,e;
	len_A=cd(A);
	len_B=cd(B);
	for(i=1;i<=len_B;i++)
	{
		cz(B,i,e);
		if(!pd(A,e))
		{
			cdzh(A,e);
		}
	}
 } 
 
int main()
{
	list A,B;
	int n,m;
	cj(A);cj(B);
	
	cout<<"请输入线性表A的元素个数：";
	cin>>n;
	sr(A,n);
	
	cout<<endl<<"请输入线性表B的元素个数：";
	cin>>m;
	sr(B,m);
	
	hb(A,B);
	cout<<"A和B合并后的集合为："<<endl;
	sc(A);
	return 0;  
}

最后

以上就是火星上芹菜为你收集整理的线性表的合并（顺序表实现）一、问题描述二、数据结构——线性表三、算法的设计和实现四、代码示例的全部内容，希望文章能够帮你解决线性表的合并（顺序表实现）一、问题描述二、数据结构——线性表三、算法的设计和实现四、代码示例所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。