顺序表实现集合并集

目录

问题描述 

程序设计 

程序分析

本节文章

---

问题描述 

【问题描述】

设有两个用顺序表表示的有序集合，输出它们的并集，要求仍然保持有序。

【输入形式】

第一行输入两个整数N和M（不大于100），分别表示两个集合的长度；

第二行输入第一个集合的N个元素（递增有序）；

第三行输入第二个集合的M个元素（递增有序）；

【输出形式】

输出两个集合的并集（仍然保持有序），元素之间以空格分隔。

【样例输入】

5 4

-3 2 4 7 20

2 3 4 5

【样例输出】

-3 2 3 4 5 7 20

【评分标准】

采用顺序表表示集合。并集操作写成算法函数，利用顺序表基本操作实现并集功能。

程序设计 

#include
#include
#define MAX 10
#define IN 10
typedef struct List{
    int *data;
    int len;
    int size;
}List,*PList;
int Init(PList L){
    L->data=(int *)malloc(sizeof(int)*MAX);
    L->len=0;
    L->size=MAX;
    return 1;
} 
int Create(PList L,int n){
    int i;
    for(i=0;i
        scanf("%d",&L->data[i]);
        L->len++;
    } 
    return 1;
}
int Print(PList L){
    int i;
    for(i=0;ilen;i++){
        printf("%d ",L->data[i]);
    }
    printf("\n");
    return 1;
}
int Connect(PList L1,PList L2,PList L3){
    int i=0,j=0,k=0;
    if(L3->size<=L1->len+L2->len){
        L3->data=(int *)realloc(L3->data,(L3->size+IN)*sizeof(int));
        L3->size+=IN;
    }
    while(ilen&&jlen){
        if(L1->data[i]==L2->data[j]){
            j++;
        }
        if(L1->data[i]data[j]){
            L3->data[k++]=L1->data[i++];
        }else{
            L3->data[k++]=L2->data[j++];
        }
    }
    while(ilen){
        L3->data[k++]=L1->data[i++];
    }
    while(jlen){
        L3->data[k++]=L2->data[j++];
    }
    L3->len=k;
    return 1;
}
int main(){
    List L1,L2,L3;
    int m,n;
    Init(&L1);
    Init(&L2);
    Init(&L3);
    scanf("%d %d",&m,&n);
    Create(&L1,m);
    Create(&L2,n);
    Connect(&L1,&L2,&L3);
    Print(&L3);
    return 0;
}

程序分析

这是一个C语言程序，主要实现两个有序列表的合并。程序中用到了动态内存分配和realloc函数，可以在程序运行时动态调整所需要的内存空间。

主要流程：

1. 定义一个结构体List，其中包含一个动态int数组data，列表长度len和列表所占的内存空间size；
2. 定义Init函数，用于初始化一个列表；
3. 定义Create函数，用于创建一个列表并赋值；
4. 定义Print函数，用于输出一个列表中的所有元素；
5. 定义Connect函数，用于将两个有序列表合并为一个新的有序列表；
6. 在主函数中，先定义三个List类型的变量L1、L2、L3，分别表示两个待合并的有序列表和合并后的结果列表；
7. 通过Init函数对三个列表进行初始化；
8. 通过Create函数分别对L1和L2列表进行初始化；
9. 调用Connect函数合并L1和L2列表到L3列表中；
10. 调用Print函数输出L3列表中的所有元素。

程序的主要思路是将L1和L2两个有序列表中的元素逐一比较并放入L3列表中，最后得到一个有序的L3列表。在比较过程中，如果L1和L2中有相同的元素，则将相同的元素放入L3中一次即可。如果L1和L2中有不同的元素，则将较小的元素放入L3中，并进行下一轮比较。当L1和L2中有一个已经比较完毕后，将剩下的元素全部放入L3中即可。

需要注意的是，程序中需要实时检查L3列表的内存空间是否足够，如果不够则需要进行动态扩展。这里使用了realloc函数进行动态内存分配，当L3列表的内存空间不够时，可以将L3列表的空间扩展一个固定大小（这里定义为10）。

总体来说，这个程序比较简单易懂，但需要注意动态内存分配和realloc函数的使用。

本节文章