1、2022-7-26 查找也叫检索，是根据给定的某个值，在表中确定一个关键字等于给定值的记录或数据元素 关键字是数据元素中某个数据项的值，它可以标识一个数据元素 查找方法评价 查找速度 占用存储空间多少 算法本身复杂程度 平均查找长度ASL(Average Search Length)：为确定记录在表中的位置，需和给定值进行比较的关键字的个数的期望值个元素所需比较次数为找到表中第个元素的概率，为查找表中第其中：个记录的表，对含有icpipcpASLniniiiniii111基本概念:2022-7-26 查找成功在查找表中找到关键字值等于给定值的记录。查找失败 对查找表常进行的操作：查询某个“特定
2、的”数据元素是否在查找表中检索某个“特定的”数据元素的各种属性在查找表中插入一个数据元素从查找表中删除某个元素静态查找表：对查找表只前两种“查找”操作动态查找表：对查找表要进行后两种“查找”操作2022-7-26 一 顺序查找（线性查找）查找过程：从表的一端开始逐个进行记录的关键字和给定值的比较 算法描述i例 0 1 2 3 4 5 6 7 8 9 10 11 5 13 19 21 37 56 64 75 80 88 92找6464监视哨iiii比较次数=5比较次数：查找第n个元素：1查找第n-1个元素：2.查找第1个元素：n查找第i个元素：n+1-i查找失败：n+18.1 静态查找表2022
3、-7-26typedef int KeyType;typedef float ElemType;typedef struct KeyType key;/记录的关键字 ElemType info;/记录的其他信息JD;int seqsrch(JD r,int n,KeyType k)/设置监视哨的算法 int i=n;r0.key=k;while(ri.key!=k)i-;return(i);2022-7-26int seqsrch(JD r,int n,KeyType k)/未设置监视哨 int i=0;while(i=n)return(-1);else return(i);2022-7-26
4、 顺序查找方法的ASL212)1(11111nnnnincpASLnpniniiii则概率相等设表中每个元素的查找niiicpASLn1个记录的表，对含有2022-7-26 二 折半查找 查找过程：每次将待查记录所在区间缩小一半 适用条件：顺序存储结构查找表按关键字排序 算法实现 设表长为n，low、high和mid分别指向待查元素所在区间的上界、下界和中点，k为给定值 初始时，令low=1,high=n,mid=(low+high)/2 让k与mid指向的记录比较 若k=rmid.key，查找成功 若krmid.key，则low=mid+1 重复上述操作，直至lowhigh时，查找失败202
5、2-7-26 算法描述lowhighmid例 1 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92找211 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92lowhighmid1 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92lowhighmid2022-7-26例 1 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92lowhighmid找701 2 3 4 5 6 7
6、8 9 10 115 13 19 21 37 56 64 75 80 88 92lowhighmid1 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92low highmid1 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92lowhighmid2022-7-261 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92lowhigh1185210741936判定树：1 2 3 4 5 6 7 8 9 10 115 13 19 21
7、37 56 64 75 80 88 926指在查找表中的位置r6，查找范围为r1r1110指在查找表中的位置r10，查找范围为r10r11注：注：判定树的形态只与表记录个数判定树的形态只与表记录个数n n有关，与记录的内容无关。有关，与记录的内容无关。2022-7-26int BinSearch(JD r,int n,KeyType k)int low,high,mid,found;low=1;high=n;found=0;while(lowrmid.key)low=mid+1;else if(khith)return-1;else mid=(low+high)/2;if(k=rmid.key
8、)return mid;else if(krmid.key)return(BinSearch(r,mid+1,high,k);else return(BinSearch(r,low,mid-1,k);2022-7-268.2 动态查找表 动态查找表的特点：表结构本身是在查找过程中动态生成的，即对于给定值key，若表中存在其关键字等于key的纪录，则返回查找成功，否则插入关键字等于key的纪录。本节主要介绍二叉排序树和平衡二叉树的有关概念和查找分析2022-7-26 定义：二叉排序树或是一棵空树，或是具有下列性质的二叉树：若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值 若它的右子树
9、不空，则右子树上所有结点的值均大于或等于它的根结点的值 它的左、右子树也分别为二叉排序树 二叉排序树的插入 插入原则：若二叉排序树为空，则插入结点应为新的根结点；否则，继续在其左、右子树上查找，直至某个叶子结点的左子树或右子树为空为止，则插入结点应为该叶子结点的左孩子或右孩子 二叉排序树生成：从空树出发，经过一系列的查找、插入操作之后，可生成一棵二叉排序树2022-7-26 插入算法例 10，18，3，8，12，2，7，310101810183101838101838 12101838 122101838 1227101838 12273中序遍历二叉排序树可得到一个关键字的有序序列2022-7
10、-26 二叉排序树的删除要删除二叉排序树中的p结点，分三种情况：p为叶子结点，只需修改p双亲f的指针f-lchild=NULL f-rchild=NULL p只有左子树或右子树 p只有左子树，用p的左孩子代替p (1)(2)p只有右子树，用p的右孩子代替p (3)(4)p左、右子树均非空 沿p左子树的根C的右子树分支找到S，S的右子树为空，将S的左子树成为S的双亲Q的右子树，用S取代p (5)若C无右子树，用C取代p (6)2022-7-26SQPLP中序遍历：Q S PL PSQPL中序遍历：Q S PL(2)SPPLQ中序遍历：PL P S QSPLQ中序遍历：PL S Q(1)2022-
11、7-26中序遍历：P PR S QSPRQ中序遍历：PR S Q(3)SPPRQ中序遍历：Q S P PRSQPR中序遍历：Q S PR(4)SQPRP2022-7-26FPCPRCLQQLSSL中序遍历：CL C QL Q SL S P PR FFSCPRCLQQLSL中序遍历：CL C QL Q SL S PR F(5)FPCPRCL中序遍历：CL C P PR FFCPRCL中序遍历：CL C PR F(6)2022-7-26 删除算法例805012060110150557053删除508060120110150557053删除60805512011015053701042581354删
12、除1084255134删除58425413二叉排序树的查找分析在二叉树上查找一个关键字的过程，恰是走了一条从根节点到该节点的路径，因此与给定值比较的次数不超过树的深度。对相同数的集合构成的二叉排序树因为根节点不同而造成平均查找长度不同。452453371293ASL=(1+2*2+3*3)/6=14/6122437455393ASL=(1+2+3+4+5+6)/6=21/62022-7-26含有n个节点的二叉排序树的平均查找长度和树的形态有关。若插入的关键字有序时，构成的二叉排序树蜕变成单支树，其平均查找长度为(n+1)/2。最好的情况为二叉排序树的形态和折半查找的判定树相同，其平均查找长度和
13、log2n成正比。要想使任何的关键字的集合构成的二叉排序树的平均查找长度均达到log2n数量级，需对二叉排序树进行“平衡化”处理，成为平衡二叉树。2022-7-26 平衡二叉树或者是一棵空树，或者具有以下性质：左子树和右子树的深度之差的绝对值不超过1；它的左子树和右子树又分别是平衡二叉树。二叉树节点的平衡因子BF：该节点的左子树深度减去右子树的深度。BFBalance Factor所以平衡二叉树的平衡因子只可能为-1，0，1。否则不能成为平衡二叉树。2022-7-26下面举例说明构成平衡二叉树的过程:有关键字序列（13，24，37，90，53），生成平衡二叉树：空（a）013024-11303
14、7-124-2130370240132022-7-26-137-124013090(1)(2)-237-224013190053-237-224013-153090(3)053-124013090037(4)2022-7-26若插入结点使平衡二叉树失去平衡的最小子树根结点指针为a,则:由于在*a的左子树根节点的左子树上插入接点，*a的平衡因子 由1增到2，致使以*a为根的子树失去平衡，则需要进行一次向右 的顺时针旋转操作。(LL型型)由于在*a的右子树根节点的右子树上插入接点，*a的平衡因子 由-1变为-2，致使以*a为根的子树失去平衡，需要进行一次向左 的逆时针旋转操作。(RR型型)由于在*
15、a的左子树根节点的右子树上插入接点，*a的平衡因子 由1变为2，致使以*a为根的子树失去平衡，需要进行两次旋转操 作（先左后右）。(LR型型)由于在*a的右子树根节点的左子树上插入接点，*a的平衡因子 由-1变为-2，致使以*a为根的子树失去平衡，需要进行两次旋转 操作（先右后左）。(RL型型)调整的原则：一是满足平衡二叉树的要求；调整的原则：一是满足平衡二叉树的要求；二是保持排序二叉树的性质二是保持排序二叉树的性质2022-7-26 (1)LL型调整型调整LL型调整规则将A的左子女B提升为新二叉树的根；原来的根A连同其右子树向右下旋转成为B的右子树；B的原右子树作为A的左子树。2022-7-
16、26 (2)RR型调整型调整RR型调整规则：将A的右子女B提升为新二叉树的根；原来的根A连同其左子树向左下旋转成为B的左子树；B的原左子树作为A的右子树。2022-7-26 (3)LR型调整型调整LR型调整规则：设C为A的左子女的右子女，将A的孙子结点C提升为新二叉树的根；原C的父结点B连同其左子树向左下旋转成为新根C的左子树，原C的左子树成为B的右子树；原根A连同其右子树向右下旋转成为新根C的右子树，原C的右子树成为A的左子树。2022-7-26 (4)RL型调整型调整 RL型调整规则：设C为A的右子女的左子女，将A的孙子结点C提升为新二叉树的根，原来C的父结点B连同其右子树向右下旋转成为新
17、根C的右子树，C的原右子树成为B的左子树；原来的根A连同其左子树向左下旋转成为新根C的左子树，原来C的左子树成为A的右子树。2022-7-26如：如：输入关键字序列输入关键字序列16,3,7,11,9,26,18,14,15,给出构给出构造一棵造一棵AVL树的步骤。树的步骤。16 0(a)插插入入 16 16 1(b)插插入入 3 3 0 16 2(c)插插入入 7 3-1 7 0 7 0(d)LR 调调整整 3 0 16 0 7-1(e)插插入入 11 3 0 16 1 11 0 7-2(f)插插入入 9 3 0 16 2 11 1 9 0 7-1(g)LL 调调整整 3 0 11 0 9
18、0 16 0 7-2 3 0 11-1 9 0 16-1(h)插插入入 26 26 0 7 0 3 0 11 0 9 0 16-1 26 0(i)RR 调调整整 2022-7-26 7 0 3 0 11-1 9 0 16-2 26 1(j)插入插入 18 18 0 7 0 3 0 11 0 9 0 18 0 26 0(k)RL 调整调整 16 0 7 0 3 0 11-1 9 0 18 1 26 0 16 1(l)插入插入 14 14 0 7 0 3 0 11-2 9 0 18 2 26 0 16 2(m)插入插入 15 14-1 15 0 7 0 3 0 11-1 9 0 18 1 26 0
19、 15 0 0 14 16 0(n)LR 调整调整 2022-7-261、B_树定义：一棵m阶的B_树，或为空树，或为满足下列特征的m叉树：树中每个节点至多有m棵子树；（m=3)若根不是叶子(非单根树)，则最少有两棵子树，最多有m棵子树；除根之外的所有非终端节点最少有m/2棵子树，最多m棵子树；所有的非终端节点包含下列信息数据 (n,A0,K1,A1,K2,A2,Kn,An)Ki为关键字，且Ki352、B_树的查找2022-7-26查找47的过程d1.35.1.18.1.27.1.11.1.99.1.39.2.43.78.3.47.53.64.tabcefghFFFFFFFFFFFF43477
20、82022-7-26查找47的过程d1.35.1.18.1.27.1.11.1.99.1.39.2.43.78.3.47.53.64.tabcefghFFFFFFFFFFFF查找成功2022-7-26查找23的过程d1.35.1.18.1.27.1.11.1.99.1.39.2.43.78.3.47.53.64.tabcefghFFFFFFFFFFFF23182022-7-26查找23的过程d1.35.1.18.1.27.1.11.1.99.1.39.2.43.78.3.47.53.64.tabcefghFFFFFFFFFFFF23272022-7-26查找23的过程d1.35.1.18.1.
21、27.1.11.1.99.1.39.2.43.78.3.47.53.64.tabcefghFFFFFFFFFFFF查找失败2022-7-263、B_树的插入100h45a53 90e24b3 12c37d50f61 70gbt2022-7-26插入303 12c45a53 90e24b30 37d50f61 70g100hbt2022-7-26插入2645a53 90e24b3 12c26 30 37d50f61 70g100hbt2022-7-26插入2645a53 90e24 30b3 12c37d50f61 70g100hbt26d2022-7-26插入8545a53 90e24 30b
22、3 12c37d50f61 70 85g100hbt26d2022-7-26bt插入8545a53 70 90e24 30b3 12c37d50f61 g100h26d85 g2022-7-26100hbt插入8545 70a53e24 30b3 12c37d50f61 g26d85 g90e2022-7-26bt插入745 70a53e7 24 30b3c37d50f61 g100h26d85 g12c90e2022-7-26插入7bt24 45 70a53e7b3c37d50f61 g100h26d85 g12c30b90e2022-7-26bt插入745m53e7b3c37d50f61
23、g100h26d85 g12c30b90e70a24a2022-7-26B+树树B树是B_树的一种变形，一棵m阶B树和B树的区别：有n棵子树的节点中含有n个关键字。所有的叶子节点中包含了全部关键字的信息，及指向这些关 键字的指针，且叶子节点本身以关键字的大小自小到大顺序 连接。所有的非终端节点可以看成是索引部分，节点中仅包含有其 子树中的最大(或最小)关键字。2022-7-26如：一棵3阶B+树59 9772 9715 44 5910 1521 37 4451 5963 7285 91 97bt叶子节点有序叶子节点有序子树根的最大值子树根的最大值子树根的最大值子树根的最大值2022-7-268
24、.4 哈希查找Hash查找 基本思想：在记录的存储地址和它的关键字之间建立一个确定的对应关系；这样，不经过比较，一次存取就能得到所查元素的查找方法 定义 哈希函数记录的关键字与记录的存储地址之间建立的一种对应关系 哈希函数是一种映象，是从关键字空间到存储地址空间的一种映象 哈希函数可写成：addr(ai)=H(ki)ai是表中的一个元素 addr(ai)是ai的存储地址 ki是ai的关键字存储地址集合hash2022-7-26 哈希表应用哈希函数，由记录的关键字确定记录在表中的地址，并将记录放入此地址。该表叫 哈希查找又叫散列查找，利用哈希函数进行查找的过程叫例1 30个地区的各民族人口统计表
25、编号 地区别 总人口 汉族 回族.1 北京2 上海.以编号作关键字，构造哈希函数：H(key)=keyH(1)=1H(2)=2以地区别作关键字，取地区名称第一个拼音字母的序号作哈希函数：H(Beijing)=2 H(Shanghai)=19 H(Shenyang)=192022-7-26 例2:对于一组关键字序列(25，74，36，15，40，29，82，19，65，33，57，47，50),选取函数 h(key)key%13 建立记录与其在查找表中存储位置之间的关系，可得到如下表所示的一张查找表：当对该表检索时，只需用给定关键字值k通过这个函数计算出地址，以该地址从检索表的对应位置取出记录的
26、有关信息即可，不需要进行关键字值的比较操作。如检索key=57的记录，通过h(57)=57%13=5知关键字值为57的记录在检索表的存储位置5处，从而得到关键字值为57的记录的有关信息。2022-7-26从例子可见：哈希函数只是一种映象，所以哈希函数的设定很灵活，只要使任何关键字的哈希函数值都落在表长允许的范围之内即可 冲突：key1key2，但H(key1)=H(key2)的现象叫 同义词：具有相同函数值的两个关键字，叫该哈希函数的 哈希函数通常是一种压缩映象，所以冲突不可避免，只能尽量减少；同时，冲突发生后，应该有处理冲突的方法 产生散列冲突相关的主要因素：u 装填因子：散列表中已存入元素
27、散列表中已存入元素n n与散列表空间大小与散列表空间大小m m的比。的比。装填因子越小，产生的冲突就越小；否则，就越大。u 散列函数 散列函数选择适当，使散列地址尽可能均匀地分布在散列空间中，产生的冲突就少；否则，就大。u 冲突的解决方法2022-7-26 哈希函数的构造方法直接定址法 方法：取关键字或关键字的某个线性函数作哈希地址。H(key)=key 或 H(key)=akey+b 特点：直接定址法所得地址集合与关键字集合大小相等，不会发生冲突。若有冲突，说明关键字错误。实际中能用这种哈希函数的情况很少 适用于关键字分布基本连续的情况。若不连续，空号较多，将造成存储空间的严重浪费。2022
28、-7-26数字分析法 方法：对关键字进行分析，取关键字的若干位或其组合作哈希地址 适用于关键字位数比哈希地址位数大，且关键字事先知道的情况例：有80个记录，关键字为8位十进制数，哈希地址为2位十进制数8 1 3 4 6 5 3 28 1 3 7 2 2 4 28 1 3 8 7 4 2 28 1 3 0 1 3 6 78 1 3 2 2 8 1 7 8 1 3 3 8 9 6 78 1 3 6 8 5 3 78 1 4 1 9 3 5 5.分析：位只取8 位只取1 位只取3、4 位只取2、7、5 位数字分布近乎随机所以：取任意两位或两位 与另两位的叠加作哈希地址2022-7-26平方取中法 方
29、法：取关键字平方后中间几位作哈希地址 适用于不知道全部关键字情况折叠法 方法：将关键字分割成位数相同的几部分，然后取这几部分的叠加和（舍去进位）做哈希地址 种类 移位叠加：将分割后的几部分低位对齐相加 间界叠加：从一端沿分割界来回折送，然后对齐相加 适于关键字位数很多，且每一位上数字分布大致均匀情况例 关键字为：0442205864，哈希地址位数为45 8 6 44 2 2 00 41 0 0 8 8H(key)=0088移位叠加5 8 6 40 2 2 40 4 6 0 9 2H(key)=6092间界叠加2022-7-26除留余数法 方法：取关键字被某个不大于哈希表表长m的数p除后所得余数
30、作哈希地址，即H(key)=key MOD p，pm 特点 简单、常用，可与上述几种方法结合使用 p的选取很重要；p选的不好，容易产生同义词随机数法 方法：取关键字的随机函数值作哈希地址。H(key)=random(key)适用于关键字长度不等的情况选取哈希函数，考虑以下因素：计算哈希函数所需时间 关键字长度 哈希表长度（哈希地址范围）关键字分布情况 记录的查找频率2022-7-26 处理冲突的方法开放定址法 方法：当冲突发生时，形成一个探查序列；沿此序列逐个地址探查，直到找到一个空位置（开放的地址），将发生冲突的记录放到该地址中。Hi=(H(key)+di)MOD m，i=1,2,k(km-
31、1)其中：H(key)哈希函数 m哈希表表长 di增量序列 分类 线性探测再散列：di=1,2,3,m-1 H1=H(key)Hj=(Hj-1+1)MOD m j=2,3,二次探测再散列：di=1,-1,2,-2,3,k(km/2)H1=H(key)H2j=(H1+j2)MOD m H2j+1=(H1-j2)MOD m j=1,2,3,伪随机探测再散：di=伪随机数序列 H1=H(key)Hj=(H1+R)MOD m2022-7-26例 表长为11的哈希表中已填有关键字为17，60，29的记录，H(key)=key MOD 11,现有第4个记录，其关键字为38，按三种处理冲突的方法，将它填入表
32、中0 1 2 3 4 5 6 7 8 9 1060 17 29(1)H(38)=38 MOD 11=5 冲突 H1=(5+1)MOD 11=6 冲突 H2=(5+2)MOD 11=7 冲突 H3=(5+3)MOD 11=8 不冲突 38(2)H(38)=38 MOD 11=5 冲突 H1=(5+1)MOD 11=6 冲突 H2=(5-1)MOD 11=4 不冲突38(3)H(38)=38 MOD 11=5 冲突 设伪随机数序列为9，则：H1=(5+9)MOD 11=3 不冲突382022-7-26再哈希法 方法：构造若干个哈希函数，当发生冲突时，计算下一个哈希地址。Hi=Rhi(key)i=1
33、,2,k 其中：Rhi不同的哈希函数 特点：计算时间增加链地址法 方法：将所有关键字为同义词的记录存储在一个单链表中，并用一维数组存放头指针2022-7-26例：已知一组关键字 (19，14，23，1，68，20，84，27，55，11，10，79)哈希函数为：H(key)=key MOD 13 用链地址法处理冲突0 1 2 3 4 5 6 7 8 9 10 11 12 141277968551984202310112022-7-26 哈希查找过程及分析 哈希查找过程给定k值计算H(k)此地址为空关键字=k查找失败查找成功按处理冲突方法计算HiYNYN2022-7-26 哈希查找分析 哈希查找
34、过程仍是一个给定值与关键字进行比较的过程 评价哈希查找效率仍要用ASL 哈希查找过程与给定值进行比较的关键字的个数取决于：哈希函数 处理冲突的方法 哈希表的装填因子=表中填入的记录数/哈希表长度例 已知一组关键字(19,14,23,1,68,20,84,27,55,11,10,79)哈希函数为：H(key)=key MOD 13,哈希表长为m=16，设每个记录的查找概率相等(1)用线性探测再散列处理冲突，即Hi=(H(key)+di)MOD mH(55)=3 冲突，H1=(3+1)MOD16=4 冲突，H2=(3+2)MOD16=5H(79)=1 冲突，H1=(1+1)MOD16=2 冲突，H
35、2=(1+2)MOD16=3 冲突，H3=(1+3)MOD16=4 冲突，H4=(1+4)MOD16=5 冲突，H5=(1+5)MOD16=6 冲突，H6=(1+6)MOD16=7 冲突，H7=(1+7)MOD16=8 冲突，H8=(1+8)MOD16=90 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15ASL=(1*6+2*1+3*3+4*1+1*9)/12 =2.514 1 68 27 55 19 20 84 79 23 11 10H(19)=6H(14)=1H(23)=10H(1)=1 冲突，H1=(1+1)MOD16=2H(68)=3H(20)=7H(84)=6
36、 冲突，H1=(6+1)MOD16=7 冲突，H2=(6+2)MOD16=8H(27)=1 冲突，H1=(1+1)MOD16=2 冲突，H2=(1+2)MOD16=3 冲突，H3=(1+3)MOD16=4H(11)=11H(10)=10 冲突，H1=(10+1)MOD16=11 冲突，H2=(10+2)MOD16=122022-7-26(2)用链地址法处理冲突0 1 2 3 4 5 6 7 8 9 10 11 12 14127796855198420231011ASL=(1*6+2*4+1*3+1*4)/12=1.75关键字(19,14,23,1,68,20,84,27,55,11,10,79
37、)2022-7-26 哈希查找算法实现 用线性探测再散列法处理冲突 实现 查找过程：同前 删除：只能作标记，不能真正删除 若移动元素，破坏哈希地址和关键字记录间的对应关系。插入：遇到空位置或有删除标记的位置就可以插入 算法描述：用外链表处理冲突算法2022-7-26#define M 100int h(int k)return(k%97);int slbxxcz(int t,int k)/散列表线形查找int i,j=0;i=h(k);while(jM)&(t(i+j)%M!=k)&(t(i+j)%M!=0)j+;i=(i+j)%M;if(ti=k)return(i);else return(
38、-1);2022-7-26int slbxxcr(int t,int k)/散列表线形插入 int i,j=0;i=h(k);while(j0)j+;if(j=M)return(0);i=(i+j)%M;if(ti=0)ti=k;return(1);if(ti=k)return(1);2022-7-26作业：1、对于给定的关键字序列，若Hash函数无冲突，则称其为完备的。设Hash表长度为7，试为 Bret,Jane,Shirley,Bryce,Michelle,Heather设计一个完备的Hash函数，并写出其C/C+代码。提示：考虑每个字符串的第3个字符。设计Hash函数为：H(key)=key的第3个字母的ASCII码 MOD 7 H(Bret)=101 MOD 7=3 H(Jane)=110 MOD 7=5 H(Shirley)=105 MOD 7=0 H(Bryce)=121 MOD 7=2 H(Michelle)=99 MOD 7=1 H(Heather)=97 MOD 7=6 int H(char*s)return(s2-a)%7;
