第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 }