【算法——有序表的合并】

墨蓝 2022-12-16 05:58 143阅读 0赞

### 目录 ###

*  一、题目描述
 *   *  1、描述
     *  2、分析
 *  二、顺序有序表的合并
 *   *  1、算法思想
     *  2、算法描述
 *  三、链式有序表的合并
 *   *  1、算法思想
     *  2、算法描述
 *  四、完整程序源码（链式合并）
 *  五、运行结果展示

# 一、题目描述 #

## 1、描述 ##

**【题目】已知线性表 LA 和 LB 的数据元素按值非递减有序排列，现要求将 LA 和 LB 归并为一个新的线性表 LC ,且 LC 中的数据元素仍按值非递减有序排列。例如，设：  
LA = (3,5,8,11)  
LB = (2,6,8,9,11,15,20)  
则  
LC = (2,3,5,6,8,8,9,11,11,15,20)**

## 2、分析 ##

**由题目可知，LC 中的数据元素或是LA中的数据元素，或是LB中的数据元素，则只要先设LC为空表，然后将LA和LB中的元素逐个插入到LC中。为使LC为按值非递减有序排序，可设两个指针pa和pb分别指向LA和LB中的某个元素，若设pa当前所指元素为a,pb当前所指元素为b,则当前应该插入到LC中的元素c为：当a<= b时，存a;当a >b 时存b.**

# 二、顺序有序表的合并 #

![在这里插入图片描述][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 1]

## 1、算法思想 ##

> 1、创建一个表长为m +n 的空表LC  
> 2、指针pc初始化，指向LC的第一个元素  
> 3、指针pa,pb初始化，分别指向LA和LB的第一个元素  
> 4、当指针pa和pb均为到达相应队尾时，则依次比较pa和pb所指向的元素值，从LA和LB中取元素值较小的结点插入到LC的最后  
> 5、如果pb已经到达LB的队尾，将依次LA的剩余元素插入到LC的最后  
> 6、如果pa已经到达LA的表尾，依次将LB的剩余元素插入到LC的最后

## 2、算法描述 ##

/*顺序有序表的合并*/
    void MergeList_Sq(SqList LA, SqList LB, SqList& LC)
    {
        
    	pa = LA.elem; pb = LB.elem;//指针pa和pb分别指向LA,LB的第一个元素
    	LC.length = LA.length + LB.length;//LC的长度是LA.LB的长度之和
    	LC.elem = new ElemType[LC.length];//合并后为新表分配一个数组空间
    	pc = LC.elem;//指针pc指向LC的第一个元素
    	pa_last = LA.elem + LA.length - 1;//指针pa_last指向LA的最后一个元素
    	pb_last = LB.elem + LB.length - 1;//指针pb_last指向LB的最后一个元素
    	while (pa <= pa_last && pb <= pb_last)//两个表都非空
    	{
        
    		if (*pa <= *pb)//依次摘取两个表中较小的元素存入到LC中
    			*pc++ = *pa++;
    		else
    			*pc++ = *pb++;
    	}
    	while (pa <= pa_last)
    		*pc++ = *pa++;//LB已经到头了，将LA中的剩余元素插入到LC中
    	while (pb <= pb_last)
    		*pc++ = *pb++;//LA已经到头了，将LB中的剩余元素插入到LC中
    }

# 三、链式有序表的合并 #

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

## 1、算法思想 ##

> 1、LC指向LA  
> 2、依次从LA或者LB中摘取元素值较小的结点插入到LC表的最后，直至其中一个表变为空为止  
> 3、继续将LA或LB其中一个表的剩余结点插入在LC表的最后  
> 4、释放LB表的表头结点

## 2、算法描述 ##

/*链式有序表的合并*/
    void MergeList_L(LinkList& LA, LinkList& LB, LinkList& LC)
    {
        
    	LinkList pa, pb, pc;//声明三个指针
    	pa = LA->next;//pa指向LA的第一个结点
    	pb = LB->next;//pb指向LB的第一个结点
    	LC = LA;//用LA的头结点作为LC的头结点
    	pc = LC;//pc指向LC的第一个结点
    
    	while (pa && pb)//两个表非空
    	{
        
    		if (pa->data <= pb->data)//摘取两个表中最小元素
    		{
        
    			pc->next = pa;
    			pc = pa;
    			pa = pa->next;//将pa所指结点接在pc所指结点之后
    		}
    		else
    		{
        
    			pc->next = pb;
    			pc = pb;
    			pb = pb->next;//将pb所指结点接在pc所指结点之后
    		}
    	}
    	pc->next = pa ? pa : pb;//插入非空表的剩余段
    	delete LB;//删除LB的头结点
    }

