哈希表的建立与运用C语言实现

共13个文件

pdb：2个

dsp：1个

opt：1个

4星 · 超过85%的资源需积分: 49 30 浏览量 2009-12-12 16:18:18 上传评论 3 收藏 167KB RAR 举报

哈希表（Hash Table）是一种数据结构，它通过一种特定的函数——哈希函数，将键（Key）映射到数组的索引位置，从而实现快速查找、插入和删除操作。在C语言中，实现哈希表需要理解其基本原理和步骤，并熟练掌握C语言的动态内存管理和指针操作。哈希函数是哈希表的核心，它的目标是将键转化为数组下标，通常要求哈希函数尽可能均匀分布，避免冲突。常见的哈希函数设计方法有直接取模法、平方取中法、除留余数法等。在C语言中，可以使用整数运算来实现这些算法。哈希表的冲突解决策略主要有两种：开放寻址法和链地址法。开放寻址法是指当发生冲突时，寻找下一个空的哈希地址，直至找到为止；链地址法则是为每个哈希桶（数组元素）维护一个链表，将所有哈希到同一位置的元素链接在一起。在C语言中，构建哈希表的基本步骤如下： 1. 定义哈希表结构：创建一个包含数组和每个元素结构体的结构体，元素结构体包含键和值，以及可能的链表指针。 ```c typedef struct HashNode { int key; void* value; struct HashNode* next; } HashNode; typedef struct HashTable { int size; HashNode** table; } HashTable; ``` 2. 初始化哈希表：分配内存并初始化所有元素为空。 ```c HashTable* initHashTable(int size) { HashTable* hashTable = (HashTable*)malloc(sizeof(HashTable)); hashTable->size = size; hashTable->table = (HashNode**)calloc(size, sizeof(HashNode*)); return hashTable; } ``` 3. 计算哈希值：根据键计算哈希值，确保其在数组范围内。 ```c int hashFunction(int key, int size) { return key % size; // 直接取模法 } ``` 4. 插入元素：使用哈希函数找到插入位置，处理冲突。 ```c void insert(HashTable* hashTable, int key, void* value) { int index = hashFunction(key, hashTable->size); HashNode* newNode = (HashNode*)malloc(sizeof(HashNode)); newNode->key = key; newNode->value = value; newNode->next = hashTable->table[index]; hashTable->table[index] = newNode; } ``` 5. 查找元素：同样通过哈希函数找到位置，遍历链表找到对应的键。 ```c void* search(HashTable* hashTable, int key) { int index = hashFunction(key, hashTable->size); HashNode* current = hashTable->table[index]; while (current != NULL) { if (current->key == key) { return current->value; } current = current->next; } return NULL; // 键不存在 } ``` 6. 删除元素：找到对应键的节点，更新链表。 ```c void delete(HashTable* hashTable, int key) { int index = hashFunction(key, hashTable->size); HashNode* current = hashTable->table[index]; HashNode* prev = NULL; while (current != NULL && current->key != key) { prev = current; current = current->next; } if (current != NULL) { if (prev == NULL) { hashTable->table[index] = current->next; } else { prev->next = current->next; } free(current); } } ``` 7. 释放哈希表：释放所有内存。 ```c void destroyHashTable(HashTable* hashTable) { for (int i = 0; i < hashTable->size; i++) { HashNode* current = hashTable->table[i]; while (current != NULL) { HashNode* temp = current; current = current->next; free(temp); } } free(hashTable->table); free(hashTable); } ``` 以上就是使用C语言实现哈希表的基本流程和关键操作。实际应用中，还需要考虑负载因子、动态扩容等问题，以确保哈希表的性能。通过理解和实践这些知识点，可以深入掌握哈希表的工作原理，提高程序的效率。

资源推荐

资源详情

资源评论

收起资源包目录

C语言实现.rar （13个子文件）

哈希表的建立与运用C语言实现

哈希表的建立与运用.c 4KB

哈希表的建立与运用.ncb 33KB

Debug

哈希表的建立与运用.exe 184KB

哈希表的建立与运用.pch 211KB

vc60.pdb 44KB

哈希表的建立与运用.obj 6KB

vc60.idb 33KB

哈希表的建立与运用.ilk 182KB

哈希表的建立与运用.pdb 345KB

哈希表的建立与运用.dsw 561B

哈希表的建立与运用.dsp 3KB

哈希表的建立与运用.opt 48KB

哈希表的建立与运用.plg 270B

