算法分析与设计及案例习题解析

1、习 题 解 析第1章1. 解析：算法主要是指求解问题的方法。计算机中的算法是求解问题的方法在计算机上的实现。2. 解析：算法的五大特征是确定性、有穷性、输入、输出和可行性。3. 解析：计算的算法，其中n是正整数。可以取循环变量i的值从1开始，算i的平方，取平方值最接近且小于或者等于n的i即可。4. 解析：可以使用反证法，设i=gcd(m, n)=gcd(n, m mod n)，则设m=a*i，n=b*i，且a与b互质，这时m mod n=（a-x*b）*i，只需要证明b和a-x*b互质，假设二者不互质，可以推出a与b不互质，因此可以得到证明。5. 解析：自然语言描述：十进制整数转换为二进制整数

2、采用“除2取余，逆序排列”法。具体做法是：用2整除十进制整数，可以得到一个商和余数；再用2去除商，又会得到一个商和余数，如此进行，直到商为0时为止，然后把先得到的余数作为二进制数的低位有效位，后得到的余数作为二进制数的高位有效位，依次排列起来。流程图：如图*.1图*.1 十进制整数转换成二进制整数流程图6. 解析：a.如果线性表是数组，则可以进行随机查找。由于有序，因此可以进行折半查找，这样可以在最少的比较次数下完成查找。b.如果线性表是链表，虽然有序，则只能进行顺序查找，从链表头部开始进行比较，当发现当前节点的值大于待查找元素值，则查找失败。7. 解析：本题主要是举例让大家了解算法的精确性。

3、过程中不能有含糊不清或者二义性的步骤。大家根据可行的方式总结一下阅读一本书的过程即可。8. 解析：数据结构中介绍的字典是一种抽象数据结构， 由一组键值对组成， 各个键值对的键各不相同， 程序可以将新的键值对添加到字典中， 或者基于键进行查找、更新或删除等操作。由于本题已知元素唯一，因此大家可以据此建立一个自己的字典结构。实现字典的方法有很多种： 最简单的就是使用链表或数组， 但是这种方式只适用于元素个数不多的情况下； 要兼顾高效和简单性，可以使用哈希表； 如果追求更为稳定的性能特征， 并且希望高效地实现排序操作的话， 则可以使用更为复杂的平衡树。在字典之上的主要操作可以有：创建操作，添加操作，

4、删除操作，查找操作，以及必要的字典维护操作。第2章1. 解析：根据本章所述，递归算法和非递归算法的数学分析方法分为5个步骤。2. 解析： 本题相当于对多项式找“主项”，也就是在除去常系数外，影响函数值递增速度最快的项。a)b)c) ，c为常数d)e)3. 解析：本题中如果手套分左右手，则最优情况选2只，最差情况选12只。本题中如果手套不分左右手，则最优情况仍然选2只，最差情况选4只。从本题的初衷推测设置题目应该是分左右手的手套，在考虑颜色的情况下，选择一双进行匹配。4. 解析： 本题的一般解法可以使用高等数学中求二者比值的极限来确定结果。 a) 相同 b) 第一个小 c) 二者相同 d) 第一

5、个大 e) 二者相同 f) 第一个小5. 解析：a) b) c) d) 6. 解析：参见本章例2.7。第3章1. 解析：蛮力法主要依靠问题的定义，采用简单直接的求解方法。由此决定了蛮力法是解决问题的最简单也是最普遍的算法，同时其经常作为简单问题求解的方法和衡量其他算法的依据。2. 解析： 2，6，1，4，5，3，2选择排序：|2614532i=0: min最后得2，交换二者。1|624532i=1: min最后得2，交换二者。12|64532i=2: min最后得6，交换二者。122|4536i=3: min最后得5，交换二者。1223|546i=4: min最后得5，交换二者12234|56

6、i=5: min最后得5。122345|6结束。冒泡排序：2614532214532|6i=0: 最大值6就位。12432|56i=1：第二大值5就位。1232|456i=2：第三大值4就位。122|3456i=3：第四大值3就位。12|23456i=4：第五大值2就位。1|223456i=5：第六大值2就位，剩余的1也就位，排序结束。3. 解析：选择排序不稳定，如3.1.1节例子：4,4,2。冒泡排序稳定。4. 解析：如2题例子，到i=4时就没有发生交换的活动了。这时可以在冒泡排序的交换部分加入一个布尔变量，如本次循环中没有发生交换，则以后的扫描就可以不进行。5. 解析：如果n个点共线，则其

