C中如何正确使用指针

Question

我正在尝试将（键、值）对添加到散列图中，但在插入后无法访问这些值。

这个散列 table 应该处理冲突，因为每当发生冲突时我都会遍历每个散列索引。然后，当我到达该索引处的 (key, value) 对列表的末尾时，我将其插入。

本质上是一个基本的链表hashmap。

问题是，当我尝试再次访问该值时，我总是遇到分段错误（而且我的 showTable() 函数也失败了）。在此测试中，我只是尝试在每个哈希索引处添加内容后访问第一个（键，值）对。我可能在做一些非常愚蠢的事情，但我看到了。

我还没有发表评论，但我希望代码是不言自明的。重要的一点是 InsertKeyValuePair() 但我已经添加了所有内容，因为代码审查也将是有益的。

#include <stdlib.h>
#include <stdio.h>

typedef struct TVal KeyValue;

typedef struct TVal {
    char *value;
    char *key;
    KeyValue *next;
} KeyValue;

typedef KeyValue **HashTable;

int MAX_SIZE = 200;

int HashKey(char *Key, int Max);
void InsertKeyValuePair(char *key, char *value, int Index, HashTable table);
int insert(char *Key, char *value, HashTable table, int size);
void showTable(HashTable table, int size);

int HashKey(char *Key, int Max) {
    char c = *Key;
    int Hash = 0;
    int n = 1;

    while (c != 0) {
        Hash += n * ((int)c);
        c = *(Key + n);
        n++;
    }

    return Hash % MAX_SIZE;
}

void InsertKeyValuePair(char *key, char *value, int Index, HashTable table) {
    KeyValue *cursor = *(table + Index);
    while (cursor != NULL) {
        cursor = cursor->next;
    }
    cursor = malloc(sizeof(KeyValue));
    cursor->value = value;
    cursor->key = key;
    printf("insert <K,V>(%s,%s) HashIndex = %i\n", cursor->key, cursor->value, Index);

    //Trying to access value previously inserted
    KeyValue *cursor2 = *(table + Index);
    printf("<K,V>(%s,%s)\n", cursor2->key, cursor2->value);
}

int insert(char *Key, char *value, HashTable table, int size) {
    int Index = HashKey(Key, MAX_SIZE);
    InsertKeyValuePair(Key, value, Index, table);
    return size + 1;
}

void showTable(HashTable table, int size) {
    int i;
    for (i = 0; i < size; i++) {
        KeyValue *cursor = *(table + i);

        if (cursor == NULL) 
            continue;

        while (cursor != NULL) {
            printf("==============");
            printf("<K,V>(%s,%s)\n", cursor->key, cursor->value);
            cursor = cursor->next;
        }   
        printf("==============");
    }
}

int main() {
    HashTable HTbl = malloc(sizeof(HashTable) * MAX_SIZE);
    int size = 0;

    size = insert("yeuydfdan", "wesfg", HTbl, size);
    size = insert("ywere", "rdgg", HTbl, size);
    size = insert("ye4", "3244", HTbl, size);

    //showTable(HTbl, MAX_SIZE);
}

Answer 1

此声明

HashTable HTbl = malloc(sizeof(HashTable)*MAX_SIZE);

不正确，而且分配的内存未初始化。应该有

HashTable HTbl = calloc( MAX_SIZE, sizeof( KeyValue * ) );

或喜欢

HashTable HTbl = calloc( MAX_SIZE, sizeof( *HTbl ) );

table 中的索引应计算为某个无符号整数。否则通常你会得到一个负指数。

函数HashKey中参数Max未使用。

在函数 InsertKeyValuePair 中更改了局部变量 cursor 而不是数据成员 cursor->next 或 *(table+Index).

函数showTable中的循环应该在循环条件中使用MAX_SIZE而不是size。也就是说，您必须将 MAX_SIZE 的值作为参数传递，而不是 size.

的值

这是一个演示程序，展示了如何更新程序。

#include <stdio.h>
#include <stdlib.h>

typedef struct TVal KeyValue;

typedef struct TVal 
{
    const char *value;
    const char *key;
    KeyValue *next;
} KeyValue;


typedef KeyValue **HashTable;

const size_t MAX_SIZE = 200;

static size_t HashKey( const char *key, size_t max_slots ) 
{
    size_t Hash = 0;

    for ( size_t i = 0; key[i]; i++ ) Hash += ( i + 1 ) * ( unsigned char )key[i];

    return Hash % max_slots;
}

static int InsertKeyValuePair( HashTable table, const char *key, const char *value, size_t index ) 
{
    KeyValue **cursor = &table[index];

    while ( *cursor != NULL ) cursor = &( *cursor )->next;

    *cursor = malloc( sizeof( KeyValue ) );

    int success = *cursor != NULL;

    if ( success )
    {
        ( *cursor )->value = value;
        ( *cursor )->key = key;
        ( *cursor )->next = NULL;
    }

    return success;
}