# 四、完整程序源码（链式合并） #

#include<stdio.h>
    #define OK 1
    #define ERROR 0
    
    typedef int Status;
    typedef int ElemType;
    
    /*线性表的链式存储结构*/
    typedef struct LNode
    {
        
    	ElemType data;//数据域
    	struct LNode* next;//指针域
    }LNode,*LinkList;
    
    
    /*链表的初始化*/
    Status InitList(LinkList& L)
    {
        
    	L = new LNode;
    	L->next = NULL;
    	return OK;
    }
    
    /*尾插法创建链表*/
    void CreatList(LinkList& L, int n)
    {
        
    	LinkList r;
    	L = new LNode;
    	L->next = NULL;//初始化头结点
    	r = L;//使用尾结点指向头结点
    	for (int i = 1;i <= n;i++)
    	{
        
    		LinkList p;
    		p = new LNode;
    		printf("请输入第%d个元素为：",i);
    		scanf_s("%d", &p->data);
    		p->next = NULL;//最后一个结点指向空
    		r->next = p;//结点r指向新插入的结点
    		r = p;//更改尾结点的位置
    	}
    }
    
    /*输出链表的内容*/
    void PrintList(LinkList L)
    {
        
    	LinkList p;
    	p = L->next;
    	while (p)
    	{
        
    		printf("%d ", p->data);
    		p = p->next;
    	}
    }
    
    /*链式有序表的合并*/
    void MergeList_L(LinkList& LA, LinkList& LB, LinkList& LC)
    {
        
    	LinkList pa, pb, pc;//声明三个指针
    	pa = LA->next;//pa指向LA的第一个结点
    	pb = LB->next;//pb指向LB的第一个结点
    	LC = LA;//用LA的头结点作为LC的头结点
    	pc = LC;//pc指向LC的第一个结点
    
    	while (pa && pb)//两个表非空
    	{
        
    		if (pa->data <= pb->data)//摘取两个表中最小元素
    		{
        
    			pc->next = pa;
    			pc = pa;
    			pa = pa->next;//将pa所指结点接在pc所指结点之后
    		}
    		else
    		{
        
    			pc->next = pb;
    			pc = pb;
    			pb = pb->next;//将pb所指结点接在pc所指结点之后
    		}
    	}
    	pc->next = pa ? pa : pb;//插入非空表的剩余段
    	delete LB;//删除LB的头结点
    }
    
    int main(void)
    {
        
    	int m, n;
    	LinkList LA, LB, LC;
    	InitList(LA);//初始化LA
    	InitList(LB);//初始化LB
    	InitList(LC);//初始化LC
    
    	printf("请输入LA表中的元素个数：");
    	scanf_s("%d", &m);
    	CreatList(LA, m);//创建LA
    	printf("LA表中的元素为：");
    	PrintList(LA);//输出LA
    	printf("\n\n");
    	printf("请输入LB表中的元素个数：");
    	scanf_s("%d", &n);
    	CreatList(LB, n);//创建LB
    	printf("LB表中的元素为：");
    	PrintList(LB);//输出LB
    	printf("\n\n");
    	printf("LA和LB合并后LC表的元素为：");
    	MergeList_L(LA,LB,LC);//合并LA和LB成LC
    	PrintList(LC);//输出LC
    	printf("\n\n");
    
    	return 0;
    }

# 五、运行结果展示 #

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

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2NTE4NDYx_size_16_color_FFFFFF_t_70_pic_center]: /images/20221123/cb03a741671d4d4a92adaa02e20a2603.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2NTE4NDYx_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221123/3058c4abd56f48e4bde47a96016e0b95.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2NTE4NDYx_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20221123/df36ef6516a2474c87c593df12daa404.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2NTE4NDYx_size_16_color_FFFFFF_t_70_pic_center 3]: /images/20221123/7fcfd1f71c9043d297cfefe9f249a01a.png