第八章查找

ASL成功 log 2 (n 1) 1
3. 索引顺序表的查找-分块查找 将顺序表中元素按元素下标顺序均匀分块，每个 分块称为子表。子表内部元素不要求按关键字有序存 储，但子表与子表之间必须是分块有序的，所谓分块 有序，是指对任意两个子表a, b，或者a中所有元素关 键字小于b中所有元素关键字，或者或者b中所有元素 关键字小于a中所有元素关键字。 建立一个关键字表(也称索引表)，存放每个子表 中的最大(或最小)关键字值以及对应子表在顺序表中 的起始下标。
0 6 12 22 12 13 8 9 20 33 42 44 38 24 48 60 58 74 49 86 53
索引顺序的查找方法： 第1步：先在索引表中对分或顺序查找关键字所在块； 第2步：在分块中顺序查找关键字。 索引顺序表查找的时间复杂度： 设元素总数为n，分块长度为s，则分块数为 n / s 。 (1) 索引表采用对分查找 s 1 n n s log 2 1 ASL成功 log 2 1 1 2 s s 2 (2) 索引表采用顺序查找 n / s 1 s 1 1 n ASL成功 s 1 2 2 2 s
西南交通大学信息科学与技术学院软件工程系‐赵宏宇 数据结构A 第8章‐16
西南交通大学信息科学与技术学院软件工程系‐赵宏宇
数据结构A 第8章‐15
8.2 静态查找表
续10完
8.3 动态查找表
1. 二叉排序树 (1) 二叉排序树的概念 二叉排序树(Binary Sort Tree, BST)或者是一棵空 树，或者是具有下列性质的二叉树： a. 若它的左子树不空，则左子树上所有结点的关键字 值小于根结点的值； b. 若它的右子树不空，则右子树上所有结点的关键字 值大于(或等于)根结点的值； c. 它的左、右子树也分别是二叉排序树。 (2) 二叉排序树的性质 中序遍历二叉排序树，所得结点访问次序为结点 关键字值的递增有序序列。
西南交通大学信息科学与技术学院软件工程系‐赵宏宇
数据结构A 第8章‐17
3
2015/6/2
8.3 动态查找表
续1
8.3 动态查找表
续2
(3) 二叉排序树的C语言数据类型定义 typedef struct node { KeyTp K; //关键字 ElemTp data; //数据域 struct node *lchild, *rchild; //左、右儿子指针 }BSTNode, *BST; (4) 二叉排序树的查找算法 BST search(BST bt, KeyTp key) //非递归算法 { while(bt&&bt->K!=key) if(key<bt->K) bt=bt->lchild; else bt=bt->rchild; return bt; //返回NULL表示查找失败 }
2015/6/2
第8章 查找
8.1 查找的基本概念 8.2 静态查找表 8.3 动态查找表 8.4 哈希表 第8章 作业
8.1 查找的基本概念
1. 查找表 由同一类型的数据元素(数据对象)组成的集合。 查找表的存储结构一般采用数组、树或散列表。 2. 静态与动态查找表 查询某个特点元素是否在查找表中或者从查找表 中提取某个特定元素的属性值称为静态查找表；若在 查找表中插入元素或者删除元素，称为动态查找表。 从信息处理的角度看，静态查找表就是对查找表 进行“只读”型查找；动态查找表则对查找表进行 “加工”型查找。
西南交通大学信息科学与技术学院软件工程系‐赵宏宇
数据结构A 第8章‐11
西南交通大学信息科学与技术学院软件工程系‐赵宏宇
数据结构A 第8章‐12
2
2015/6/2
8.2 静态查找表
续6
8.2 静态查找表
续7
对分查找的时间复杂度： 对于n个有序存储元素，二叉判定树的最大深度为 log 2 n 1 这是查找成功或失败时所需的最大循环次数。 此外，可以证明，当n>50时，
续5
初始： low 1： 2： 3：
mid low mid low high mid
high high
例2 若8元升序数组每个元素等概率查找，分析对分查 找的平均查找长度。 解：设8个元素按升序排列为a0, a1, …, a7, 则对分查找 每次循环比较的元素下标可以表示为如下二叉判定树： 1 3 ASL成功 1 2 2 3 4 4 1 2.625 8 1 5 根结点为mid位置元素； 左子树为low至mid-1元素； 0 2 4 6 右子树为mid+1至high元素。 7
西南交通大学信息科学与技术学院软件工程系‐赵宏宇 数据结构A 第8章‐19
BST search1(BST bt, KeyTp key) //递归算法 { if(bt==NULL||bt->K==key) return bt; if(key<bt->K) return search1(bt->lchild, key); return search1(bt->rchild, key); } (5) 二叉排序树插入结点算法 void insert(BST &bt, BST p) { parent=NULL; pt=bt; while(pt) { parent=pt; if(p->K<pt->K) pt=pt->lchild; else pt=pt->rchild; }
西南交通大学信息科学与技术学院软件工程系‐赵宏宇 数据结构A 第8章‐7
8.2 静态查找表
续1
(2) 顺序查找算法 int sqsearch(SqList &R, KeyTp key) { for(i=0; i<R.n; i++) if(R.elem[i].K==key) break; if(i>=R.n) return -1; //返回-1表示查找失败 return i; //查找成功，返回元素下标 } //用监视哨改进上述算法(避免每次循环判断i<R.n) int sqsearch1(SqList &R, KeyTp key) { R.elem[R.n]=key; //设置监视哨, 要求R.n<MAX_N for(i=0; R.elem[i].K!=key; i++); if(i==R.n) return -1; return i; }
西南交通大学信息科学与技术学院软件工程系‐赵宏宇 数据结构A 第8章‐5
(2) ASL失败分析 查找失败时平均关键字比较次数一般需要根据查 找表的存储结构具体分析。 (3) 综合查找成功与失败的ASL分析 ASL=p成功ASL成功+p失败ASL失败 其中，p成功与p失败分别表示查找成功与失败的概 率(p成功+p失败=1)，有时候可根据经验估计它们的值。 在教材和本电子教案中，一般只考虑(1), (2)。
西南交通大学信息科学与技术学院软件工程系‐赵宏宇
数据结构A 第8章‐1
西南交通大学信息科学与技术学院软件工程系‐赵宏宇
数据结构A 第8章‐2
8.1 查找的基本概念
续1
8.1 查找的基本概念
续2
3. 关键字 数据元素(对象)的某个属性值称为关键字。若关 键字可以唯一标识一个数据元素，称为主关键字，否 则称为次关键字。几个次关键字组成的关键字组也可 以构成主关键字。 关键字的大小：查找操作要求数据元素(对象)的关键 字应可以比较大小(至少应该可以比较“相等”)。对 于数值型关键字(C语言的整型、实型、指针类型)，比 较大小操作可以直接由高级语言的关系运算符(C语言 的<, <=, >, >=, ==, !=)实现；对于非数值型关键字，比 如：字符串等，关键字比较大小的操作需定义专门的 函数实现(C语言的strcmp函数)。
西南交通大学信息科学与技术学院软件工程系‐赵宏宇 数据结构A 第8章‐18
例3 若索引顺序表长度为n，索引表和每个分块内部均 采用顺序查找，求最佳分块长度。 解：设分块长度为s，则 n / s 1 s 1 1 n s 1 ASL成功 2 2 2 s 当n/s=s时，上式取得最小值。 即最佳分块长度(使ASL最小的分块长度)s满足 s2 n s n 。
西南交通大学信息科学与技术学院软件工程系‐赵宏宇 数据结构A 第8章‐4
8.1 查找的基本概念
续3
8.1 查找的基本概念
续4完
4. 查找与查找结果 根据给定关键字查找数据元素(对象)在查找表中 的存储位置或者实现数据元素的插入与删除称为查找。 查找的结果分为查找成功与查找失败(查找不成功)两 种情况。 5. 查找操作的时间复杂度分析方法 (1) ASL成功分析 查找成功时的时间复杂度由ASL(Average Search Length, 平均查找长度)决定，对于含有n个数据元素的 查找表{a0, a1, … , an-1}，成功查找的ASL定义为 n 1 p 表示查找ai的概率, ASL成功 pi ci i ci为成功找到ai的关键字比较次数。 i 0
西南交通大学信息科学与技术学院软件工程系‐赵宏宇 数据结构A 第8章‐10
西南交通大学信息科学与技术学院软件工程系‐赵宏宇
数据结构A 第8章‐9
8.2 静态查找表
例1 对分查找运态运行过程(key=40) 下标：0 3 1 10 2 13 3 17 4 40 5 43 6 50 7 70
续4
8.2 静态查找表
西南交通大学信息科学与技术学院软件工程系‐赵宏宇
数据结构A 第8章‐6
1
2015/6/2
8.2 静态查找表
1. 顺序表的查找 (1) 顺序表的存储结构 //用数组实现顺序查找表存储结构 #define MAX_N 最大元素个数 typedef struct { KeyTp K; //某关键字 … //其它属性 }ElemTp; //数据元素类型 typedef struct { ElemTp elem[MAX_N]; int n; //实际元素个数 }SqList; //数组实现的顺序查找表类型