哈希表设计(共8页).doc

《哈希表设计(共8页).doc》由会员分享，可在线阅读，更多相关《哈希表设计(共8页).doc（8页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、精选优质文档-倾情为你奉上 哈希表设计一问题描述问题描述：针对某个集体中人名设计一个哈希表，使得平均查找长度不超过R，并完成相应的建表和查表程序。基本要求：假设人名为中国人姓名的汉语拼音形式。待填入哈希表的人名共有30个，取平均查找长度的上限为2。哈希函数用除留余数法构造，用线性探测再散列法或链地址法处理冲突。二. 需求分析（1） 针对某个集体中的人名设计一个哈希表，使得平均查找长度不超过R，完成相应的建立和查表程序。（2）人名为汉语拼音形式，最长不超过19个字符(如：庄双双 zhuangshuangshuang)。（3） 假设待填入哈希表的人名有30个，平均查找长度的上限为2。哈希表用除留余

2、数法构造，用伪随机探测在散列法处理冲突。（4） 在输入人名过程中能自动识别非法输入，并给与非法输入的反馈信息要求重新输入。（5）查找成功时，显示姓名及关键字，并计算和输出查找成功的平均查找长度三概要设计1.为实现上述算法，需要顺序的抽象数据类型。ADT Hash数据对象D：D是具有相同特征的数据元素的集合。各数据元素均含有类型相同，可唯一标识的数据元素的关键字。数据关系：数据元素同属于一个集合。基本操作P： Creat（&ST，n）； 操作结果：构造一个含n个数据元素的静态查找表ST。 Destroy（&ST） 初始条件：静态查找表ST存在。 操作结果：销毁表ST. Search：（ST,ke

3、y）初始条件：静态查找表ST存在，key为和关键字类型相同的定值。操作结果：若ST中存在其关键字等于key的数据元素，则函数值为该数据元素的值或在表中的位置，否则为“空”。 Insert（&h,key） 初始条件：哈希表h存在。 操作结果：若表中没有key，则在h中插入key。 Hash（h,&k） 初始条件：哈希表h存在。 操作结果：通过除留余数法得到地址用k返回。2.本程序有三个模块：（1）主程序模块 Main() 初始化； 接受命令； 显示结果； （2）创建hash表的模块（3）查找hash表的模块（4）显示哈希表的模块 四详细设计#include #include #include /

4、#include #define HASH_LEN 50 /哈希表的长度 #define M 47 #define NAME_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()

5、 NameList0.py=baojianbo;NameList1.py=chenjiabin;NameList2.py=chenxi;NameList3.py=dinglin;NameList4.py=fangzewei;NameList5.py=fengpan;NameList6.py=guidong;NameList7.py=hanlijuan;NameList8.py=haoxiaoju;NameList9.py=heqing;NameList10.py=jishaomei;NameList11.py=jiyunfeng;NameList12.py=jiangshanshan;Name

6、List13.py=lixuefei;NameList14.py=lixueqin;NameList15.py=liyuanxin;NameList16.py=liangguannan;NameList17.py=liuna;NameList18.py=liupeiyu;NameList19.py=nixiaodong;NameList20.py=peixue;NameList21.py=sunke;NameList22.py=sunying;NameList23.py=wanqishuai;NameList24.py=wangna;NameList25.py=linglei;NameList

7、26.py=xinnaping;NameList27.py=xuyuanfei;NameList28.py=yanlipeng;NameList29.py=yangmengjiao; 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 CreateHashL

8、ist() for (int i=0; iHASH_LEN;i+)/哈希表的初始化 HashListi.py=; HashListi.k=0; HashListi.si=0; for (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

9、+1)%M; /伪散列 sum=sum+1; /查找次数加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 %

10、 M; /使用哈希函数 int d=adr; if(HashListadr.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,s

11、um); g=1; while(g=0); /*-显示哈希表-*/ 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); /由于数据比较多，所以分屏显示（以便在Win9x

12、DOS下能看到所有的数据） / getch(); for( 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( i=30; i40; i+) printf(%d ,i); printf(t%d ,HashListi.k); printf(tt%d ,HashListi

13、.si); printf(tt%d ,(HashListi.k)%M); printf(t %s ,HashListi.py); printf(n); /printf(按任意键继续显示.n); /getch(); for( 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 (i=0;iHASH_LE

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

15、); InitNameList(); CreateHashList (); while(1) printf(nn); printf( 1. 显示哈希表n); printf( 2. 查找n); printf( 3. 退出n); err: char ch1; scanf(%c,&ch1); if (ch1=1) Display(); else if (ch1=2) FindList(); else if (ch1=3) return; else printf(n请输入正确的选择!); goto err; 五调试分析1.因为人数太多，所以最初总得不到想要的结果，有很多人名的关键字重复2.该程序不占用额外空间，因此时间复杂度是O（n）的3.注意人名的长度，正确的输入信息六用户手册 七测试数据专心-专注-专业