C語言資料結構雜湊表詳解

/*
 * 程式名：hash.c，此程式演示雜湊表的實現，資料元素單連結串列帶頭結點。
 * 
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
// 雜湊表中資料元素的結構體。
typedef struct Element
{
  unsigned int key; // 關鍵字。
  int value;        // 資料元素其它資料項，可以是任意資料型別。
  // char value[1001];        // 資料元素其它資料項，可以是任意資料型別。
}Element;
 
// 資料元素單連結串列。
typedef struct Node
{
  Element elem;      // 資料元素。
  struct Node *next; // next指標。
}Node;
 
// 雜湊表
typedef struct HashTable
{
  struct Node *head;  // 資料元素儲存基址，動態分配陣列。
  int tablesize;      // 雜湊表當前大小，即表長。
  int count;          // 雜湊表中資料元素的個數。
}HashTable;
 
// 初始化雜湊表，tablesize為雜湊表的表長，返回雜湊表的地址。
HashTable *InitHashTable(const unsigned int tablesize)
{
  // 分配雜湊表。
  HashTable *hh=(HashTable *)malloc(sizeof(HashTable));
 
  hh->tablesize=tablesize;  // 雜湊表長。
 
  // 分配和初始化資料元素單連結串列的頭結點。
  hh->head=(Node *)malloc((hh->tablesize)*sizeof(Node));
  memset(hh->head,0,(hh->tablesize)*sizeof(Node));
 
  hh->count=0;  // 雜湊表中資料元素個數置為0。
 
  return hh;
}
 
// 雜湊函數。
unsigned int Hash(HashTable *hh,unsigned int key)
{
  return key%hh->tablesize;  // 對錶長取餘。
}
 
// 在雜湊表中查詢關鍵字，成功返回單連結串列結點的地址，失敗返回空。
Node *LookUp(HashTable *hh,unsigned int key)
{
  int ii;
 
  ii=Hash(hh,key);  // 獲取關鍵key的雜湊地址。
 
  Node *pp=hh->head[ii].next;
 
  // 遍歷單連結串列。
  while( (pp!=NULL) && (pp->elem.key!=key) )
  {
    pp=pp->next;
  }
 
  return pp;
}
 
// 從雜湊表中刪除關鍵及其資料，成功返回1，如果關鍵字不存在返回0。
int Delete(HashTable *hh,unsigned int key)
{
  int ii;
 
  ii=Hash(hh,key);  // 獲取關鍵key的雜湊地址。
 
  Node *pp=&hh->head[ii];
 
  // 遍歷單連結串列，pp指標停留在待刪除關鍵key的前一結點。
  while( (pp->next!=NULL) && (pp->next->elem.key!=key) )
  {
    pp=pp->next;
  }
 
  if (pp->next==NULL) return 0;  // 查詢失敗。
 
  Node *tmp=pp->next;        // tmp為將要刪除的結點。
  pp->next=pp->next->next;   // 寫成p->next=tmp->next更簡潔。
 
  free(tmp);     // 釋放結點。
 
  hh->count--;   // 表中元素個數減1。
 
  return 1;
}
 
// 向雜湊表中插入資料元素，成功返回1，如果資料元素關鍵字已存在，返回0。
int Insert(HashTable *hh,Element *ee)
{
  // 查詢關鍵字是否已存在，如果存在，插入失敗。
  Node *pp=LookUp(hh,ee->key);
 
  if (pp!=NULL) { printf("關鍵字%d已存在。n",ee->key); return 0; }
  
  Node *qq=(Node *)malloc(sizeof(Node));
 
  memcpy(&qq->elem,ee,sizeof(Element));
 
  // 用頭插法插入新資料元素。
  int ii=Hash(hh,ee->key);
  qq->next=hh->head[ii].next;
  hh->head[ii].next=qq;
  
  hh->count++;   // 表中元素個數加1。
 
  return 1;
}
 
// 銷燬雜湊表
void FreeHashTable(HashTable *hh)
{
  int ii;
 
  Node *pp,*qq;
 
  // 釋放全部的單連結串列。
  for(ii=0;ii<hh->tablesize;ii++)
  {
    pp=hh->head[ii].next;
    while(pp)
    {
      qq=pp->next;
      free(pp);
      pp=qq;
    }
  }
 
  // 釋放全部單連結串列的頭結點陣列。
  free(hh->head);
 
  free(hh);  // 釋放雜湊表。
}
 
// 列印雜湊表。
void PrintTable(HashTable *hh)
{
  int ii; 
 
  for (ii=0;ii<hh->tablesize;ii++)
  {
    Node *pp=hh->head[ii].next;
    while (pp)
    {
      printf("[%d-%d] ",pp->elem.key,pp->elem.value);
      // printf("[%d-%s] ",pp->elem.key,pp->elem.value);
      pp=pp->next;
    }
 
    printf("^n");
  }
 
  printf("n");
}
 
int main()
{
  // 初始化雜湊表。
  HashTable *hh=InitHashTable(10);
 
  Element ee;
 
  // 插入資料元素，關鍵字從10到20。
  ee.key=10; ee.value=110; Insert(hh,&ee);
  ee.key=11; ee.value=111; Insert(hh,&ee);
  ee.key=12; ee.value=112; Insert(hh,&ee);
  ee.key=13; ee.value=113; Insert(hh,&ee);
  ee.key=14; ee.value=114; Insert(hh,&ee);
  ee.key=15; ee.value=115; Insert(hh,&ee);
  ee.key=16; ee.value=116; Insert(hh,&ee);
  ee.key=17; ee.value=117; Insert(hh,&ee);
  ee.key=18; ee.value=118; Insert(hh,&ee);
  ee.key=19; ee.value=119; Insert(hh,&ee);
 
  // 插入資料元素，關鍵字從20到30。
  ee.key=20; ee.value=120; Insert(hh,&ee);
  ee.key=21; ee.value=121; Insert(hh,&ee);
  ee.key=22; ee.value=122; Insert(hh,&ee);
  ee.key=23; ee.value=123; Insert(hh,&ee);
  ee.key=24; ee.value=124; Insert(hh,&ee);
  ee.key=25; ee.value=125; Insert(hh,&ee);
  ee.key=26; ee.value=126; Insert(hh,&ee);
  ee.key=27; ee.value=127; Insert(hh,&ee);
  ee.key=28; ee.value=128; Insert(hh,&ee);
  ee.key=29; ee.value=129; Insert(hh,&ee);
 
  // 插入資料元素，關鍵字從30到32。
  ee.key=30; ee.value=130; Insert(hh,&ee);
  ee.key=31; ee.value=131; Insert(hh,&ee);
  ee.key=32; ee.value=132; Insert(hh,&ee);
 
  printf("count=%dn",hh->count);
  PrintTable(hh);    // 列印雜湊表 
 
  Delete(hh,12);     // 刪除雜湊表中關鍵字為12的資料元素。
 
  printf("count=%dn",hh->count);
  PrintTable(hh);    // 列印雜湊表 
 
  // 在雜湊表中查詢關鍵字18。
  Node *pp=LookUp(hh,18);
  if (pp==0) printf("LookUp(18) failed.n");
  else printf("key=18,value=%d.n",pp->elem.value);  
 
  // ee.key=10; strcpy(ee.value,"<no>00010<no/><name>西施</name><yz>絕世美人</yz>"); Insert(hh,&ee);
  // PrintTable(hh);    // 列印雜湊表 
 
  FreeHashTable(hh);  // 銷燬雜湊表 
 
  return 0;
}