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

1、課 程 設 計 課程名稱 數(shù)據(jù)結構 題目名稱 哈希表設計 學生學院 計算機學院 專業(yè)班級 10級網(wǎng)絡工程1班 學 號 3210006470 學生姓名 指導教師 2012 年 6 月 17 日一問題描述針對某個集體（比如你所在的班級）中的“人名”設計一個哈希表，使得平均查找長度不超過R，完成相應的建表和查表程序。二.基本要求假設人名為中國人姓名的漢語拼音形式。待填入哈希表的人名共有30個，取平均查找長度的上限為2。哈希函數(shù)用除留余數(shù)法構造，用偽隨機探測再散列發(fā)處理沖突。三. 需求分析 針對某個集體中的人名設計一個哈希表，使得平均查找長度不超過R，完成相應的建立和查表程序。人名為漢語拼音形式，最長

2、不超過19個字符(如：莊雙雙 zhuangshuangshuang)。 假設待填入哈希表的人名有30個，平均查找長度的上限為2。哈希表用除留余數(shù)法構造，用偽隨機探測在散列法處理沖突。 在輸入人名過程中能自動識別非法輸入，并給與非法輸入的反饋信息要求重新輸入。查找成功時，顯示姓名及關鍵字，并計算和輸出查找成功的平均查找長度。四程序設計1 .存儲結構設計typedef struct char *py; int k; NAME;NAME NameListHASH_LEN; typedef struct char *py; int k; int si; HASH; 2 .源代碼#include<

3、stdio.h>#include<iostream>#include<conio.h>using namespace std;#define HASH_LEN 50 #define M 47 int NAME_NO=30; HASH HashListHASH_LEN; void InitNameList() char *f; int r,s0,i; NameList0.py="caizenghua" NameList1.py="chenjiachuang" NameList2.py="chenquanzhong&q

4、uot; NameList3.py="chenxuebin" NameList4.py="chenzhongchao" NameList5.py="chenzifan" NameList6.py="dengchenhua" NameList7.py="duweihao" NameList8.py="fangjiatai" NameList9.py="heguoliang" NameList10.py="hongzexin" NameLi

5、st11.py="huangjinbiao" NameList12.py="huangliquan" NameList13.py="huangmiaojie" NameList14.py="huangrong hao" NameList15.py="huangyonghao" NameList16.py="liguangxi" NameList17.py="lilangzheng" NameList18.py="liangcailin"

6、 NameList19.py="linjiewen" NameList20.py="liufurupeng" NameList21.py="liuliang" NameList22.py="luohaoheng" NameList23.py="luowenchao" NameList24.py="sunwenhong" NameList25.py="tanzeming" NameList26.py="wangjian" NameList

7、27.py="wangkaibin" NameList28.py="wangyixin" NameList29.py="wenduke" for (i=0;i<NAME_NO;i+) s0=0; f=NameListi.py; for (r=0;*(f+r)!='0'r+) s0=*(f+r)+s0; NameListi.k=s0; void CreateHashList() int i; for (i=0; i<NAME_NO;i+) HashListi.py="" HashListi

8、.k=0; HashListi.si=0; for (i=0;i<HASH_LEN;i+) int sum=0; int adr=(NameListi.k)%M; int d=adr; if(HashListadr.si=0) HashListadr.k=NameListi.k; HashListadr.py=NameListi.py; HashListadr.si=1; else do d=(d+NameListi.k%10+1)%M; sum=sum+1; while (HashListd.k!=0); HashListd.k=NameListi.k; HashListd.py=Na

9、meListi.py; HashListd.si=sum+1; int FindList() char name20=0; int s0=0,r,sum=1,adr,d; printf("n請輸入人物名稱:"); scanf("%s",name); for (r=0;r<20;r+) s0+=namer; adr=s0%M; d=adr; if(HashListadr.k=s0) printf("n名稱:%s 關鍵字:%d 查找長度為: 1",HashListd.py,s0); cout<<endl; return

10、0; else if (HashListadr.k=0) printf("無此記錄!"); cout<<endl; return 1; else int g=0; do d=(d+s0%10+1)%M; sum=sum+1; if (HashListd.k=0) printf("無此記錄! "); cout<<endl; g=1; return 1; if (HashListd.k=s0) printf("n名稱:%s 關鍵字:%d 查找長度為:%d",HashListd.py,s0,sum); cout<

