两个线性表La和Lb均采用顺序存储结构,数据元素均为正整数,两个线性表中各有若干个整数,编写程序求出两个线性表的交集。 已知顺序表的结构定义如下:
时间: 2024-03-06 19:51:34 浏览: 81
好的,以下是可以用C语言实现的代码:
```c
#include <stdio.h>
#define MaxSize 100 // 定义线性表的最大长度
typedef struct {
int data[MaxSize]; // 用数组存储数据元素
int length; // 顺序表的当前长度
} SqList; // 定义顺序表类型
void InitList(SqList *L) { // 初始化顺序表
L->length = 0;
}
void InputList(SqList *L) { // 从键盘输入顺序表的数据元素
int n, i;
printf("请输入顺序表的长度:");
scanf("%d", &n);
printf("请输入%d个正整数:\n", n);
for (i = 0; i < n; i++) {
scanf("%d", &L->data[i]);
}
L->length = n;
}
void PrintList(SqList L) { // 输出顺序表的数据元素
int i;
for (i = 0; i < L.length; i++) {
printf("%d ", L.data[i]);
}
printf("\n");
}
void Intersection(SqList La, SqList Lb, SqList *Lc) { // 求两个顺序表的交集
int i, j, k;
k = 0;
for (i = 0; i < La.length; i++) {
for (j = 0; j < Lb.length; j++) {
if (La.data[i] == Lb.data[j]) { // 如果找到相同元素
Lc->data[k] = La.data[i]; // 将其存入新的顺序表中
k++;
break; // 跳出内层循环,查找下一个元素
}
}
}
Lc->length = k; // 新的顺序表的长度为k
}
int main() {
SqList La, Lb, Lc;
InitList(&La);
InitList(&Lb);
InitList(&Lc);
printf("请输入第一个顺序表:\n");
InputList(&La);
printf("请输入第二个顺序表:\n");
InputList(&Lb);
Intersection(La, Lb, &Lc);
printf("两个顺序表的交集为:");
PrintList(Lc);
return 0;
}
```
在这个程序中,我们定义了一个结构体 `SqList` 表示顺序表,包含一个数组 `data` 存储数据元素,以及一个整数 `length` 表示当前顺序表的长度。我们通过 `InitList` 函数对顺序表进行初始化,通过 `InputList` 函数从键盘输入顺序表的数据元素,通过 `PrintList` 函数输出顺序表的数据元素。最重要的是 `Intersection` 函数,它实现了求两个顺序表的交集,具体思路如下:
1. 定义一个整数 `k`,表示新的顺序表的长度,初始化为0。
2. 从第一个顺序表的第一个元素开始,依次与第二个顺序表的所有元素进行比较。
3. 如果找到相同元素,则将其存入新的顺序表中,并将 `k` 加1,然后跳出内层循环查找下一个元素。
4. 内层循环结束后,继续从第一个顺序表的下一个元素开始查找。
5. 最后,新的顺序表的长度为 `k`,即为两个顺序表的交集的长度。
我们在 `main` 函数中调用 `InitList` 函数对三个顺序表进行初始化,调用 `InputList` 函数从键盘输入前两个顺序表的数据元素,然后调用 `Intersection` 函数求两个顺序表的交集,最后调用 `PrintList` 函数输出新的顺序表的数据元素,即为两个顺序表的交集。
阅读全文