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

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

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

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

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

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

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

7、<p>　?、?設計目的....................................4</p><p>　　⒈3測試用例....................................5</p><p>　?、苍O計分析................................5 </p><p>　?、? 存儲結構.......

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

9、...6</p><p>　　⒊2代碼設計.....................................7</p><p>　?、凑{試分析和測試結果......................15</p><p>　　⒋1 編碼分析...................................15</p><p>　?、?

10、 調試運行....................................16</p><p>　?、?調試結果.....................................16</p><p>　?、敌牡皿w會................................17</p><p>　　⒍參考文獻...................

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

12、;p>　　⑴輸入一些整數，采用哈希表結構存儲；</p><p>　?、茖崿F(xiàn)對哈希表的查找；</p><p>　?、浅绦虿捎米映绦蚪Y構，結構清晰；</p><p>　?、扔押们逦挠脩艚缑?，能識別輸入錯誤并控制錯誤的修改。</p><p><b>　?、?設計目的</b></p><p>　　

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

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

15、t;/p><p>　　輸入的一系列整數為：</p><p>　　?, 12,15,68,29,51,13,24,81,75,26,19,18,?,?,?</p><p><b>　?、苍O計分析</b></p><p><b>　?、?存儲結構</b></p><p>　　哈希表是

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

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

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

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

20、<p>　　Hash(key)=key MOD p (p<=m)</p><p><b>　　⒊設計步驟</b></p><p><b>　?、?概要設計</b></p><p><b>　　數據段</b></p><p>　　數據定義及存儲器分配偽操作&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>　　即偽操作，說明所定義的數據類型。</p><p><b>　　代碼段</b></p>

23、<p>　　使用80×86的指令系統(tǒng)和尋址方式。指令由操作碼字段和操作數字段兩部分組成。用一指令序列完成程序設計。 </p><p><b>　?、?代碼設計</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>　?、凑{試分析與測試結果</p><p><b>　　⒋1編碼分析</b></p><p>　　哈希查找，顧名思義就是基于哈希表結構的查找算法，其基本

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

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

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

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

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

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

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

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