设s和t是表示成单链表的两个串,试用C语言编写一个找出s中第1个不在t中出现的字符(假定每个结点只存放一个字符)的算法。
时间: 2024-05-15 19:17:39 浏览: 89
好的,让我来回答你的问题。
以下是一个C语言的算法,可以在s中找到第一个不在t中出现的字符:
```
#include <stdio.h>
#include <stdlib.h>
typedef struct ListNode {
char val;
struct ListNode *next;
} ListNode;
char findFirstChar(ListNode *s, ListNode *t) {
int dict[256] = {0};
// 统计t中字符的出现次数
ListNode *p = t;
while (p) {
dict[p->val]++;
p = p->next;
}
// 找到第一个不在t中出现的字符
p = s;
while (p) {
if (dict[p->val] == 0) {
return p->val;
}
p = p->next;
}
// 如果s中所有字符都在t中出现过,则返回空字符
return '\0';
}
int main() {
// 构造样例数据
ListNode s[5] = {{'a', &s[1]}, {'b', &s[2]}, {'c', &s[3]}, {'d', &s[4]}, {'e', NULL}};
ListNode t[3] = {{'b', &t[1]}, {'e', &t[2]}, {'d', NULL}};
char ret = findFirstChar(s, t);
printf("%c\n", ret);
return 0;
}
```
该算法的时间复杂度是O(n),其中n为s链表的长度。
阅读全文