使用C++进行编程,输入为两个由单链表组成的字符串x和y,(其中每个结点只存储一个字符),请编写一个算法,找出x中第一个不在y中出现的字符。
时间: 2024-05-11 08:14:24 浏览: 18
思路:
首先,我们需要遍历链表x中的每个字符,并逐个检查它是否存在于链表y中。为了减少时间复杂度,我们可以使用一个哈希表来存储链表y中的字符,并在遍历链表x时进行查找。如果找到了一个不在哈希表中的字符,就返回它。
代码实现如下:
```c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define TABLE_SIZE 128
typedef struct Node {
char data;
struct Node* next;
} Node;
Node* createList(char* str) {
Node* head = NULL;
Node* tail = NULL;
int len = strlen(str);
for (int i = 0; i < len; i++) {
Node* node = (Node*)malloc(sizeof(Node));
node->data = str[i];
node->next = NULL;
if (tail) {
tail->next = node;
} else {
head = node;
}
tail = node;
}
return head;
}
char findFirstMissingChar(Node* x, Node* y) {
int table[TABLE_SIZE] = {0};
Node* p = y;
while (p) {
table[p->data] = 1;
p = p->next;
}
p = x;
while (p) {
if (table[p->data] == 0) {
return p->data;
}
p = p->next;
}
return '\0';
}
int main() {
char str1[100], str2[100];
printf("Please enter two strings:\n");
scanf("%s%s", str1, str2);
Node* x = createList(str1);
Node* y = createList(str2);
char c = findFirstMissingChar(x, y);
if (c) {
printf("The first missing char is: %c\n", c);
} else {
printf("All chars in x are in y.\n");
}
return 0;
}
```
测试:
输入:
```
abcde
abcfgh
```
输出:
```
The first missing char is: d
```
相关推荐
![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_column_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)