首页 > 代码库 > 数据结构与算法分析-分离链接散列表的实现
数据结构与算法分析-分离链接散列表的实现
#include<stdio.h>#include<math.h>typedef char* ElementType;typedef unsigned int Index;#define MinTableSize 15struct ListNode;typedef struct ListNode *Position;struct HashTbl;typedef struct HashTbl *HashTable;HashTable InitializeTable(int TableSize);void DestroyTable(HashTable H);Position Find(ElementType key,HashTable H);void Insert(ElementType key,HashTable H);ElementType Retrieve(Position P);void Delete(ElementType key,HashTable H);struct ListNode{ ElementType Element; Position next;};typedef Position List;struct HashTbl{ int TableSize; List *TheLists;};Index Hash(const char *key,int TableSize){ unsigned int HashVal=0; while(*key!=‘\0‘) { HashVal+=*key++; } return HashVal%TableSize;}int NextPrime(int TableSize){ int i,j=2; for(i=TableSize;i>0;i--) { while(j<sqrt(i)) { if(i%j==0) break; j++; } if(j==sqrt(i)) break; } return i;}HashTable InitializeTable(int TableSize){ HashTable H; int i; if(TableSize<MinTableSize) { Error("Table size too small"); return NULL; } H=malloc(sizeof(struct HashTbl)); if(H==NULL) { FatalError("Out of space!!"); } H->TableSize=NextPrime(TableSize); H->TheLists=malloc(sizeof(List)*H->TableSize); if(H->TheLists==NULL) { FatalError("Out of space!!"); } for(i=0;i<H->TableSize;i++) { //分配头节点 H->TheLists[i]=malloc(sizeof(struct ListNode)); if(H->TheLists[i]==NULL) FatalError("Out of space!!"); else H->TheLists[i]->next=NULL; } return H;}void DestroyTable(HashTable H){ int i; for(i=0;i<H->TableSize;i++) { free(H->TheLists[i]); } free(H->TheLists); free(H);}Position Find(ElementType key,HashTable H){ Position P; List L; L=H->TheLists[Hash(key,H->TableSize)]; P=L->next; while(P!=NULL&&P->Element!=key) P=P->next; return P;}void Insert(ElementType key,HashTable H){ Position Pos,NewCell; List L; Pos=Find(key,H); if(Pos==NULL) { NewCell=malloc(sizeof(struct ListNode)); if(NewCell==NULL) { FatalError("Out of space!!"); } else { L=H->TheLists[Hash(key,H->TableSize)]; NewCell->next=L->next; NewCell->Element=key; L->next=NewCell; } }}ElementType Retrieve(Position P){ if(P==NULL) return NULL; else return P->Element;}void Delete(ElementType key,HashTable H){ Position Pos,Pre; List L; int i; Pos=Find(key,H); if(Pos==NULL) return; else { L=H->TheLists[Hash(key,H->TableSize)]; for(Pre=L;pre->next!=NUll;Pre=Pre->next) { if(Pre->next==Pos) { free(Pos->Element); free(Pos); break; } } }}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。