//* * * * * * * * * * * * * * * * * * * * * * * *
//*CHAPTER          :6  (6_6)                   *
//*PROGRAM          :哈希表的綜合操作           *
//*CONTENT          :Insert,Search,Deltet       *
//* * * * * * * * * * * * * * * * * * * * * * * *
#include <dos.h>
#include <conio.h>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 12 //哈希表的最大容量，與所采用的哈希函數有關
enum BOOL{False,True};
enum HAVEORNOT{NULLKEY,HAVEKEY,DELKEY}; 
    //哈希表元素的三種狀態，沒有記錄、有記錄、有過記錄但已被刪除
typedef struct         //定義哈希表的結構
{int  elem[MAXSIZE];   //數據元素體
 HAVEORNOT elemflag[MAXSIZE]; //元素狀態標志，沒有記錄、有記錄、有過記錄但已被刪除
 int count;  //哈希表中當前元素的個數 
}HashTable;
typedef struct
{int keynum;      //記錄的數據域，只有關鍵字一項
}Record;
void InitialHash(HashTable&); //初始化哈希表
void PrintHash(HashTable);    //顯示哈希表中的所有元素
BOOL SearchHash(HashTable,int,int&); //在哈希表中查找元素
BOOL InsertHash(HashTable&,Record);    //在哈希表中插入元素
BOOL DeleteHash(HashTable&,Record);    //在哈希表中刪除元素
int  Hash(int);  //哈希函數
void main()
{HashTable H;  //聲明哈希表H
 char ch,j='y'; 
 int position;
 Record R;
 BOOL temp;
 textbackground(3);  //設定屏幕顏色
 textcolor(15);
 clrscr();
 //-------------------------程序說明-------------------------------
 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); //輸入操作選項
     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); //輸入待查記錄的關鍵字
		    temp=SearchHash(H,R.keynum,position); 
                       //temp=True:記錄查找成功；temp=False:沒有找到待查記錄
		    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:已存在關鍵字相同的記錄
		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); //輸入要刪除記錄的關鍵字
		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) //只顯示標志為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); //顯示哈希表當前記錄數
}
BOOL SearchHash(HashTable H,int k,int &p)
{//在開放定址哈希表H中查找關鍵字為k的數據元素，若查找成功，以p指示
 //待查數據元素在表中的位置，并返回True；否則，以p指示插入位置，并
 //返回False
 int p1;
 p1=p=Hash(k); //求得哈希地址
 while(H.elemflag[p]==HAVEKEY&&k!=H.elem[p])  
      //該位置中填有記錄并且關鍵字不相等
   {p++;  //沖突處理方法：線性探測再散列
    if(p>=MAXSIZE) p=p%MAXSIZE; //循環搜索
    if(p==p1) return False;  //整個表已搜索完，沒有找到待查元素
   }
 if(k==H.elem[p]&&H.elemflag[p]==HAVEKEY) //查找成功，p指示待查元素位置
    return True; 
 else return False; //查找不成功
}
BOOL InsertHash(HashTable &H,Record e)
{//查找不成功時插入元素e到開放定址哈希表H中，并返回True，否則返回False
 int p;
 if(SearchHash(H,e.keynum,p)) //表中已有與e有相同關鍵字的元素
    return False;
 else
   {H.elemflag[p]=HAVEKEY;  //設置標志為HAVEKEY，表示該位置已有記錄
    H.elem[p]=e.keynum;     //插入記錄
    H.count++;              //哈希表當前長度加一 
    return True;
   }
}
BOOL DeleteHash(HashTable &H,Record e)
{//在查找成功時刪除待刪元素e，并返回True，否則返回False
 int p;
 if(!SearchHash(H,e.keynum,p)) //表中不存在待刪元素
   return False;
 else
   {H.elemflag[p]=DELKEY; //設置標志為DELKEY，表明該元素已被刪除
    H.count--;    //哈希表當前長度減一
    return True;
   }
}
int Hash(int kn)
{//哈希函數：H(key)=key MOD 11
 return (kn%11);
}