使用C++进行编程,假设x和y是两个由单链表组成的字符串(其中每个结点只存储一个字符),请编写一个算法,找出x中第一个不在y中出现的字符。 注:在朴素的算法之上,如果使用某些技巧提升算法效率的可以额外得分。 提交的实验报告中请说明所使用的技巧,以及为什么可以有提升。
时间: 2023-05-24 09:06:39 浏览: 58
算法思路:
首先我们遍历y,把y中的所有字符存储到一个hash表(可以使用数组实现hash表),然后遍历x,查找x中第一个不在y中出现的字符。
算法步骤:
1. 构建hash表,将y中的所有字符存储到hash表中。其中数组下标表示字符的ascii码,值表示该字符是否在y中出现过。
2. 遍历x,查找x中第一个不在y中出现的字符。遍历过程中,首先在hash表中查找当前字符是否出现过,如果没有出现过,则说明找到了目标字符,返回该字符;否则继续遍历,直到遍历完x。
算法分析:
时间复杂度为O(m+n),其中m和n分别为x和y的长度。构建hash表的时间复杂度为O(n),遍历x的时间复杂度为O(m),查找hash表的时间复杂度为O(1)。
使用hash表可以大大降低遍历的时间复杂度,因为hash表可以在O(1)的时间复杂度内查找某个元素是否存在。相比于朴素算法,使用hash表可以大大提高算法效率。
C程序实现:
```c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_LEN 1000000 // 字符串最大长度
char x[MAX_LEN], y[MAX_LEN]; // 两个字符串
int hash[128]; // hash表,用来存储y中出现的字符
// 构建hash表
void build_hash(char *str) {
memset(hash, 0, sizeof(hash)); // 初始化hash表
while (*str) {
hash[*str++] = 1; // 将出现过的字符的hash值设为1
}
}
// 查找x中第一个不在y中出现的字符
char find_first_char() {
char *p = x;
while (*p) {
if (!hash[*p]) { // 当前字符不在y中出现过,找到了答案
return *p;
}
p++;
}
return '\0'; // 没有找到答案
}
int main() {
printf("请输入字符串x:");
scanf("%s", x);
printf("请输入字符串y:");
scanf("%s", y);
build_hash(y); // 构建hash表
char ch = find_first_char(); // 查找x中第一个不在y中出现的字符
if (ch) {
printf("字符串x中第一个不在y中出现的字符是:%c\n", ch);
} else {
printf("字符串x中所有字符均在y中出现过\n");
}
return 0;
}
```
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.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)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![](https://img-home.csdnimg.cn/images/20210720083646.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)