线性表的合并C/C++代码实现

爱被打了一巴掌 2023-02-14 10:19 33阅读 0赞

## 1，无序线性表的合并 ##

![在这里插入图片描述][20200602103850313.png]  
只要从B中依次取得每个数据元素， 并依值在A中进行查访， 若不存在， 则插入。

## 代码如下： ##

#include<stdio.h>
    #include<stdlib.h>
    #include<string.h>
    
    #define MAXSIZE 100
    #define ElemType int
    #define Status int
    
    //顺序表的数据结构
    typedef struct 
    {
        
    	ElemType *data;
    	int length;
    }SqList;
    
    
    //初始化
    void InitList(SqList &L)
    {
        
    	L.data = new ElemType[MAXSIZE];
    	L.length = 0;
    }
    
    //打印线性表
    void PrintList(SqList L) 
    {
        
    	printf("当前顺序表的所有元素：");
    	for (int i = 0; i <L.length; i++)
    	{
        
    		printf("%d ", L.data[i]);
    	}
    	printf("\n");
    }
    
    //创建线性表
    void Create(SqList &L)
    {
        
    	int n,i;
    	printf("请输入要输入元素的个数：");
    	scanf("%d", &n);
    	if (n<0 || n>MAXSIZE) 
    	{
        
    		printf("请输入正确的个数!\n");
    	}
    	for (i = 0; i < n; i++) 
    	{
        
    		printf("请输入第%d个元素：",(i+1));
    		scanf("%d", &(L.data[i]));
    		L.length++;
    	}
    
    }
    
    
    //合并二个无序线性表
    void MergeList(SqList &A, SqList &B)
    {
        
    	int i, j=0;
    	int m = A.length;
    	int n = B.length;
    
    	for (i = 0; i < n; i++)
    	{
        
    		while (A.data[j] != B.data[i] && j < m)		//遍历A，直到找到等于B.data[i]的元素或没找到才退出
    		{
        
    			j++;
    		}
    		if (j >= m)		//没找到，则插入
    		{
        
    			A.data[m] = B.data[i];
    			A.length++;
    			m++;
    		}
    		j = 0;
    	}
    }
    
    int main()
    {
        
    	SqList A, B;
    	//初始化
    	InitList(A);
    	InitList(B);
    	//创建
    	printf("请输入集合A的元素：\n");
    	Create(A);
    	printf("请输入集合B的元素：\n");
    	Create(B);
    
    	//合并A和B集合到A中
    	MergeList(A, B);
    	PrintList(A);
    
    }

## 运行结果： ##

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

## 2，顺序有序表的合并 ##

![在这里插入图片描述][20200602104220632.png]  
只需将小者插入到C中即可  
![在这里插入图片描述][20200602104403433.png]

#include<stdio.h>
    #include<stdlib.h>
    #include<string.h>
    
    #define MAXSIZE 100
    #define ElemType int
    #define Status int
    
    //顺序表的数据结构
    typedef struct 
    {
        
    	ElemType *data;
    	int length;
    }SqList;
    
    
    //初始化
    void InitList(SqList &L)
    {
        
    	L.data = new ElemType[MAXSIZE];
    	L.length = 0;
    }
    
    //打印线性表
    void PrintList(SqList L) 
    {
        
    	printf("当前顺序表的所有元素：");
    	for (int i = 0; i <L.length; i++)
    	{
        
    		printf("%d ", L.data[i]);
    	}
    	printf("\n");
    }
    
    //创建线性表
    void Create(SqList &L)
    {
        
    	int n,i;
    	printf("请输入要输入元素的个数：");
    	scanf("%d", &n);
    	if (n<0 || n>MAXSIZE) 
    	{
        
    		printf("请输入正确的个数!\n");
    	}
    	for (i = 0; i < n; i++) 
    	{
        
    		printf("请输入第%d个元素：",(i+1));
    		scanf("%d", &(L.data[i]));
    		L.length++;
    	}
    
    }
    
    
    //合并二个有序线性表到C中
    void MergeList(SqList &A, SqList &B, SqList &C)
    {
        
    	int i=0, j=0,k=0;
    	int m = A.length;
    	int n = B.length;
    
    	while(j < n && i< m)
    	{
        
    			if (A.data[i]>B.data[j])
    			{
        
    				C.data[k] = B.data[j];
    				C.length++;
    				k++;
    				j++;
    			}
    			else
    			{
        
    				C.data[k] = A.data[i];
    				C.length++;
    				k++;
    				i++;
    			}
    	}
    			
    	while (i < m)	//B已到达表尾，依次将A的剩余元素插人C的最后
    	{
        
    		C.data[k] = A.data[i];
    		C.length++;
    		k++;
    		i++;
    	}
    	while (j < n)	//A已到达表尾，依次将B的剩余元素插人C的最后
    	{
        
    		C.data[k] = B.data[j];
    		C.length++;
    		k++;
    		j++;
    	}
    
    
    }
    
    int main()
    {
        
    	SqList A, B,C;
    	//初始化
    	InitList(A);
    	InitList(B);
    	InitList(C);
    	//创建
    	printf("请输入集合A的元素：\n");
    	Create(A);
    	printf("请输入集合B的元素：\n");
    	Create(B);
    
    	//合并A和B集合到A中
    	MergeList(A, B, C);
    	PrintList(C);
    
    }

