一道Leetcode题引起的思考:Segmentation fault是什么?

在Leetcode上刷题时,刷到题目Valid Anagram,给定两个字符串st,编写一个函数来确定t是否是s的一个anagram,谷歌翻译对anagram的解释是通过重新排列另一个单词的字母顺序而组成的一个新单词,比如cinema是iceman的anagram。本质就是判断st是否有一样的字母组成。

什么是Segmentation fault

我看到这个题目的第一印象就是对字符串st中的字母排序,然后逐一比对,如果全部相同,就返回true,否则返回false

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <string.h>
#include <stdlib.h>
#include <stdbool.h>

int charcmp(const void *a, const void *b) {
return *(char *)a - *(char *)b;
}

bool isAnagram(char* s, char* t) {
int i;
int s_len;
int t_len;

s_len = strlen(s);
t_len = strlen(t);
if (s_len != t_len) {
return false;
}
qsort(s, s_len, sizeof(s[0]), charcmp);
qsort(t, t_len, sizeof(t[0]), charcmp);
for (i = 0; i < s_len; i++) {
if (s[i] != t[i]) {
return false;
}
}
return true;
}

程序编译没有任何问题,但运行出错,提示Segmentation fault (core dumped)。咦!好像见过,是不是哪个社区来着。查了查维基,存储器段错误会出现在当程序企图访问CPU无法定址的存储器区块时。

产生Segmentation fault的情景

stackoverflow上的一个回答有更详细的解释,存储器段错误是由于访问没有权限的内存而导致的一种错误,它可以防止破坏内存和引入难调试的内存bug。
在C语言中有很多情景都会导致存储器段错误,如对一个空指针解引用(dereference),

1
2
int *p = NULL;
*p = 1;

另一种常见原因是对只读内存区域执行写操作,这也是上段程序产生bug的原因。

1
2
char *str = "Foo";
*str = 'b';

还有一种就是悬空指针,它指向根本不存在的东西。

1
2
3
4
5
char *p = NULL;
{
char c;
p = &c;
}

p是一个悬空指针,因为变量c是代码块作用域,代码执行后,就被销毁了,不复存在。此时,如果对p进行解引用,就可能会出现存储器段错误,此处的代码在gcc下并没有报错,是因为程序简单。

解决问题

st是字符串常量,是不可修改的,我想对它重新排序,势必需要改变字符串常量。解决办法就是复制一份,对复制后的字符数组排序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
bool isAnagram(char* s, char* t) {
int i;
int s_len;
int t_len;
char *s_cpy;
char *t_cpy;

s_len = strlen(s);
t_len = strlen(t);
s_cpy = (char *)malloc(sizeof(char)*s_len);
t_cpy = (char *)malloc(sizeof(char)*t_len);
strcpy(s_cpy, s);
strcpy(t_cpy, t);

if (s_len != t_len) {
return false;
}
qsort(s_cpy, s_len, sizeof(s_cpy[0]), charcmp);
qsort(t_cpy, t_len, sizeof(t_cpy[0]), charcmp);
for (i = 0; i < s_len; i++) {
if (s_cpy[i] != t_cpy[i]) {
return false;
}
}
return true;
}

问题解决了,不过对于这个问题还有更好的算法,使用哈希表。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
bool isAnagram(char* s, char* t) {
char alphabet[26];
char *ptr;
int i;

for (i = 0; i < 26; i++) {
alphabet[i] = 0;
}
for (ptr = s; *ptr != '\0'; ptr++) {
alphabet[*ptr-'a']++;
}
for (ptr = t; *ptr != '\0'; ptr++) {
alphabet[*ptr-'a']--;
}
for (i = 0; i < 26; i++) {
if (alphabet[i] != 0) {
return false;
}
}
return true;
}

排序是需要成本的,使用哈希表就可以节省下这个资源,性能就快了不少,哈希是4ms,上一个排序则是24ms。


参考资料

Copyright © 2021 DukeLuo Blog

Powered by Hexo • Theme Candelas