【例9.1】已知一组关键字为(26，36，41，38，44，15，68，12，06，51)，用除余法构造散列函数，用线性探查法解决冲突构造这组关键字的散列表。
解答:为了减少冲突，通常令装填因子α 用线性探查法解决冲突时，当表中i,i+1，…，i+k的位置上已有结点时，一个散列地址为i，i+1，…，i+k+1的结点都将插入在位置i+k+1上。把这种散列地址不同的结点争夺同一个后继散列地址的现象称为聚集或堆积(Clustering)。这将造成不是同义词的结点也处在同一个探查序列之中，从而增加了探查序列的长度，即增加了查找时间。若散列函数不好或装填因子过大，都会使堆积现象加剧。 【例】上例中，h(15)=2，h(68)=3，即15和68不是同义词。但由于处理15和同义词41的冲突时，15抢先占用了T[3]，这就使得插入68时，这两个本来不应该发生冲突的非同义词之间也会发生冲突。 为了减少堆积的发生，不能像线性探查法那样探查一个顺序的地址序列(相当于顺序查找)，而应使探查序列跳跃式地散列在整个散列表中。 ②二次探查法(Quadratic Probing) 二次探查法的探查序列是：h i =(h(key)+i*i)％m 0≤i≤m-1 //即d i =i 2，即探查序列为d=h(key)，d+1 2 ，d+2 2 ，…，等。该方法的缺陷是不易探查到整个散列空间。 ③双重散列法(Double Hashing) 该方法是开放定址法中最好的方法之一，它的探查序列是：h i =(h(key)+i*h1(key))％m 0≤i≤m-1 //即d i =i*h1(key)，即探查序列为： d=h(key)，(d+h1(key))％m，(d+2h1(key))％m，…，等。 该方法使用了两个散列函数h(key)和h1(key)，故也称为双散列函数探查法。注意：定义h1(key)的方法较多，但无论采用什么方法定义，都必须使h1(key)的值和m互素，才能使发生冲突的同义词地址均匀地分布在整个表中，否则可能造成同义词地址的循环计算。 【例】若m为素数，则h1(key)取1到m-1之间的任何数均与m互素，因此，我们可以简单地将它定义为：h1(key)=key％(m-2)+1 【例】对例9.1，我们可取h(key)=key％13，而h1(key)=key％11+1。 【例】若m是2的方幂，则h1(key)可取1到m-1之间的任何奇数。 2、拉链法 （1）拉链法解决冲突的方法 拉链法解决冲突的做法是：将所有关键字为同义词的结点链接在同一个单链表中。若选定的散列表长度为m，则可将散列表定义为一个由m个头指针组成的指针数组T[0..m-1]。凡是散列地址为i的结点，均插入到以T[i]为头指针的单链表中。T中各分量的初值均应为空指针。在拉链法中，装填因子α可以大于1，但一般均取α≤1。 【例9.2】已知一组关键字和选定的散列函数和例9.1相同，用拉链法解决冲突构造这组关键字的散列表。 解答：不妨和例9.1类似，取表长为13，故散列函数为h(key)=key％13，散列表为T[0..12]。注意：当把h(key)=i的关键字插入第i个单链表时，既可插入在链表的头上，也可以插在链表的尾上。这是因为必须确定key不在第i 个链表时，才能将它插入表中，所以也就知道链尾结点的地址。若采用将新关键字插入链尾的方式，依次把给定的这组关键字插入表中，则所得到的散列表如下图所示。 （2）拉链法的优点 与开放定址法相比，拉链法有如下几个优点：(1)拉链法处理冲突简单，且无堆积现象，即非同义词决不会发生冲突，因此平均查找长度较短；(2)由于拉链法中各链表上的结点空间是动态申请的，故它更适合于造表前无法确定表长的情况；(3)开放定址法为减少冲突，要求装填因子α较小，故当结点规模较大时会浪费很多空间。而拉链法中可取α≥1，且结点较大时，拉链法中增加的指针域 可忽略不计，因此节省空间；(4)在用拉链法构造的散列表中，删除结点的操作易于实现。只要简单地删去链表上相应的结点即可。而对开放地址法构造的散列表，删除结点不能简单地将被删结点的空间置为空，否则将截断在它之后填人散列表的同义词结点的查找路径。这是因为各种开放地址法中，空地址单元(即开放地址)都是查找失败的条件。因此在用开放地址法处理冲突的散列表上执行删除操作，只能在被删结点上做删除标记，而不能真正删除结点。 （3）拉链法的缺点 拉链法的缺点是：指针需要额外的空间，故当结点规模较小时，开放定址法较为节省空间，而若将节省的指针空间用来扩大散列表的规模，可使装填因子变小，这又减少了开放定址法中的冲突，从而提高平均查找速度。 四、散列表上的运算 散列表上的运算有查找、插入和删除。其中主要是查找，这是因为散列表的目的主要是用于快速查找，且插入和删除均要用到查找操作。 1、散列表类型说明： #define NIL -1 //空结点标记依赖于关键字类型，本节假定关键字均为非负整数 #define M 997 //表长度依赖于应用，但一般应根据。确定m为一素数 typedef struct{ //散列表结点类型 KeyType key； InfoType otherinfo； //此类依赖于应用 }NodeType； typedef NodeType HashTable[m]； //散列表类型 2、基于开放地址法的查找算法 散列表的查找过程和建表过程相似。假设给定的值为K，根据建表时设定的散列函数h，计算出散列地址h(K)，若表中该地址单元为空，则查找失败；否则将该地址中的结点与给定值K比较。若相等则查找成功，否则按建表时设定的处理冲突的方法找下一个地址。如此反复下去，直到某个地址单元为空(查找失败)或者关键字比较相等(查找成功)为止。 （1）开放地址法一般形式的函数表示 int Hash(KeyType k，int i) { //求在散列表T[0..m-1]中第i次探查的散列地址hi，0≤i≤m-1 //下面的h是散列函数。Increment是求增量序列的函数，它依赖于解决冲突的方法 return(h(K)+Increment(i))％m； //Increment(i)相当于是d i } 若散列函数用除余法构造，并假设使用线性探查的开放定址法处理冲突，则上述函数中的h(K)和Increment(i)可定义为： int h(KeyType K){//用除余法求K的散列地址 return K％m； } int Increment(int i){ //用线性探查法求第i个增量d i return i; //若用二次探查法，则返回i*i } （2）通用的开放定址法的散列表查找算法： int HashSearch(HashTable T，KeyType K，int *pos) { //在散列表T[0..m-1]中查找K，成功时返回1。失败有两种情况：找到一个开放地址 //时返回0，表满未找到时返回-1。 *pos记录找到K或找到空结点时表中的位置 int i=0； //记录探查次数 do{ *pos=Hash(K，i)； //求探查地址hi if(T[*pos].key==K) return l； //查找成功返回 if(T[*pos].key==NIL) return 0；//查找到空结点返回 }while(++i return -1； //表满且未找到时，查找失败 } //HashSearch 注意：上述算法适用于任何开放定址法，只要给出函数Hash中的散列函数h(K)和增量函数Increment(i)即可。但要提高查找效率时，可将确定的散列函数和求增量的方法直接写入算法HashSearch中。 3、基于开放地址法的插入及建表 建表时首先要将表中各结点的关键字清空，使其地址为开放的；然后调用插入算法将给定的关键字序列依次插入表中。插入算法首先调用查找算法，若在表中找到待插入的关键字或表已满，则插入失败；若在表中找到一个开放地址，则将待插入的结点插入其中，即插入成功。 void Hashlnsert(HashTable T，NodeTypene w) { //将新结点new插入散列表T[0..m-1]中 int pos，sign； sign=HashSearch(T，new.key，&pos)； //在表T中查找new的插入位置 if(!sign) //找到一个开放的地址pos T[pos]=new； //插入新结点new，插入成功 else //插人失败 if(sign>0) printf("duplicate key!")； //重复的关键字 else //sign<0 Error("hashtableoverflow!")； //表满错误，终止程序执行 } //Hashlnsert void CreateHashTable(HashTable T，NodeType A[]，int n) { //根据A[0..n-1]中结点建立散列表T[0..m-1] int i if(n>m) //用开放定址法处理冲突时，装填因子α须不大于1 Error("Load factor>1")； for(i=0;i T[i].key=NIL； //将各关键字清空，使地址i为开放地址 for(i=0;i } //CreateHashTable 4、删除 基于开放定址法的散列表不宜执行散列表的删除操作。若必须在散列表中删除结点，则不能将被删结点的关键字置为NIL，而应该将其置为特定的标记DELETED。因此须对查找操作做相应的修改，使之探查到此标记时继续探查下去。同时也要修改插人操作，使其探查到DELETED标记时，将相应的表单元视为一个空单元，将新结点插入其中。这样做无疑增加了时间开销，并且查找时间不再依赖于装填因子。因此，当必须对散列表做删除结点的操作时，一般是用拉链法来解决冲突。 5、性能分析 插入和删除的时间均取决于查找，故下面只分析查找操作的时间性能。 虽然散列表在关键字和存储位置之间建立了对应关系，理想情况是无须关键字的比较就可找到待查关键字。但是由于冲突的存在，散列表的查找过程仍是一个和关键字比较的过程，不过散列表的平均查找长度比顺序查找、二分查找等完全依赖于关键字比较的查找要小得多。 （1）查找成功的ASL 散列表上的查找优于顺序查找和二分查找。 【例】在例9.1和例9.2的散列表中，在结点的查找概率相等的假设下，线性探查法和拉链法查找成功的平均查找长度分别为： ASL=(1×6+2×2+3×l+9×1)/10=2.2 //线性探查法 ASL=(1×7+2×2+3×1)/10=1.4 //拉链法 当n=10时，顺序查找和二分查找的平均查找长度(成功时)分别为： ASL=(10+1)/2=5.5 //顺序查找 ASL=(1×l+2×2+3×4+4×3)/10=2.9 //二分查找，可由判定树求出该值 （2）查找不成功的ASL 对于不成功的查找，顺序查找和二分查找所需进行的关键字比较次数仅取决于表长，而散列查找所需进行的关键字比较次数和待查结点有关。因此，在等概率情况下，也可将散列表在查找不成功时的平均查找长度，定义为查找不成功时对关键字需要执行的平均比较次数。 【例】例9.1和例9.2的散列表中，在等概率情况下，查找不成功时的线性探查法和拉链法的平均查找长度分别为： ASL unsucc =(9+8+7+6+5+4+3+2+1+1+2+1+10)/13=59/13≈4.54 ASL unsucc =(1+0+2+1+0+1+1+0+0+0+1+0+3)/13≈10/13≈0.77 注意： ①由同一个散列函数、不同的解决冲突方法构造的散列表，其平均查找长度是不相同的。 ②散列表的平均查找长度不是结点个数n的函数，而是装填因子α的函数。因此在设计散列表时可选择α以控制散列表的平均查找 长度。 ③ α的取值越小，产生冲突的机会就小，但α过小，空间的浪费就过多。只要α选择合适，散列表上的平均查找长度就是一个常数，即散列表上查找的平均时间为O(1)。 ④ 散列法与其他查找方法的区别 除散列法外，其他查找方法有共同特征为：均是建立在比较关键字的基础上。其 中顺序查找是对无序集合的查找，每次关键字的比较结果为"="或"!="两种可能，其平均时间为O(n)；其余的查找均是对有序集合的查找，每次关键字的比较有"="、"<"和">"三种可能，且每次比较后均能缩小下次的查找范围，故查找速度更快，其平均时间为O(lgn)。而散列法是根据关键字直接求出地址的查找方法，其查找的期望时间为O(1)。 （2）查找不成功的ASL 对于不成功的查找，顺序查找和二分查找所需进行的比较次数仅取决于表长，而散列查找所需进行的比较次数和待 查结点有关。因此，在等概率情况下，也可将散列表在查找不成功时的平均查找长度，定义为查找不成功时对需要执行的平均 比较次数。 【例】例9.1和例9.2的散列表中，在等概率情况下，查找不成功时的线性探查法和拉链法的平均查找长度分别为： ASL unsucc =/13=59/13≈4.54 ASL unsucc =/13≈10/13≈0.77 注意： ①由同一个散列函数、不同的解决冲突方法构造的散列表，其平均查找长度是不相同的。 ②散列表的平均查找长度不是结点个数n的函数，而是装填因子α的函数。因此在设计散列表时可选择α以控制散列表的平均查找 长度。 ③ α的取值 α越小，产生冲突的机会就小，但α过小，空间的浪费就过多。只要α选择合适，散列表上的平均查找长度就是一个常数，即散 列表上查找的平均时间为O。 ④ 散列法与其他查找方法的区别 除散列法外，其他查找方法有共同特征为：均是建立在比较的基础上。其中顺序查找是对无序集合的查找，每次的比较 结果为"="或"!="两种可能，其平均时间为O；其余的查找均是对有序集合的查找，每次的比较有"="、""和""三种可能 ，且每次比较后均能缩小下次的查找范围，故查找速度更快，其平均时间为O。而散列法是根据直接求出地址的查找方法 ，其查找的期望时间为O。 （1）查找成功的ASL 散列表上的查找优于顺序查找和二分查找。 【例】在例9.1和例9.2的散列表中，在结点的查找概率相等的假设下，线性探查法和拉链法查找成功的平均查找长度分别为： ASL=/10=2.2 //线性探查法 ASL=/10=1.4 //拉链法 而当n=10时，顺序查找和二分查找的平均查找长度分别为： ASL=/2=5.5 //顺序查找 ASL=/10=2.9 //二分查找，可由判定树求出该值 （2）查找不成功的ASL 对于不成功的查找，顺序查找和二分查找所需进行的比较次数仅取决于表长，而散列查找所需进行的比较次数和待 查结点有关。因此，在等概率情况下，也可将散列表在查找不成功时的平均查找长度，定义为查找不成功时对需要执行的平均 比较次数。 【例】例9.1和例9.2的散列表中，在等概率情况下，查找不成功时的线性探查法和拉链法的平均查找长度分别为： ASL unsucc =/13=59/13≈4.54 ASL unsucc =/13≈10/13≈0.77 注意： ①由同一个散列函数、不同的解决冲突方法构造的散列表，其平均查找长度是不相同的。 ②散列表的平均查找长度不是结点个数n的函数，而是装填因子α的函数。因此在设计散列表时可选择α以控制散列表的平均查找 长度。 ③ α的取值 α越小，产生冲突的机会就小，但α过小，空间的浪费就过多。只要α选择合适，散列表上的平均查找长度就是一个常数，即散 列表上查找的平均时间为O。 ④ 散列法与其他查找方法的区别 除散列法外，其他查找方法有共同特征为：均是建立在比较的基础上。其中顺序查找是对无序集合的查找，每次的比较 结果为"="或"!="两种可能，其平均时间为O；其余的查找均是对有序集合的查找，每次的比较有"="、""和""三种可能 ，且每次比较后均能缩小下次的查找范围，故查找速度更快，其平均时间为O。而散列法是根据直接求出地址的查找方法 ，其查找的期望时间为O。 查找是对数据、文件处理时常使用的一种操作。查找算法主要分为两类，静态查找和动态查找。 静态查找是指查找过程中标的结构始终不会发生变化，而动态查找表会发生变化，通常伴随着插入和删除操作。一般衡量查找算法的优越性主要看平均查找长度和最大查找长度。 一、静态查找表 1.顺序查找 算法思想：从表的一端开始顺序扫描线性表，依次将扫描到的结点关键字与给定值K比较，若当前扫描到的结点关键字与k相等则查找成功；若扫描结束后，仍未找到关键字等于K 的结点，则查找失败。 复杂度：若表中一共有N个记录，则顺序查找的最大查找长度为N，平均查找长度为(N+1)/2，算法的时间复杂度为O(N)。 应用：它可以用于顺序存储结构，也可以用于链表结构。 2.折半查找（二分查找） 算法思想：对一有序表中的元素，从初始的查找区间开始，每经过一次与当前查找区间的中点位置（通常(n+1)/2向下取整）上的结点关键字进行比较，若相等，则查找成功，否则，当前查找区间的缩小一半，按k值大小在某半个区间内重复相同的步骤进行查找，直到查找成功或失败为止。 复杂度：若表中一共有N个记录，则顺序查找的最大查找长度为【log2N】+1，平均查找长度为log【N+1】-1，算法的时间复杂度为O(log【N】)。 应用：但是折半查找是建立在已经排序的表的基础上的，而且折半查找只适用于顺序结构，不适用于链表结构，因为链表结构直接访问表的中间节点，不能像顺序结构一样通过下表操 作访问，链表要通过头指针移动找到中间节点。 3.分块查找（索引顺序查找） 算法思想：将原表分成若干块，各块内部不一定有序，但表中的块是"分块有序"的，并抽取各块中的最大关键字及其起始位置建立索引表。因为索引表是有序的，分块查找就是先用二分查找或顺序查找确定待查结点在哪一块，然后在已确定的块中进行顺序查找(不能用二分查找，因为块内是无序的)。 复杂度：分块查找实际上是两次查找过程，其平均查找长度为两次平局查找长度之和，它的算法效率介于顺序查找和二分查找之间。 应用：此种方法经常用于外部查找，将索引表放在内存中，原始数据的分块有序表以子表的形式存在外存储器上，先用索引表确定外存的子表，在将子表调入内存中查找。 二、动态查找 1.二叉排序树(BST)又称二叉查找树 算法思想：主要是根据二叉排序树的性质，1)若它的左子树非空，则左子树上所有结点的值均小于根结点的值；2)若它的右子树非空，则右子树上所有结点的值均大于根结点的值；3)左、右子树本身又是一棵二叉排序树。之后其查找方法类似于折半查找。 复杂度：它的关键字比较次数不超过树的深度，二叉排序树的查找复杂度与树形有关，在生成的过程中比较匀称，平衡的二叉树时约为lgn.在最坏的情况下，极不平衡时，退化为一个链表，此时的二叉排序树的高度将达到O(n),复杂度O(n)，为这种情况应当避免。为了构造形状比较均匀的二叉树，引出平衡二叉树的概念。 应用：其实二叉排序树和折半查找的复杂度差不多，但是折半查找只是用于顺序结构，对这种表的插入和删除操作很麻烦，而二叉排序树可以适用于链表存储结构，插入和删除操作灵活方便。 2.B-树 M阶B-树的性质1）树的根或者是一个叶子，或者含有[2,M]个孩子；2）除树根外，其他非叶子节点的儿子数在[【2/M】,M]之间。 3)所有的树叶都在相同的深度上。4）所有的数据都存储在树叶上。 算法思想：与二叉查找树类似。 应用：适用于大量文件的查找，它适合在磁盘等直接存取设备上组织动态的查找表，是一种外查找算法。 上面的查找方法都是建立在比较关键字的基础上，下面这种方法不需要比较关键字，称为哈希查找或者散列查找。 以下是在一片博客上看到的，总结的不错，本文来自CSDN博客https://www.doczj.com/doc/8015644260.html,/mosoft/archive/2005/06/06/388410.aspx 散列技术：可以无需任何比较就找到待查关键字，其查找的期望时间为O(1). 散列表的概念：就是将所有可能出现的关键字的集合U(全集)映射到一个表T[0..m-1]的下标集上，这个表就是散列表。 而关键字与这个表地址之间以什么样的关系发生联系呢，这就要通过一个函数来建立，这个函数是以U中的关键字为自变量，以相应结点的存储地址为函数值，它就称为散列函数或者哈希函数。将结点按其关键字的散列地址存储到散列表的过程称为散列。根据某种散列函数，一个关键字的散列函数值是唯一的，但是有可能两个或多个不同关键字的函数值是相同的，这时就会把几个结点存储到同一个表位置上，这时就造成冲突(或碰撞)现象，这两个关键字称为该散列函数的同义词。要完全(不是"安全")避免冲突需满足两个条件，一是关键字集合U不大于散列表长m，另一个是选择合适的散列函数。通常情况下U总是大大于m的，因此不可能完全避免冲突。冲突的频繁程度还与表的填满程度相关。装填因子α表示表中填入的结点数n与表长m的比值，即n/m，通常取α≤1，因为α越大，表越满，冲突的机会也越大。散列函数的选择有两条标准：简单和均匀。看看h(ki)=0这样的函数，简单是简单，但绝不均匀。 下面是常见的几种散列函数构造方法： （1）平方取中法 （2）除余法：它是用表长m来除关键字，取余数作为散列地址。若选除数m是关键字的基数的幂次，就会使得高位不同而低位相同的关键字互为同义词。因此最好选取素数为除数. （3）相乘取整法：有两个步骤，先用关键字key乘上某个常数A(0) （4）随机数法，此法以关键字为自变量，通过一随机函数得到的值作为散列地址。 处理冲突的方法：当不可避免发生冲突时，就必须对冲突加以解决，使发生冲突的同义词能存储到表中。通常有两类方法处理冲突：开放定址法和拉链法。前者是将所有结点均存放在散列T[0..m-1]中，后者是将互为同义词的结点链成一个单链表，而将此链表的头指针放在散列表中。 开放定址法的一般形式为：hi=(h(key)+di)%m 1≤i≤m-1。开放定址法要求散列表的装填因子α≤1。开放定址法又有线性探查法、二次探查法和双重散列法之分。 （1）由于线性探查法在构造散列表时，遇到冲突(有同义词)的时候会按探查序列向后面的空地址插入，从而使原来应插入到此位置的结点又与它发生冲突，当一连串的位置均已有结点时，本应插入到这些位置的结点又只能将其插入到更后面的同一个空结点上，这种散列地址不同的结点争夺同一个后继散列地址的现象就是聚集或堆积。(注意，同义词发生冲突不是堆积) 为了减小堆积现象的发生，可以用二次探查法和双重散列法进行探查。 （2）拉链法解决冲突的做法是，将所有关键字为同义词的结点链接在同一个单链表中。 与开放定址法相比，拉链法有如下几个优点： (1)拉链法处理冲突简单，且无堆积现象，即非同义词决不会发生冲突，因此平均查找长度较短；(简单无堆积) (2)由于拉链法中各链表上的结点空间是动态申请的，故它更适于造表前无法确定表长的情况；(动态申表长) (3)开放定址法为减少冲突要求装填因子α较小，当结点规模较大时会浪费很多空间，拉链法中α可以大于1，且结点较大时，其指针域可忽略不计，因此节省空间；(空间可节省) (4)拉链法构造的散列表删除结点易实现，而开放定址法中则不能真正删除结点只能做删除标记。(删除易实现) 拉链法也有缺点：当结点规模较小时，用拉链法中的指针域也要占用额外空间，还是开放定址法省空间。 在散列表上的运算有查找、插入和删除,主要是查找。这三个操作的算法并不复杂，也容易理解。散列表的平均查找长度不是结点个数n的函数，而是装填因子α的函数。α越小，冲突的概率越小，但空间的浪费将增加，当α大小合适时，散列表上的平均查找长度就是一个常数，时间性能是O(1). 一: 需求分析 (2) 三: 详细设计（含代码分析） (4) 1.程序描述: (4) 2具体步骤 (4) 四调试分析和测试结果 (7) 五，总结 (9) 六.参考文献; (10) 七.致谢 (10) 八.附录 (11) 一: 需求分析 问题描述：设计哈希表实现电话号码查询系统。 基本要求 1、设每个记录有下列数据项：电话号码、用户名、地址 2、从键盘输入各记录，分别以电话号码和用户名为关键字建立哈希表； 3、采用再哈希法解决冲突； 4、查找并显示给定电话号码的记录； 5、查找并显示给定用户名的记录。 6、在哈希函数确定的前提下，尝试各种不同类型处理冲突的方法（至少 两种），考察平均查找长度的变化。 二: 概要设计 进入主函数,用户输入1或者2,进入分支选择结构:选1:以链式方法建立哈希表,选2:以再哈希的方法建立哈希表,然后用户输入用户信息,分别以上述确定的方法分别以用户名为检索以及以以电话号码为检索将用户信息添加到哈希表,.当添加一定量的用户信息后,用户接着输入用户名或者电话号码分别以用户名或者电话号码的方式从以用户名或电话号码为检索的哈希表查找用户信息.程序用链表的方式存储信息以及构造哈希表。 具体流程图如下所示: 三: 详细设计（含代码分析） 1.程序描述: 本程序以要求使用哈希表为工具快速快速查询学生信息，学生信息包括电话号码、用户名、地址；用结构体存储 struct node { string phone; //电话号码 string name; //姓名 string address;//地址 node *next; //链接下一个地址的指针 }; 2具体步骤 1. 要求主要用在哈希法解决冲突，并且至少尝试用两种方法解决冲突，定义两个指针数组存储信息node *infor_phone[MAX]; node *infor_name[MAX];前者以电话号码为关键字检索哈希表中的信息，后者以姓名为关键字检索哈希表中的信息 用链式法和再哈希法解决冲突： int hash(string key) //以姓名或者电话号码的前四位运算结果作为哈{ //希码 int result=1,cur=0,i; if(key.size()<=4) i=key.size()-1; else i=4; for(;i>=0;i--) { cur=key[i]-'0'; result=result*9+cur; } result%=(MOD); return result; 附件4： 北京理工大学珠海学院 课程设计任务书 2010 ～2011学年第二学期 学生姓名：专业班级： 指导教师：工作部门： 一、课程设计题目 哈希表应用 二、课程设计内容（含技术指标） 【问题描述】 利用哈希表进行存储。 【任务要求】 任务要求：针对一组数据进行初始化哈希表，可以进行显示哈希表，查找元素，插入元素，删除元素，退出程序操作。 设计思想：哈希函数用除留余数法构造，用线性探测再散列处理冲突。 设计目的：实现哈希表的综合操作 简体中文控制台界面：用户可以进行创建哈希表，显示哈希表，查找元素，插入元素，删除元素。 显示元素：显示已经创建的哈希表。 查找元素：查找哈希表中的元素，分为查找成功和查找不成功。 插入元素：在哈希表中，插入一个元素，分为插入成功和失败。 删除元素：在已有的数据中，删除一个元素。 退出系统：退出程序。 【测试数据】 自行设定，注意边界等特殊情况。 三、进度安排 1．初步设计：写出初步设计思路，进行修改完善，并进行初步设计。 2．详细设计：根据确定的设计思想，进一步完善初步设计内容，按要求编写出数据结构类型定义、各算法程序、主函数。编译分析调试错误。 3．测试分析：设计几组数据进行测试分析，查找存在的设计缺陷，完善程序。 4．报告撰写：根据上面设计过程和结果，按照要求写出设计报告。 5．答辩考核验收：教师按组（人）检查验收，并提出相关问题，以便检验设计完成情况。 四、基本要求 1．在设计时，要严格按照题意要求独立进行设计，不能随意更改。若确因条件所限，必须要改变课题要求时，应在征得指导教师同意的前提下进行。 2．在设计完成后，应当场运行和答辩，由指导教师验收，只有在验收合格后才能算设计部分的结束。 3．设计结束后要写出课程设计报告，以作为整个课程设计评分的书面依据和存档材料。设计报告以规定格式的电子文档书写、打印并装订，报告格式严格按照模板要求撰写，排版及图、表要清楚、工整。 从总体来说，所设计的程序应该全部符合要求，问题模型、求解算法以及存储结构清晰；具有友好、清晰的界面；设计要包括所需要的辅助程序，如必要的数据输入、输出、显示和错误检测功能；操作使用要简便；程序的整体结构及局部结构要合理；设计报告要符合规范。 课程负责人签名： 年月日 数据结构课程设计哈希表设计问题 目录 1 前言 (1) 2 需求分析 (1) 2.1 任务和要求 (1) 2.2 运行环境 (1) 2.3 开发工具 (1) 3 分析和设计 (2) 3.1 系统分析及设计思路 (2) 3.2 主要数据结构及算法 (2) 3.3 函数流程图 (2) （1）哈希表的创建及初始化流程图 (2) 5 课程设计总结 (13) 5.1 程序运行结果或预期运行结果 (13) 说明：输入的数为30个姓的拼音，查找的为“pan”，输出的如上图所示。 (14) 5.2 设计结论 (15) 参考文献 (15) 致谢 (15) 1 前言 从C语言产生到现在，它已经成为最重要和最流行的编程语言之一。在各种流行编程语言中，都能看到C语言的影子，如Java的语法与C语言基本相同。学习、掌握C语言是每一个计算机技术人员的基本功之一。 根据本次课程设计的要求，我设计小组将编写一个C语言程序来处理哈希表问题，通过这个程序，将针对自己的班集体中的“人名”设计一个哈希表，使得平均查找长度不超过R，完成相应的建表和查表程序。 2 需求分析 2.1 任务和要求 针对自己的班集体中的“人名”设计一个哈希表，使得平均查找长度不超过R，完成相应的建表和查表程序。 要求：假设人名为中国姓名的汉语拼音形式。待填入哈希表的人名共有30个，取平均查找长度的上限为2。哈希函数用除留余数法构造，用链表法处理冲突。 2.2 运行环境 （1）WINDOWS2000/XP系统 （2）Visual C++ 6.0编译环境或TC编译环境 2.3 开发工具 C语言 3 分析和设计 3.1 系统分析及设计思路 （1）创建哈希表 （2）姓名（结构体数组）初始化 （1）用除留余数法构建哈希函数 （2）用链表法处理冲突 (3)查找哈希表 在哈希表中进行查找，输出查找的结果和关键字，并计算和输出查找成功的平均查找长度 (4) 显示哈希表 显示哈希表的的格式： 3.2 主要数据结构及算法 定义结构体typedef struct hashtable创建哈希表 定义函数Hash_Init(HashTable ht)来对哈希表初始化 定义函数Hash_Insert(HashTable ht, Node *node)来为哈希表分配地址 定义函数Hash_Init(ht)输入30个名字 定义函数Hash_Create(HashTable ht)来求哈希表长度 定义函数hash_output(HashTable h)来输出哈希表 定义函数Hash_Link()构造链表函数 定义函数int hash_search(int h[],int key)查找输入的名字 3.3 函数流程图 （1）哈希表的创建及初始化流程图 哈希表实现电话号码查询系统 一目的 利用《数据结构》课程的相关知识完成一个具有一定难度的综合设计题目，利用 C/C++语言进行程序设计，并规范地完成课程设计报告。通过课程设计，巩固和加深对线性表、栈、队列、字符串、树、图、查找、排序等理论知识的理解；掌握现实复杂问题的分析建模和解决方法（包括问题描述、系统分析、设计建模、代码实现、结果分析等）；提高利用计算机分析解决综合性实际问题的基本能力。 二需求分析 1、程序的功能 1)读取数据 ①读取原电话本存储的电话信息。 ②读取系统随机新建电话本存储的电话信息。 2)查找信息 ①根据电话号码查询用户信息。 ②根据姓名查询用户信息。 3)存储信息 查询无记录的结果存入记录文档。 2、输出形式 1)数据文件“old.txt”存放原始电话号码数据。 2)数据文件“new.txt”存放有系统随机生成的电话号码文件。 3)数据文件“out.txt”存放未查找到的电话信息。 4)查找到相关信息时显示姓名、地址、电话号码。 3、初步测试计划 1)从数据文件“old.txt”中读入各项记录，或由系统随机产生各记录，并且把记录保存 到“new.txt”中。 2)分别采用伪随机探测再散列法和再哈希法解决冲突。 3)根据姓名查找时显示给定姓名用户的记录。 4)根据电话号码查找时显示给定电话号码的用户记录。 5)将没有查找的结果保存到结果文件Out.txt中。 6)系统以菜单界面工作，运行界面友好，演示程序以用户和计算机的对话方式进行。三概要设计 1、子函数功能 int Collision_Random(int key,int i) //伪随机数探量观测再散列法处理冲突 void Init_HashTable_by_name(string name,string phone,string address) //以姓名为关键字建立哈希表 int Collision_Rehash(int key,string str) //再哈希法处理冲突 void Init_HashTable_by_phone(string name,string phone,string address) //以电话号码为关键字建立哈希表 void Outfile(string name,int key) //在没有找到时输出未找到的记录，打开文件out.txt并将记录储存在文档中void Outhash(int key) //输出哈希表中的记录 void Rafile() //随机生成数据，并将数据保存在new.txt void Init_HashTable(char*fname,int n) //建立哈希表 int Search_by_name(string name) //根据姓名查找哈希表中的记录 int Search_by_phone(string phone) //根据电话号码查找哈希表中的记录 1. 引言 哈希表（Hash Table）的应用近两年才在NOI（全国青少年信息学奥林匹克竞赛）中出现，作为一种高效的数据结构，它正在竞赛中发挥着越来越重要的作用。 哈希表最大的优点，就是把数据的存储和查找消耗的时间大大降低，几乎可以看成是常数时间；而代价仅仅是消耗比较多的内存。然而在当前可利用内存越来越多的情况下，用空间换时间的做法是值得的。另外，编码比较容易也是它的特点之一。 哈希表又叫做散列表，分为“开散列” 和“闭散列”。考虑到竞赛时多数人通常避免使用动态存储结构，本文中的“哈希表”仅指“闭散列”，关于其他方面读者可参阅其他书籍。 2. 基础操作 2.1 基本原理 我们使用一个下标范围比较大的数组来存储元素。可以设计一个函数（哈希函数，也叫做散列函数），使得每个元素的关键字都与一个函数值（即数组下标）相对应，于是用这个数组单元来存储这个元素；也可以简单的理解为，按照关键字为每一个元素“分类”，然后将这个元素存储在相应“类”所对应的地方。 但是，不能够保证每个元素的关键字与函数值是一一对应的，因此极有可能出现对于不同的元素，却计算出了相同的函数值，这样就产生了“冲突”，换句话说，就是把不同的元素分在了相同的“类”之中。后面我们将看到一种解决“冲突”的简便做法。 总的来说，“直接定址”与“解决冲突”是哈希表的两大特点。 2.2 函数构造 构造函数的常用方法（下面为了叙述简洁，设h(k) 表示关键字为k 的元素所对应的函数值）： a) 除余法： 选择一个适当的正整数p ，令h(k ) = k mod p ，这里，p 如果选取的是比较大 的素数，效果比较好。而且此法非常容易实现，因此是最常用的方法。 b) 数字选择法： 如果关键字的位数比较多，超过长整型范围而无法直接运算，可以选择其中数字分布比较均匀的若干位，所组成的新的值作为关键字或者直接作为函数值。 2.3 冲突处理 线性重新散列技术易于实现且可以较好的达到目的。令数组元素个数为S ，则当h(k)已经存储了元素的时候，依次探查(h(k)+i) mod S , i=1,2,3…… ，直到找到空的存储单元为止（或者从头到尾扫描一圈仍未发现空单元，这就是哈希表已经满了，发生了错误。当然这是可以通过扩大数组范围避免的）。 2.4 支持运算 哈希表支持的运算主要有：初始化(makenull)、哈希函数值的运算(h(x))、插入元素(i nsert)、查找元素(member)。设插入的元素的关键字为x ，A 为存储的数组。初始化比较容易，例如： const empty=maxlongint; // 用非常大的整数代表这个位置没有存储元素 p=9997; // 表的大小 procedure makenull; var i:integer; begin for i:=0 to p-1 do A[i]:=empty; End; 哈希函数值的运算根据函数的不同而变化，例如除余法的一个例子： 一,哈希表(Hashtable)简述 在.NET Framework中，Hashtable是System.Collections命名空间提供的一个容器，用于处理和表现类似key/value的键值对，其中key通常可用来快速查找，同时key是区分大小写；value用于存储对应于key的值。Hashtable中key/value键值对均为object 类型，所以Hashtable可以支持任何类型的key/value键值对. 二,哈希表的简单操作 在哈希表中添加一个key/value键值对：HashtableObject.Add(key,value); 在哈希表中去除某个key/value键值对：HashtableObject.Remove(key); 从哈希表中移除所有元素：HashtableObject.Clear(); 判断哈希表是否包含特定键key：HashtableObject.Contains(key); 下面控制台程序将包含以上所有操作： using System; using System.Collections; //使用Hashtable时，必须引入这个命名空间 class hashtable { public static void Main() { Hashtable ht=new Hashtable(); //创建一个Hashtable实例 ht.Add("E","e");//添加key/value键值对 ht.Add("A","a"); ht.Add("C","c"); ht.Add("B","b"); string s=(string)ht["A"]; if(ht.Contains("E")) //判断哈希表是否包含特定键,其返回值为true或false Console.WriteLine("the E key:exist"); ht.Remove("C");//移除一个key/value键值对 Console.WriteLine(ht["A"]);//此处输出a ht.Clear();//移除所有元素 Console.WriteLine(ht["A"]); //此处将不会有任何输出 } } 三,遍历哈希表 遍历哈希表需要用到DictionaryEntry Object，代码如下： for(DictionaryEntry de in ht) //ht为一个Hashtable实例 { Console.WriteLine(de.Key);//de.Key对应于key/value键值对key Console.WriteLine(de.Value);//de.Key对应于key/value键值对value 课程设计题目哈希表及其应用 教学院计算机学院 专业 班级 姓名 指导教师 年月日 课程设计任务书 2010 ～2010 学年第 1 学期 一、课程设计题目哈希表及其应用 二、课程设计内容 建立一个小型信息管理系统（可以是图书、人事、学生、物资、商品等任何信息管理系统）。要求： 1.使用哈希查找表存储信息； 2.实现查找、插入、删除、统计、输出等功能； 三、进度安排 1．初步完成总体设计，搭好框架； 2．完成最低要求：尝试使用多种哈希函数和冲突解决方法，并通过实际运行测试给出自己的评价 四、基本要求 1．界面友好，函数功能要划分好 2．程序要加必要的注释 3．要提供程序测试方案 教研室主任签名： 年月日 1 概述 (4) 2 设计目的 (4) 3 设计功能说明 (4) 4 详细设计说明 (5) 5 流程图 (5) 6 程序代码 (6) 7 程序运行结果 (15) 8 总结 (19) 参考文献 (19) 成绩评定表 (20) 数据结构是一门理论性强、思维抽象、难度较大的课程，是基础课和专业课之间的桥梁，只有进行实际操作，将理论应用于实际中，才能确实掌握书中的知识点。通过课程设计，不仅可以加深学生对数据结构基本概念的了解，巩固学习成果，还能够提高实际动手能力。为学生后继课程的学习打下良好的基础。 2 设计目的 《数据结构》课程设计是在教学实践基础上进行的一次大型实验，也是对该课程所学理论知识的深化和提高。因此，要求学生能综合应用所学知识，设计与制造出具有较复杂功能的应用系统，并且在实验的基本技能方面上进行一次全面的训练。通过程序的编译掌握对程序的调试方法及思想，并且让学生学会使用一些编程技巧。促使学生养成良好的编程习惯。 1.使学生能够较全面地巩固和应用课堂中所学的的基本理论和程序设计方法，能够较熟练地完成程序的设计和调试。 2.培养学生综合运用所学知识独立完成程序课题的能力。 3.培养学生勇于探索、严谨推理、实事求是、有错必改，用实践来检验理论，全方位考虑问题等科学技术人员应具有的素质。 4．提高学生对工作认真负责、一丝不苟，对同学团结友爱，协作攻关的基本素质。 5.培养学生从资料文献、科学实验中获得知识的能力，提高学生从别人经验中找到解决问题的新途径的悟性，初步培养工程意识和创新能力。 6.对学生掌握知识的深度、运用理论去处理问题的能力、实验能力、课程设计能力、书面及口头表达能力进行考核。 3 设计功能分析 本设计的功能如下： 1、利用哈希函数来实现一个小型信息管理系统，其中信息包含用户名，地址，电话等。 2、能添加用户信息，并能保存该信息。 3、查询管理系统中的信息：可通过姓名查找，也可通过电话查找等两种方式。 /* （1）设计哈希表，该表应能够容纳50个英文单词。 （2）对该哈希表进行查询，实现对特定单词的快速查询，并显示经过的节点内容 已经发到你邮箱里了enochwills@https://www.doczj.com/doc/8015644260.html, */ #include Java哈希表及其应用 哈希表也称为散列表，是用来存储群体对象的集合类结构。 什么是哈希表 数组和向量都可以存储对象，但对象的存储位置是随机的，也就是说对象本身与其存储位置之间没有必然的联系。当要查找一个对象时，只能以某种顺序（如顺序查找或二分查找）与各个元素进行比较，当数组或向量中的元素数量很多时，查找的效率会明显的降低。 一种有效的存储方式，是不与其他元素进行比较，一次存取便能得到所需要的记录。这就需要在对象的存储位置和对象的关键属性（设为k）之间建立一个特定的对应关系（设为f），使每个对象与一个唯一的存储位置相对应。在查找时，只要根据待查对象的关键属性k 计算f(k)的值即可。如果此对象在集合中，则必定在存储位置f(k)上，因此不需要与集合中的其他元素进行比较。称这种对应关系f 为哈希（hash）方法，按照这种思想建立的表为哈希表。 Java 使用哈希表类（Hashtable）来实现哈希表，以下是与哈希表相关的一些概念： ?容量（Capacity）：Hashtable 的容量不是固定的，随对象的加入其容量也可以自动增长。?关键字（Key）：每个存储的对象都需要有一个关键字，key 可以是对象本身，也可以是对象的一部分（如某个属性）。要求在一个Hashtable 中的所有关键字都是唯一的。 ?哈希码（Hash Code）：若要将对象存储到Hashtable 上，就需要将其关键字key 映射到一个整型数据，成为key 的哈希码。 ?项（Item）：Hashtable 中的每一项都有两个域，分别是关键字域key 和值域value（存储的对象）。Key 和value 都可以是任意的Object 类型的对象，但不能为空。 ?装填因子（Load Factor）：装填因子表示为哈希表的装满程度，其值等于元素数比上哈希表的长度。 哈希表的使用 哈希表类主要有三种形式的构造方法： Hashtable(); //默认构造函数，初始容量为101，最大填充因子0.75 Hashtable(int capacity); 一、问题描述 针对某个集体（比如你所在的班级）中的“人名”设计一个哈希表，使得平均查找长度均不超过R，完成相应的建表和查表顺序。 二、基本要求 假设人名为中国人姓名的汉语拼音形式。待填入哈希表的人名共有30个，取平均查找长度的上限为2。哈希函数用除留余数法构造，用伪随机探测再散列法处理冲突。 三、概要设计 1.构造结构体：typedef struct{}； 2.姓名表的初始化：void InitNameTable()； 3.建立哈希表：void CreateHashTable()； 4.显示姓名表：void DisplayNameTable()； 5.姓名查找：void FindName()； 6.主函数：void main() ； 四、详细设计 1.姓名表的初始化 void InitNameTable() { NameTable[0].py="louyuhong"; NameTable[1].py="shenyinghong"; NameTable[2].py="wangqi"; NameTable[3].py="zhuxiaotong"; NameTable[4].py="zhataotao"; NameTable[5].py="chenbinjie"; NameTable[6].py="chenchaoqun"; NameTable[7].py="chencheng"; NameTable[8].py="chenjie"; NameTable[9].py="chenweida"; NameTable[10].py="shanjianfeng"; NameTable[11].py="fangyixin"; NameTable[12].py="houfeng"; NameTable[13].py="hujiaming"; NameTable[14].py="huangjiaju"; NameTable[15].py="huanqingsong"; NameTable[16].py="jianghe"; NameTable[17].py="jinleicheng"; NameTable[18].py="libiao"; NameTable[19].py="liqi"; NameTable[20].py="lirenhua"; NameTable[21].py="liukai"; NameTable[22].py="louhanglin"; NameTable[23].py="luchaoming"; NameTable[24].py="luqiuwei"; NameTable[25].py="panhaijian"; NameTable[26].py="shuxiang"; NameTable[27].py="suxiaolei"; NameTable[28].py="sunyubo"; NameTable[29].py="wangwei"; for (i=0;i 实习6、哈希表设计 一、需求分析 1. 问题描述 针对某个集体（比如你所在的班级）中的“人名”设计一个哈希表，使得平均查找长度均不超过R，完成相应的建表和查表顺序。 2. 基本要求 假设人名为中国人姓名的汉语拼音形式。待填入哈希表的人名共有30个，取平均查找长度的上限为2。哈希函数用除留余数法构造，用伪随机探测再散列法处理冲突。 3. 测试数据 取读者周围较熟悉的30个人的姓名。 4. 实现提示 如果随机数自行构造，则应首先调整好随机函数，使其分布均匀。人名的长度均不超过19个字符（最长的人名如：庄双双（Zhuang Shuangshuang））。字符的取码方法可直接利用C 语言中的toascii函数，并可先对过长的人名先作折叠处理。 二、概要设计 ADT Hash { 数据对象D：D是具有相同特征的数据元素的集合。各数据元素均含有类型相同，可唯一标识数据元素的关键字。 数据关系R：数据元素同属一个集合。 InitNameTable() 操作结果：初始化姓名表。 CreateHashTable() 操作结果：建立哈希表。 DisplayNameTable() 操作结果：显示姓名表。 DisplayHashTable() 操作结果：显示哈希表。 FindName() 操作结果：查找姓名。 }ADT Hash 三、详细设计（源代码） （使用C语言） #include 哈希表（hashtable） 注：哈希表为1.24及以上版本才有的功能，以下版本是无法使用的说~ （在1.24之前，游戏缓存（ganecache）+return bug起到了相同的作用，124之后它们即被哈希表取代， 并且return bug在1,24之后，被修复了） 本演示侧重于hashtable，仅仅会顺带提到hashtable与gamecache两种方式的等价代码转换~ ☆哈希表的特点与优势~ 散列表（Hash table，也叫哈希表），是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。 当然这个概念可能过于深奥，我们不必了解那么深入，只需要了解它的功能以及如何使用~（当然有能力的童鞋，推荐去百度寻找详解） 先简单介绍下好了~hashtable就相当于一个存储数据的仓库，其具有容量大以及存储速度稳定的特点~ 使用hashtable与GetHandleId函数，能够非常轻易地实现一个技能的多人无冲突使用~ ☆先来认识下这货~ 首先，我们先来声明一个哈希表对象~ 由于哈希表通常起到全局范围内的数据存储以及传递~ 所以我们绝大多数情况（和所有基本没区别）都是将其作为一个全局变量来声明（几乎没有局部变量的 哈希表，只有在某些特殊需求下，才会罕见地出现；如果你明确知道自己创建局部hashtable的目的，并 且知道如何妥善掌控，那么是毫无问题的） jass globals hashtable ht=InitHashtable() //函数InitHashtable，无参数，返回一个新建的哈希表对象 //在向一个哈希表中存入数据之前，必须先通过此函数创建哈希表，否则无效（好比你无法往一个根本 不存在的容器中倒水一样的说~） endglobals 很简单，这样就创建了一个哈希表，你可以在地图中的任何地方（没错，任何地方）访问它~ Tips： （显式声明globals块（也就是上面）的方式，其实是Vjass才有的功能~如果你的编辑器UI没有这个，请 在T的变量管理器中，创建一个哈希表对象，但别忘了加上udg_前缀以及调用InitHashtable函数进行初 始化~） 然后我们可以试着，在其中存并且读取一些数据~ jass function Trig_Init_Actions takes nothing returns nothing local integer i=5 local integer ret//两个整数变量 课程设计(论文)任务书 软件学院学院软件工程专业班 一、课程设计(论文)题目：通讯录管理系统的设计与实现——哈希表 二、课程设计(论文)工作自2016 年 1 月 4 日起至 2016 年 1 月 10 日止 三、课程设计(论文) 地点: 软件测试中心（北区测试二室） 四、课程设计(论文)内容要求： 1．本课程设计的目的 ⑴训练学生灵活应用所学数据结构知识，独立完成问题分析，结合课程的理论知识，编写程序求解指定问题； ⑵初步掌握软件开发过程的问题分析、系统设计、编码、测试等基本方法和技能； ⑶提高综合运用所学的理论知识和方法独立分析和解决问题的能力，巩固、深化学生的理论知识，提升编程水平。 2．课程设计的任务及要求 1）基本要求： ⑴要求从分析题目的需求入手，按设计抽象数据类型、构思算法、通过设计实现抽象数据类型、编写上机程序和上机调试等若干步骤完成题目，最终写出完整的报告； ⑵在程序设计阶段应尽量利用已有的标准函数，加大代码的重用率； ⑶程序设计语言推荐使用C/C++，程序书写规范，源程序需加必要的注释； ⑷每位同学需提交可独立运行的程序和规范的课程设计报告。 2）课程设计论文编写要求 ⑴理论设计部分以课程设计论文的形式提交，格式必须按照课程设计论文标准格式进行书写和装订； ⑵课程设计报告包括中文目录、设计任务、需求分析、概要设计、详细设计、编码实现、调试分析、课设总结、谢辞、参考文献、附录等； ⑶设计部分应包含系统功能模块图，调试分析应包括运行截图等。 3）课程设计评分标准： ⑴学习态度：10分； ⑵系统设计：20分； ⑶编程调试：20分； ⑷回答问题：20分； ⑸论文撰写：30分。 哈希表设计数据结构课程设计 实习6、哈希表设计 一、需求分析 1. 问题描述 针对某个集体（比如你所在的班级）中的“人名”设计一个哈希表，使得平均查找长度均不超过R，完成相应的建表和查表顺序。 2. 基本要求 假设人名为中国人姓名的汉语拼音形式。待填入哈希表的人名共有30个，取平均查找长度的上限为2。哈希函数用除留余数法构造，用伪随机探测再散列法处理冲突。 3. 测试数据 取读者周围较熟悉的30个人的姓名。 4. 实现提示 如果随机数自行构造，则应首先调整好随机函数，使其分布均匀。人名的长度均不超过19个字符（最长的人名如：庄双双（Zhuang Shuangshuang））。字符的取码方法可直接利用C语言中的toascii函数，并可先对过长的人名先作折叠处理。 二、概要设计 ADT Hash { 数据对象D：D是具有相同特征的数据元素的集合。各数据元素均含有类型相同，可唯一标识数据元素的关键 字。 数据关系R：数据元素同属一个集合。 InitNameTable() 操作结果：初始化姓名表。 CreateHashTable() 操作结果：建立哈希表。 DisplayNameTable() 操作结果：显示姓名表。 DisplayHashTable() 操作结果：显示哈希表。 FindName() 操作结果：查找姓名。 }ADT Hash 三、详细设计（源代码） （使用C语言） #include #include } return -1; } //删除 void DeleteHT(HashTable ha,int p,int k,int n) { int adr; int adr2; adr2=k%p; typedef struct node { int val; node * next; }; //拉链法 node *pt,*r; adr=SearchHT(ha,p,k);//查找关键字 pt=(node*)adr; if(adr!=-1) { while(pt->val!=k) { r=pt; pt=pt->next; } if(pt->val==k) { if((int)pt==adr) { if(pt->next==NULL) ha[adr2].key=NULLKEY; else adr=(int)pt->next; } else r->next=pt->next; } ha[adr2].count--; } else printf("删除失败！"); } //插入 合肥学院 计算机科学与技术系 课程设计报告 2009 ～2010 学年第二学期 课程数据结构与算法 课程设计名称哈希表的设计与实现 学生姓名王东东 学号0804012030 专业班级08计本（2) 指导教师王昆仑、李贯虹 2010 年5 月 课程设计目的 “数据结构与算法课程设计”是计算机科学与技术专业学生的集中实践性环节之一， 是学习“数据结构与算法”理论和实验课程后进行的一次全面的综合练习。其目的是要达到 理论与实际应用相结合，提高学生组织数据及编写程序的能力，使学生能够根据问题要求和 数据对象的特性，学会数据组织的方法，把现实世界中的实际问题在计算机内部表示出来并 用软件解决问题，培养良好的程序设计技能。 一、问题分析和任务定义 1、问题分析 要完成如下要求：设计哈希表实现电话号码查询系统。 实现本程序需要解决以下几个问题： （1）如何定义一个包括电话号码、用户名、地址的节点。 （2）如何以电话号码和用户名为关键字建立哈希表。 （3）用什么方法解决冲突。 （4）如何查找并显示给定电话号码的记录。 （5）如何查找并显示给定用户名的记录。 2 任务定义 1、由问题分析知，本设计要求分别以电话号码和用户名为关键字建立哈希表，z在此基 础上实现查找功能。本实验是要我们分析怎么样很好的解决散列问题，从而建立一比较合理 的哈希表。由于长度无法确定，并且如果采用线性探测法散列算法，删除结点会引起“信息 丢失”的问题。所以采用链地址法散列算法。采用链地址法，当出现同义词冲突时，可以使 用链表结构把同义词链接在一起，即同义词的存储地址不是散列表中其他的空地址。 根据问题分析，我们可以定义有3个域的节点，这三个域分别为电话号码char num[30]，姓名char name[30]，地址char address[30]。这种类型的每个节点对应链表中的每个节点，其中电话号码和姓名可分别作关键字实现哈希表的创建。 二、数据结构的选择和概要设计 1、数据结构的选择 数据结构：散列结构。 散列结构是使用散列函数建立数据结点关键词与存储地址之间的对应关系，并提供多 种当数据结点存储地址发生“冲突”时的处理方法而建立的一种数据结构。 散列结构基本思想，是以所需存储的结点中的关键词作为自变量，通过某种确定的函 数H（称作散列函数或者哈希函数）进行计算，把求出的函数值作为该结点的存储地址，并 将该结点或结点地址的关键字存储在这个地址中。 散列结构法（简称散列法）通过在结点的存储地址和关键字之间建立某种确定的函数 关系H，使得每个结点（或关键字）都有一个唯一的存储地址相对应。 当需要查找某一指定关键词的结点时，可以很方便地根据待查关键字K计算出对应的“映像”H(K)，即结点的存储地址。从而一次存取便能得到待查结点，不再需要进行若干次的 比较运算，而可以通过关键词直接计算出该结点的所在位置。哈希表的设计与实现 课程设计报告
哈希表应用
数据结构课程设计哈希表设计问题复习过程
哈希表实现电话号码查询系统
散列表(哈希表)
哈希表基本操作
哈希表及其应用-课程设计
哈希表查询设计及实现
Java哈希表及其应用
数据结构哈希表设计
哈希表设计-数据结构课程设计
哈希表
数据结构课设-通讯录系统的设计与实现——哈希表
哈希表设计数据结构课程设计
哈希表拉链法
哈希表的设计与实现-数据结构与算法课程设计报告
相关主题
文本预览