数据结构

Size: px

Start display at page:

Download "数据结构"

结任
6 years ago
Views:

1 9 查找董洪伟

2 主要内容查找的概念线性查找表线性查找折半查找索引查找 ( 分块查找 ) 二叉查找树 ( 平衡二叉树 ) 二叉查找树平衡二叉树哈希查找 ( 散列查找 )

3 查找的概念查找 : 在数据集合中寻找满足某种条件的数据元素关键字相当于排序中的排序码数据元素中某个数据项的值可以标识一个数据元素关键字可以相同, 即不一定唯一标识这个元素

4 查找的概念平均查找长度 Average Search Length 查找就是不断将数据元素的关键字与待查找关键字进行比较, 查找算法在查找成功时平均比较的次数称作平均查找长度 ASL n i 1 P C i i Pi: 查找第 i 个数据元素的概率 Ci: 查找该元素的过程中比较的次数

5 查找的概念线性查找表数据集合是一个线性表二叉查找树数据集合是一个二叉树哈希 ( 散列 ) 表根据哈希函数 ( 关键字映射到存储地址 ) 存储和查找有点类似根据下标到地址

6 线性查找线性查找又称为顺序查找主要用于在线性的数据结构中进行查找基本思想设若表中有 N 个对象, 则从表的一端开始, 顺序用各数据的关键字与给定值 X 进行比较, 直到找到与其值相等的元素, 则搜索成功, 给出该对象在表中的位置若整个表都已检测完仍未找到关键字与 X 相等的元素, 则搜索失败, 给出失败信息

7 线性查找 i 欲查找 57

8 线性查找 i 欲查找 57

9 线性查找 i 欲查找 57

10 线性查找 i 欲查找 57

11 线性查找 i 欲查找 57 找到, 位置在第 4 个单元

12 线性查找 i 欲查找 27

13 线性查找 i 欲查找 27

14 线性查找 i 欲查找 27

15 线性查找 i 欲查找 27

16 线性查找 i 欲查找 27

17 线性查找 i 欲查找 27

18 线性查找 i 欲查找 27 找不到

19 线性查找时间复杂度最好情况 :O(1) 第一个就是欲查找值最差情况 :O(n) 欲查找值在最后一个单元或搜索了所有的数据才得知找不到平均情况 :O(n) 等概率时 : ASL n 1 n 1 i n 2 i 1

20 折半查找折半查找基于有序的顺序表基本思想 middle = n/2 比较 key 和 Data[middle] 若 key < Data[middle]: 欲查找值在前半段若 key > Data[middle]: 欲查找值在后半段若 key = Data[middle]: 查找成功若搜索区间已缩小到一个数据仍未找到 : 找不到

21 折半查找 low mid high key = 25 low = 0 high = 11 mid = (low + high)/2 = 5

22 折半查找 low mid high key = 25 key < Data[mid] 搜索范围应缩小为 low ~ mid-1 即 high = mid - 1

23 折半查找 low mid high key = 25 low = 0 high = 4 mid = (low + high)/2 = 2

24 折半查找 low mid high key = 25 key > Data[mid] 搜索范围应缩小为 mid+1 ~ high 即 low = mid + 1

25 折半查找 mid low high key = 25 low = 3 high = 4 mid = (low + high)/2 = 3

26 折半查找 mid low high key = 25 key = Data[middle] 找到位置在第 3 个单元

