分别对顺序表a、b及单链表a、b,编写算法求a=a∩b,a=a∪b。
时间: 2023-05-31 10:17:58 浏览: 191
### 回答1:
顺序表a、b求a=a∩b的算法:
1. 初始化一个新的顺序表c。
2. 遍历顺序表a,对于a中的每个元素,判断是否也在顺序表b中出现。
3. 如果该元素同时出现在a和b中,则将其加入顺序表c中。
4. 返回顺序表c作为a∩b的结果。
顺序表a、b求a=a∪b的算法:
1. 初始化一个新的顺序表c,将顺序表a中的所有元素加入c中。
2. 遍历顺序表b,对于b中的每个元素,判断是否已经在顺序表c中出现。
3. 如果该元素还没有出现在c中,则将其加入c中。
4. 返回顺序表c作为a∪b的结果。
单链表a、b求a=a∩b的算法:
1. 初始化一个新的单链表c。
2. 遍历单链表a,对于a中的每个元素,判断是否也在单链表b中出现。
3. 如果该元素同时出现在a和b中,则将其加入单链表c中。
4. 返回单链表c作为a∩b的结果。
单链表a、b求a=a∪b的算法:
1. 初始化一个新的单链表c,将单链表a中的所有元素加入c中。
2. 遍历单链表b,对于b中的每个元素,判断是否已经在单链表c中出现。
3. 如果该元素还没有出现在c中,则将其加入c中。
4. 返回单链表c作为a∪b的结果。
### 回答2:
顺序表a、b的求交集算法如下:
1. 初始化一个空的顺序表c;
2. 遍历顺序表a中的每一个元素,判断它是否也是顺序表b中的元素;
3. 如果是,就将该元素加入顺序表c中;
4. 最后返回顺序表c,即为a∩b。
时间复杂度为O(n^2),因为需要遍历顺序表a和b中的所有元素。
顺序表a、b的求并集算法如下:
1. 根据a和b的长度创建一个新的顺序表c,并将a中的所有元素复制到c中;
2. 遍历顺序表b中的每一个元素,判断它是否已经在顺序表c中出现过;
3. 如果没有出现过,就将该元素加入顺序表c中;
4. 最后返回顺序表c,即为a∪b。
时间复杂度为O(n^2),因为需要遍历顺序表a和b中的所有元素。
单链表a、b的求交集算法如下:
1. 初始化一个空的单链表c;
2. 遍历单链表a中的每一个元素,判断它是否也是单链表b中的元素;
3. 如果是,就将该元素加入单链表c中;
4. 最后返回单链表c,即为a∩b。
时间复杂度为O(n^2),因为需要遍历单链表a和b中的所有元素。
单链表a、b的求并集算法如下:
1. 根据a和b的长度创建一个新的单链表c,并将a中的所有元素复制到c中;
2. 遍历单链表b中的每一个元素,判断它是否已经在单链表c中出现过;
3. 如果没有出现过,就将该元素加入单链表c中;
4. 最后返回单链表c,即为a∪b。
时间复杂度为O(n^2),因为需要遍历单链表a和b中的所有元素。
### 回答3:
顺序表a、b求并集
定义两个指针i、j,分别从a、b的头开始往后扫描,如果a[i]小于b[j],则将a[i]加入到结果集合中,并将i向后移动一位;如果a[i]大于b[j],则将b[j]加入到结果集合中,并将j向后移动一位,直到a、b其中任意一个扫描完毕,则将另外一个未扫描完毕的顺序表中的元素全部加入到结果集合中即可。
算法实现如下:
```
void unionList(SeqList a, SeqList b, SeqList &result) {
int i = 0, j = 0;
result.length = 0;
while (i < a.length && j < b.length) {
if (a.data[i] < b.data[j]) {
result.data[result.length++] = a.data[i++];
} else if (a.data[i] > b.data[j]) {
result.data[result.length++] = b.data[j++];
} else {
result.data[result.length++] = a.data[i++];
j++;
}
}
while (i < a.length) {
result.data[result.length++] = a.data[i++];
}
while (j < b.length) {
result.data[result.length++] = b.data[j++];
}
}
```
顺序表a、b求交集
定义两个指针i、j,分别从a、b的头开始往后扫描,如果a[i]等于b[j],则将a[i]加入到结果集合中,并将i、j都向后移动一位;如果a[i]小于b[j],则将i向后移动一位;如果a[i]大于b[j],则将j向后移动一位,直到a、b其中任意一个扫描完毕,则将另外一个未扫描完毕的顺序表中的元素全部加入到结果集合中即可。
算法实现如下:
```
void intersectList(SeqList a, SeqList b, SeqList &result) {
int i = 0, j = 0;
result.length = 0;
while (i < a.length && j < b.length) {
if (a.data[i] == b.data[j]) {
result.data[result.length++] = a.data[i++];
j++;
} else if (a.data[i] < b.data[j]) {
i++;
} else {
j++;
}
}
}
```
单链表a、b求并集
定义一个指针p,从a的头开始往后扫描,将每个元素加入到结果集合中,并将p向后移动一位,当p扫描完a之后再扫描b中的元素,将与a中元素不重复的元素加入到结果集合中。
算法实现如下:
```
void unionList(LinkList a, LinkList b, LinkList &result) {
LNode *p = a->next, *q = b->next, *r;
result = a;
r = result->next;
while (p != NULL && q != NULL) {
if (p->data < q->data) {
r->next = p;
r = r->next;
p = p->next;
} else if (p->data > q->data) {
r->next = q;
r = r->next;
q = q->next;
} else {
r->next = p;
r = r->next;
p = p->next;
q = q->next;
}
}
if (q != NULL) {
r->next = q;
}
}
```
单链表a、b求交集
定义三个指针p、q、r,分别从a、b、结果集合result的头开始往后扫描,如果p->data等于q->data,则将p->data加入到结果集合中,并将p、q、r都向后移动一位;如果p->data小于q->data,则将p向后移动一位;如果p->data大于q->data,则将q向后移动一位,直到a、b其中任意一个扫描完毕,则将另外一个未扫描完毕的单链表中的元素全部加入到结果集合中即可。
算法实现如下:
```
void intersectList(LinkList a, LinkList b, LinkList &result) {
LNode *p = a->next, *q = b->next, *r = (LinkList)malloc(sizeof(LNode));
r->next = NULL;
result = r;
while (p != NULL && q != NULL) {
if (p->data == q->data) {
r->next = p;
r = r->next;
p = p->next;
q = q->next;
} else if (p->data < q->data) {
p = p->next;
} else {
q = q->next;
}
}
}
```
相关推荐
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)