原创

顺序表的合并

温馨提示：

本文最后更新于 2021年02月08日，已超过 1,438 天没有更新。若文章内的图片失效（无法正常加载），请留言反馈或直接联系我。

已知线性表La 和Lb中的数据元素按值非递减有序排列，现要求将La和Lb归并为一个新的线性表Lc，且Lc中的数据元素仍按值非递减有序排列。

算法描述

（1）创建一个空的顺序表Lc。
（2）依次此从La和Lb中分别挑选最小的元素，插入到Lc中，直到其中一个表为空。
（3）最后，将La或Lb中剩余的元素在依次插入到Lc中。

算法分析

时间复杂度：O(La.length+Lb.length)
空间复杂度：O(n)

代码实现

/*合并链表*/
int MergeList_L(SqList La,SqList Lb,SqList &Lc){
    int i=0,j=0,k=0;
    while(i<La.length&&j<Lb.length){
        if(La.data[i]<Lb.data[j]){
            InsertSqList_L(Lc,++k,La.data[i++]);
        }else{
            InsertSqList_L(Lc,++k,Lb.data[j++]);
        }
    }
    while(i<La.length)
        InsertSqList_L(Lc,++k,La.data[i++]);
    while(j<Lb.length)
        InsertSqList_L(Lc,++k,Lb.data[j++]);
    return 0;
}

完整代码

#include<stdio.h> 
#include<stdlib.h>
#define MAXSIZE 100
/*声明顺序存储结构*/
typedef struct {
    int *data;
    int length;
}SqList; 
/*初始化顺序表*/ 
int InitSqList_L(SqList &L) {
    L.data = (int *)malloc(MAXSIZE);
    L.length = 0; 
    if(!L.data) return -1;
    return 0;
} 
/*顺序表的插入*/
int InsertSqList_L(SqList &L,int i,int e) {
    if(i<1) return -1;  //如果顺序表不存在,或者插入位置大于链表长度返回-1 
    for(int j=L.length-1;j>=i-1;j--){
        L.data[j+1] = L.data[j]; //插入位置之后的元素全都向后移动一个位置 
    }
    L.data[i-1] = e;  //将需要插入的元素插入到i-1的位置 
    L.length++;  //链表的长度+1
    return 0;
}
/*顺序表的删除*/
int DelSqList_L(SqList &L,int i){
    if(i<1||i>L.length) return -1;  //如果顺序表不存在,或者插入位置大于链表长度返回-1     
    for(int j=i-1;j<L.length-1;j++){
        L.data[j] = L.data[j+1]; 
    }
    L.length--;
    return 0;
}
/*获取指定位置的元素*/
int GetElem_L(SqList L,int i,int &e){
    if(i>L.length||i<1) return -1;
    e = L.data[i-1];
    return 0;
} 
/*打印顺序表中的元素*/ 
int PrintSqList_L(SqList L){
    if(L.length==0) return -1;
    for(int i=0;i<L.length;i++){
        printf("%d ",L.data[i]);
    }
    printf("\n ");
    return 0;
} 
/*合并链表*/
int MergeList_L(SqList La,SqList Lb,SqList &Lc){
    int i=0,j=0,k=0;
    while(i<La.length&&j<Lb.length){
        if(La.data[i]<Lb.data[j]){
            InsertSqList_L(Lc,++k,La.data[i++]);
        }else{
            InsertSqList_L(Lc,++k,Lb.data[j++]);
        }
    }
    while(i<La.length)
        InsertSqList_L(Lc,++k,La.data[i++]);
    while(j<Lb.length)
        InsertSqList_L(Lc,++k,Lb.data[j++]);
    return 0;
} 
main(){
    SqList La,Lb,Lc;
    int aInitStatus = InitSqList_L(La);
    int bInitStatus = InitSqList_L(Lb);
    int cInitStatus = InitSqList_L(Lc);
    if(aInitStatus==0&&bInitStatus==0){
        printf("初始化成功！\n");
    }else{
        printf("初始化失败！\n");
    } 

    InsertSqList_L(La,1,3);
    InsertSqList_L(La,2,7);
    InsertSqList_L(La,3,8);
    printf("------表La------\n");
    PrintSqList_L(La);

    InsertSqList_L(Lb,1,2);
    InsertSqList_L(Lb,2,4);
    InsertSqList_L(Lb,3,6);
    InsertSqList_L(Lb,4,8);
    InsertSqList_L(Lb,5,10);
    InsertSqList_L(Lb,6,11);
    printf("------表Lb------\n");
    PrintSqList_L(Lb);
    printf("------表Lc------\n");
    MergeList_L(La,Lb,Lc);
    PrintSqList_L(Lc);
}

file

正文到此结束

所属分类：算法

本文标签： 线性表 c语言数据结构
本文链接： https://www.it1997.com/article/41
版权声明： 本文由小陈没烦恼原创发布，转载请遵循《署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0)》许可协议授权

顺序表的合并

算法描述

算法分析

代码实现

完整代码

相关文章

热门推荐

说给你听

本文目录

标签云

近期评论

网站信息