【数据结构】合并有序顺序表

#include<iostream>
using namespace std;
#define MaxSize  100
typedef int ElemType;
typedef struct {
	ElemType* elem;         // 顺序表的基地址
	int length;             // 顺序表的长度
}Sqlist;

/*******************************************************************************/
/*顺序表初始化*/
/*******************************************************************************/
bool InitList(Sqlist& L) {
	L.elem = new int[MaxSize];   // 为顺序表动态分配Maxsize个空间
	if (!L.elem) return false;   // 分配空间失败
	L.length = 0;
	return true;
}

/*******************************************************************************/
/*顺序表创建*/
/*******************************************************************************/
bool CreateList(Sqlist& L) {
	int x, i = 0;
	std::cout << "输入顺序表数据元素（输入-1结束）：" << std::endl;
	std::cin >> x;
	while (x != -1)              // 输入-1时结束
	{
		if (L.length == MaxSize) {
			std::cout << "顺序表已满";
			return false;
		}
		L.elem[i++] = x;              // 将数据存入第i个位置
		L.length++;                   // 顺序表长度加1
		std::cin >> x;                // 输入一个数据元素
	}
	return true;
}

/*******************************************************************************/
/*顺序表遍历*/
/*******************************************************************************/
bool ListTraverse(Sqlist& L) {
	if (L.length == 0) return false;
	for (int i = 0; i < L.length; i++) {
		std::cout << L.elem[i] << " ";
	}
	std::cout << std::endl;
	return true;
}

/*有序顺序表的合并*/
void MergeSqlist(Sqlist La, Sqlist Lb, Sqlist& Lc) {
	int i, j, k;
	i = j = k = 0;
	Lc.length = La.length + Lb.length;//新表长度
	Lc.elem = new int[Lc.length];
	while (i<La.length&&j<Lb.length)  // 两表都非空
	{
		if (La.elem[i] < Lb.elem[j]) {
			Lc.elem[k++] = La.elem[i++];
		}
		else
		{
			Lc.elem[k++] = Lb.elem[j++];
		}
	}
	while (j<Lb.length)		//Lb有剩余，依次将Lb的剩余元素放入Lc表的尾部
	{
		Lc.elem[k++] = Lb.elem[j++];
	}
}

int main() {
	Sqlist La, Lb,Lc;
	cout << "初始化La,Lb,Lc" << endl;
	InitList(La);
	InitList(Lb);
	InitList(Lc);
	cout << "创建La:" << endl;
	CreateList(La);
	cout << "创建Lb:" << endl;
	CreateList(Lb);
	cout << "合并La,Lb:" << endl;
	MergeSqlist(La, Lb, Lc);
	cout << "遍历Lc:" << endl;
	ListTraverse(Lc);
}

更多文章请关注《万象专栏》