7、最近对只需要考察相邻的点对，因此在对点进行按行坐标排序后，只需要两两计算相邻两点距离，就可以找到最近对。6. 解析：所有的过程与寻找二维空间中的最近点对类似，只是计算距离的公式变为：sqrt(p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y)+(p1.z-p2.z)*(p1.z-p2.z)使用循环计算任意两个点之间的距离，然后记录最小值即可。类似的，如果推广到n维空间，需要考虑空间中任意两点的距离计算公式，同样计算每两个点之间的距离，并记录最小距离即可。7. 解析：a) 线段的凸包为本身，极点为两个端点。b) 正方形的凸包为本身，极点为四个顶点。c)

8、正方形的边界不是凸包，凸包为正方形（包括边界和内部）。d) 直线的凸包为本身，没有极点。8. 解析：哈密顿回路的穷举查找算法，首选选择起点（图中任意一个点开始），之后不断寻找下一个点，下一个点应该满足：1) 不在已经走过的点中；2) 与上一个点有直连路径。如果这样能找到回到起点的路径，并且遍历所有点，则为一条哈密顿回路。然后依次进行下一个可行点的选择。9. 解析：生成给定元素的一个排列，通过连续比较它们之间的元素，检查它们是否符合排序的要求。如果符合就停止，否则重新生成新的排列。最差情况生成排列的个数是，每趟连续元素比较次数为n-1次。所以效率类型为。第4章1. 解析：假定把16枚硬币上网例子

9、看作一个大的问题。（1）把这一问题分成两个小问题，随机选择8个硬币作为第一组称为A组，剩下的8个硬币作为第二组称为B组；这样，就把16个硬币的问题分成两个8个银币的问题来解决；（2）判断A组和B组中是否有伪币，可以使用仪器比较A组硬币和B组硬币的重量；假如两组硬币重量相等，则可以判断伪币不存在；假如两组硬币重量不相等，则存在伪币，并且可以判断它位于较轻的那一组硬币中；（3）假设B是轻的那一组，因此再把它分成两组，每组有4个硬币，称其中一组为B1，另一组为B2，比较这两组，肯定有一组轻一些，假设B1轻，则伪币在B1中，再将B1分为两组，每组有两个硬币，称其中一组为B1a,另一组为B1b。比较这两

10、组，可以得到一个较轻的组，由于这个组织有两个硬币，因此不必再细分。比较组中两个硬币的重量，可以立即知道哪个硬币轻一些，轻币就是要找的伪币；最终，比较次数为4次。2. 解析：逆序对是指在序列a0,a1,a2.an中，若aij)，则(ai,aj)上一对逆序对。而逆序数是指序列中逆序对的个数。例如： 1 2 3是顺序，则逆序数是0；1 3 2中(2,3)满足逆序对的条件，所以逆序数只有1； 3 2 1中(1,2)(1,3)(2,3)满足逆序对，所以逆序是3。由定义不能想象，序列n的逆序数范围在0,n*(n-1)/2，其中顺序时逆序数为 0，完全逆序时逆序数是n*(n-1)/2。对于一个数组s将其分为

11、2个部分s1和s2，求s1和s2的逆序对个数，再求s1和s2合并后逆序对的个数：这个过程与merge排序的过程是一样的，可以使用merge排序求得。代码如下：/a为字符数组，len为字符数组的长度int number = 0; /number表示逆序对的个数void copy(char *dest, char *src, int l, int r)while(l = r) destl = srcl; l+; void mergeSort(char *a, int size)char *b = (char*)malloc(sizeof(char) * size);mergePass(a, b,

12、0, size - 1);free(b);void mergePass(char *a, char *b, int l, int r) int m; if(l r) m = (l + r) / 2; mergePass(a,b,l,m); mergePass(a,b,m+1,r); merge(a,b,l,m,r); copy(a,b,l,r);void merge(char *a, char *b, int l, int m, int r)int i = l, j = m + 1;while( i = m & j = r) if(ai = aj) bl+ = ai+; else bl+ =

