第7章 跳表和散列 (Skip List and Hashing) 山东大学计算机科学与技术学院数据结构第7章跳表和散列
山东大学计算机科学与技术学院 数据结构 第7章 跳表和散列 1 第 7 章 跳表和散列 （Skip List and Hashing）
本章内容 7.1字典 dictionaries 7.2线性表描述 Linear list 7.3跳表描述 Skip list 7.4散列表描述 Hash tab|e 75应用 Applications 山东大学计算机科学与技术学院数据结构第7章跳表和散列 2
山东大学计算机科学与技术学院 数据结构 第7章 跳表和散列 2 本章内容 ◼ 7.1 字典 dictionaries ◼ 7.2 线性表描述 Linear List ◼ 7.3 跳表描述 Skip List ◼ 7.4 散列表描述 Hash table ◼ 7.5 应用 Applications
Bird's eye view Although a sorted array of n elements can be searched in O(logn time using the binary search method and o(n time for sorted chain, we still like to improve the search performance of a sorted chain by placing additional pointers in some or all the chain nodes. These additional points permit us to skip over several nodes of of the chain during a search. Chains augmented with additional forward points are called skip lists 山东大学计算机科学与技术学院数据结构第7章跳表和散列
山东大学计算机科学与技术学院 数据结构 第7章 跳表和散列 Bird’s eye view ◼ Although a sorted array of n elements can be searched in O(logn) time using the binary search method and O(n) time for sorted chain, we still like to improve the search performance of a sorted chain by placing additional pointers in some or all the chain nodes. These additional points permit us to skip over several nodes of the chain during a search. Chains augmented with additional forward points are called skip lists
7.1字典 字典( dictionary)是一些元素的集合。每个元素有 个称作key的域,不同元素的key各不相同 有关字典的操作有: 插入( Insert)具有给定关键字值的元素 ■在字典中寻找/搜索( Search)具有给定关键字值的元素 ■删除( Delete)具有给定关键字值的元素 例,班级的学生注册表,key=学号 有重复元素的字典 a dictionary with duplicates May be there are more than one elements have a same key 例,班级的学生考试报表,key=成绩 山东大学计算机科学与技术学院数据结构第7章跳表和散列
山东大学计算机科学与技术学院 数据结构 第7章 跳表和散列 4 7.1 字典 ◼ 字典（dictionary）是一些元素的集合。每个元素有 一个称作key 的域，不同元素的key 各不相同。 ◼ 有关字典的操作有： ◼ 插入（Insert）具有给定关键字值的元素。 ◼ 在字典中寻找/搜索（Search）具有给定关键字值的元素。 ◼ 删除（Delete）具有给定关键字值的元素 ◼ 例，班级的学生注册表，key =学号 ⚫有重复元素的字典 A dictionary with duplicates –May be there are more than one elements have a same key –例，班级的学生考试报表，key =成绩
AbstractDataType AbstractDataT ype dictionary Instances Collection of elements with distinct keys operations Create(O):创建一个空字典 Search(kx):搜索关键字为k的元素,结果放入x; 如果没找到,则返回alse,香则返回true Inseri(x):向字典中插入元素x Delete(kx):删除关键字为k的元素,并将其放入x 山东大学计算机科学与技术学院数据结构第7章跳表和散列
山东大学计算机科学与技术学院 数据结构 第7章 跳表和散列 5 AbstractDataType AbstractDataType Dictionary{ Instances Collection of elements with distinct keys operations Create(): 创建一个空字典 Search(k,x): 搜索关键字为k的元素，结果放入x； 如果没找到，则返回false，否则返回true Insert(x): 向字典中插入元素x Delete(k,x): 删除关键字为k的元素，并将其放入x }
72线性表描述 有序线性表:L=(e1re2,e3r…,en) ■关键字从左到右依次增大 在计算机存储器中的数据描述 ■公式化描述 链表描述 山东大学计算机科学与技术学院数据结构第7章跳表和散列
山东大学计算机科学与技术学院 数据结构 第7章 跳表和散列 6 7.2 线性表描述 ◼ 有序线性表: L = (e1 , e2 , e3 , …, en ), ◼ 关键字从左到右依次增大 ◼ 在计算机存储器中的数据描述 ◼ 公式化描述 ◼ 链表描述
链表描述的有序线性表(字典) 采用链表描述的有序线性表——有序链表 ■类 Sorted Chain 山东大学计算机科学与技术学院数据结构第7章跳表和散列
山东大学计算机科学与技术学院 数据结构 第7章 跳表和散列 7 链表描述的有序线性表（字典） ➢ 采用链表描述的有序线性表——有序链表 ◼ 类 SortedChain
类 Sorted chain first e template>//E:链表元素,K:关键字。 class Sorted ChainNode& Friend sorted chain private e data Sorted chainnode link 山东大学计算机科学与技术学院数据结构第7章跳表和散列
山东大学计算机科学与技术学院 数据结构 第7章 跳表和散列 8 类 SortedChain template >//E:链表元素，K:关键字。 class SortedChainNode{ Friend SortedChain private: E data; SortedChainNode *link; } ; first e1 e2 0 en … ei ei-1 … ei+1
Class sorted chain template class Sorted Chain( public Sorted(first=0; sorted Chain bool isemptyo const return first==0; int Lengthy const bool search(const K&k, e& e)const Sorted chain& delete(const K&k, e& e Sorted chain& Insert( const e&e)许关键字相同 Sorted chain& DistinctInsert( const ec&e)/不允许关 键字相同 private Sorted chainnode *first 山东大学计算机科学与技术学院数据结构第7章跳表和散列
山东大学计算机科学与技术学院 数据结构 第7章 跳表和散列 9 Class SortedChain template class SortedChain{ public : SortedChain() {first =0;} ~SortedChain(); bool IsEmpty() const {return first = =0;} int Length() const; bool Search(const K& k , E& e) const; SortedChain& Delete(const K& k , E& e); SortedChain& Insert(const E& e);//允许关键字相同 SortedChain& DistinctInsert(const E& e);//不允许关 键字相同 private: SortedChainNode *first; } ;
操作 search template bool Sorted chain: Search(const K&k, e& e)const /搜索与k匹配的元素,结果放入e,返回true ∥如果没有匹配的元素,则返回 false Sorted ChainNodee, K> * p=first for(;p&&p>datalink),∥搜索与k相匹配的元素 ∥验证是否与k匹配 if(p&&p->data==k)∥与k相匹配 te=p->data; return true; i return false;∥/不存在相匹配的元素 山东大学计算机科学与技术学院数据结构第7章跳表和散列
山东大学计算机科学与技术学院 数据结构 第7章 跳表和散列 10 操作 ‘search’ template bool SortedChain::Search(const K& k, E& e) const {// 搜索与k匹配的元素，结果放入e,返回true. //如果没有匹配的元素，则返回false SortedChainNode *p = first; for (; p && p->data link); // 搜索与k相匹配的元素 // 验证是否与k匹配 if (p && p->data = = k) // 与k相匹配 {e = p->data; return true;} return false; // 不存在相匹配的元素 }