《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計(jì)說明書hash表的建立和查找

1、課程設(shè)計(jì)任務(wù)書學(xué)生姓名： xxx 專業(yè)班級(jí)： 計(jì)算機(jī)0502 指導(dǎo)教師： xxx 工作單位：計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 題 目: hash表的建立和查找初始條件：理論：學(xué)習(xí)了數(shù)據(jù)結(jié)構(gòu)課程，掌握了基本的數(shù)據(jù)結(jié)構(gòu)和常用的算法；實(shí)踐：計(jì)算機(jī)技術(shù)系實(shí)驗(yàn)室提供計(jì)算機(jī)及軟件開發(fā)環(huán)境。要求完成的主要任務(wù): （包括課程設(shè)計(jì)工作量及其技術(shù)要求，以及說明書撰寫等具體要求）1、系統(tǒng)應(yīng)具備的功能：（1）設(shè)計(jì)哈希函數(shù)和哈希表；（2）設(shè)計(jì)解決沖突的方法；（3）輸入一組數(shù)據(jù)建立哈希表，并實(shí)現(xiàn)在哈希表中進(jìn)行查找。2、數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)；3、主要算法設(shè)計(jì)；4、編程及上機(jī)實(shí)現(xiàn)；5、撰寫課程設(shè)計(jì)報(bào)告，包括：（1）設(shè)計(jì)題目；（2）摘要和關(guān)鍵字；

2、（3）正文，包括引言、需求分析、數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)、算法設(shè)計(jì)、程序?qū)崿F(xiàn)及測(cè)試、結(jié)果分析、設(shè)計(jì)體會(huì)等；（4）結(jié)束語(yǔ)；（5）參考文獻(xiàn)。時(shí)間安排： 2007年7月2日7日 （第18周）7月2日 查閱資料7月3日 系統(tǒng)設(shè)計(jì)，數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)，算法設(shè)計(jì)7月4日-5日 編程并上機(jī)調(diào)試7月6日 撰寫報(bào)告7月7日 驗(yàn)收程序，提交設(shè)計(jì)報(bào)告書。指導(dǎo)教師簽名： 2007年7月2日系主任（或責(zé)任教師）簽名： 2007年7月2日hash表的建立和查找摘要: 本人設(shè)計(jì)了一個(gè)hash表的建立和查找系統(tǒng)，其主要功能是，用戶可以手工輸入hash表元素個(gè)數(shù)和各個(gè)元素的數(shù)據(jù)內(nèi)容，系統(tǒng)便相應(yīng)地建立一個(gè)hash表，（輸入錯(cuò)誤時(shí)，系統(tǒng)會(huì)顯示輸入錯(cuò)

3、誤，并提示重新輸入）；可對(duì)已建立的hash表進(jìn)行多次查找，系統(tǒng)打印查找到的信息，用戶可以按提示信息退出系統(tǒng)。hash表采用結(jié)構(gòu)體數(shù)組進(jìn)行存儲(chǔ)，hash函數(shù)由除留余數(shù)法建立，沖突的解決采用線性探測(cè)。關(guān)鍵字: hash表，結(jié)構(gòu)體數(shù)組，除留余數(shù)法，線性探測(cè)0.引言隨著時(shí)代的進(jìn)步，科技的發(fā)展，信息時(shí)代已經(jīng)來臨，在這樣的時(shí)代背景之下，人們迫切需要對(duì)信息進(jìn)行存儲(chǔ)和查找，而數(shù)據(jù)結(jié)構(gòu)成為了信息技術(shù)中極為重要的一門學(xué)科，發(fā)揮著關(guān)鍵作用。信息資料之多之雜之廣，使如何存儲(chǔ)和高效查找信息成為了一個(gè)很嚴(yán)肅的問題。本次課程設(shè)計(jì)中，我設(shè)計(jì)了一個(gè)小程序?qū)τ脩糨斎氲臄?shù)據(jù)利用hash表進(jìn)行存儲(chǔ)。存儲(chǔ)完成后，用戶可利用hash表查

4、找數(shù)據(jù)，速度十分快，可多次查找，也可按提示信息退出。1.需求分析本次課程設(shè)計(jì)需要實(shí)現(xiàn)hash表的建立和查找，具體內(nèi)容如下：1.1 hash 表的建立建立hash函數(shù)，從而根據(jù)用戶輸入的數(shù)據(jù)元素個(gè)數(shù)和各元素的值建立hash 表，即數(shù)據(jù)的添加和存儲(chǔ)。如果輸入的元素個(gè)數(shù)超出規(guī)定范圍，則打印出錯(cuò)信息，并提示重新輸入信息。1.2 hash 表的查找hash表建立好之后，用戶可以輸入想要查找的值，屏幕顯示相應(yīng)信息。如果存在此值，屏幕顯示該值信息；如果不存在，則顯示該值不存在；如果想退出系統(tǒng)，則按提示輸入命令。2.數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)2.1定義結(jié)構(gòu)體typedef structint key; /定義關(guān)鍵字int

