1、系 别:计算机科学与通信工程学院专 业:计算机科学与技术班 级:10-01 学 号:*41指导教师:卢冰、李晔 2012年 6月 21 日设计题目题目:每个记录有下列数据项:电话号码、用户名、地址;运行环境(软、硬件环境)Vc6.0算法设计的思想 电话号码查询系统主要是考察我们对哈希查找的掌握。题目要求用电话号码和姓名两种方式查找;第一大部份是用电话号码查找,第二部分是用姓名查找。1:电话号码查找(先建立哈希表读入数据,然后再处理冲突,查找):在这部分中,我用了除留取余法和数字分析法设计的哈希表,用的是开放定址法进行的冲突处理。除留取余法思想:取关键字被某个不大于哈希表表长的数p除后所得余数为
2、哈希地址即:H(key)=key%p。数字分析法:已知关键字是以r为基础的数,哈希表中出现的关键字是事先知道的,选择关键字是候,我们应该尽量避免冲突。开放地址法:开放地址法主要公式;H=(H+di)%m,di的取法有三种,但是我的程序中只用到了线性探测在散列,本可以用再哈希函数解决冲突的,但是考虑到再哈希函数会增加计算时间,所以就没用。2:姓名查找(先建立哈希表读入数据,然后再处理冲突,查找)方式:这个过程中,我选取了数字分析法,解释如上。主菜单的设计在设计效果上已经显示,不过多说明。算法的流程主菜单建立除留取余和数字分析法存储开放地址法解决冲突查找。算法设计分析这段代码是哈希存储时从第三个数
3、开始求,提高了代码效率。int i = 3; while(s.numi!=0) /关键字 key+=(s.numi-0); /关键字求和 i+; key=key%21;线性探测再散列处理冲突 if(!strcmp(W.tkey.num,)/查找,解决冲突 W.tkey=s; else /第一次没解决彻底,继续解决冲突 int j=1; while(strcmp(W.t(key+j)%21.num,) j+; W.t(key+j)%21=s; 查找代码;while(xnumi!) key+=(xnumi- /求和 i+; key=key%21; if(!strcmp(W.tkey.num,xnu
4、m)/第一次查找,如果值相等直接赋值 printf(%s %s %sn,W.tkey.name,W.tkey.address,W.tkey.num); else /第一次没找到,继续查找 int j=1; while(strcmp(W.t(key+j)%21.num,xnum) j+; if(j=20) printf(查找元素不存在!,W.t(key+j)%21.name,W.t(key+j)%21.address,W.t(key+j)%21.num);/输出查找到得元素 主界面: printf(*电话号码查询系统*n 用电话号码查询 1 n 用用户名查询 2 n*n请输入您要的选项:n in
5、t x,y; while(scanf(%d,&x)!=-1) if(x=1)*电话号码查询*n 除留取余法 1 n 数字分析法 2 n*n请输入y值: scanf(y); while(y3) switch(y) case 1:chuliu();break;/调用除留取余函数 case 2:shuzi();/调用数字分析函数 default:printf(输入指令不存在! else if(x=2)*用户名查询 *n 分析法 3 n fenxi();/调用分析函数查找方式不存在!请重新输入n运行结果分析测试实例:wangping kaifeng 123456 wangdoudou luoyang
6、456789 zhaijiajai zhengzhou 147258 sunxueping zhoukou 258369收获及体会本次试验电话号码查询系统,看起来也不是想我想象中的那么难,他比较具有针对性,要求我们用哈希函数解决这倒比较实用的题目,但是这道题目用到的哈希函数仅仅是哈希中的九牛一毛,虽然写了大程序,但是对哈希表的了解还是一无所知,数据结构这门课程我认为有点难,也许是我c语言基础不够强吧,好多代码都不是很理解,以至于不能够灵活运用,其实通过每次实验我们都可以发现,数据结构的知识好像就是草原的草,密密麻麻的等待我们去拔掉,这是一项浩大的工程等待我们去建设,与此同时,也要求我们要踏实的
7、完成每一次作业,认真的去分析重要的代码,只有端正自己的态度,才能不断地学到新的知识,提高自己。程序设计代码:#include #includestdio.h#define NULL 0 int *p;struct node /建节点 char name20,address50; char num11; node * next;struct Node /建节点 typedef node* Lnode;typedef Node Tnode;typedef struct lode Lnode next;lode;typedef struct/顺序表存储下的哈希表 int size; Tnode t1
8、0000;Qnode;typedef struct/链表存储下的哈希表 lode L10000;Pnode;void chuliu()/除留取余法查询电话号码 Qnode W; memset(W.t,0,sizeof(W.t);/初始化 Tnode s;输入录入数据个数: int n; scanf(n); W.size=n; /录入元素请输入你要录入的元素: while(n-)姓名 地址 电话号码n%s %s %s,s.name,s.address,s.num); int i = 3,key; /线性探测再散列处理冲突请输入您要查找的电话号码: /查找 char xnum11;%s,xnum)
9、; int i = 3; int key=xnum2-; while(xnumi!void shuzi()/按电话号码-数字分析法 Qnode q1;请输入您要输入的数据个数: int n,m1,m2; memset(q1.t,0,sizeof(q1.t); q1.size=n; for(int i=0;i10000;i+) strcpy(q1.ti.num,/置空 m1=m2=0;请输入您要录入的元素:/读入数据 _int64 key; key=(_int64)s.num)%10000; /处理冲突(方法同上)strcmp(q1.tkey.num,) q1.tkey=s; i=1; m1+;
10、 while(strcmp(q1.t(key+i)%10000.num,) i+; q1.t(key+i)%10000=s; int k= 3; _int64 key=(_int64)xnum; key=key%10000;strcmp(q1.tkey.num,xnum),q1.tkey.name,q1.tkey.address,q1.tkey.num); while(strcmp(q1.t(key+j)%10000.num,xnum) j+;,q1.t(key+j)%10000.name,q1.t(key+j)%10000.address,q1.t(key+j)%10000.num); vo
11、id fenxi() Qnode q2; memset(q2.t,0,sizeof(q2.t); q2.size=n; strcpy(q2.ti.name, key=(_int64)s.name)%10000; /处理冲突strcmp(q2.tkey.name, q2.tkey=s; while(strcmp(q2.t(key+i)%10000.name, q2.t(key+i)%10000=s;请输入您要查找的名字: char xname20;,xname); int k= 1; _int64 key=(_int64)xname;strcmp(q2.tkey.name,xname),q2.tkey.name,q2.tkey.address,q2.tkey.num); while(strcmp(q2.t(key+j)%10000.name,xname) j+;,q2.t(key+j)%10000.name,q2.t(key+j)%10000.address,q2.t(key+j)%10000.num);void menu() int main()/函数 menu(); return 0;
copyright@ 2008-2023 冰点文库 网站版权所有
经营许可证编号:鄂ICP备19020893号-2