博客

现有两个线性表LA和LA分别表示两个集合A和B，合并为一个新的集合A=A∪B.

完整代码如下：

#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <malloc.h>
#include <iostream> 
using namespace std;

#define LIST_INIT_SIZE 100	//线性表存储空间初始分配量
#define LISTINCREMENT  10 	//线性表存储空间的分配增量
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define OVERFLOW -2
#define MAX_SIZE 100
#define List int

typedef int Status;
typedef int ElemType;
typedef struct
{
    ElemType *elem;		//存储空间基址
    int length;    		//当前长度
    int listsize;  		//当前分配的存储容量(以sizeof(ElemType)为单位)
} SqList;

/****************基本操作函数*****************/ 
//1.线性表L的初始化
Status InitList_Sq(SqList &L)			//构建一个空的线性表 
{
	L.elem = (ElemType *)malloc(LIST_INIT_SIZE * sizeof(ElemType));
	if ( !L.elem )						//存储分配失败	
		exit(OVERFLOW);
	L.length = 0;						//空表长度为0 
	L.listsize = LIST_INIT_SIZE;		//初始化存储容量 
	return OK;
} 

//2.求线性表的长度
int GetLength(SqList L)
{
	return(L.length);
} 

//3.顺序表的取值，根据位置i获取内容
int GetElem(SqList L, int i, ElemType &e)
{
	if (i < 1 || i > L.length)		//判断i的位置是否合理 
		return ERROR;
	else
		return (L.elem[i-1]); 		//第i-1个单元存储着第i个数据 
} 

//4.顺序表的查找
//算法思想：
//	1.在线性表L中查找与指定元素e相同的数据元素的位置
//	2.从表的一端开始，逐个进行比较 
int LocateElem(SqList L, ElemType e)
{
	for (int i = 0; i < L.length; i++)
	{
		if (L.elem[i] == e)
			return (i+1);		
	}
	return ERROR;
}

//5.创建顺序表函数 初始化前n个数据
int CreatList(SqList &L, int n)
{
	if (n < 0 || n > LIST_INIT_SIZE)
		return ERROR;				//n非法
	for (int i = 0; i<n; i++)
	{
		scanf("%d", &L.elem[i]);
		L.length++;
	}
	return OK;	
}

//6.顺序表的插入
//算法思想：
//	1.判断插入位置i是否合法
//	2.判断顺序表的存储空间是否已满，已满增加存储空间
//	3.将第n至第i位的元素一次向后移动一个位置，空出第i个位置
//	4.将要插入的新元素放入e放入第i个位置
//	5.表长加1，插入成功返回OK 
Status ListInsert_Sq(SqList &L , int i, ElemType e)
{
	ElemType *newbase, *p, *q;
	
	if (i < 1 || i > L.length+1)		//i值不合法 
		return ERROR;
		
	if (L.length >= L.listsize)			//当前存储空间已满，增加分配 
	{
		newbase = (ElemType *)realloc(L.elem, (L.listsize + LISTINCREMENT) * sizeof(ElemType));
		if ( !newbase )					//分配失败 
			exit(OVERFLOW);
		L.elem = newbase;				//新基址 
		L.listsize += LISTINCREMENT;	//增加存储容量 
	}
	
	q = &(L.elem[i-1]);					//q为插入位置的地址 
	for (p = &L.elem[L.length-1]; p >= q; --p)
	{
		*(p+1) = *p;					//插入位置及之后的元素后移一个位置 
	}
	*q = e;								//全部移动完后插入e 
	++L.length;							//表长加1 
	return OK;
} 


//********************************功能函数*****************************************//
//输出功能函数 按位置从小到大输出顺序表所有元素
void PrintList(SqList L)
{
	printf("当前顺序表所有元素:");
	for (int i = 0; i<L.length; i++)
	{
		printf("%d ", L.elem[i]);
	}
	printf("\n");
}

//创建顺序表函数
void Create(SqList &L)
{
	int n;
	L.length = 0;
	printf("请输入要创建的顺序表长度(>1):");
	scanf("%d", &n);
	printf("请输入%d个数（空格隔开）: ", n);
	
	if ( CreatList(L, n) ) 
	{
		printf("创建成功！\n");
		PrintList(L);
	}
	else 
		printf("输入长度非法！\n");
}

//合并顺序表 
//	将所有在顺序表Lb但不在La中的数据元素插入到La中 
void unionn(SqList &La, SqList Lb)
{
	int La_len = GetLength(La);				//求顺序表长度 
	int Lb_len = GetLength(Lb);
	ElemType equal, e;
	
	for (int i = 1; i <= Lb_len; i++)
	{
		equal = GetElem(Lb, i, e);			//取Lb中第i个数据元素赋值给equal 
		if ( !LocateElem(La, equal) )		//La中不存在和e相同的数据元素，则插入 
		{
			ListInsert_Sq(La, ++La_len, equal);
		}
	}
}

//主函数 
int main()
{
	SqList La; 
	InitList_Sq(La);
	printf("请录入顺序表La的数据：\n");
	Create(La);
	printf("\n");
	SqList Lb; 
	InitList_Sq(Lb);
	printf("请录入顺序表Lb的数据：\n");
	Create(Lb);
	printf("\n");
	unionn(La, Lb);
	printf("输出合并后的顺序表La: \n");
	PrintList(La);
	printf("\n");

	return 0;
}

运行结果