哈希表查找算法课程设计任务书.doc

武汉理工大学IBMPC汇编程序设计程序设计报告书学 号： 0121010340410课 程 设 计题 目哈希表查找算法的实现学 院计算机科学与技术学院专 业计算机科学与技术专业班 级计科1004班姓 名郭守飞指导教师许毅2012年6月21日课程设计任务书学生姓名： 郭守飞 专业班级： 计科1004班 指导教师： 许毅 工作单位：计算机科学与技术学院 题目: 哈希表查找算法的实现初始条件：理论：完成了汇编语言程序设计课程，对微机系统结构和80系列指令系统有了较深入的理解，已掌握了汇编语言程序设计的基本方法和技巧。实践：完成了汇编语言程序设计的4个实验，熟悉了汇编语言程序的设计环境并掌握了汇编语言程序的调试方法。要求完成的主要任务: （包括课程设计工作量及其技术要求，以及说明书撰写等具体要求）进一步理解和掌握较复杂程序的设计方法，掌握子程序结构的设计和友好用户界面的设计。具体的设计任务及要求：1） 输入一些整数，采用哈希表结构存储；2） 实现对哈希表的查找；3） 程序采用子程序结构，结构清晰；4） 友好清晰的用户界面，能识别输入错误并控制错误的修改。在完成设计任务后，按要求撰写课程设计说明书；对课程设计说明书的具体要求请见课程设计指导书。阅读资料：1）IBMPC汇编语言程序设计实验教程实验2.42）IBMPC汇编语言程序设计（第2版）例6.11时间安排：设计安排一周：周1、周2：完成系统分析及设计。周3、周4：完成程序调试，和验收。周5：撰写课程设计报告。指导教师签名： 年 月 日系主任（或责任教师）签名： 年 月 日哈希表查找算法的实现1. 设计内容及要求（1）输入一些整数，采用哈希表结构存储；（2）实现对哈希表的查找；（3）程序采用子程序结构，结构清晰；（4）友好清晰的用户界面，能识别输入错误并控制错误的修改。2.设计方案说明开始 显示主菜单 输出哈希表 输入字符1 N输入要查找的数字 N 输入字符2 显示该数字存在并输出该数字在哈希表中的位置判断该数字是否在哈希表中 N 显示该数字不存在哈希表中结束退出流程图注解：该程序由主程序main和inputkey，hashsearch，crlf三个子程序组成，程序运行时会显示一个有好清晰的用户界面，该界面会有哈希表的相关信息。根据提示输入1时，程序会输出哈希表并提示输入要查找的数字，输入完数字后，如果存在就显示在哈希表中的位置，如果不存在就显示不存在。输入2时就退出程序。3.程序代码data segmenthashtable db ?,12,15,68,29,51,13,24,81,75,26,19,18,?,?,? /定义一个哈希表temp db ?,?x db 13y db 16menu db 0dh,0ah,* Hash table search * db 0dh,0ah, Declarations: db 0dh,0ah, 1.the length of the list: m=16 db 0dh,0ah, 2.hash function is: h(key)=key mod 13 db 0dh,0ah, 3.collision management: linear rehash method db 0dh,0ah, hi=( h(key)+di ) mod m db 0dh,0ah, i=1,2,.,k (k=m-1) di=1,2,.,m-1 db 0dh,0ah, Instructions: db 0dh,0ah, Input range:0255 db 0dh,0ah, Enter a number(1 or 2) db 0dh,0ah, 1:CONTINUE 2:EXIT db 0dh,0ah,*$mess0 db 0dh,0ah,The hash table is: db 0dh,0ah,?,12,15,68,29,51,13,24,81,75,26,19,18,?,?,? db 0dh,0ah,INPUT KEY:$mess1 db 0dh,0ah,FOUND!$mess11 db 0dh,0ah,The location (start with 0) is :$mess2 db 0dh,0ah,SORRY,NOT FOUND!$mess3 db 0dh,0ah,ILLEGAL KEY DETECTED! Input again!$mess4 db 0dh,0ah,EXIT NOW.$mess5 db 0dh,0ah,CONTINUE? 1.CONTINUE 2.EXIT$data endscode segmentassume cs:code,ds:datamain proc far / 主程序main开始push dspush axstart:mov ax,datamov ds,axlable:lea dx,menumov ah,09hint 21hcall crlfmov ah,01hint 21hcmp al,31hjz funccmp al,32hjz exitillegal:call crlf /转入子程序crlflea dx,mess3mov ah,09hint 21hjmp lablefunc:call inputkey /转入子程序inputkeycall crlf /转入子程序crlfcall hashsearch /转入子程序hashsearchcall crlf /转入子程序crlflea dx,mess5mov ah,09hint 21hcall crlf /转入子程序crlfmov ah,01hint 21hcmp al,31hjz funccmp al,32hjz exitjmp illegalexit:call crlf /转入子程序crlflea dx,mess4mov ah,09hint 21hcall crlf /转入子程序crlfretmain endp /主程序main结束inputkey proc near /子程序inputkey开始lea dx,mess0mov ah,09hint 21hmov bx,0inl1:mov ah,01hint 21hcmp al,0dhjz inexitsub al,30hmov ah,0xchg ax,bxmov cx,10mul cxadd bx,axjmp inl1inexit:retinputkey endp /子程序inputkey结束hashsearch procnear /子程序hashsearch开始push bxmov cx,0mov ax,bxdiv xmov bl,ahmov bh,0mov temp0,ahmov si,bxmov dl,hashtablesimov dh,0pop bxcmp bx,dxjnz conflictsucceed:lea dx,mess1mov ah,09hint 21hlea dx,mess11int 21hmov ah,02hmov dl,temp0add dl,30Hcmp dl,3AHjb twi push dx ;位置超过10mov dl,31Hint 21Hpop dxsub dl,10 twi: int 21Hjmp hashexitconflict:push bxpush siinc cxcmp cx,15ja failadd si,cxmov ax,sidiv ymov bl,ahmov bh,0mov temp0,ahmov si,bxmov dl,hashtablesimov dh,0pop sipop bxcmp bx,dxjnz conflictjmp succeedfail:pop sipop bxlea dx,mess2mov ah,09hint 21hjmp hashexithashexit:rethashsearch endp /子程序hashsearch结束crlf proc near /子程序crlf开始mov ah,02hmov dl,0ahint 21hmov dl,0dhint 21hretcrlf endp /子程序crlf结束code endsend main4.运行调试图1开始运行程序会显示出一个主菜单，显示哈希表的相关信息，并提示输入1继续程序，输入0退出程序.图2输入1，显示出哈希表中的数字，输入一个关键字51，程序显示FOUND！并显示该数字在哈希表中的位置是：5。图3继续输入1，输入要查找的数字99，程序显示”SORRY.NOT FOUND!”表示99不在哈希表中。查找完毕后，输入数字2退出程序。5.参阅资料1）IBMPC汇编语言程序设计实验教程实验2.42）IBMPC汇编语言程序设计（第2版）例6.116.设计心得体会和所有的程序设计语言一样，要学好汇编语言，实验是必不可少的环节。我深有体会：书上的程序都能看懂，基本原理也都明白，但是在自己亲手编写程序时，却无从下手，甚至连第一句该怎么写都不知道。通过实验，可以在很大程度上加深印象。在书上看程序，一切都是理所当然，十分顺利，而自己动手，才真正发现自己的不足之处。编写程序在记事本中进行即可，掌握debug的使用对实验有很大帮助。通过这次实验，使我对哈希表的查找算法有了更熟练的掌握，认识更深了。对汇编语言的运用也更加熟练了，这次实验使我获益匪浅。汇编语言本身就是一门很重要的应用技术。本次实验是我加深了对汇编语言的理解。如果想学好计算机编程技能，如果想做一名合格的编程人员，如果我们想在计算机编程之路上走得更远，我们只有，也必须深入了解汇编语言，才能完整，完善的建立计算机编程知识体系！本科生