13

Size: px

Start display at page:

Download "13"

桧雷
5 years ago
Views:

1 孙猛年 11 月 23 日 1

2 字典及其抽象数据类型字典的线性表实现二分法与插值法 (interpolation) 检索集合的抽象数据类型及实现 2

3 数据的存储和访问是计算中最重要最基本的工作, 也是各种计算机应用和信息处理理的基础在许多情况下, 计算过程并不不知道数据的存储位置, 但需要使用数据, 此时首先需要找到数据存储的位置, 这一操作称为检索一些具体应用中数据的存储和检索 ( 查询 ) 的例例子 : 电子字典, 基本功能就是基于算法的数据检索图书馆编目目录和检索系统, 支持读者检索书籍资料料的有关信息规模巨大的有机物库, 需要基于结构或光谱等参数进行行检索我们要讨论的是基于关键码的数据存储和检索关键码指数据项的某种 ( 具有唯一性的 ) 特征, 可以是数据内容的组成部分, 也可以是专门为数据检索建立的标签支持这种操作的数据结构, 通常称为字典查找表或映射 3

4 字典就是实现存储和检索的结构需要存储和检索的信息和环境有许多具体情况, 因此要考虑各种不不同的字典实现技术字典的实现可以用到前面讨论过的许多想法和结构包括各种线性结构树性结构及其各种组合涉及到在这些结构上操作的许多算法组织方法很多, 下面讨论顺序散列列二叉树和其他树形结构等这里里的基本问题是空间利利用率和操作效率字典的最主要也是使用最频繁的操作是检索 (searching, 也称查找 ) 检索效率是字典实现中最重要的考虑因素由于规模不不同, 检索效率的重要性也可能不不同 4

5 字典可以分为两类 : 静态字典 : 建立后保持不不变, 只做检索, 实现只需考虑检索效率动态字典 : 内容经常动态变动的字典除检索外, 基本操作还包括插入和删除等, 实现时就必须考虑插入删除操作的效率动态字典的插入删除操作可能导致字典结构的变化要支持长期使用, 还需要考虑字典在动态变化中能否保持良好的结构, 能否保证良好的检索效率?( 字典的性能不不应该随着反复操作而逐渐恶化 ) 5

6 字典 : 一种特殊的集合 ; 每个元素都有两部分组成, 即关键码和属性 ( 也称为值 ): 可以依据关键码对字典元素进行行排序字典元素的插入删除和检索等操作一般以关键码为依据进行行包含关键码和属性的二元组称作关联关联 <k,v>: 关键码值 k 到属性值 v 的一个对应字典 : 从关键码值集合到值集合的二元关系 : D={<k,v> k K v V} 静态字典 : 一经建立就基本固定不不变动态字典 : 需要经常更更新 6

7 关于字典最主要的操作 : 检索 ( 也称查找 ) 给定一个值 key, 在字典中找出关键码等于 key 的元素静态字典选择存储需要考虑 : 检索效率 ; 空间的利利用效率动态字典选择存储需要考虑 : 存储效率检索效率元素的插入删除运算的效率 7

8 衡量量一个字典检索算法, 需要考虑平均检索长度 ASL (Average Search Length) ; 检索过程中对关键码的平均比较次数, 即 ASL(n)= n i=1 p i c i, 其中 n 是字典中元素的个数,p i 是查找第 i 个元素的概率,c i 是找第 i 个元素的比较次数检索失败的概率及各种失败情况所需花费的比较次数 ; 空间开销 ; 算法是否易易于理理解等等 8

9 假设用Dictionary 表示抽象数据类型字典, 用DicElement 表示字典元素类型, 用KeyType 来表示元素中关键码的类型, 用Position 表示字典中元素的位置 9

10 ADT Dictionary is operations Dictionary createemptydictionary(void) 创建一个空字典 int search(dictionary dic, KeyType key, Position p) 在字典 dic 中检索关键码为 key 的关联的位置 p int insert(dictionary dic, DicElement ele) 在字典 dic 中插入关联 ele int delete(dictionary dic, KeyType key) 在字典 dic 中删除关键码为 key 的关联 end ADT Dictionary 10