## 3，链式有序表的合并 ##

需要注意的是:因为链表结点之间的关系是通过指针指向建立起来的，所以用链表进行合并不需要另外开辟存储空间，可以直接利用原来两个表的存储空间。  
C与A共用一个头结点，只需改链即可！

## 代码如下： ##

#include<stdio.h>
    #include<stdlib.h>
    #include<string.h>
    
    #define MAXSIZE 100
    #define ElemType int
    #define Status int
    
    //单链表的数据结构
    typedef struct LNode
    {
        
    	ElemType data;
    	struct LNode *next;
    }LNode,*LinkList;
    
    
    //初始化
    void InitList(LinkList &L)
    {
        
    	L = (LNode *)malloc(sizeof(LNode));
    	L->next = NULL;
    }
    
    //打印线性表
    void PrintList(LinkList L) 
    {
        
    	LNode *p=L;
    	p = p->next;
    	printf("当前单链表的所有元素：");
    	while(p)
    	{
        
    		printf("%d ",p->data);
    		p = p->next;
    	}
    	printf("\n");
    }
    
    //尾插法 创建线性表
    void Create(LinkList &L)
    {
        
    	int n,i;
    	LNode *temp = L;		//尾插法指针
    	printf("请输入要输入元素的个数：");
    	scanf("%d", &n);
    	
    	for (i = 1; i <=n; i++) 
    	{
        
    		LNode *a= (LNode *)malloc(sizeof(LNode));
    		printf("请输入第%d个元素：",(i));
    		scanf("%d", &(a->data));
    		temp->next = a;
    		a->next = NULL;
    		temp =temp->next;
    	}
    
    }
    
    
    //合并二个有序线性表到C中
    //不需要申请辅助空间，只需改链即可
    void MergeList(LinkList &A, LinkList &B, LinkList &C)
    {
        
    	LNode *pa = A->next;	//pa指向A的第一个结点
    	LNode *pb = B->next;	//pb指向B的第一个结点
    	C = A;					//C指向A的头结点，共用
    	LNode *pc = C;			//pc指向C的头结点即A的头结点
    
    	while (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;	//将非空表的剩余段插入到pc所指结点之后 
    	delete(B);
    }
    
    int main()
    {
        
    	LinkList A, B, C;
    	//初始化
    	InitList(A);
    	InitList(B);
    	InitList(C);
    	//创建
    	printf("请输入集合A的元素：\n");
    	Create(A);
    	printf("请输入集合B的元素：\n");
    	Create(B);
    
    	//合并A和B集合到A中
    	MergeList(A, B, C);
    	PrintList(C);
    
    }

## 运行结果： ##

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

[20200602103850313.png]: https://img-blog.csdnimg.cn/20200602103850313.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ4MjY4MzAx_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200602105508277.PNG?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ4MjY4MzAx,size_16,color_FFFFFF,t_70
[20200602104220632.png]: https://img-blog.csdnimg.cn/20200602104220632.png
[20200602104403433.png]: https://img-blog.csdnimg.cn/20200602104403433.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ4MjY4MzAx_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200602105727530.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ4MjY4MzAx,size_16,color_FFFFFF,t_70