27 折半查找 : 算法 int Search_Bin(SqList ST, KeyType key) { low = 1; high = ST.length; while(low <= high) { mid = (low + high)/2; } if(eq(key, ST.elem[mid].key)) // 找到 return mid; else if(lt(key, ST.elem[mid].key)) // 前半段 high = mid - 1; else low = mid + 1; } return 0; typedef struct{ ElemType data; int length,listsize; } SqList; // 后半段 // 如果 left>right, 说明找不到

28 折半查找性能分析比较次数 = 折半的次数 n 个元素, 最多 log 2 n +1 次折半判定树 :

29 折半查找平均查找长度第 h 层的元素有 2 h-1 个, 找到它需要比较 h 次等概率条件下 ASL j h 1 j n j 1 n 1 log 2 ( n 1) 1 n log ( n 1) 1 2 2

30 折半查找总结顺序查找和折半查找都针对静态查找表折半查找效率较高但是折半查找要求数据有序并且存储结构必须是顺序存储 ( 链表怎么折半?)

31 分块查找 ( 索引顺序查找 ) 索引顺序表 : 顺序表 + 索引表 - 顺序表分块有序 - 索引项 : 子表最大关键字子表首指针索引表按照关键字有序最大关键字起始地址索引表

32 分块查找 ( 索引顺序查找 ) 分块查找 : 1) 先查找索引表, 确定数据元素 ( 记录 ) 所在的块 ( 子表 ) 2) 在块 ( 子表 ) 中顺序查找平均查找长度 : ASL bs =ASL b +ASL w 假设长度为 n 顺序表被均匀地分成 b 块, 每块有 s 个记录, 则 : ASLbs= (b+1)/2 + (s+1)/2 =(n/s+s)/2+1

33 二叉查找树二叉查找树又称二叉排序树是一棵二叉树, 不过左子树节点的值 < 根节点的值 < 右子树节点的值

34 二叉查找树二叉查找树的查找从根节点开始查找比较欲查找值和当前节点的值若当前节点为空, 则未找到若相等则查找成功若欲查找值更小, 则向左子树继续查找若欲查找值更大, 则向右子树继续查找

35 二叉查找树 // 二叉查找树的查找算法 BiTNode* SearchBST(BiTNode* T, ElemType e){ if (!T) return 0; // 递归出口 typedef struct binode{ ElemType data; struct binode *lchild,*rchild; } BiTNode; } if (T->data == e) return T; // 处理根 if (e < T->data) // 左子树 return SearchBST(T->lchild, e); else // 右子树 return SearchBST(T->rchild, e);

36 二叉查找树结点的插入如果是空树, 新结点作为树根如果等于当前结点, 则返回如果小于当前结点, 则在其左子树上插入如果大于当前结点, 则在其右子树上插入

37 二叉查找树的插入 bool InsertBST(BiTNode* &T, ElemType e){ if(t==0) { T = (BiTNode *)malloc(sizeof(bitnode)); if(t){ T->data = e; T->lchild = 0; T->rchild = 0; } return true; } } if (T->data == e) return false; else if (e<t->data) InsertBST(T->lchild, e); else if (e>t->data) // 右子树 InsertBST(T->rchild, e); return true; // 左子树

38 bool InsertBST(BiTNode* &T, ElemType e){ if(t==0) { T = (BiTNode *)malloc(sizeof(bitnode)); if(t){ T->data = e; T->lchild = 0; T->rchild = 0; } return true; } } //if (T->data == e) return false; if (e<t->data) // 左子树 InsertBST(T->lchild, e); else if (e>t->data) // 右子树 InsertBST(T->rchild, e); return true; T void main(){ } BiTNode* root = 0; ElemType e; e = 30;InsertBST(root, e); e = 20;InsertBST(root, e); e = 38;InsertBST(root, e); e = 22;InsertBST(root, e); e = 19;InsertBST(root, e); root 0

39 bool InsertBST(BiTNode* &T, ElemType e){ if(t==0) { T = (BiTNode *)malloc(sizeof(bitnode)); if(t){ T->data = e; T->lchild = 0; T->rchild = 0; } return true; } } //if (T->data == e) return false; if (e<t->data) // 左子树 InsertBST(T->lchild, e); else if (e>t->data) // 右子树 InsertBST(T->rchild, e); return true; T void main(){ BiTNode* root = 0; ElemType e; e = 30;InsertBST(root, e); e = 20;InsertBST(root, e); e = 38;InsertBST(root, e); e = 22;InsertBST(root, e); e = 19;InsertBST(root, e); } root