11、;<endl; g=1; return 0; while(g=0); void Display() int i; float average=0; for(i=0; i<NAME_NO; i+) if(HashListi.k%M=0) HashListi.py="" printf("nn地址t關鍵字tt搜索長度tH(key)t 名稱n"); for(i=0; i<NAME_NO; i+) printf("%d ",i); printf("t%d ",HashListi.k); printf(&qu

12、ot;tt%d ",HashListi.si); printf("tt%d ",HashListi.k%M); printf("t %s ",HashListi.py); printf("n"); for (i=0;i<HASH_LEN;i+) average+=HashListi.si; average/=NAME_NO; printf("nn平均查找長度：ASL(%d)=%f nn",NAME_NO,average); void DeleteList() char name20=0; int s

13、0=0,r,sum=1,adr,d; printf("n請輸入人名拼音:"); scanf("%s",name); for (r=0;r<20;r+) s0+=namer; adr=s0%M; d=adr; if(HashListadr.k=s0) printf("n名稱:%s 關鍵字:%d 查找長度為: 1",HashListd.py,s0); cout<<endl; cout<<"刪除成功！"<<endl; s0=0; HashListd.py=""

14、 HashListd.k=0; HashListd.si=0; else if (HashListadr.k=0) printf("無此記錄!無法執(zhí)行刪除操作!"); else int g=0; do d=(d+s0%10+1)%M; sum=sum+1; if (HashListd.k=0) printf("無此記錄!無法執(zhí)行刪除操作!"); g=1; if (HashListd.k=s0) printf("n名稱:%s 關鍵字:%d 查找長度為:%d",HashListd.py,s0,sum); cout<<endl;

15、 cout<<"已刪除成功！"<<endl; s0=0; HashListd.py="" HashListd.k=0; HashListd.si=0; g=1; while(g=0); void EnterList() char st20; char *xin; xin=st; int s0=0,r,sum=1,adr,d,h; printf("n請輸入人名的拼音:"); cin>>xin; for (r=0;*(xin+r)!='0'r+) s0=(int)(*(xin+r)+s0

16、; adr=s0%M; d=adr; if(HashListadr.k=s0) printf("n名稱:%s 關鍵字:%d 查找長度為: 1",HashListd.py,s0); cout<<endl; cout<<"已存在于表中，無需插入！"<<endl; else if (HashListd.k=0) printf("插入成功！"); HashListd.py=xin; HashListd.k=s0; HashListd.si=1; h=1; cout<<endl; else int

17、 g=0,h=0; do d=(d+s0%10+1)%M; sum=sum+1; if (HashListd.k=0) printf("插入成功！"); HashListd.py=xin; HashListd.k=s0; HashListd.si=sum; h=1; cout<<endl; g=1; if (HashListd.k=s0) printf("n名稱:%s 關鍵字:%d 查找長度為:%d",HashListd.py,s0,sum); cout<<endl; cout<<"已存在于表中，無需插入！&

18、quot;<<endl; g=1; while(g=0); if(h=0) return; else NAME_NO+; NameListNAME_NO-1.py=xin; int sum=0; int adr=(NameListNAME_NO-1.k)%M; int d=adr; if(HashListadr.si=0) HashListadr.k=NameListNAME_NO-1.k; HashListadr.py=NameListNAME_NO-1.py; HashListadr.si=1; else do d=(d+NameListNAME_NO-1.k%10+1)%M;

19、 sum=sum+1; while (HashListd.k!=0); HashListd.k=NameListNAME_NO-1.k; HashListd.py=NameListNAME_NO-1.py; HashListd.si=sum+1; void main() char ch1; printf("n 哈希表n"); printf(" *-*n"); printf(" | A. 顯示哈希表 |n"); printf(" | B. 查找 |n"); printf(" | C. 刪除 |n"

20、); printf(" | D. 插入 |n"); printf(" | E. 退出 |n"); printf(" *-*n"); InitNameList(); CreateHashList (); while(1) printf("n請輸入執(zhí)行命令:"); fflush(stdin); ch1=getchar(); if (ch1='A'|ch1='a') Display(); else if (ch1='B'|ch1='b') FindList(); else if (ch1='C'|ch1='c') DeleteList(); else if (ch1='D'|ch1='d') EnterLi