5、cn; /定義查找次數(shù)cnhashtable; /定義哈希表類型2.2定義結(jié)構(gòu)體數(shù)組hashtable hthm; /定義哈希表空間3.算法設(shè)計(jì)3.1 hash函數(shù)該函數(shù)利用除留余數(shù)法實(shí)現(xiàn)“hash 函數(shù)”#define m 19 /不大于表長(zhǎng)的最大質(zhì)數(shù)status h(keytype key)/哈希函數(shù)return(key%m); /除留余數(shù)法/h3.2信息查找函數(shù) 這個(gè)函數(shù)能查找信息，它既能用于查找所輸入信息，又能在建立hash的時(shí)候被建立hash表的函數(shù)調(diào)用。用戶可以輸入想要查找的值，屏幕顯示相應(yīng)信息。如果存在此值，屏幕顯示該值信息；如果不存在，則顯示該值不存在；如果想退出系統(tǒng)，則按提示

6、輸入命令。status hashsearch(hashtable ht,keytype key)/哈希表查找函數(shù)int d,i;i=0;d=h(key); /求哈希地址=0; /記錄元素被查找的次數(shù)while(htd.key!=key)&(htd.key!=free)&(i=hm) /hash表已滿，插入失敗，返回unsuccessprintf(the hashtable is full!n);return(unsuccess);return(d); /若hd的關(guān)鍵字等于key說明查找成功/hashsearch3.3數(shù)據(jù)輸入函數(shù)此函數(shù)能夠?qū)τ脩糨斎氲臄?shù)據(jù)進(jìn)行處理，即將輸入數(shù)據(jù)插入h

7、ash表中。它調(diào)用了hash函數(shù)。如果插入成功，顯示插入成功信息；如果插入不成功，則顯示插入不成功信息。status hashinsert(hashtable ht,keytype key)/哈希插入函數(shù)，插入成功返回success，插入不成功返回unsuccess/查找不成功的時(shí)候，將給定關(guān)鍵字key插入哈希表中int d;d=hashsearch(ht,key);if(htd.key=free) /插入成功htd.key=key;printf(insert success!n);return(success);else /插入不成功printf(uneuccess!n);return(un

8、success); /hashinseart3.4建立hash表函數(shù)此函數(shù)能夠根據(jù)用戶輸入的數(shù)據(jù)建立hash表，并將所有數(shù)據(jù)存入表中。如果輸入數(shù)據(jù)不和理（即輸入的數(shù)據(jù)長(zhǎng)度大于或等于表長(zhǎng)，或小于0），屏幕會(huì)提示錯(cuò)誤信息，并提示用戶重新輸入正確的數(shù)據(jù)值；如果輸入數(shù)據(jù)合理（即輸入的表長(zhǎng)大于等于0，小于表長(zhǎng)），用戶就可以按提示信息輸入表元素，哈希表就會(huì)被成功建立。hash表的建立也利用了除留余數(shù)法，所以該函數(shù)調(diào)用了哈希表插入運(yùn)算函數(shù)。void hashcreat(hashtable ht)/根據(jù)用戶輸入的信息建立一個(gè)哈希表int n;int i;int key1;printf(input the nu

9、mber of the elements(less than the length of the list %d and no less than 0):n,hm); /提示輸入規(guī)定范圍內(nèi)的長(zhǎng)度scanf(%d,&n); /輸入表長(zhǎng)if(n=20) /輸入不合理的表長(zhǎng)度 printf(please input a length less than 20:n);/表長(zhǎng)大于等于20else if(n0) printf(please input a length no less than 0:n);/表長(zhǎng)小于0while(n=20) /輸入表長(zhǎng)度合理scanf(%d,&n);if(n=20) pri

10、ntf(please input a length less than 20:n); /表長(zhǎng)大于等于20 else if(n0) printf(please input a length no less than 0:n); /表長(zhǎng)小于0 for(i=0;in;i+) /依次插入用戶輸入的各個(gè)元素的數(shù)據(jù)printf(input the key word:n);scanf(%d,&key1); /輸入元素?cái)?shù)據(jù)hashinsert(ht,key1); /調(diào)用哈希表插入運(yùn)算/hashcreat3.5主要界面的設(shè)計(jì)void jiemian()/主界面設(shè)計(jì)hashtable ht0hm; /分配hash

