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

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

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

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

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

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

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

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

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

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

10、 調(diào)試運行....................................16</p><p>　　⒋3調(diào)試結(jié)果.....................................16</p><p>　?、敌牡皿w會................................17</p><p>　?、秴⒖嘉墨I...................

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

12、;p>　?、泡斎胍恍┱麛?shù)，采用哈希表結(jié)構(gòu)存儲；</p><p>　?、茖崿F(xiàn)對哈希表的查找；</p><p>　?、浅绦虿捎米映绦蚪Y(jié)構(gòu)，結(jié)構(gòu)清晰；</p><p>　?、扔押们逦挠脩艚缑?，能識別輸入錯誤并控制錯誤的修改。</p><p><b>　　⒈2設(shè)計目的</b></p><p>　　

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

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

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

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

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

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

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

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

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

23、<p>　　使用80×86的指令系統(tǒng)和尋址方式。指令由操作碼字段和操作數(shù)字段兩部分組成。用一指令序列完成程序設(shè)計。 </p><p><b>　?、?代碼設(shè)計</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ù)，根據(jù)給定關(guān)鍵字值，直接求出其哈希地址，若該地址中數(shù)據(jù)元素為空，則查找失?。蝗绻摰刂分袛?shù)據(jù)元素不為空，且其關(guān)鍵字值與給定關(guān)鍵字值相等，則查找成功；如果該地址中數(shù)據(jù)元素不為空，但其關(guān)鍵字值不等于給定關(guān)鍵字值，則需按照建立哈希表時解決沖突的辦法，繼續(xù)在“下一個哈希地址”中查找，如此深入，直至找到或者某一哈希地址中的元 素為空時結(jié)束。 </p><p>　　哈希查

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

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

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

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

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

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

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