有序表归并算法（数据结构学习笔记）

小咪咪 2022-12-28 04:18 65阅读 0赞

### 文章目录 ###

*  有序表归并算法
 *   *  顺序表存放有序表的二路归并算法
     *  单链表存放有序表的二路归并算法

--------------------

# 有序表归并算法 #

假设有两个有序表LA和LB，设计一个算法，将它们合并成一个有序表LC（假设每个有序表中和两个有序表间均不存在重复元素），要求不破坏原有表LA和LB。

> 具体算法思路：  
> 用两个变量i,j分别遍历LA,LB，在遍历过程中比较当前两有序表中的最小值，并将最小值复制到有序表LC中。  
> 最后直到其中一个有序表遍历完毕，则默认另一个有序表中所有元素都大于遍历完毕的有序表中的所有元素，就将另一个有序表中所有剩余元素复制到有序表LC中。

**具体图解：**

> 例如：LA=(1,3,5),LB=(2,4,8,10)

将变量i,j分别指向有序表LA和LB的第一个元素  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzg0NTk1Ng_size_16_color_FFFFFF_t_70]

对于当前变量i,j所指元素的最小值复制到有序表LC中，并将所选最小值的记录变量i或j向后移动一位。  
此时元素值最小的为变量i所指的元素（值为1），因此将变量i所指元素复制给有序表LC，并执行i++。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzg0NTk1Ng_size_16_color_FFFFFF_t_70 1]

此时元素值最小的为变量j所指的元素（值为2），因此将变量j所指元素复制给有序表LC，并执行j++。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzg0NTk1Ng_size_16_color_FFFFFF_t_70 2]

此时元素值最小的为变量i所指的元素（值为3），因此将变量i所指元素复制给有序表LC，并执行i++。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzg0NTk1Ng_size_16_color_FFFFFF_t_70 3]

此时元素值最小的为变量j所指的元素（值为4），因此将变量j所指元素复制给有序表LC，并执行j++。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzg0NTk1Ng_size_16_color_FFFFFF_t_70 4]

此时元素值最小的为变量i所指的元素（值为5），因此将变量i所指元素复制给有序表LC，并执行i++。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzg0NTk1Ng_size_16_color_FFFFFF_t_70 5]

此时可以发现有序表`LA已经遍历完毕`，而`有序表LB还未遍历完毕`，因此`可默认有序表LB中的所有剩余元素都比有序表LA中的所有元素都大`，因此可**直接将有序表LB中的所有剩余元素复制给有序表LC**

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

> **很明显可以看出此算法的时间复杂度为O(m+n)，空间复杂度为O(m+n)**

## 顺序表存放有序表的二路归并算法 ##

**代码：**

#include <stdio.h>
    
    typedef struct SqNode
    {
        
    	int data[30];
    	int length;
    }SqList;
    
    SqList LA,LB,LC;
    int NA,NB;
    
    //有序表LA,LB输入函数 
    void ListInput()
    {
        
    	LA.length=NA;
    	LB.length=NB;
    	for(int i=0;i<NA;i++)
    		scanf("%d",&LA.data[i]);
    		
    	for(int i=0;i<NB;i++)
    		scanf("%d",&LB.data[i]);
    }
    
    //二路归并函数 
    void Union()
    {
        
    	int i=0,j=0,k=0;
    	while(i<LA.length&&j<LB.length){
        
    		if(LA.data[i]<LB.data[j])
    			LC.data[k++]=LA.data[i++];
    		else
    			LC.data[k++]=LB.data[j++];
    	}
    	
    	while(i<LA.length)
    		LC.data[k++]=LA.data[i++];
    	while(j<LB.length)
    		LC.data[k++]=LB.data[j++];
    		
    	LC.length=k;
    }
    
    //有序表输出函数
    void ListOutput()
    {
        
    	for(int i=0;i<LC.length;i++)
    		printf("%d ",LC.data[i]);
     } 
    int main()
    {
        
    	scanf("%d %d",&NA,&NB);
    	
    	ListInput();
    	
    	Union();
    	
    	ListOutput();
    	
    	return 0;
    }