13、aj+;number += m-i+1; while(i = m) bl+ = ai+; while(j 2时，先求出序列A1.n-1中的第1大元素x1和第2大元素x2；然后，通过2次比较即可在三个元素x1，x2和An中找出第2大元素，该元素即为A1.n中的第2大元素。SecondElement (Alow.high, max1, max2) /假设主程序中调用该过程条件为high-low=2 if(high-low=2) if(AlowAhigh) max2=Alow; max1=Ahigh; else max2=Ahigh; max1=Alow; else SecondElement (A

14、low . high,x1,x2); if(x1=An) max2=x2; max1=x1; else max2=An; max1=x1; 该算法的时间复杂度满足如下递归方程：T(n)=T(n-1)+2; T(2)=1。解得T(n)=2n-3。4. 解析：如果在算法SELECT执行中每次标准元素都恰好选取的是序列中的真正中值元素，那算法的行为与二分查找算法类似。最坏情况下，每次在原序列的一半上进行查找。此时如果标准元素得到时间为T（n）；如果标准元素得到时间为T（1），则算法的最坏情况时间与二分检索一样，为T（logn）。5. 解析：对于两棵二叉树T1和T2，若其根结点值相同，且其左右子树分别

15、对应相同，则T1=T2，否则T1T2。其描述如下：Boolean BTEQUAL(BT T1, BT T2) if(T1= =NULL&T2=NULL) return True; /均为空树 if(T1&T2&T1.data=T2.data&BTEQUAL(T1.lchild,T2.lchild) &BTEQUAL (T1.lchild,T2.lchild) return True; return False;6. 解析：快速分类算法是根据分治策略设计出来的算法。其关键步骤就是“划分”：根据某个元素v为标准，将序列中的元素重新整理，使得整理后的序列中v之前的元素都不大于v，而v之后的元素都不小

16、于v。此时，元素v即找到了其最终的位置。要得到序列的排序结果，再只需对v之前的元素和v之后的元素分别排序即可，这可通过递归处理来完成。7. 解析：当序列中的元素都相同时，每次执行算法SPLIT时，仅出现一次元素交换，即将序列的第一个元素与最后一个元素交换，且划分元素的新位置为该序列的最后一个位置。因此，在元素均相同的数组A1.n上，算法QUICKSORT的执行特点为：每次划分后剩下A1.n-2未处理，第n-1此划分后剩下A1（已有序）。在这类实例上，算法的执行时间为：(n-1)+(n-2)+2+1=(n2)，属于最坏的情况。此外，算法最后所得结果中各元素顺序如下：A2,A3,A4,An,A1（

17、这里，Ai表示输入时的第i个元素，i=1,2,n）。8. 解析：算法QUICKSORT所需要的工作空间是指其递归执行时所需要的栈空间，其大小与递归调用的深度成比例。考虑算法在n个元素上执行时的递归调用树，树最高可为T(n)，最矮可为T(logn)。所以，算法所需的工作空间在T(logn)到T(n)之间变化。第5章1. 解析：0个元素的幂集为空集；1个元素的幂集为空集和本身；（可以看做空集并空集加入元素的集合）2个元素的幂集为1个元素的幂集和该幂集中每个集合加入新元素的集合的并集；类似的继续下去可以生成n个元素的幂集。2. 解析：插入排序：2，6，1，4，5，3，22|614532i=1：A1插

18、入26|14532i=2：A2插入126|4532i=3：A3插入1246|532i=4：A4插入12456|32i=5：A5插入123456|2i=6：A6插入1223456|结束3. 解析：对照给出的算法，进行链表插入排序。这时，每次进行插入时均需要从链表头部节点开始，寻找插入位置。因此要设置相邻的两个指针，用于寻找插入位置。具体请大家自己完成。4. 解析：折半插入排序：/输入：待排序数组A0.n-1/输出：排好序后的数组A0.n-1void ISort(&A0.n-1)/* v用来保存待插入元素；s, t, k 分别是插入位置寻找时使用的指针，s指向头，t指向尾，k指向中间。*/for(

19、i=1; i=s & vAk)if(vAk)s=k+1;k=;elset=k-1;k=;if(Ak=k; j-)Aj+1 = Aj;Ak = v;；最差效率为：。5. 解析：用减一法进行拓扑排序，每次删除入度为0的结点即可，所有可能情况共有7种：d-a-b-c-g-e-f；d-a-b-c-g-f-e；d-a-b-g-c-e-f；d-a-b-g-c-f-e；d-a-c-b-g-e-f；d-a-c-b-g-f-e；d-a-b-g-e-c-f。同样，可以用深度优先遍历时，出栈顺序的逆序作为拓扑排序。6解析：字典序列算法是一种非递归算法。而它正是STL中Next_permutation的实现算法。它的

20、整体思想是让排列成为可递推的数列，也就是说从前一状态的排列，可以推出一种新的状态，直到最终状态。比如说，最初状态是12345，最终状态是54321。其实我觉得这跟我们手动做全排列是一样的。首先是12345，然后12354，然后12435，12453.逐渐地从后往前递增。看看算法描述： 首先，将待排序列变成有序（升序）序列。然后，从后向前寻找，找到相邻的两个元素，TiTi(很多时候k=j)，找到它，交换Ti跟Tk，并且将Tj到Tn(Tn是最后一个元素)的子序列进行倒置操作。输出此序列。并回到第二步继续寻找ij。例如839647521是数字19的一个排列。从它生成下一个排列的步骤如下：自右至左找出

21、排列中第一个比右边数字小的数字4 839647521在该数字后的数字中找出比4大的数中最小的一个5 839647521将5与4交换 839657421将7421倒转 839651247所以839647521的下一个排列是839651247。839651247的下一个排列是839651274。以下是C语言的代码：#include #define MAX 1000int n=4; int setMAX=1,2,3,4;int flag=0;/swap a and bvoid s *a,int *b) int temp=*a; *a=*b; *b=temp;/reverse a range of a

22、 setvoid reverse(int start,int end) int index_r=0; int new_end=end-start; for(index_r=0;index_r=new_end/2;index_r+) sindex_r+start,&setnew_end-index_r+start);void set_print() int index; for(index=0;index0;index_i-) if(setindex_i0;index_k-) if(setindex_ksetindex_i) break; sindex_i,&setindex_k); rever

