課程設(shè)計(jì)--哈希表查找算法的實(shí)現(xiàn)

1、<p><b>　　課 程 設(shè) 計(jì)</b></p><p><b>　　課程設(shè)計(jì)任務(wù)書</b></p><p>　　題目: 哈希表查找算法的實(shí)現(xiàn)</p><p><b>　　初始條件：</b></p><p>　　理論：完成了《匯編語言程序設(shè)計(jì)》課程，對(duì)微機(jī)系統(tǒng)結(jié)構(gòu)

2、和80系列指令系統(tǒng)有了較深入的理解，已掌握了匯編語言程序設(shè)計(jì)的基本方法和技巧。</p><p>　　實(shí)踐：完成了《匯編語言程序設(shè)計(jì)》的4個(gè)實(shí)驗(yàn)，熟悉了匯編語言程序的設(shè)計(jì)環(huán)境并掌握了匯編語言程序的調(diào)試方法。</p><p>　　要求完成的主要任務(wù): （包括課程設(shè)計(jì)工作量及其技術(shù)要求，以及說明書撰寫等具體要求）</p><p>　　進(jìn)一步理解和掌握較復(fù)雜程序的設(shè)計(jì)方法，

3、掌握子程序結(jié)構(gòu)的設(shè)計(jì)和友好用戶界面的設(shè)計(jì)。具體的設(shè)計(jì)任務(wù)及要求：</p><p>　　輸入一些整數(shù)，采用哈希表結(jié)構(gòu)存儲(chǔ)；</p><p>　　實(shí)現(xiàn)對(duì)哈希表的查找；</p><p>　　程序采用子程序結(jié)構(gòu)，結(jié)構(gòu)清晰；</p><p>　　友好清晰的用戶界面，能識(shí)別輸入錯(cuò)誤并控制錯(cuò)誤的修改。</p><p>　　在完成設(shè)計(jì)

4、任務(wù)后，按要求撰寫課程設(shè)計(jì)說明書；對(duì)課程設(shè)計(jì)說明書的具體要求請(qǐng)見課程設(shè)計(jì)指導(dǎo)書。</p><p><b>　　閱讀資料：</b></p><p>　　1）《IBM—PC匯編語言程序設(shè)計(jì)實(shí)驗(yàn)教程》實(shí)驗(yàn)2.4</p><p>　　2）《IBM—PC匯編語言程序設(shè)計(jì)（第2版）》例6.11</p><p><b>　　

5、時(shí)間安排：</b></p><p>　　設(shè)計(jì)安排一周：周1、周2：完成系統(tǒng)分析及設(shè)計(jì)。</p><p>　　周3、周4：完成程序調(diào)試，和驗(yàn)收。</p><p>　　周5：撰寫課程設(shè)計(jì)報(bào)告。</p><p>　　指導(dǎo)教師簽名： 年 月 日</p><p>

6、;　　系主任（或責(zé)任教師）簽名： 年 月 日</p><p><b>　　目 錄</b></p><p>　　⒈設(shè)計(jì)目的與任務(wù).........................4</p><p>　?、?問題描述...................................4</p>

7、<p>　?、?設(shè)計(jì)目的....................................4</p><p>　　⒈3測試用例....................................5</p><p>　?、苍O(shè)計(jì)分析................................5 </p><p>　?、? 存儲(chǔ)結(jié)構(gòu).......

8、.............................5</p><p>　　⒉2主要算法.....................................5</p><p>　?、吃O(shè)計(jì)步驟................................6</p><p>　　⒊1概要設(shè)計(jì).................................

