学 号： 0121010340132课 程 设 计题 目 哈希表查找算法的实现学 院 计算机科学与技术学院专 业 计算机科学与技术专业班 级 计算机 1001 班姓 名 蒋为指导教师 杨荣英2012 年 6 月 27 日2课程设计任务书学生姓名： 蒋为 专业班级： 计科 1001 班 指导教师： 杨荣英 工作单位：计算机科学与技术学院 题目: 哈希表查找算法的实现初始条件：理论：完成了汇编语言程序设计课程，对微机系统结构和 80 系列指令系统有了较深入的理解，已掌握了汇编语言程序设计的基本方法和技巧。实践：完成了汇编语言程序设计的 4 个实验，熟悉了汇编语言程序的设计环境并掌握了汇编语言程序的调试方法。要求完成的主要任务: （包括课程设计工作量及其技术要求，以及说明书撰写等具体要求）进一步理解和掌握较复杂程序的设计方法，掌握子程序结构的设计和友好用户界面的设计。具体的设计任务及要求：1） 输入一些整数，采用哈希表结构存储；2） 实现对哈希表的查找；3） 程序采用子程序结构，结构清晰；4） 友好清晰的用户界面，能识别输入错误并控制错误的修改。在完成设计任务后，按要求撰写课程设计说明书；对课程设计说明书的具体要求请见课程设计指导书。阅读资料：1） IBMPC 汇编语言程序设计实验教程实验 2.42） IBMPC 汇编语言程序设计（第 2 版） 例 6.11时间安排：设计安排一周：周 1、周 2：完成系统分析及设计。周 3、周 4：完成程序调试，和验收。周 5：撰写课程设计报告。指导教师签名： 年 月 日系主任（或责任教师）签名： 年 月 日3目 录设计目的与任务.41 问题描述.42 设计目的.43 测试用例.5设计分析.5 1 存储结构.52 主要算法.5设计步骤.61 概要设计.62 代码设计.7调试分析和测试结果.151 编码分析.152 调试运行.163 调试结果.16心得体会.17参考文献.184设计目的与任务1 问题描述1 题目：哈希表查找算法的实现 2 任务与要求：输入一些整数，采用哈希表结构存储；实现对哈希表的查找；程序采用子程序结构，结构清晰；友好清晰的用户界面，能识别输入错误并控制错误的修改。2 设计目的汇编语言是计算机专业的专业基础课，也是电子、通信等相 关专业的计算机课程。通过课程设计，一反面使我们掌握汇编语言的编程方法、思路和技巧，并对计算机的底层编程有一定认识；另一方面，也能让我们理解计算机底层运行程序的机制，了解计算机的工作原理，为以后一些课程的学习（如操作系统、微机原理等）打下基础。比如强调 CS 和 IP 寄存器的作用，比如在介绍子程序设计时，除了让学生能够使用 CALL 指令和 RET 指令编写子程序结构的程序，还要通过 CALL 指令和 RET 指令内部执行的操作，让学生明白计算机内部如何能够做到调用子程序，又如何能够从子程序返回主程序，5子程序多层嵌套时为什么子程序返回不会乱套等问题。实际上，完成这次的课程设计，我们也会对以前学过的 C+语言的一些概念有更深刻的理解，如指针，也会明白数组等数据结构在计算机内部是如何组织和表示的。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 中的每一个值。其三是散列函数应是简单的，能在短时间内计算出来的。本次课程设计采用的散列函数是除留取余法。除留取余法设哈希表中允许的地址数为 m,取一个不大于 m 但最接近于或等于 m 的质数 p 作为除数，利用以下公式把关键码转换成散列地址。散列函数为： Hash(key)=key MOD p (p=m)设计步骤1 概要设计数据段数据定义及存储器分配伪操作这一类伪操作的格式是：Variable Mnemonic Operand,Operand ;comments7其中变量（Variable）字段是可有可无的，它用符号地址表示，其作用与指令语句前的标号相同，但它的后面不跟冒号。如果语句中有变量，则汇编程序使其记以第一个字节的偏移地址。注释（comments）字段用来说明该伪操作的功能，它也是可有可无的。助记符（Mnemonic）字段用来说明所用伪操作的助记符。即伪操作，说明所定义的数据类型。代码段使用 8086 的指令系统和寻址方式。指令由操作码字段和操作数字段两部分组成。用一指令序列完成程序设计。 2 代码设计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: 8db 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 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 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$9data endscode segmentassume cs: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 exitillegal:call crlflea dx,mess3mov ah,09h10int 21hjmp lablefunc: call inputkeycall crlfcall hashsearchcall crlflea dx,mess5mov ah,09hint