## 单链表存放有序表的二路归并算法 ##

**代码：**

#include <stdio.h>
    #include <stdlib.h>
    
    typedef struct LNode
    {
        
    	int data;
    	struct LNode *next;
    }LinkNode;
    
    int NA,NB;
    LinkNode *LA,*LB,*LC;
    
    //单链表输入 
    void ListInput()
    {
        
    	LinkNode *s,*ra,*rb;
    	LA=(LinkNode *)malloc(sizeof(LinkNode));
    	LA->next=NULL;
    	ra=LA;
    	
    	LB=(LinkNode *)malloc(sizeof(LinkNode));
    	LB->next=NULL;
    	rb=LB;
    	
    	int a;
    	for(int i=0;i<NA;i++){
        
    		scanf("%d",&a);
    		s=(LinkNode *)malloc(sizeof(LinkNode));
    		s->data=a;
    		s->next=ra->next;
    		ra->next=s;
    		ra=s;
    	}
    	
    	for(int i=0;i<NB;i++){
        
    		scanf("%d",&a);
    		s=(LinkNode *)malloc(sizeof(LinkNode));
    		s->data=a;
    		s->next=rb->next;
    		rb->next=s;
    		rb=s;
    	}
    }
    
    //二路并行算法 
    void Union()
    {
        
    	LinkNode *pa,*pb,*r,*s;
    	LC=(LinkNode *)malloc(sizeof(LinkNode));
    	r=LC;
    	pa=LA->next;
    	pb=LB->next;
    	
    	while(pa!=NULL&&pb!=NULL){
        
    		if(pa->data<pb->data){
        
    			s=(LinkNode *)malloc(sizeof(LinkNode));
    			s->data=pa->data;
    			r->next=s;
    			r=s;
    			pa=pa->next;
    		}
    		else{
        
    			s=(LinkNode *)malloc(sizeof(LinkNode));
    			s->data=pb->data;
    			r->next=s;
    			r=s;
    			pb=pb->next;
    		}
    	} 
    		
    	while(pa!=NULL){
        
    		s=(LinkNode *)malloc(sizeof(LinkNode));
    		s->data=pa->data;
    		r->next=s;
    		r=s;
    		pa=pa->next;
    	}
    	while(pb!=NULL){
        
    		s=(LinkNode *)malloc(sizeof(LinkNode));
    		s->data=pb->data;
    		r->next=s;
    		r=s;
    		pb=pb->next;
    	}
    	//尾插法要在最后将尾节点的next域置为空 
    	r->next=NULL;
    }
    
    //单链表输出 
    void ListOutput()
    {
        
    	LinkNode *p=LC->next;
    	while(p!=NULL){
        
    		printf("%d ",p->data);
    		p=p->next;
    	}
    }
    
    int main()
    {
        
    	scanf("%d %d",&NA,&NB);
    	
    	ListInput();
    	
    	Union();
    	
    	ListOutput();
    	
    	return 0;
    }

*  学习数据结构教程（第五版）——李春葆教授主编
 *  图片来源于MOOC，数据结构——武汉大学——李春葆教授
 *  （如若侵权可联系QQ删除）

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzg0NTk1Ng_size_16_color_FFFFFF_t_70]: /images/20221120/9eca2fcd6bb2436daa38cc329c206c3f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzg0NTk1Ng_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20201214162605816.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzg0NTk1Ng==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzg0NTk1Ng_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20201214162610322.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzg0NTk1Ng==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzg0NTk1Ng_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20201214162618798.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzg0NTk1Ng==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzg0NTk1Ng_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/20201214162624376.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzg0NTk1Ng==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzg0NTk1Ng_size_16_color_FFFFFF_t_70 5]: https://img-blog.csdnimg.cn/20201214162629417.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzg0NTk1Ng==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzg0NTk1Ng_size_16_color_FFFFFF_t_70 6]: https://img-blog.csdnimg.cn/20201214162634982.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzg0NTk1Ng==,size_16,color_FFFFFF,t_70