哈希表_數(shù)據(jù)結(jié)構(gòu)課設

1、洛陽理工學院課程設計說明書課程名稱數(shù)據(jù)結(jié)構(gòu)設計課題哈希表的設計與實現(xiàn)專業(yè)班級學號姓名完成日期2.課程設計任務書設計題目：哈希表的設計與實現(xiàn)設計內(nèi)容與要求：設計哈希表實現(xiàn)電話號碼查詢系統(tǒng)。 基本要求 1、設每個記錄有下列數(shù)據(jù)項：電話號碼、用戶名、地址；2、從鍵盤輸入各記錄，分別以電話號碼和用戶名為關(guān)鍵字建立哈希表；3、采用再哈希法解決沖突；4、查找并顯示給定電話號碼的記錄；5、查找并顯示給定用戶名的記錄。6、在哈希函數(shù)確定的前提下，考察平均查找長度的變化。指導教師：2014年課程設計評語成績：指導教師：年月日.【問題描述】如何設計一個結(jié)構(gòu)體數(shù)組使該數(shù)組中每個元素包含電話號碼、用戶名、地址。如何分

2、別以電話號碼和用戶名為關(guān)鍵字建立哈希表。如何利用線性探測再散列法解決沖突。如何實現(xiàn)用哈希法查找并顯示給定電話號碼的記錄。如何查找并顯示給定用戶的記錄。手工計算查找不成功的平均查找長度?！净疽蟆吭O計哈希表實現(xiàn)電話號碼查詢系統(tǒng)。設計程序完成以下要求：（ 1）、設每個記錄有下列數(shù)據(jù)項：電話號碼、用戶名、地址；（ 2）、從鍵盤輸入各記錄，分別以電話號碼和用戶名為關(guān)鍵字建立哈希表；（ 3）、采用再哈希法解決沖突（ 4）、查找并顯示給定電話號碼的記錄；（ 5）、查找并顯示給定用戶的記錄。（ 6）、在哈希函數(shù)確定的前提下，考察平均查找長度的變化?！緶y試數(shù)據(jù)】1. 用戶名： weiguo，號碼： 123，

3、地址： gansu2. 用戶名： zhangkui ，號碼： 321，地址： shanxi【算法思想】進入主函數(shù) ,用戶輸入 1: 輸入哈希表元素，然后再選擇 2 或者 3 按照用戶名或者電話號碼散列，在這下面又有分支語句選擇解決沖突的辦法，用線性探測再散列還是再哈希法。生成哈希表之后，選擇查找操作3 分別以用戶名和電話號碼為關(guān)鍵字進行查找。最后，輸出查找不成功的平均查找長度。在本程序當中用了兩種解決沖突的辦法，分別是線性探測再散列和再哈希法。哈希函數(shù)構(gòu)造方法是，除留余數(shù)法。.具體流程圖 1 所示 :開始選擇 1 調(diào)用 Create 創(chuàng)建輔助數(shù)組選擇 2 以姓名為關(guān)鍵字按0結(jié)束選擇 3 以號碼

4、為關(guān)鍵字創(chuàng)建哈希表 creat_name創(chuàng)建哈希表 creat_num解決沖突解決沖突線性探測再哈希法線性探測再哈希法按用戶名查找，調(diào)用Search_name 函數(shù)按號碼查找，調(diào)用Search_num 函數(shù)查找不成功的平均查找長度選擇 0退出圖 1具體流程圖.【模塊劃分】本程序在菜單選項下包含六個子模塊，如圖2 所示創(chuàng)建查找以姓名散列主菜單以電話散列平均查找長度退出程序圖 2模塊劃分【數(shù)據(jù)結(jié)構(gòu)】本設計涉及到的數(shù)據(jù)結(jié)構(gòu)為：哈希表。要求輸入電話號碼、用戶名、地址三個信息，并要求分別以電話號碼和用戶名為關(guān)鍵字進行查找，所以本問題要用到兩個哈希函數(shù)，進行哈希查找。/* 哈希表結(jié)構(gòu)體 */typedef

5、 structchar name20; /用戶名char phone20;/電話char add30; /地址Record;Record InfM;/全局變量Record HM; /全局變量.【測試情況】1. 運行程序，顯示主菜單并選擇選項 1 來創(chuàng)建哈希表2. 執(zhí)行選項 1，輸入元素內(nèi)容3. 執(zhí)行選項 2，按用戶名散列創(chuàng)建哈希表.4. 執(zhí)行選項 3，按號碼散列創(chuàng)建哈希表5. 執(zhí)行選項 4，按用戶名查找6. 執(zhí)行選項 4，按號碼查找.7. 執(zhí)行選項 5，輸出查找不成功的平均查找長度【心得】【源程序】/*電話號碼查詢系統(tǒng) */#include#include#include#define M 1

6、0#define NULLKEY 0/* 哈希表結(jié)構(gòu)體 */typedef struct.char name20; /用戶名char phone20;/電話char add20; /地址Record;Record InfM;/定義輔助數(shù)組為全局變量Record HM; /定義哈希表為全局變量/* 菜單函數(shù) */int menu()int m;system(cls);system(color 0a);printf(tt*電話號碼查詢系統(tǒng)*n);printf(n);printf(tt_主菜單_n);printf(tt|1.哈希表的創(chuàng)建|n);printf(tt|2.按用戶名散列|n);printf

