【免费】第6章查找与排序1资源-CSDN文库

数据结构

需积分: 0 165 浏览量 2022-08-04 14:51:37 上传评论收藏 252KB PDF 举报

资源推荐

资源详情

资源评论

第6章查找与排序

 主要内容：

 查找

 查找的基本概念

 静态查找表

 动态查找表

 哈希表

 内部排序

 排序的基本概念

 插入排序

 交换排序

 选择排序

 归并排序

§6.1查找的概述

 查找是一种常见的操作，其操作的对象叫查

找表

 查找表是一种松散的数据结构：集合

 集合的特点是数据元素间只存在同属于一个

集合的关系，这给查找带来不便，因此常常

人为加上一些关系，例如线性关系，树的关

系等。

查找表是一种非常灵活的数据结构

§6.1.1 基本概念

 查找表：由同一类型的数据元素(记录)构成的集合

 该数据元素可以由若干个数据项组成

 关键字：数据元素中某个数据项或组合项的值，用它

可以标识一个数据元素。

 主关键字：能唯一地标识一个数据元素的值为主关键字

 次关键字：不能唯一确定一个记录，一般用以识别若干个

记录的关键字

 查找：也叫检索，是根据给定的某个值，在查找表中

确定一个关键字等于给定值的记录或数据元素的过程

 查找成功：查到该记录，给出其在列表中的位置或其它信

息。

 查找失败：查不到记录，输出相应信息或把元素插入表中

 查找表的操作有四个基本内容：

 查询某个“特定的”数据元素是否在查找表中

 检索某个“特定的”数据元素的各种属性

 在查找表中插入一个数据元素

 从查找表中删除某个数据元素

 静态查找表：不涉及插入和删除操作的查找表，即

在查找过程中其结构始终不发生变化的查找表。

 也适用于经过一段时间的查找之后，集中地进行插入和

删除等修改操作的情况

 动态查找表：能进行全部四种操作的查找表，即其

结构在查找过程中要发生变化的查找表。

查找表的分类

查找表的结构

静态查找表

动态查找表

无序顺序表

有序顺序表

索引表

无监视哨

有监视哨

无监视哨

有监视哨

顺序查找

折半查找

*插值查找

*斐波那契查找

*静态树表查找

二叉排序树

*平衡二叉树

*B-/B

树

*键树

查找算法的性能

 算法效率评价：时间复杂度+空间复杂度

 查找：性能通过对关键字的比较次数来度量

 最大查找长度：对关键字的最多比较次数。

 平均查找长度：为确定记录在表中的位置，需要和关键

字进行比较的次数的期望值。

SL p c





pi p





为查找第个元素的概率，

为找到表中第个元素所需比较次数

注意：c

取决于算法；p

与算法无关，取决于具

体应用。如果p

是已知

的，则平均查找长度只

是问题规模的函数。

 对含有n个记录的表，其平均查找长度为：

典型的关键字类型说明

 类型说明

typedef float KeyType;

typedef int KeyType;

typedef char *KeyType;

typedef struct {

KeyType key;

…

}ElemType;

#define EQ(a,b) ((a)==(b))

#define LT(a,b) ((a)<(b))

#define LQ(a,b) ((a)<=(b))

#define EQ(a,b) (!strcmp((a),(b))

#define LT(a,b) (strcmp((a),(b))<0)

#define LQ(a,b) (strcmp((a),(b))>0)

 数据元素类型定义

 两个关键字比较约定

§6.1.2 静态查找表

 抽象数据类型定义

ADT Staticsearchtable

{ 数据对象D：……；

数据关系R：……；

基本操作P：

create(&ST,n); destroy(&ST);

search(ST,key); traverse(ST);

}ADT StaticSearchTable

1. 顺序表的查找

 顺序查找又称线性查找，是最基本的查找方法之一

 顺序表的数据结构

typedef struct{

ElemType *elem; //0为空单元

int Length; //表长度

}SSTable;

typedef struct

{ Keytype key;

其它域定义

}elemtype

 查找基本思想：从表的一端，一般是第n个记录开

始，逐个进行记录的关键字和给定值的比较。若相

等，则查找成功；若整个表扫描结束后仍未找到与

