《内蒙古大学《算法与数据结构》讲义07跳表和散列》由会员分享，可在线阅读，更多相关《内蒙古大学《算法与数据结构》讲义07跳表和散列（30页珍藏版）》请在金锄头文库上搜索。
1、下载第7章跳表和散列对于一个有n 个元素的有序数组，用折半搜索法进行搜索所需要的时间为 O ( l o gn)，而对一个有序链表进行搜索所需要的时间为O (n)。我们可以通过对有序链表上的全部或部分节点增加额外的指针，来提高搜索性能。在搜索时，可以通过这些指针来跳过链表中若干个节点，因此没有必要从左到右搜索链表中的所有节点。增加了向前指针的链表叫作跳表。跳表不仅能提高搜索性能，同时也可以提高插入和删除操作的性能。它采用随机技术决定链表中哪些节点应增加向前指针以及在该节点中应增加多少个指针。采用这种随机技术，跳表中的搜索、插入、删除操作的时间均为 O ( l o gn)，然而，最坏情况下时间复杂
2、性却变成(n)。相比之下，在一个有序数组或链表中进行插入 /删除操作的时间为O(n)，最坏情况下为(n)。散列法是用来搜索、插入、删除记录的另一种随机方法。与跳表相比，它的插入 /删除操作时间提高到( 1 )，但最坏情况下仍为(n)。尽管如此，在经常将所有元素按序输出或按序号搜索元素时(如寻找第1 0个最小元素)，跳表的执行效率将优于散列。本章所给出的应用是关于文本压缩和解压缩的应用，该应用用散列实现。所设计的程序基于当前流行的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）是一些元素的集合。每
3、个元素有一个称作 key 的域，不同元素的key 各不相同。有关字典的操作有： 插入具有给定关键字值的元素。 在字典中寻找具有给定关键字值的元素。 删除具有给定关键字值的元素。抽象数据类型D i c t i o n a ry的描述见ADT 7-1。若仅按照一个字典元素本身的关键字来访问该元素，则称为随机访问（random access） 。而顺序访问（sequential access）是指按照关键字的递增顺序逐个访问字典中的元素。顺序访问需借助于 Begin (用来返回关键字最小的元素 )和Next (用来返回下一个元素)等操作来实现。对于本章中所实现的部分字典，既可以采用随机访问方式，也可
4、以采用顺序访问方式。ADT7-1 字典的抽象数据类型描述抽象数据类型D i c t i o n a ry 实例具有不同关键字的元素集合操作C re a t e( )：创建一个空字典S e a rc h(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）与上面定义的字典相似，只是它允许多个元素有相同的关键字。在有重复元素的字典中，在进行搜索和删除时需要一个规
5、则来消除岐义。也就是说，如果要搜索(或删除)关键字为k 的元素，那么在所有关键字为k 值的元素中应该返回(或删除)哪一个呢? 在有些字典应用中，可能需要：删除在某个时间以后插入的所有元素。例7-1 一个班中注册学习数据结构课程的学生构成了一个字典。当有一个新学生注册时，就要在字典中插入与该学生相关的元素 (记录)。当有人要放弃这门课程时，则删除他的记录。在上课过程中，老师可以查询字典以得到与某特定学生相关的记录或修改记录 (例如，加入或修改考试成绩)。学生的姓名域可作为关键字。例7-2 在编译器中定义用户描述符的符号表（symbol table）就是一个有重复元素的字典。当定义一个描述符时，要
6、建立一个记录并插入到符号表中。记录中包括作为关键字的描述符以及其他信息，如描述符类型( i n t，float 等) 和(相关的)存储其值的内存地址。因为同样的描述符名可以定义多次(在不同的程序块中)，所以符号表中必然存在有多个记录具有相同的关键字，搜索结果应是最新插入的元素。只有在程序块的结尾才能进行删除，所有在开始插入的元素最终都要被删除掉。7.2 线性表描述字典可以保存在线性序列(e1, e2, ) 中，其中ei是字典中的元素，其关键字从左到右依次增大。为了适应这种描述方式，可以定义两个类 SortedList 和S o r t e d C h a i n。前者采用公式化描述的线性表，如
7、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)。进行插入时，必须确信该字典中没有相同关键字的元素 ,这要通过搜索来实现。然后进行插入，此时要为新元素腾出空间而移动表中 O (n)个元素，故插入操作的时间是O (n)。删除则首先要找到欲删除的元素，然后再进行删除。在进行搜索之后，还要移动O (n)个元素以填补所删除元素的空间，因此删
8、除的时间复杂性为 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
9、l i c :SortedChain() first =0; S o r t e d C h a i n ( ) ;bool IsEmpty() const return first =0;int Length() const;bool Search(const K& k , E& e) const;SortedChain& Delete(const K& k , E& e);第7章跳表和散列2 1 9下载SortedChain& Insert(const E& e);SortedChain& DistinctInsert(const E& e);p r i v a t e :SortedCh
10、ainNode *first; ;程序7-2 SortedChain类的成员函数s e a r c h和d e l e t etemplatebool SortedChain:Search(const K& k, E& e) const/ 搜索与k匹配的元素，结果放入e/ 如果没有匹配的元素，则返回f a l s eSortedChainNode *p = first;/ 搜索与k相匹配的元素for (; p & p-data link);/ 验证是否与k匹配if (p & p-data = k) / 与k相匹配e = p-data; return true;return false; / 不
11、存在相匹配的元素templateSortedChain& SortedChain :Delete(const K& k, E& e)/ 删除与k相匹配的元素/ 并将被删除的元素放入e/ 如果不存在匹配元素，则引发异常 B a d I n p u tSortedChainNode *p = first, *tp = 0; /跟踪p/ 搜索与k相匹配的元素for (; p & p-data link;/ 验证是否与k匹配if (p & p-data = k) / 找到一个相匹配的元素e = p-data; / 保存d a t a域/ 从链表中删除p所指向的元素if (tp) tp-link = p
12、-link;else first = p-link; / p是链首节点delete p;2 2 0第二部分数 据 结 构下载return *this;throw BadInput(); / 不存在相匹配的元素程序7-3 有序链表中的插入操作templateSortedChain& SortedChain:DistinctInsert(const E& e)/ 如果表中不存在关键值与e相同的元素，则插入e/ /否则引发异常B a d I n p u tSortedChainNode *p = first, *tp = 0; / 跟踪p/ 移动 tp 以便把 e 插入到 t p之后for (; p
13、 & p-data link);/ 检查关键值是否重复if (p & p-data = e) throw BadInput();/ 若没有出现重复关键值, 则产生一个关键值为e的新节点SortedChainNode *q = new SortedChainNode;q-data = e;/ 将新节点插入到t p之后q-link = p;if (tp) tp-link = q;else first = q;return *this;类S o r t e d C h a i n提供了两种插入操作，D i s t i n c t I n s e r t操作保证链中所有元素有不同的关键字，而I n s
14、 e r t允许有相同的关键字。虽然字典应用要求D i s t i n c t I n s e r t操作，但有序链表的其他应用可能会用到I n s e r t操作。析构函数、L e n g t h、Output 和 的重载的代码与类Chain (见程序3 - 8 )一样，在这里不再重复。可以通过删除 DistinctInsert 中搜索重复元素的那段代码 (即程序7 - 3中的第一条if 语句)来得到I n s e r t。从代码中可以看出，在有 n个节点的链表中，搜索、插入、删除的时间均为O (n)。在类S o r t e d C h a i n中，需定义有关数据类型 E的操作符 ，= =
15、，! =和，至于用户自定义的数据类型，可以采用 C + +的操作符重载机制来定义各种操作符。许多应用要求只根据E的关键字来实现这些操作。实现重载操作的一个简单方法是重载类型转换符以实现类型E到类型 K的转换( K的类型为 k e y )。例如，当 K是l o n g时，可以在 E的类定义中加入如下语句：operator long( ) const return key；可以扩充所有的S o r t e d L i s t和S o r t e d C h a i n以提供高效的顺序访问。在这两种情况下 B e g i n和第7章跳表和散列2 2 1下载N e x t返回一个元素所需要的时间均为(
16、 1 )。练习1. 采用公式化描述方法定义C + +类S o r t e d L i s t。要求提供与S o r t e d C h a i n中同样的成员函数。编写所有函数的代码，并用合适的数据测试代码。2. 扩充S o r t e d C h a i n类，使其包括顺序访问函数 B e g i n和N e x t。B e g i n用来返回字典中第一个元素，Next 用来返回字典中下一个元素（采用从小到大的排列顺序） 。在没有第一个或下一个元素的情况下，这两个函数均返回 0。两个函数的复杂度均应为( 1 )。测试代码的正确性。3. 修改类S o r t e d C h a i n，使用一条具有头节点和尾节点的链表。尾节点用来存放比其他元素值都大的元素。采用尾节点可以简化代码。7.3 跳表描述7.3.1 理想情况在一个使用有序链表描述的具有n 个元素的字典中进行搜索，至多需进行 n 次比较。如果在链中部节点加一个指针，则比较次数可以减少到 n/ 2 + 1。搜索时，首先将欲搜索元素与中间元素进行比较。如果欲搜索的元素较小，则仅需搜索链表的左半部分，否则，只要在链表右半部分进行比较即