9、...6</p><p>　?、?代碼設(shè)計(jì).....................................7</p><p>　?、凑{(diào)試分析和測試結(jié)果......................15</p><p>　　⒋1 編碼分析...................................15</p><p>　?、?

10、 調(diào)試運(yùn)行....................................16</p><p>　?、?調(diào)試結(jié)果.....................................16</p><p>　　⒌心得體會(huì)................................17</p><p>　?、秴⒖嘉墨I(xiàn)...................

11、.............18</p><p><b>　　⒈設(shè)計(jì)目的與任務(wù)</b></p><p><b>　?、?問題描述</b></p><p>　?、雹?題目：哈希表查找算法的實(shí)現(xiàn) </p><p><b>　?、雹?任務(wù)與要求：</b></p><

12、;p>　?、泡斎胍恍┱麛?shù)，采用哈希表結(jié)構(gòu)存儲(chǔ)；</p><p>　?、茖?shí)現(xiàn)對(duì)哈希表的查找；</p><p>　?、浅绦虿捎米映绦蚪Y(jié)構(gòu)，結(jié)構(gòu)清晰；</p><p>　　⑷友好清晰的用戶界面，能識(shí)別輸入錯(cuò)誤并控制錯(cuò)誤的修改。</p><p><b>　　⒈2設(shè)計(jì)目的</b></p><p>　　

13、匯編語言是計(jì)算機(jī)專業(yè)的專業(yè)基礎(chǔ)課，也是電子、通信等相 關(guān)專業(yè)的計(jì)算機(jī)課程。通過課程設(shè)計(jì)，一反面使我們掌握匯編語言的編程方法、思路和技巧，并對(duì)計(jì)算機(jī)的底層編程有一定認(rèn)識(shí)；另一方面，也能讓我們理解計(jì)算機(jī)底層運(yùn)行程序的機(jī)制，了解計(jì)算機(jī)的工作原理，為以后一些課程的學(xué)習(xí)（如操作系統(tǒng)、微機(jī)原理等）打下基礎(chǔ)。</p><p>　　比如強(qiáng)調(diào)CS和IP寄存器的作用，比如在介紹子程序設(shè)計(jì)時(shí)，除了讓學(xué)生能夠使用CALL指令和RET指

14、令編寫子程序結(jié)構(gòu)的程序，還要通過CALL指令和RET指令內(nèi)部執(zhí)行的操作，讓學(xué)生明白計(jì)算機(jī)內(nèi)部如何能夠做到調(diào)用子程序，又如何能夠從子程序返回主程序，子程序多層嵌套時(shí)為什么子程序返回不會(huì)亂套等問題。實(shí)際上，完成這次的課程設(shè)計(jì)，我們也會(huì)對(duì)以前學(xué)過的C++語言的一些概念有更深刻的理解，如指針，也會(huì)明白數(shù)組等數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)內(nèi)部是如何組織和表示的。</p><p><b>　?、?測試用例</b>&l

15、t;/p><p>　　輸入的一系列整數(shù)為：</p><p>　　?, 12,15,68,29,51,13,24,81,75,26,19,18,?,?,?</p><p><b>　?、苍O(shè)計(jì)分析</b></p><p><b>　　⒉1存儲(chǔ)結(jié)構(gòu)</b></p><p>　　哈希表是

16、表示集合和字典的另一種有效方法，它提供了一種完全不同的存儲(chǔ)和搜索方式，通過將關(guān)鍵碼映射到表中某個(gè)位置上來存儲(chǔ)元素，然后根據(jù)關(guān)鍵碼用同樣的方式直接訪問。</p><p><b>　?、?主要算法</b></p><p><b>　　散列方法</b></p><p>　　理想的搜索方法是可以不經(jīng)過任何比較，一次直接從字典中得到

17、要搜索的元素。如果在元素的存儲(chǔ)位置與它的關(guān)鍵碼之間建立一個(gè)確定的函數(shù)對(duì)應(yīng)關(guān)系Hash（），使得每個(gè)關(guān)鍵碼與結(jié)構(gòu)中的一個(gè)唯一的位置相對(duì)應(yīng)：Address=Hash（key）</p><p>　　在插入時(shí)，依此函數(shù)計(jì)算存儲(chǔ)位置并按此位置存放。在搜索時(shí)，對(duì)元素的關(guān)鍵碼進(jìn)行同樣的函數(shù)計(jì)算，把求得的函數(shù)當(dāng)做元素的存儲(chǔ)位置，在結(jié)構(gòu)中按此位置取元素比較，若關(guān)鍵碼相等，則搜索成功。這種方法就叫做散列方法。在散列方法中使用的轉(zhuǎn)換函

