哈希表是一种高效的数据结构。本文分五个部分：首先提出了哈希表的优点，其次介绍了它的基础操作，接着从简单的例子中作了效率对比，指出其适用范围以及特点，然后通过例子说明了如何在题目中运用哈希表以及需要注意的问题，最后总结全文。
[正文]. 引言
哈希表（）的应用近两年才在中出现，作为一种高效的数据结构，它正在竞赛中发挥着越来越重要的作用。
哈希表最大的优点，就是把数据的存储和查找消耗的时间大大降低，几乎可以看成是常数时间；而代价仅仅是消耗比较多的内存。然而在当前可利用内存越来越多的情况下，用空间换时间的做法是值得的。另外，编码比较容易也是它的特点之一。
哈希表又叫做散列表，分为"开散列" 和"闭散列"。考虑到竞赛时多数人通常避免使用动态存储结构，本文中的"哈希表"仅指"闭散列"，关于其他方面读者可参阅其他书籍。
. 基础操作基本原理
我们使用一个下标范围比较大的数组来存储元素。可以设计一个函数（哈希函数，也叫做散列函数），使得每个元素的关键字都与一个函数值（即数组下标）相对应，于是用这个数组单元来存储这个元素；也可以简单的理解为，按照关键字为每一个元素"分类"，然后将这个元素存储在相应"类"所对应的地方。
但是，不能够保证每个元素的关键字与函数值是一一对应的，因此极有可能出现对于不同的元素，却计算出了相同的函数值，这样就产生了"冲突"，换句话说，就是把不同的元素分在了相同的"类"之中。后面我们将看到一种解决"冲突"的简便做法。
总的来说，"直接定址"与"解决冲突"是哈希表的两大特点。
函数构造
构造函数的常用方法（下面为了叙述简洁，设 () 表示关键字为的元素所对应的函数值）：
) 除余法：
选择一个适当的正整数，令 ( )
这里，如果选取的是比较大的素数，效果比较好。而且此法非常容易实现，因此是最常用的方法。
) 数字选择法：
如果关键字的位数比较多，超过长整型范围而无法直接运算，可以选择其中数字分布比较均匀的若干位，所组成的新的值作为关键字或者直接作为函数值。
冲突处理
线性重新散列技术易于实现且可以较好的达到目的。令数组元素个数为，则当 () 已经存储了元素的时候，依次探查 (()) , ……，直到找到空的存储单元为止（或者从头到尾扫描一圈仍未发现空单元，这就是哈希表已经满了，发生了错误。当然这是可以通过扩大数组范围避免的）。
支持运算
哈希表支持的运算主要有：初始化()、哈希函数值的运算(())、插入元素()、查找元素()。
设插入的元素的关键字为，为存储的数组。
初始化比较容易，例如
; 用非常大的整数代表这个位置没有存储元素
; 表的大小
;
;
[];
;
哈希函数值的运算根据函数的不同而变化，例如除余法的一个例子：
();
;
;
我们注意到，插入和查找首先都需要对这个元素定位，即如果这个元素若存在，它应该存储在什么位置，因此加入一个定位的函数
();
;
();
;
(<)([() ]<>)([() ]<>)
();
当这个循环停下来时，要么找到一个空的存储单元，要么找到这个元
素存储的单元，要么表已经满了
() ;
;
插入元素
();
;
(); 定位函数的返回值
[] []
; 即为发生了错误，当然这是可以避免的
;
查找元素是否已经在表中
();
;
();
[]
;
;
这些就是建立在哈希表上的常用基本运算。
下文提到的所有程序都能在附录中找到。
. 效率对比简单的例子与实验
下面是一个比较简单的例子：
集合 ( ) 问题描述：
给定两个集合、，集合内的任一元素满足≤ ≤ ，并且每个集合的元
素个数不大于个。我们希望求出、之间的关系。只需确定在中但是不在中的元素的个数即可。（这个题目是根据模拟赛的第一题改编的。）
分析：我们先不管与的具体关系如何，注意到这个问题的本质就是对于给定的集合，确定中的元素是否在中。所以，我们使用哈希表来处理。至于哈希函数，只要按照除余法就行了，由于故意扩大了原题的数据规模， () ;
当然本题可以利用别的方法解决，所以选取了速度最快的快速排序二分查
找，让这两种方法作效率对比。
我们假定，对于随机生成的数据，计算程序重复运行次所用时间。
对比表格如下：
哈希表（）快速排序二分查找()
复杂度() (只有忽略了冲突才是这个结果。当然
实际情况会比这个大，但是重复的几率与
哈希函数有关，不容易估计)
( ) ( )
测试数据规
模
对于数据的说明：在下用测试，为了使时间的差距明显，让程序重复运了行次。同时哈希表中的，下标范围。由于快速排序不稳定，因此使用了随机
数据。
．对实验结果的分析：
注意到两个程序的用时并不像我们期望的那样，总是哈希表快。设哈希表
的大小为 .
首先，当规模比较小的时候（大约为< * ，这个数据仅仅是通过若干数据估记出来的，没有严格证明，下同），第二种方法比哈希表快。这是由于，虽然每次计算哈希函数用() 的时间，但是这个系数比较大。例如这道题的 () ，通过与做同样次数的加法相比较，测试发现系数 > ，因为运算本身与快速排序的比较大小和交换元素运算相比，比较费时间。所以规模小的时候，()（忽略冲突）的算法反而不如 ()。这一点在更复杂的哈希函数上会体现的更明显，因
为更复杂的函数系数会更大。
其次，当规模稍大（大约为 * < < *）的时候，很明显哈希表的效率高。
这是因为冲突的次数较少。
再次，当规模再大（大约为 * < < ）的时候，哈希表的效率大幅下降。这是因为冲突的次数大大提高了，为了解决冲突，程序不得不遍历一段都存储了元素的数组空间来寻找空位置。用白箱测试的方法统计，当规模为的时候，为了找空位置，线性重新散列平均做了次运算；而当规模为的时候，平均竟然高达次运算，某些数据甚至能达到次。显然浪费这么多次运算来解决冲突是不合算的，
解决这个问题可以扩大表的规模，或者使用"开散列"（尽管它是动态数据结构）。
然而需要指出的是，冲突是不可避免的。
初步结论：
当数据规模接近哈希表上界或者下界的时候，哈希表完全不能够体现高效的特点，甚至还不如一般算法。但是如果规模在中央，它高效的特点可以充分体现。我们可以从图像直观的观察到这一点。
实验表明当元素充满哈希表的的时候，效率就已经开始明显下降。这就给了我们提示：如果确定使用哈希表，应该尽量使数组开大（由于竞赛中可利用内存越来越多，大数组通常不是问题，当然也有少数情况例外），但对最太大的数组进行操作也比较费时间，需要找到一个平衡点。通常使它的容量至少是题目最大需求的，效果比较好（这个仅仅是经验，没有严格证明）。
. 应用举例应用的简单原则
什么时候适合应用哈希表呢？如果发现解决这个问题时经常要询问："某个元素是否在已知集合中？"，也就是需要高效的数据存储和查找，则使用哈希表是最好不过的了！那么，在应用哈希表的过程中，值得注意的是什么呢？
哈希函数的设计很重要。一个不好的哈希函数，就是指造成很多冲突的情况，从前面的例子已经可以看出来，解决冲突会浪费掉大量时间，因此我们的目标就是尽力避免冲突。前面提到，在使用"除余法"的时候，() ，最好是一个大素数。这就是为了尽力避免冲突。为什么呢？假设，则哈希函数分类的标准实际上就变成了按照末三位数分类，这样最多类，冲突会很多。一般地说，如果的约数越多，那么冲突的几率就越大。
简单的证明：假设是一个有较多约数的数，同时在数据中存在满足() > ，即有 * , *, 则有* [ ] *[ ] . ① 其中 [ ] 的取值范围是不会超过 [，] 的正整数。也就是说， [ ] 的值只有种可能，而是一个预先确定的数。因此① 式的值就只有种可能了。这样，虽然运算之后的余数仍然在 [，] 内，但是它的取值仅限于① 可能取到的那些值。也就是说余数的分布变得不均匀了。容易看出，的约数越多，发生这种余数分布不均匀的情
况就越频繁，冲突的几率越高。而素数的约数是最少的，因此我们选用大素数。记住"素数是我们的得力助手"。
另一方面，一味的追求低冲突率也不好。理论上，是可以设计出一个几乎完美，几乎没有冲突的函数的。然而，这样做显然不值得，因为这样的函数设计很浪费时间而且编码一定很复杂，与其花费这么大的精力去设计函数，还不如用一个虽然冲突多一些但是编码简单的函数。因此，函数还需要易于编码，即易于实现。
综上所述，设计一个好的哈希函数是很关键的。而"好"的标准，就是较低的冲突率和易于实现。
另外，使用哈希表并不是记住了前面的基本操作就能以不变应万变的。有的时候，需要按照题目的要求对哈希表的结构作一些改进。往往一些简单的改进就可以带来巨大的方便。
这些只是一般原则，真正遇到试卷的时候实际情况千变万化，需要具体问题具体分析才行。下面，我们看几个例子，看看这些原则是如何体现的。
有关字符串的例子
我们经常会遇到处理字符串的问题，下面我们来看这个例子：
找名字问题描述：
给定一个全部由字符串组成的字典，字符串全部由大写字母构成。其中为每个字符串编写密码，编写的方式是对于位字符串，给定一个位数，大写字母与数字的对应方式按照电话键盘的方式：
: : :
: : :
: :
题目给出一个位的数，找出在字典中出现且密码是这个数的所有字符串。
字典中字符串的个数不超过。（这个是的一道题。）
分析：看懂题目之后，对于给定的编码，只需要一个回溯的过程，所有可能的原字符串都可以被列举出来，剩下的就是检查这个字符串是否在给定的字典中了。所以这个问题需要的还是"某个元素是否在已知集合中？"由于给出的"姓名"都是字符串，因此我们可以利用字符的码。那么，如何设计这个哈希函数呢？注意到题目给出的字典中，最多能有个不同元素，而一个字符的码只能有种不同的取值，因此至少需要用在个位置上的字符（^ > ，但是 ^ < ），于是我们就选取个位置上的字符。由于给定的字符串的长度从都有可能，为了容易实现，选取最开始的个字符，和最末尾的个字符。让这个字符组成进制的位
数，则这个数的值就是这个字符串的编码。这样哈希函数就设计出来了！
不过，由于可能出现只有位的字符串，在写函数代码的时候需要特殊考虑；
大素数选取。
这个函数是这样的：
();
;
; {用来记录进制数的值}
()>
*([]);
*([()]); {取第一位和后两位}
*([]);{当长度为的时候特殊处理}
;
;
值得指出的是，本题给出的字符串大都没有什么规律，用哈希表可以做到近似"平均"，但是对于大多数情况，字符串是有规律的（例如英文单词），这个时
候用哈希表反而不好（例如英语中有很多以开头的单词），通常用检索树解决
这样的查找问题。
在广度优先搜索中应用的例子
在广度优先搜索中，一个通用而且有效的剪枝就是在拓展节点之前先判重。而判重的本质也是数据的存储与查找，因此哈希表大有用武之地。来看下面的例
子：
转花盆题意描述:
给定两个正边形的花坛，要求求出从第一个变化到第二个的最小操作
次数以及操作方式。一次操作是：选定不在边上的一盆花，将这盆花周围的盆花
按照顺时针或者逆时针的顺序依次移动一个单位。限定一个花坛里摆放的不同种
类的花不超过种，对于任意两种花，数量多的花的盆数至少是数量少的花的倍。
（这是的一道题）
分析：首先确定本题可以用广度优先搜索处理，然后来看问题的规模。正边形
共有个格子可以用来放花，而且根据最后一句限定条件，至多只能存在 () * () 种状态，用搜索完全可行。然而操作的时候，可以预料产生的重复节点是相当多的，需要迅速判重才能在限定时间内出解，因此想到了哈希表。那么这个哈希函
数如何设计呢？注意到个格子组成边形是有顺序的，而且每一个格子只有种可能
情况，那么用进制位数最大 ^ 用完全可以承受。于是我们将每一个状态与一
个整数对应起来，使用除余法就可以了。
小结
从这两个例子可以发现，对于字符串的查找，哈希表虽然不是最好的方法，但是每个字符都有"天生"的码，在设计哈希函数的时候可以直接利用。而其他方法，例如利用检索树的查找，编写代码不如哈希表简洁。至于广度优先搜索中
的判重更是直接利用了哈希表的特点。
另外，我们看到这两个题目都是设计好哈希函数之后，直接利用前面的基本操作就可以了，因此重点应该是在哈希函数的设计上（尽管这两个例子的设计都很简单），需要注意题目本身可以利用的条件，以及估计值域的范围。下面我们看两个需要在哈希表基础上作一些变化的例子。
需要微小变化的例子
下面，我们来分析一道的试卷：
方
程的解数问题描述
已知一个元高次方程：
其中：是未知数，是系数，是指数。且方程中的所有数均为整数。
假设未知数≤ ≤, ，求这个方程的整数解的个数。
约束条件
≤≤；≤≤；
方程的整数解的个数小于。
本题中，指数(,……)均为正整数。
这个是的第二试中的《方程的解数》。
分析：初看此题，题目要求出给定的方程解的个数，这个方程在最坏的情况下可以有个未知数，而且次数由输入决定。这样就不能利用数学方法直接求出解
的个数，而且注意到解的范围最多个数，因此恐怕只能使用枚举法了。最简单的思路是穷举所有未知数的取值，这样时间复杂度是 (^) ，无法承受。因此我们需要寻找更好的方法，自然想到能否缩小枚举的范围呢？但是发现这样也有很大的困难。我们再次注意到的范围，若想不超时，似乎算法的复杂度上限应该是 (^) 左右，这是因为 ^ < 。这就启示我们能否仅仅通过枚举个未知数的值来找到答案呢？如果这样，前一半式子的值可以确定，这时只要枚举后个数的值，检查他们的和是否等于即可。这样只相当于在 (^) 前面加了一个系数，当然还需要预先算出到的各个幂次的值。想到了这里，问题就是如何迅速的找到某个是否曾经出现过，以及出现过了多少次，于是又变成了"某个元素是否在给定集合中"这个问题。所以，我们还是使用哈希表解决这个问题。至于哈希函数不是问题，还是把的值作为关键字使用除余法即可。然而有一点需要注意，这个例子我们不仅需要纪录某个是否出现，出现的次数也很重要，所以可以用一个维数组，仅仅是加了一个存储出现次数的域而已。
[] ; {[] 记录哈希函数值为的值， [] 记录这个值出现了几次}
因此过程也需要一些变化：
();
;
();
[];
([]); {仅仅这一条语句，就可以记录下来出现了几次} ;
最后一个例子
下面我们来仔细分析下面这个问题：
迷宫
的墙题意描述:
神话中山边有一个井之迷宫。迷宫的入口在山顶。迷宫中有许多房间，每个的颜色是以下之一：红、绿、蓝。两个相同颜色的房间看起来相似而不可区分。每个房间里有三口井标以。从一个房间到另一间只有一种方式：从上面房间的井里跳到（不一定竖直地）井底的房间。可以从入口房间到达任何其他房间。迷宫中的所有通路走向坐落在最底部的龙宫。所有的迷宫之旅对应了一系列在相继访问的房间里选择的井的标号。这一列数称为一个旅行计划。一个走过好几次迷宫的英雄画好了图，然而有的房间重复出现了多次。
输入：
第一行有一个整数<<，房间数（包括龙宫）。房间从１到标号，较大编号的房间再较低处（入口房间编号１，龙宫编号）。接下的行描述迷宫的房间（除
了龙宫）和井。每行有一个字母，一个空格，和三个由空格分隔的整数。字母代表了房间的颜色（红，绿，蓝），第()个数是第个井通往的房间号。
输出：
迷宫最少的房间数目
这是中国国家集训队难题讨论活动的题。
分析：题目的意思是给出这个迷宫的地图，去掉重复出现的房间，找出这个迷宫的最少房间数目。于是关键就是确定什么样的房间是重复的。通过对样例的分析，可以看出这样的房间是重复的：如果两个房间和（< <），他们的颜色相同，而且第 () 堵墙通向的房间或者相同、或者重复。因为这样从和可到达的房间是完全相同的。
所以，我们只需要记录下每个房间的情况和已经被确定相同的房间，然后挨个比较即可。于是又需要用到高效的数据存储与查找，自然想到哈希表。然而，这里面需要对哈希表作更大的改进：首先每个房间只能是种颜色之一，因此针对每种颜色分别建立哈希表，可以使哈希函数的自变量减少一个；其次还需要纪录每个不重复的房间每堵墙都通向哪个房间，还有哪些房间是重复的。
具体这样实现：
[] ; { 代表共有种颜色，是哈希函数的值域，而中的表示三堵墙连接到那个房间，表示这个单元存储的是哪个节点}
[] ; {[] 表示与相同的节点。如果有多个节点都是相同的，择取其中最大的（这一点不需要特殊的操作，只要在处理节点的时候注意就行了）}
至于哈希函数，最开始我是随意的写了一个（因为越是随意的，就越是随机的！），定位函数是这样的：
( );
;
;
[]*[]*[]*; {用堵墙的值任意乘大素数相加再取余数，使得结果分布比较随机，也就比较均匀}
;
;
([,() ]<>)([,() ]<>[])
([,() ]<>[])([,() ]<>[]) (); {线性重新散列}
() ;
;
但是后来发现完全没有必要这样做，这样的哈希函数在计算的时候浪费了很多时间（不过数据规模不是很大，所以这点不十分明显），而且素数起到的作用也不应当是这样的。其实让 [][][] 组成进制数就完全能够达到目的了，加入了素数不仅是小规模数据计算浪费时间，对大数据最后结果的分布平均也没有起到比进制数更多的作用。因此改为
[]*()[]*[];
当然肯定会有更好的哈希函数的。
小结
第一个例子，乍一看与哈希表毫无关系；第二个例子叙述比较复杂，但是经过仔细分析，发现问题的本质都是确定"某个元素是否在给定集合中"，这正是哈希表的特点。所以，不论题目的表面看起来如何，只要本质是需要高效的数据检索，哈希表通常就是最好的选择！
另外，这两个例子都在原来哈希表的基础上作了一些变化。第一个例子加入了纪录某个值出现次数的域，第二个例子加入了纪录所有墙的情况以及原节点编号的域。虽然都只是很小的变化，但是却给问题的解决带来了不小的方便。因此我们得到提示：哈希表虽然有标准的操作，但也不是一成不变的，需要具体问题具体分析，根据题目的要求和特点作出相应变化。
一，实验题目 实验十一：图实验 采用邻接表存储有向图，设计算法判断任意两个顶点间手否存在路径。 二，问题分析 本程序要求采用邻接表存储有向图，设计算法判断任意两个顶点间手否存在路径，完成这些操作需要解决的关键问题是：用邻接表的形式存储有向图并输出该邻接表。用一个函数实现判断任意两点间是否存在路径。 1，数据的输入形式和输入值的范围：输入的图的结点均为整型。 2，结果的输出形式：输出的是两结点间是否存在路径的情况。 3，测试数据：输入的图的结点个数为：4 输入的图的边得个数为：3 边的信息为：1 2，2 3，3 1 三，概要设计 （1）为了实现上述程序的功能，需要： A，用邻接表的方式构建图 B，深度优先遍历该图的结点 C，判断任意两结点间是否存在路径 （2）本程序包含6个函数： a，主函数main（） b，用邻接表建立图函数create_adjlistgraph() c，深度优先搜索遍历函数dfs() d，初始化遍历数组并判断有无通路函数dfs_trave() e，输出邻接表函数print() f，释放邻接表结点空间函数freealgraph() 各函数间关系如右图所示： 四，详细设计 （1）邻接表中的结点类型定义：
typedef struct arcnode{ int adjvex; arcnode *nextarc; }arcnode; （2）邻接表中头结点的类型定义： typedef struct{ char vexdata; arcnode *firstarc; }adjlist; （3）邻接表类型定义： typedef struct{ adjlist vextices[max]; int vexnum,arcnum; }algraph; （4）深度优先搜索遍历函数伪代码： int dfs(algraph *alg,int i,int n){ arcnode *p; visited[i]=1; p=alg->vextices[i].firstarc; while(p!=NULL) { if(visited[p->adjvex]==0){ if(p->adjvex==n) {flag=1; } dfs(alg,p->adjvex,n); if(flag==1) return 1; } p=p->nextarc; } return 0; } （5）初始化遍历数组并判断有无通路函数伪代码： void dfs_trave(algraph *alg,int x,int y){ int i; for(i=0;i<=alg->vexnum;i++) visited[i]=0; dfs(alg,x,y); } 五，源代码 #include "stdio.h" #include "stdlib.h" #include "malloc.h" #define max 100 typedef struct arcnode{ //定义邻接表中的结点类型 int adjvex; //定点信息 arcnode *nextarc; //指向下一个结点的指针nextarc }arcnode; typedef struct{ //定义邻接表中头结点的类型 char vexdata; //头结点的序号 arcnode *firstarc; //定义一个arcnode型指针指向头结点所对应的下一个结点}adjlist; typedef struct{ //定义邻接表类型 adjlist vextices[max]; //定义表头结点数组
实验三二叉树的遍历 一、实验目的 １、熟悉二叉树的结点类型和二叉树的基本操作。 ２、掌握二叉树的前序、中序和后序遍历的算法。 3、加深对二叉树的理解，逐步培养解决实际问题的编程能力。 二、实验环境 运行Ｃ或VC++的微机。 三、实验内容 1、依次输入元素值，以链表方式建立二叉树，并输出结点的值。 2、分别以前序、中序和后序遍历二叉树的方式输出结点内容。 四、设计思路 1. 对于这道题，我的设计思路是先做好各个分部函数，然后在主函数中进行顺序排列，以此完成实验要求 2．二叉树采用动态数组 3.二叉树运用9个函数，主要有主函数、构建空二叉树函数、建立二叉树函数、访问节点函数、销毁二叉树函数、先序函数、中序函数、后序函数、范例函数，关键在于访问节点 五、程序代码 #include
int data; //数据域 struct TNode *lchild,*rchild; // 指针域包括左右孩子指针 }TNode,*Tree; void CreateT(Tree *T)//创建二叉树按,依次输入二叉树中结点的值 { int a; scanf("%d",&a); if(a==00) // 结点的值为空 *T=NULL; else // 结点的值不为空 { *T=(Tree)malloc(sizeof(TNode)); if(!T) { printf("分配空间失败！！TAT"); exit(ERROR); } (*T)->data=a; CreateT(&((*T)->lchild)); // 递归调用函数，构造左子树 CreateT(&((*T)->rchild)); // 递归调用函数，构造右子树 } } void InitT(Tree *T)//构建空二叉树 { T=NULL; } void DestroyT(Tree *T)//销毁二叉树 { if(*T) // 二叉树非空 { DestroyT(&((*T)->lchild)); // 递归调用函数，销毁左子树 DestroyT(&((*T)->rchild)); // 递归调用函数，销毁右子树 free(T); T=NULL; } } void visit(int e)//访问结点 { printf("%d ",e); }
图实验一，邻接矩阵的实现 1.实验目的 （1）掌握图的逻辑结构 （2）掌握图的邻接矩阵的存储结构 （3）验证图的邻接矩阵存储及其遍历操作的实现 2.实验内容 （1）建立无向图的邻接矩阵存储 （2）进行深度优先遍历 （3）进行广度优先遍历 3．设计与编码 MGraph.h #ifndef MGraph_H #define MGraph_H const int MaxSize = 10;
template
#include
实验报告 姓名：学号： 1．实验题目 针对某个集体中人名设计一个哈希表，使得平均查找长度不超过R，并完成相应的建表和查表程序。 基本要求：假设人名为中国人姓名的汉语拼音形式。待填入哈希表的人名共有30个，取平均查找长度的上限为2。哈希函数用除留余数法构造，用线性探测再散列法或链地址法处理冲突。 2．需求分析 本演示程序用VC编写，完成哈希函数用除留余数法构造，用线性探测再散列法或链地址法处理冲突。 输出形式：地址，关键字，收索长度，H（key），拼音 3.概要设计 typedef struct NAME typedef struct hterm void InitNameList() void CreateHashList() void FindList() void Display() int main() 4．详细设计 #include
#define HASH_LEN 50 #define M 47 #define NAME_NO 8 typedef struct NAME { char *py; //名字的拼音 int k; //拼音所对应的整数}NAME; NAME NameList[HASH_LEN]; typedef struct hterm //哈希表{ char *py; //名字的拼音 int k; //拼音所对应的整数int si; //查找长度 }HASH; HASH HashList[HASH_LEN]; void InitNameList() { NameList[0].py="houxinming"; NameList[1].py="abc"; NameList[2].py="defdgf"; NameList[3].py="zhangrji"; NameList[4].py="jiaxin"; NameList[5].py="xiaokai"; NameList[6].py="liupeng"; NameList[7].py="shenyonghai";
邻接矩阵的实现 1. 实验目的 （1）掌握图的逻辑结构 （2）掌握图的邻接矩阵的存储结构 （3）验证图的邻接矩阵存储及其遍历操作的实现2. 实验内容 （1）建立无向图的邻接矩阵存储 （2）进行深度优先遍历 （3）进行广度优先遍历3．设计与编码MGraph.h #ifndef MGraph_H #define MGraph_H const int MaxSize = 10; template
int vertexNum, arcNum; }; #endif MGraph.cpp #include
福建工程学院 课程设计 课程：算法与数据结构 题目：哈希表 专业：网络工程 班级：xxxxxx班 座号：xxxxxxxxxxxx 姓名：xxxxxxx 2011年12 月31 日 实验题目：哈希表 一、要解决的问题 针对同班同学信息设计一个通讯录，学生信息有姓名，学号，电话号码等。以学生姓名为关键字设计哈希表，并完成相应的建表和查表程序。 基本要求：姓名以汉语拼音形式，待填入哈希表的人名约30个，自行设计哈希函数，用线性探测再散列法或链地址法处理冲突；在查找的过程中给出比较的次数。完成按姓名查询的操作。 运行的环境：Microsoft Visual C++ 6.0 二、算法基本思想描述 设计一个哈希表（哈希表内的元素为自定义的结构体）用来存放待填入的30个人名，人名为中国姓名的汉语拼音形式，用除留余数法构造哈希函数，用线性探查法解决哈希冲突。建立哈希表并且将其显示出来。通过要查找的关键字用哈希函数计算出相应的地址来查找人名。通过循环语句调用数组中保存的数据来显示哈希表。 三、设计 1、数据结构的设计和说明 （1）结构体的定义 typedef struct //记录 { NA name; NA xuehao; NA tel; }Record;
{ Record *elem[HASHSIZE]; //数据元素存储基址 int count; //当前数据元素个数 int size; //当前容量 }HashTable; 哈希表元素的定义，包含数据元素存储基址、数据元素个数、当前容量。 2、关键算法的设计 （1）姓名的折叠处理 long fold(NA s) //人名的折叠处理 { char *p; long sum=0; NA ss; strcpy(ss,s); //复制字符串，不改变原字符串的大小写 strupr(ss); //将字符串ss转换为大写形式 p=ss; while(*p!='\0') sum+=*p++; printf("\nsum====================%d",sum); return sum; } （2）建立哈希表 1、用除留余数法构建哈希函数 2、用线性探测再散列法处理冲突 int Hash1(NA str) //哈希函数 { long n; int m; n=fold(str); //先将用户名进行折叠处理 m=n%HASHSIZE; //折叠处理后的数，用除留余数法构造哈希函数 return m; //并返回模值 }Status collision(int p,int c) //冲突处理函数，采用二次探测再散列法解决冲突{ int i,q; i=c/2+1; while(i
《数据结构》第六次实验报告 学生姓名 学生班级 学生学号 指导老师
一、实验内容 1) 采用二叉树链表作为存储结构，完成二叉树的建立，先序、中序和后序 以及按层次遍历的操作，求所有叶子及结点总数的操作。 2) 输出树的深度，最大元，最小元。 二、需求分析 遍历二叉树首先有三种方法，即先序遍历，中序遍历和后序遍历。 递归方法比较简单，首先获得结点指针如果指针不为空，且有左子，从左子递归到下一层，如果没有左子，从右子递归到下一层，如果指针为空，则结束一层递归调用。直到递归全部结束。 下面重点来讲述非递归方法： 首先介绍先序遍历： 先序遍历的顺序是根左右，也就是说先访问根结点然后访问其左子再然后访问其右子。具体算法实现如下：如果结点的指针不为空，结点指针入栈，输出相应结点的数据，同时指针指向其左子，如果结点的指针为空，表示左子树访问结束，栈顶结点指针出栈，指针指向其右子，对其右子树进行访问，如此循环，直至结点指针和栈均为空时，遍历结束。 再次介绍中序遍历： 中序遍历的顺序是左根右，中序遍历和先序遍历思想差不多，只是打印顺序稍有变化。具体实现算法如下：如果结点指针不为空，结点入栈，指针指向其左子，如果指针为空，表示左子树访问完成，则栈顶结点指针出栈，并输出相应结点的数据，同时指针指向其右子，对其右子树进行访问。如此循环直至结点指针和栈均为空，遍历结束。 最后介绍后序遍历： 后序遍历的顺序是左右根，后序遍历是比较难的一种，首先需要建立两个栈，一个用来存放结点的指针，另一个存放标志位，也是首先访问根结点，如果结点的指针不为空，根结点入栈，与之对应的标志位也随之入标志位栈，并赋值0，表示该结点的右子还没有访问，指针指向该结点的左子，如果结点指针为空，表示左子访问完成，父结点出栈，与之对应的标志位也随之出栈，如果相应的标志位值为0，表示右子树还没有访问，指针指向其右子，父结点再次入栈，与之对应的标志位也入栈，但要给标志位赋值为1，表示右子访问过。如果相应的标志位值为1，表示右子树已经访问完成，此时要输出相应结点的数据，同时将结点指针赋值为空，如此循环直至结点指针和栈均为空，遍历结束。 三、详细设计 源代码：
实验1 (C语言补充实验) 有顺序表A和B,其元素值均按从小到大的升序排列，要求将它们合并成一 个顺序表C,且C的元素也是从小到大的升序排列。 #include 求A QB #include 数据结构实验报告四——哈希表查找名字(字符串） 实验题目:哈希表查找名字（字符串) 实验目标: 输入一组名字(至少50个）,将其保存并利用哈希表查找。输出哈希查找冲突次数,哈希表负载因子、查找命中率。 数据结构： 哈希表与数组（二维）。二维数组用于静态顺序存储名字(字符串),哈希表采用开放定址法,用于存储名字(字符串)对应得关键字并实现对名字（字符串)得查找。 需要得操作有: １、关键字求取(主函数中两次出现，未单独编为函数） 关键字key=abｓ(字符串首位AＳＣII码值-第二位ASCIＩ码值＋第([]+1)位ASCＩI码值-最后一位ASCII码值－倒数第二位ASCII码值)*字符串长度（abｓ为求整数绝对值得函数)。 ２、处理关键字得哈希函数(Hash) 利用平方取中法求关键值key在哈希表中得位置。公式ａdd=(key＊key）%1０00/LENGTH（a ｄd为key在哈希表中得地址)。 int Hａsｈ（ｉｎｔkey) { ?rｅturn((key*key)/1０００%LENＧＴH); } 3、处理哈希表中冲突得函数(Coｌlｉｓiｏn) 利用线性探测再散列处理冲突,利用全局变量counｔ统计冲突次数。 ｉnt Collｉsioｎ（inｔkｅy,int Haｓhtaｂle［］) { ｉｎtｉ; for(i=1;i<=ＬENGTH;ｉ++） { ??iｆ（Ｈashtabｌe[(Hａsｈ（kｅy)+ｉ)％LEＮGＴＨ]==-1） ?returｎ(（Hａsｈ(keｙ）＋i)％LENＧTＨ); ??count+＋; } } 4、哈希表初始化（InitＨaｓh) ｖoid InitHash(int Hａshtaｂlｅ[]) { ｉｎｔi; for(i=0;ｉ＜ＬＥNGTH；i++) ??Hashtable[i]=-1; } 5、向哈希表中插入关键字(InsｅrｔＨaｓh) void InｓertＨash(int kｅy,int Hａshｔablｅ［]) { ｉｎt add; .栈通常采用的两种存储结构是______________________ .用链表表示线性表的优点是_______________________ 8.在单链表中，增加头结点的目的是___________________ 9.循环链表的主要优点是________________________- 12.线性表的顺序存储结构和线性表的链式存储结构分别是__________________________ 13.树是结点的集合，它的根结点数目是_____________________ 14.在深度为5的满二叉树中，叶子结点的个数为_______________ 15.具有3个结点的二叉树有（_____________________ 16.设一棵二叉树中有3个叶子结点，有8个度为1的结点，则该二叉树中总的结点数为____________________ 17.已知二叉树后序遍历序列是dabec，中序遍历序列是debac，它的前序遍历序列是____________________________ 18.已知一棵二叉树前序遍历和中序遍历分别为ABDEGCFH和DBGEACHF，则该二叉树的后序遍历为______________________ 19.若某二叉树的前序遍历访问顺序是abdgcefh，中序遍历访问顺序是dgbaechf，则其后序遍历的结点访问顺序是_______________________ 20.数据库保护分为：安全性控制、完整性控制、并发性控制和数据的恢复。 在计算机中，算法是指_______________________ 算法一般都可以用哪几种控制结构组合而成_____________________ .算法的时间复杂度是指______________________ 5. 算法的空间复杂度是指__________________________ 6. 算法分析的目的是__________________________ ******************************* 实验题目：二叉树的操作 实验者信息：班级13007102，姓名庞文正，学号1300710226 实验完成的时间3:00 ****************************** 一、实验目的 1,掌握二叉树链表的结构和二叉树的建立过程。 2,掌握队列的先进先出的运算原则在解决实际问题中的应用。 3,进一步掌握指针变量、指针数组、动态变量的含义。 4,掌握递归程序设计的特点和编程方法。 二、实验内容 已知以二叉链表作存储结构，试编写按层次遍历二叉树的算法。（所谓层次遍历，是指从二叉树的根结点开始从上到下逐层遍历二叉树，在同一层次中从左到右依次访问各个节点。）调试程序并对相应的输出作出分析；修改输入数据，预期输出并验证输出的结果。加深对算法的理解。 三、算法设计与编码 1.本实验用到的理论知识 总结本实验用到的理论知识，实现理论与实践相结合。总结尽量简明扼要，并与本次实验密切相关，最好能加上自己的解释。 本算法要采用一个循环队列que，先将二叉树根结点入队列，然后退队列，输出该结点；若它有左子树，便将左子树根结点入队列；若它有右子树，便将右子树根结点入队列，直到队列空为止。因为队列的特点是先进先出，从而达到按层次顺序遍历二叉的目的。2.算法概要设计 给出实验的数据结构描述，程序模块、功能及调用关系 #include 福建工程学院课程设计 课程：算法与数据结构 题目：哈希表 专业：网络工程 班级：xxxxxx班 座号：xxxxxxxxxxxx 姓名：xxxxxxx 2011年12 月31 日 实验题目：哈希表 一、要解决的问题 针对同班同学信息设计一个通讯录，学生信息有姓名，学号，电话号码等。以学生姓名为关键字设计哈希表，并完成相应的建表和查表程序。 基本要求：姓名以汉语拼音形式，待填入哈希表的人名约30个，自行设计哈希函数，用线性探测再散列法或链地址法处理冲突；在查找的过程中给出比较的次数。完成按姓名查询的操作。 运行的环境：Microsoft Visual C++ 6.0 二、算法基本思想描述 设计一个哈希表（哈希表内的元素为自定义的结构体）用来存放待填入的30个人名，人名为中国姓名的汉语拼音形式，用除留余数法构造哈希函数，用线性探查法解决哈希冲突。建立哈希表并且将其显示出来。通过要查找的关键字用哈希函数计算出相应的地址来查找人名。通过循环语句调用数组中保存的数据来显示哈希表。 三、设计 1、数据结构的设计和说明 （1）结构体的定义 typedef struct //记录 { NA name; NA xuehao; NA tel; }Record; 录入信息结构体的定义，包含姓名，学号，电话号码。 typedef struct //哈希表 { Record *elem[HASHSIZE]; //数据元素存储基址 int count; //当前数据元素个数 int size; //当前容量 }HashTable; 哈希表元素的定义，包含数据元素存储基址、数据元素个数、当前容量。 2、关键算法的设计 （1）姓名的折叠处理 学生实验报告 学院：软通学院 课程名称：数据结构与算法 专业班级：软件142 班 姓名：邹洁蒙 学号： 0143990 学生实验报告 （二） 一、实验综述 1、实验目的及要求 目的：1）掌握树与二叉树的基本概念； 2）掌握二叉树的顺序存储，二叉链表的先序遍历中序遍历和后序遍历算法； 3）掌握树的双亲表示法。 要求：1）编程：二叉树的顺序存储实现； 2）编程：二叉链表的先序遍历中序遍历和后序遍历实现； 3）编程：树的双亲表示法实现。 2、实验仪器、设备或软件 设备：PC 软件：VC6 二、实验过程(编程，调试，运行；请写上源码，要求要有注释) 1.编程：二叉树的顺序存储实现 代码： BiTree::BiTree()//建立存储空间 { data = new int[MAXSIZE]; count = 0; } void BiTree::AddNode(int e)//加结点 { int temp = 0; data[count] = e; count++;//从编号0开始保存 } 运行截图： 2.编程：二叉链表的先序遍历中序遍历和后序遍历实现代码： void InOrderTraverse(BiTree* Head)//中序遍历 { if (Head) { InOrderTraverse(Head->LeftChild); cout << Head->data<<" "; InOrderTraverse(Head->RightChild); } } void PreOrderTraverse(BiTree* Head)//先序遍历 { if (Head) { cout << Head->data << " "; PreOrderTraverse(Head->LeftChild); PreOrderTraverse(Head->RightChild); } } void PostOrderTraverse(BiTree* Head)//后序遍历 { if (Head) { PostOrderTraverse(Head->LeftChild); PostOrderTraverse(Head->RightChild); cout << Head->data << " "; } } 运行截图： 附录A 实验报告 课程：数据结构（c语言）实验名称：图的建立、基本操作以及遍历系别：数字媒体技术实验日期： 12月13号 12月20号 专业班级：媒体161 组别：无 姓名：学号： 实验报告内容 验证性实验 一、预习准备： 实验目的： 1、熟练掌握图的结构特性，熟悉图的各种存储结构的特点及适用范围； 2、熟练掌握几种常见图的遍历方法及遍历算法； 实验环境：Widows操作系统、VC6.0 实验原理： 1.定义： 基本定义和术语 图(Graph)——图G是由两个集合V(G)和E(G)组成的,记为G=(V,E)，其中：V(G)是顶点(V ertex)的非空有限集E(G)是边(Edge)的有限集合，边是顶点的无序对(即：无方向的，（v0,v2）)或有序对（即：有方向的, 无向图中顶点V i的度TD(V i)是邻接矩阵A中第i行元素之和有向图中， 顶点V i的出度是A中第i行元素之和 顶点V i的入度是A中第i列元素之和 邻接表 实现：为图中每个顶点建立一个单链表，第i个单链表中的结点表示依附于顶点Vi的边（有向图中指以Vi为尾的弧） 特点: 无向图中顶点Vi的度为第i个单链表中的结点数有向图中 顶点Vi的出度为第i个单链表中的结点个数 顶点Vi的入度为整个单链表中邻接点域值是i的结点个数 逆邻接表：有向图中对每个结点建立以Vi为头的弧的单链表。 图的遍历 从图中某个顶点出发访遍图中其余顶点，并且使图中的每个顶点仅被访问一次过程.。遍历图的过程实质上是通过边或弧对每个顶点查找其邻接点的过程，其耗费的时间取决于所采用的存储结构。图的遍历有两条路径：深度优先搜索和广度优先搜索。当用邻接矩阵作图的存储结构时，查找每个顶点的邻接点所需要时间为O（n2），n为图中顶点数；而当以邻接表作图的存储结构时，找邻接点所需时间为O（e），e 为无向图中边的数或有向图中弧的数。 实验内容和要求： 选用任一种图的存储结构，建立如下图所示的带权有向图： 要求：1、建立边的条数为零的图； 云南大学数学与统计学实验教学中心实验报告 课程名称： 数据结构与算法学期： 2011-2012学年第二学期 成绩： 指导教师：xxx学生姓名：xxx学生学号：xxxxx 实验名称：哈希表及其查找实验要求：必做实验学时：4（+2）学时 实验编号：4（及5）实验日期：第6-8周完成日期：2012.5.10 学院：数学与统计学院专业：信息与计算科学年级：2010级 一、实验目的 通过实验掌握散列存储的基本概念，进行哈希问题的处理，同时附带进行字符串的处理的练习。 二、实验内容 为某单位的人名（n=30人）设计一个哈希表，使得平均查找长度<2，要求完成相应的哈希建表和查表。。 三、实验环境 Windows XP 程序设计语言C 四、实验过程 1．实验要求： 1、设人名长度<10个字符，用二维字符数组存储哈希表：char hash[ ][10]; 2、要求哈希函数用除留余数法，并用人名的10个字符代码和作为分子； 用（补偿性）线性探测再散列处理冲突。 3、依题意有：平均查找长度=（1+1/(1-α)）/2< 2，∴取α=0.6， 由此哈希表长m=n/α=30/0.6=50; 所以有char hashlist [ 50][10]； 令：除留余数法中的P取47； （补偿性）线性探测再散列的地址：j=(j+Q)% m中的Q取17。 4、对程序结构的要求： ①要求为哈希建表和哈希查表分别编写和设计相应的函数： createhash( ... ... ); hashsearch(... ...)； ②再设计一个哈希函数表的输出函数printhash( )，对构造的哈希表进行输出，注 意输出格式要在屏幕好看，先输出序号（1~30），再输出该序号 的人名或null，每行输出10项，共输出5行。 ③还应有一个初始化char hashlist [ 50][10]的函数Inithashlist( )， 初始时将50个人名全赋值为null. 5、在主函数中： 调用Inithashlist( )初始化哈希表； 习题二 ⒉１描述以下四个概念的区别：头指针变量，头指针，头结点，首结点（第一个结点）。解：头指针变量和头指针是指向链表中第一个结点（头结点或首结点）的指针；在首结点之前附设一个结点称为头结点；首结点是指链表中存储线性表中第一个数据元素的结点。若单链表中附设头结点，则不管线性表是否为空，头指针均不为空，否则表示空表的链表的头指针为空。 2.2简述线性表的两种存储结构有哪些主要优缺点及各自使用的场合。 解：顺序存储是按索引直接存储数据元素，方便灵活，效率高，但插入、删除操作将引起元素移动，降低了效率；而链式存储的元素存储采用动态分配，利用率高，但须增设表示结点之间有序关系的指针域，存取数据元素不如顺序存储方便，但结点的插入和删除十分简单。顺序存储适用于线性表中元素数量基本稳定，且很少进行插入和删除，但要求以最快的速度存取线性表中的元素的情况；而链式存储适用于频繁进行元素动态插入或删除操作的场合。 2.3 在头结点为h的单链表中，把值为b的结点s插入到值为a的结点之前，若不存在a，就把结点s插入到表尾。 Void insert(Lnode *h,int a,int b) {Lnode *p,*q,*s; s=(Lnode*)malloc(sizeof(Lnode)); s->data=b; p=h->next; while(p->data!=a&&p->next!=NULL) {q=p; p=p->next; } if (p->data==a) {q->next=s; s->next=p;} else {p->next=s; s->next=NULL; } } 2.4 设计一个算法将一个带头结点的单链表A分解成两个带头结点的单链表A和B，使A中含有原链表中序号为奇数的元素，而B中含有原链表中序号为偶数的元素，并且保持元素原有的相对顺序。 Lnode *cf(Lnode *ha) {Lnode *p,*q,*s,*hb; int t; p=ha->next; q=ha; t=0; hb=(Lnode*)malloc(sizeof(Lnode)); s=hb; while(p->next!=NULL) {if (t==0) {q=p;p=p->next;t=1;} else {q->next=p->next; p->next=s->next; s->next=p; s=p; p=p->next; t=0; } } s->next=NULL; return (hb); } 算法与数据结构》课程实验报告 一、实验目的 1、实现二叉树的存储结构 2、熟悉二叉树基本术语的含义 3、掌握二叉树相关操作的具体实现方法 二、实验内容及要求 1. 建立二叉树 2. 计算结点所在的层次 3. 统计结点数量和叶结点数量 4. 计算二叉树的高度 5. 计算结点的度 6. 找结点的双亲和子女 7. 二叉树前序、中序、后序遍历的递归实现和非递归实现及层次遍历 8. 二叉树的复制 9. 二叉树的输出等 三、系统分析 （1）数据方面：该二叉树数据元素采用字符char 型，并且约定“ #”作为二叉树输入结束标识符。并在此基础上进行二叉树相关操作。 （2）功能方面：能够实现二叉树的一些基本操作，主要包括： 1. 采用广义表建立二叉树。 2. 计算二叉树高度、统计结点数量、叶节点数量、计算每个结点的度、结点所在层次。 3. 判断结点是否存在二叉树中。 4. 寻找结点父结点、子女结点。 5. 递归、非递归两种方式输出二叉树前序、中序、后序遍历。 6. 进行二叉树的复制。 四、系统设计 （1）设计的主要思路 二叉树是的结点是一个有限集合，该集合或者为空，或者是由一个根节点加上两棵分别称为左子树和右子树、互不相交的二叉树组成。根据实验要求，以及课上老师对于二叉树存储结构、基本应用的讲解，同时课后研究书中涉及二叉树代码完成二叉树模板类，并将所需实现各个功能代码编写完成，在建立菜单对功能进行调试。 （2）数据结构的设计 二叉树的存储结构有数组方式和链表方式。但用数组来存储二叉树有可能会消耗大量的存储空间，故在此选用链表存储，提高存储空间的利用率。根据二叉树的定义，二叉 数据结构教程 上机实验报告 实验七、图算法上机实现 一、实验目的： 1.了解熟知图的定义和图的基本术语，掌握图的几种存储结构。 2.掌握邻接矩阵和邻接表定义及特点，并通过实例解析掌握邻接矩阵和邻接表的类型定义。 3.掌握图的遍历的定义、复杂性分析及应用，并掌握图的遍历方法及其基本思想。 二、实验内容： 1.建立无向图的邻接矩阵 2.图的xx优先搜索 3.图的xx优先搜索 三、实验步骤及结果： 1.建立无向图的邻接矩阵： 1)源代码： #include "stdio.h" #include "stdlib.h" #define MAXSIZE 30 typedefstruct{charvertex[MAXSIZE];//顶点为字符型且顶点表的长度小于MAXSIZE intedges[MAXSIZE][MAXSIZE];//边为整形且edges为邻近矩阵 }MGraph;//MGraph为采用邻近矩阵存储的图类型 voidCreatMGraph(MGraph *g,inte,int n) {//建立无向图的邻近矩阵g->egdes，n为顶点个数，e为边数inti,j,k; printf("Input data of vertexs(0~n-1): \n"); for(i=0;i 课程实习报告 一、需求分析： 1.本程序来自于图书馆靠书名来检索想要查找的书问题。 2.本程序要求： （1）根据输入建立图书名称表，采用创建散列表实现。 （2）建散列表后，如果想要查找的数据在散列表中输出yes否则输出no。 二、哈希表简介 结构中存在关键字和K相等的记录，则必定存储在f(K）的位置上。由此，不需比较便可直接取得所查记录。这个对应关系f称为散列函数(Hash function），按这个思想建立的表为散列表。 * 对不同的关键字可能得到同一散列地址，即key1≠key2，而f(key1)=f(key2），这种现象称冲突。具有相同函数值的关键字对该散列函数来说称做同义词。 * 综上所述，根据散列函数H(key）和处理冲突的方法将一组关键字映象到一个有限的连续的地址集（区间）上，并以关键字在地址集中的“象”，作为这条记录在表中的存储位置，这种表便称为散列表，这一映象过程称为散列造表或散列，所得的存储位置称散列地址。这个现象也叫散列桶，在散列桶中，只能通过顺序的方式来查找，一般只需要查找三次就可以找到。科学家计算过，当负载因子(load factor)不超过75%，查找效率最高。* 若对于关键字集合中的任一个关键字，经散列函数映象到地址集合中任何一个地址的概率是相等的，则称此类散列函数为均匀散列函数（Uniform Hash function），这就是使关键字经过散列函数得到一个“随机的地址”，从而减少冲突。 程序设计流程 程序思想 (一)哈希函数unsigned int hash_BKDE(char *str)生成映射 地址，成为散列表的编号。 (二)哈希表HashTable::HashTable()通过数组储存元素 (三)插入函数void HashTable::insert(char*c)插入字符串， 先计算要插入字符串生成的映射地址，然后在相应的地址插入，如果没有空位查找空位插入。哈希表实验报告
经典数据结构面试题(含答案)
数据结构实验-二叉树的操作
数据结构课程设计--哈希表实验报告
数据结构实验报告之树与二叉树
数据结构实验报告(图)
数据结构实验四哈希表及其查找
数据结构上机例题及答案
数据结构实验报告—二叉树
数据结构图实验报告
数据结构哈希表的实验报告
相关主题
文本预览