课程设计-哈希表查找算法的实现

1、学 号：0121010340132课程设计题目哈希表查找算法的实现学院计算机科学与技术学院专业计算机科学与技术专业班 级计算机1001班姓名2012年 6 月 27 日课程设计任务书题目：哈希表查找算法的实现初始条件：理论：完成了汇编语言程序设计课程，对微机系统结构和80系列指令系统有了较深入的理解，已掌握了汇编语言程序设计的基本方法和技巧。实践：完成了汇编语言程序设计的4个实验，熟悉了汇编语言程序的设计环境并掌握了汇编语言程序的调试方法。要求完成的主要任务：（包括课程设计工作量及其技术要求，以及说明书撰写等具体要求）进一步理解和掌握较复杂程序的设计方法，掌握子程序结构的设计和友好用户界面的设

2、计。具体的设计任务及要求：1）输入一些整数，采用哈希表结构存储；2）实现对哈希表的查找；3）程序采用子程序结构，结构清晰；4）友好清晰的用户界面，能识别输入错误并控制错误的修改。在完成设计任务后，按要求撰写课程设计说明书；对课程设计说明书的具体要求请见 课程设计指导书。阅读资料：1）旧M PC汇编语言程序设计实验教程实验 2.42）旧M PC汇编语言程序设计（第 2版）例6.11时间安排：设计安排一周：周1、周2:完成系统分析及设计。周3、周4:完成程序调试，和验收。周5:撰写课程设计报告。指导教师签名：年月日系主任（或责任教师）签名：年月日 TOC o 1-5 h z HYPERLINK l

3、 bookmark4 o Current Document .设计目的与任务4. 1问题描述4.2设计目的43测试用例5 HYPERLINK l bookmark6 o Current Document .设计分析5.1存储结构5. 2主要算法5 HYPERLINK l bookmark8 o Current Document .设计步骤61概要设计62代码设计7 HYPERLINK l bookmark10 o Current Document .调试分析和测试结果 151编码分析15调试运行16调试结果16 HYPERLINK l bookmark12 o Current Document

4、 .心得体会17 HYPERLINK l bookmark14 o Current Document .参考文献18.设计目的与任务问题描述题目：哈希表查找算法的实现1. 2任务与要求：输入一些整数，采用哈希表结构存储；实现对哈希表的查找；程序采用子程序结构，结构清晰；友好清晰的用户界面，能识别输入错误并控制错误的 修改。1.2设计目的汇编语言是计算机专业的专业基础课， 也是电子、通信等相 关专业的计算机课程。通过课程设计，一反面使我们掌握汇编语言的 编程方法、思路和技巧，并对计算机的底层编程有一定认识；另一方 面，也能让我们理解计算机底层运行程序的机制，了解计算机的工作原理，为以后一些课程的

5、学习（如操作系统、微机原理等）打下基础。 比如强调CS和IP寄存器的作用，比如在介绍子程序设计时，除了让 学生能够使用CALL指令和RET指令编写子程序结构的程序，还要 通过CALL指令和RET指令内部执行的操作，让学生明白计算机内 部如何能够做到调用子程序，又如何能够从子程序返回主程序， 子程 序多层嵌套时为什么子程序返回不会乱套等问题。实际上，完成这次4的课程设计，我们也会对以前学过的C+语言的一些概念有更深刻的理解，如指针，也会明白数组等数据结构在计算机内部是如何组织和 表本的。L3测试用例输入的一系列整数为：?, 12,15,68,29,51,13,24,81,75,26,19,18,

6、?,?,?2.设计分析1存储结构哈希表是表示集合和字典的另一种有效方法，它提供了一 种完全不同的存储和搜索方式，通过将关键码映射到表中某个位置上 来存储元素，然后根据关键码用同样的方式直接访问。2主要算法散列方法理想的搜索方法是可以不经过任何比较，一次直接从字典中得到要搜索的元素。如果在元素的存储位置与它的关键码之间建立一个确 定的函数对应关系Hash(),使得每个关键码与结构中的一个唯一的 位置相对应：Address=Hash (key)在插入时，依此函数计算存储位置并按此位置存放。在搜索时， 对元素的关键码进行同样的函数计算，把求得的函数当做元素的存储 位置，在结构中按此位置取元素比较，若

7、关键码相等，则搜索成功 这种方法就叫做散列方法。在散列方法中使用的转换函数叫做散列函 数。散列函数在构造散列函数时有几点需要加以注意：其一是散列函数的定义域必须包括需要存储的全部关键码，而如果散列表允许有m个地址时，其值域必须在0到m-1之间。其二散列函数计算出来的地址应能 均匀分布在整个地址空间中：若key是从关键码集合中随机抽取的一 个关键码，散列函数应能以同等概率取在 0到m-1中的每一个值。其 三是散列函数应是简单的，能在短时间内计算出来的。本次课程设计采用的散列函数是除留取余法。除留取余法设哈希表中允许的地址数为 m,取一个不大于m但最接近于或等 于m的质数p作为除数，利用以下公式把

8、关键码转换成散列地址。 散列函数为：Hash(key)=key MOD p (p=m)3.设计步骤1概要设计数据段数据定义及存储器分配伪操作 这一类伪操作的格式是：Variable Mnemonic Operand, ，Operand ;comments其中变量(Variable )字段是可有可无的，它用符号地址表示，其作 用与指令语句前的标号相同，但它的后面不跟冒号。如果语句中有变 量，则汇编程序使其记以第一个字节的偏移地址。注释（comments字段用来说明该伪操作的功能，它也是可有可无的。助记符（Mnemoni。字段用来说明所用伪操作的助记符。即伪操作，说明所定义的数据类型。代码段使用8