////1 哈希表操作，采用线性探测法处理冲突 ////采用除留余数法定义哈希表，哈希表长度为10，哈希函数为H(key)=key%13。产生冲突时采用线性探测法实现下面要求的功能。 ////（1）初始化哈希表,置空哈希表 ////（2）在哈希表中查找元素 ////（3）在哈希表中插入元素 ////（4）输出哈希表中所有元素 ////（5）建立Hash表 #include "stdio.h" #define M 13 #define N 12 struct hterm { int key;//关键字值 int si;//散列次数 }; struct hterm hashlist[M+1]; int i,address,sum,d,x[N+1]; float average; main() { for(i=1;i<=M;i++)//置初值 { hashlist[i].key=0; hashlist[i].si=0; } x[1]=19;x[2]=14;x[3]=23;x[4]=1; x[5]=68;x[6]=20;x[7]=84;x[8]=27; x[9]=55;x[10]=11;x[11]=10;x[12]=79; for(i=1;i<=N;i++) { sum=0; address=x[i]%M; d=address; if(hashlist[address].key==0) { hashlist[address].key=x[i]; hashlist[address].si=1; } else { do //处理冲突 { d=(d+1)%M; sum=sum+1; }while (hashlist[d].key!=0); hashlist[d].key=x[i]; hashlist[d].si=sum+1; } } printf("散列表地址： "); for(i=0;i<M;i++) printf("%-4d",i); printf("\n"); printf("散列表关键字："); for(i=0;i<M;i++) printf("%-4d",hashlist[i].key); printf("\n"); printf("查找长度： "); for(i=0;i<M;i++) printf("%-4d",hashlist[i].si); printf("\n"); average=0; for(i=0;i<M;i++) average=average+hashlist[i].si; average=average/N; printf("平均查找长度：ASL(%d)=%g",N,average); } // //#include <stdio.h> //#include <malloc.h> //#include <stdio.h> // ///**** 哈希表类型的定义****/ //#define NIL 0 // 用NIL作为空闲单元的标志 //#define DelNIL -1 // 用DelNIL作为已删除单元的标志 //#define m 13 // mod number //#define n 20 //hash 长度 // // //typedef struct //{ // int key; //关键字 //}LHashTable; // ///****初始化哈希表****/ //void HashListInit(LHashTable HT[n]) //{ // int i; // for(i=0;i<n;i++) //初始化关键字-0 // HT[i].key=NIL; //} // ///**** 清空哈希表 ****/ //void HashListClear (LHashTable HT[]) //{ // int i; // for(i=0;i<n;i++) // 关键字-0 // HT[i].key=NIL; //} // ///****定义哈希函数****/ //int Hash(int k) // 返回余数 //{ // return (k%m); //} // ///****在哈希表中查找元素****/ //int HashListSearch(LHashTable HT[n],int k) // -1:没有找到,other-找到 //{ // int d,temp; // d=Hash(k); // 计算k的哈希地址 // temp=d; // temp暂存k的哈希地址 // while(HT[d].key!=NIL) // { // if(HT[d].key==k) // return d; // 在哈希表中查找到元素k // else // d=(d+1)%n; // 没找到进行线性探测法继续查找 // if(d==temp) // return -1; //哈希中没有待查元素k // } // return -1; //} // ///****在哈希表中插入一个元素****/ //void HashListInsert(LHashTable HT[n],int k) //{ // int d,temp; // d=Hash(k); // 计算k的哈希地址 // temp=d; //temp暂存k的哈希地址 // while(HT[d].key!=NIL&&HT[d].key!=DelNIL) // 当前位置已有元素 // { // d=(d+1)%n; //进行线性探测 // if(d==temp) // { // printf("哈希表已满\n"); // 哈希表已满 // exit(1); //退出 // } // } // HT[d].key=k; // 插入k //} // ///***从哈希表中删除元素****/ //void HashListDelete(LHashTable HT[n],int k) //{int d,temp; // d=Hash(k); // temp=d; // while(HT[d].key!=NIL) // { // if(HT[d].key==k) // { // HT[d].key=DelNIL; // 找到k，删除标志 // return ; // } // else // d=(d+1)%n; //当前位置没找到k，进行线性探测 // if(d==temp) // break; // } // printf("哈希表中无待删除元素%d",k); // exit(1); //} // ///****输出哈希表中所有元素****/ //void PrintHashList(LHashTable HT[n]) //{ // int i; // for(i=0;i<n;i++) // printf(" %d ",i); // printf("\n"); // for(i=0;i<n;i++) // printf(" %d ",HT[i]); //} // // // // // // //main() //{ // // int k,i; // LHashTable HT[n]; // HashListInit(HT); // 初始化 // // for(i=1;i<13;i++) // 给 hash 赋值 // HashListInsert(HT,i); // // HashListInsert(HT,13); // 0 // HashListInsert(HT,13); // 0 // HashListInsert(HT,26); // 0 // HashListInsert(HT,39); // 0 // HashListInsert(HT,17); // HashListInsert(HT,14); // // printf("所建立的哈希表长为20\n"); // printf("所建立的哈希表为:\n"); // PrintHashList(HT); // printf("\n"); // printf("请输入要删除的关键字:"); // scanf("%d",&k); // HashListDelete(HT,k); // printf("删除成功后的哈希表为:\n"); // PrintHashList(HT); //system("pause"); // //}

评论收藏

内容反馈