哈希表-數(shù)據(jù)結構課設

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

指導2014年課程設計評語成績：指導年月日..[問題描述]如何設計一個結構體數(shù)組使該數(shù)組中每個元素包含號碼、用戶名、地址。如何分別以號碼和用戶名為關鍵字建立哈希表。如何利用線性探測再散列法解決沖突。如何實現(xiàn)用哈希法查找并顯示給定號碼的記錄。如何查找并顯示給定用戶的記錄。手工計算查找不成功的平均查找長度。[基本要求]設計哈希表實現(xiàn)號碼查詢系統(tǒng)。設計程序完成以下要求：〔1、設每個記錄有下列數(shù)據(jù)項：號碼、用戶名、地址；〔2、從鍵盤輸入各記錄,分別以號碼和用戶名為關鍵字建立哈希表；〔3、采用再哈希法解決沖突〔4、查找并顯示給定號碼的記錄；〔5、查找并顯示給定用戶的記錄。〔6、在哈希函數(shù)確定的前提下,考察平均查找長度的變化。[測試數(shù)據(jù)]1.用戶名：weiguo,號碼：123,地址：gansu2.用戶名：zhangkui,號碼：321,地址：shanxi[算法思想]進入主函數(shù),用戶輸入1:輸入哈希表元素,然后再選擇2或者3按照用戶名或者號碼散列,在這下面又有分支語句選擇解決沖突的辦法,用線性探測再散列還是再哈希法。生成哈希表之后,選擇查找操作3分別以用戶名和號碼為關鍵字進行查找。最后,輸出查找不成功的平均查找長度。在本程序當中用了兩種解決沖突的辦法,分別是線性探測再散列和再哈希法。哈希函數(shù)構造方法是,除留余數(shù)法。具體流程圖1所示:開始開始選擇1調(diào)用Create創(chuàng)建輔助數(shù)組選擇1調(diào)用Create創(chuàng)建輔助數(shù)組按0結束選擇3以號碼為關鍵字創(chuàng)建哈希表creat按0結束選擇3以號碼為關鍵字創(chuàng)建哈希表creat_num選擇2以姓名為關鍵字創(chuàng)建哈希表creat_name解決沖突解決沖突解決沖突解決沖突線性探測再哈希法再哈希法線性探測線性探測再哈希法再哈希法線性探測按號碼查找,調(diào)用按號碼查找,調(diào)用Search_num函數(shù)按用戶名查找,調(diào)用Search_name函數(shù)查找不成功的平均查找長度查找不成功的平均查找長度選擇0退出選擇0退出圖1具體流程圖[模塊劃分]本程序在菜單選項下包含六個子模塊,如圖2所示圖2模塊劃分[數(shù)據(jù)結構]本設計涉及到的數(shù)據(jù)結構為：哈希表。要求輸入號碼、用戶名、地址三個信息,并要求分別以號碼和用戶名為關鍵字進行查找,所以本問題要用到兩個哈希函數(shù),進行哈希查找。/*哈希表結構體*/typedefstruct{ charname[20];//用戶名 charphone[20];// charadd[30];//地址}Record;RecordInf[M];//全局變量RecordH[M];//全局變量[測試情況]運行程序,顯示主菜單并選擇選項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<stdio.h>#include<string.h>#include<stdlib.h>#defineM10#defineNULLKEY"\0"/*哈希表結構體*/typedefstruct{ charname[20];//用戶名 charphone[20];// charadd[20];//地址}Record;RecordInf[M];//定義輔助數(shù)組為全局變量RecordH[M];//定義哈希表為全局變量/*菜單函數(shù)*/intmenu<>{intm; system<"cls">; system<"color0a">; printf<"\t\t************號碼查詢系統(tǒng)*************\n">; printf<"\n">; printf<"\t\t______________主菜單_______________\n">; printf<"\t\t|1.哈希表的創(chuàng)建|\n">; printf<"\t\t|2.按用戶名散列|\n">; printf<"\t\t|3.按號碼散列|\n">; printf<"\t\t|4.查找操作 |\n">; printf<"\t\t|5.平均查找長度|\n">; printf<"\t\t|0.退出程序|\n">; printf<"\t\t-----------------------------------------\n">; printf<"\n">; printf<"\t\t\t請輸入您的選項<0-5>:\n">;scanf<"%d",&m>;return<m>;} //創(chuàng)建輔助數(shù)組 intCreate<RecordH[M]>{ inti; charsign; for<i=0;i<10;i++>//初始化哈希表 { strcpy< H[i].add,"\0">; strcpy< H[i].phone,"\0">; strcpy< H[i].name,"\0">; } i=0;while<sign!='n'&&sign!='N'> { printf<"請輸入名字\n">; scanf<"%s",Inf[i].name>; printf<"請輸入號碼\n">; scanf<"%s",Inf[i].phone>;printf<"請輸入地址\n">; scanf<"%s",Inf[i].add>; printf<"\t\t\t還需要繼續(xù)輸入嗎?<Y/N>">;scanf<"\t\t\t%c",&sign>;i++; }returni;}//以用戶名為關鍵字的哈希函數(shù)intHash_name<charname[20]>{ inti=0; inta=0; while<name[i]!='\0'> { a=a+name[i]; i++; } a=a%7;//對小于哈希表的最大素數(shù)求余,此處哈希表長為10,對7求余 return<a>;}//再哈希intname_again<charname[20]>{ inti,h; h=<int>name[1]; for<i=2;i<20;i++> h=h+<int>name[i]; h=h%7; returnh;}//以用戶名為關鍵字創(chuàng)建哈希表voidcreat_name<RecordInf[M],intm,RecordH[M]>{ intj,key=0;for<j=0;j<m;j++> { key=Hash_name<Inf[j].name>;//計算哈希地址 while<1>{ if<strcmp<H[key].name,NULLKEY>==0>//判斷該位置是否為空,不為空就把輔助數(shù)組中的元素存到該位置 { strcpy<H[key].name,Inf[j].name>; strcpy<H[key].phone,Inf[j].phone>; strcpy<H[key].add,Inf[j].add>; break; } else key++;//如果為空,采用線性探測法,將元素后移 } } }//再哈希法voidagain_put<RecordInf[M],intm,RecordH[M]>{ intj,key=0;for<j=0;j<m;j++> { key=Hash_name<Inf[j].name>;//計算哈希地址 while<1>{if<strcmp<H[key].name,NULLKEY>==0>//輔助數(shù)組中的元素存到該位置 { strcpy<H[key].name,Inf[j].name>; strcpy<H[key].phone,Inf[j].phone>; strcpy<H[key].add,Inf[j].add>; break; } else key=name_again<Inf[j].name>;//再哈希 }} }//以號碼為關鍵字的哈希函數(shù)intHash_phone<charphone[20]>{ inti=0; intb=0; while<phone[i]!='\0'>//計算號碼中每個字符的ASCII碼值相加 { b=b+phone[i]; i++; } b=b%7;//對小于哈希表的最大素數(shù)求余,此處哈希表長為10,對7求余 return<b>;}//再哈希intphone_again<charphone[20]>{ inti,h; h=<int>phone[1]; for<i=2;i<20;i++> h=h+<int>phone[i]; h=h%7; returnh;}//以號碼為關鍵字創(chuàng)建哈希表voidcreat_phone<RecordInf[M],intm,RecordH[M]>{ intj,key=0; for<j=0;j<m;j++> { key=Hash_phone<Inf[j].phone>;//計算哈希地址 while<1> {if<strcmp<H[key].phone,NULLKEY>==0>//把輔助數(shù)組中的元素存到該位置 { strcpy<H[key].name,Inf[j].name>; strcpy<H[key].phone,Inf[j].phone>; strcpy<H[key].add,Inf[j].add>; break; } else key++;//如果為空,采用線性探測法,將元素后移 } } }//再哈希法voidagain_put2<RecordInf[M],intm,RecordH[M]>{ intj,key=0;for<j=0;j<m;j++> { key=Hash_phone<Inf[j].phone>;//計算哈希地址 while<1>{ if<strcmp<H[key].phone,NULLKEY>==0>//判斷該位置是否為空,不為空就把輔助數(shù)組中的元素存到該位置 { strcpy<H[key].name,Inf[j].name>; strcpy<H[key].phone,Inf[j].phone>; strcpy<H[key].add,Inf[j].add>; break; } else key=phone_again<Inf[j].phone>;//再哈希 } } }//按姓名查找intSearch_name<RecordH[M],charname[20]>{ inth0; inti; inthi; intresult; h0=Hash_name<name>; if<H[h0].name==NULLKEY> { printf<"查找名字不存在!\n">; return<-1>; } else { result=strcmp<H[h0].name,name>; if<result==0> return<h0>; else//用線性探測再散列解決沖突 { for<i=1;i<=M-1;i++> { hi=<h0+i>%M; if<H[hi].name==NULLKEY> return<-1>; else { result=strcmp<H[hi].name,name>; if<result==0> return<hi>; } } return<-1>; } }}//按號碼查找intSearch_phone<RecordH[M],charphone[20]>{ inth0; inti; inthi; intresult; h0=Hash_phone<phone>; if<H[h0].phone==NULLKEY> { printf<"查找號碼不存在!\n">; return<-1>; } else { result=strcmp<H[h0].phone,phone>; if<result==0> return<h0>; else//用線性探測再散列解決沖突 { for<i=1;i<=M-1;i++> { hi=<h0+i>%M; if<H[hi].phone==NULLKEY> return<-1>; else { result=strcmp<H[hi].phone,phone>; if<result==0> return<hi>; } } return<-1>; } }}//以用戶名為關鍵字的哈希表的輸出函數(shù)voidPrint_name<RecordH[M]>{ inti; printf<"\t哈希地址\t用戶名\t\t號碼\t\t地址\n">; for<i=0;i<10;i++> { if<strcmp<H[i].name,"\0">!=0> { printf<"\t%d\t\t%s\t\t%s\t\t%s\n",i,H[i].name,H[i].phone,H[i].add>; } }}//以號碼為關鍵字的哈希表的輸出函數(shù)voidPrint_phone<RecordH[M]>{ inti; printf<"\t哈希地址\t用戶名\t\t號碼\t\t地址\n">; for<i=0;i<10;i++> { if<strcmp<H[i].phone,"\0">!=0> { printf<"\t%d\t\t%s\t\t%s\t\t%s\n",i,H[i].name,H[i].phone,H[i].add>; } }}//查找不成功的平均查找長度voidunsucc_length<intm>{ charphone[20]; inti,j; intcount; intasl=0; floatunasl; Hash_phone<phone>; for<i=0;i<7;i++> { j=i; count=1; while<strcmp<H[j].name,NULLKEY>!=0> { count++; j=<j+1>%7; } asl=asl+count; } unasl=<float>asl/7; printf<"查找不成功的平均查找長度為:%5.2f\n",unasl>;}voidmain<>//主函數(shù){ charname[20],phone[20]; intm; intn,p; intfind; intw,k;while<1> { switch<menu<>> { case1: m=Create<H>;//創(chuàng)建輔助數(shù)組 break; case2: printf<"\t\t\t***********************\n">; printf<"\t\t\t****1.線性再散列****\n">; printf<"\t\t\t****2.再哈希法散列****\n">; printf<"\t\t\t****3.退出本菜單****\n">; printf<"\t\t\t***********************\n">; printf<"輸入散列選項<0-2>:\n">; scanf<"%d",&p>; switch<p> { case1:creat_name<Inf,m,H>; Print_name<H>; break; case2: again_put<Inf,m,H>; Print_name<H>; break; } break; case3: printf<"\t\t\t***********************\n">; printf<"\t\t\t****1.線性再散列****\n">; printf<"\t\t\t****2.再哈希法散列****\n">; printf<"\t\t\t****3.退出本菜單****\n">; printf<"\t\t\t***********************\n">; printf<"輸入散列選項<0-2>:\n">; scanf<"%d",&n>; switch<n> { case1: creat_phone<Inf,m,H>; Print_phone<H>; break; case2: again_put<Inf,m,H>; Print_phone<H>; break; } break; case4: printf<"\t\t\t***********************\n">; printf<"\t\t\t****1.按用戶名查詢****\n">; printf<"\t\t\t****2.按查詢****\n">; printf<"\t\t\t****3.退出本菜單****\n">; printf<"\t\t\t***********************\n">; printf<"輸入查找條件<0-2>:\n">; scanf<"%d",&find>; switch<find> { case1: printf<"\n請輸入要查找的名字：\n">; scanf<"%s",name>;k=Search_name<H,name>; //k=Hash_again<H,name>; if<k!=-1> { printf<"查找該人的信息是:\n">; printf<"查找的用戶名是:%s\n",H[k].name>; printf<"