1、洛 陽 理 工 學 院課 程 設 計 說 明 書課程名稱 數 據 結 構 設計課題 哈 希 表 的 設 計 與 實 現 專 業 班 級 學 號 姓 名 完成日期 2 課 程 設 計 任 務 書設計題目： 哈 希 表 的 設 計 與 實 現 設計內容與要求：設計哈希表實現電話號碼查詢系統。基本要求1、設每個記錄有下列數據項：電話號碼、用戶名、地址；2、從鍵盤輸入各記錄，分別以電話號碼和用戶名為關鍵字建立哈希表；3、采用再哈希法解決沖突；4、查找并顯示給定電話號碼的記錄；5、查找并顯示給定用戶名的記錄。6、在哈希函數確定的前提下，考察平均查找長度的變化。  指導教師： 2014 年 課

2、程 設 計 評 語成績： 指導教師： 年 月 日洛 陽 理 工 學 院 課 程 設 計 報 告【問題描述】如何設計一個結構體數組使該數組中每個元素包含電話號碼、用戶名、地址。如何分別以電話號碼和用戶名為關鍵字建立哈希表。如何利用線性探測再散列法解決沖突。如何實現用哈希法查找并顯示給定電話號碼的記錄。如何查找并顯示給定用戶的記錄。手工計算查找不成功的平均查找長度。 【基本要求】設計哈希表實現電話號碼查詢系統。設計程序完成以下要求：（1）、設每個記錄有下列數據項：電話號碼、用戶名、地址；（2）、從鍵盤輸入各記錄，分別以電話號碼和用戶名為關鍵字建立哈希表；（3）、采用再哈希法解決沖突（4）、查找并顯

3、示給定電話號碼的記錄；（5）、查找并顯示給定用戶的記錄。（6）、在哈希函數確定的前提下，考察平均查找長度的變化。【測試數據】1.用戶名：weiguo，號碼：123，地址：gansu2.用戶名：zhangkui，號碼：321，地址：shanxi【算法思想】進入主函數,用戶輸入1:輸入哈希表元素，然后再選擇2或者3按照用戶名或者電話號碼散列，在這下面又有分支語句選擇解決沖突的辦法，用線性探測再散列還是再哈希法。生成哈希表之后，選擇查找操作3分別以用戶名和電話號碼為關鍵字進行查找。最后，輸出查找不成功的平均查找長度。在本程序當中用了兩種解決沖突的辦法，分別是線性探測再散列和再哈希法。哈希函數構造方法

4、是，除留余數法。具體流程圖1所示:開始選擇1調用Create創建輔助數組按0結束選擇3以號碼為關鍵字創建哈希表creat_num選擇2以姓名為關鍵字創建哈希表creat_name解決沖突解決沖突線性探測再哈希法再哈希法線性探測按號碼查找，調用Search_num函數按用戶名查找，調用Search_name函數查找不成功的平均查找長度選擇0退出圖 1 具體流程圖【模塊劃分】本程序在菜單選項下包含六個子模塊，如圖2所示圖2 模塊劃分【數據結構】本設計涉及到的數據結構為：哈希表。要求輸入電話號碼、用戶名、地址三個信息，并要求分別以電話號碼和用戶名為關鍵字進行查找，所以本問題要用到兩個哈希函數，進行哈

5、希查找。/*哈希表結構體*/typedef struct char name20; /用戶名char phone20;/電話char add30; /地址Record;Record InfM;/全局變量Record HM; /全局變量【測試情況】1. 運行程序，顯示主菜單并選擇選項1來創建哈希表2.執行選項1，輸入元素內容3.執行選項2，按用戶名散列創建哈希表4.執行選項3，按號碼散列創建哈希表5.執行選項4，按用戶名查找6.執行選項4，按號碼查找7.執行選項5，輸出查找不成功的平均查找長度【心得】 【源程序】/*電話號碼查詢系統*/#include<stdio.h>#includ

