//* * * * * * * * * * * * * * * * * * * * * * * * *
//*PROGRAM :哈希表的綜合操作 *
//*CONTENT :Insert,Search,Deltet *
//* * * * * * * * * * * * * * * * * * * * * * * *
#include <dos.h>
#include <conio.h>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 12 //哈希表的最大容量，與所采用的哈希函數(shù)有關(guān)
enum BOOL{False,True};
enum HAVEORNOT{NULLKEY,HAVEKEY,DELKEY}; 
//哈希表元素的三種狀態(tài)，沒(méi)有記錄、有記錄、有過(guò)記錄但已被刪除
typedef struct //定義哈希表的結(jié)構(gòu)
{int elem[MAXSIZE]; //數(shù)據(jù)元素體
HAVEORNOT elemflag[MAXSIZE]; //元素狀態(tài)標(biāo)志，沒(méi)有記錄、有記錄、有過(guò)記錄但已被刪除
int count; //哈希表中當(dāng)前元素的個(gè)數(shù) 
}HashTable;
typedef struct
{int keynum; //記錄的數(shù)據(jù)域，只有關(guān)鍵字一項(xiàng)
}Record;
void InitialHash(HashTable&); //初始化哈希表
void PrintHash(HashTable); //顯示哈希表中的所有元素
BOOL SearchHash(HashTable,int,int&); //在哈希表中查找元素
BOOL InsertHash(HashTable&,Record); //在哈希表中插入元素
BOOL DeleteHash(HashTable&,Record); //在哈希表中刪除元素
int Hash(int); //哈希函數(shù)
void main()
{HashTable H; //聲明哈希表H
char ch,j='y'; 
int position;
Record R;
BOOL temp;
textbackground(3); //設(shè)定屏幕顏色
textcolor(15);
clrscr();
//-------------------------程序說(shuō)明-------------------------------
printf("This program will show how to operate to a HashTable.\n");
printf("You can display all elems,search a elem,\ninsert a elem,delete a elem.\n");
//----------------------------------------------------------------
InitialHash(H);
while(j!='n')
{printf("1.display\n");
printf("2.search\n");
printf("3.insert\n");
printf("4.delete\n");
printf("5.exit\n");
scanf(" %c",&ch); //輸入操作選項(xiàng)
switch(ch)
{case '1':if(H.count) PrintHash(H); //哈希表不空
else printf("The HashTable has no elem!\n");
break;
case '2':if(!H.count) printf("The HashTable has no elem!\n"); //哈希表空
else
{printf("Please input the keynum(int) of the elem to search:");
scanf("%d",&R.keynum); //輸入待查記錄的關(guān)鍵字
temp=SearchHash(H,R.keynum,position); 
//temp=True:記錄查找成功；temp=False:沒(méi)有找到待查記錄
if(temp) printf("The position of the elem is %d\n",position);
else printf("The elem isn't exist!\n"); 
}
break;
case '3':if(H.count==MAXSIZE) //哈希表已滿
{printf("The HashTable is full!\n");
break;
}
printf("Please input the elem(int) to insert:");
scanf("%d",&R.keynum); //輸入要插入的記錄
temp=InsertHash(H,R); 
//temp=True:記錄插入成功；temp=False:已存在關(guān)鍵字相同的記錄
if(temp) printf("Sucess to insert the elem!\n");
else printf("Fail to insert the elem.The same elem has been exist!\n");
break;
case '4':printf("Please input the keynum of the elem(int) to delet:");
scanf("%d",&R.keynum); //輸入要?jiǎng)h除記錄的關(guān)鍵字
temp=DeleteHash(H,R); 
//temp=True:記錄刪除成功；temp=False:待刪記錄不存在 
if(temp) printf("Sucess to delete the elem!\n");
else printf("The elem isn't exist in the HashTable!\n");
break;
default: j='n';
}
}
printf("The program is over!\nPress any key to shut off the window!\n");
getchar();getchar();
}
void InitialHash(HashTable &H)
{//哈希表初始化
int i;
H.count=0;
for(i=0;i<MAXSIZE;i++) H.elemflag[i]=NULLKEY;
}
void PrintHash(HashTable H)
{//顯示哈希表所有元素及其所在位置
int i;
for(i=0;i<MAXSIZE;i++) //顯示哈希表中記錄所在位置
if(H.elemflag[i]==HAVEKEY) //只顯示標(biāo)志為HAVEKEY(存放有記錄)的元素
printf("%-4d",i);
printf("\n");
for(i=0;i<MAXSIZE;i++) //顯示哈希表中記錄值
if(H.elemflag[i]==HAVEKEY)
printf("%-4d",H.elem[i]);
printf("\ncount:%d\n",H.count); //顯示哈希表當(dāng)前記錄數(shù)
}
BOOL SearchHash(HashTable H,int k,int &p)
{//在開放定址哈希表H中查找關(guān)鍵字為k的數(shù)據(jù)元素，若查找成功，以p指示
//待查數(shù)據(jù)元素在表中的位置，并返回True；否則，以p指示插入位置，并
//返回False
int p1;
p1=p=Hash(k); //求得哈希地址
while(H.elemflag[p]==HAVEKEY&&k!=H.elem[p]) 
//該位置中填有記錄并且關(guān)鍵字不相等
{p++; //沖突處理方法：線性探測(cè)再散列
if(p>=MAXSIZE) p=p%MAXSIZE; //循環(huán)搜索
if(p==p1) return False; //整個(gè)表已搜索完，沒(méi)有找到待查元素
}
if(k==H.elem[p]&&H.elemflag[p]==HAVEKEY) //查找成功，p指示待查元素位置
return True; 
else return False; //查找不成功
}
BOOL InsertHash(HashTable &H,Record e)
{//查找不成功時(shí)插入元素e到開放定址哈希表H中，并返回True，否則返回False
int p;
if(SearchHash(H,e.keynum,p)) //表中已有與e有相同關(guān)鍵字的元素
return False;
else
{H.elemflag[p]=HAVEKEY; //設(shè)置標(biāo)志為HAVEKEY，表示該位置已有記錄
H.elem[p]=e.keynum; //插入記錄
H.count++; //哈希表當(dāng)前長(zhǎng)度加一 
return True;
}
}
BOOL DeleteHash(HashTable &H,Record e)
{//在查找成功時(shí)刪除待刪元素e，并返回True，否則返回False
int p;
if(!SearchHash(H,e.keynum,p)) //表中不存在待刪元素
return False;
else
{H.elemflag[p]=DELKEY; //設(shè)置標(biāo)志為DELKEY，表明該元素已被刪除
H.count--; //哈希表當(dāng)前長(zhǎng)度減一
return True;
}
}
int Hash(int kn)
{//哈希函數(shù)：H(key)=key MOD 11
return (kn%11);
}


