试用顺序表表示集合，并确定合适的约定，在此基础上编写算法以实现集合的交、并、差等运算，并分析各算法的时间性能

一、顺序表表示集合

顺序表是一种线性表，可以用来表示集合。定义如下：

#define MAXSIZE 100 // 定义最大容量

typedef struct {
    int data[MAXSIZE]; // 存放元素的数组
    int length; // 当前长度
} SqList; // 顺序表的数据类型

约定：

- 元素的值为正整数。
- 集合中不含相同的元素。
- 集合按照元素的大小非降序排列。
- 集合的长度不能超过 MAXSIZE。

二、集合的交、并、差等运算

1. 集合的交

算法思路：从两个集合中依次取出相同的元素，放入新的集合中。

void intersection(SqList A, SqList B, SqList &C) {
    int i = 0, j = 0, k = 0;
    while (i < A.length && j < B.length) {
        if (A.data[i] < B.data[j]) {
            i++;
        } else if (A.data[i] > B.data[j]) {
            j++;
        } else {
            C.data[k++] = A.data[i++];
            j++;
        }
    }
    C.length = k;
}

时间复杂度：$O(m+n)$，其中 $m$ 和 $n$ 分别为两个集合的长度。

2. 集合的并

算法思路：将两个集合合并成一个新集合，去除重复元素。

void unionSet(SqList A, SqList B, SqList &C) {
    int i = 0, j = 0, k = 0;
    while (i < A.length && j < B.length) {
        if (A.data[i] < B.data[j]) {
            C.data[k++] = A.data[i++];
        } else if (A.data[i] > B.data[j]) {
            C.data[k++] = B.data[j++];
        } else {
            C.data[k++] = A.data[i++];
            j++;
        }
    }
    while (i < A.length) {
        C.data[k++] = A.data[i++];
    }
    while (j < B.length) {
        C.data[k++] = B.data[j++];
    }
    C.length = k;
}

时间复杂度：$O(m+n)$，其中 $m$ 和 $n$ 分别为两个集合的长度。

3. 集合的差

算法思路：从集合 $A$ 中去除集合 $B$ 中的所有元素，得到新集合 $C$。

void difference(SqList A, SqList B, SqList &C) {
    int i = 0, j = 0, k = 0;
    while (i < A.length && j < B.length) {
        if (A.data[i] < B.data[j]) {
            C.data[k++] = A.data[i++];
        } else if (A.data[i] > B.data[j]) {
            j++;
        } else {
            i++;
            j++;
        }
    }
    while (i < A.length) {
        C.data[k++] = A.data[i++];
    }
    C.length = k;
}

时间复杂度：$O(m+n)$，其中 $m$ 和 $n$ 分别为两个集合的长度。

三、总结

以上算法的时间复杂度都为 $O(m+n)$，其中 $m$ 和 $n$ 分别为两个集合的长度。因为算法中都需要遍历两个集合，时间复杂度与集合长度成线性关系。