11 从最基本的存储需求看, 字典也就是关联的汇集前面讨论过的各种数据汇集结构都可用作字典的实现基础例例如线性表, 是元素的线性的顺序汇集如果以关联作为元素, 就可以看作是字典下面首先考虑这种实现作为字典实现, 最重要的问题是字典操作的实现由于字典可能有一定规模, 需要频繁执行行查询等操作, 操作的效率非常重要 11

12 typedef int KeyType; typedef int DataType; typedef struct { KeyType key; /* 字典元素的关键码字段 */ DataType value; /* 字典元素的属性字段 */ } DicElement; typedef struct { int MAXNUM ; /* 字典中元素的个数上界 */ int n; /* 为字典中实际元素的个数 */ DicElement *elem; /* 存放字典中的元素 */ } SeqDictionary; 12

13 int seqsearch(seqdictionary * pdic, KeyType key, int * position) { /* 在字典中顺序检索关键码为 key 的元素 */ int i; for(i=0; i<pdic->n; i++) /* 从头开始向后扫描 */ if(pdic->elem[i].key==key) { *position=i; return 1; } /* 检索成功 */ *position=pdic->n; return 0; /* 检索失败 */ } 13

14 插入的元素放在最后,O(1) 时间复杂性删除元素时需要先检索, 确定了了元素的位置后删除 ( 表中删除元素 ) 主要操作是检索 ( 删除依赖于检索 ), 分析其复杂性, 考虑比较次数 : 基于线性表的字典实现, 优点和缺点都很明显在字典的动态变化中, 各种操作的效率不不变 ( 因为都已经是效率很低的操作了了 ) 14

15 顺序检索的优点是算法简单且适应面广无论字典中元素是否有序均可使用缺点是平均检索长度较大, 特别是当 n 很大时, 检索效率较低一般情况下, 字典中各元素的检索概率不不相等则当 P 1 P 2 P n 时, 平均检索长度最小因此, 如果已知各元素的检索概率, 则应将字典中元素按检索概率由大到小排序, 以便便提高检索效率 15

16 另一种提高检索效率的方法是将字典元素按关键码递增 ( 或者递减 ) 的顺序排序, 这种按照关键码大小排序的顺序表称为有序顺序表对于有序顺序表, 可以还采用顺序检索的方法进行行查找下面介绍的另外一种检索方法, 称为二分法检索, 是专门为有序顺序表设计的 16

17 二分法检索又称折半检索, 是一种效率较高的检索方法, 通过按比例例缩小检索范围的方式, 快速逼近要检索的数据使用这种方法检索时, 要求字典的元素在顺序表中按关键码排序 ( 假设按升序排列列 ) 思想 : 首先将给定值 key 与顺序表中间位置上元素的关键码比较, 如果相等, 则检索成功 ; 否则, 若 key 小, 则在前半部分中继续进行行二分法检索, 否则在后半部分中继续进行行二分法检索 ; 直到检索成功或范围中已经没有数据, 则检索失败结束这样, 经过一次比较就缩小一半的查找区间, 如此进行行下去, 直到能够确定检索成功或检索失败为止 17

18 int binarysearch(seqdictionary * pdic, KeyType key, int *position) { int low, mid, high; low=0; high=pdic->n-1; while(low<=high) { } mid=(low+high)/2; /* 当前检索的中间位置 */ if(pdic->elem[mid].key==key) {*position=mid; return(1);} /* 检索成功 */ else if(pdic->elem[mid].key>key) high=mid-1; /* 检索左半区 */ } else low=mid+1; /* 检索右半区 */ *position=low; return 0 ; /* 检索失败 */ 18

19 二分法检索的具体示例例 : 以下面 11 个数的检索为例例 : 关键码 : 位置 : 采用二分法检索 : 找到位置 5 的数需比较 1 次, 找到位置 2 8 需比较 2 次, 找到位置需 3 次, 找到另外 4 个位置需比较 4 次检索过程可用二叉树表示树结点所标数字是数据的位置通过检索找到某结点的比较次数等于该结点的层数加 1 检索结点的过程沿着从根结点到需要检索的结点的路路径, 在每个位置做了了一次比较