23、se(index_j,n-1); find_next();int main() int count=1; int i=n-1; while(i=0) set0=count+; find_next(); s0,&seti); reverse(1,n-1); i-; return 0;7. 解析：说到汉诺塔问题，首先想到的是最经典的递归解法。在求格雷码的方法中，提到可以观察格雷码每一次改变的位数和汉诺塔每次移动的盘子的编号，从而产生一种不需要递归和堆栈的汉诺塔解法。在生成格雷码的算法中，依次改变的位数是最低位和从右往左数第一个1所在位的左一位，对应汉诺塔的盘子就是最小的盘子和中间某个盘子。最小的盘

24、子有两种可能的移动方案，其他的盘子只有一种可能。对于最小盘子移动到的柱子的解决方法是，根据观察，当盘子总数是奇数时，最小盘子的位置依次是“3-2-1-3-2-1.”；当总数是偶数时，这个顺序是“2-3-1-2-3-1.”。据此从格雷码到汉诺塔的一种对应解决方案就产生了。如下是非递归方法的代码。int main()char digitMAX; int positionMAX; int i,j; for(i = 0; i 20) break; if(even) coutposition0circleiendl; position0 = circlei; i = (+i)%3; FLIP_DIGIT

25、(digit0); else for(j = 0 ; j n & digitj=0; j+) ; if(j = n-1) break; FLIP_DIGIT(digitj+1); coutpositionj+16-positionj+1-position0endl; positionj+1 = 6-positionj+1-position0; FLIP(even); cout=endl; system(pause); return 0;8. 解析：nm5234266813136 6272+136 3544 11088+544+1361768=1088+544+1369. 解析：顺序查找的平均效

26、率约为：。最高效的排序算法其效率为：。因此，如果只做一次查找，不需要进行排序后再折半查找。10. 解析： 构造2-3树的数据结构。之后建立插入节点和分裂的算法。第6章1. 解析：以所经过的权值之和最大值为例进行说明。行进的过程中，每次只有两种选择：向左或向右。一个有n层的数字三角形的完整路径有2n条，所以当n比较大的时候，搜索全部路径，从中找出最大值，效率较低。采用动态规划方法实现。用d(i,j)表示从位置(i,j)出发时得到的最大值（包括位置(i,j)本身），可以写出最大值的递归方程：由于递归方程中包含了重复子问题，直接采用递归方程求解， 效率较低。采用动态规划的备忘录方法，用一张二维表记录

