C语言线性表交集与并集含测试源码

• • 题目再现
  • • 交集
    • 并集
  • 测试效果
  • 解题思路
  • • 并集
    • 并集
  • 核心源码
  • 完整源码
  • 参考文献

设有两个线性表LA和LB，将LA与LB的并,结果存于LA，即LA=LA ∪ cup ∪LB

设有两个线性表LA和LB，求LA与LB的交，结果存在于LA,即LA=LA ∩ cap ∩LB

对于LB中的每一个元素，检查在LA中是否有值相等的元素，若没有则把它插入LA中。

对于LA中的每一个元素，检查在LB中是否有值相等的元素，若没有则从LA中删除它

void Merge(SeqList& LA,SeqList& LB) {
    int n = Length(LA);

    int m = Length(LB);
    int i,k,x;
    for(i=1;i<=m;i++){
        x = getValue(LB,i);
        k = Search(LA,x);
        if (k == -1){
            Insert(LA,n+1,x);
            n++;
        }

    }
}

void Intersection(SeqList& LA,SeqList& LB) {
    //求顺序表LA与LB中的共有元素，结果存于LA
    int n = Length(LA);
    int m = Length(LB),i = 1,k,x;
    while(i <= n) {
        x = getValue(LA,i);
        k = Search(LB,x);
        if(k==-1){
            Remove(LA,i,x);
            n--;
        }else
            i++;

    }
}

#include
#include
#define initSize 100
typedef int DataType;
typedef struct{
    DataType *data;
    int maxSize,n;
}SeqList;


void initList(SeqList& L) {
    //调用方式initList(L),输入:未初始化的顺序表L;输出；已初始化的顺序表L
    L.data = (DataType *) malloc(initSize*sizeof(DataType));
    if(!L.data) {
        printf("分配有误....n");
        exit(1);
    }
    L.maxSize = initSize;
    L.n = 0;
}

int Length(SeqList &L) {
    return L.n;
}

//顺序表L,待查找值x;输出:函数值
int Search(SeqList &L, DataType x) {
    for(int i =0;i L.n+1)
        return false;
    for(int j=L.n;j>=i;j--)
        L.data[j] = L.data[j-1];
    L.data[i-1] = x;
    L.n++;
    return true;

}

bool Remove(SeqList &L,int i,DataType& x) {
    if(!L.n)
        return false;
    if (i< 1 || i > L.n)
        return false;
    x = L.data[i-1];
    for(int j = i;j<=L.n;j++)
        L.data[j-1] = L.data[j];
    L.n--;
    return true;
}

DataType getValue(SeqList &L,int i) {
    if(i > 0 && i <= L.n)
        return L.data[i-1];
    else
        return -1;

}

void Merge(SeqList& LA,SeqList& LB) {
    int n = Length(LA);

    int m = Length(LB);
    int i,k,x;
    for(i=1;i<=m;i++){
        x = getValue(LB,i);
        k = Search(LA,x);
        if (k == -1){
            Insert(LA,n+1,x);
            n++;
        }

    }
}

void Intersection(SeqList& LA,SeqList& LB) {
    //求顺序表LA与LB中的共有元素，结果存于LA
    int n = Length(LA);
    int m = Length(LB),i = 1,k,x;
    while(i <= n) {
        x = getValue(LA,i);
        k = Search(LB,x);
        if(k==-1){
            Remove(LA,i,x);
            n--;
        }else
            i++;

    }
}
int main()
{

    SeqList A,B;
    //模拟1的情况
    int arr1[5] = {5,8,9,2,1};
    createList(A,arr1,sizeof(arr1)/sizeof(int));
    int arr2[5] = {5,3,2,1,98};
    createList(B,arr2,sizeof(arr2)/sizeof(int));
    printList(A);
    printList(B);
    printf("并集为:n");
    Merge(A,B);
    printList(A);
    printf("n");


    SeqList  C,D;
    int arr3[5] = {5,8,9,2,1};
    createList(C,arr3,sizeof(arr3)/sizeof(int));
    int arr4[5] = {5,3,2,1,98};
    createList(D,arr4,sizeof(arr3)/sizeof(int));
    printList(C);
    printList(D);
    Intersection(C,D);
    printf("交集为:n");
    printList(C);
    return 0;
}

殷人昆著.数据结构与算法解析.北京：清华大学出版社，2021.4