int insert( HashTable table, const char *key, const char *value, size_t *size ) 
{
    size_t index = HashKey( key, MAX_SIZE );

    int success = InsertKeyValuePair( table, key, value, index );

    if ( success ) ++*size;

    return success;
}

void showTable( HashTable table, size_t size )
{
    for ( size_t i = 0; i < size; i++ )
    {
        KeyValue *cursor = table[i];

        if ( cursor != NULL )
        {
            do
            {
                puts( "==============" );
                printf( "<K,V>(%s, %s)\n", cursor->key, cursor->value );
                cursor = cursor->next;
            } while ( cursor != NULL );

            puts( "==============\n" );
        }
    }        
}

int main( void )
{
    HashTable HTbl = calloc( MAX_SIZE, sizeof( *HTbl ) );

    size_t size = 0;

    insert( HTbl, "yeuydfdan", "wesfg", &size );
    insert( HTbl, "ywere", "rdgg", &size );
    insert( HTbl, "ye4", "3244", &size );

    showTable( HTbl, MAX_SIZE );
}

程序输出为

==============
<K,V>(ywere, rdgg)
==============

==============
<K,V>(ye4, 3244)
==============

==============
<K,V>(yeuydfdan, wesfg)
==============

当然你应该添加一些其他函数，例如删除 table 及其节点的函数。

如果每个节点都为一个键和一个值分配内存并将传递的参数复制到那里会更好。否则 table 通常只能处理字符串文字，因为它们具有静态存储持续时间。

如果您将重写 table 的实现，使其复制 table 节点中的键和值，则结构应定义为

typedef struct TVal KeyValue;

typedef struct TVal 
{
    char *value;
    const char *key;
    KeyValue *next;
} KeyValue;

也就是说，在任何情况下都不应更改密钥，并且应使用限定符 const.

进行声明

Answer 2

您的代码中存在多个问题：

散列 table 未初始化为 NULL，在尝试取消引用它包含的指针时导致分段错误。使用 calloc() 分配将解决此问题。
将指针隐藏在 typedef 后面会令人困惑且容易出错。
main 中的分配应为 HashTable HTbl = calloc(sizeof(*HTbl), MAX_SIZE);
InsertKeyValuePair 中的插入代码不会 link 末尾的新对，也不会在散列 table 存储桶列表的开头。
建议使用 unsigned 算法计算哈希键以避免溢出问题。
指针符号 *(table + Index) 令人困惑。您应该改用数组表示法 table[Index]。
散列的长度table (MAX_SIZE) 和散列中的条目数table (size) 之间似乎有些混淆。适当地重命名变量可以提高可读性。按地址传递计数和 return 成功指示符也可能更好。

这是更正后的版本：

#include <stdlib.h>
#include <stdio.h>

typedef struct TVal KeyValue;

typedef struct TVal {
    const char *value;
    const char *key;
    KeyValue *next;
} KeyValue;

typedef KeyValue **HashTable;

static unsigned int HASH_SIZE = 200;

static unsigned int HashKey(const char *key);
static KeyValue *InsertKeyValuePair(const char *key, const char *value, int index, HashTable table);
static int insert(const char *Key, const char *value, HashTable table, int *countp);
static void showTable(HashTable table);

static unsigned int HashKey(const char *key) {
    unsigned int hash = 0;
    size_t n;

    for (n = 0; key[n] != 0; n++) {
        hash += n * (unsigned char)key[n];
    }
    return hash % HASH_SIZE;
}

static KeyValue *InsertKeyValuePair(const char *key, const char *value, int index, HashTable table) {
    KeyValue *cursor;
    cursor = malloc(sizeof(KeyValue));
    if (cursor != NULL) {
        KeyValue **cursorp = &table[index];
        while (*cursorp != NULL) {
            cursorp = &(*cursorp)->next;
        }
        cursor->value = value;
        cursor->key = key;
        cursor->next = NULL;
        *cursorp = cursor;
    }
    return cursor;
}

static int insert(const char *key, const char *value, HashTable table, int *countp) {
    int index = HashKey(key);
    if (InsertKeyValuePair(key, value, index, table)) {
        *countp += 1;
        return 1;
    }
    return 0;
}

static void showTable(HashTable table) {
    unsigned int i;
    for (i = 0; i < HASH_SIZE; i++) {
        KeyValue *cursor = table[i];

        if (cursor == NULL)
            continue;

        while (cursor != NULL) {
            printf("==============");
            printf("<K,V>(%s,%s)\n", cursor->key, cursor->value);
            cursor = cursor->next;
        }
        printf("==============\n");
    }
}

int main() {
    HashTable HTbl = calloc(sizeof(*HTbl), HASH_SIZE);
    int count = 0;

    insert("yeuydfdan", "wesfg", HTbl, &count);
    insert("ywere", "rdgg", HTbl, &count);
    insert("ye4", "3244", HTbl, &count);

    showTable(HTbl);
    return 0;
}

C中如何正确使用指针

How to use pointers correctly in C

c

pointers

hashtable

linked-list

singly-linked-list