1

ハッシュ関数を実現するコードを書きました。リストに 9 番目の要素「a12a」を追加すると問題が発生し、gdb は次のように報告します。malloc によるメモリの適用中に問題が発生したようです。しかし、この 9 番目の要素を追加する前に、6 番目の要素「ad」を追加するときに malloc で 1 回のメモリの適用に成功したことがあるのに、2 回目のメモリの適用が失敗するのはなぜですか?

Breakpoint 1, insert (p=0x3d2d10, value=0x4030e8 "a12a") at hashop.c:39
39              id = hash(value);
(gdb) n
40              *current = p + id;
(gdb)
41              if((*current)->value == NULL) {
(gdb)
44                      if((lookup(p+id, value)) == NULL) {
(gdb)
45                              new = (nList *)malloc(sizeof(nList));
(gdb)

Program received signal SIGSEGV, Segmentation fault.
0x7c938996 in ntdll!RtlDuplicateUnicodeString ()
   from C:\WINDOWS\system32\ntdll.dll
(gdb)

そして私のコードは次のとおりです。

void insert(nList *p, char *value)
{
    nList *new, **current;
    int id;

    id = hash(value);
    *current = p + id;
    if((*current)->value == NULL) {
        (*current)->value = value;
    } else {
        if((lookup(p+id, value)) == NULL) {
            new = (nList *)malloc(sizeof(nList));
            new->value = value;
            new->next = NULL;       
            while((*current)->next != NULL) {
                (*current) =(*current)->next;
            }
            (*current)->next = new;
        }
    }
}   

static char *str2[] = {"ac", "ba", "abv", "bc", "bx", "ad", "xx", "aaa", "a12a", "b123"};

また、各要素のハッシュ ID は次のとおりです。

ac, HashId=6
ba, HashId=5
abv, HashId=3
bc, HashId=7
bx, HashId=8
ad, HashId=7
xx, HashId=0
aaa, HashId=1
a12a, HashId=3
b123, HashId=8

上記のリストから、「bc」と「ad」のハッシュ ID が同じであることは確かなので、insert() 関数で、「ad」を格納するためのメモリ ブロックを適用します。そして、「abv」や「a12a」も同様で、メモリのブロックを適用したのですが、今回は失敗しました。なんで？誰でも把握できますか？感謝！

4

2 に答える 2

4

次の行でメモリを破損しています：

*current = p + id;

gcc に渡し-Wallてすべての警告をオンにすると、次のように表示されます。

buggy-hash.c: In function ‘insert’:
buggy-hash.c:19:14: warning: ‘current’ is used uninitialized in this function [-Wuninitialized]

ヒント: Linux のValgrindのようgcc -Wallなメモリ デバッガでプログラムを使用および実行すると、これらのメモリの問題を簡単に見つけることができます。

Windows で CodeBlocks やその他の IDE を使用して C プログラミングを学習していると思いますか? Visual Studio でデバッグ モードでプログラムをビルドすると、これらの問題も検出されます。

于 2012-10-04T18:25:48.597 に答える
0

問題は、ルックアップ関数の入力として p+id を使用しましたが、p が *current によって既に変更されていることを忘れていたことです。したがって、正しいコードは次のとおりです。

void insert(nList *p, char *value)
{
    nList *new, **current = &p;
    int id;
    id = hash(value);
    *current += id;

    if((*current)->value == NULL) {
        (*current)->value = value;
    } else {
        if((lookup(*current, value)) == NULL) {
            new = (nList *)malloc(sizeof(nList));

            if(new == NULL)
                printf("\nCannot get memory");
            else {
                new->value = value;
                new->next = NULL;       

                while((*current)->next != NULL) {
                    (*current) =(*current)->next;
                }

                (*current)->next = new;
            }
        }
    }
}
于 2012-10-05T01:18:18.763 に答える