1、课程设计哈希表查找算法的实现 学 号： 0121010340132课 程 设 计题 目哈希表查找算法的实现学 院计算机科学与技术学院专 业计算机科学与技术专业班 级计算机1001班姓 名 指导教师 2012年6月27日课程设计任务书题目: 哈希表查找算法的实现初始条件：理论：完成了汇编语言程序设计课程，对微机系统结构和80系列指令系统有了较深入的理解，已掌握了汇编语言程序设计的基本方法和技巧。实践：完成了汇编语言程序设计的4个实验，熟悉了汇编语言程序的设计环境并掌握了汇编语言程序的调试方法。要求完成的主要任务: （包括课程设计工作量及其技术要求，以及说明书撰写等具体要求）进一步理解和掌握较复杂
2、程序的设计方法，掌握子程序结构的设计和友好用户界面的设计。具体的设计任务及要求：1） 输入一些整数，采用哈希表结构存储；2） 实现对哈希表的查找；3） 程序采用子程序结构，结构清晰；4） 友好清晰的用户界面，能识别输入错误并控制错误的修改。在完成设计任务后，按要求撰写课程设计说明书；对课程设计说明书的具体要求请见课程设计指导书。阅读资料：1）IBMPC汇编语言程序设计实验教程实验2.42）IBMPC汇编语言程序设计（第2版）例6.11时间安排：设计安排一周：周1、周2：完成系统分析及设计。周3、周4：完成程序调试，和验收。周5：撰写课程设计报告。指导教师签名： 年 月 日系主任（或责任教师）签
3、名： 年 月 日 目 录设计目的与任务.4 1问题描述.4 2设计目的.4 3测试用例.5设计分析.5 1 存储结构.5 2主要算法.5设计步骤.6 1概要设计.6 2代码设计.7调试分析和测试结果.15 1 编码分析.15 2 调试运行.16 3调试结果.16心得体会.17参考文献.18设计目的与任务 1问题描述 1题目：哈希表查找算法的实现 2任务与要求： 输入一些整数，采用哈希表结构存储； 实现对哈希表的查找； 程序采用子程序结构，结构清晰； 友好清晰的用户界面，能识别输入错误并控制错误的修改。 2设计目的 汇编语言是计算机专业的专业基础课，也是电子、通信等相 关专业的计算机课程。通过课
4、程设计，一反面使我们掌握汇编语言的编程方法、思路和技巧，并对计算机的底层编程有一定认识；另一方面，也能让我们理解计算机底层运行程序的机制，了解计算机的工作原理，为以后一些课程的学习（如操作系统、微机原理等）打下基础。比如强调CS和IP寄存器的作用，比如在介绍子程序设计时，除了让学生能够使用CALL指令和RET指令编写子程序结构的程序，还要通过CALL指令和RET指令内部执行的操作，让学生明白计算机内部如何能够做到调用子程序，又如何能够从子程序返回主程序，子程序多层嵌套时为什么子程序返回不会乱套等问题。实际上，完成这次的课程设计，我们也会对以前学过的C+语言的一些概念有更深刻的理解，如指针，也会
5、明白数组等数据结构在计算机内部是如何组织和表示的。 3测试用例 输入的一系列整数为： ?, 12,15,68,29,51,13,24,81,75,26,19,18,?,?,?设计分析1存储结构 哈希表是表示集合和字典的另一种有效方法，它提供了一种完全不同的存储和搜索方式，通过将关键码映射到表中某个位置上来存储元素，然后根据关键码用同样的方式直接访问。 2主要算法 散列方法 理想的搜索方法是可以不经过任何比较，一次直接从字典中得到要搜索的元素。如果在元素的存储位置与它的关键码之间建立一个确定的函数对应关系Hash（），使得每个关键码与结构中的一个唯一的位置相对应：Address=Hash（key
6、） 在插入时，依此函数计算存储位置并按此位置存放。在搜索时，对元素的关键码进行同样的函数计算，把求得的函数当做元素的存储位置，在结构中按此位置取元素比较，若关键码相等，则搜索成功。这种方法就叫做散列方法。在散列方法中使用的转换函数叫做散列函数。 散列函数在构造散列函数时有几点需要加以注意：其一是散列函数的定义域必须包括需要存储的全部关键码，而如果散列表允许有m个地址时，其值域必须在0到m-1之间。其二散列函数计算出来的地址应能均匀分布在整个地址空间中：若key是从关键码集合中随机抽取的一个关键码，散列函数应能以同等概率取在0到m-1中的每一个值。其三是散列函数应是简单的，能在短时间内计算出来的
7、。本次课程设计采用的散列函数是除留取余法。 除留取余法设哈希表中允许的地址数为m,取一个不大于m但最接近于或等于m的质数p作为除数，利用以下公式把关键码转换成散列地址。散列函数为： Hash(key)=key MOD p (p=m)设计步骤 1概要设计 数据段 数据定义及存储器分配伪操作 这一类伪操作的格式是： Variable Mnemonic Operand,Operand ;comments其中变量（Variable）字段是可有可无的，它用符号地址表示，其作用与指令语句前的标号相同，但它的后面不跟冒号。如果语句中有变量，则汇编程序使其记以第一个字节的偏移地址。注释（comments）字段
8、用来说明该伪操作的功能，它也是可有可无的。助记符（Mnemonic）字段用来说明所用伪操作的助记符。即伪操作，说明所定义的数据类型。 代码段 使用8086的指令系统和寻址方式。指令由操作码字段和操作数字段两部分组成。用一指令序列完成程序设计。 2代码设计data segment hashtable db ?,12,15,68,29,51,13,24,81,75,26,19,18,?,?,? temp db ?,? x db 13 y db 16 Menu db 0dh,0ah, *Hash table search* db 0dh,0ah , Declarations: db 0dh,0ah,
9、 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 db0dh,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
10、 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, IL
11、LEGAL KEY DETECTED! Input again!$ mess4 db 0dh,0ah, EXIT NOW.$ mess5 db 0dh,0ah, CONTINUE? 1.CONTINUE 2.EXIT$data endscode segment assume cs:code,ds:data main proc far push ds push ax start: mov ax,data mov ds,ax lable: lea dx,menu mov ah,09h int 21h call crlf mov ah,01h int 21h cmp al,31h jz func c
12、mp al,32h jz exit illegal:call crlf lea dx,mess3 mov ah,09h int 21h jmp lable func: call inputkey call crlf call hashsearch call crlf lea dx,mess5 mov ah,09h int 21h call crlf mov ah,01h int 21h cmp al,31h jz func cmp al,32h jz exit jmp illegal exit: call crlf lea dx,mess4 mov ah,09h int 21h call cr
13、lf ret main endp inputkey proc near lea dx,mess0 mov ah,09h int 21h mov bx,0 inl1: mov ah,01h int 21h cmp al,0dh jz inexit sub al,30h mov ah,0 xchg ax,bx mov cx,10 mul cx add bx,ax jmp inl1 inexit: ret inputkey endp hashsearch proc near push bx mov cx,0 mov ax,bx div x mov bl,ah mov bh,0 mov temp0,a
14、h mov si,bx mov dl,hashtablesi mov dh,0 pop bx cmp bx,dx jnz conflict succeed: lea dx,mess1 mov ah,09h int 21h lea dx,mess11 int 21h mov ah,02h mov dl,temp0 add dl,30H cmp dl,3AH jb twi push dx ;位置超过10 mov dl,31H int 21H pop dx sub dl,10 twi: int 21H jmp hashexit conflict: push bx push si inc cx cmp
15、 cx,15 ja fail add si,cx mov ax,si div y mov bl,ah mov bh,0 mov temp0,ah mov si,bx mov dl,hashtablesi mov dh,0 pop si pop bx cmp bx,dx jnz conflict jmp succeed fail: pop si pop bx lea dx,mess2 mov ah,09h int 21h jmp hashexit hashexit:ret hashsearch endp crlf proc near mov ah,02h mov dl,0ah int 21h m
16、ov dl,0dh int 21h ret crlf endp code ends end main调试分析与测试结果1编码分析哈希查找，顾名思义就是基于哈希表结构的查找算法，其基本思想是，按照建立哈希表时的哈希函数，根据给定关键字值，直接求出其哈希地址，若该地址中数据元素为空，则查找失败；如果该地址中数据元素不为空，且其关键字值与给定关键字值相等，则查找成功；如果该地址中数据元素不为空，但其关键字值不等于给定关键字值，则需按照建立哈希表时解决冲突的办法，继续在“下一个哈希地址”中查找，如此深入，直至找到或者某一哈希地址中的元 素为空时结束。 哈希查找的方法是一种直接计算存储地址的方法，在查找
17、过程中，如果构造哈希表所选择的哈希函数使得地址分布均匀的话，几乎无需进行比较，就可以得出“找到”或者“找不到”的结论的。但由于在构造哈希函数时难以避免发生冲突，因此，在考察哈希查找的效率时，不但要考虑查找时所需比较的次数，还需考虑求取哈希地址所需的时间，显然，此时仍然可以用平均查找长度作为评价哈希查找效率的标准。2调试运行 编辑 输入代码 编译 源文件建立后，用汇编程序对源文件汇编，汇编后产生二进制的目标文件（OBJ文件） 连接 OBJ文件不是可执行的文件，还必须使用连接程序（LINK）把OBJ文件转换为可执行的EXE文件 调试 执行程序3运行结果 心得体会 通过本次的课程设计，我更好的掌握了
18、有关哈希表查找算法等程序设计中的中高级技术，而且也让我熟练了调试方法，逐渐养成良好的编程习惯。 在汇编课程设计过程中，虽然遇到了一些困难，但在老师的指导和同学的帮助下，经过多次的修改和调试，终于找出了原因所在，当然这也暴露出了前期我在理论知识方面的欠缺和动手经验的不足。最终的检测调试环节，不断出现错误，不断修正，不断领悟，不断获取。实践出真知，通过亲自动手，使我们掌握的知识不再是纸上谈兵，也不再如以往一样对于编程充满了畏惧。 在走入社会并参加工作后，要做一个有所坚持的人，不能遇到问题就想到要退缩，知难而退，那样永远不可能收获成功。只有不厌其烦的发现问题所在，然后一一进行解决，才能成功的做成想做
19、的事，才能在今后的道路上劈荆斩棘，收获喜悦，才可能得到社会及他人对你的认可！ 有一个好的态度才能够做成一件事情，做好一件事情，在今后的学习和生活中我会更加努力完善自己，提升自己。参考文献IBMPC汇编语言程序设计（第2版） 沈美明温冬婵 编著 清华大学出版社IBMPC汇编语言程序设计实验教程 沈美明 温冬婵 张赤红 编著 清华大学出版社本科生课程设计成绩评定表班级：计算机1001班 姓名：蒋为学号：0121010340132序号评分项目满分实得分1学习态度认真、遵守纪律102设计分析合理性103设计方案正确性、可行性、创造性204设计结果正确性405设计报告的规范性106设计验收10总得分/等级评语：注：最终成绩以五级分制记。优（90-100分）、良（80-89分）、中（70-79分）、及格（60-69分）、60分以下为不及格指导教师签名：20 年月日