40 bool InsertBST(BiTNode* &T, ElemType e){ if(t==0) { T = (BiTNode *)malloc(sizeof(bitnode)); if(t){ T->data = e; T->lchild = 0; T->rchild = 0; } return false; } } //if (T->data == e) return false; if (e<t->data) // 左子树 InsertBST(T->lchild, e); else if (e>t->data) // 右子树 InsertBST(T->rchild, e); return true; T void main(){ BiTNode* root = 0; ElemType e; e = 30;InsertBST(root, e); e = 20;InsertBST(root, e); e = 38;InsertBST(root, e); e = 22;InsertBST(root, e); e = 19;InsertBST(root, e); } root

41 bool InsertBST(BiTNode* &T, ElemType e){ if(t==0) { T = (BiTNode *)malloc(sizeof(bitnode)); if(t){ T->data = e; T->lchild = 0; T->rchild = 0; } return true; } } //if (T->data == e) return false; if (e<t->data) // 左子树 InsertBST(T->lchild, e); else if (e>t->data) // 右子树 InsertBST(T->rchild, e); return true; T void main(){ BiTNode* root = 0; ElemType e; e = 30;InsertBST(root, e); e = 20;InsertBST(root, e); e = 38;InsertBST(root, e); e = 22;InsertBST(root, e); e = 19;InsertBST(root, e); } root

42 bool InsertBST(BiTNode* &T, ElemType e){ if(t==0) { T = (BiTNode *)malloc(sizeof(bitnode)); if(t){ T->data = e; T->lchild = 0; T->rchild = 0; } return true; } } //if (T->data == e) return false; if (e<t->data) // 左子树 InsertBST(T->lchild, e); else if (e>t->data) // 右子树 InsertBST(T->rchild, e); return true; T void main(){ BiTNode* root = 0; ElemType e; e = 30;InsertBST(root, e); e = 20;InsertBST(root, e); e = 38;InsertBST(root, e); e = 22;InsertBST(root, e); e = 19;InsertBST(root, e); } root

43 二叉查找树的结点的删除基本思想找到待删除结点, pointer 找到待删除结点的父结点, parent 该结点的子孙怎么办? 即谁来继承它? 该结点的父结点指针怎么办?

44 二叉查找树的结点的删除待删除的结点是叶结点若 pointer 是 parent 的左孩子 parent->lchild = NULL 否则 :parent->rchild = NULL 最后释放 pointer 的空间 40 parent pointer

45 二叉查找树的结点的删除待删除的结点只有 1 个孩子 parent pointer child 唯一的继承人 pointer 的孩子 child 顶替 pointer 的位置

46 二叉查找树的结点的删除待删除的结点有 2 个孩子 parent 40 pointer 继承人

47 二叉查找树的结点的删除继承人左子树中的最右的结点因为它是左子树中最大的能够保证比左子树中其余的结点都大 ; 比右子树中的所有结点都小

48 二叉查找树的结点的删除继承人右子树中的最左的结点因为它是右子树中最小的能够保证比左子树中的所有结点都大 ; 比右子树中的其它结点都小

49 40 pointer 继承人继承人顶替被删除结点问题是 : 谁又来顶替继承人的位置呢? 继承人最多只有一个孩子, 否则它就不会是最左 / 最右的了

50 二叉查找树的结点的删除新的查找算法 : // 找到待删除的结点的双亲结点 BiTNode* SearchBST( BiTNode* &T, ElemType e, BiTNode* &parent){ if (!T) return 0; // 递归出口 } if (T->data == e) return T; parent = T; // 处理根 if (e < T->data) // 左子树 return SearchBST(T->lchild, e,parent); else // 右子树 return SearchBST(T->rchild, e,parent);

51 二叉查找树的结点的删除 bool DeleteBST( BiTNode* &root, ElemType e){ if(!root) return false; } BiTNode *T = root, *parent = 0; BiTNode* p = SearchBST(T,e,parent) ; if(p) Delete( p, parent); return true;

52 void Delete( BiTNode* &p, BiTNode* parent) { BiTNode* q ; if(!p) return; if (!p->lchild &&!p->rchild ) { if(parent){ if( parent->lchild==p) parent->lchild=0; } else parent->rchild=0; } free(p);p = 0; return; } else if (!p->rchild) { /* */ } else if (!p->lchild){ /* */ } else { /*..*/ } return true; parent p A O

