本讲主要内容.ppt

1、词典、Hash表、集合,2011/04/20,2,本讲主要内容：,集合及抽象数据结构 字典及抽象数据结构 二分查找算法及复杂度分析 二叉排序树的建构与维护,3,字典的基本概念,字典是一个由数据记录（record）构成的顺序表，其中记录中有一个特殊的字段，称为关键码。每条记录都有唯一的不重复的关键码取值。 字典中的元素之间能够根据其关键码进行比较与排序，对字典元素的插入、删除和检索等操作一般也以关键码为依据进行。 字典可以看成是由关键码值k到数据记录r的一个对应。唯一的关键码取值可以唯一对应一条数据记录。,4,字典与查找表 由一些具有相同可辨认特性的数据元素构成的集合。,5,根据给定的某个值，在

2、查找表中确定一个其关键字等于给定值的数据条目。 顺序检索、二分检索。 衡量一个字典检索算法效率的主要标准是检索过程中对关键码的平均比较次数：,字典的检索（searching）,6,Dictionary表示抽象数据类型字典， DicElement 表示字典元素类型， KeyType 表示元素中关键码的类型， Position 表示字典中元素的位置。,Dictionary的抽象数据类型,ADT Dictionary operations Dictionary createEmptyDictionary ( void ) /创建一个空字典。 int search(Dictionary dic, Ke

3、yType key, Position p) /在字典dic中检索关键码为key的记录的位置p。 int insert(Dictionary dic, DicElement ele) /在字典dic中插入记录ele。* int delete(Dictionary dic, KeyType key) /在字典dic中删除关键码为key的记录。 * end ADT Dictionary,7,字典的顺序检索,字典中的元素可以是无序的，但为了实现的方便，可以把字典中的元素按关键码值排序。 从字典的一端开始顺序扫描，将字典中元素的关键码和给定值比较： 如果相等，则检索成功； 当扫描结束时，还未找到关键码

4、等于给定值的元素，则检索失败。 顺序检索算法适用于非排序顺序存储或非关键码字段检索 顺序检索的算法复杂度为O(n)，平均比较次数为n/2。,8,字典的二分查找,二分查找(binary search) 要求： 查找表为有序表，即表中 结点按关键字有序排列，并且采用顺序存储结构。 基本思想： 确定搜索区间的中点位置： 然后将待查的key值与rangemid.key比较：若相等，则查找成功并返回此位置，否则确定新的查找区间，继续二分查找.,9,二分查找算法：,10,二分法检索每经过一次比较就将检索范围缩小一半，第i次比较可能涉及的元素=2i -1。 二分法检索的最大检索长度为：log2(n+1) 算

5、法复杂度：log2(n),二分查找性能分析,11,字典的基本概念,字典是一个由数据记录（record）构成的顺序表，其中记录中有一个特殊的字段，称为关键码。每条记录都有唯一的不重复的关键码取值。 字典中的元素之间能够根据其关键码进行比较与排序，对字典元素的插入、删除和检索等操作一般也以关键码为依据进行。 字典可以看成是由关键码值k到数据记录r的一个对应。唯一的关键码取值可以唯一对应一条数据记录。,12,根据给定的某个值，在查找表中确定一个其关键字等于给定值的数据条目。 顺序检索、二分检索。 衡量一个字典检索算法效率的主要标准是检索过程中对关键码的平均比较次数：,字典的检索（searching）

6、,13,Dictionary表示抽象数据类型字典， DicElement 表示字典元素类型， KeyType 表示元素中关键码的类型， Position 表示字典中元素的位置。,Dictionary的抽象数据类型,ADT Dictionary operations Dictionary createEmptyDictionary ( void ) /创建一个空字典。 int search(Dictionary dic, KeyType key, Position p) /在字典dic中检索关键码为key的记录的位置p。 int insert(Dictionary dic, DicElement

7、 ele) /在字典dic中插入记录ele。* int delete(Dictionary dic, KeyType key) /在字典dic中删除关键码为key的记录。 * end ADT Dictionary,14,Hash的思想：一种高效的词典结构,将数据集合中的所有对象都唯一对应到一个关键值，然后通过关键值映射到一个表中（哈希表）进行存放，之后可以根据关键值实现迅速查找。 其他实现方案： 插入速度 检索速度 顺序表 链表,15,Hash表的问题：空间冗余，多对一（碰撞）,确定性问题：关键码分布已知。 编码-解码 非确定性问题：关键码分布未知且理论上编码空间巨大。（vs 实际问题规模）,

8、16,17,18,碰撞、负载因子、堆积,19,Hash函数设计的一般思路：,要能够保证是空间的全覆盖 尽可能在指定空间内表现为随机分布，避免堆积 数字分析法、中平方法、基数转换法 除余法,20,碰撞处理,开地址法 拉链法,21,22,23,24,如何处理文件中数据记录的删除？,25,Hash表的应用,词典索引 用来判重和统计数目,26,常用的字符串hash函数,27,28,网络爬虫与hash表：,网络爬虫是什么？ 怎样爬？ 整体框架 核心算法 算法改进,29,怎样搜集?, , , ,网页为节点 网页中的HyperLink为有向边 Crawl = 图遍历, right?,30,串匹配算法中运用has