11、表的空間int key0=0; /初始化為0float key1=0; /初始化為0 int i;printf(build the hash list:n); /提示建立信息hashcreat(ht0); /建立hash表printf(now you can search in the hash list:n); /提示用戶查找printf(input the key word of the element required to searchn(if you want to exit ,input a figure bigger than 0 and small than 1.):n);sc

12、anf(%f,&key1); /輸入想要查找的數(shù)據(jù)key0=(int)key1;while(key1-(float)key0)=0)/多次查找輸入的數(shù)據(jù)，系統(tǒng)顯示相應(yīng)結(jié)果/按提示退出系統(tǒng) i=hashsearch(ht0,key0); if(ht0i.key=key0) /存在該元素時(shí) printf(%d exists in the list.n ,key0); /打印存在信息 printf(its pose is num.%dnn,i); /打印元素位置 else printf(there is no %d in the list.nn,key0);printf(input the key

13、word of the element required to searchn(if you want to exit ,input a figure bigger than 0 and small than 1.):n); /提示用戶退出 scanf(%f,&key1); /用戶繼續(xù)輸入數(shù)據(jù) key0=(int)key1; /key0是key1的整數(shù)部分/jiemian3.6其他有關(guān)技術(shù)討論我這個(gè)程序選用結(jié)構(gòu)體數(shù)組為存儲(chǔ)結(jié)構(gòu)，實(shí)現(xiàn)了hash表的數(shù)據(jù)存儲(chǔ)。hash表查找給予一種盡可能不通過比較操作而直接得到記錄的存儲(chǔ)位置的想法而提出的一種特殊查找技術(shù)。它的基本思想是通過記錄中關(guān)鍵字的值key為

14、自變量，通過某一種確定的函數(shù)h，計(jì)算出函數(shù)值h（key）作為存儲(chǔ)地址，將相應(yīng)的關(guān)鍵字的記錄存儲(chǔ)到對(duì)應(yīng)的位置上。而在查找是仍需要用這個(gè)確定的函數(shù)h進(jìn)行計(jì)算，獲得所要查找的關(guān)鍵字所在的記錄的存儲(chǔ)位置。除留余數(shù)法（division method）是用關(guān)鍵字key除以某個(gè)正整數(shù)m，所得余數(shù)作為哈希地址的方法。對(duì)應(yīng)hash函數(shù)h（key）為：h（key）=key % m，一般情況下m 的取值為不大于表長(zhǎng)的質(zhì)數(shù)。開放定址發(fā)解決沖突，形成下一個(gè)地址的形式是： hi=（h（key）+di）%m i=1，2，k（k=m）其中，h（key）為哈希函數(shù)，m為某個(gè)正整數(shù)，di為增量序列。線形探測(cè)再散列，是將開放定地址

15、發(fā)中的增量di設(shè)定為一系列從1開始一直到表長(zhǎng)減1的整數(shù)序列：1，2，3，,m-1(m為表長(zhǎng))。本系統(tǒng)對(duì)用戶在操作時(shí)可能進(jìn)行的錯(cuò)誤和違規(guī)操作，給出了基本的提示信息和解決方案，以便用戶在非法操作后得到意想不到的結(jié)果，即在根據(jù)用戶輸入的數(shù)據(jù)建立hash表并將所有數(shù)據(jù)存入表中時(shí)。如果輸入數(shù)據(jù)不和理（即輸入的數(shù)據(jù)長(zhǎng)度大于或等于表長(zhǎng)，或小于0），屏幕會(huì)提示錯(cuò)誤信息，并提示用戶重新輸入正確的數(shù)據(jù)值；如果輸入數(shù)據(jù)合理（即輸入的表長(zhǎng)大于等于0，小于表長(zhǎng)），用戶就可以按提示信息輸入表元素，哈希表就會(huì)被成功建立。本系統(tǒng)對(duì)用戶在操作時(shí)可能進(jìn)行的錯(cuò)誤和違規(guī)操作，給出了基本的提示信息和解決方案，以便用戶在非法操作后得到意