20 二分法检索每经过一次比较就将检索范围缩小一半, 第 i 次比较可能比较的元素个数如下比较次数可能比较的元素个数 1 1 = = = 2 2 j 2 j-1 若字典元素个数 n 刚好为 j-1 =2 j -1 则最大检索长度为 j; 若 2 j -1 < n 2 j+1-1, 则最大检索长度为 j+1 dlog 2 (n + 1)e 所以, 二分法检索的最大检索长度为 : 20

21 设字典元素个数 n=2 j -1, 检索每个元素的概率相同, 则平均检索长度为 : ASL = 1 n jx jx i=1 m=i 2 m 1 = 1 jx n (2 j 2 i 1 ) i=1 = 1 jx n (j 2j 2 i 1 ) i=1 = 1 n (j 2j 2 j + 1) = n +1 n log 2 (n + 1) 1 21

22 包含检索成功和不不成功情况的判定树如下方框表示检索不不成功 ( 是扩充二叉树的外部结点 ), 例例如下图中标着的方框表示被检索关键码值在 13 和 19 之间检索到达方框就是失败 56 由此可见, 检索不不成功时, 最大比较次数 < >92 也是 dlog 2 (n + 1)e 这是基于检索中的判定操作形成的判定树的分析 22

23 二分法检索的优点是检索速度快 (O(log 2 (n))) 不不足 : 只能用于顺序存储的元素按关键码排序的字典 ; 为了了保持顺序表的有序性 : 插入和删除时需要移动元素 (O(n) 时间代价 ); 不不适合大的动态字典 23

24 24

25 int interpolationsearch(seqdictionary * pdic, KeyType key, int *position){ int low, mid, high; low=0; high=pdic->n-1; while(low<=high) { mid = low + (key-pdic->elem[low] / pdic->elem[high]-pdic->elem[low])* (high-low); /* 插值检索与分法检索的差别 */ } if(pdic->elem[mid].key==key) {*position=mid; return(1);} /* 检索成功 */ else if(pdic->elem[mid].key>key) high=mid-1; /* 检索左半区 */ } else low=mid+1; /* 检索右半区 */ *position=low; return 0 ; /* 检索失败 */ 25

26 pdic->elem key low high 26

27 也可以考虑用单链表或双链表实现字典, 有关情况 : 如果字典里里的数据项任意排列列 : 插入时可以简单插入在表头,O(1) 操作 ; 检索和删除需要顺序扫描检查,O(n) 操作 ; 如果数据项按关键码升序或者降序排列列, 插入需要检索位置,O(n) 操作 ; 检索和删除需要顺序扫描检查, 平均查半个表,O(n) 操作 ; 易易见 : 用链接表实现字典没有任何优势, 实际中很少采用具体的实现技术很简单, 不不需要再进一步讨论 27

28 采用线性表技术实现字典常常不不能满足实际需要实际中需要存储和检索的数据集的数据量量常常很大, 内容动态变化采用简单连续表或链接表, 顺序检索的效率太低, 不不能满足存储和检索大规模的数据集合的需要采用排序连续表和二分 / 插值检索, 检索的速度大大提高, 但仍有两大问题 : 1. 不不能很好支持数据的变化 ( 数据插入和删除 ); 2. 必须采用连续方式表示如果数据集很大 ( 例例如几百 M 或者几个 G 或更更大的数据集 ), 连续实现方式就很难接受了了要支持在大且变动的数据集合里里高效检索, 必须考虑其他组织结构 28

29 基本概念 : 集合是一些互不不相同元素的无序汇集集合中的元素也称为该集合的成员集合中的成员可以是一个原子 ( 不不可再分解 ); 也可以是一个结构, 甚至又是一个集合数据结构中讨论的集合, 一般有以下限制 : 1. 限制为有穷集 ; 2. 所有元素属同一类型 ; 3. 元素之间存在一个小于关系 ( 有序集 ) 29

30 列列举法 : 定义一个有穷集, 可以将成员放在一对花括号中, 成员之间用逗号隔开 {1, 2, 3, 4, 5} 谓词描述法 : I = {x Z(x) ^ x 0} 集合的大小 : 集合中所包含的元素的个数空集子集超集 x 2 A, x /2 A 30