18、數(shù)叫做散列函數(shù)。</p><p><b>　　散列函數(shù)</b></p><p>　　在構(gòu)造散列函數(shù)時(shí)有幾點(diǎn)需要加以注意：其一是散列函數(shù)的定義域必須包括需要存儲(chǔ)的全部關(guān)鍵碼，而如果散列表允許有m個(gè)地址時(shí)，其值域必須在0到m-1之間。其二散列函數(shù)計(jì)算出來的地址應(yīng)能均勻分布在整個(gè)地址空間中：若key是從關(guān)鍵碼集合中隨機(jī)抽取的一個(gè)關(guān)鍵碼，散列函數(shù)應(yīng)能以同等概率取在0到m-1中

19、的每一個(gè)值。其三是散列函數(shù)應(yīng)是簡單的，能在短時(shí)間內(nèi)計(jì)算出來的。</p><p>　　本次課程設(shè)計(jì)采用的散列函數(shù)是除留取余法。</p><p><b>　　除留取余法</b></p><p>　　設(shè)哈希表中允許的地址數(shù)為m,取一個(gè)不大于m但最接近于或等于m的質(zhì)數(shù)p作為除數(shù)，利用以下公式把關(guān)鍵碼轉(zhuǎn)換成散列地址。散列函數(shù)為： 　</p>

20、<p>　　Hash(key)=key MOD p (p<=m)</p><p><b>　?、吃O(shè)計(jì)步驟</b></p><p><b>　　⒊1概要設(shè)計(jì)</b></p><p><b>　　數(shù)據(jù)段</b></p><p>　　數(shù)據(jù)定義及存儲(chǔ)器分配偽操作&l

21、t;/p><p>　　這一類偽操作的格式是：</p><p>　　[Variable] Mnemonic Operand,…,Operand [;comments]</p><p>　　其中變量（Variable）字段是可有可無的，它用符號(hào)地址表示，其作</p><p>　　用與指令語句前的標(biāo)號(hào)相同，但它的后面不跟冒號(hào)。如果語句中有變量，則匯編程

22、序使其記以第一個(gè)字節(jié)的偏移地址。</p><p>　　注釋（comments）字段用來說明該偽操作的功能，它也是可有可無的。</p><p>　　助記符（Mnemonic）字段用來說明所用偽操作的助記符。</p><p>　　即偽操作，說明所定義的數(shù)據(jù)類型。</p><p><b>　　代碼段</b></p>

23、<p>　　使用80×86的指令系統(tǒng)和尋址方式。指令由操作碼字段和操作數(shù)字段兩部分組成。用一指令序列完成程序設(shè)計(jì)。 </p><p><b>　?、?代碼設(shè)計(jì)</b></p><p>　　data segment</p><p>　　hashtable db ?,12,15,68,29,51,13,24,81,75

24、,26,19,18,?,?,?</p><p>　　temp db ?,?</p><p><b>　　x db 13</b></p><p><b>　　y db 16</b></p><p>　　Menu db 0dh,0ah, '********Hash table se

25、arch************' </p><p>　　db 0dh,0ah , ' Declarations: ' </p><p>　　db 0dh,0ah, '

26、 1.the length of the list: m=16 ' </p><p>　　db 0dh,0ah, ' 2.hash function is: h(key)=key mod 13' </p><p&

27、gt;　　db 0dh,0ah, ' 3.collision management: linear rehash method' </p><p>　　db0dh,0ah, 'h[i]=(h(key)+d[i]) mod m' db 0dh,0

