北京理工大学数据结构查找课件

1、第 2 2 页第第9章章 查查 找找l查找表查找表：由同一类型的数据元素（或记录）构成的：由同一类型的数据元素（或记录）构成的集合集合。l查找表的查找表的基本操作基本操作1) 查询查询某个某个“特定的特定的”数据元素是否在表中数据元素是否在表中2) 检索检索某个某个“特定的特定的”数据元素的各种数据元素的各种属性属性3) 插入插入一个数据元素一个数据元素4) 删去删去某个数据元素某个数据元素l静态静态查找表：只作查找表：只作查询查询和和检索检索操作的查找表。操作的查找表。l动态动态查找表：在查找表：在查找查找过程中同时作过程中同时作插入插入或或删除删除操作操作的查找表。的查找表。第 3 3 页

2、第第9章章 查查 找找l关键字关键字：能标识一个数据元素（或记录）的数据项。：能标识一个数据元素（或记录）的数据项。l主关键字主关键字：能唯一地标识一个记录的关键字。：能唯一地标识一个记录的关键字。l次关键字次关键字：用以识别若干记录的关键字。：用以识别若干记录的关键字。 学号学号 姓名姓名 专业专业 年龄年龄 20090001 王洪王洪 自动化自动化 17 20090002 李文李文 自动化自动化 18 20090003 谢军谢军 自动化自动化 18 20090004 张辉张辉 信息工程信息工程 20 20090005 李文李文 信息工程信息工程 19第 4 4 页第第9章章 查查 找找l查

3、找：查找：根据给定的某个值，在查找表中确定一个其根据给定的某个值，在查找表中确定一个其关键字等于给定值的记录或数据元素，若表中存在关键字等于给定值的记录或数据元素，若表中存在这样的记录，则称查找这样的记录，则称查找成功成功，查找，查找结果结果为该记录在为该记录在查找表中的位置；否则称为查找查找表中的位置；否则称为查找不成功不成功，查找，查找结果结果为为0或或NULL。 学号学号 姓名姓名 专业专业 年龄年龄 20090001 王洪王洪 自动化自动化 17 20090002 李文李文 自动化自动化 18 20090003 谢军谢军 自动化自动化 18 20090004 张辉张辉 信息工程信息工程

4、 20 20090005 李文李文 信息工程信息工程 19第 5 5 页第第9章章 查查 找找l查找方法评价查找方法评价l查找算法的基本操作：查找算法的基本操作：比较比较l平均查找长度平均查找长度ASL ( Average Search Length)：为确为确定记录在表中的位置，需和给定值进行定记录在表中的位置，需和给定值进行比较比较的关键的关键字个数的字个数的期望值期望值。l平均查找长度：平均查找长度： ASL = PiCi l Pi：查找第：查找第 i 个记录的概率，且个记录的概率，且 Pi=1 ；l Ci：查找第：查找第 i 个记录所需的比较次数。个记录所需的比较次数。第 6 6 页第

5、第9章章 查查 找找l关键字类型定义关键字类型定义 typedef float KeyType; 实型实型 typedef int KeyType; 整型整型 typedef char* KeyType; 字符串型字符串型l数据元素类型定义数据元素类型定义 typedef struct KeyType key; 关键字域关键字域 其他域其他域 ElemType; key 第 7 7 页第第9章章 查查 找找l对数值型关键字对数值型关键字 #define EQ(a,b) (a) = = (b) #define LT(a,b) (a) (b) #define LQ(a,b) (a) = (b)l对

6、字符串型关键字对字符串型关键字 #define EQ(a,b) (!strcmp(a),(b) #define LT(a,b) (strcmp(a),(b) 0) #define LQ(a,b) (strcmp(a),(b) = 0)第 8 8 页第第9章章 查查 找找l静态查找静态查找在指定的表中查找某一个在指定的表中查找某一个“特定特定”的数据元的数据元素是否存在，素是否存在，检索检索某一个某一个“特定特定”数据元素的各数据元素的各种属性。种属性。l动态查找动态查找在查找的过程中在查找的过程中同时插入同时插入表中不存在的数据表中不存在的数据元素，或者从查找表中元素，或者从查找表中删除删除已