31 集合间的高层运算 : 元素的基本操作 : A [ B = {x x 2 A _ x 2 B} A \ B = {x x 2 A ^ x 2 B} A B = {x x 2 A ^ x/2 B} A B, 8x.(x 2 A ) x 2 B) A B, B A A = B, A B ^ B A 测试一个元素是否存在于集合中 ; 增加一个元素 ; 删除一个元素等 31

32 已知集合 A 和 B, 求它们的并集 : 只要以集合 A( 或 B) 为基础, 把集合 B( 或 A) 的元素逐个插入如果要求两个集合的交集 : 只要从 A( 或 B) 出发, 检查各元素是否在 B( 或 A) 中出现, 选出那些也在另一个集合里里出现的元素, 插入 ( 初态为空集的 ) 结果集合求 A 与 B 的差集 A-B 时 : 只要以 A 为基础, 对每个 B 中的元素做删除运算 32

33 ADT Set is operations Set createemptyset ( void ) int member(set A,DataType x) int insert(set A,DataType x) int delete(set A,DataType x) int union(set A,Set B,Set C) int intersection (Set A,Set B,Set C) int difference(set A,Set B,Set C) int subset(set A,Set B) end ADT Set 33

34 任何字典实现方法都可以用于实现集合 : 只需把集合的元素直接存储在保存字典项 ( 关联 ) 的位置集合的最基本操作是元素与集合的关系, 对应于字典查询 ; 集合数据结构需要的创建空集检查加入删除等都有字典操作与之对应集合实现需要考虑常用集合运算的实现 : 求并集和交集, 求相对于某个集合的补集 ( 集合差 ) 都是从两个已有集合得到另一个集合集合的实现需要考虑这些操作的效率 34

35 一个元素是否属于一个集合, 是一种二值判断基于这一认识, 人们提出了了一种专门的集合实现技术 : 位向量量表示位向量量是一种每个元素都是二进制位 ( 即 0/1 值 ) 的数组当表示的集合存在某个不不太大的公共超集时, 采用位向量量的方式来表示这种集合往往十分有效如果所需要的集合对象有一个公共超集 U, 也就是说, 需要实现的集合都是 U 的子集, 就可以采用位向量量技术实现这些集合, 方法是 : 假定 U 包含 n 个元素, 给每个元素一个编号作为该元素的下标对任何要考虑的集合 S( 注意 S U), 用一个 n 位的二进制序列列 ( 位向量量 )v S 表示 S 对元素 e U, 如果 e S, 令 v S 里里对应于 e( 的编号, 下标 ) 的那个位取值 1, 否则令该位取值 0 35

36 array size (a) 位向量量表示存储结构示意图 array size (b) 集合 {1,3,5,7,9} 的实际存储状态 36

37 假设需要表示的集合的公共超集中, 共有 n 个不不同的元素, 为叙述的方便便, 不不妨假设这些元素就是整数 0,1, 2,,n-1 每个集合可以采用一个有 n 位的位向量量来表示若整数 i 是这个集合的一个元素, 则位向量量中对应的位为 1( 真 ), 否则为 0( 假 ) 用位向量量表示集合时, 所占空间的大小与公共超集的大小 n 成正比, 而与要表示的集合的大小无关在位向量量表示里里只有对应元素是否成员的标记, 没有具体给成员的详细信息 37

38 位向量量集合的元素操作加入删除元素, 就是把位向量量里里相应的二进制位置 1 或置 0 判断元素关系, 对应于检查相应的二进制位是否为 1 位向量量集合的集合运算都可以通过逐位操作实现 : S 和 T 的第 i 位都是 1 时 S T 第 i 位取值 1, 否则取值 0 S 和 T 的第 i 位都是 0 时 S T 第 i 位取值 0, 否则取值 1 S 第 i 位是 1 而 T 第 i 位是 0 时 S-T 第 i 位取值 1, 否则取值 0 例例 : 假设 U 是 {a, b, c, d, e, f, g, h, i, j}, 其子集 S = {a,b,d}: T = {a,e,i}: S T = {a}: S T = {a,b,d,e,i}: S-T = {b,d}:

