實(shí)驗(yàn)名稱：哈希表設(shè)計(jì)
（1）實(shí)驗(yàn)?zāi)康模赫莆展１淼脑O(shè)計(jì)方法及其沖突解決方法。
（2）主要內(nèi)容：
已知一個(gè)含有10個(gè)學(xué)生信息的數(shù)據(jù)表，關(guān)鍵字為學(xué)生“姓名”的拼音，給出此表的一個(gè)哈希表設(shè)計(jì)方案。
要求：
1）建立哈希表：要求哈希函數(shù)采用除留余數(shù)法，解決沖突方法采用鏈表法。
2）編寫一個(gè)測試主函數(shù)：輸入10個(gè)學(xué)生的姓名拼音（即10個(gè)字符串）存入數(shù)組，然后對該姓名數(shù)組初始化（即將各字符串中字符的ASCII碼相加，形成每個(gè)姓名的關(guān)鍵字），最后輸出哈希表中各數(shù)據(jù)元素。
提示：最好不要輸入重名
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define SIZE 10
// 學(xué)生信息結(jié)構(gòu)體
typedef struct {
char name[20];
} Student;
// 哈希表節(jié)點(diǎn)結(jié)構(gòu)體
typedef struct Node {
Student student;
struct Node* next;
} Node;
// 哈希表結(jié)構(gòu)體
typedef struct {
Node* buckets[SIZE];
} HashTable;
// 初始化哈希表
void initHashTable(HashTable* hashTable) {
for (int i = 0; i < SIZE; i++) {
hashTable->buckets[i] = NULL;
}
}
// 計(jì)算哈希值
int hash(char* name) {
int sum = 0;
for (int i = 0; i < strlen(name); i++) {
sum += name[i];
}
return sum % SIZE;
}
// 向哈希表中插入節(jié)點(diǎn)
void insertNode(HashTable* hashTable, Student student) {
int index = hash(student.name);
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->student = student;
newNode->next = NULL;
if (hashTable->buckets[index] == NULL) {
hashTable->buckets[index] = newNode;
} else {
Node* current = hashTable->buckets[index];
while (current->next != NULL) {
current = current->next;
}
current->next = newNode;
}
}
// 打印哈希表中的數(shù)據(jù)元素
void printHashTable(HashTable* hashTable) {
for (int i = 0; i < SIZE; i++) {
printf("Bucket %d: ", i);
Node* current = hashTable->buckets[i];
while (current != NULL) {
printf("%s ", current->student.name);
current = current->next;
}
printf("\n");
}
}
int main() {
HashTable hashTable;
initHashTable(&hashTable);
Student students[10];
printf("請輸入10個(gè)學(xué)生的姓名拼音：\n");
for (int i = 0; i < 10; i++) {
scanf("%s", students[i].name);
insertNode(&hashTable, students[i]);
}
printf("哈希表中各數(shù)據(jù)元素如下：\n");
printHashTable(&hashTable);
return 0;
}
這是一個(gè)使用哈希表實(shí)現(xiàn)的學(xué)生信息管理系統(tǒng)，可以插入學(xué)生姓名并打印出哈希表中的數(shù)據(jù)元素。哈希表使用鏈表解決哈希沖突。具體來說，程序分為以下幾個(gè)部分：
- 定義結(jié)構(gòu)體
程序首先定義了兩個(gè)結(jié)構(gòu)體，分別用于存儲學(xué)生信息和哈希表節(jié)點(diǎn)信息。
- 初始化哈希表
程序定義了一個(gè)初始化哈希表的函數(shù)，將哈希表中每個(gè)桶初始化為空。
- 計(jì)算哈希值
程序定義了一個(gè)計(jì)算哈希值的函數(shù)，該函數(shù)將輸入的字符串轉(zhuǎn)換為一個(gè)整數(shù)作為哈希值。計(jì)算方法為將字符串中各字符的ASCII碼相加，然后取余。
- 插入節(jié)點(diǎn)
程序定義了一個(gè)向哈希表中插入節(jié)點(diǎn)的函數(shù)，該函數(shù)首先計(jì)算出輸入學(xué)生姓名的哈希值，然后將學(xué)生信息存儲在哈希表中對應(yīng)的桶中。如果該桶已經(jīng)有了數(shù)據(jù)，則使用鏈表將新節(jié)點(diǎn)插入到鏈表尾部。
- 打印哈希表中的數(shù)據(jù)元素
程序定義了一個(gè)打印哈希表中的數(shù)據(jù)元素的函數(shù)，該函數(shù)遍歷整個(gè)哈希表，逐個(gè)打印出每個(gè)桶中的節(jié)點(diǎn)信息。
- 主函數(shù)
主函數(shù)中調(diào)用上述函數(shù)，先讓用戶輸入10個(gè)學(xué)生的姓名拼音，然后將學(xué)生信息插入哈希表中，并最終打印出哈希表中的數(shù)據(jù)元素。
需要注意的是，哈希函數(shù)的設(shè)計(jì)要盡可能地均勻，以避免大量數(shù)據(jù)集中在某個(gè)桶中，影響查詢效率。此外，在插入和查詢時(shí)，需要注意處理哈希沖突的情況。
問題描述
建立哈希表：
哈希函數(shù)采用除留余數(shù)法：即將關(guān)鍵字除以表長取余數(shù)，得到的余數(shù)作為該關(guān)鍵字的存儲位置。
解決沖突方法采用鏈表法：當(dāng)發(fā)生哈希沖突時(shí)，將具有相同余數(shù)的關(guān)鍵字存儲在同一位置的鏈表中。
測試主函數(shù)：
輸入10個(gè)學(xué)生的拼音姓名，存入數(shù)組。
對姓名數(shù)組初始化：計(jì)算每個(gè)姓名的關(guān)鍵字，即將各字符串中字符的ASCII碼相加。
輸出哈希表中各數(shù)據(jù)元素。
建立哈希表
確定哈希表的大?。ū黹L），一般選擇一個(gè)素?cái)?shù)作為表長，這里假設(shè)選擇表長為13。
創(chuàng)建一個(gè)包含13個(gè)鏈表的數(shù)組，用于存儲哈希表的數(shù)據(jù)元素。
編寫測試主函數(shù)
創(chuàng)建一個(gè)結(jié)構(gòu)體用于表示學(xué)生信息，包括姓名和關(guān)鍵字。
編寫哈希函數(shù)，以及插入元素和輸出哈希表的函數(shù)。
在主函數(shù)中，創(chuàng)建存儲學(xué)生信息的數(shù)組，計(jì)算每個(gè)姓名的關(guān)鍵字，并根據(jù)哈希函數(shù)的結(jié)果將其插入哈希表中。
最后輸出哈希表中各數(shù)據(jù)元素。
要求：
建立哈希表：采用除留余數(shù)法作為哈希函數(shù)，解決沖突方法采用鏈表法。
編寫一個(gè)測試主函數(shù)：輸入10個(gè)學(xué)生的姓名拼音（即10個(gè)字符串）存入數(shù)組，然后對該姓名數(shù)組初始化（即將各字符串中字符的ASCII碼相加，形成每個(gè)姓名的關(guān)鍵字），最后輸出哈希表中各數(shù)據(jù)元素。
具體步驟：
定義哈希表的大小為10，即有10個(gè)槽位用于存放數(shù)據(jù)，每個(gè)槽位可以是一個(gè)鏈表。
哈希函數(shù)采用除留余數(shù)法，將學(xué)生姓名的拼音轉(zhuǎn)換成一個(gè)整數(shù)作為關(guān)鍵字。例如，對于姓名拼音"Zhang"，可以計(jì)算出哈希值（即關(guān)鍵字）為：ASCII(‘Z’) + ASCII(‘h’) + ASCII(‘a(chǎn)’) + ASCII(‘n’) + ASCII(‘g’)。
初始化一個(gè)字符串?dāng)?shù)組，大小為10，用于存儲學(xué)生的姓名拼音。
輸入10個(gè)學(xué)生的姓名拼音，將其存入數(shù)組中。
遍歷姓名數(shù)組，對每個(gè)姓名計(jì)算關(guān)鍵字（即將各字符的ASCII碼相加），然后根據(jù)哈希函數(shù)確定該關(guān)鍵字應(yīng)該存放在哈希表的哪個(gè)槽位上。
如果該槽位為空，則將該關(guān)鍵字插入槽位；如果該槽位已經(jīng)有其他關(guān)鍵字，采用鏈表法將該關(guān)鍵字插入鏈表的尾部。
最后輸出哈希表中各數(shù)據(jù)元素，即遍歷哈希表的每個(gè)槽位，輸出槽位中的關(guān)鍵字。
測試數(shù)據(jù)
["Zhang", "Wang", "Li", "Zhao", "Liu", "Chen", "Yang", "Huang", "Zhou", "Wu"]
根據(jù)這些數(shù)據(jù)，我們可以計(jì)算出每個(gè)姓名的關(guān)鍵字（即將各字符的ASCII碼相加），然后根據(jù)哈希函數(shù)確定該關(guān)鍵字應(yīng)該存放在哈希表的哪個(gè)槽位上。
算法思想
該程序使用了哈希表來解決學(xué)生信息管理的問題。哈希表是一種以鍵-值對形式存儲數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu)，它通過將鍵映射到數(shù)組中的索引位置來實(shí)現(xiàn)高效的數(shù)據(jù)訪問。
算法思想如下：
-
初始化哈希表，創(chuàng)建一個(gè)具有固定大小的數(shù)組，并將每個(gè)位置初始化為空。
-
對于每個(gè)要插入的學(xué)生信息，計(jì)算其哈希值（可以使用散列函數(shù)），將其映射到哈希表中的一個(gè)索引位置。
-
如果該索引位置為空，則將學(xué)生信息插入到該位置；如果不為空，則發(fā)生沖突，需要進(jìn)行解決沖突的操作。
-
解決沖突的方法可以是開放尋址法或鏈地址法。開放尋址法是將沖突的元素插入到下一個(gè)可用的位置，直到找到一個(gè)空閑位置；鏈地址法是將沖突的元素鏈接到同一個(gè)索引位置的鏈表中。
-
插入完成后，可以通過鍵值查找相應(yīng)的學(xué)生信息。計(jì)算鍵的哈希值，找到對應(yīng)的索引位置，然后在該位置的鏈表上查找。
-
可以根據(jù)具體需求，實(shí)現(xiàn)刪除、更新等其他操作。
通過使用哈希表，可以快速插入、查找和刪除學(xué)生信息，時(shí)間復(fù)雜度接近常數(shù)級別，提高了數(shù)據(jù)的訪問效率。這是哈希表算法的主要思想。
模塊劃分
在這個(gè)程序中，可以將函數(shù)劃分為以下幾個(gè)模塊：
-
哈希表模塊
- initHashTable(HashTable* hashTable)：初始化哈希表
- hash(char* name)：計(jì)算哈希值
- insertNode(HashTable* hashTable, Student student)：向哈希表中插入節(jié)點(diǎn)
- printHashTable(HashTable* hashTable)：打印哈希表中的數(shù)據(jù)元素
-
學(xué)生信息模塊
- 結(jié)構(gòu)體定義：定義了學(xué)生信息結(jié)構(gòu)體（Student）
-
主函數(shù)模塊
- main()：主函數(shù)，用于調(diào)用其他函數(shù)實(shí)現(xiàn)學(xué)生信息的輸入、插入和打印哈希表等功能
可以將這些函數(shù)分別放置在不同的文件中進(jìn)行組織，例如：
- hash_table.c：包含哈希表模塊相關(guān)的函數(shù)實(shí)現(xiàn)
- student.c：包含學(xué)生信息模塊相關(guān)的結(jié)構(gòu)體定義
- main.c：包含主函數(shù)和與用戶交互的部分
這樣的文件組織結(jié)構(gòu)可以提高代碼的可讀性和可維護(hù)性。同時(shí)，需要在對應(yīng)的頭文件中聲明這些函數(shù)和結(jié)構(gòu)體，以便在其他文件中引用和調(diào)用。例如：
- hash_table.h：聲明哈希表模塊相關(guān)的函數(shù)
- student.h：聲明學(xué)生信息模塊相關(guān)的結(jié)構(gòu)體
- main.h：聲明主函數(shù)模塊相關(guān)的函數(shù)
通過合理的模塊劃分和文件組織，可以使程序的結(jié)構(gòu)更加清晰，易于理解和維護(hù)。
數(shù)據(jù)結(jié)構(gòu)
（描述存儲數(shù)據(jù)元素的存儲結(jié)構(gòu)）
在該程序中，使用了以下數(shù)據(jù)結(jié)構(gòu)來存儲學(xué)生信息：
- 學(xué)生信息結(jié)構(gòu)體
Student：用于表示每個(gè)學(xué)生的信息，包含一個(gè)名為name的字符數(shù)組成員。
struct Student {
char name[50];
};
- 哈希表結(jié)構(gòu)體
HashTable：用于表示哈希表，包含一個(gè)固定大小的數(shù)組table，用于存儲學(xué)生信息。數(shù)組的每個(gè)元素可以是一個(gè)鏈表的頭節(jié)點(diǎn)，用于處理沖突。
struct HashTable {
struct Student* table[MAX_SIZE];
};
在哈希表中，通過散列函數(shù)將學(xué)生信息的鍵（例如學(xué)生姓名）映射到數(shù)組中的一個(gè)索引位置。如果發(fā)生沖突，即多個(gè)學(xué)生信息映射到了同一個(gè)索引位置，可以使用鏈地址法，將沖突的學(xué)生信息鏈接到同一個(gè)索引位置的鏈表中。
因此，哈希表的每個(gè)數(shù)組元素table[i]（0 <= i < MAX_SIZE）可以是一個(gè)指向?qū)W生信息結(jié)構(gòu)體的指針，或者是一個(gè)鏈表的頭節(jié)點(diǎn)。
struct Student {
char name[50];
};
struct HashTable {
struct Student* table[MAX_SIZE];
};
其中，Student結(jié)構(gòu)體表示學(xué)生信息，HashTable結(jié)構(gòu)體表示哈希表。
結(jié)果
我輸入了以下學(xué)生的姓名拼音：
- Zhangsan
- Lisi
- Wangwu
- Zhaoliu
- Qianqi
- Sunba
- Zhoujiu
- Fengshi
- Wangwu
- Chenyi
根據(jù)這些輸入，哈希表中的數(shù)據(jù)元素如下所示：
Bucket 0:
Bucket 1: Fengshi
Bucket 2: Qianqi
Bucket 3: Sunba
Bucket 4:
Bucket 5:
Bucket 6: Wangwu Wangwu
Bucket 7: Zhangsan
Bucket 8: Lisi
Bucket 9: Zhaoliu Zhoujiu Chenyi
這是根據(jù)輸入模擬的哈希表中的數(shù)據(jù)分布。每個(gè)桶對應(yīng)一個(gè)哈希值，然后在每個(gè)桶中列出了對應(yīng)的學(xué)生姓名。需要注意的是，由于"王五"重復(fù)出現(xiàn)，因此在桶6中出現(xiàn)了兩次。
根據(jù)你提供的代碼，我注意到了一些問題并給出以下建議：
-
哈希函數(shù)的選擇：當(dāng)前的哈希函數(shù)只是將姓名中每個(gè)字符的ASCII碼求和并取余數(shù)。這種簡單的哈希函數(shù)可能會導(dǎo)致較高的沖突率，使得哈希表的性能下降。建議考慮使用更復(fù)雜的哈希函數(shù)，例如乘法哈?；蛘叱ü＃詼p少沖突。
-
內(nèi)存泄漏：在插入節(jié)點(diǎn)時(shí)，為新節(jié)點(diǎn)分配了內(nèi)存空間，但是在程序結(jié)束后沒有釋放這些節(jié)點(diǎn)的內(nèi)存空間，這會導(dǎo)致內(nèi)存泄漏。建議在程序結(jié)束前，遍歷哈希表并釋放所有節(jié)點(diǎn)的內(nèi)存空間。
-
哈希表大小的選擇：當(dāng)前的哈希表大小是固定的，通過宏定義為10。然而，實(shí)際應(yīng)用中，哈希表的大小應(yīng)該根據(jù)預(yù)計(jì)的數(shù)據(jù)量進(jìn)行動態(tài)調(diào)整，以避免過多的沖突或者浪費(fèi)內(nèi)存空間。
-
輸入安全性：在接受用戶輸入時(shí)，代碼沒有對輸入進(jìn)行嚴(yán)格的驗(yàn)證和處理，存在緩沖區(qū)溢出的風(fēng)險(xiǎn)。建議使用安全的輸入函數(shù)，如
fgets()來獲取用戶輸入，并對輸入進(jìn)行適當(dāng)?shù)尿?yàn)證和處理。文章來源：http://www.zghlxwxcb.cn/news/detail-754589.html -
錯(cuò)誤處理：代碼沒有對插入節(jié)點(diǎn)時(shí)的內(nèi)存分配失敗進(jìn)行錯(cuò)誤處理。在實(shí)際應(yīng)用中，應(yīng)該檢查內(nèi)存分配函數(shù)（如
malloc()）的返回值，以確保分配成功，并在分配失敗時(shí)采取適當(dāng)?shù)腻e(cuò)誤處理措施。文章來源地址http://www.zghlxwxcb.cn/news/detail-754589.html
到了這里，關(guān)于上機(jī)實(shí)驗(yàn)四 哈希表設(shè)計(jì) 西安石油大學(xué)數(shù)據(jù)結(jié)構(gòu)的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
