哈希表实验报告完整版

1、实验报告姓名： 学号： 1 实验题目针对某个集体中人名设计一个哈希表，使得平均查找长度不超过R，并完成相应的建表和查表程序。基本要求：假设人名为中国人姓名的汉语拼音形式。待填入哈希表的人名共有30个，取平均查找长度的上限为2。哈希函数用除留余数法构造，用线性探测再散列法或链地址法处理冲突。2需求分析本演示程序用VC编写，完成哈希函数用除留余数法构造，用线性探测再散列法或链地址法处理冲突。输出形式：地址，关键字，收索长度，H（key），拼音3.概要设计typedef struct NAMEtypedef struct htermvoid InitNameList()void CreateHash

2、List()void FindList()void Display()int main()4详细设计#include #include#include#define HASH_LEN 50#define M 47#define NAME_NO 8typedef struct NAME char *py; /名字的拼音 int k; /拼音所对应的整数NAME;NAME NameListHASH_LEN;typedef struct hterm /哈希表 char *py; /名字的拼音 int k; /拼音所对应的整数 int si; /查找长度HASH;HASH HashListHASH_L

3、EN;void InitNameList() NameList0.py=houxinming; NameList1.py=abc; NameList2.py=defdgf; NameList3.py=zhangrji; NameList4.py=jiaxin; NameList5.py=xiaokai; NameList6.py=liupeng; NameList7.py=shenyonghai; char *f; int r,s0; for (int i=0;iNAME_NO;i+)/ 求出各个姓名的拼音所对应的整数 s0=0; f=NameListi.py; for (r=0;*(f+r)

4、 != 0;r+) /方法：将字符串的各个字符所对应的ASCII码相加，所得的整数做为哈希表的关键字 s0=*(f+r)+s0; NameListi.k=s0; void CreateHashList() for ( int i=0; iHASH_LEN;i+)/哈希表的初始化 HashListi.py=; HashListi.k=0; HashListi.si=0; for ( i=0; iNAME_NO;) int sum=0; int adr=(NameListi.k) % M; /哈希函数 int d=adr; if(HashListadr.si=0) /如果不冲突 HashLista

5、dr.k=NameListi.k; HashListadr.py=NameListi.py; HashListadr.si=1; else /冲突 do d=(d+(NameListi.k)%10+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,nam

6、e); int s0=0; for (int r=0;r20;r+) /求出姓名的拼音所对应的整数(关键字) s0+=namer; int sum=1; int adr=s0 % 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

7、) printf(无记录! ); g=1; if (HashListd.k=s0) printf(n姓名:%s 关键字:%d 查找长度为:%d,HashListd.py,s0,sum); 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

8、 %s ,HashListi.py); printf(n); 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); for( i=30; i40; i+) printf(%d ,i); printf(t%d ,HashListi.k); printf(tt%d ,HashListi.si); printf(tt%d ,(HashLis

9、ti.k)%M); printf(t %s ,HashListi.py); printf(n); 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_LEN;i+) average+=HashListi.si; average/=NAME_NO; printf(nn平均查

10、找长度：ASL(%d)=%f nn,NAME_NO,average);int main() printf(n-哈希表的建立和查找-); 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 0; else printf(n请输入

11、正确的选择!); goto err; 5调试分析(略)6使用说明程序名为hash tablet.exe，运行环境为DOS。程序执行后显示=1. 显示哈希表2. 查找3. 退出=SELECT:在select后输入数字选择执行不同的功能。要求首先输入足够多的插入元素，才可以进行其他的操作。每执行一次功能，就会显示执行的结果（正确或错误）以及执行后单链表的内容。选择1：显示哈希表选择2：显示请输入姓名的拼音，要求输入要删除元素的位置，执行成功后返回元素的值。选择3：退出程序 7测试结果-哈希表的建立和查找- 1. 显示哈希表 2. 查找 3. 退出1地址 关键字 搜索长度 H(key) 拼音0 0

12、0 01 0 0 02 0 0 03 0 0 04 756 1 4 liupeng5 0 0 06 1181 1 6 shenyonghai7 0 0 08 0 0 09 0 0 010 0 0 011 0 0 012 294 1 12 abc13 1094 1 13 houxinming14 0 0 015 861 1 15 zhangrji16 0 0 017 0 0 018 0 0 019 0 0 020 0 0 021 0 0 022 0 0 023 0 0 024 0 0 025 0 0 026 0 0 027 0 0 028 0 0 029 0 0 030 0 0 031 0 0 032 643 1 32 jiaxin33 0 0 034 0 0 035 0 0 036 0 0 037 742 1 37 xiaokai38 0 0 039 0 0 040 0 0 041 0 0 042 0 0 043 0