9、0X 86的指令系统和寻址方式。指令由操作码字段和操作 数字段两部分组成。用一指令序列完成程序设计。2代码设计data segmenthashtabledb 7,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* TOC o 1-5 h z db 0dh,0ah ,*Declarations:*db 0dh,0ah,*1.the length of the list: m=16*db 0dh,0ah,*2.hash function is: h

10、(key)=key mod13*db 0dh,0ah,* 3.collision management: linear rehash method*db0dh,0ah,hi=(h(key)+di)moddb 0dh,0ah,i=1,2,.,k (k=m-1) di=1,2,.,m-1 db 0dh,0ah,Instructions:db 0dh,0ah,Input range:。255db 0dh,0ah,Enter a number(1 or 2)db 0dh,0ah,1:CONTINUE2:EXITdb 0dh,0ah,*$mess0db 0dh,0ah, The hash table i

11、s:db 0dh,0ah?,12,15,68,29,51,13,24,81,75,26,19,18,?,?,?db 0dh,0ah,INPUT KEY:$mess1db 0dh,0ah,FOUND!$mess11db 0dh,0ah,mess2db 0dh,0ah,SORRYNOT FOUND!$The location (start with 0) is :$mess3db 0dh,0ah,mess4db 0dh,0ah,EXIT NOW.$ILLEGAL KEY DETECTED! Input again!$mess5db 0dh,0ah,CONTINUE? 1.CONTINUE 2.EX

12、IT$data endscode segmentassumecs:code,ds:datamain proc farpush dspush axstart mov ax,datamov ds,axlable: lea dx,menumov ah,09hint 21hcall crlfmov ah,01hint 21hcmp al,31hjz funccmp al,32hjz exit川egal:call crlflea dx,mess3mov ah,09hint 21hjmp lable func: call inputkeycall crlfcall hashsearchcall crlfl

13、ea dx,mess5mov ah,09hint 21hcall crlfmov ah,01hint 21hcmp al,31hjz funccmp al,32hjz exitjmp illegalexit: call crlflea dx,mess4mov ah,09hint 21hcall crlfretmain endp10 inputkey proc nearlea dx,mess0mov ah,09hint 21hmov bx,0inl1: mov ah,01hint 21hcmp al,0dhjz inexitsub al,30hmov ah,0 xchg ax,bxmov cx,

14、10mul cxadd bx,axjmp inl1inexit: retinputkey endphashsearch proc near push bxmov cx,011mov 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,3AH jb twi12

15、push dx;位置超过10mov dl,31Hint 21Hpop dxsub dl,10twi: int 21Hjmp hashexitconflict:push bxpush siinc cxcmp cx,15ja failadd si,cxmov ax,sidiv ymov bl,ahmov bh,0mov temp0,ahmov si,bxmov dl,hashtablesi13mov dh,0pop sipop bxcmp bx,dxjnz conflictjmp succeedfail: pop sipop bxlea dx,mess2mov ah,09hint 21hjmp h

16、ashexithashexit:rethashsearch endpcrlf proc nearmov ah,02hmov dl,0ahint 21hmov dl,0dhint 21h ret14crlf endpcode ends end main4.调试分析与测试结果4. 1编码分析哈希查找，顾名思义就是基于哈希表结构的查找算法，其基本思想是，按照建立哈希表时的哈希函数，根据给定关键字值，直接求出 其哈希地址，若该地址中数据元素为空，则查找失败；如果该地址中 数据元素不为空，且其关键字值与给定关键字值相等，则查找成功； 如果该地址中数据元素不为空，但其关键字值不等于给定关键字值， 则需按照

17、建立哈希表时解决冲突的办法，继续在下一个哈希地址”中查找，如此深入，直至找到或者某一哈希地址中的元素为空时结束。哈希查找的方法是一种直接计算存储地址的方法，在查找过程 中，如果构造哈希表所选择的哈希函数使得地址分布均匀的话，几乎无需进行比较，就可以得出 找到”或者 找不到”的结论的。但由于在 构造哈希函数时难以避免发生冲突，因此，在考察哈希查找的效率时， 不但要考虑查找时所需比较的次数，还需考虑求取哈希地址所需的时15间，显然，此时仍然可以用平均查找长度作为评价哈希查找效率的标准。4. 2调试运行编辑一一输入代码编译一一源文件建立后，用汇编程序对源文件汇编，汇编后产生二进制的目标文件（OBJ文

18、件）连接一一OBJ文件不是可执行的文件，还必须使用连接程序（LINK ）把OBJ文件转换为可执行的EXE文件调试一一执行程序4. 3运行结果勒 C:J M SO FTMasmba nDWTem p. exe二.匕。Hash tAble 后HN?ieK*KHlEmWM*M*WHNHf4eKdMDeclaFations：.the length of the list： m=16.hash function is： h=key nod 13.collision management ： linear rehasln methodhi= nod m”1含 - kdtikl.Z.jmTI instruct ions 二Input yange ：0*255Enter a numheFIsCONTINUE 2=EX【T16.心得体会通过本次的课程设计，我更好的掌握了有关哈希表查找算法等程 序设计中的中高级技术，而且也让我熟练了调试方法，逐渐养成良好 的编程习惯。在汇编课程设计过程中，虽然遇到了一些困难，但在老师的指 导和