[其它]数据结构第9章.ppt

数据结构 基础数据结构应用数据结构 非线性结构线性结构 线 性 表栈 队 列串 数 组 广 义 表树 二 叉 树图 查 找 内 部 排 序 外 部 排 序 文 件 动 态 存 储 管 理 9.1 查找的基本概念 9.2 静态查找表基于线性表的查找法 9.3 动态查找表基于树表的查找法 9.4 哈希表计算式查找法 第9章 查找 l查找表 由同一类型的数据元素（记录）构成的集合。 l查找的定义 给定一个值key，在含有n个记录的表中找出关键字等于key 的记录。若找到,则查找成功，返回该记录的信息或该记录在 表中的位置；否则查找失败，返回相关的指示信息。 1. 查找的基本概念 采用何种查找方法? (1)使用哪种数据结构来表示“表”,即表中记录是按何种方式 组织的。 (2)表中关键字的次序。是对无序集合查找还是对有序集合查找 ? l静态查找表(Static Search Table)：查询某个特定的元素是否 在表中；检索某个特定的元素的各种属性。 l动态查找表(Dynamic Search Table)：若在查找的同时对表 做修改运算(如插入和删除)。 l主关键字：能唯一标识一个记录的关键字。 l次关键字：能标识多个记录的关键字。 2. 查找操作的性能分析 l基本操作：将记录的关键字和给定值进行比较。 l平均查找长度ASL(Average Search Length) ：为确定数据 元素在查找表中的位置， 需和给定值进行比较的关键字个数的 期望值，称为查找算法在查找成功时的平均查找长度。 Pi为查找表中第i个记录的概率，Ci为找到第i个记录时，和给定 值已经进行过比较的关键字个数。 在表的组织方式中,线性表是最简单的一种。三种在线性表上进 行查找的方法： (1) 顺序查找 (2) 折半查找（二分查找） (3) 索引顺序表查找（分块查找）。 因为不考虑在查找的同时对表做修改,故上述三种查找操作都 是在静态查找表上实现的。 9.1 静态查找表 1.顺序查找 顺序查找法的特点：用所给关键字与线性表中各元素的关键字 逐个比较，直到成功或失败。 开始: 3 9 1 5 8 10 6 7 2 4 第1次比较: 3 9 1 5 8 10 6 7 2 4 i=0 第2次比较: 3 9 1 5 8 10 6 7 2 4 i=1 第3次比较: 3 9 1 5 8 10 6 7 2 4 i=2 第4次比较: 3 9 1 5 8 10 6 7 2 4 i=3 第5次比较: 3 9 1 5 8 10 6 7 2 4 i=4 查找成功,返回序号4 例如,在关键字序列为 3,9,1,5,8,10,6,7,2,4 的线性表查找关键字 为8的元素。 l存储结构通常为顺 序结构，也可为链 式结构。 typedef struct int *elem; int length; SSTable; int Search_Seq(SStable ST, int key) ST.elem0 = key;/监视哨：下标为0的位置存放待查找的元素 for( i=ST.length; ST.elemi != key; -i ); return i; for( i=ST.length; i0 -i ); 12 23699 45 30 51 28 12345678 i 监视哨 0 12 23699 45 30 51 28 12345678 i l顺序查找的平均查找长度ASL： 假设表长度为n，那么查找到第i个记录时，和给定值已进行过 比较的关键字个数为n-i+1，即Ci=n-i+1。又假设查找每个数据 元素的概率相等，即Pi=1/n， 则顺序查找算法查找成功时的平 均查找长度为： 查找失败时的平均查找长度为： a1 a2 a3 a4 a5 a6 a7 a8 2. 折半查找法 （二分查找法） 要求待查找的表必须是按关键字大小有序排列的顺序表。 折半查找的思想：将表中间位置记录的关键字与查找关键字比 较，如果两者相等，则查找成功；否则利用中间位置记录将表 分成前、后两个子表， 如果中间位置记录的关键字大于查找关 键字，则进一步查找前一子表，否则进一步查找后一子表。重 复以上过程，直到找到满足条件的记录，使查找成功，或直到 子表不存在为止，此时查找不成功。 l关键字有序序列2,4,7,9,10,14,18,26,32,40中采用折半查 找法，查找关键字为7的元素。 1 2 3 4 5 6 7 8 9 10 开始: 2 4 7 9 10 14 18 26 32 40 low=1 high=10 mid=(1+10)/2=5 第1次比较: 2 4 7 9 10 14 18 26 32 40 1 4 mid=(1+4)/2=2 第2次比较: 2 4 7 9 10 14 18 26 32 40 mid=(3+4)/2=3 第3次比较: 2 4 7 9 10 14 18 26 32 40 R3.key=7 查找成功,返回序号3 查找不成功: low high 2 4 7 9 10 14 18 26 32 40 mid=(4+4)/2=4 high=mid-1=3 key) high=mid-1; /*继续在lowmid-1中查找,前半区*/ else low=mid+1; /*继续在mid+1high中查找,后半区*/ return 0; 问题： 若采用链表（单链表或双向链表）作为 查找表的存储结构，能否进行折半查找？ 判定树(比较树)：折半查找过程可用二叉树来描述,把当前查找区间的中间 位置上的记录作为根,左子表和右子表中的记录分别作为根的左子树和右子 树。 1 2 3 4 5 6 7 8 9 10 11 5 13 19 21 37 56 64 75 80 88 92 6 3 14 9 10 7 11 2 5 8 小于5的 所有元素 大于5而 小于13的 所有元素 l折半查找的效率分析 如果查找表中有n个元素，那么对应的折半查找判 定树又如何？ 查找成功和失败的平均查找长度与有n个结点的 完全二叉树的高度相同。即： l折半查找成功时的平均查找长度ASL 假定表的长度n=2h-1，则相应判定树必为深度是h的满二叉树 ，h=log2(n+1)。又假设每个记录的查找概率相等， 则折半查 找成功时的平均查找长度为： 当n较大(n50)时，有近似结果： 折半查找判定树 (1)在查找成功时,会找到图中某个圆形结点,则成功时的平均查 找长度： (2)在查找不成功时,会找到图中某个方形结点,则不成功时的平 均查找长度： 3.索引顺序查找(分块查找) 是一种性能介于顺序查找和折半查找之间的查找方法。 将表1n均分为b块,前b-1块中记录个数为s=n/b,最后 一块即第b块的记录数小于等于s；表是“分块有序”的；索 引表是一个递增有序表。 13 89 20 33 42 44 38 24 48 60 58 74 49 86 5322 12 B1B2B3 22 1 48 7 86 13 最大关键字 起始地址( 下标) 索引表 LB：查找索引表的ASL； LW ：块内进行顺序查找的ASL。 ASLbs=LB+LW b块，每块含s个元素。查找概率相等，则每个索引项的查找概 率为1/b，块中每个元素的查找概率为1/s。 l若用顺序查找法确定待查元素所在的块，则有 l若用折半查找法确定待查元素所在的块，则有 l 静态查找表的三种查找方法的比较 顺序查找对对于表有序、无序均适用；折半查找仅适用于 有序表；分块查找要求表分块后“分块有序”。 从表的存储结构上看，顺序查找和分块查找对于表的顺序 和链式存储结构均适用，而折半查找只适用于顺序存储结 构。 平均查找长度ASL而言，折半最小（log2(n+1)-1），分块 次之，当 时（ ），顺序最大（(n+1)/2）。 9.2 动态查找表 动态查找表的特点：表结构本身在查找过程中动态生成，即对于 给定值key，若表中存在关键字等于key的记录，则查找成功，否 则插入关键字等于key的记录。 二叉排序树、 平衡二叉排序树和B树等。 动态查找表的主要运算 创建、销毁 查找、插入和删除 遍历 1. 二叉排序树BST (Binary Sort Tree) 的定义 2. (二叉检索树、二叉查找树) 或者是一棵空树， 或者是具有如下性质的二叉树： (1)若它的左子树不空， 则左子树上所有结点的值均小于根结 点的值； (2)若它的右子树不空， 则右子树上所有结点的值均大于根结 点的值； (3)它的左右子树也分别为二叉排序树。 二叉排序树示例 typedef struct BiTNode /*记录类型*/ KeyType key; /*关键字项*/ InfoType data; /*其他数据域*/ struct BiTNode *lchild,*rchild; /*左右孩子指针*/ BiTNode, *BiTree; 45 1253 337100 90 24 61 78 CAO ZHAO DING CHEN WANG LI XIA DU MA 2. 二叉排序树上的查找 二叉排序树可看做是一个有序表，在二叉排序树上进行查找, 和折半查找类似,也是一个逐步缩小查找范围的过程。 BiTree SearchBST(BiTree T, KeyType key) if (!T | key=T-key) /*递归终结条件*/ return T; else if (key key) return SearchBST(T-lchild, key); /*在左子树中递归查找*/ else return SearchBST(T-rchild, key); /*在右子树中递归查找*/ BiTree SearchBST(BiTree T, KeyType key) p = T; while( ) if(p-key key) p = p-lchild; else p = p-rchild; return ; p T-key=key; T-lchild=T-rchild=NULL; return 1; else if (key = T-key) /*存在相同关键字的结点,返回0*/ return 0; else if(key key) return InsertBST(T-lchild, key);/*插入到左子树中*/ else return InsertBST(T-rchild, key); /*插入到右子树中*/ l在以T为根结点的BST中插入一个关键字为key的结点。插 入成功返回1,否则返回0. if (p) return 0; /键值为key的结点已经存在 s = new BiTNode; s-key = e; s-lchild = s-rchild = NULL; if (father=NULL) T = s; else if (keyfather-key) father-rchild = s; else father-lchild = s; return 1; /InsertBST p = T; father = NULL; while (p if (keyp-key) p = p-rchild; else p = p-lchild; /while int InsertBST(BiTree /*初始时T为空树*/ int i=0; while (irchild=NULL(或f-lchild=NULL) ； free(p)； (2) 若p结点只有左子树，或只有右子树，则可将p的左子树或右 子树直接改为其双亲结点f的左(右)子树， 即：f-rchild=p-lchild（或f-rchild=p-rchild）； free(p)； (3) 若p既有左子树，又有右子树，设p为双亲f的左孩子。 此时有 两种处理方法： 方法1：将p的左子树改为f的左子树，而将p的 右子树改为s的右子树。 CLCQLQSLSPPRF S为P的直接前驱，在其“ 左子树最右下”的结点 方法2：用s结点的值替代p结点的值，再将s结点删除，原s结 点的左子树改为s的双亲结点q的右子树。 CLCQLQSLSPPRF Status DeleteBST(BiTree else if(T-key = key) return Delete(T); else if(T-key key) return DeleteBST(T-lchild, key); else return DeleteBST(T-rchild, key); return TRUE; void Delete( BiTree p = p-lchild; free(q); /右子树空 else if( !p-lchild) q = p; p = p-rchild; free(q); /左子树空 else/左右子树均不空 q = p; s = p-lchild; while( s-rchild) q = s; s = s-rchild; p-data = s-data; if(q!=p) q-rchild = s-lchild; else q-lchild = s-lchild; free(s); p 5. 二叉排序树的查找分析 45, 24, 53, 12, 37, 93 12, 24, 37, 45, 53, 93 ASL=(1+2*2+3*3)/6 ASL=(1+2+3+4+5+6)/6 最