数据结构学习笔记（九）跳表、字典的跳表描述

一、跳表

        在使用有序链表描述的n个数对的字典中进行查找，至多需要n词比较。如果使用折半查找的思想，使用跳表来描述，可以大大加快搜索的速度。在下图10-1中，a表示的有序链表有7个数对，该链表增加一个头结点和一个尾节点。对该链表进行搜索最多需要7次关键字的比较。如果像b那样，在中间的节点中加入一个指针，那么比较时先和这个中间节点比较，在决定在前半部分还是后半部分继续搜索，因此搜索最多需要4次关键字的比较。        在使用有序链表描述的n个数对的字典中进行查找，至多需要n词比较。