数据结构-dsch7动画版

查找表静态查找表动态查找表哈希表下一章第七章查找定义：是同一类型的数据元素构成的集合。集合中的数据元素之间存在着松散的关系对查找表经常进行的操作:1）查询某个“特定的”数据元素是否在查找表中；2）检索某个“特定的”数据元素的各种属性；3）在查找表中插入一个数据元素；4）从查找表中删去某个数据元素。静态查找表:仅作查询和检索操作的查找表动态查找表:查找过程中,还进行数据元素插入或删除操作的查找表查找表可分为两类:查找表SearchTable查找Searching——是根据给定的某个值，在表中确定一个关键字等于给定值的记录或数据元素关键字Key——数据元素中某个数据项的值，它可以标识一个数据元素主关键字PrimaryKey——可以唯一标识一个记录的关键字次关键字SecondaryKey——可以标识若干记录的关键字查找结果——“查找成功”，给出整个记录的信息，或指示该记录在查找表中的位置；“查找不成功”，给出“空记录”或“空指针”查找表SearchTable查找方法评价查找速度占用存储空间多少算法本身复杂程度平均查找长度ASL(AverageSearchLength)：为确定记录在表中的位置，需要与给定值进行比较的次数的期望值叫查找算法的~平均查找长度ASL:查找表SearchTable查找表SearchTabletypedefint

KeyType;//typedeffloat

KeyType;//typedefchar*

