数据结构查找

数据结构（C++版）清华大学出版社第7章查找技术本章的主要内容是:查找的基本概念线性表的查找技术树表的查找技术散列表的查找技术数据结构（C++版）清华大学出版社查找的基本概念关键码：可以标识一个记录的某个数据项。键值：关键码的值。主关键码：可以唯一地标识一个记录的关键码。次关键码：不能唯一地标识一个记录的关键码。7.1概述50女李爽000525女齐梅000447女刘楠000325男张亮000238男王刚0001年龄性别姓名职工号1972年9月2003年7月1979年9月2003年7月1990年4月参加工作数据结构（C++版）清华大学出版社查找的基本概念查找：在具有相同类型的记录构成的集合中找出满足给定条件的记录。7.1概述查找的结果：若在查找集合中找到了与给定值相匹配的记录，则称查找成功；否则，称查找失败。50女李爽000525女齐梅000447女刘楠000325男张亮000238男王刚0001年龄性别姓名职工号1972年9月2003年7月1979年9月2003年7月1990年4月参加工作数据结构（C++版）清华大学出版社静态查找：不涉及插入和删除操作的查找。动态查找：涉及插入和删除操作的查找。7.1概述查找的基本概念静态查找适用于：查找集合一经生成，便只对其进行查找，而不进行插入和删除操作，或经过一段时间的查找之后，集中地进行插入和删除等修改操作；动态查找适用于：查找与插入和删除操作在同一个阶段进行，例如当查找成功时，要删除查找到的记录，当查找不成功时，要插入被查找的记录。数据结构（C++版）清华大学出版社7.1概述查找的基本概念查找结构：面向查找操作的数据结构，即查找基于的数据结构。查找结构查找方法集合中元素之间不存在明显的组织规律，不便查找。集合线性表树表散列表数据结构（C++版）清华大学出版社本章讨论的查找结构：线性表：适用于静态查找，主要采用顺序查找技术、折半查找技术。树表：适用于动态查找，主要采用二叉排序树的查找技术。散列表：静态查找和动态查找均适用，主要采用散列技术。7.1概述查找结构：面向查找操作的数据结构，即查找基于的数据结构。查找的基本概念数据结构（C++版）清华大学出版社查找算法的性能查找算法时间性能通过关键码的比较次数来度量。关键码的比较次数与哪些因素有关呢？⑴算法；⑵问题规模；⑶待查关键码在查找集合中的位置；⑷查找频率。7.1概述查找频率与算法无关，取决于具体应用。通常假设pi是已知的。数据结构（C++版）清华大学出版社查找算法的性能查找算法时间性能通过关键码的比较次数来度量。查找算法的时间复杂度是问题规模n和待查关键码在查找集合中的位置k的函数，记为T(n，k)。同一查找集合、同一查找算法，关键码的比较次数与哪些因素有关呢？7.1概述数据结构（C++版）清华大学出版社平均查找长度：将查找算法进行的关键码的比较次数的数学期望值定义为平均查找长度。计算公式为：其中：n：问题规模，查找集合中的记录个数；pi：查找第i个记录的概率；ci：查找第i个记录所需的关键码的比较次数。结论：ci取决于算法；pi与算法无关，取决于具体应用。如果pi是已知的，则平均查找长度只是问题规模的函数。7.1概述查找算法的性能ASL==niiicp1数据结构（C++版）清华大学出版社顺序查找（线性查找）基本思想：从线性表的一端向另一端逐个将关键码与给定值进行比较，若相等，则查找成功，给出该记录在表中的位置；若整个表检测完仍未找到与给定值相等的关键码，则查找失败，给出失败信息。101524612354098550123456789i7.2线性表的查找技术例：查找k＝35iii数据结构（C++版）清华大学出版社顺序查找（线性查找）7.2线性表的查找技术intSeqSearch1(intr[],intn,intk)//数组r[1]~r[n]存放查找集合{i=n;while(i0&&r[i]!=k)i--;returni;}数据结构（C++版）清华大学出版社基本思想：设置“哨兵”。哨兵就是待查值，将它放在查找方向的尽头处，免去了在查找过程中每一次比较后都要判断查找位置是否越界，从而提高查找速度。7.2线性表的查找技术改进的顺序查找101524612354098550123456789i例：查找k＝35iii哨兵35查找方向数据结构（C++版）清华大学出版社基本思想：设置“哨兵”。哨兵就是待查值，将它放在查找方向的尽头处，免去了在查找过程中每一次比较后都要判断查找位置是否越界，从而提高查找速度。7.2线性表的查找技术改进的顺序查找101524612354098550123456789i例：查找k＝25ii25查找方向iiiiiii数据结构（C++版）清华大学出版社intSeqSearch2(intr[],intn,intk)//数组r[1]~r[n]存放查找集合{r[0]=k;i=n;while(r[i]!=k)i--;returni;}7.2线性表的查找技术改进的顺序查找ASL===niicp1+-=niiinp1)1(i=(n+1)/2=O(n)数据结构（C++版）清华大学出版社平均查找长度较大，特别是当待查找集合中元素较多时，查找效率较低。7.2线性表的查找技术顺序查找的缺点：算法简单而且使用面广。对表中记录的存储没有任何要求，顺序存储和链接存储均可；对表中记录的有序性也没有要求，无论记录是否按关键码有序均可。顺序查找的优点：数据结构（C++版）清华大学出版社折半查找使用条件：线性表中的记录必须按关键码有序；必须采用顺序存储。基本思想：在有序表中，取中间记录作为比较对象，若给定值与中间记录的关键码相等，则查找成功；若给定值小于中间记录的关键码，则在中间记录的左半区继续查找；若给定值大于中间记录的关键码，则在中间记录的右半区继续查找。不断重复上述过程，直到查找成功，或所查找的区域无记录，查找失败。7.2线性表的查找技术数据结构（C++版）清华大学出版社折半查找的基本思想7.2线性表的查找技术[r1………rmid-1]rmid[rmid+1………rn]如果krmid如果krmid查找左半区查找右半区k（mid=(1+n)/2）数据结构（C++版）清华大学出版社例：查找值为14的记录的过程：0123456789101112137141821232931353842464952low=1high=13mid=7high=6mid=3high=2mid=131141814714low=2mid=214=147.2线性表的查找技术数据结构（C++版）清华大学出版社例：查找值为22的记录的过程：0123456789101112137141821232931353842464952low=1high=13mid=7high=6mid=3high=4mid=5312218222322low=4mid=421227.2线性表的查找技术low=5lowhigh数据结构（C++版）清华大学出版社intBinSearch1(intr[],intn,intk)//数组r[1]~r[n]存放查找集合{low=1;high=n;while(low=high){mid=(low+high)/2;if(kr[mid])high=mid-1;elseif(kr[mid])low=mid+1;elsereturnmid;}return0;}7.2线性表的查找技术折半查找——非递归算法数据结构（C++版）清华大学出版社intBinSearch2(intr[],intlow,inthigh,intk)//数组r[1]~r[n]存放查找集合{if(lowhigh)return0;else{mid=(low+high)/2;if(kr[mid])returnBinSearch2(r,low,mid-1,k);elseif(kr[mid])returnBinSearch2(r,mid+1,high,k);elsereturnmid;}}7.2线性表的查找技术折半查找——递归算法数据结构（C++版）清华大学出版社折半查找判定树判定树：折半查找的过程可以用二叉树来描述，树中的每个结点对应有序表中的一个记录，结点的值为该记录在表中的位置。通常称这个描述折半查找过程的二叉树为折半查找判定树，简称判定树。7.2线性表的查找技术数据结构（C++版）清华大学出版社⑴当n=0时，折半查找判定树为空；⑵当n＞0时，折半查找判定树的根结点是有序表中序号为mid=(n+1)/2的记录，根结点的左子树是与有序表r[1]~r[mid-1]相对应的折半查找判定树，根结点的右子树是与r[mid+1]~r[n]相对应的折半查找判定树。7.2线性表的查找技术判定树的构造方法数据结构（C++版）清华大学出版社7.2线性表的查找技术－11－22－33－44－510－1111－9－108－97－85－66－7内部结点外部结点3691011784512判定树的构造方法数据结构（C++版）清华大学出版社具有n个结点的折半查找判定树的深度为查找成功：在表中查找任一记录的过程，即是折半查找判定树中从根结点到该记录结点的路径，和给定值的比较次数等于该记录结点在树中的层数。查找不成功：查找失败的过程就是走了一条从根结点到外部结点的路径，和给定值进行的关键码的比较次数等于该路径上内部结点的个数。7.2线性表的查找技术。1log2+n折半查找性能分析数据结构（C++版）清华大学出版社二叉排序树二叉排序树（也称二叉查找树）：或者是一棵空的二叉树，或者是具有下列性质的二叉树：⑴若它的左子树不空，则左子树上所有结点的值均小于根结点的值；⑵若它的右子树不空，则右子树上所有结点的值均大于根结点的值；⑶它的左右子树也都是二叉排序树。7.3树表的查找技术二叉排序树的定义采用的是递归方法。数据结构（C++版）清华大学出版社二叉排序树非二叉排序树二叉排序树7.3树表的查找技术6390554258104567837063605582581045678370中序遍历二叉排序树可以得到一个按关键码有序的序列数据结构（C++版）清华大学出版社二叉排序树的存储结构以二叉链表形式存储，类声明如下：classBiSortTree{public:BiSortTree(inta[],intn);~BiSortTree();voidInsertBST(BiNodeint*root,BiNodeint*s);voidDeleteBST(BiNodeint*p,BiNodeint*f);BiNodeint*SearchBST(BiNodeint*root,intk);private:BiNodeint*root;};7.3树表的查找技术数据结构（C++版）清华大学出版社二叉排序树的插入分析：若二叉排序树为空树，则新插入的结点为新的根结点；否则，新插入的结点必为一个新的叶子结点，其插入位置由查找过程得到。7.3树表的查找技术voidInsertBST(BiNodeint*root,BiNodeint*s);数据结构（C++版）清华大学出版社例：插入值为98的结点7.3树表的查找技术6355905870985563root∧9058∧∧70∧∧98∧∧sroot∧数据结构（C++版）清华大学出版社voidBiSortTree::InsertBST(BiNodeint*root,BiNodeint*s){if(root==NULL)root=s;elseif(s-dataroot-data)InsertBST(root-lchild,s);elseInsertBST(root-rchild,s);}7.3树表的查找技术二叉排序树的插入算法数据结构（C++版）清华大学出版社二叉排序树的构造从空的二叉排序树开始，依次插入一个个结点。例：关键码集合为{63，90，70，55，58}，二叉排序树的构造过程为：7.3树表的查找技术6355905870数据结构（C++