數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)五

1、實(shí)驗(yàn)報(bào)告學(xué)院（系）名稱：計(jì)算機(jī)與通信工程學(xué)院姓名王宏昌學(xué)號(hào)20135628專業(yè)計(jì)算機(jī)科學(xué)與技術(shù)班級(jí)2班實(shí)驗(yàn)名稱實(shí)驗(yàn)五 查找算法應(yīng)用課程名稱數(shù)據(jù)結(jié)構(gòu)課程代碼實(shí)驗(yàn)時(shí)間2016實(shí)驗(yàn)地點(diǎn)7-220批改意見成績教師簽字： 1. 實(shí)驗(yàn)?zāi)康睦斫舛媾判驑?、AVL樹的查找、插入、刪除、建立算法的思想及程序?qū)崿F(xiàn)；掌握散列存儲(chǔ)結(jié)構(gòu)的思想，能選擇合適散列函數(shù)，實(shí)現(xiàn)不同沖突處理方法的散列表的查找、建立。散列表等查找算法解決實(shí)際問題。2. 實(shí)驗(yàn)要求具體實(shí)驗(yàn)題目：（任課教師根據(jù)實(shí)驗(yàn)大綱自己指定）每位同學(xué)可從下面題目中選擇1-2題實(shí)現(xiàn)：1哈希表查找1）問題描述：針對(duì)某個(gè)集體的“人名”構(gòu)造哈希表，解決按“人名”進(jìn)行查找的索引

2、結(jié)構(gòu)。2）實(shí)驗(yàn)要求：要求表的平均查找長度不超過R（R可以從鍵盤輸入確定），完成相應(yīng)的建表和查表程序。2構(gòu)造二叉排序樹，并進(jìn)行中序遍歷1）問題描述：從鍵盤讀入一串整數(shù)構(gòu)造一棵二叉排序樹，并對(duì)得到的二叉排序述進(jìn)行中序遍歷，得到有序序列。2）實(shí)驗(yàn)要求：該二叉排序樹以二叉鏈表存儲(chǔ)3. 拼寫檢查1）問題描述：現(xiàn)在有一些英語單詞需要做拼寫檢查，你的工具是一本詞典。需要檢查的單詞，有的是詞典中的單詞，有的與詞典中的單詞相似，你的任務(wù)是發(fā)現(xiàn)這兩種情況。單詞A與單詞B相似的情況有三種： 刪除單詞A的一個(gè)字母后得到單詞B； 用任意一個(gè)字母替換單詞A的一個(gè)字母后得到單詞B； 在單詞A的任意位置增加一個(gè)字母后得到單詞

3、B。2）實(shí)驗(yàn)要求：發(fā)現(xiàn)詞典中與給定單詞相同或相似的單詞。3. 實(shí)驗(yàn)過程記錄（源程序、測(cè)試用例、測(cè)試結(jié)果及心得體會(huì)等）1.#include#include#define max 37#define HashLen 100#define m 74 typedef struct Namechar *name;int n;/名字對(duì)應(yīng)的整數(shù) 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+) /求出姓名的拼音所對(duì)應(yīng)的整數(shù)(關(guān)鍵字) if(namei=0) break;s0+=namei; int sum=1; in

10、t address=s0%m; /使用哈希函數(shù) 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