数据结构实验五

1、实验报告学院（系）名称：计算机与通信工程学院姓名王宏昌学号20135628专业计算机科学与技术班级2班实验名称实验五 查找算法应用课程名称数据结构课程代码实验时间2016实验地点7-220批改意见成绩教师签字： 1. 实验目的理解二叉排序树、AVL树的查找、插入、删除、建立算法的思想及程序实现；掌握散列存储结构的思想，能选择合适散列函数，实现不同冲突处理方法的散列表的查找、建立。散列表等查找算法解决实际问题。2. 实验要求具体实验题目：（任课教师根据实验大纲自己指定）每位同学可从下面题目中选择1-2题实现：1哈希表查找1）问题描述：针对某个集体的“人名”构造哈希表，解决按“人名”进行查找的索引

2、结构。2）实验要求：要求表的平均查找长度不超过R（R可以从键盘输入确定），完成相应的建表和查表程序。2构造二叉排序树，并进行中序遍历1）问题描述：从键盘读入一串整数构造一棵二叉排序树，并对得到的二叉排序述进行中序遍历，得到有序序列。2）实验要求：该二叉排序树以二叉链表存储3. 拼写检查1）问题描述：现在有一些英语单词需要做拼写检查，你的工具是一本词典。需要检查的单词，有的是词典中的单词，有的与词典中的单词相似，你的任务是发现这两种情况。单词A与单词B相似的情况有三种： 删除单词A的一个字母后得到单词B； 用任意一个字母替换单词A的一个字母后得到单词B； 在单词A的任意位置增加一个字母后得到单词

3、B。2）实验要求：发现词典中与给定单词相同或相似的单词。3. 实验过程记录（源程序、测试用例、测试结果及心得体会等）1.#include#include#define max 37#define HashLen 100#define m 74 typedef struct Namechar *name;int n;/名字对应的整数 Name;Name NameListmax;typedef struct Hashchar *name;int n;int sl;/查找长度 Hash;Hash HashListHashLen;void Initname()char *n;int i,j,s; Na

4、meL=adilijiang;/1036NameL=chenlong;/846NameL=dingtianzhu;/1189NameL=fengzhenxin;/1188NameL=gaobiao;/722NameL=henglixiang;/1166 2NameL=jiashihang;/1046NameL=lidebiao;/825NameL=liuguannan;/1074NameL=liushengjie;/

5、1175NameL=maxiaoyun;/987NameL=mayingjie;/957NameL=mengziheng;/1068 2NameL=sunyihong;/996NameL=tanshuang;/969NameL=wangguoyao;/1089NameL=wangpeng;/855NameL=wangruitao;/1089 2NameL=wangyuxin;/1002NameL=

6、xiaolingxu;/1096NameL=yangwanhao;/1069NameL=yangwen;/761NameL=zhangboyang;/1176NameL=zhangdoudou;/1192NameL=zhangxinxin;/1206NameL=zhouxianhe;/1091NameL=yanxu;/565NameL=fanliangya;/1050NameL=guzixuan;/891NameLi

7、=jiafeng;/724NameL=lixiang;/748 2NameL=liuziyi;/783NameL=ningxin;/763NameL=renyongqi;/988NameL=yuchengfang;/1167NameL=yuanmeng;/868NameL=zhangjunzhuo;/1323 3for(i=0;imax;i+)s=0;n=NameL;for(j=0;*(n+j)!=0;j+)s+=*(n

8、+j);NameListi.n=s;void CreateHashList()int i;for(i=0;iHashLen;i+)HashL=;HashListi.n=0;HashListi.sl=0;for(i=0;imax;i+)int sum=0; int address=(NameListi.n)%m; int d=address; if(HashListaddress.n=0) HashListaddress.n=NameListi.n; HashL=NameL; HashListaddress.sl=1; else

9、while(HashListd.n!=0) d=(d+19)%m; sum+; HashListd.n=NameListi.n; HashL=NameL; HashListd.sl=sum+1; void Search()char namemax;int i;printf(Enter names pinyin you want to search: );scanf(%s,name);int s0=0; for(i=0;imax;i+) /求出姓名的拼音所对应的整数(关键字) if(namei=0) break;s0+=namei; int sum=1; in

10、t address=s0%m; /使用哈希函数 int d=address; if(HashListaddress.n=0) printf(ERROR! NO RECORD!); else if(HashListaddress.n=s0) printf(Name: %s Keyword: %d Search length: 1,HashL,s0); else d=(d+19)%m; sum+; if(HashListd.n=s0) printf(Name: %s Keyword: %d Search length: %d,HashL,s0,sum);else

11、printf(NO RECORD!); void DisplayHashList()int i;printf(nsubtNamettKeywordtSearch lengthn);for(i=0;im;i+)if(HashListi.n!=0)if(HashListi.n800)printf(%dt%stt%dt%dn,i,HashL,HashListi.n,HashListi.sl);elseprintf(%dt%st%dt%dn,i,HashL,HashListi.n,HashListi.sl);int main()int a;Initname(); CreateHashList(); printf(Enter 1,2,0 to search, show Hash