编程语言

一道Leetcode题引起的思考：Segmentation fault是什么？

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

什么是Segmentation fault

我看到这个题目的第一印象就是对字符串s和t中的字母排序，然后逐一比对，如果全部相同，就返回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下并没有报错，是因为程序简单。

解决问题

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

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。

参考资料