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

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

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