哈希表设计 哈希表 哈希表

对一批关键字集合采用开放定址哈希表的存储结构来建立相应的哈希表和完成查找过程。 (1) 熟练掌握哈希表的构造方法 (2) 理解哈希表与其他结构表的实质性差别。

#include
#include
#include
#include
#include 
#include
#include
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define SUCCESS 1
#define UNSUCCESS 0
#define DUPLICATE -1
#define NULLKEY 0 // 0为无记录标志
#define N 10 // 数据元素个数
#define EQ（ab） （（a）==（b））
#define LT（ab） （（a）<（b））
#define LQ（ab） （（a）<=（b））
typedef int Status; // Status是函数的类型其值是函数结果状态代码，如OK等
typedef int Boolean; // Boolean是布尔类型其值是TRUE或FALSE
typedef int KeyType; // 设关键字域为整型

struct ElemType // 数据元素类型
{
   KeyType key;
   int ord;
};

int hashsize[]={11192937}; // 哈希表容量递增表，一个合适的素数序列
int m=0; // 哈希表表长，全局变量
struct HashTable
{
   ElemType *elem; // 数据元素存储基址，动态分配数组
   int count; // 当前数据元素个数
   int sizeindex; // hashsize[sizeindex]为当前容量
};

Status InitHashTable（HashTable &H）// 操作结果: 构造一个空的哈希表
{ int i;
   H.count=0; // 当前元素个数为0
   H.sizeindex=0; // 初始存储容量为hashsize[0]
   m=hashsize[0];
   H.elem=（ElemType*）malloc（m*sizeof（ElemType））;
   if（!H.elem）
     exit（OVERFLOW）; // 存储分配失败
   for（i=0;i     H.elem[i].key=NULLKEY; // 未填记录的标志
   return OK;
}

void DestroyHashTable（HashTable &H）
{ free（H.elem）;
   H.elem=NULL;
   H.count=0;
   H.sizeindex=0;
}

unsigned Hash（KeyType K）// 一个简单的哈希函数（m为表长，全局变量）
{ return K%m;
}

void collision（int &pint d） // 线性探测再散列
{ 
   p=（p+d）%m;// 开放定址法处理冲突
}

Status SearchHash（HashTable HKeyType Kint &pint &c）// 在开放定址哈希表H中查找关键码为K的元素若查找成功以p指示待查数据
{ p=Hash（K）; // 求得哈希地址
   while（H.elem[p].key!=NULLKEY&&!EQ（KH.elem[p].key））
   { // 该位置中填有记录．并且关键字不相等
     c++;
     if（c       collision（pc）; // 求得下一探查地址p
     else
       break;
   }
   if EQ（KH.elem[p].key）
     return SUCCESS; // 查找成功，p返回待查数据元素位置
   else
     return UNSUCCESS; // 查找不成功（H.elem[p].key==NULLKEY），p返回的是插入位置
}

Status InsertHash（HashTable &ElemType）; // 对函数的声明
void RecreateHashTable（HashTable &H） // 重建哈希表
{ int icount=H.count;
   ElemType *p*elem=（ElemType*）malloc（count*sizeof（ElemType））;
   p=elem;
   printf（“重建哈希表\n“）;
   for（i=0;i   if（（H.elem+i）->key!=NULLKEY） // 该单元有数据
   *p++=*（H.elem+i）;
   H.count=0;
   H.sizeindex++; // 增大存储容量
   m=hashsize[H.sizeindex];
   p=（ElemType*）realloc（H.elemm*sizeof（ElemType））;
   if（!p）
     exit（OVERFLOW）; // 存储分配失败
   H.elem=p;
   for（i=0;i     H.elem[i].key=NULLKEY; // 未填记录的标志（初始化）
   for（p=elem;p     InsertHash（H*p）;
}

Status InsertHash（HashTable &HElemType e）// 查找不成功时插入数据元素e到开放定址哈希表H中，并返回OK；
{ int cp;
   c=0;
   if（SearchHash（He.keypc）） // 表中已有与e有相同关键字的元素
     return DUPLICATE;
   else if（c   { // 插入e
     H.elem[p]=e;
     ++H.count;
     return OK;
   }
   else
     RecreateHashTable（H）; // 重建哈希表
   return ERROR;
}

void TraverseHash（HashTable Hvoid（*Vi）（intElemType））// 按哈希地址的顺序遍历哈希表
{ 
   printf（“哈希地址0～%d\n“m-1）;

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----

     文件        901  2009-03-04 17:30  哈希表设计.plg

     文件      12878  2009-03-04 17:30  Debug\main.obj

     文件      41984  2009-03-04 17:30  Debug\vc60.idb

     文件      53248  2008-11-20 12:25  Debug\vc60.pdb

     文件     184388  2009-03-04 17:30  Debug\哈希表设计.exe

     文件     190624  2009-03-04 17:30  Debug\哈希表设计.ilk

     文件     248132  2008-11-20 12:25  Debug\哈希表设计.pch

     文件     451584  2008-11-20 12:25  Debug\哈希表设计.pdb

     文件       5193  2008-11-19 22:06  main.cpp

     文件       4326  2008-11-19 12:37  哈希表设计.dsp

     文件        528  2008-11-19 12:36  哈希表设计.dsw

     文件      41984  2009-03-04 17:30  哈希表设计.ncb

     文件      48640  2009-03-04 17:30  哈希表设计.opt

     目录          0  2008-11-20 12:25  Debug

----------- ---------  ---------- -----  ----

              1284410                    14