内蒙古大学《算法与数据结构》讲义07跳表和散列
30页1、下载第7章跳表和散列对于一个有n 个元素的有序数组,用折半搜索法进行搜索所需要的时间为 O ( l o gn),而对一个有序链表进行搜索所需要的时间为O (n)。我们可以通过对有序链表上的全部或部分节点增加额外的指针,来提高搜索性能。在搜索时,可以通过这些指针来跳过链表中若干个节点,因此没有必要从左到右搜索链表中的所有节点。增加了向前指针的链表叫作跳表。跳表不仅能提高搜索性能,同时也可以提高插入和删除操作的性能。它采用随机技术决定链表中哪些节点应增加向前指针以及在该节点中应增加多少个指针。采用这种随机技术,跳表中的搜索、插入、删除操作的时间均为 O ( l o gn),然而,最坏情况下时间复杂性却变成(n)。相比之下,在一个有序数组或链表中进行插入 /删除操作的时间为O(n),最坏情况下为(n)。散列法是用来搜索、插入、删除记录的另一种随机方法。与跳表相比,它的插入 /删除操作时间提高到( 1 ),但最坏情况下仍为(n)。尽管如此,在经常将所有元素按序输出或按序号搜索元素时(如寻找第1 0个最小元素),跳表的执行效率将优于散列。本章所给出的应用是关于文本压缩和解压缩的应用,该应用用散列
2、实现。所设计的程序基于当前流行的L i v _ Z e m p e l _ We l c h算法(简称L Z W算法) 。7.1 字典字典(d i c t i o n a r y)是一些元素的集合。每个元素有一个称作 key 的域,不同元素的key 各不相同。有关字典的操作有: 插入具有给定关键字值的元素。 在字典中寻找具有给定关键字值的元素。 删除具有给定关键字值的元素。抽象数据类型D i c t i o n a ry的描述见ADT 7-1。若仅按照一个字典元素本身的关键字来访问该元素,则称为随机访问(random access) 。而顺序访问(sequential access)是指按照关键字的递增顺序逐个访问字典中的元素。顺序访问需借助于 Begin (用来返回关键字最小的元素 )和Next (用来返回下一个元素)等操作来实现。对于本章中所实现的部分字典,既可以采用随机访问方式,也可以采用顺序访问方式。ADT7-1 字典的抽象数据类型描述抽象数据类型D i c t i o n a ry 实例具有不同关键字的元素集合操作C re a t e( ):创建一个空字典S e a rc h
3、(k, x):搜索关键字为k 的元素,结果放入x;如果没找到,则返回f a l s e,否则返回t r u eI n s e rt (x):向字典中插入元素xDelete (k, x):删除关键字为k 的元素,并将其放入x有重复元素的字典(dictionary with duplicates)与上面定义的字典相似,只是它允许多个元素有相同的关键字。在有重复元素的字典中,在进行搜索和删除时需要一个规则来消除岐义。也就是说,如果要搜索(或删除)关键字为k 的元素,那么在所有关键字为k 值的元素中应该返回(或删除)哪一个呢? 在有些字典应用中,可能需要:删除在某个时间以后插入的所有元素。例7-1 一个班中注册学习数据结构课程的学生构成了一个字典。当有一个新学生注册时,就要在字典中插入与该学生相关的元素 (记录)。当有人要放弃这门课程时,则删除他的记录。在上课过程中,老师可以查询字典以得到与某特定学生相关的记录或修改记录 (例如,加入或修改考试成绩)。学生的姓名域可作为关键字。例7-2 在编译器中定义用户描述符的符号表(symbol table)就是一个有重复元素的字典。当定义一个描述符时,要
4、建立一个记录并插入到符号表中。记录中包括作为关键字的描述符以及其他信息,如描述符类型( i n t,float 等) 和(相关的)存储其值的内存地址。因为同样的描述符名可以定义多次(在不同的程序块中),所以符号表中必然存在有多个记录具有相同的关键字,搜索结果应是最新插入的元素。只有在程序块的结尾才能进行删除,所有在开始插入的元素最终都要被删除掉。7.2 线性表描述字典可以保存在线性序列(e1, e2, ) 中,其中ei是字典中的元素,其关键字从左到右依次增大。为了适应这种描述方式,可以定义两个类 SortedList 和S o r t e d C h a i n。前者采用公式化描述的线性表,如L i n e a r L i s t类(见程序3 - 1 ),而后者则采用链表描述,如C h a i n类(见程序3 - 8 )。练习1要求设计S o r t e d l L i s t类。应注意到在SortedList 中可以采用折半搜索法搜索元素,因此对有n个元素的字典进行搜索的时间为O ( l o gn)。进行插入时,必须确信该字典中没有相同关键字的元素 ,这要通过搜索来实现。然后进行插入
5、,此时要为新元素腾出空间而移动表中 O (n)个元素,故插入操作的时间是O (n)。删除则首先要找到欲删除的元素,然后再进行删除。在进行搜索之后,还要移动O (n)个元素以填补所删除元素的空间,因此删除的时间复杂性为 O (n)。程序7 - 1、程序7 - 2和程序7 - 3给出了类S o r t e d C h a i n的定义。E表示链表元素的数据类型, K是链表中排序所用到的关键字。类S o r t e d C h a i n N o d e与类C h a i n N o d e (见程序3 - 8 )一样,只有两个私有成员d a t a和l i n k。类S o r t e d C h a i n是类S o r t e d C h a i n N o d e的友元。程序7-1 类S o r t e d C h a i ntemplateclass SortedChainp u b l i c :SortedChain() first =0; S o r t e d C h a i n ( ) ;bool IsEmpty() const return first =0;int L
《内蒙古大学《算法与数据结构》讲义07跳表和散列》由会员东***分享,可在线阅读,更多相关《内蒙古大学《算法与数据结构》讲义07跳表和散列》请在金锄头文库上搜索。
幼儿园大班科学活动《智能留言机》课件
幼儿园大班语言绘本阅读《手电筒看见了什么》PPT
幼儿园小班科学《教宝宝认识动物》课件
幼儿园中班语言《灰狼家的小饭桶们》教案
【国家审计报告】审计报告W-06审计处罚决定书
【企业财务管理办法】会计档案管理办法
【员工主动离职-风险防范】劳动争议判决书
【员工被动离职-后续工作】70-070员工违反有关商业秘密的约定可以索赔吗
【员工被动离职-辞退申请】第六节 员工任免通知书
【员工被动离职-后续工作】70-050因员工的原因使服务期无法完成可以索赔吗
企业岗位管理制度12办公室行为规范
企业岗位管理制度30离职人员薪资发放通知单
幼儿园春游活动美丽的公园教案
呼职院电力机车制动机讲义11高速列车和重载列车制动
武理工《运输管理》教案第1章 运输系统
中海大海洋化学讲义02海洋的形成和海水的组成——兼论地球上水的起源、变迁和循环
武理工船舶柴油机习题库及答案04燃油喷射和燃烧
厦大海洋生态学课件07海洋初级生产力
华北理工水声学课件05声波在目标上的反射和散射-1目标强度及常见声纳目标的目标强度的一般特征
武理工船舶结构与设备课件02船体结构与管系-4专用船特殊船体结构特点
2023-09-25 37页
2023-09-25 10页
2023-09-25 33页
2023-09-25 26页
2023-04-03 8页
2023-04-03 4页
2023-04-03 8页
2023-03-29 10页
2023-03-22 10页
2023-03-20 8页