【数据结构与算法】查找.pptVIP

第九章 查找 9.1 静态查找表 9.1.1 顺序表的查找 9.1.2 有序表的查找 9.2 动态查找表 9.2.1 二叉排序树和二叉平衡树 9.3 哈希( Hashing )表(散列表) 第九章 查找 查找表 (search table): 同一类型数据元素构成的集合。 查找操作: (1)查询某个“特定的”数据元素是否在查找表中; (2)检索某个“特定的”数据元素的各种属性; (3)在查找表中插入一个数据元素; (4)从查找表中删除某个数据元素. 静态查找表:对查找表只作(1)、(2)操作； 动态查找表：可以对查找表作(1)-(4)操作。 有关查找的“词”的含义 关键字(KEY): 数据元素(或记录)的某个数据项的值,用以标识一个数据元素(或记录). 可以唯一标识一个记录的关键字称为主关键字(Primary Key); 否则称为次关键字(Secondary Key). 查找(Searching) 根据给定的值,在查找表中确定一个关键字等于给定值的记录或数据元素. 9.1 静态查找表 可以用顺序表，也可以用线性链表来表示静态查找表。 顺序表的查找 typedef struct{ //静态查找表的顺序存储结构 ElemType *elem; int length; }SSTable; 顺序查找（Sequential Search） int Search_Seq(SSTable ST, KeyType key){ ST.elem[0].key = key; // “哨兵” for(i=ST.length; !EQ(ST.elem[i].key, key); --i); return i; } 性能分析： 设Pi为查找表中第i个记录的概率(取Pi=1/n)； Ci为找到第i个记录所需的查找次数。则 n ASL = ? Pi Ci = nP1+(n-1)P2+...+2Pn-1+Pn i=1 = [n+(n-1) +...+2+1]*1/n = (n+1)/2 若查找成功与不成功的概率相同，即Pi=1/2n， ASL = nP1+(n-1)P2+...+2Pn-1+Pn+(n+1)/2 = (n+1)*3/4 有序表的查找:折半查找（Binary Search） 确定待查记录的区间，逐步缩小范围直到找到或找不到该记录为止。 例子： 数据元素有序表如下,查找关键字key=21的数据元素。 21(05，13，19，21，37，56，64，75，80，88，92） 下标: 0 1 2 3 4 5 6 7 8 9 10 11 05，13，19，21，37，56，64，75，80，88，92 ?low ?mid ?high mid = [(low+high)/2]; key=ST.elem[mid].key查找成功; 当keyST.elem[mid].key时,下一个待查区间为[low,mid-1] 05，13，19，21，37，56，64，75，80，88，92 ?low ?mid ?high 当keyST.elem[mid].key时下一个待查区间为[mid+1,high] 折半查找的性能分析查找上例中所有元素的判定二叉树为 9.2 动态查找表9.2.1 二叉排序树 什么是二叉排序树(Binary Sort Tree) ? 二叉排序树是空树,或者是具有以下性质的二叉树: (1)若左子树非空,则左子树上所有结点的值均小于 它的根结点的值; (2)若右子树非空,则右子树上所有结点的值均大于 它的根结点的值; (3)它的左、右子树也分别为二叉排序树。 二叉排序树举例 二叉排序树的生成(插入结点) 二叉排序树的生成(连续进行插入操作) 例如:对{45,24,53,45,12,24,90} 关键字序列的二叉排序树生成过程如下: 二叉排序树结点的删除(保持二叉排序树的特性及次序) 设被删除的结点为*p,其父结点为*f,并不失一般性假设*p为*f的左孩子,则 (1)若*p为叶结点,即PL和PR均为空.直接删除不会影响树结构; (2)若*p只有PL或只有PR.只要令PL或PR直接成为其双亲结点*f的左孩子即可,这样也不会影响树结构; (3)若*p有PL也有PR.为保持中序遍历二叉树的序列不变,可以有两种处理方法:其一是令PL为*f的左子树,PR为*s的右子树(*s为中序遍历PL的最后一个结点);其二是令*p的