哈希查找算法程序

查找算法

问题描述：

设计一个实现顺序查找、二分查找（折半查找）、二叉排序树、哈希查找算法的程序，并具有人机交互界面。

基本要求：

（1）设计一个菜单将实现的查找算法的名字显示出来，并提示用户对查找算法进行选择；

（2）分别实现顺序查找、二分查找（折半查找）、二叉排序树、哈希查找；

（3）哈希函数采用除留余数发，解决冲突的方法大家任选择一种；

（4）二叉排序树必须实现构建、查找、插入、删除四个基本 *** 作；

（5）输出各种排序的结果并进行比较。*/

#include<stdio.h>

#include<conio.h>

#include<stdlib.h>

#define MAX 20

typedef struct/*顺序结构数据类型*/

h.length++

h.r[ }

else

if(k<l.r[mid].key) high=mid-1

else low=mid +1

}

if(i!=0)

{

printf("l.r[%d].key=%d\n",i,k)

printf("查找成功\n")

}

return ht

}

void HashSearch(RecordHash ht) /*哈希查找*/

{

int k,i

page_title("哈希查找")

printf("请输入要查找的关键字:")

scanf("%d",&k)

i=k%13

if(ht.HashTable[i].key==k)

{

printf("ht.HashTable[%d].key=%d\n",i,k)

printf("查找成功\n")

}

else

{

i=i+1

for(i<MAXi++)

if(ht.HashTable[i].key==k)

{

printf("ht.HashTable[%d].key=%d\n",i,k)

printf("查找成功\n")

break

}

if(i==MAX) printf("查找失败\n")

}

return_confirm()

}

void main()

{

RecordList L1,L2

BSTNode *pt

RecordHash ht

int k,i

printf("\n创建顺序查找线性表,输入0则结束输入(可不按顺序输入)\n")

L1=creat1()

printf("\n创建二分查找线性表，输入0则结束输入(按递增顺序输入)\n")

L2=creat1()

printf("\n创建二叉排序树，输入0则结束输入\n")

pt=creat2()

printf("\n创建哈希表\n")

ht=creat3()

menu:page_title("请选择查找方式，输入0则结束输入")

printf("顺序查找请按1\n二分查找请按2\n二叉排序树查找请按3\n哈希查找请按4\n推出请按0\n")

switch(getch())

{

case '1':

SeqSearch(L1)

break

case '2':

Binsrch(L2)

break

case '3':

page_title("二叉排序树查找")

printf("请输入要查找的关键字:")

scanf("%d",&k)

SearchBST(pt,k)

break

case '4':

HashSearch(ht)

break

case '0':

exit(0)

default :

printf("输入错误，按任意键返回")

getch()

}

goto menu

算法设计

已知一个含有100个记录的表，关键字为中国人姓氏的拼音，请给出此表的一个哈希表设计方案，要求在等概率情况下查找成功的平均查找长度不超过3。

（1） 根据平均查找长度不超过3，确定装填因子α；

snl≈1/2(1+(1/(1-α))){使用线性探测再散列解决冲突}

因snl<=3,所以α至少为0.8,取α=0.8.

（2） 根据α确定表长

由α=（表中添入的记录数）/（哈希表的长度）

所以 哈希表的长度=100/α=125

取表长=150；

（3） 选取哈希函数

H(key)=key MOD 149

(4) key 的选取方法。

设大写字母在表中用1..26 表示，小写字母用27--52 表示。每个人的姓名取四个字

　母（两字姓名取首尾两个字母，三字姓名取各字拼音第一个字母，中间字取首尾两

　个拼音字母）。

将前两个拼音字母的序号并起来，后两个也并起来, 然后相加形成关键字。要求姓名

　的第一个拼音字母要大写，如姓名'王丽明'拼音为'Wang liming'，取出四个拼音字母

　为'W,l,i,m',个字母序号依次为 23 38 35 39，组成关键字为 2338+3539=5877，该姓

　名的哈希地址为 5877 MOD 149=66。

(5) 用线性探测再散列处理冲突。

这是设计原理，别的要求没拉：（

#define MaxSize 100 //定义最大哈希表长度

#define NULLKEY -1 //定义空关键字值

#define DELKEY -2 //定义被删关键字值

typedef int KeyType //关键字类型

typedef char * InfoType //其他数据类型

typedef struct

{

KeyType key //关键字域

InfoType data //其他数据域

int count //探查次数域

} HashData

typedef HashData HashTable[MaxSize] //哈希表类型

void InsertHT(HashTable ha,int &n,KeyType k,int p) //将关键字k插入到哈希表中

{

int i,adr

adr=k % p

if (ha[adr].key==NULLKEY || ha[adr].key==DELKEY)//x[j]可以直接放在哈希表中

{

ha[adr].key=k

ha[adr].count=1

}

else//发生冲突时采用线性探查法解决冲突

{

i=1 //i记录x[j]发生冲突的次数

do

{

adr=(adr+1) % p

i++

}

while (ha[adr].key!=NULLKEY &&ha[adr].key!=DELKEY)

ha[adr].key=k

ha[adr].count=i

}

n++

}

void CreateHT(HashTable ha,KeyType x[],int n,

---