28、ah, ' i=1,2,...,k (k<=m-1) d[i]=1,2,...,m-1 ' </p><p>　　db 0dh,0ah, ' Instructions: '

29、 </p><p>　　db 0dh,0ah, ' Input range:0~255 ' </p><p>　　db 0dh,0ah, ' Enter a number(1 or 2)

30、 ' </p><p>　　db 0dh,0ah, ' 1:CONTINUE 2:EXIT ' </p><p

31、>　　db 0dh,0ah, '*****************************$'</p><p>　　mess0 db 0dh,0ah, 'The hash table is: '</p><p>　　db 0dh,0ah,'?,12,15,68,29,51,13,24,81,7

32、5,26,19,18,?,?,?'</p><p>　　db 0dh,0ah, 'INPUT KEY:$'</p><p>　　mess1 db 0dh,0ah, 'FOUND!$'</p><p>　　mess11 db 0dh,0ah, 'The location (start with 0) is :$

33、'</p><p>　　mess2 db 0dh,0ah, 'SORRY,NOT FOUND!$'</p><p>　　mess3 db 0dh,0ah, 'ILLEGAL KEY DETECTED! Input again!$'</p><p>　　mess4 db 0dh,0ah, 'EXIT NOW.

34、$'</p><p>　　mess5 db 0dh,0ah, 'CONTINUE? 1.CONTINUE 2.EXIT$'</p><p><b>　　data ends</b></p><p>　　code segment</p><p>　　assume cs:code,ds:data&

35、lt;/p><p>　　main proc far</p><p><b>　　push ds</b></p><p><b>　　push ax</b></p><p>　　start: mov ax,data</p><p>　　mov ds,ax</p>

36、<p>　　lable:lea dx,menu</p><p>　　mov ah,09h</p><p><b>　　int 21h</b></p><p><b>　　call crlf</b></p><p>　　mov ah,01h</p><p><

37、;b>　　int 21h</b></p><p>　　cmp al,31h</p><p><b>　　jz func</b></p><p>　　cmp al,32h</p><p><b>　　jz exit</b></p><p>　　illegal:

38、call crlf</p><p>　　lea dx,mess3</p><p>　　mov ah,09h</p><p><b>　　int 21h</b></p><p>　　jmp lable</p><p>　　func:call inputkey</p><p&

39、gt;<b>　　call crlf</b></p><p>　　call hashsearch</p><p><b>　　call crlf</b></p><p>　　lea dx,mess5</p><p>　　mov ah,09h</p><p><b>

40、　　int 21h</b></p><p><b>　　call crlf</b></p><p>　　mov ah,01h</p><p><b>　　int 21h</b></p><p>　　cmp al,31h</p><p><b>　　jz

41、func</b></p><p>　　cmp al,32h</p><p><b>　　jz exit</b></p><p>　　jmp illegal</p><p>　　exit:call crlf</p><p>　　lea dx,mess4</p><p

42、>　　mov ah,09h</p><p><b>　　int 21h</b></p><p><b>　　call crlf</b></p><p><b>　　ret</b></p><p><b>　　main endp</b></p&

43、gt;<p>　　inputkey proc near</p><p>　　lea dx,mess0</p><p>　　mov ah,09h</p><p><b>　　int 21h</b></p><p><b>　　mov bx,0</b></p><p&g

44、t;　　inl1:mov ah,01h</p><p><b>　　int 21h</b></p><p>　　cmp al,0dh</p><p><b>　　jz inexit</b></p><p>　　sub al,30h</p><p><b>　　mo

45、v ah,0</b></p><p>　　xchg ax,bx</p><p><b>　　mov cx,10</b></p><p><b>　　mul cx</b></p><p><b>　　add bx,ax</b></p><p>

46、<b>　　jmp inl1</b></p><p>　　inexit:ret</p><p>　　inputkey endp</p><p>　　hashsearch procnear</p><p><b>　　push bx</b></p><p><b&

