数据结构实验报告七查找.docx
《数据结构实验报告七查找.docx》由会员分享，可在线阅读，更多相关《数据结构实验报告七查找.docx（22页珍藏版）》请在冰点文库上搜索。
数据结构实验报告七查找
（本实验项目方案受“教育部人才培养模式创新实验区（X3108005）”项目资助）
实验难度：
A□B□C□
序号
学号
姓名
成绩
1
2
3
指导教师
（签名）
学 期：
2010秋季学期
任课教师:
实验题目:
查找算法设计与实现
姓名:
王辉
学号:
20091120154
电子邮件:
完成提交时间：
2010年12月27日
云南大学软件学院2010学年秋季学期
《数据结构实验》成绩考核表
学号：
姓名：
本人承担角色：
评分项目
评分指标
分值
得分
实验构思（10%）
1.实验目的明确
5
2.实验内容理解透彻、对实验所涉及到的知识点分析到位
5
实验设计（15%）
1.有对基本数据结构的抽象数据类型定义
5
2.实验方案设计完整，数据结构、算法选择合理
5
3.算法结构和程序功能模块之间逻辑清晰、有相应的流程图
5
实验实现（25%）
1.代码编写规范、风格统一、注释清楚易读
5
2.程序运行正常，测试结果正确
15
3.界面友好、易于操作、有较强的容错性
5
实验报告撰写（10%）
1.内容详实无缺漏，文字流畅、图表清楚
5
2.实验结果分析客观、详细，实验体会真实可信，对原实验方案的改进和对实验内容的发散性思考
5
个人工作量（30%）
1.个人完成工作量
15
2.个人技术水平
10
3.团队合作精神
5
实验运作（10%）
1.有一定用户群
5
2.应用前景分析
5
综合得分：
（满分100分）
指导教师：
年月日
（注：
此表在难度为C时使用，每个成员一份。
）
（下面的内容由学生填写，格式统一为，字体:
楷体,行距:
固定行距18，字号:
小四，个人报告按下面每一项的百分比打分。
难度A满分70分，难度B满分90分）
一、【实验构思（Conceive）】（10%）
1哈希表查找。
根据全年级学生的姓名，构造一个哈希表，选择适当的哈希函数和解决冲突的方法，设计并实现插入、删除和查找算法。
熟悉各种查找算法的思想。
2、掌握查找的实现过程。
3、学会在不同情况下运用不同结构和算法求解问题。
4把每个学生的信息放在结构体中：
typedefstruct//记录
{
NAname;
NAtel;
NAadd;
}Record;
5voidgetin（Record*a）函数依次输入学生信息
6人名折叠处理，先将用户名进行折叠处理折叠处理后的数，用除留余数法构造哈希函数，并返回模值。
并采用二次探测再散列法解决冲突。
7姓名以汉语拼音形式，待填入哈希表的人名约30个，自行设计哈希函数，用线性探测再散列法或链地址法处理冲突；在查找的过程中给出比较的次数。
完成按姓名查询的操作。
将初始班级的通讯录信息存入文件。
二、【实验设计（Design）】（20%）
（本部分应包括：
抽象数据类型的功能规格说明、主程序模块、各子程序模块的伪码说明，主程序模块与各子程序模块间的调用关系）
1抽象数据类型的功能规格说明和结构体：
#include
#include
#include
#include
#defineMAXSIZE20//电话薄记录数量
#defineMAX_SIZE20//人名的最大长度
#defineHASHSIZE53//定义表长
#defineSUCCESS1
#defineUNSUCCESS-1
#defineLENsizeof（HashTable）
typedefintStatus;
typedefcharNA[MAX_SIZE];
typedefstruct//记录
{
NAname;
NAtel;
NAadd;
}Record;
typedefstruct//哈希表
{
Record*elem[HASHSIZE];//数据元素存储基址
intcount;//当前数据元素个数
intsize;//当前容量
}HashTable;
2主函数与各子函数的调用关系：
（通过switch（num）函数按不同功能要求分别调用相关函数）
intmain（intargc,char*argv[]）{
system（"color61"）;
intc,flag=1;
HashTable*H;
H=（HashTable*）malloc（LEN）;
for（inti=0;iH->elem[i]=NULL;
H->size=HASHSIZE;
H->count=0;
Recorda[MAXSIZE];
while
（1）
{
printf（"\n★☆★☆★☆★☆★☆wanghui★☆★☆★☆★☆★☆★☆"）;
printf（"\n★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★"）;
printf（"\n★☆★☆我的未来不是梦★☆★☆"）;
printf（"\n★☆★☆无聊中郁闷死★☆★☆"）;
printf（"\n★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★"）;
printf（"\n┏━━━━━━━━━━━━━┓"）;
printf（"\n★┃欢迎欢迎欢迎欢迎欢迎欢迎┃★"）;
printf（"\n〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓"）;
printf（"\n★★★★★★★哈希表的设计与实现★★★★★★"）;
printf（"\n【】.添加用户信息"）;
printf（"\n【】.读取所有用户信息"）;
printf（"\n【】.以姓名建立哈希表（再哈希法解决冲突）"）;
printf（"\n【】.以电话号码建立哈希表（再哈希法解决冲突）"）;
printf（"\n【】.查找并显示给定用户名的记录"）;
printf（"\n【】.查找并显示给定电话号码的记录"）;
printf（"\n【】.清屏"）;
printf（"\n【】.保存"）;
printf（"\n【】.退出程序"）;
printf（"\n温馨提示：
"）;
printf（"\nⅠ.进行操作前请先输出"）;
printf（"\nⅡ.进行操作前请先输出"）;
printf（"\n★★★★★★★〓〓〓〓〓〓〓〓〓★★★★★★"）;
printf（"\n"）;
printf（"请输入一个任务选项>>>"）;
printf（"\n"）;
intnum;
scanf（"%d",&num）;
switch（num）{
case1:
getin（a）;
break;
case2:
ShowInformation（a）;
break;
case3:
CreateHash1（H,a）;/*以姓名建立哈希表*/
break;
case4:
CreateHash2（H,a）;/*以电话号码建立哈希表*/
break;
case5:
c=0;
SearchHash1（H,c）;
break;
case6:
c=0;
SearchHash2（H,c）;
break;
case7:
Cls（a）;
break;
case8:
Save（）;
break;
case9:
return0;
break;
default:
printf（"你输错了，请重新输入!
"）;
printf（"\n"）;
}
}
system（"pause"）;
return0;
}
三、【实现描述（Implement）】（30%）
（本部分应包括：
抽象数据类型具体实现的函数原型说明、关键操作实现的伪码算法、函数设计、函数间的调用关系，关键的程序流程图等，给出关键算法的时间复杂度分析。
）
1主函数打印和主子函数调用：
intmain（intargc,char*argv[]）{
system（"color61"）;
intc,flag=1;
HashTable*H;
H=（HashTable*）malloc（LEN）;
for（inti=0;iH->elem[i]=NULL;
H->size=HASHSIZE;
H->count=0;
Recorda[MAXSIZE];
while
（1）
{
printf（"\n★☆★☆★☆★☆★☆申平★☆★☆★☆★☆★☆★☆"）;
printf（"\n★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★"）;
printf（"\n★☆★☆我的未来不是梦★☆★☆"）;
printf（"\n★☆★☆无聊中郁闷死★☆★☆"）;
printf（"\n★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★"）;
printf（"\n┏━━━━━━━━━━━━━┓"）;
printf（"\n★┃欢迎欢迎欢迎欢迎欢迎欢迎┃★"）;
printf（"\n〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓"）;
printf（"\n★★★★★★★哈希表的设计与实现★★★★★★"）;
printf（"\n【】.添加用户信息"）;
printf（"\n【】.读取所有用户信息"）;
printf（"\n【】.以姓名建立哈希表（再哈希法解决冲突）"）;
printf（"\n【】.以电话号码建立哈希表（再哈希法解决冲突）"）;
printf（"\n【】.查找并显示给定用户名的记录"）;
printf（"\n【】.查找并显示给定电话号码的记录"）;
printf（"\n【】.清屏"）;
printf（"\n【】.保存"）;
printf（"\n【】.退出程序"）;
printf（"\n温馨提示：
"）;
printf（"\nⅠ.进行操作前请先输出"）;
printf（"\nⅡ.进行操作前请先输出"）;
printf（"\n★★★★★★★〓〓〓〓〓〓〓〓〓★★★★★★"）;
printf（"\n"）;
printf（"请输入一个任务选项>>>"）;
printf（"\n"）;
intnum;
scanf（"%d",&num）;
switch（num）{
case1:
getin（a）;
break;
case2:
ShowInformation（a）;
break;
case3:
CreateHash1（H,a）;/*以姓名建立哈希表*/
break;
case4:
CreateHash2（H,a）;/*以电话号码建立哈希表*/
break;
case5:
c=0;
SearchHash1（H,c）;
break;
case6:
c=0;
SearchHash2（H,c）;
break;
case7:
Cls（a）;
break;
case8:
Save（）;
break;
case9:
return0;
break;
default:
printf（"你输错了，请重新输入!
"）;
printf（"\n"）;
}
}
system（"pause"）;
return0;
}
2键盘输入各人的信息:
voidgetin（Record*a）//键盘输入各人的信息
{
system（"cls"）;
printf（"输入要添加的个数：
\n"）;
scanf（"%d",&NUM_BER）;
inti;
for（i=0;iprintf（"请输入第%d个记录的用户名:
\n",i+1）;
scanf（"%s",a[i].name）;
printf（"请输入%d个记录的电话号码:
\n",i+1）;
scanf（"%s",a[i].tel）;
printf（"请输入第%d个记录的地址:
\n",i+1）;
scanf（"%s",a[i].add）;//gets（str2）;?
?
?
?
?
?
}
}
3显示输入的用户信息和人名的折叠处理:
voidShowInformation（Record*a）//显示输入的用户信息
{
system（"cls"）;
inti;
for（i=0;iprintf（"\n第%d个用户信息:
\n姓名：
%s\n电话号码：
%s\n联系地址：
%s\n",i+1,a[i].name,a[i].tel,a[i].add）;
}
voidCls（Record*a）{
printf（"*"）;
system（"cls"）;
}
longfold（NAs）//人名的折叠处理
{
char*p;
longsum=0;
NAss;
strcpy（ss,s）;//复制字符串，不改变原字符串的大小写
strupr（ss）;//将字符串ss转换为大写形式
p=ss;
while（*p!
='\0'）
sum+=*p++;
printf（"\nsum====================%d",sum）;
returnsum;
}
5哈希函数,先将用户名进行折叠处理,折叠处理后的数，用除留余数法构造哈希函数并返回模值;把字符串转换成整型数,用除留余数法构造哈希函数并返回模值:
intHash1（NAstr）//哈希函数
{
longn;
intm;
n=fold（str）;//先将用户名进行折叠处理
m=n%HASHSIZE;//折叠处理后的数，用除留余数法构造哈希函数
returnm;//并返回模值
}
intHash2（NAstr）//哈希函数
{
longn;
intm;
n=atoi（str）;//把字符串转换成整型数.
m=n%HASHSIZE;//用除留余数法构造哈希函数
returnm;//并返回模值
}
6冲突处理函数，采用二次探测再散列法解决冲突:
Statuscollision（intp,int&c）//冲突处理函数，采用二次探测再散列法解决冲突
{
inti,q;
i=c/2+1;
while（iif（c%2==0）{
c++;
q=（p+i*i）%HASHSIZE;
if（q>=0）returnq;
elsei=c/2+1;
}
else{
q=（p-i*i）%HASHSIZE;
c++;
if（q>=0）returnq;
elsei=c/2+1;
}
}
returnUNSUCCESS;
}
voidbenGetTime（）;
voidCreateHash1（HashTable*H,Record*a）//建表，以人的姓名为关键字，建立相应的散列表
{
system（"cls"）;//若哈希地址冲突，进行冲突处理
benGetTime（）;
inti,p=-1,c,pp;
for（i=0;ic=0;
p=Hash1（a[i].name）;
pp=p;
while（H->elem[pp]!
=NULL）{
pp=collision（p,c）;
if（pp<0）{
printf（"第%d记录无法解决冲突",i+1）;//需要显示冲突次数时输出
continue;
}//无法解决冲突，跳入下一循环
}
H->elem[pp]=&（a[i]）;//求得哈希地址，将信息存入
H->count++;
printf（"第%d个记录冲突次数为%d。
\n",i+1,c）;//需要显示冲突次数时输出
}
printf（"\n建表完成!
\n此哈希表容量为%d,当前表内存储的记录个数为%d.\n",HASHSIZE,H->count）;
benGetTime（）;
}
7在通讯录里查找姓名关键字，若查找成功，显示信息:
voidSearchHash1（HashTable*H,int&c）//在通讯录里查找姓名关键字，若查找成功，显示信息
{
system（"cls"）;//c用来记录冲突次数,查找成功时显示冲突次数
benGetTime（）;
NAstr;
printf（"\n请输入要查找记录的姓名：
\n"）;
scanf（"%s",str）;
intp,pp;
p=Hash1（str）;
pp=p;
while（（H->elem[pp]!
=NULL）&&（eq（str,H->elem[pp]->name）==-1））
pp=collision（p,c）;
if（H->elem[pp]!
=NULL&&eq（str,H->elem[pp]->name）==1）{
printf（"\n查找成功！
\n查找过程冲突次数为%d．以下是您需要要查找的信息：
\n\n",c）;
printf（"姓名：
%s\n电话号码：
%s\n联系地址：
%s\n",H->elem[pp]->name,H->elem[pp]->tel,H->elem[pp]->add）;
}
elseprintf（"\n此人不存在，查找不成功!
\n"）;
benGetTime（）;
}
8建表，以电话号码为关键字，建立相应的散列表,若哈希地址冲突，进行冲突处理:
voidCreateHash2（HashTable*H,Record*a）//建表，以电话号码为关键字，建立相应的散列表
{
//若哈希地址冲突，进行冲突处理
benGetTime（）;
inti,p=-1,c,pp;
for（i=0;ic=0;
p=Hash2（a[i].tel）;
pp=p;
while（H->elem[pp]!
=NULL）{
pp=collision（p,c）;
if（pp<0）{
printf（"第%d记录无法解决冲突",i+1）;//需要显示冲突次数时输出
continue;
}//无法解决冲突，跳入下一循环
}
H->elem[pp]=&（a[i]）;//求得哈希地址，将信息存入
H->count++;
printf（"第%d个记录冲突次数为%d。
\n",i+1,c）;//需要显示冲突次数时输出
}
printf（"\n建表完成!
\n此哈希表容量为%d,当前表内存储的记录个数为%d.\n",HASHSIZE,H->count）;
benGetTime（）;
}
9在通讯录里查找电话号码关键字，若查找成功，显示信:
voidSearchHash2（HashTable*H,int&c）//在通讯录里查找电话号码关键字，若查找成功，显示信息
{
system（"cls"）;//c用来记录冲突次数,查找成功时显示冲突次数
benGetTime（）;
NAtele;
printf（"\n请输入要查找记录的电话号码：
\n"）;
scanf（"%s",tele）;
intp,pp;
p=Hash2（tele）;
pp=p;
while（（H->elem[pp]!
=NULL）&&（eq（tele,H->elem[pp]->tel）==-1））
pp=collision（p,c）;
if（H->elem[pp]!
=NULL&&eq（tele,H->elem[pp]->tel）==1）{
printf（"\n查找成功！
\n查找过程冲突次数为%d．以下是您需要要查找的信息：
\n\n",c）;
printf（"姓名：
%s\n电话号码：
%s\n联系地址：
%s\n",H->elem[pp]->name,H->elem[pp]->tel,H->elem[pp]->add）;
}
elseprintf（"\n此人不存在，查找不成功!
\n"）;
benGetTime（）;
}
voidSave（）{
FILE*fp;
if（（fp=fopen（"c:
\test.txt","w"））==NULL）{
printf（"\nERRORopeningcustometfile"）;
}
fclose（fp）;
}
四、【测试结果（Testing）】（10%）
（本部分应包括：
对实验的测试结果，应具体列出每次测试所输入的数据以及输出的数据，并对测试结果进行分析总结）
五、【实验总结】（10%）
（本部分应包括：
自己在实验中完成的任务，注意组内的任意一位同学都必须独立完成至少一项接口的实现；对所完成实验的经验总结、心得）
1通常有两类方法处理冲突：
开放定址（OpenAddressing）法和拉链（Chaining）法。
前者是将所有结点均存放在散列表T[0..m-1]中；后者通常是将互为同义词的结点链成一个单链表，而将此链表的头指针放在散列表T[0..m-1]中。
2用开放定址法解决冲突的做法是：
当冲突发生时，使用某种探查（亦称探测）技术在散列表中形成一个探查（测）序列。
沿此序列逐个单元地查找，直到找到给定的关键字，或者碰到一个开放的地址（即该地址单元为空）为止（若要插入，在探查到开放的地址，则可将待插入的新结点存人该地址单元）。
查找时探查到开放的地址则表明表中无待查的关键字，即查找失败。
注意：
①用开放定址法建立散列表时，建表前须将表中所有单元（更严格地说，是指单元中存储的关键字）置空。
②空单元的表示与具体的应用相关。
3拉链法解决冲突的方法
拉链法解决冲突的做法是：
将所有关键字为同义词的结点链接在同一个单链表中。
若选定的散列表长度为m，则可将散列表定义为一个由m个头指针组成的指针数组T[0..m-1]。
凡是散列地址为i的结点，均插入到以T[i]为头指针的单链表中。
T中各分量的初值均应为空指针。
在拉链法中，装填因子α可以大于1，但一般均取α≤1.
4拉链法的优点
与开放定址法相比，拉链法有如下几个
升级会员 