浙江大学：《数据结构与算法》第九章 查找

第九章查找 91静态查找表 q9顺序表的查找 912有序表的查找 u92动态查找表 921二又排序树和二叉平衡树 93哈希( Hashing)表(散列表)

第九章 查找 9.1 静态查找表 9.1.1 顺序表的查找 9.1.2 有序表的查找 9.2 动态查找表 9.2.1 二叉排序树和二叉平衡树 9.3 哈希( Hashing )表(散列表)

第九章查找 查找表( search table) 同一类型数据元素构成的集合。 查找操作 (1)查询某个“特定的”数据元素是否在查找表 中 (2)检索某个“特定的”数据元素的各种属性 (3)在查找表中插入一个数据元素; (4)从查找表中删除某个数据元素 静态查找表:对查找表只作(1)、(2)操作;

第九章 查找 查找表 (search table): • 同一类型数据元素构成的集合。 查找操作: • (1)查询某个“特定的”数据元素是否在查找表 中; • (2)检索某个“特定的”数据元素的各种属性; • (3)在查找表中插入一个数据元素; • (4)从查找表中删除某个数据元素. 静态查找表:对查找表只作(1)、(2)操作； 动态查找表：可以对查找表作(1)-(4)操作

有关查找的“词”的含义 口关键字(KEY 数据元素(或记录)的某个数据项的值,用 以标识一个数据元素(或记录 可以唯一标识一个记录的关键字称为主 关键字( Primary key);香则称为次关键字 (Secondary Key) 可查找 (Searching) 根据给定的值,在查找表中确定一个关键 字等于给定值的记录或数据元素

有关查找的“词”的含义 关键字(KEY): • 数据元素(或记录)的某个数据项的值,用 以标识一个数据元素(或记录). • 可以唯一标识一个记录的关键字称为主 关键字(Primary Key); 否则称为次关键字 (Secondary Key). 查找(Searching) • 根据给定的值,在查找表中确定一个关键 字等于给定值的记录或数据元素

91静态查找表 口可以用顺序表,也可以用线性链表来表示静 态查找表。 顺序表的查找 typedef struct{//静态查找表的顺序存储结杉 ElemType米elem; ele em int length y0 length I SSTable length-1 length

9.1 静态查找表 可以用顺序表，也可以用线性链表来表示静 态查找表。 顺序表的查找 • typedef struct{ //静态查找表的顺序存储结构 • ElemType *elem; • int length; • }SSTable; elem length key 0 1 2 ... length-1 length

顺序查找( 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 1 性能分析:设P为查找表中第i个记录的概率(取P=1/n); C1为找到第i个记录所需的查找次数。则 ASL=2 P: C:= nP+(n-1)P,+ =[n+(n-1)+...+2+1]*1/n=(n+1)/2 若查找成功与不成功的概率相同,即P:=1/2n, ASL=nP1+(n-1)P2+..+2Pn-1+Pn+(n+1)/2=(n+1)*3/4

顺序查找（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) la下标:01234567891011 05,13,19,21,37,56,64,75,80,88,92 个1ow 个mid 个high d=[(low+high)/2];key=ST.elem[mid].key查找成功; 口当key〈ST. elem[mid.key时,下一个待查区间为[low,mid-1] 05,13,19,21,37,56,64,75,80,88,92 0个1ow个mid个high D当key>ST.elem[mid.key时下一个待查区间为mid+1,high]

有序表的查找: 折半查找（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时下一个待查区间为[mid+1,high]

折半查找的性能分析 查找上例中所有元素的判定二叉树为 6 判定树上每个结点需要的 查找次数刚好为该结点所 在的层数 查找成功时查找次数不会 超过判定树的深度 n个结点的判定树的深度 2 5 8)(11)为on+1 折半查找的算法复杂度为 判定树 logan+I

折半查找的性能分析 查找上例中所有元素的判定二叉树为 6 3 1 4 7 9 5 10 2 8 11 判定树 判定树上每个结点需要的 查找次数刚好为该结点所 在的层数. 查找成功时查找次数不会 超过判定树的深度 n个结点的判定树的深度 为[log2n]+1. 折半查找的算法复杂度为 [log2n]+1

9.2动态查找表 921二又排序树 什么是二叉排序树( Binary Sort tree)? 二叉排序树是空树或者是具有以下性质的二叉树: (1)若左子树非空,则左子树上所有结点的值均小于 0它的根结点的值; d(2)若右子树非空,则右子树上所有结点的值均大于 它的根结点的值; n(3它的左、右子树也分别为二又排序树

9.2 动态查找表 9.2.1 二叉排序树 什么是二叉排序树(Binary Sort Tree) ? 二叉排序树是空树,或者是具有以下性质的二叉树: (1)若左子树非空,则左子树上所有结点的值均小于 它的根结点的值; (2)若右子树非空,则右子树上所有结点的值均大于 它的根结点的值; (3)它的左、右子树也分别为二叉排序树

叉排序树举例 查找过程: 从根结点出发,结点 53 的值与key进行比较: (1)相等时查找成功; (2)key较大时,沿右 子树继续查找(无右子 树表明查找失败); 24 (3)key较小时,沿左 子树继续查找(无左子 90 树表明查找失败)。 二叉排序树 其中序遍历序列 78 3,12,24,37,45,53,61,78,90,100

二叉排序树举例 45 12 3 37 53 78 100 24 90 61 二叉排序树 查找过程： 从根结点出发，结点 的值与key进行比较： （1）相等时查找成功； （2）key较大时，沿右 子树继续查找（无右子 树表明查找失败）； （3）key较小时，沿左 子树继续查找（无左子 树表明查找失败）。 其中序遍历序列: 3,12,24,37,45,53,61,78,90,100

二叉排序树的生成唾插入结点 ¤二叉排序树的生成(连续进行插入操作) 口例如:对45,24,53,45,12,24,90 囚关键字序列的二叉排序树生成过程如下: 45 (45 (24 24 53 45 45 24 53 24 53 2 90

二叉排序树的生成(插入结点) 二叉排序树的生成(连续进行插入操作) 例如:对{45,24,53,45,12,24,90} 关键字序列的二叉排序树生成过程如下: 45 24 12 53 45 24 12 53 90 45 24 53 45 24 45