给定值相等的关键字，则查找失败。

改进的顺序查找算法

 算法思路：把给定值K作为第0个元素(该元素不是

查找表的元素)的关键字。这样不必判断是否已查

找完整个表。第0个元素起到了监视哨的作用。这

样可节省大量测试时间。

int search(SStable ST, Keytype key)//顺序表,也可以用链表

{ ST.elem[0].key=key; //0位置本身为空单元

for(i=ST.length; !EQ(ST.elem[i].key,key); --i);

return i;

} //若存在返回在静态表中的位置i ,否则i=0

优点：对表的结构无任何要求(勿需排序)，算法简单且适应面广

缺点：效率低(当表很长时，线性查找的效率很低)

性能分析(平均查找长度ASL)

 查找次数c

取决于所查记录在表中的位置。

 查找最后一个记录时，比较1次；查找第1个记录，比较n次

 在查找成功情况下，c

=n-i+1

 设表中每个元素的查找概率相等

11 1

111(1)1

(1)

nn n

ii i

nn n

ASL p c n i i

nnn

 



 

 



 设查找成功与不成功的可能性相同

，则查找成功时的概率修改为：



)1(3

)1(













ASL

 总平均查找长度

(1)

ASL n





 查找不成功查找长度

2. 折半查找(二分查找)

 有序表：对于以顺序方式存储的记录，若元素按关

键字非递减(或非递增)顺序排序则称为有序数组或

有序表

mid (low high) / 2









 查找思想：每次将待查记录所在范围缩小一半，直

到找到或找不到该记录为止。

 设表长为n，low、high和mid分别指向待查元素所在区

间的上界、下界和中点，k为给定值

 初始时，令low=1，high=n，

，让k与mid指向的记录比较

 若k==elem[mid].key，查找成功

 若k<elem[mid].key，则在左半区比较: high=mid-1

 若k>elem[mid].key，则在右半区比较: low=mid+1

 重复上述操作，如果直至low>high，查找失败

算法程序

 查找关键字为21的数据元素

low mid high

low

high

mid

int search_bin(SStable ST, KeyType key)

{ low=1; high=ST.length;

while (low<=high)

{ mid=(low+high)/2;

if (EQ(key, ST.elem[mid].key)) return mid;

else if (LT(key, ST.elem[mid].key)) high=mid-1;

else low=mid+1; }

return 0; }

①②

③④ ⑤ ⑥ ⑦ ⑧⑨

⑩

⑪

13 19 21 37 56 64 75 80 88 92

05 21

64 88

性能分析

成功的查找恰好是走了一条从根结点到被查找结点的路径

失败的查找则是经历了一条从根结点到某个外部结点的路径

2 5

13 37 75

1223444

ii i

ASL p c c









low mid high

low high

mid

①②

③④⑤⑥⑦⑧⑨

⑩

⑪

13 19 21 37 56 64 75 80 88 92

二叉判定树

 判定树：用来描述折半查找过程的二叉树。树中的

每个结点对应有序表中的一个记录，结点的值为该

记录在表中的位置。也称折半查找判定树或二叉判

定树

 判定树的形态只与表结点的个数有关，与输入实例的关

键字的取值无关。

log 1n











 特点：

 叶子结点所在层次之差最多为1

 具有n个结点的判定树的深度为。特别地，当

n=2

-1 时，二叉树判断树一定是深度为d的满二叉树。

 和给定值进行比较的次数恰为该结点在判定树中的层次

 不成功查找的比较次数也不超过判定树的深度

111

11 1

2log(1)1log(1)1

nnh

ii i

iij

ASL p c c j n n

nn n







 



 结论：

 当元素有序时，折半查找比顺序查找效率高得多。但当

元素无序时，需要先进行费时的排序，即使采用高效率

的排序方法也要花费O(nlogn)的时间。

 折半查找只适用顺序存储结构。若要经常插入和删除元

素，此时宜采用二叉排序树结构。当查找较少时，也可

以用链表存储并进行顺序查找。

 设表长n=2

-1，h=log

(n+1)，即判定树是深度

为h的满二叉树，则层次为h的结点有2

h-1

个。设每

个记录的查找概率相等：

性能分析(.续)

3. 索引顺序表的查找—分块查找

 分块查找又称索引顺序查找

 表中元素均匀地分成块(子表)，块间按大小排序，块内

不排序

 建立一个关键字表(也称索引表)，按大小顺序存放每块

中最大或最小关键字值，其指针项给出每块起始地址。

 分块有序：是指第二个子表中所有记录的关键字均

大于第一个子表中的最大关键字。

22 12 13 8 9 20 33 42 44 38 24 48 60 58 74 49 86 53

22 48 86

1 7 13

最大关键字

起始地址

索引表

 算法思想：

 按折半查找获得所查关键字所对应的记录块

 按线性查找在块中找到key对应的记录

 查找效率：设有n个元素，每块s个元素，

1n 

分块查找过程

 平均查找长度=顺序查找平均次数+线性查找平均次数

 结论：其效率介于折半查找和线性查找之间。

 容易证明，当s取时，分块查找可取最小值

 平均查找长度=折半查找平均次数+线性查找平均次数



log / 1 1 log 1

ASL n s









  











(2)

222

ASL s













剩余12页未读，继续阅读

评论收藏

内容反馈

FelaniaLiu

粉丝: 22
资源: 334

第6章 查找与排序1

计算机程序设计艺术（第3卷 第二版）排序与查找（中文版+带书签目录）pdf格式

二叉排序树查找

吉大数据结构课程 数据结构与算法课程 由浅入深 讲解清晰 08 第八章 查找（共91页）.pptx

【精品课件】数据结构与算法 数据结构与C语言 data structure课程 第7章 查找（共105页）.ppt

【精品课件】数据结构与算法 数据结构与C语言 data structure课程 第8章 排序（共223页）.ppt

数据结构第九章 查找作业及答案（100分）.docx

完整精品课件 吉林大学数据结构与算法课程 由浅入深 讲解清晰 07 第七章 排序（共151页）.ppt

算法：算法C语言实现 第1-4部分 基础知识、数据结构、排序及搜索

C常用算法程序集源码-每章至少10个例子

完整精品课件 吉林大学数据结构与算法课程 由浅入深 讲解清晰 06 第六章 递归（共62页）.ppt

【精品课件】数据结构与算法 数据结构与C语言 data structure课程 第6章 图（共126页）.ppt

查找排序实验报告.doc

单链表的创建，查找，排序，插入，删除

数据结构C语言版--中国铁道出版社

数据结构(C#)顺序表,栈,队列,图,树,查找,排序

Pascal的多种退出语句用法.doc

数据结构与算法(C#)

java数据结构和算法.（第二版）

数据结构 实现二叉排序树的各种算法(2)

最新版ISO/IEC 27001:2022、ISO 27002:2022中英文合集

Goby红队版-win-x64-2.4.7版本

Chrome Header Editor 插件

ISO SAE 21434-2021 中文版.pdf

安全认证cisp教材全套

OpenVAS GVM 中文翻译补丁

2024最新：Hvv中常见的面试问题

现代永磁同步电机控制原理及MATLAB仿真__袁雷编著1

全面的安全基线核查清单

最新资源

第6章查找与排序1

计算机程序设计艺术（第3卷第二版）排序与查找（中文版+带书签目录）pdf格式

吉大数据结构课程数据结构与算法课程由浅入深讲解清晰 08 第八章查找（共91页）.pptx

【精品课件】数据结构与算法数据结构与C语言 data structure课程第7章查找（共105页）.ppt

【精品课件】数据结构与算法数据结构与C语言 data structure课程第8章排序（共223页）.ppt

数据结构第九章查找作业及答案（100分）.docx

完整精品课件吉林大学数据结构与算法课程由浅入深讲解清晰 07 第七章排序（共151页）.ppt

算法：算法C语言实现第1-4部分基础知识、数据结构、排序及搜索

完整精品课件吉林大学数据结构与算法课程由浅入深讲解清晰 06 第六章递归（共62页）.ppt

【精品课件】数据结构与算法数据结构与C语言 data structure课程第6章图（共126页）.ppt

数据结构实现二叉排序树的各种算法(2)