6、e<string.h>#include<stdlib.h>#define M 10#define NULLKEY "0"/*哈希表結構體*/typedef struct char name20; /用戶名char phone20;/電話char add20; /地址Record;Record InfM;/定義輔助數組為全局變量Record HM; /定義哈希表為全局變量/*菜單函數*/int menu() int m; system("cls"); system("color 0a"); printf(&quo

7、t;tt*電話號碼查詢系統*n");printf("n");printf("tt_ 主 菜 單 _n"); printf("tt| 1. 哈希表的創建 |n"); printf("tt| 2. 按用戶名散列 |n"); printf("tt| 3. 按 號 碼散列 |n"); printf("tt| 4. 查 找 操 作 |n"); printf("tt| 5. 平均查找長度 |n");printf("tt| 0. 退 出 程 序 |n

8、"); printf("tt-n"); printf("n");printf("ttt 請輸入您的選項<0-5>:n"); scanf("%d",&m); return(m); /創建輔助數組int Create(Record HM)int i;char sign; for(i=0;i<10;i+)/初始化哈希表strcpy(Hi.add,"0");strcpy(Hi.phone,"0");strcpy(H,"0&qu

9、ot;);i=0; while(sign!='n'&&sign!='N') printf("請輸入名字n"); scanf("%s",I); printf("請輸入號碼n"); scanf("%s",Infi.phone); printf("請輸入地址n"); scanf("%s",Infi.add); printf("ttt還需要繼續輸入嗎?(Y/N)"); scanf("ttt%

10、c",&sign); i+; return i;/以用戶名為關鍵字的哈希函數int Hash_name(char name20)int i=0;int a=0;while(namei!='0')a=a+namei;i+;a=a%7;/對小于哈希表的最大素數求余，此處哈希表長為10，對7求余return(a);/再哈希 int name_again(char name20) int i,h;h=(int)name1;for(i=2;i<20;i+)h=h+(int)namei;h=h%7;return h;/以用戶名為關鍵字創建哈希表void creat_

11、name(Record InfM,int m,Record HM)int j,key=0; for(j=0;j<m;j+) key=Hash_name(I);/計算哈希地址 while(1) if(strcmp(H,NULLKEY)=0)/判斷該位置是否為空，不為空就把輔助數組中的元素存到該位置 strcpy(H,I); strcpy(Hkey.phone,Infj.phone); strcpy(Hkey.add,Infj.add); break; else key+;/如果為空，采用線性探測法，將元素后移 /再哈希法voi

12、d again_put(Record InfM,int m,Record HM)int j,key=0; for(j=0;j<m;j+) key=Hash_name(I);/計算哈希地址 while(1) if(strcmp(H,NULLKEY)=0)/輔助數組中的元素存到該位置 strcpy(H,I); strcpy(Hkey.phone,Infj.phone); strcpy(Hkey.add,Infj.add); break; else key=name_again(I);/再哈希 /以號碼為關鍵字的哈

13、希函數int Hash_phone(char phone20)int i=0;int b=0;while(phonei!='0')/計算電話號碼中每個字符的ASCII碼值相加b=b+phonei;i+;b=b%7;/對小于哈希表的最大素數求余，此處哈希表長為10，對7求余return(b);/再哈希int phone_again(char phone20) int i,h;h=(int)phone1;for(i=2;i<20;i+)h=h+(int)phonei;h=h%7;return h;/以電話號碼為關鍵字創建哈希表void creat_phone(Record I

14、nfM,int m,Record HM)int j,key=0;for(j=0;j<m;j+) key=Hash_phone(Infj.phone);/計算哈希地址 while(1) if(strcmp(Hkey.phone,NULLKEY)=0)/把輔助數組中的元素存到該位置 strcpy(H,I); strcpy(Hkey.phone,Infj.phone); strcpy(Hkey.add,Infj.add); break; else key+;/如果為空，采用線性探測法，將元素后移 /再哈希法void again_put2(Record InfM,

15、int m,Record HM)int j,key=0; for(j=0;j<m;j+) key=Hash_phone(Infj.phone);/計算哈希地址 while(1) if(strcmp(Hkey.phone,NULLKEY)=0)/判斷該位置是否為空，不為空就把輔助數組中的元素存到該位置 strcpy(H,I); strcpy(Hkey.phone,Infj.phone); strcpy(Hkey.add,Infj.add); break; else key=phone_again(Infj.phone);/再哈希 /按姓名查找int Sear

16、ch_name(Record HM,char name20)int h0;int i;int hi;int result;h0=Hash_name(name);if (H=NULLKEY) printf("查找名字不存在!n");return (-1);else result = strcmp(H,name);if (result = 0) return (h0);else / 用線性探測再散列解決沖突 for (i=1; i<=M-1; i+)hi=(h0+i) % M;if (H=NULLKEY) return (-1);

17、elseresult = strcmp(H,name);if (result = 0) return (hi);return (-1);/按 號碼查找int Search_phone(Record HM,char phone20)int h0;int i;int hi;int result;h0=Hash_phone(phone);if (Hh0.phone=NULLKEY) printf("查找號碼不存在!n");return (-1);else result = strcmp(Hh0.phone,phone);if (result = 0) return

18、(h0);else / 用線性探測再散列解決沖突 for (i=1; i<=M-1; i+)hi=(h0+i) % M;if (Hhi.phone=NULLKEY) return (-1);elseresult = strcmp(Hhi.phone,phone);if (result = 0) return (hi);return (-1);/以用戶名為關鍵字的哈希表的輸出函數void Print_name(Record HM)int i;printf("t哈希地址t用戶名tt號碼tt地址n");for(i=0;i<10;i+)if(strcmp(H

19、,"0")!=0)printf("t%dtt%stt%stt%sn",i,H,Hi.phone,Hi.add);/以電話號碼為關鍵字的哈希表的輸出函數void Print_phone(Record HM)int i;printf("t哈希地址t用戶名tt號碼tt地址n");for(i=0;i<10;i+)if(strcmp(Hi.phone,"0")!=0) printf("t%dtt%stt%stt%sn",i,H,Hi.phone,Hi.add);/查找不成功的

20、平均查找長度void unsucc_length(int m) char phone20;int i,j;int count;int asl=0;float unasl;Hash_phone(phone);for(i=0;i<7;i+)j=i;count=1;while(strcmp(H,NULLKEY)!=0)count+;j=(j+1)%7;asl=asl+count;unasl=(float)asl/7;printf("查找不成功的平均查找長度為:%5.2fn",unasl);void main()/主函數char name20,phone20;in

21、t m;int n,p;int find;int w,k; while(1)switch(menu()case 1:m=Create(H);/創建輔助數組break;case 2:printf("ttt*n");printf("ttt* 1.線性再散列*n");printf("ttt* 2.再哈希法散列 *n");printf("ttt* 3.退出本菜單 *n");printf("ttt*n"); printf("輸入散列選項 <0-2> :n"); scanf(

22、"%d",&p); switch(p)case 1:creat_name(Inf,m,H);Print_name(H);break;case 2:again_put(Inf,m,H);Print_name(H);break;break;case 3:printf("ttt*n");printf("ttt* 1.線性再散列*n");printf("ttt* 2.再哈希法散列 *n");printf("ttt* 3.退出本菜單 *n");printf("ttt*n");

23、printf("輸入散列選項 <0-2> :n"); scanf("%d",&n); switch(n)case 1:creat_phone(Inf,m,H);Print_phone(H);break;case 2:again_put(Inf,m,H);Print_phone(H);break;break;case 4:printf("ttt*n");printf("ttt* 1.按用戶名查詢*n");printf("ttt* 2.按電話查詢 *n");printf(&quo

24、t;ttt* 3.退出本菜單 *n");printf("ttt*n"); printf("輸入查找條件 <0-2> :n"); scanf("%d",&find); switch(find) case 1: printf("n請輸入要查找的名字：n"); scanf("%s",name); k=Search_name(H,name);/k=Hash_again( H, name);if(k!=-1) printf("查找該人的信息是:n"); printf(&qu