KeyType;typedefstruct{KeyType

key;……}ElemType;查找实现中涉及的类型定义静态查找表StaticSearchTable顺序表查找---顺序查找有序表查找---折半查找索引顺序表查找---分块查找静态查找表:仅作查询和检索操作的查找表静态查找方法比较typedefstruct{ElemType*elem;//数据元素存储空间基址，//建表时按实际长度分配，0号单元留空intlength;//表的长度}SSTable;顺序表查找SequentialSearchTable以顺序表或线性链表表示静态查找表，可用顺序查找实现静态查找表的顺序存储结构顺序查找过程：从表的一端开始逐个进行记录关键字和给定值的比较i64监视哨iiii比较次数=比较次数：查找第n个元素：1查找第n-1个元素：2……….查找第1个元素：n查找第i个元素：n+1-i查找失败：n+15例01234567891011513192137566475808892找顺序表查找SequentialSearchTable顺序表查找SequentialSearchTable算法描述intSearch_Seq(SSTableST,KeyTypekey){inti;

ST.elem[0].key=key;for(i=ST.length;ST.elem[i].key!=key;i--);return(i);}返回0，查找失败顺序查找方法的ASL顺序查找平均要比较表长的一半记录能够查找成功★优点：算法简单，对线性表的逻辑次序和存储结构无要求★缺点：ASL较大，n很大时，查找效率较低顺序表查找SequentialSearchTable在等概率查找的情况下，顺序表查找的平均查找长度为：对顺序表而言，Ci=n-i+1 又叫二分法查找查找过程：每次将待查记录所在区间缩小一半适用条件：采用顺序存储结构的有序表算法实现设表长为ST.length，low、high和mid分别指向待查元素所在区间的上界、下界和中点,key为给定值初始时，令low=1,high=ST.length,mid=(low+high)/2将mid指向的记录与key比较(假设有序表升序)若key==ST.elem[mid].key，查找成功若key<ST.elem[mid].key，则high=mid-1若key>ST.elem[mid].key，则low=mid+1重复上述操作，直至找到记录，查找成功；或low>high，查找失败折半查找BinarySearchlowhighmid1234567891011例513192137566475808892找21查找成功折半查找BinarySearchlowhighmid1234567891011例513192137566475808892找70查找失败折半查找BinarySearch算法描述intSearch_Bin(SSTableST,KeyTypekey){intlow,high,mid;

low=1;high=ST.length;while(low<=high){mid=(low+high)/2;if(key==ST.elem[mid].key)return(mid);elseif(key>ST.elem[mid].key)low=mid+1;elsehigh=mid-1;}return0;}折半查找BinarySearch折半查找BinarySearch算法分析6391471025811判定树1234567891011513192137566475808892判定树：描述查找过程的二叉树叫~有n个结点的判定树的深度为log2n+1判定树与结点数相同的完全二叉树：63914710258116391471051128折半查找法在查找过程中进行的比较次数最多不超过其判定树的深度ASL=(1*1+2*2+3*4+4*4)/11=3123114589121367101415设判定树是深度为h的满二叉树n比较次数顺序查找折半查找★优点：平均查找长度较小，查找效率高于顺序查找★缺点：只适用于顺序存储的有序表，不适用于一般顺序表和链式存储结构折半查找BinarySearch折半查找的ASL2248861713索引表查38查找成功12345678910111213141516171822121389203342443824486058745786531234567891011121314151617182212138920334244382448605874578653分块查找IndexSequentialSearch最大关键字起始地址分块查找过程：算法描述intSearch_Index(SSTableST,IndexTable

IT[],KeyTypekey,intb,intn){inti=1,k;while((key>IT[i].MaxKey)&&(i<=b))i++;//在索引表中顺序查找确定所在块if(i>b)return(0);

k=IT[i].FirstLink;//找到本块第一个元素while((k<n)&&(key!=ST.elem[k].key)&&(ST.elem[k].key<=IT[i].MaxKey))k++;//块内顺序查找if(key!=ST.elem[k].key)k=0;return(k);}分块查找IndexSequentialSearchtypedefstruct{KeyTypeMaxKey;intFirstLink;}IndexTable;分块查找IndexSequentialSearch分块查找算法评价其中:Lb----查找索引表确定所在块的ASL

LW----在块中查找元素的ASL若将表长为n的表平均分成b块,每块有s个元素(1)用顺序查找确定所在块:(2)用折半查找确定所在块:假设表中元素的查找概率相等ASL最大最小两者之间表结构有序表、无序表有序表分块有序表存储结构顺序存储结构线性链表顺序存储结构顺序存储结构线性链表查找方法比较顺序查找折半查找分块查找静态查找方法比较动态查找表DynamicSearchTable二叉排序树二叉平衡树B-树动态查找表:在查找过程中还进行插入和删除操作的查找表B+树键树二叉排序树BinarySortTree1．二叉排序树定义2．二叉排序树查找3．二叉排序树插入4．二叉排序树删除5．二叉排序树查找性能分析二叉查找树BinarySearchTree定义：二叉排序树或是一棵空树，或是具有下列性质的二叉树：若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值若它的右子树不空，则右子树上所有结点的值均大于或等于它的根结点的值它的左、右子树本身也是一棵二叉排序树10183812273二叉排序树BinarySortTree66503080204010252390358588是二叉排序树不查找过程8060120110150557053查找70查找成功二叉排序树查找

BinarySortTreeSearch查找过程二叉排序树查找

BinarySortTreeSearch503080204010252390358588查找5050查找3550304035查找908090查找839085若二叉排序树为空，则查找不成功否则，1）若给定值等于根结点的关键字，则查找成功；2）若给定值小于根结点的关键字，则继续在左子树上进行查找；3）若给定值大于根结点的关键字，则继续在右子树上进行查找。二叉排序树具有类似折半查找的性质，又采用了链表结构，是一种动态查找表有n个结点的二叉排序树的平均检索长度ASL为O(log2n),和二叉树的形态有关递归算法描述二叉排序树查找

BinarySortTreeSearchBiTreeSearchBST(BiTreeT,KeyTypekey){if(!T||

key==

T->data.key)returnT;//查找成功或失败elseif(key<T->data.key)returnSearchBST(T->lchild,key);//在左子树中继续查找elsereturnSearchBST(T->rchild,key);//在右子树中继续查找}返回NULL，查找失败BST插入根据动态查找表的定义，“插入”操作在查找不成功时才进行插入原则：若二叉排序树为空，则插入结点应为新的根结点；否则，继续在其左、右子树上查找，直至某个叶子结点的左子树或右子树为空为止，则插入结点应为该叶子结点的左孩子或右孩子二叉排序树插入

BinarySortTreeInsert1031828712插入1515101812BST生成二叉排序树插入

BinarySortTreeInsert二叉排序树生成：从空树出发，经过一系列的查找、插入操作之后，可生成一棵二叉排序树1031828712例{10，18，3，8，12，2，7，3}中序遍历二叉排序树可得到一个关键字的有序序列中序遍历二叉排序树，得出其特点?33研究二叉排序树的意义？?一个无序序列可以通过构造一棵二叉排序树变成一个有序序列构造树的过程即是对无序序列进行排序的过程插入的新结点是二叉排序树的新叶子结点相当于在有序序列上插入记录而不需要移动3二叉排序树删除

BinarySortTreeDelete和插入相反，删除在查找成功之后进行，并且要求在删除二叉排序树上某个结点之后，仍然保持二叉排序树的特性。要删除二叉排序树中的p结点，分三种情况讨论：p为叶子结点p只有左子树或右子树p左、右子树均非空二叉排序树删除

BinarySortTreeDelete（1）被删除的结点是叶子结点删除2050308032409035852088删除88其双亲结点中相应指针域的值改为“空”f->lchild=NULL;或f->rchild=NULL;二叉排序树删除

BinarySortTreeDelete（2）被删除的结点只有左子树或只有右子树删除4050308032409035852088删除80其双亲结点中相应指针域的值改为“指向被删除结点的左孩子或右孩子”f->rchild=p->lchild;f->rchild=p->rchild;f->lchild=p->rchild;f->lchild=p->lchild;二叉排序树删除

BinarySortTreeDelete（3）被删除的结点既有左子树，也有右子树FPPRPLpfFPPRpfCCLQSQLSL被删结点前驱结点S以其前驱替代之，然后再删除该前驱结点方案一：中序遍历：CLC……QLQSL

S

PPRF中序遍历：CLC……QLQSL

SPRF二叉排序树删除

BinarySortTreeDelete（3）被删除的结点既有左子树，也有右子树FPPRPLpfFPPRpfCCL被删结点前驱结点C以其前驱替代之，然后再删除该前驱结点方案一：中序遍历：CL

C

PPRF中序遍历：CL

CPRF二叉排序树删除

BinarySortTreeDelete（3）被删除的结点既有左子树，也有右子树FPPRPLpfFPpfCCRQS后继结点被删结点S以其后继替代之，然后再删除该后继结点PLQRSR方案二：中序遍历：PL

P

SSRQQR……CCRF中序遍历：PL

SSRQQR……CCRF例805012060110150557053删除508060120110150557053删除60805512011015053701042581354删除1084255134删除58425413二叉排序树删除

BinarySortTreeDelete按方案一删除例由关键字1,2,3,4,5构造二叉排序树3145212345ASL=(1+2*2+3*2)/5=2.2ASL=(1+2+3+4+5)/5=3二叉排序树查找性能分析例由关键字3,1,2,4,5构造二叉排序树由值相同的n个关键字，构造所得的不同形态的各棵二叉排序树的平均查找长度的值不同，甚至可能差别很大当先后插入的关键字有序时，蜕变成单枝树，此时最差最好情况是二叉排序树形态与折半查找判定树相同，此时ASL与log2n成正比最佳二叉排序树定义：平均检索长度ASL最小的二叉排序树构造方法：平分法例用1，2，3，4，5，6，7，8，9构造最佳二叉排序树527836194ASL=(1+2*2+3*4+4*2)/9=25/9最佳二叉排序树BestBinarySortTree哈希表HashTable什么是哈希表？哈希函数的构造方法处理冲突的方法哈希查找过程与分析哈希查找的算法实现基本思想：在记录的存储地址和它的关键字之间建立一个确定的对应关系；这样，不经过比较，一次存取就能得到所查元素关键字集合存储地址集合Hash什么是哈希表HashTable哈希函数是一种映象，是从关键字集合到存储地址集合的一种映象哈希函数可写成：addr(ai)=H(keyi)ai是表中的一个元素addr(ai)是ai的存储地址keyi是ai的关键字哈希函数——在记录的关键字与记录在表中的存储位置之间建立的一个函数对应关系，叫~什么是哈希表HashTable关键字集合存储地址集合Hash例30个地区的各民族人口统计数据什么是哈希表HashTable编号地区别总人口汉族回族…...1北京2上海…...…...30沈阳以编号作关键字，构造哈希函数：H(key)=keyH(1)=1H(2)=2……北京上海…………………………沈阳1230...以地区别作关键字，取地区名称第一个拼音字母的序号作哈希函数：H(Beijing)=2H(Shanghai)=19H(Shenyang)=19北京………………上海……1230..19沈阳怎么办？定义从例子可见：哈希函数只是一种映象，所以哈希函数的设定很灵活，只要使任何关键字的哈希函数值都落在哈希表长允许的范围之内即可冲突：key1key2，但H(key1)=H(key2)的现象叫~，又称碰撞同义词：具有相同函数值的两个关键字,叫该哈希函数的~哈希函数通常是一种压缩映象，所以冲突不可避免，只能选择一个好的哈希函数，尽量减少产生冲突的机率；同时，冲突发生后，应该有处理冲突的方法选择一个好的哈希函数的标准：能将关键字均匀的分布在存储空间中什么是哈希表HashTable什么是哈希表HashTable哈希表——根据设定的哈希函数H(key)和选中的处理冲突的方法，将一组记录按其关键字映象到一个有限的、地址连续的地址集(区间)上，并以关键字在地址集中的“象”作为相应记录在表中的存储位置，这样构造所得的查找表，叫~哈希查找——又叫散列查找，利用哈希函数在哈希表中进行查找的过程叫~关键字集合存储地址集合Hash哈希函数构造方法

对数字的关键字可有下列构造方法：若是非数字关键字，则需先对其进行数字化处理1.

直接定址法3.平方取中法5.除留余数法4.折叠法6.随机数法2.数字分析法哈希函数选取原则直接定址法构造：取关键字或关键字的某个线性函数作哈希地址，即H(key)=key或H(key)=a·key+b特点适合于：地址集合大小==关键字集合大小不会发生冲突实际中能用这种哈希函数的情况很少例有一个从1岁到100岁的人口数字统计表，其中年龄作为关键字，哈希函数取关键字自身：地址

010203……252627……100年龄

123……252627……100人数300020005000……105011002030……10000……哈希函数构造方法

return数字分析法(数字选择法)构造：对关键字进行分析，提取分布均匀的若干位或其组合作哈希地址适于关键字位数比哈希地址位数大，且能预先估计出全体关键字的每一位上各种数字出现的频度例有80个记录，关键字为8位十进制数，哈希地址为2位十进制数8134653281372242813874228130136781322817813389678136853781419355…..…..分析：只取8只取1只取3、4只取2、7、5数字分布近乎随机所以：取任意两位或两位与另两位的叠加作哈希地址哈希函数构造方法

return平方取中法构造：取关键字平方后中间几位作哈希地址目的是“扩大差别”，平方值的中间位能受到整个关键字中各位的影响适于不知道全部关键字，关键字中的每一位都有某些数字重复出现频度很高的现象例有一组记录的关键字为：0100、1100、1200、1160、2061、2062、2161、2162、2163，哈希地址位数为3记录关键字(关键字)2哈希地址AIJI0P1P2Q1Q2Q30100110012001160206120622161216221630010

00012100001

440000137040043105414314704473474147413044745651010210440370310314734741745哈希函数构造方法

return折叠法构造：将关键字分割成位数相同的几部分，然后取这几部分的叠加和（舍去进位）作为哈希地址种类移位叠加：将分割后的几部分低位对齐相加间界叠加：从一端沿分割界来回折送，然后对齐相加适于关键字位数很多，且每一位上数字分布大致均匀情况例关键字为：，哈希地址位数为458642379018244H(key)=8244移位叠加586497320115597H(key)=5597间界叠加哈希函数构造方法

return除留余数法构造：取关键字被p除后所得余数作哈希地址（p是某个不大于哈希表表长m的数）即H(key)=keyMOD

p，pm特点简单、常用p的选取很重要；p选的不好，容易发生冲突p一般取小于等于表长m的最大素数，或是不含20以下的质因子哈希函数构造方法

return哈希函数构造方法

随机数法构造：取关键字的随机函数值作哈希地址，即H(key)=random(key)random为伪随机函数适于关键字长度不等的情况return选取哈希函数，考虑以下因素：计算哈希函数所需时间关键字长度哈希表长度（哈希地址范围）关键字分布情况记录的查找频率哈希函数构造方法

实际造表时，采用何种构造哈希函数的方法取决于建表的关键字集合的情况(包括关键字的范围和形态)，总的原则是使产生冲突的可能性降到尽可能地小。return冲突处理方法

“处理冲突”的实际含义是：为产生冲突的地址寻找下一个哈希地址1.

开放定址法2.再哈希法3.链地址法开放定址法方法：当冲突发生时，形成一个探查序列；沿此序列逐个地址探查，直到找到一个空位置（开放的地址），将发生冲突的记录放到该地址中，即Hi=(H(key)+di)MOD

m，i=1,2,……k(km-1)其中：H(key)——哈希函数m——哈希表表长di——增量序列依据增量di三种取法，分类线性探测再散列：di=1,2,3,……m-1二次探测再散列：di=1²,-1²,2²,…,±k²(km/2)伪随机探测再散列：di=伪随机数序列冲突处理方法

例表长为11的哈希表中已填有关键字为17，60，29的记录，H(key)=keyMOD

11,现有第4个记录，其关键字为38，按三种探测再散列处理冲突的方法，将它填入哈希表中(1)

哈希函数值：H(38)=38MOD11=5

冲突

线性探查：H1=(5+1)MOD11=6

冲突

H2=(5+2)MOD11=7

冲突

H3=(5+3)MOD11=8

不冲突

38(2)哈希函数值：H(38)=38MOD11=5

冲突

二次探查：H1=(5+1²)MOD11=6

冲突

H2=(5-1²)MOD11=4

不冲突38(3)

哈希函数值：H(38)=38MOD11=5

冲突

设伪随机数序列为9，则：H1=(5+9)MOD11=3

不冲突38012345678910176029开放定址法处理冲突举例

开放定址法处理冲突举例

例如:关键字集合{19,01,23,14,55,68,11,82,36}设定哈希函数H(key)=keyMOD11(表长m=11)1901231455681901231468若采用线性探测再散列处理冲突若采用二次探测再散列处理冲突11823655118236ASL=22/9returnASL=16/9830501132112136251112121431再哈希法(双散列)方法：构造若干个哈希函数，当发生冲突时，使用另外一个哈希函数计算哈希地址，即：Hi=RHi(key)i=1,2,……k，直到不发生冲突为止其中：RHi——不同的哈希函数特点：不易再次产生冲突，但计算时间增加冲突处理方法

例如:关键字集合{19,01,23,14,55,68,11,82,36}设定哈希函数H1(key)=keyMOD11

(表长m=11)设H2(key)=(3key)MOD10+1190155143668118223ASL=12/9return8305011329410111121221链地址法(外链法)方法：将所有关键字为同义词的记录存储在一个单链表中，并用一维数组存放单链表的头指针冲突处理方法

例已知一组关键字(19,01,23,14,55,68,11,82,36

)哈希函数为：H(key)=keyMOD7,用链地址法处理冲突196882140136115523012