53 void Delete( BiTNode* &p, BiTNode* parent) { BiTNode* q ; if(!p) return; if (!p->lchild &&!p->rchild ) {/* */} else if (!p->rchild) { q = p->lchild; if(q){ p->data = q->data; p->lchild = q->lchild; p p->rchild = q->rchild; free(q); A } q } else if (!p->lchild){ /* */ B } else { /*..*/ } return; C D }

54 void Delete( BiTNode* &p, BiTNode* parent) { BiTNode* q ; if(!p) return; if (!p->lchild &&!p->rchild ) {/* */} else if (!p->rchild) { q = p->lchild; if(q){ p->data = q->data; p->lchild = q->lchild; p p->rchild = q->rchild; free(q); B } q } else if (!p->lchild){ B /* */ C } else { /*..*/ } return; } D

55 void Delete( BiTNode* &p, BiTNode* parent) { BiTNode* q ; if(!p) return; if (!p->lchild &&!p->rchild ) {/* */} else if (!p->rchild) { q = p->lchild; if(q){ p->data = q->data; p->lchild = q->lchild; p p->rchild = q->rchild; free(q); B } q } else if (!p->lchild){ /* */ C } else { /*..*/ } return; } D

56 void Delete( BiTNode* &p, BiTNode* parent) { BiTNode* q ; if(!p) return; if (!p->lchild &&!p->rchild ) {/* */} else if (!p->rchild) { /* */ } else if (!p->lchild){/* */ } else { q = p; s = p->lchild; while (s->rchild) { q = s; s = s->rchild; } p->data = s->data; if (q!= p) q->rchild=s->lchild; else q->lchild=s->lchild; free(s); } return; q s C q p B q E AF D s 56 G F s

57 二叉查找树的结点的删除 q = p; s = p->lchild; while (s->rchild) { q = s; s = s->rchild } p->data = s->data; q s C p q B q E AF s D G F s

58 二叉查找树的结点的删除 q = p; s = p->lchild; while (s->rchild) { q = s; s = s->rchild } p->data = s->data; s q p B AB G

59 二叉查找树的结点的删除 if (q!= p) q->rchild = s->lchild; else q->lchild = s->lchild; free(s); C p B q F D G s E F H

60 二叉查找树的结点的删除 if (q!= p) q->rchild = s->lchild; else q->lchild = s->lchild; free(s); s C q p B AB G

61 二叉查找查找算法的效率查找的次数 = 树的高度因此复杂度 =O(h), 问题是 h=?

62 h = log 2 n +1 ASL log 2 n 1 h = n ASL n 2 1 所以二叉搜索树需要平衡使得查找复杂度可以达到 O(log 2 n)

63 平衡二叉树平衡二叉树也叫 AVL 树 Adelson-Velskii 和 Landis 发明或者是空树或者 : 左右子树都是 AVL 树且左右子树的深度之差不超过 1

64 平衡二叉树平衡因子 = 左子树的深度右子树的深度 AVL 树上任何结点的平衡因子都 <=

65 平衡二叉树平衡二叉树的构造初始为空树不断插入结点如果导致了不平衡, 调整之

66 调整插入插入

68 局部影响全局不平衡是从局部开始的调整也就只需要从局部着手

69 平衡二叉树分析插入一个结点, 树根的平衡因子最多 ±1, 所以只需要消除这一层的不平衡即可设失去平衡的最低的子树根为 A, 从局部着手, 只需要对以 A 为子树根的子树进行调整 A

70 平衡二叉树分情况讨论以 A 为子树根的子树就这 4 种情况 : (1)LL 型 12 A 01 B h-1 h-1

71 平衡二叉树 (2)RR 型 h A -1 0 B h-1

72 平衡二叉树 (3)LR 型 21 A h B 01 C h-1 h-2

73 平衡二叉树 (4)RL 型 -2-1 A h-1 01 C 01 B h-1 h-2

74 平衡二叉树各个击破 h-1 (1)LL 型 B L 1 B B R 2 A A R h-1 右旋 0 B 0 A B L B R AR

75 平衡二叉树 (2)RR 型 2 A 1 B 左旋 0 A 0 B h-1 A L B R B L B R h-1 A L B L

76 平衡二叉树 h-1 (3)LR 型 B L -1 B 1 C 2 A A R 先左旋 h-1 0 B 0 C C R -1 A A R C L C R h-2 C L B L

77 平衡二叉树 (3)LR 型 0 B 0 C C R -1 A A R 后右旋 0 B 0 C -1 A C L B L C L C R A R B L

78 平衡二叉树 (3)LR 型 h-1 B L -1 B 1 C 2 A A R h-1 0 B 0 C -1 A C L C R h-2 B L C L C R A R

79 平衡二叉树 h-1 (4)RL 型 -2 A 1 B 先右旋 A L 1-1 C C B B h-1 L R A L 0 A 0 C h-2 C L C R C R B R

80 平衡二叉树 A L (4)RL 型 0 A 0 C -1 B 后左旋 0 A 0 C -1 B C L C L C R C R A L B R B R

81 平衡二叉树 (4)RL 型 h-1-2 A 1 B A L C A B B h-1 R 0 C h-2 C L C R A L C L C R B R

82 哈希查找查找算法的效率主要取决于比较的次数因此我们希望尽量减少比较的次数哈希查找 (Hash) 一种可以最少只比较一次就找到目标的查找方法又称为散列查找杂凑查找

83 哈希查找例某大学学生的学号有 10 位, 比如 : 院系编号班级编号序号一共有 0~ ,10 亿个学号而实际上在校生只有所以学生花名册有栏就够了

84 哈希查找设定一个 hash 函数 hash(x) = x % 这样 hash 函数值的范围是 0~17999 并且每个关键字映射为唯一的一个函数值 hash()

85 哈希查找关键字 Hash 函数 Hash 表 hash(x)= x%18000 学号姓名张三李四 17999

86 哈希查找 Hash 函数把关键字映射为存储位置的函数 Hash 表按照此方法构造出来的表或结构 Hash 查找使用 Hash 方法进行查找不必进行多次关键字的比较, 搜索速度比较快, 可以直接到达或接近具有此关键字的表项的实际存放地址

87 哈希查找冲突 (Collision) 散列函数是一个压缩映象函数关键字集合比 Hash 表地址集合大得多因此有可能经过 Hash 函数的计算, 把不同的关键字映射到同一个 Hash 地址上, 这些关键字互为同义词 hash(x) = x%10 1

88 哈希查找 Hash 查找的主要问题设计 Hash 函数对于给定的一个关键字集合选择一个计算简单且地址分布比较均匀的 Hash 函数, 避免或尽量减少冲突研究解决冲突的方案

89 哈希查找 Hash 函数 Hash 函数的设计要求简单, 能很快计算出函数值定义域 >= 全部关键字集合值域 <= 所有的表地址集合比如学号的范围是 0~ Hash 表项的编号是 0~17999 所以 Hash 函数的定义域应该为 [0, ], 值域为 [0,17999]

90 哈希查找 Hash 函数 Hash 函数计算出来的地址应能均匀分布在整个地址空间中若 key 是从关键字集合中随机抽取的一个关键字,Hash 函数应能以同等概率取到值域中的每一个值反之, 如果关键字总是更容易映射到某个或某些地址上, 称作堆积

91 哈希查找常用的 Hash 函数直接定址法 Hash 函数取关键字的某个线性函数 Hash( key ) = a * key + b 一一映射, 不会产生冲突但是, 它要求 Hash 地址空间的大小与关键字集合的大小相同

92 哈希查找 Hash 函数余数法设 Hash 表中允许地址数为 m hash( key ) = key % p 对 p 的要求 p <= m, 尽量接近 m 最好取质数最好不要接近 2 的幂

93 哈希查找 Hash 函数比如 : 有一关键字 key = Hash 表大小 m = 25 取质数 p = 23 Hash 函数 :hash(key) = key % p 则 Hash 地址为 : Hash( ) = % 23 = 12

94 哈希查找 Hash 函数数值抽取法 ( 数字分析法 ) 将关键字的某几位数字取出作为地址比如关键字为 6 位数,Hash 表地址为 3 位数可以取出关键字的第位, 组成 Hash 地址 >138

95 哈希查找 Hash 函数数值抽取法仅适用于事先明确知道表中关键字每一位数值的分布情况, 它完全依赖于关键字集合如果换一个关键字集合, 选择哪几位要重新决定比如如果关键字是电话号码学号, 则前几位就不太适合, 因为规律性太强

96 哈希查找 Hash 函数平方取中法将关键字的前几位取出, 做平方再取出平方结果的中间几位作为地址比如 : => = => 056 此方法在词典处理中使用十分广泛

97 哈希查找 Hash 函数折叠法将关键字拆成位数相等的多段, 将这几段叠加起来, 相加结果作为 Hash 地址移位折叠法 : 各段最后一位对齐相加比如关键字 : Hash 地址要求 3 位数 => 380

98 哈希查找 Hash 函数边界折叠法 : 各部分沿各部分的分界来回折叠, 然后对齐相加, 将相加的结果当做 Hash 地址比如 : 关键字 = => 587

99 哈希查找 Hash 函数旋转法将关键字中的数字旋转位置比如 : 关键字 = 把个位数移到最左 : 此法通常和其它方法结合使用

100 哈希查找 Hash 函数伪随机数法利用伪随机数算法生成 Hash 地址 Hash(key) = random(key)

101 哈希查找 Hash 函数总结应根据实际情况选择 : 效率要求关键字长度 Hash 表长度关键字分布情况等有人曾用统计分析方法对它们进行了模拟分析, 结论是中间平方法最随机有时候可以多种方法结合使用, 比如 Hash(key) = random(key)%13

102 哈希查找冲突的解决冲突多个关键字映射到同一个 Hash 表地址 hash(x) = x%10 编号姓名李四

103 哈希查找冲突的解决线性开放地址法开放地址 : 如果这个地址冲突, 尝试其它地址, 即不封闭在一个地址上其它地址到底是哪个? 线性探测再散列二次探测再散列伪随机探测再散列 H ( H( key) d )% m i i

104 哈希查找冲突的解决线性开放地址法之线性探测再散列原地址 H 0 发生了冲突则第 i 次冲突的探测地址 H i = (H 0 +i)%m 例如 : Hash 函数为 :H(key) = key % 11 插入关键字 key = 60 Hash(key) = 60 % 11 = 5, 无冲突

105 哈希查找冲突的解决插入 key = 17 Hash(key) = 17 % 11 =

106 哈希查找冲突的解决插入 key = 29 Hash(key) = 29 % 11 =

107 哈希查找冲突的解决插入 key = 38 Hash(key) = 38 % 11 = 5 冲突! 看看第 6(5+1) 个单元是否空着? 冲突看看第 7(5+2) 个单元是否空着? 冲突看看第 8(5+3) 个单元是否空着? 空闲

108 哈希查找冲突的解决插入 key = 51 Hash(key) = 51 % 11 = 8 冲突! 鸠占雀巢看看第 9(8+1) 个单元是否空着? 空闲

109 哈希查找冲突的解决插入 key = 21 Hash(key) = 21 % 11 =

110 哈希查找冲突的解决插入 key = 16 Hash(key) = 16 % 11 = 5 冲突! 尝试

111 哈希查找冲突的解决线性探索法容易产生堆积 : 冲突的关键字只好向后寻找可用的空单元结果又占据了其它关键字的位置使得冲突更加严重查找次数增加

112 哈希查找冲突的解决线性开放地址法之二次探测再散列线性探索法容易产生堆积 : 因为如果当前地址产生了冲突, 尝试下一个地址, 这样容易造成连续的一大串地址冲突, 使得查找次数增加改进方法 : 如果当前地址冲突, 下一个的地址不是紧挨着, 而是离远一些, 而且冲突次数越多, 离得越远

113 哈希查找冲突的解决设关键字 key 原本映射为地址 H 0 = Hash(key) H 0 但是 H 0 发生了冲突则下一次尝试的地址为 : H i = (H 0 ±i 2 ) % m i 为冲突的次数 m 为 Hash 表大小 m = 4k+3, k=0,1,2...

114 哈希查找冲突的解决例 : 插入 key = 38 H0 = 38 % 11 = 5 冲突! H1 = (H )%11 = 6, 仍然冲突 H2 = (H )%11 =

115 哈希查找冲突的解决再哈希法若原地址 H 0 = Hash 0 (key) 冲突则下一个地址 H i = Hash i (key) 即换一个哈希函数试试

116 哈希查找冲突的解决链表法映射到同一地址的数据存放在链表中如 Hash(key) = key %

117 哈希查找查表查表给定关键字 key 运算 Hash 函数, 得到 Hash 地址若该地址存放的不是该关键字, 说明原来出现了冲突, 按照冲突解决方法查找下一个可能的地址

118 哈希查找查表例 Hash 函数 H(key) = key % 13 冲突解决方法 : 线性探测查找 % 13 = 6, 但是第 6 个单元不是 84 看看第 7 个单元看看第 8 个单元

119 本章小结查找的概念 : 平均查找长度 ASL 线性查找表线性查找 : 顺序表或链表 O(n) 折半查找 : 有序表 O(logn) 分块查找 : 索引顺序表 O(s+n/s) 二叉查找树二叉查找树平衡二叉树 O(logn) 散列表 ( 哈希表 ) 哈希查找 ( 哈希函数冲突解决方法 ( 开放链地址 )) O( 冲突次数 )

120 作业和参考作业习题集 P57: 参考 c-tutorial-intro-to-hash-tables/

121 附 : 链式 Hash 表 #include <stdio.h> #include <stdlib.h> #define SIZE 119 typedef int KeyType; typedef struct{ KeyType key; double score; }ElemType; typedef struct h_lnode{ ElemType data; struct h_lnode *next; }HLNode; typedef struct{ // int *array = (int *) malloc(100 * sizeof(int)) HLNode* *table; // HLNode* table[100] int size; }HashTable;

122 附 : 链式 Hash 表 bool InitHashTable( HashTable &hasht){ hasht.table = (HLNode* *) malloc(size*sizeof(hlnode*)); if (!hasht.table) return false; } hasht.size = SIZE; for (int i = 0; i < hasht.size; i++) hasht.table[i] = 0; return true; table

123 附 : 链式 Hash 表 int Hash(KeyType key){ return key%size;} bool InsertHashTable( HashTable &hasht, KeyType key, ElemType e){ HLNode* s = (HLNode* )malloc(sizeof(hlnode)); s->data = e; int hash_address = Hash(key); // 新结点插入在 hasht.table[hash_address] 所指示的链表的最前面 s->next = hasht.table[hash_address]; } hasht.table[hash_address] = s; return true;

124 附 : 链式 Hash 表 bool FindHashTable( HashTable &hasht, KeyType key, ElemType &e){ int hash_address = Hash(key); } HLNode* p = hasht.table[hash_address]; while (p){ if (p->data.key == key) { e = p->data;return true; } p = p->next; } return false;

125 附 : 链式 Hash 表 void HashTable_test(){ HashTable ht; ElemType e; KeyType key; InitHashTable(hT); e.key = 2134; e.score = 10.5; InsertHashTable(hT,e.key, e); e.key = 34; e.score = 20.5; InsertHashTable(hT, e.key, e); e.key = 25; e.score = 30.5; InsertHashTable(hT, e.key, e); } key = 20; if (FindHashTable(hT, key, e)) printf("%f\n", e.score); else printf("can't find the key%d\n", key); key = 25; if (FindHashTable(hT, key, e)) printf("%f\n", e.score); else printf("can't find the key%d\n", key);

PowerPoint Presentation

PowerPoint Presentation 数据结构与算法 ( 六 ) 张铭主讲采用教材 : 张铭, 王腾蛟, 赵海燕编写高等教育出版社,2008. 6 ( 十一五国家级规划教材 ) http://www.jpk.pku.edu.cn/pkujpk/course/sjjg 第 6 章树 C 树的定义和基本术语树的链式存储结构子结点表表示方法静态左孩子 / 右兄弟表示法动态表示法动态左孩子 / 右兄弟表示法父指针表示法及其在并查集中的应用