分离连接法 散列

最简单的一个散列表示

头文件

#ifndef _Hash_H #define _Hash_H struct ListNode; struct HashTbl; typedef struct ListNode *Position; typedef struct HashTbl *HashTable; typedef int Item; HashTable initial(int tableSize); void destroy(HashTable H); Position find(Item x,HashTable H); void insert(Item x,HashTable H); void deleteItem(Item item,HashTable H); #endif struct ListNode{ Item item; Position next; }; typedef Position List; struct HashTbl{ int size; List *theList; };源文件

#include"hash.h" #include<stdio.h> #include<stdlib.h> #define MinSize 10 static int hash(int key,int tableSize){ return key%tableSize; } HashTable initial(int tableSize){ if(tableSize <MinSize ){ printf("given size too small"); return NULL; } HashTable H=malloc(sizeof(struct HashTbl)); if(H==NULL){ printf("arrange hashtbl fail"); return NULL; } H->size=tableSize; H->theList=malloc(sizeof(List)*H->size); if(H->theList==NULL){ printf("arrange thelist fail"); free(H); return NULL; } int i; for(i=0;i<H->size;i++){ H->theList[i]=malloc(sizeof(struct ListNode)); if(H->theList[i]==NULL){ printf("arrange listnode fail"); free(H->theList); free(H); } H->theList[i]->next=NULL; } return H; } void destroy(HashTable H){ int i; Position head,p,tmp; for(i=0;i<H->size;i++){ head=H->theList[i]; p=head->next; head->next=NULL; while(p){ tmp=p->next; free(p); p=tmp; } } } Position find(Item x,HashTable H){ Position p = H->theList[hash(x,H->size)]; p=p->next; while(p && p->item != x){ p=p->next; } return p; } void insert(Item x,HashTable H){ Position tmp,head; Position p = find(x,H); if(p==NULL){ tmp=malloc(sizeof(struct ListNode)); if(tmp==NULL){ printf("insert key fail"); return ; } tmp->item=x; head=H->theList[hash(x,H->size)]; tmp->next=head->next; head->next=tmp; } } void deleteItem(Item item,HashTable H){ Position head,p,tmp; head=H->theList[hash(item,H->size)]; p=head; while(p->next && p->next->item != item){ p=p->next; } if(p->next==NULL){ printf("no such a key"); return ; } else { tmp=p->next; p->next=tmp->next; free(tmp); } } 测试例程

#include"hash.h" #include<stdio.h> #include<stdlib.h> int main(){ HashTable table; Position p; table=initial(19); insert(0,table); insert(1,table); insert(81,table); insert(4,table); insert(64,table); insert(25,table); insert(16,table); insert(36,table); insert(9,table); insert(49,table); p=find(81,table); if(p==NULL) printf("cant find 1\n"); else printf("find %d \n",p->item); deleteItem(81,table); p=find(81,table); if(p==NULL) printf("cant find 81\n"); else printf("find %d \n",p->item); destroy(table); p=find(81,table); if(p==NULL) printf("cant find 81\n"); else printf("find %d \n",p->item); }