16、想不到的結(jié)果。4.程序的實(shí)現(xiàn)4.1所有的函數(shù)聲明int h(int key)int hashsearch(hashtable ht,int key)int hashinsert(hashtable ht,int key)void hashcreat(hashtable ht)4.2主要方法的代碼實(shí)現(xiàn)4.2.1哈希表查找函數(shù)int hashsearch(hashtable ht,int key)/*哈希表查找函數(shù)*/int d,i;i=0;d=h(key); /*求哈希地址*/=0;while(htd.key!=key)&(htd.key!=free)&(i=hm)printf(th

17、e hashtable is full!n);return(unsuccess);return(d); /*若hd的關(guān)鍵字等于key說明查找成功*/*hashsearch*/4.2.2哈希插入函數(shù)int hashinsert(hashtable ht,int key)/*哈希插入函數(shù)*/*查找不成功的時(shí)候，將給定關(guān)鍵字key插入哈希表中*/int d;d=hashsearch(ht,key);if(htd.key=free)htd.key=key;printf(insert success!n);return(success); /*插入成功*/elseprintf(uneuccess!n);

18、return(unsuccess); /*插入不成功*/*hashinseart*/4.2.3哈希表建立函數(shù)void hashcreat(hashtable ht)/*建立哈希表的函數(shù)*/int n;int i;int key1;printf(input the number of the elements(less than the length of the list %d and no less than 0):n,hm);scanf(%d,&n);if(n=20) /*輸入不合理的表長(zhǎng)度*/ printf(please input a length less than 20:n);el

19、se if(n0) printf(please input a length no less than 0:n);while(n=20) /*輸入表長(zhǎng)度合理*/scanf(%d,&n);if(n=20) printf(please input a length less than 20:n); else if(n0) printf(please input a length no less than 0:n); for(i=0;in;i+)printf(input the key word:n);scanf(%d,&key1);hashinsert(ht,key1); /*調(diào)用哈希表插入運(yùn)算*

20、/*hashcreat*/4.3程序運(yùn)行結(jié)果4.3.1運(yùn)行界面4.3.2輸入出錯(cuò)提示界面4.3.3輸入元素超過hash表表長(zhǎng)屆面4.3.4輸入正確建立hash表提示界面4.3.5根據(jù)提示建立hash表界面4.3.6輸入查找數(shù)據(jù)得到顯示數(shù)據(jù)界面4.3.7表中無輸入數(shù)據(jù)時(shí)的界面4.3.8用戶可按提示信息退出系統(tǒng)界面4.4結(jié)果分析用戶手工輸入數(shù)據(jù)并對(duì)輸入數(shù)據(jù)建立hash表，具有提示錯(cuò)誤功能；另外就是對(duì)已建立的hash表進(jìn)行查找，具有多次查找功能，并打印信息，可以按提示信息退出系統(tǒng)。本系統(tǒng)采用了hash表存儲(chǔ),查找速度極其快,查找的時(shí)間復(fù)雜度為o(1)。本系統(tǒng)仍然存在一些不足之處值得改進(jìn)，例如：在建立

21、hash表的過程中，如果用戶想退出系統(tǒng)，也不得不在建立好hash表之后，才能實(shí)現(xiàn)。5.設(shè)計(jì)體會(huì)通過這次做課程設(shè)計(jì)，使我對(duì)數(shù)據(jù)結(jié)構(gòu)這門課的認(rèn)識(shí)更進(jìn)一步，這門課確實(shí)是學(xué)好計(jì)算機(jī)程序設(shè)計(jì)的基礎(chǔ)。與此同時(shí)，自己對(duì)程序設(shè)計(jì)中應(yīng)該注意的一些問題也有了自己的一些想法。首先，一個(gè)程序要達(dá)到正確性，可讀性，健壯性，高效率和低存儲(chǔ)量的要求，這樣用戶在使用程序的時(shí)候才會(huì)更加滿意，程序才能得到更多的關(guān)注。其次，要養(yǎng)成良好的編程習(xí)慣，在做一個(gè)程序之前，要對(duì)該程序的存儲(chǔ)結(jié)構(gòu)，抽象數(shù)據(jù)類型和應(yīng)該具備的功能以及各模塊之間的調(diào)用關(guān)系有一個(gè)總體的把握，畫出必要的算法流程圖或?qū)懗霰匾膫未a來表示各模塊應(yīng)該具備的功能。再次，在編寫程序的過程中應(yīng)該對(duì)一些難于理解的地方加上必要的注釋，這樣會(huì)使在之后的調(diào)試與維護(hù)階段更加容易，在定義功能函數(shù)與變量時(shí)應(yīng)該盡量采取有表征意義的名稱，這樣也可達(dá)到見名知意的效果。最后，在程序的調(diào)試階段，應(yīng)該針對(duì)程序中用戶可能進(jìn)行的錯(cuò)誤操作給出解決的方法，要盡量選出幾組具有毀滅性的數(shù)據(jù)