47、gt;　　mov cx,0</b></p><p><b>　　mov ax,bx</b></p><p><b>　　div x</b></p><p><b>　　mov bl,ah</b></p><p><b>　　mov bh,0</b&g

48、t;</p><p>　　mov temp[0],ah</p><p><b>　　mov si,bx</b></p><p>　　mov dl,hashtable[si]</p><p><b>　　mov dh,0</b></p><p><b>　　pop b

49、x</b></p><p><b>　　cmp bx,dx</b></p><p>　　jnz conflict</p><p><b>　　succeed:</b></p><p>　　lea dx,mess1</p><p>　　mov ah,09h</

50、p><p><b>　　int 21h</b></p><p>　　lea dx,mess11</p><p><b>　　int 21h</b></p><p>　　mov ah,02h</p><p>　　mov dl,temp[0]</p><p

51、>　　add dl,30H</p><p>　　cmp dl,3AH</p><p>　　jb twi </p><p>　　push dx ;位置超過10</p><p>　　mov dl,31H</p><p><b>　　int 21H</b></p>

52、<p><b>　　pop dx</b></p><p><b>　　sub dl,10</b></p><p>　　twi: int 21H</p><p>　　jmp hashexit</p><p><b>　　conflict:</b></p>

53、<p><b>　　push bx</b></p><p><b>　　push si</b></p><p><b>　　inc cx</b></p><p><b>　　cmp cx,15</b></p><p><b>　　j

54、a fail</b></p><p><b>　　add si,cx</b></p><p><b>　　mov ax,si</b></p><p><b>　　div y</b></p><p><b>　　mov bl,ah</b><

55、/p><p><b>　　mov bh,0</b></p><p>　　mov temp[0],ah</p><p><b>　　mov si,bx</b></p><p>　　mov dl,hashtable[si]</p><p><b>　　mov dh,0<

56、;/b></p><p><b>　　pop si</b></p><p><b>　　pop bx</b></p><p><b>　　cmp bx,dx</b></p><p>　　jnz conflict</p><p>　　jmp succ

57、eed</p><p>　　fail:pop si</p><p><b>　　pop bx</b></p><p>　　lea dx,mess2</p><p>　　mov ah,09h</p><p><b>　　int 21h</b></p><

58、p>　　jmp hashexit</p><p>　　hashexit:ret</p><p>　　hashsearch endp</p><p>　　crlf proc near</p><p>　　mov ah,02h</p><p>　　mov dl,0ah</p><p>

59、<b>　　int 21h</b></p><p>　　mov dl,0dh</p><p><b>　　int 21h</b></p><p><b>　　ret</b></p><p><b>　　crlf endp</b></p>

60、<p><b>　　code ends</b></p><p><b>　　end main</b></p><p>　?、凑{(diào)試分析與測試結(jié)果</p><p><b>　?、?編碼分析</b></p><p>　　哈希查找，顧名思義就是基于哈希表結(jié)構(gòu)的查找算法，其基本

61、思想是，按照建立哈希表時(shí)的哈希函數(shù)，根據(jù)給定關(guān)鍵字值，直接求出其哈希地址，若該地址中數(shù)據(jù)元素為空，則查找失敗；如果該地址中數(shù)據(jù)元素不為空，且其關(guān)鍵字值與給定關(guān)鍵字值相等，則查找成功；如果該地址中數(shù)據(jù)元素不為空，但其關(guān)鍵字值不等于給定關(guān)鍵字值，則需按照建立哈希表時(shí)解決沖突的辦法，繼續(xù)在“下一個(gè)哈希地址”中查找，如此深入，直至找到或者某一哈希地址中的元 素為空時(shí)結(jié)束。 </p><p>　　哈希查

62、找的方法是一種直接計(jì)算存儲(chǔ)地址的方法，在查找過程中，如果構(gòu)造哈希表所選擇的哈希函數(shù)使得地址分布均勻的話，幾乎無需進(jìn)行比較，就可以得出“找到”或者“找不到”的結(jié)論的。但由于在構(gòu)造哈希函數(shù)時(shí)難以避免發(fā)生沖突，因此，在考察哈希查找的效率時(shí)，不但要考慮查找時(shí)所需比較的次數(shù)，還需考慮求取哈希地址所需的時(shí)間，顯然，此時(shí)仍然可以用平均查找長度作為評(píng)價(jià)哈希查找效率的標(biāo)準(zhǔn)。</p><p><b>　　⒋2調(diào)試運(yùn)行<

63、;/b></p><p><b>　　編輯 ——輸入代碼</b></p><p>　　編譯 ——源文件建立后，用匯編程序?qū)υ次募R編，匯編后產(chǎn)生二進(jìn)制的目標(biāo)文件（OBJ文件）</p><p>　　連接 ——OBJ文件不是可執(zhí)行的文件，還必須使用連接程序（LINK）把OBJ文件轉(zhuǎn)換為可執(zhí)行的EXE文件</p><p>

