一般线性表的合并（C语言描述）

深藏阁楼爱情的钟 2022-12-15 14:13 81阅读 0赞

### 目录 ###

*  一、题目描述
 *  二、算法
 *   *  （1）算法思想
     *  （2）算法描述
 *  三、完整源码
 *  四、运行结果展示

# 一、题目描述 #

**假设利用两个线性表 LA 和 LB 分别表示两个集合 A 和 B （即线性表中的数据元素为集合中的成员），现要求一个新的集合 A = AUB .假如，设  
LA = (7,5,3,11)  
LB = (2,6,3)  
合并后  
LA = (7,5,3,11,2,6)**

# 二、算法 #

## （1）算法思想 ##

**扩大线性表LA，将存在于线性表LB中而不存在于LA中的数据放到线性表LA中。只要从线性表LB中依次取得每个元素，并依次在线性表LA中进行查访，若不存在则将其插入。**

## （2）算法描述 ##

/*合并*/
    void Union(LinkList& LA, LinkList& LB,int n,int m)
    {
        
    	int e,a;
    	for (int i = 1;i <= n;i++)
    	{
        
    		e = GetElem(LB, i, e);//取LB中第i个元素赋值给e
    		a = LocateElem(LA, e);//返回0或者1
    		if (a != 1 )//链表里面元素为空了或者没有找到元素
    			ListInsert(LA,m, e);//LA中不存在和e相同的数据元素，插入
    	}
    }

# 三、完整源码 #

#include<stdio.h>
    #define OK 1
    #define ERROR 0
    
    typedef int ElemType;
    typedef int Status;
    
    /*定义链式存储结构*/
    typedef struct LNode
    {
        
    	ElemType data;
    	struct LNode* next;
    }*LinkList;
    
    /*链表的初始化*/
    Status InitList(LinkList& L)
    {
        
    	L = new LNode;
    	L->next = NULL;
    	return OK;
    }
    
    /*创建链表*/
    void CreateList(LinkList& L,int n)
    {
        
    	LinkList p;//生成一个新结点*p
    	L = new LNode;
    	L->next = NULL;
    	for (int i = n;i > 0;--i)
    	{
        
    		p = new LNode;
    		printf("请输入第%d个元素：", i);
    		scanf_s("%d", &p->data);//输入元素
    		p->next = L->next;//新结点与后继结点接起来
    		L->next = p;//新结点与前驱结点接起来
    	}
    }
    
    /*按序号查找元素*/
    Status GetElem(LinkList L, int i, ElemType& e)
    {
        
    	LinkList p;
    	int j = 1;
    	p = L->next;//初始化，p指向第一个结点
    	while (p && j < i)
    	{
        
    		p = p->next;//p向后扫描
    		++j;
    	}
    	if (!p || j > i) return ERROR;//i值不存在
    	e = p->data;//第i个元素的数据域赋值给e
    	return e;
    }
    
    /*查访LA*/
    Status LocateElem(LinkList L, ElemType e)
    {
        
    	LinkList p;
    	p = L->next;//p指向头结点
    	while ( p && p->data != e )//链表不为空且没有找到要找元素就一直循环
    	{
        
    		p = p->next;//p往下找
    	}
    	/*跳出循环，要么是链表没元素，要么是找到要找的元素*/
    	if (!p) return ERROR;//如果链表空了，返回0
    	return OK;//返回1说明找到元素了
    }
    
    /*插入到LA*/
    Status ListInsert(LinkList &L,int m,ElemType &e)
    {
        
    	LinkList p;
    	p = L;
    	int j = 0;
    	while (p && j < m)
    	{
        
    		p = p->next;
    		++j;
    	}
    	if (!p || j > m) return ERROR;
    	LinkList s;//新建结点
    	s = new LNode;
    	s->data = e;//存入数据域
    	s->next = p->next;//更改指针的位置
    	p->next = s;
    	return OK;
    }
    
    /*合并*/
    void Union(LinkList& LA, LinkList& LB,int n,int m)
    {
        
    	int e,a;
    	for (int i = 1;i <= n;i++)
    	{
        
    		e = GetElem(LB, i, e);//取LB中第i个元素赋值给e
    		a = LocateElem(LA, e);//返回0或者1
    		if (a != 1 )//链表里面元素为空了或者没有找到元素
    			ListInsert(LA,m, e);//LA中不存在和e相同的数据元素，插入
    	}
    }
    
    /*输出链表*/
    void PrintList(LinkList L)
    {
        
    	LinkList p;
    	p = L->next;
    	while (p)
    	{
        
    		printf("%d,", p->data);
    		p = p->next;
    	}
    }
    
    int main()
    {
        
    	int m, n,e;
    	LinkList LA, LB;//声明两个链表
    	InitList(LA);//初始化LA
    	InitList(LB);//初始化LB
    
    	printf("请输入LA元素的个数m：");
    	scanf_s("%d", &m);
    	CreateList(LA, m);//创建LA
    	printf("集合LA的元素为：");
    	printf("LA=（");
    	PrintList(LA);//输出集合LA
    	printf(")\n");
    	printf("\n");
    
    	printf("请输入LB元素的个数n：");
    	scanf_s("%d", &n);
    	CreateList(LB, n);//创建LB
    	printf("集合LB的元素为：");
    	printf("LB=（");
    	PrintList(LB);//输出集合LB
    	printf(")\n");
    	printf("\n");
    
    	printf("合并后集合为：");
    	Union(LA,LB,n,m);//合并LA和LB
    	printf("LA=（");
    	PrintList(LA);
    	printf(")\n");
    	return 0;
    }

# 四、运行结果展示 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2NTE4NDYx_size_16_color_FFFFFF_t_70_pic_center]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2NTE4NDYx_size_16_color_FFFFFF_t_70_pic_center]: /images/20221123/b4be0a87c29a480bb49a36d7f4048e5c.png