7-1 顺序表求交集

顺序表求两个集合的交集可以使用双指针法，具体步骤如下：

1. 对两个集合进行排序，确保元素按照从小到大的顺序排列。

2. 定义两个指针分别指向两个集合的第一个元素。

3. 如果两个指针所指的元素相等，则将该元素添加到交集中，并将两个指针同时向后移动一位。

4. 如果两个指针所指的元素不相等，则将较小的那个指针向后移动一位。

5. 重复上述步骤直到任意一个集合遍历完毕。

下面是一个示例代码，假设两个集合分别为 A 和 B，交集为 C：

void intersection(int A[], int B[], int C[], int n, int m)
{
    int i = 0, j = 0, k = 0;
    while (i < n && j < m) {
        if (A[i] == B[j]) {
            C[k++] = A[i++];
            j++;
        } else if (A[i] < B[j]) {
            i++;
        } else {
            j++;
        }
    }
}

其中，n 和 m 分别为集合 A 和 B 的元素个数，C 为交集，k 为交集中元素的个数。

相关问题

顺序表求两个集合的交集

假设有两个顺序表 A 和 B，它们分别表示两个集合。以下是求它们的交集的步骤：

1. 定义一个空集合 C，用于存储交集的元素。

2. 对于 A 中的每个元素，遍历 B 中的所有元素，查找是否存在相同的元素。若存在，则将该元素加入集合 C 中。

3. 遍历完 A 中的所有元素后，集合 C 中存储的就是 A 和 B 的交集。

下面是 C++ 代码示例：

void intersection(SeqList A, SeqList B, SeqList &C) {
    int i, j, k;
    k = 0;
    for (i = 0; i < A.length; i++) {
        for (j = 0; j < B.length; j++) {
            if (A.data[i] == B.data[j]) {
                C.data[k++] = A.data[i];
                break;
            }
        }
    }
    C.length = k;
}

其中，`SeqList` 是顺序表的类型，`A` 和 `B` 分别表示两个集合，`C` 是存储交集的顺序表。在函数中，我们用两个循环分别遍历 A 和 B 中的所有元素，如果找到相同的元素，则将它加入集合 C 中。最后，将 C 的长度更新为实际存储的元素个数。

c语言代码用顺序表求两集合交集

假设两个集合A和B已经存储在顺序表中，可以按照以下步骤求它们的交集：

1.定义一个新的顺序表C，用于存储交集结果；
2.遍历集合A，对于A中的每个元素，遍历集合B，查找是否存在相同的元素，若存在则将该元素插入到C中；
3.遍历完成后，C中存储的即为A和B的交集。

以下是求两集合交集的C语言代码实现：

#include <stdio.h>

#define MAXSIZE 100

// 定义顺序表
typedef struct {
    int data[MAXSIZE];
    int length;
} SqList;

// 初始化顺序表
void InitList(SqList *L) {
    L->length = 0;
}

// 插入元素
void InsertElem(SqList *L, int elem) {
    if (L->length >= MAXSIZE) {
        printf("List is full!\n");
        return;
    }
    L->data[L->length] = elem;
    L->length++;
}

// 求两集合交集
void GetIntersection(SqList *A, SqList *B, SqList *C) {
    InitList(C);
    int i, j;
    for (i = 0; i < A->length; i++) {
        for (j = 0; j < B->length; j++) {
            if (A->data[i] == B->data[j]) {
                InsertElem(C, A->data[i]);
                break;
            }
        }
    }
}

// 输出顺序表元素
void PrintList(SqList *L) {
    int i;
    for (i = 0; i < L->length; i++) {
        printf("%d ", L->data[i]);
    }
    printf("\n");
}

int main() {
    SqList A = {{1, 3, 5, 7, 9}, 5};
    SqList B = {{2, 3, 5, 7, 8}, 5};
    SqList C;
    GetIntersection(&A, &B, &C);
    printf("A ∩ B: ");
    PrintList(&C);
    return 0;
}

输出结果为：

A ∩ B: 3 5 7