7、存在的某个数据元已存在的某个数据元素。素。第 9 9 页第第9章章 查查 找找9.1 静态查找表静态查找表 9.2 动态查找表动态查找表 9.3 哈希表哈希表第 1010 页l静态查找表静态查找表无序表无序表的查找：的查找：顺序顺序查找查找有序表有序表的查找：的查找：折半折半查找查找索引顺序表索引顺序表的查找：的查找：分块分块查找查找9.1 静态查找表静态查找表第 1111 页l 查找表查找表用用线性表线性表表示表示L1=(45,61,12,3,37,24,90,53,98,78）l 用用顺序表顺序表表示静态查找表表示静态查找表l 用用线性链表线性链表表示静态查找表表示静态查找表l 查找方法：

8、查找方法：顺序顺序查找查找9.1 静态查找表静态查找表第 1212 页l顺序表类型定义顺序表类型定义 typedef struct ElemType *elem; / 0号单元留空号单元留空 int length; SSTable;9.1 静态查找表静态查找表-顺序表查找顺序表查找 0 1 2 3 4 5 6 7 8 9 10 m-0 1 2 3 4 5 6 7 8 9 10 m-1 1 45 61 1245 61 12 3 37 24 90 53 98 78 3 37 24 90 53 98 78ST.elemSSTable ST;第 1313 页int Search_Seq ( SSTab

9、le ST, KeyType key ) ST.elem0.key = key; / “哨兵哨兵” for ( i=ST.length; !EQ(key, ST.elemi.Key; -i )； return i; / 若表中不存在待查元素若表中不存在待查元素, i=09.1 静态查找表静态查找表 0 1 2 3 4 5 6 7 8 9 10 m-0 1 2 3 4 5 6 7 8 9 10 m-1 1 45 61 1245 61 12 3 37 24 90 53 98 78 3 37 24 90 53 98 78ST.elemkey免去查找过程中每免去查找过程中每一步都要检测整个一步都要检测

10、整个表是否查找完毕表是否查找完毕第 1414 页例例1：在下表中查找在下表中查找 key = 8 的结点。的结点。9.1 静态查找表静态查找表80 01 12 2n-3n-3n-2n-2n-1n-1n nST.elem ST.elem keykey10010010100 07 71 13 3iiiiiii查找不成功，查找不成功，i = 080 01 12 2n-3n-3n-2n-2n-1n-1n nST.elem ST.elem keykey例例2：在下表中查找在下表中查找 key = 8 的结点。的结点。10010010100 08 81 13 3iii查找成功，查找成功，i = n-2第

11、1515 页l顺序查找顺序查找的特点：的特点：无排序要求；无排序要求；存储结构：顺序、链式；存储结构：顺序、链式；平均查找长度平均查找长度ASLSS=(n+1)/2；9.1 静态查找表静态查找表第 1616 页l查找表：用查找表：用有序表有序表表示表示l查找方法：查找方法：折半折半查找（二分查找）查找（二分查找）l查找过程：先确定待查记录所在的范围（区间），查找过程：先确定待查记录所在的范围（区间），然后然后逐步缩小范围逐步缩小范围直到找到或找不到该记录为止。直到找到或找不到该记录为止。例：例：有原始查找表有原始查找表45, 61, 12, 3, 37, 24, 90, 53, 98, 78为

12、进行折半查找，需要先进行为进行折半查找，需要先进行排序排序： L=(3, 12, 24, 37, 45, 53, 61, 78, 90, 98)9.1 静态查找表静态查找表-有序表查找有序表查找第 1717 页例：查找例：查找 Key=24 的记录。的记录。9.1 静态查找表静态查找表-有序表查找有序表查找 1 2 3 4 5 6 7 8 9 101 2 3 4 5 6 7 8 9 10 3 12 24 37 45 53 61 78 90 983 12 24 37 45 53 61 78 90 98lowlow midmid highhigh 1 2 3 4 5 6 7 8 9 101 2 3

13、 4 5 6 7 8 9 10 3 12 24 37 45 53 61 78 90 983 12 24 37 45 53 61 78 90 98lowlowmidmid highhigh 242445 45 24241212 1 2 3 4 5 6 7 8 9 101 2 3 4 5 6 7 8 9 10 3 12 24 37 45 53 61 78 90 98 3 12 24 37 45 53 61 78 90 98LowLow highhighmidmid第 1818 页int Search_Bin ( SSTable ST, KeyType key ) low=1; high=ST.le

14、ngth;return 0; /表中不存在待查元素表中不存在待查元素/Search_Bin9.1 静态查找表静态查找表-有序表查找有序表查找while ( lowkey，令，令highmid1low=1high=7mid=4012key4891011131934567elemhigh=3mid=2low=1ST.elemmid.key8 key，令，令highmid1high=7mid=4low=1low=1high=3mid=2ST.elemmid.key8 key，令，令highmid1low=1mid=1ST.elemmid.key4 lchild=NULL f-rchild=NULLf

15、-lchild=NULL f-rchild=NULLl p p只有左子树或右子树只有左子树或右子树l p p左、右子树均非空左、右子树均非空9.2 动态查找表动态查找表 F F P PP PR RP PL Lf fp p第 3838 页l二叉排序树二叉排序树的删除操作（一）的删除操作（一）lp为叶子结点为叶子结点：9.2 动态查找表动态查找表pf F P删除前删除前f F删除后删除后l 只需修改只需修改 p 双亲双亲 f 的指针的指针：f-lchild=NULL f-rchild=NULL第 3939 页l二叉排序树二叉排序树的删除操作（二）的删除操作（二）n p只有左子树只有左子树：用用p的

16、左孩子代替的左孩子代替p (1)(2)9.2 动态查找表动态查找表SQPLP中序遍历：中序遍历：Q S PL PSQPL中序遍历：中序遍历：Q S PL(2)SPPLQ中序遍历：中序遍历：PL P S QSPLQ中序遍历：中序遍历：PL S Q(1)第 4040 页l二叉排序树二叉排序树的删除操作（二）的删除操作（二）n p只有右子树只有右子树：用用p的右孩子代替的右孩子代替p (3)(4)9.2 动态查找表动态查找表中序遍历：中序遍历：P PR S QSPRQ中序遍历：中序遍历：PR S Q(3)SPPRQ中序遍历：中序遍历：Q S P PRSQPR中序遍历：中序遍历：Q S PR(4)SQ

17、PRP第 4141 页l二叉排序树二叉排序树的删除操作（三）：的删除操作（三）：p左、右子树均非空左、右子树均非空n沿沿 p 左子树的根左子树的根 C 的右子树分支找到的右子树分支找到 S，S的右子的右子树为空，将树为空，将 S 的左子树成为的左子树成为 S 的双亲的双亲Q 的右子树，的右子树，用用 S 取代取代 p (5)9.2 动态查找表动态查找表FPCPRCLQQLSSL中序遍历：中序遍历：CL C QL Q SL S P PR FFSCPRCLQQLSL中序遍历：中序遍历：CL C QL Q SL S PR F(5)第 4242 页l二叉排序树二叉排序树的删除操作（三）：的删除操作（三

18、）：p左、右子树均非空左、右子树均非空n 若若p 左子树的根左子树的根 C 无右子树，无右子树，用用 C 取代取代 p (6)9.2 动态查找表动态查找表FPCPRCL中序遍历：中序遍历：CL C P PR FFCPRCL中序遍历：中序遍历：CL C PR F(6)第 4343 页l二叉排序树二叉排序树的删除操作，的删除操作，分三种情况：分三种情况：n p为叶子结点为叶子结点，只需修改，只需修改 p 双亲双亲 f 的指针的指针： f-lchild=NULL f-rchild=NULLn p只有左子树或右子树只有左子树或右子树 p只有左子树，用只有左子树，用p的左孩子代替的左孩子代替p (1)(

19、2) p只有右子树，用只有右子树，用p的右孩子代替的右孩子代替p (3)(4)n p左、右子树均非空左、右子树均非空 沿沿 p 左子树的根左子树的根 C 的右子树分支找到的右子树分支找到 S，S的右子树的右子树为空，将为空，将 S 的左子树成为的左子树成为 S 的双亲的双亲Q 的右子树，用的右子树，用 S 取代取代 p (5) 若若 C 无右子树，用无右子树，用 C 取代取代 p (6)9.2 动态查找表动态查找表第 4444 页l二叉排序树二叉排序树的删除操作的删除操作9.2 动态查找表动态查找表例例805012060110150557053删除删除508060120110150557053

20、删除删除60805512011015053701052581376删除删除1085257136删除删除78525613第 4545 页l性能分析性能分析查找表：查找表：3,12,24,37,45,53,61,78,90,989.2 动态查找表动态查找表 45 12 3 37 53 90 24 78 98 61ASL=(1+2+3+4+ASL=(1+2+3+4+5+6+7+8+9+15+6+7+8+9+10)/10=5.50)/10=5.5ASL=(1+2ASL=(1+2 2 2+3+3 4+44+4 3 3)/10)/10 =2.9 =2.9 4512337539024789861单支树单支树

21、第 4646 页二叉排序树的特点之一（缺陷）：二叉排序树的特点之一（缺陷）：没有对没有对树的深度进行控制树的深度进行控制。l在构造二叉排序树的过程中进行在构造二叉排序树的过程中进行“平衡化平衡化”处处理，成为理，成为平衡二叉树平衡二叉树（AVL树）。树）。l平衡二叉树：左子树和右子树的平衡二叉树：左子树和右子树的深度之差深度之差的绝的绝对值不超过计划。对值不超过计划。9.2 动态查找表动态查找表第 4747 页l二叉排序树的特点二叉排序树的特点含有含有n个结点的二叉排序树不唯一，与结点插个结点的二叉排序树不唯一，与结点插入的顺序有直接关系。当查找失败后，在叶结点入的顺序有直接关系。当查找失败后

22、，在叶结点插入。插入。删除某个结点后，二叉排序树要重组。删除某个结点后，二叉排序树要重组。没有对树的深度进行控制。没有对树的深度进行控制。l二叉排序树的适用范围二叉排序树的适用范围用于组织规模较小的、内存中可以容纳的数据。用于组织规模较小的、内存中可以容纳的数据。对于数据量较大必须存放在外存中的数据，则无对于数据量较大必须存放在外存中的数据，则无法快速处理。法快速处理。9.2 动态查找表动态查找表第 4848 页在记录的在记录的存储地址存储地址和它的和它的关键字关键字之间建立一个确之间建立一个确定的定的对应关系对应关系，一次存取就能得到所查元素的查找，一次存取就能得到所查元素的查找方法。即：方

23、法。即：1) 哈希哈希(Hash)函数函数是一个映象，即：将关键字是一个映象，即：将关键字的集合映射到某个地址集合上，的集合映射到某个地址集合上，映象原则映象原则：地址集合的大小不超出允许范围。：地址集合的大小不超出允许范围。哈希函数：哈希函数：addr(ai)=H(ki)ai是表中的一个元素是表中的一个元素addr(ai)是是ai的存储地址的存储地址ki是是ai的关键字的关键字。9.3 哈希表哈希表关键字关键字集合集合存储地址存储地址集合集合hash第 4949 页2) 由于哈希函数是一个压缩映象，因此，在一由于哈希函数是一个压缩映象，因此，在一般情况下，很容易产生般情况下，很容易产生“冲突

24、冲突”现象，现象，即：即：key1 key2，而，而 f(key1) = f(key2)。3) 很难找到一个不产生冲突的哈希函数。一般很难找到一个不产生冲突的哈希函数。一般情况下，只能选择恰当的哈希函数，使情况下，只能选择恰当的哈希函数，使冲突尽可能冲突尽可能少少地产生。地产生。9.3 哈希表哈希表 1 2 3 51 52年份年份人数人数 1949 1950 1951 1999 2000 2000 2100 2200 4400 4420例例: 某地区的人口统计表某地区的人口统计表H(年度）年度）=年度年度-1948第 5050 页9.3 哈希表哈希表例例: 30个地区的各民族人口统计表个地区的

25、各民族人口统计表编号编号 地区地区 总人口总人口 汉族汉族 回族回族.1 北京北京2 上海上海.以以编号编号作关键字，作关键字，构造构造哈希函数：哈希函数：H(key)=keyH(1)=1H(2)=2以以地区地区作关键字，取地区作关键字，取地区名称第一个拼音字母的序号名称第一个拼音字母的序号作哈希函数：作哈希函数：H(Beijing)=2 H(Shanghai)=19 H(Shenyang)=19第 5151 页哈希表哈希表应用哈希函数，由记录的关键应用哈希函数，由记录的关键字确定记录在表中的地址，并将记录放入此地字确定记录在表中的地址，并将记录放入此地址，这样构成的表叫哈希表。址，这样构成的

26、表叫哈希表。哈希查找哈希查找又叫散列查找，利用哈希函又叫散列查找，利用哈希函数进行查找的过程。数进行查找的过程。9.3 哈希表哈希表第 5252 页9.3 哈希表哈希表1、直接定址法、直接定址法：取关键字或关键字的某个线性函：取关键字或关键字的某个线性函数值为哈希地址。数值为哈希地址。2、数字分析法、数字分析法：取关键字的若干数位组成哈希地：取关键字的若干数位组成哈希地址。址。 3、平方取中法、平方取中法：取关键字平方后的中间几位为哈：取关键字平方后的中间几位为哈希地址。希地址。 4、折叠法、折叠法：将关键字分割成位数相同的几部分，：将关键字分割成位数相同的几部分，然后取这几部分的叠加和作为哈希地址。然后取这几部分的叠加和作为哈希地址。 第 5353 页9.3 哈希表哈希表5、除留余数法：、除留余数法：取关键字被某个不大于哈希表长取关键字被某个不大于哈希表长m的数的数p除后所得余数为哈希地址。除后所得余数为哈希地址。 H(key)= key%p，p=m6、随机数法：、随机数法：选择一个随机函数，取关键字的随选择一个随机函数，取关键字的随机函数值为它的哈希地址。机函数值为它的哈希地址。