39 C 语言中无法直接定义位数组, 只能定义字符数组一个字符占用8 位二进制编码, 它实际上包含了了 8 个二进制位要定义长度为 n 的位向量量, 需要用长度为 dn/8e的字符数组 39

40 typedef struct { int size; /* 字符数组的长度 */ char * array; /* 位向量量空间每一数组元素保存 8 位 */ } BitSet; 40

41 假设 x 和 y 都是 8 位的字符, 其值分别是 : X= Y= 各种字位运算, 得到的结果如下 : ~x ( 求补 ) x & y x ^ y ( 按位加 / 异或 ) x y x << y >>

42 BitSet * createemptyset (int n) { /* 创建 n 位的位向量量 */ int i; BitSet * s = (BitSet *)malloc(sizeof(bitset)); if (s!=null) { } } printf( "Out of space! \n" ) ; /* 存储分配失败 */ return NULL; 42

43 BitSet * createemptyset (int n) { /* 创建 n 位的位向量量 */ int i; BitSet * s = (BitSet *)malloc(sizeof(bitset)); if (s!=null) { s->size = (n + 7) / 8; s->array = (char *)malloc(s->size * sizeof(char)); if (s->array!= NULL){ for (i = 0; i < s->size; i++) s->array[i] = '\0'; return s; } } printf( "Out of space! \n" ) ; /* 存储分配失败 */ return NULL; } 43

44 int member(bitset * s, int index) { } /* 检查位向量中下标为 index 的位置是否为 1*/ if (index >= 0 && index >> 3 < s->size&& (s->array[index >> 3] & (1 << (index & 07)))) return 1; return 0; 44

45 int member(bitset * s, int index) { } /* 检查位向量中下标为 index 的位置是否为 1*/ if (index >= 0 && index >> 3 < s->size&& (s->array[index >> 3] & (1 << (index & 07)))) return 1; return 0; array size 集合 {1,3,5,7,9} 的实际存储状态 45

46 int insert (BitSet * s, int index){ /* 将位向量中下标为 index 的位置为 1*/ if (index >= 0 && index>>3 < s->size) { s->array[index >> 3] = (1 << (index & 07)); return 1; } } return 0; array size 集合 {1,3,5,7,9} 的实际存储状态 46

47 int insert (BitSet * s, int index){ /* 将位向量中下标为 index 的位置为 1*/ if (index >= 0 && index>>3 < s->size) { s->array[index >> 3] = (1 << (index & 07)); return 1; } } return 0; array size 集合 {1,3,5,7,9} 的实际存储状态 47

48 int delete(bitset * s, int index) { /* 将位向量中下标为 index 的位置为 0*/ if (index >= 0 && index >> 3 < s->size) { s->array[index >> 3] &= ~(1 << (index & 07)); return 1; } return 0; } array size 集合 {1,3,5,7,9} 的实际存储状态 48

