实验报告
姓名： 学号： 1． 实验题目
针对某个集体中人名设计一个哈希表，使得平均查找长度不超过R，并完成相应的建表和查表程序。
基本要求：假设人名为中国人姓名的汉语拼音形式。待填入哈希表的人名共有30个，取平均查找长度的上限为2。哈希函数用除留余数法构造，用线性探测再散列法或链地址法处理冲突。 2．需求分析
本演示程序用VC编写，完成哈希函数用除留余数法构造，用线性探测再散列法或链地址法处理冲突。
输出形式：地址，关键字，收索长度，H（key），拼音 3.概要设计
typedef struct NAME typedef struct hterm void InitNameList() void CreateHashList() void FindList() void Display() int main()
4．详细设计
#include 页脚内容 哈尔滨市建筑安装工程备案表 #include char *py; //名字的拼音 int k; //拼音所对应的整数 }NAME; NAME NameList[HASH_LEN]; typedef struct hterm //哈希表{ char *py; //名字的拼音 int k; //拼音所对应的整数 int si; //查找长度 }HASH; HASH HashList[HASH_LEN]; void InitNameList() { NameList[0].py=\"houxinming\"; NameList[1].py=\"abc\"; NameList[2].py=\"defdgf\"; NameList[3].py=\"zhangrji\"; NameList[4].py=\"jiaxin\"; NameList[5].py=\"xiaokai\"; NameList[6].py=\"liupeng\"; 页脚内容 哈尔滨市建筑安装工程备案表 NameList[7].py=\"shenyonghai\"; char *f; int r,s0; for (int i=0;i for (r=0;*(f+r) != '\\0';r++) //方法：将字符串的各个字符所对应的ASCII码相加，所得的整数做为哈希表的关键字 s0=*(f+r)+s0; NameList[i].k=s0; } } void CreateHashList() { for ( int i=0; i for ( i=0; i 哈尔滨市建筑安装工程备案表 int sum=0; int adr=(NameList[i].k) % M; //哈希函数 int d=adr; if(HashList[adr].si==0) //如果不冲突 { HashList[adr].k=NameList[i].k; HashList[adr].py=NameList[i].py; HashList[adr].si=1; } else //冲突 { do { d=(d+((NameList[i].k))%10+1)%M; //伪散列 sum=sum+1; //查找次数加1 }while (HashList[d].k!=0); HashList[d].k=NameList[i].k; HashList[d].py=NameList[i].py; HashList[d].si=sum+1; }i++; } } void FindList() { printf(\"\\n\\n请输入姓名的拼音: \"); //输入姓名 页脚内容 哈尔滨市建筑安装工程备案表 char name[20]={0}; scanf(\"%s\ int s0=0; for (int r=0;r<20;r++) //求出姓名的拼音所对应的整数(关键字) s0+=name[r]; int sum=1; int adr=s0 % M; //使用哈希函数 int d=adr; if(HashList[adr].k==s0) //分3种情况进行判断 printf(\"\\n姓名:%s 关键字:%d 查找长度为: 1\ else if (HashList[adr].k==0) printf(\"无该记录!\"); else { int g=0; do { d=(d+s0%10+1)%M; //伪散列 sum=sum+1; if (HashList[d].k==0) { printf(\"无记录! \"); g=1; } if (HashList[d].k==s0) 页脚内容 哈尔滨市建筑安装工程备案表 { printf(\"\\n姓名:%s 关键字:%d 查找长度为:%d\ g=1; } }while(g==0); } } void Display() { printf(\"\\n\\n地址\关键字\\搜索长度\H(key)\\拼音 \\n\"); //显示的格式 for(int i=0; i<15; i++) { printf(\"%d \ printf(\"\%d \ printf(\"\\%d \ printf(\"\\%d \ printf(\"\ %s \ printf(\"\\n\"); } for( i=15; i<30; i++) { printf(\"%d \ printf(\"\%d \ printf(\"\\%d \ printf(\"\\%d \ printf(\"\ %s \ 页脚内容 哈尔滨市建筑安装工程备案表 printf(\"\\n\"); } for( i=30; i<40; i++) { printf(\"%d \ printf(\"\%d \ printf(\"\\%d \ printf(\"\\%d \ printf(\"\ %s \ printf(\"\\n\"); } for(i=40; i<50; i++) { printf(\"%d \ printf(\"\%d \ printf(\"\\%d \ printf(\"\\%d \ printf(\"\ %s \ printf(\"\\n\"); } float average=0; for (i=0;i 页脚内容 哈尔滨市建筑安装工程备案表 } int main() { printf(\"\\n------------------------哈希表的建立和查找 ----------------------\"); InitNameList(); CreateHashList (); while(1) { printf(\"\\n\\n\"); printf(\" 1. 显示哈希表\\n\"); printf(\" 2. 查找\\n\"); printf(\" 3. 退出\\n\"); err: char ch1; scanf(\"%c\ if (ch1=='1') Display(); else if (ch1=='2') FindList(); else if (ch1=='3') return 0; else { printf(\"\\n请输入正确的选择!\");页脚内容 哈尔滨市建筑安装工程备案表 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 0 0 1 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 0页脚内容 哈尔滨市建筑安装工程备案表 22 0 0 0 23 0 0 0 24 0 0 0 25 0 0 0 26 0 0 0 27 0 0 0 28 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 0 044 608 1 44 defdgf45 0 0 046 0 0 047 0 0 048 0 0 0页脚内容 哈尔滨市建筑安装工程备案表 49 0 0 0 平均查找长度：ASL(8)=1.000000 1. 显示哈希表 2. 查找 3. 退出 请输入正确的选择!2 请输入姓名的拼音: houxinming 姓名:houxinming 关键字:1094 查找长度为: 1 1. 显示哈希表 2. 查找 3. 退出 请输入正确的选择! 页脚内容 因篇幅问题不能全部显示，请点此查看更多更全内容