两个线性表La和Lb均采用顺序存储结构,数据元素均为正整数,两个线性表中各有若干个整数,编写程序求出两个线性表的交集。 已知顺序表的结构定义如下:
时间: 2024-03-06 07:51:35 浏览: 162
好的,以下是可以用C++语言实现的代码:
```c++
#include <iostream>
using namespace std;
#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;
cout << "请输入顺序表的长度:";
cin >> n;
cout << "请输入" << n << "个正整数:" << endl;
for (i = 0; i < n; i++) {
cin >> L.data[i];
}
L.length = n;
}
void PrintList(SqList L) { // 输出顺序表的数据元素
int i;
for (i = 0; i < L.length; i++) {
cout << L.data[i] << " ";
}
cout << endl;
}
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);
cout << "请输入第一个顺序表:" << endl;
InputList(La);
cout << "请输入第二个顺序表:" << endl;
InputList(Lb);
Intersection(La, Lb, Lc);
cout << "两个顺序表的交集为:";
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` 函数输出新的顺序表的数据元素,即为两个顺序表的交集。
阅读全文