49 int union (BitSet * s0, BitSet * s1, BitSet * s2) { /* 当三个位向量长度相等时返回 1, 置 s2 为 s0 与 s1 的并 ; 否则 } 返回 0 */ int i; if (s0->size!= s1->size s2->size!= s1->size) return 0; for (i = 0; i < s1->size; i++) s2->array[i]=s0->array[i] s1->array[i]; return 1; 49

50 int intersection (BitSet * s0, BitSet * s1, BitSet * s2) { /* 当三个位向量长度相等时返回 1, 置 s2 为 s0 与 s1 的交 ; 否则 } 返回 0 */ int i; if (s0->size!= s1->size s2->size!= s1->size) return 0; for (i = 0; i < s1->size; i++) s2->array[i]=s0->array[i] & s1->array[i]; return 1; 50

51 int difference (BitSet * s0, BitSet * s1, BitSet * s2) { /* 当三个位向量长度相等时返回 1, 置 s2 为 s0 与 s1 的差 ; 否则 } 返回 0 */ int i; if (s0->size!= s1->size s2->size!= s1->size) return 0; for (i = 0; i < s1->size; i++) s2->array[i]=s0->array[i] & ~s1->array[i]; return 1; 51

52 链接表示方式下, 在链表中存放的是集合中元素的实际值, 而不不是元素是否属于集合的标记链表中的每个结点表示集合中的一个元素, 具体方式与单链表的结点类似不不同之处在于 : 线性表的单链表中,link 字段表示线性表元素之间的逻辑后继关系, 而在这里里仅仅是把属于同一集合的所有元素链接成一个整体因为我们讨论的是有序集, 如果将集合中的所有元素按 < 关系排序构造有序链表, 给集合的某些运算会带来方便便 52

53 struct Node; typedef struct Node *PNode; struct Node { DataType info; PNode link; }; typedef struct Node *LinkSet; 53

54 集合 S={0, 1, 2,, n-1} 采用带表头结点的有序链表表示时, 如图所示 : 0 1 n-1 info link 54

55 int intersectionlink (LinkSet s0,linkset s1,linkset s2) { PNode x; if(s0= =NULL s1= =NULL s2= =NULL){ printf("no head node error");return 0;} s2->link=null; /* 将 s2 置成空集合 */ s0=s0->link; s1=s1->link; while(s0!=null&&s1!=null) if(s0->info>s1->info) s1=s1->link; elseif(s0->info<s1->info) s0=s0->link; elseif(s0->info= =s1->info) { /* 找到相同元素 */ x=(pnode)malloc(sizeof(struct Node)); /* 分配结点空间 */ if(x= =NULL) {printf("out of space");return 0;} x->info=s0->info; x->link=null; s2->link=x; /* 在 s2 中插 */ s0=s0->link; s1=s1->link; s2=s2->link; /* 指针后推 */ } return 1; } 55

56 int assignlink (LinkSet s0,linkset s1) { PNode x; if(s0==null s1==null){printf("no head node error");return 0;} s0->link=null; /* 将 s0 置成空集合 */ s1=s1->link; while(s1!=null) { x=(pnode)malloc(sizeof(struct Node)); /* 分配结点空间 */ if(x= =NULL) {printf("out of space");return 0;} x->info=s1->info; x->link=null; s0->link=x; /* 在 s0 中插入 */ s1=s1->link; s0=s0->link; /* 指针后推 */ } return 1; } 注意这一运算不不能简单地将 s0 的表头结点置成 s1 的表头结点 56

57 int insertlink (LinkSet s0,datatype x) { PNode temp; if(s0= =NULL){printf("no head node error");return 0;} temp=(pnode)malloc(sizeof(struct Node)); /* 分配结点空间 */ if(temp= =NULL){printf("out of space");return 0;} while(s0->link!=null) { if(s0->link->info= =x) {printf("data already exist");return 1;} else if(s0->link->info<x) s0=s0->link; else if(s0->link->info>x) { /* 找到插位置 */ temp->info=x; temp->link=s0->link; s0->link=temp; /* 插 */ return 1; } } if(s0->link= =NULL) { /* 插到最后 */ temp->info=x; temp->link=s0->link; s0->link=temp; return 1; } } 57

58 集合和字典的概念, 抽象数据类型, 存储结构和操作的实现从逻辑结构上看, 集合和字典属于两种最简单的数据结构, 它们的元素之间没有任何确定的依赖关系然而正是这个原因使得在具体表示集合和字典时, 可以选择多种不不同的存储结构集合的实现方法很多, 当讨论的集合都是某个更更大的公共超集的子集, 并且这个公共超集不不很大时, 可以采用位向量量的方式来表示字典的每个元素是一个二元组 : 分别称为关键码和属性, 这种二元组称作关联字典就是以关联为元素的集合字典顺序表示和顺序检索 ; 有序顺序表表示和二分法检索 58

2

孙猛 http://www.math.pku.edu.cn/teachers/sunm 2017 年 9 月 18 日课程主页 : http://www.math.pku.edu.cn/teachers/sunm/ds2017/ 作业通过 course.pku.edu.cn 提交 2 线性表的概念和抽象数据类型顺序表示链接表示 3 4 线性表 ( 简称为表 ) 是零个或多个元素的有穷序列列