64、;<b>　　調(diào)試 ——執(zhí)行程序</b></p><p><b>　?、?運(yùn)行結(jié)果</b></p><p><b>　　⒌心得體會(huì)</b></p><p>　　通過本次的課程設(shè)計(jì)，我更好的掌握了有關(guān)哈希表查找算法等程序設(shè)計(jì)中的中高級(jí)技術(shù)，而且也讓我熟練了調(diào)試方法，逐漸養(yǎng)成良好的編程習(xí)慣?！　?lt;/

65、p><p>　　在匯編課程設(shè)計(jì)過程中，雖然遇到了一些困難，但在老師的指導(dǎo)和同學(xué)的幫助下，經(jīng)過多次的修改和調(diào)試，終于找出了原因所在，當(dāng)然這也暴露出了前期我在理論知識(shí)方面的欠缺和動(dòng)手經(jīng)驗(yàn)的不足。最終的檢測調(diào)試環(huán)節(jié)，不斷出現(xiàn)錯(cuò)誤，不斷修正，不斷領(lǐng)悟，不斷獲取。實(shí)踐出真知，通過親自動(dòng)手，使我們掌握的知識(shí)不再是紙上談兵，也不再如以往一樣對(duì)于編程充滿了畏懼。 　　在走入社會(huì)并參加工作后，要做一個(gè)有所堅(jiān)持的人，不能遇到問

66、題就想到要退縮，知難而退，那樣永遠(yuǎn)不可能收獲成功。只有不厭其煩的發(fā)現(xiàn)問題所在，然后一一進(jìn)行解決，才能成功的做成想做的事，才能在今后的道路上劈荊斬棘，收獲喜悅，才可能得到社會(huì)及他人對(duì)你的認(rèn)可！</p><p>　　有一個(gè)好的態(tài)度才能夠做成一件事情，做好一件事情，在今后的學(xué)習(xí)和生活中我會(huì)更加努力完善自己，提升自己。</p><p><b>　?、秴⒖嘉墨I(xiàn)</b><

67、/p><p>　　Ⅰ《IBM—PC匯編語言程序設(shè)計(jì)（第2版）》 沈美明</p><p>　　溫冬嬋 編著 清華大學(xué)出版社</p><p>　?、颉禝BM—PC匯編語言程序設(shè)計(jì)實(shí)驗(yàn)教程》 沈美明 溫冬嬋 </p><p>　　張赤紅 編著 清華大學(xué)出版社</p><p>　　本科生課程設(shè)計(jì)成績評(píng)定表</p>

68、<p>　　班級(jí)：計(jì)算機(jī)1001班　 姓名：蔣為　　學(xué)號(hào)：0121010340132</p><p>　　注：最終成績以五級(jí)分制記。優(yōu)（90-100分）、良（80-89分）、中（70-79分）、</p><p>　　及格（60-69分）、60分以下為不及格</p><p><b>　　指導(dǎo)教師簽名：</b></p>&