******************************************************************
知道是你沒(méi)說(shuō)清還是我理解不好，不太明白你的目的！   
  整理一份資料給你參考：   
          　散列方法不同于順序查找、二分查找、二叉排序樹及B-樹上的查找。它不以關(guān)鍵字的比較為基本操作，采用直接尋址技術(shù)。在理想情況下，無(wú)須任何比較就可以找到待查關(guān)鍵字，查找的期望時(shí)間為O(1)。   
    
  散列表的概念   
    
  1、散列表   
          　設(shè)所有可能出現(xiàn)的關(guān)鍵字集合記為U(簡(jiǎn)稱全集)。實(shí)際發(fā)生(即實(shí)際存儲(chǔ))的關(guān)鍵字集合記為K（|K|比|U|小得多）。   
          　散列方法是使用函數(shù)h將U映射到表T[0..m-1]的下標(biāo)上（m=O(|U|)）。這樣以U中關(guān)鍵字為自變量，以h為函數(shù)的運(yùn)算結(jié)果就是相應(yīng)結(jié)點(diǎn)的存儲(chǔ)地址。從而達(dá)到在O(1)時(shí)間內(nèi)就可完成查找。   
      其中：   
  　         ①   h：U→{0，1，2，…，m-1}   ，通常稱h為散列函數(shù)(Hash   Function)。散列函數(shù)h的作用是壓縮待處理的下標(biāo)范圍，使待處理的|U|個(gè)值減少到m個(gè)值，從而降低空間開銷。   
          　②   T為散列表(Hash   Table)。   
          　③   h(Ki)(Ki∈U)是關(guān)鍵字為Ki結(jié)點(diǎn)存儲(chǔ)地址(亦稱散列值或散列地址)。   
          　④   將結(jié)點(diǎn)按其關(guān)鍵字的散列地址存儲(chǔ)到散列表中的過(guò)程稱為散列(Hashing)   
        
    
  3、散列表的沖突現(xiàn)象   
  （1）沖突   
          　兩個(gè)不同的關(guān)鍵字，由于散列函數(shù)值相同，因而被映射到同一表位置上。該現(xiàn)象稱為沖突(Collision)或碰撞。發(fā)生沖突的兩個(gè)關(guān)鍵字稱為該散列函數(shù)的同義詞(Synonym)。   
      　【例】上圖中的k2≠k5，但h(k2)=h(k5)，故k2和K5所在的結(jié)點(diǎn)的存儲(chǔ)地址相同。   
    
  （2）安全避免沖突的條件   
          　最理想的解決沖突的方法是安全避免沖突。要做到這一點(diǎn)必須滿足兩個(gè)條件：   
  ①其一是|U|≤m   
  ②其二是選擇合適的散列函數(shù)。   
  　         這只適用于|U|較小，且關(guān)鍵字均事先已知的情況，此時(shí)經(jīng)過(guò)精心設(shè)計(jì)散列函數(shù)h有可能完全避免沖突。   
    
  （3）沖突不可能完全避免   
          　通常情況下，h是一個(gè)壓縮映像。雖然|K|≤m，但|U|>m，故無(wú)論怎樣設(shè)計(jì)h，也不可能完全避免沖突。因此，只能在設(shè)計(jì)h時(shí)盡可能使沖突最少。同時(shí)還需要確定解決沖突的方法，使發(fā)生沖突的同義詞能夠存儲(chǔ)到表中。