哈希表-算法-hash表-C++实现

1、精选优质文档-倾情为你奉上精选优质文档-倾情为你奉上专心-专注-专业专心-专注-专业精选优质文档-倾情为你奉上专心-专注-专业哈希表算法hash表问题描述：针对某个集体（比如你所在的班级）中的“人名”设计一个哈希表，使得平均查找长度不超过R，完成相应的建表和查表程序。基本要求：假设人名为中国人姓名的汉语拼音形式。待填入哈希表的人名共有30个，取平均查找长度的上限为2。哈希函数用除留余数法构造，用伪随机探测再散列发处理冲突。#include #include #include /#include #define HASH_LEN 50 /哈希表的长度 #define M 47 #define N

2、AME_NO 30 /人名的个数 typedef struct NAME char *py; /名字的拼音 int k; /拼音所对应的整数 NAME; NAME NameListHASH_LEN; typedef struct hterm /哈希表 char *py; /名字的拼音 int k; /拼音所对应的整数 int si; /查找长度 HASH; HASH HashListHASH_LEN; /*-姓名（结构体数组）初始化-*/ void InitNameList() NameList0.py=zhanghongshuai;NameList1.py=xurensong;NameLis

3、t2.py=huangxiangyu;NameList3.py=luoqi;NameList4.py=zhangsan;NameList5.py=lisi;NameList6.py=wangwu;NameList7.py=renwei;NameList8.py=zhangchu;NameList9.py=wangmengyuan;NameList10.py=libaohua;NameList11.py=zhaoyanlong;NameList12.py=jwangyuxin;NameList13.py=duyanmo;NameList14.py=wangmingyang;NameList15.

4、py=lijiawei;NameList16.py=hesiyu;NameList17.py=zhanghailong;NameList18.py=lixinyu;NameList19.py=songdiyao;NameList20.py=zhaomingzhi;NameList21.py=zhangchenglong;NameList22.py=sunjie;NameList23.py=zhangdongmei;NameList24.py=antianyu;NameList25.py=zhulaiao;NameList26.py=wangyuting;NameList27.py=wangxi

5、liang;NameList28.py=zhangdeshuai;NameList29.py=xumingming; char *f; int r,s0; for (int i=0;iNAME_NO;i+)/ 求出各个姓名的拼音所对应的整数 s0=0; f=NameListi.py; for (r=0;*(f+r) != 0;r+) /方法：将字符串的各个字符所对应的ASCII码相加，所得的整数做为哈希表的关键字 s0=*(f+r)+s0; NameListi.k=s0; /*-建立哈希表-*/ void CreateHashList() for (int i=0; iHASH_LEN;i+)

6、/哈希表的初始化 HashListi.py=; HashListi.k=0; HashListi.si=0; for (int i=0; i=NAME_NO;) int sum=0; int adr=(NameListi.k) % M; /哈希函数 int d=adr; if(HashListadr.si=0) /如果不冲突 HashListadr.k=NameListi.k; HashListadr.py=NameListi.py; HashListadr.si=1; else /冲突 do d=(d+(NameListi.k)%10+1)%M; /伪散列 sum=sum+1; /查找次数加

7、1 while (HashListd.k!=0); HashListd.k=NameListi.k; HashListd.py=NameListi.py; HashListd.si=sum+1; i+; /*-查找-*/ void FindList() printf(nn请输入姓名的拼音: ); /输入姓名 char name20=0; scanf(%s,name); int s0=0; for (int r=0;r20;r+) /求出姓名的拼音所对应的整数(关键字) s0+=namer; int sum=1; int adr=s0 % M; /使用哈希函数 int d=adr; if(Has

8、hListadr.k=s0) /分3种情况进行判断 printf(n姓名:%s 关键字:%d 查找长度为: 1,HashListd.py,s0); else if (HashListadr.k=0) printf(无该记录!); else int g=0; do d=(d+s0%10+1)%M; /伪散列 sum=sum+1; if (HashListd.k=0) printf(无记录! ); g=1; if (HashListd.k=s0) printf(n姓名:%s 关键字:%d 查找长度为:%d,HashListd.py,s0,sum); g=1; while(g=0); /*-显示哈希

9、表-*/ void Display() printf(nn地址t关键字tt搜索长度tH(key)tt拼音 n); /显示的格式 for(int i=0; i15; i+) printf(%d ,i); printf(t%d ,HashListi.k); printf(tt%d ,HashListi.si); printf(tt%d ,(HashListi.k)%M); printf(t %s ,HashListi.py); printf(n); / printf(按任意键继续显示.n); /由于数据比较多，所以分屏显示（以便在Win9xDOS下能看到所有的数据） / getch(); for(

10、 int i=15; i30; i+) printf(%d ,i); printf(t%d ,HashListi.k); printf(tt%d ,HashListi.si); printf(tt%d ,(HashListi.k)%M); printf(t %s ,HashListi.py); printf(n); / printf(按任意键继续显示.n); / getch(); for( int i=30; i40; i+) printf(%d ,i); printf(t%d ,HashListi.k); printf(tt%d ,HashListi.si); printf(tt%d ,(H

11、ashListi.k)%M); printf(t %s ,HashListi.py); printf(n); /printf(按任意键继续显示.n); /getch(); for( int i=40; i50; i+) printf(%d ,i); printf(t%d ,HashListi.k); printf(tt%d ,HashListi.si); printf(tt%d ,(HashListi.k)%M); printf(t %s ,HashListi.py); printf(n); float average=0; for (int i=0;iHASH_LEN;i+) average

12、+=HashListi.si; average/=NAME_NO; printf(nn平均查找长度：ASL(%d)=%f nn,NAME_NO,average); /*-主函数-*/ main() /* :SetConsoleTitle(哈希表操作); /Windows API函数,设置控制台窗口的标题 HANDLE hCon = :GetStdHandle(STD_OUTPUT_HANDLE); /获得标准输出设备的句柄 :SetConsoleTextAttribute(hCon, 10|0); /设置文本颜色 */ printf(n-哈希表的建立和查找-); InitNameList(); CreateHashList (); while(1) printf(nn); printf( 1. 显示哈