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

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

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

3、B。2）實驗要求：發(fā)現(xiàn)詞典中與給定單詞相同或相似的單詞。3. 實驗過程記錄（源程序、測試用例、測試結(jié)果及心得體會等）1.#include#include#define max 37#define HashLen 100#define m 74 typedef struct Namechar *name;int n;/名字對應(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+) /求出姓名的拼音所對應(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