27、中间过程的值，可以把时间效率提高到n2。2. 解析：采用动态规划方法实现。用fi表示以ai为结尾的最长上升子序列的长度，可建立如下递归方程： f是单调递增的，因为如果有i=fj，那么fi必定可以被fj的内容所更新。每处理到一个ai，要找到一个k满足fk1= ai，并用ai更新fk，最终maxk|fk!=就是答案。可以编写出时间复杂度为O(n2)的动态规划算法。3. 解析：用sumi,j表示将从第i颗石子开始的接下来j颗石子合并所得的分值。用fi,j表示将第从第i颗石子开始的接下来j颗石子合并所得的重量的最小值。有如下递归方程：可以编写出时间复杂度为O(n3)的动态规划算法。如果采用四边形不等式

28、优化动态规划算法，可得到时间复杂度为O(n2)的动态规划算法，是一种比较高效的优化算法。4. 解析：按照动态规划求解多阶段决策的思路，每投资一个项目作为一个阶段，将原问题划分阶段，从而将静态模型转化为动态。用xk(k=1,2,3)表示第k个项目的投资额，其中用sk表示投资第k个项目前的资金数(k=1,2,3,4，k=4为虚设的阶段)，则有0xksk 以及sk+1 = sk -xk 成立。用vk(sk, xk)表示在当前在资金数为sk，投资额为xk的情况下的投资效益值。为便于理解，如下图所示表示各阶段内容。效益值v3(s3, x3)效益值v2(s2, x2)效益值v1(s1,x1)s3s2s1x

29、3x2x1 项目1 项目2 项目3s4投资效益阶段表示图根据以上分析，可写出求解问题的递归式和特殊值： 采用逆序倒推的方法，先计算在第三阶段，即投资项目3时的最大效益，再考虑第二阶段，即投资项目2时的最大效益，此时利用递归公式，其最大效益的获得是在所有在第二阶段的当前效益与第三阶段最大效益的累加和中求取最大值，同样方法获取第一阶段的最大效益。5. 解析：利用高斯公式，从1到n的自然数之和为：1+2+3+n=n*(n+1)/2。题目要求：对于从1到N的连续整集合，划分为两个子集合，且保证每个集合的数字和是相等的。因而，划分之后每个子集全的数字应该为n*(n+1)/2的一半，即n*(n+1)/4由

30、于两个子集中都是整数，所以n*(n+1)必为偶数，则可以设s=n*(n+1),并判断s%4 ，则，s/=4是划分之后子集合的数字和。dynj数组表示任意个数加起来等于j的组数，则有下面公式成立：dynj= dynj+dynj-i; 其中dynj-i表示加起来等于j-i的组数，利用上述公式，可得到问题的解。6. 解析：按照样例输入：即3 42 -1 50 51 3 -1 6-1 8 9 10则表示迷宫如下：ai,j保存第i行第j列的宝藏价值。令fi,j为从（1，1）走过第i行第j列时所能收集的宝藏的最大价值。有如下递归方程：同时满足：ai,j-1初始 采用动态规划算法，利用递推公式构造并求解二维

31、表fi,j，目标即求解出fn,m即可。7. 解析：按照样例输入如下：5 6 44 3 4 4 5ai表示第i首歌曲的长度。令fi,j,k表示前i首歌曲，用j张光盘，另加k分钟能够发行的最多歌曲树木。有如下递归方程： 采用动态规划算法，利用递推公式构造并求解二维表fi,j,k，目标即求解出fn,m,0或fn,m-1,t即可。8. 解析：按照样例输入如下：ACDEFABCDE令fi,j为将A的前i个字符变成B的前j个字符所用的最少操作步数。从后向前依次比较分析，fi,j有以下三种情况；(1)删除A 中的前i-1 个字符中的最后一个字符，问题变为将A 中前i-1 个字符转换为B 中的前j 个字符，即

32、：fI,j=fi-1,j+1;(2)在A 的前i-1 个字符中的最后插入一个字符，插入后使ai+1=bj，问题变为将A 中的前i 个字符转换为B 中的前j-1 个字符，即：iI,j=fi,j-1+1;(3)将A 中的一个字符转换为另一个字符。如果ai=bj，则fi,j=fi-1,j-1如果aibj，将ai 换成bj；则fi,j=fi-1,j-1+1综上所述，有如下递归方程：初始 采用动态规划算法，利用递推公式构造并求解二维表fi,j，目标即求解出fn,m即可。第7章1. 解析：由待排序数据可知，最小值为92，最大值为98，由此可创建一个长度为7的数组C，Ci（-1i0&PatternLengt