7、(tt|3.按號碼散列|n);printf(tt|4.查 找 操 作|n);printf(tt|5.平均查找長度|n);printf(tt|0.退出程序|n);printf(tt-n);printf(n);printf(ttt請輸入您的選項 :n);scanf(%d,&m);return(m);/ 創(chuàng)建輔助數(shù)組int Create(Record HM)int i;char sign;for(i=0;i10;i+)/初始化哈希表.strcpy(Hi.add,0);strcpy(Hi.phone,0);strcpy(H,0);i=0;while(sign!=n&sign!=N)prin

8、tf(請輸入名字 n);scanf(%s,I);printf(請輸入號碼 n);scanf(%s,Infi.phone);printf(請輸入地址 n);scanf(%s,Infi.add);printf(ttt還需要繼續(xù)輸入嗎 ?(Y/N);scanf(ttt%c,&sign);i+;return i;/ 以用戶名為關(guān)鍵字的哈希函數(shù) int Hash_name(char name20)int i=0; int a=0; while(namei!=0)a=a+namei;i+;a=a%7;/ 對小于哈希表的最大素數(shù)求余，此處哈希表長為 10，對 7 求余 return(a);/

9、 再哈希int name_again(char name20)int i,h;h=(int)name1;for(i=2;i20;i+)h=h+(int)namei;h=h%7;return h;/ 以用戶名為關(guān)鍵字創(chuàng)建哈希表.void creat_name(Record InfM,int m,Record HM)int j,key=0;for(j=0;jm;j+)key=Hash_name(I);/計算哈希地址while(1)if(strcmp(H,NULLKEY)=0)/判斷該位置是否為空，不為空就把輔助數(shù)組中的元素存到該位置strcpy(H,

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

11、.phone,Infj.phone);strcpy(Hkey.add,Infj.add);break;elsekey=name_again(I);/再哈希 / 以號碼為關(guān)鍵字的哈希函數(shù)int Hash_phone(char phone20).int i=0;int b=0;while(phonei!=0)/計算電話號碼中每個字符的ASCII 碼值相加b=b+phonei;i+;b=b%7;/ 對小于哈希表的最大素數(shù)求余，此處哈希表長為 10，對 7 求余 return(b);/ 再哈希int phone_again(char phone20)int i,h;h=(int)pho

12、ne1;for(i=2;i20;i+)h=h+(int)phonei;h=h%7;return h;/ 以電話號碼為關(guān)鍵字創(chuàng)建哈希表void creat_phone(Record InfM,int m,Record HM)int j,key=0;for(j=0;jm;j+)key=Hash_phone(Infj.phone);/計算哈希地址while(1)if(strcmp(Hkey.phone,NULLKEY)=0)/把輔助數(shù)組中的元素存到該位置strcpy(H,I);strcpy(Hkey.phone,Infj.phone);strcpy(Hkey.add,

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

14、fj.add);break;elsekey=phone_again(Infj.phone);/再哈希/ 按姓名查找int Search_name(Record HM,char name20)int h0;int i;int hi;int result;h0=Hash_name(name);if (H=NULLKEY)printf(查找名字不存在 !n);return (-1);elseresult = strcmp(H,name);if (result = 0)return (h0);else/用線性探測再散列解決沖突for (i=1; i=M-1; i+).hi=

15、(h0+i) % M;if (H=NULLKEY)return (-1);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);elseresult = strcmp(Hh0.phone

16、,phone);if (result = 0)return (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);/ 以用戶名為關(guān)鍵字的哈希表的輸出函數(shù) void Print_name(Record HM)int i;printf(t 哈希地址 t 用戶名 tt 號碼 tt 地址 n); for(i=0;i10;i+)

17、if(strcmp(H,0)!=0)printf(t%dtt%stt%stt%sn,i,H,Hi.phone,Hi.add);/ 以電話號碼為關(guān)鍵字的哈希表的輸出函數(shù)void Print_phone(Record HM)int i;printf(t哈希地址 t用戶名 tt號碼 tt地址 n);for(i=0;i10;i+)if(strcmp(Hi.phone,0)!=0)printf(t%dtt%stt%stt%sn,i,H,Hi.phone,Hi.add);/ 查找不成功的平均查找長度 void unsucc_length(int m)char phone

18、20; int i,j;int count;.int asl=0;float unasl;Hash_phone(phone);for(i=0;i7;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()/主函數(shù)char name20,phone20;int m;int n,p;int find;int w,k;while(1)switch(menu()case 1

19、:m=Create(H);/創(chuàng)建輔助數(shù)組break;case 2:printf(ttt*n);printf(ttt* 1.線性再散列 *n);printf(ttt* 2.再哈希法散列*n);printf(ttt* 3.退出本菜單*n);printf(ttt*n);printf(輸入散列選項 :n);scanf(%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(

20、ttt* 1.線性再散列 *n);printf(ttt* 2.再哈希法散列*n);printf(ttt* 3.退出本菜單*n);printf(ttt*n);printf(輸入散列選項 :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(ttt* 3.退出本菜單*n);printf(ttt*n);printf(輸入查找條件 :n);scanf(%d,&find);switch(find)case 1:print