数据结构DAY4--哈希表

哈希表

概念：相当于字典，可以根据数据的关键字来寻找相关数据的查找表。

步骤：建立->插入->遍历->查找->销毁

建立

建立数据，形式随意，但一般为结构体（储存的数据量大）；建立表结构体，包括储存数据的数据为和表结构体类型的指针（用于指向下一位）。

typedef struct hsnode
{DATA_TYPE data;struct hsnode *pnext;
}HASH_NODE;

接着用该结构体定义出一个大小为HASN_SIZE的哈希表：

HASH_NODE *hash_table[HASN_SIZE] = {NULL};

建立查找方法：根据具体的数据使用不同的方法，如汉字拼音可用拼音首子母来查找，将拼音转化为数字，根据数字来搜寻所需的数据域所对应的其余数据。

int hash_fun(char ch)
{if (ch >= 'a' && ch <= 'z'){return ch-'a';}else if (ch >= 'A' && ch <= 'Z'){return ch-'A';}else{return HASN_SIZE-1;}
}

插入

用表结构体定义一个大小为结构体大小的指针结点，使其数据域为输入的数据，后驱指针指向空，用建立的查找方法获得该结构体的角标，然后使后驱指针指向角标为获得的角标的哈希表，并使该表值为带新数据的表头。

int insert_hash_table(DATA_TYPE data)
{HASH_NODE *pnode = malloc(sizeof(HASH_NODE));if (NULL == pnode){perror("fail malloc");return -1;}pnode->data = data;pnode->pnext = NULL;int addr = hash_fun(data.name[0]);pnode->pnext = hash_table[addr];hash_table[addr] = pnode;return 0;
}

遍历

用循环来遍历表头，在循环内，建立一个指针，指向哈希表，再建立一个循环，若哈希表不指向空，就遍历该表，并打印表的内容。

void hash_for_each()
{for (int i = 0; i < HASN_SIZE; i++){HASH_NODE *ptmp = hash_table[i];while (ptmp != NULL){printf("%s %s %s %d\n", ptmp->data.name, ptmp->data.tel, ptmp->data.addr, ptmp->data.age);ptmp = ptmp->pnext;}printf("\n");}
}

查找

用表结构体定义一个指针，其值为角标为自定义的哈希函数的返回值的哈希表，只要其表结点不为空，就对比输入的搜索条件与表数据域相关内容，相同则返回，不同则使指针指向后驱结点继续对比

HASH_NODE *find_hash_table(char *name)
{int addr = hash_fun(name[0]);HASH_NODE *ptmp = hash_table[addr];while (ptmp != NULL){if (!strcmp(name, ptmp->data.name)){return ptmp;}ptmp = ptmp->pnext;}return NULL;
}

销毁

用表结构体定义一个指针，设置一个循环次数为哈希表长度的循环，再嵌套一个循环，若角标为循环次数的哈希表不为空（循环条件），则使指针等于角标为循环次数的哈希表，并使该哈希表值为指针的后驱结点，最后释放指针即可

void destroy_hash_table()
{HASH_NODE *ptmp = NULL;for (int i = 0; i < HASN_SIZE; i++){while(hash_table[i] != NULL){ptmp = hash_table[i];hash_table[i] = ptmp->pnext;free(ptmp);}}}