33、h0&i=0 & Patternj=Texti+j)/从右向左匹配j-;if(j=-1)/在文本中找到了模式，返回对应位置return i;else/本轮匹配失败，模式右移printf(n模式第%d次移动距离：%d,count+1,DiscTexti+PatternLength-1-A);i=i+DiscTexti+PatternLength-1-A;count+;return -1;/在完成所有轮次匹配后，文本中没有出现模式，返回-1void main()char Text80=FAILUREEISATHEBMOTHERCCFDSUCCESS;/定义文本char Pattern80=SUCC

34、E;/定义并初始化模式int n;/定义模式在文本中的位置int i;for(i=0;i-1)printf(n模式在文本中的位置是：%d,n+1);elseprintf(n模式没有在文本中出现!);printf(n模式共向右移动了%d次！n,count);4. 解析：C语言中的关键字为：auto、break、case、char、const、continue、default、do、double、else、enun、extern、float、for、goto、if、int、long、register、return、short、signed、sizeof、static、struct、switch、t

35、ypedef、union、unsigned、void、volatile、while各记录的散列地址如下：f(auto)=1、f(break)=2、f(case)=3、f(char)=3、f(const)=3、f(continue)=3、f(default)=4、f(do)=4、f(double)=4、f(else)=5、f(enum)=5、f(extern)=5、f(float)=6、f(for)=6、f(goto)=7、f(if)=9、f(int)=9、f(long)=12、f(register)=18、f(return)=18、f(short)=19、f(signed)= 19、f(siz

36、eof)= 19、f(static)= 19、f(struct)= 19、f(switch)= 19、f(typedef)=20、f(union)=21、f(unsigned)=21、f(void)=22、f(volatile)=22、f(while)=23散列表如下：散列地址123456789记录指针记录autobreakcasedefaultelsefloatgotoNULLif记录NULLNULLchardoenumforNULLint记录constdoubleexternNULLNULL记录continueNULLNULL记录NULL散列地址1011128记录指针记录NULLNULLl

37、ongNULLNULLNULLNULLNULLregister记录NULLreturn记录NULL散列地址19226记录指针记录shorttypedefunionvoidwhileNULLNULLNULL记录signedNULLunsignedvolatileNULL记录sizeofNULLNULL记录static记录struct记录switch记录NULL平均查找长度=（115+29+34+42+51+61）/262.465. 解析：#includestdio.h#includestring.h#define RecordNum 32/定义记录个数#define HashTableNum 3

38、2/定义散列表大小struct HashType/定义记录类型char str80;struct HashType *next;int count=0;/定义查找次数/定义并初始化记录数据struct HashType HashDataRecordNum= auto,NULL,break,NULL,case,NULL,char,NULL,const,NULL,continue,NULL,default,NULL,do,NULL,double,NULL,else,NULL,enum,NULL,extern,NULL,float,NULL,for,NULL,goto,NULL,if,NULL,in

39、t,NULL,long,NULL,register,NULL,return,NULL,short,NULL,signed,NULL,sizeof,NULL,static,NULL,struct,NULL,switch,NULL,typedef,NULL,union,NULL,unsigned,NULL,void,NULL,volatile,NULL,while,NULL;int HashAddressHashTableNum;/定义散列地址数组struct HashType *HashTableHashTableNum;/定义散列表数组struct HashType *p,*q;/定义搜索链表

40、指针void CalculateHashAddress()/根据散列函数计算各记录散列地址,散列函数：f(s)int i,j,HashSumTemp;for(i=0;iRecordNum;i+)HashAddressi=HashDatai.str0-a+1;void CalculateHashTable()/将各记录的指针分布到散列表中int i;for(i=0;iHashTableNum;i+)/初始化散列表HashTablei=NULL;for(i=0;inext;q-next=&HashDatai;/查找记录时，先计算其散列地址int CalculateSearchRecordHashAddress(char record)return record0-a+1;void SearchRecord()/根据散列地址判断待查找记录的有无char record80;int SearchRecordHashAddress;printf(n请输入待查找的记录：);gets(record);SearchRecordHashAddress=Calcul