《散列表的设计与实现》课程设计说明书.docx
《《散列表的设计与实现》课程设计说明书.docx》由会员分享，可在线阅读，更多相关《《散列表的设计与实现》课程设计说明书.docx（12页珍藏版）》请在冰点文库上搜索。
《散列表的设计与实现》课程设计说明书
届课程设计
《散列表的设计与实现》
设计说明书
学生姓名
学号
所属学院信息工程学院
专业计算机科学与技术
班级计算机
指导教师
教师职称讲师
塔里木大学教务处制
目录
前言1
1.1设计背景和意义1
1.1.1数据结构简介1
1.1.2选择算法的原因1
1.2设计的原理和内容1
正文1
2.1设计的目的和意义2
2.2目标和总体方案2
2.3设计方法和内容2
2.3.1硬件环境2
2.3.2软件环境3
2.3.3设计内容3
2.3.4设计流程图4
2.4设计创新与关键技术6
2.5结论6
2.5.1存在的问题6
2.5.2解决方案7
参考文献9
程序的设计思想和内容10
3.1程序设计的初始运行环境10
3.2散列表的初始化10
3.3数据的插入13
3.4数据元素的查找14
3.5数据的删除15
3.6数据的合并16
3.7完成17
前言
1.1设计背景和意义
1.1.1数据结构简介
数据结构是计算机程序设计的重要理论设计基础，是一门综合性的专业基础科。
数据结构是研究数据之间的相互关系，也即数据的组织形式的一门科学。
它不仅是计算机学科的核心课程，数据结构是计算机存储、组织数据的方式。
通常情况下，精心选择的数据结构可以带来更高的运行或者存储效率的算法。
在计算机科学中，“数据结构”不仅是一般程序设计的基础，而且是设计和实现编译程序、操作系统、数据库系统及其他系统程序和大型应用程序的重要基础。
1.1.2选择算法的原因
在许多类型的程序的设计中，数据结构的选择是一个基本的设计考虑因素。
许多大型系统的构造经验表明，系统实现的困难程度和系统构造的质量都严重的依赖于是否选择了最优的数据结构。
许多时候，确定了数据结构后，算法就容易得到了。
有些时候事情也会反过来，我们根据特定算法来选择数据结构与之适应。
不论哪种情况，选择合适的数据结构都是非常重要的。
1.2设计的原理和内容
本次程序设计采用C语言作为描述和实现操作的程序语言，主要的设计思路就是完成对单链表的实现的操作，如链表的插入、删除操作，这些操作都是通过C语言程序来实现的。
最后的结果就是运行程序时能够完成对以上设计的操作。
正文
散列表的链式存储结构的特点是用一组任意的存储单元存储线性表的数据元素（这组存储单元可以是连续的，也可以是不连续的）。
它包括两个域：
其中存储数据元素信息的域称为数据域；存储直接后继存储位置的域称为指针域。
指针域中存储的信息称作指针或链。
n个结点链结成一个链表，即为线性表的链式存储结构。
又由于次链表的每个结点中只包含一个指针域，故又称哈希表或散列表。
2.1设计的目的和意义
我们是计算机科学与技术专业的本科生，《数据结构》是我们重要的必修课程。
当代社会学要大学培养出理论扎实，动手实践能力强的大学生。
所以，本次课程设计的目的就在于通过一次实践性的活动加深对这门课程的理解，使我们在感性的认识上进一步升华为理性的认识。
为后继课程的学习打下坚实的基础。
通过本次数据结构课程设计，我们基本上掌握了课设流程，还掌握了一些知识和技能，这对于我们以后对于数据结构的学习有了很大的帮助和提高，加深了我们对链表的理解，对数据结构的了解，为今后的学习打下了坚实的基础。
同时也提高了我们对于编程这方面的能力。
2.2目标和总体方案
本次设计的目标在于将单链表的这一特殊的访问规则和特殊的操作用程序语言形象地再现和描述出来。
于是特制订了一个总体的方案。
由于时间只有七天，所以在有限的时间内，我做了如下的计划安排，将这项工程分为两大部分：
程序的设计和程序的调试。
首先在程序的设计部分分为几个步骤：
第一步：
查阅有关数据结构散列表操作的资料，用半天的时间。
第二步：
设计这个项目的整体架构和算法。
用一到两天的时间。
第三步：
选择一门程序设计语言进行算法的描述。
两天的时间。
其次，进行程序的调试。
用一天。
最后，我在完整的整理一遍，完成课设。
2.3设计方法和内容
“工欲善其事，必先利其器”。
有了总体方案后必须用一个事半功倍的设计方法来提高程序设计的效率。
在这个项目的设计上，笔者选择了Ｃ语言作为算法的描述语言，因为Ｃ语言具有丰富的表达能力以及代码的高效性，并且有着良好的移植性和灵活性。
同时，采用“自顶向下，个个击破”的程序设计思路和思想，充分运用Ｃ语言强大的功能。
笔者将这个项目整体设分成了两个模块。
一个是功能函数模块群，主要实现设计方案中的具体功能，是整个项目的执行部分；另一个是主函数模块，主要实现对数据流和控制流的控制，使整个项目的控制部分。
这两大模块有机的结合共同构成了这个项目的全部面貌。
2.3.1硬件环境
微型计算机：
方正台式品牌机
中央处理器：
Pentuim4主频：
3.0GHz
主存容量：
512M
硬盘容量：
80G
2.3.2软件环境
WindowsXP操作系统
MicrosoftNotePad记事本程序
MicrosoftVisualC++编译器
2.3.3设计内容
一、程序设计的基本算法介绍
1、散列表，是用一组任意的存储单元存储线性表元素的一种数据结构。
2、单链表的基本操作:
（1）InitList（&L）：
构造一个空的散列表L。
（2）DestroyList（&L）：
销毁散列表L。
（3）ClearList（&L）:
将L重置为空表。
（4）ListLength（L）:
返回L中数据元素个数。
（5）GetElen（L，i，&e）：
用e返回L中第i个数据元素的值。
（6）ListInsert（&L，i，e）：
在L中第i个位置之前插入新的数据元素e，L的长度加1。
（7）ListDelete（&L，i，&e）：
删除L的第i个元素，并用e返回其值，L的长度减1.
二、程序中涉及的基本算法
线性表的顺序村结构的特点是为表中相邻的的元素ai和ai+1赋以相邻的存储位置。
也就是说，一元素在计算机内“物理位置相邻”来表示线性表中数据元素之间的逻辑关系。
1、散列表的插入操作算法
在散列表的第i-1个数据元素和第i个数据元素之间插入一个新的数据元素，就是要使长度为n的散列表（a1，…,ai-1，ai，…,an）变成长度为n+1的散列表（a1，…,ai-1，b，ai，…，an）数据元素ai-1和ai之间的逻辑关系发生了变化。
一般情况下，在第i（1≤i≤n）个元素之前插入一个元素时，需要将第n至第i（共n-i+1）个元素向后移动一个位置。
2、散列表的删除操作算法
长度为n的散列表（a1,…,ai-1,ai,ai+1,…,an）变成长度为n-1的散列表（a1,…,ai-1,ai+1,…,an）数据元素ai-1、ai和ai+1之间的逻辑关系发生变化，在存储结构上要反映这个变化，就必须需要移动元素。
一般情况，要删除第i（1≤i≤n）个元素时需要将从第n（共n-i）个元素一次向前移动一个位置。
2.3.4设计流程图
以号码为关键字的hash函数流程图
添加信息节点流程图
2.4设计创新与关键技术
这个课程设计是一个简单的设计，如果说有“设计创新与关键技术”的话，只能勉强说有设计创新，至于关键技术应该谈不上。
因为个人目前能力有限，学的东西还不太多，出了上课老师讲解之外，平时在图书馆也看到一些课堂上以外的知识，所以仅凭借在图书馆自学还是远远不够的，要与老师上课讲的相结合，才能达到圆满效果，才能更好的突出创新。
本次课设虽然简单，但是完成了，完成了自己定制的方案。
谈到设计创新，只能说在设计思路、设计方法和设计内容上有别人没有的东西。
而所用的技术倒是没有多少。
主要是运用了C语言丰富的表达能力，实现了对课程设计的要求。
2.5结论
本次设计进展顺利，如期完成，并且达到了预先的设计要求，完全贯彻和执行了设计的总体方案。
对于单链表的实现操作比较成功。
然而，限于时间和水平，这个设计还有很多的不足之处，所以了解到了自己的不足之处，自己以后就有了动力，有了方向，。
通过这次课程设计，让我深深了解到了C语言的魅力所在，了解到了它庞大的一面。
让我意识到了学好这门语言是多么得重要，这对于我们计算机专业的同学来说，是一门基础课，树木之所以长那么高大，全是因为根基很牢，根扎得很深，高层楼之所以如此高，是因为地基很深、很牢。
所以，为了更好更有效地学好这们语言，学好数据结构，我们就得以根基为主，把这门基础课上好，给以后的路打下坚实的基础。
2.5.1存在的问题
没有使用图形的形式描述散列表的操作。
主要是因为本设计主要是在MicroSoftVisualC++编译器调试，但VC的根目录下的Include文件夹中没有graphics.h这个头文件。
因此，在TurboC下编译成功的地源程序在VC中无法编译通过。
另外，所有的对散列表的操作只能当单链表被初始化以后方可进行。
冲突是如何产生的？
上文中谈到，哈希函数是指如何对关键字进行编址的规则，这里的关键字的范围很广，可视为无限集，如何保证无限集的原数据在编址的时候不会出现重复呢？
规则本身无法实现这个目的。
2.5.2解决方案
通常有两类方法处理冲突：
开放定址（OpenAddressing）法和拉链（Chaining）法。
前者是将所有结点均存放在散列表T[0..m-1]中；后者通常是将互为同义词的结点链成一个单链表，而将此链表的头指针放在散列表T[0..m-1]中。
1、开放定址法
（1）开放地址法解决冲突的方法
用开放定址法解决冲突的做法是：
当冲突发生时，使用某种探查（亦称探测）技术在散列表中形成一个探查（测）序列。
沿此序列逐个单元地查找，直到找到给定的关键字，或者碰到一个开放的地址（即该地址单元为空）为止（若要插入，在探查到开放的地址，则可将待插入的新结点存人该地址单元）。
查找时探查到开放的地址则表明表中无待查的关键字，即查找失败。
开放地址法的一般形式
开放定址法的一般形式为：
hi=（h（key）+di）％m1≤i≤m-1
其中：
①h（key）为散列函数，di为增量序列，m为表长。
②h（key）是初始的探查位置，后续的探查位置依次是hl，h2，…，hm-1，即h（key），hl，h2，…，hm-1形成了一个探查序列。
③若令开放地址一般形式的i从0开始，并令d0=0，则h0=h（key），则有：
hi=（h（key）+di）％m0≤i≤m-1
探查序列可简记为hi（0≤i≤m-1）。
（3）开放地址法堆装填因子的要求
开放定址法要求散列表的装填因子α≤l，实用中取α为0.5到0.9之间的某个值为宜。
（4）形成探测序列的方法
按照形成探查序列的方法不同，可将开放定址法区分为线性探查法、二次探查法、双重散列法等。
①线性探查法（LinearProbing）
该方法的基本思想是：
将散列表T[0..m-1]看成是一个循环向量，若初始探查的地址为d（即h（key）=d），则最长的探查序列为：
d，d+l，d+2，…，m-1，0，1，…，d-1
即:
探查时从地址d开始，首先探查T[d]，然后依次探查T[d+1]，…，直到T[m-1]，此后又循环到T[0]，T[1]，…，直到探查到T[d-1]为止。
探查过程终止于三种情况：
（1）若当前探查的单元为空，则表示查找失败（若是插入则将key写入其中）；
（2）若当前探查的单元中含有key，则查找成功，但对于插入意味着失败；
（3）若探查到T[d-1]时仍未发现空单元也未找到key，则无论是查找还是插入均意味着失败（此时表满）。
利用开放地址法的一般形式，线性探查法的探查序列为：
hi=（h（key）+i）％m0≤i≤m-1//即di=i
利用线性探测法构造散列表
2、拉链法
（1）拉链法解决冲突的方法
拉链法解决冲突的做法是：
将所有关键字为同义词的结点链接在同一个单链表中。
若选定的散列表长度为m，则可将散列表定义为一个由m个头指针组成的指针数组T[0..m-1]。
凡是散列地址为i的结点，均插入到以T[i]为头指针的单链表中。
T中各分量的初值均应为空指针。
在拉链法中，装填因子α可以大于1，但一般均取α≤1。
（2）拉链法的优点
与开放定址法相比，拉链法有如下几个优点：
（1）拉链法处理冲突简单，且无堆积现象，即非同义词决不会发生冲突，因此平均查找长度较短；
（2）由于拉链法中各链表上的结点空间是动态申请的，故它更适合于造表前无法确定表长的情况；
（3）开放定址法为减少冲突，要求装填因子α较小，故当结点规模较大时会浪费很多空间。
而拉链法中可取α≥1，且结点较大时，拉链法中增加的指针域可忽略不计，因此节省空间；
（4）在用拉链法构造的散列表中，删除结点的操作易于实现。
只要简单地删去链表上相应的结点即可。
而对开放地址法构造的散列表，删除结点不能简单地将被删结点的空间置为空，否则将截断在它之后填人散列表的同义词结点的查找路径。
这是因为各种开放地址法中，空地址单元（即开放地址）都是查找失败的条件。
因此在用开放地址法处理冲突的散列表上执行删除操作，只能在被删结点上做删除标记，而不能真正删除结点。
（3）拉链法的缺点
拉链法的缺点是：
指针需要额外的空间，故当结点规模较小时，开放定址法较为节省空间，而若将节省的指针空间用来扩大散列表的规模，可使装填因子变小，这又减少了开放定址法中的冲突，从而提高平均查找速度。
2.5.3调试的结果
这个项目是由主函数模块和功能函数模块组成的。
其中主函数模块是项目的控制部分，很重要的一个作用就是对整个程序的初始化功能。
在设计初始运行环境时，为了每一次操作后都可以进行对程序的初始化，采用了do…while循环语句构成一个无限循环，使得每一次对数据操作之后都可以将程序初始化重新选择对数据的另一个操作，例如：
选择1，插入一个数据元素之后，程序便又回到了初始的界面，我们可以选择3进行删除操作。
选择4进行合并操作。
具体运行截面如下图：
图3-2界面的初始化
参考文献
[1]严蔚敏.吴伟民编著.数据结构（C语言版）.清华大学出版社.2006
[2]李春葆.曾慧.张植民编著.数据结构程序设计题典.清华大学出版社.2002
[3]郭翠英等编著.C语言课程设计案例精编.中国水利水电出版社.2004
[4]谭浩强编著.C程序设计.清华大学出版社.2005
[5]许卓群.张乃孝.杨冬青.唐世渭《数据结构》.高等教育出版社.1988年
[6]晋良颍《数据结构》.人民邮电出版社.2002年
升级会员 