Microsoft PowerPoint - ds-9.ppt [兼容模式]

Size: px

Start display at page:

Download "Microsoft PowerPoint - ds-9.ppt [兼容模式]"

蓁耗波柯
7 years ago
Views:

1 第九章静态表动态表哈希表 9.1 基本概念 (Page 214) 2 表 : 是由同一类型元素成的集合静态表 : 只做询或检索操作动态表 : 询检索插入删除关键字 : 是元素中某个相的值, 用它可以标识一个元素主关键字次关键字 : 根给定值, 在表中确定一个其关键字等于给定值的元素成功返回位置序号不成功返回 0 1

2 3 注意比较各种算法时间复杂度和空间复杂度, 算法的主要时间用于关键字的比较静态表顺序表的 typedef int KT ; typedef struct{kt key ;... }ET; typedef struct{et *elem; // 元素存储空间基址,0 为空单元 int length;}sst; int Search_Sq(SST ST, KT key){ St.elem[0].key=key;// 设置哨兵 for (i=st.length ; key!=st.elem[i].key; i--) ; return i; } 2

$Search_Sq(SST ST, KT key){ St.elem[0].key=key;// 设置哨兵 for (i=st.length ; key!$

3 5 顺序表的算法性能分析在等概率的情况下 :Pi=1/n 成功时的平均长度 : (n+1)/2 不成功时的比较次 : n+1 假设成功与不成功的可能性相同, 在等概率的情况下 :Pi=1/2n, 则顺序的平均长度为 : ASLss=((n+1)+(n+1)/2)/2=3(n+1)/4 有序表的折半折半 ( 二分 ): 经过一次比较将表分割成两部分, 然后只在表的一部分中继续进行的方法 mid=(low+high)/2 6 key =13 3

4 7 二分算法描述 int Search_Bin(SST ST, KT key){ low=1 ; high=st. length; while (low<=high) { mid=(low+high)/2; if(key==st.elem[mid].key) return mid; else if (key<st.elem[mid].key) high=mid-1; else low=mid+1; } return 0; }// 时间复杂度 :O(log2 n) 8 二叉树的性质 i-1 1 在二叉树的第 i 层上至多有 2 个点 (i>=1); k 2 深度为 k 的二叉树至多有 2-1 个点 (k>=1); 3 对任何一棵二叉树 T, 如果其终端点为 n0, 度为 2 的点为 n2, 则 n0=n2+1 4 具有 n 个点的完全二叉树的深度为 : log2 n +1 4

5 9 二叉判定树过程可用二叉树来描述树中每个点表示一个记录, 点中的值为该记录在表中的位置, 通常这个描述过程的二叉树为判定树在该树中, 和给定值进行比较的次恰为该点在判定树中的层次 10 性能分析比较次最多 : log2 n +1 不超过判定树的深度时间复杂度 : O(log2 n) 此方法只能适用于有序表, 且限于顺序存储 5

6 11 索引顺序表的 ( 分块 ) 要求 : 索引表按表中记录的关键字分块, R 1,R 2,,R L 第 R k 块中所有关键字 < R k+1 块中的所有关键字 k=1,2,,l-1, 称为分块有序对每块建立一个索引项, 包含有两项内容 : 关键字项 : 为该块中最大关键字值 ; 指针项 : 为该块第一个记录在表中位置. 所有索引项组成索引表过程确定待记录所在块 ; ( 可以用顺序或折半 ) 在块内顺序. ( 块内只能用顺序 ) 索引表

录在表中位置. 所有索引项组成索引表过程确定待记录所在块 ; ( 可以用顺序或折半 ) 在块内顺序.

7 13 性能分析 ASL bs =L b +L w, L b 为确定块的平均长度 ;L w 为块内次若顺序 : ASL bs =L b +L w =(n/s+s)/2+1 若折半 : ASL bs =L b +L w = log 2 (n/s+1)+s/2 三种方法比较顺序折半分块 ASL 大小中表要求无有序表块间有序 9.3 动态表 14 二叉排序树 (BST) 二叉排序树的定义 :page 227 过程二叉排序树的插入和删除二叉排序树的分析含有 n 个点的二叉排序树的平均长度和树的形态有关 : 最差的形态是 : 单支树 ( (n+1)/2 ); 最好的形态是 : 判定树 ( log 2 n ) 在随机情况下, 二叉排序树的平均长度和 log n 是等量级的 7

3 动态表 14 二叉排序树 (BST) 二叉排序树的定义 :page 227 过程二叉排序树的插入和删除二叉排序树的分析含有 n 个点的二叉排序树

8 15 算法当前 BST 非空时, 将给定值 k 与当前根点的关键字比较 : 若相等, 成功, 束 ; 若 k 小于当前根点的关键字, 则将左子树作为当前 BST; 若 k 大于当前根点的关键字, 则将右子树作为当前 BST; 重复 (1) 16 8

9 17 BT SearchBST ( BT T,int key ) { if ( (!T ) key = =T->data) ) return ( T ); else if (key<t->data) return ( SearchBST ( T->lchild, key ) ); else return ( SearchBST ( T->rchild, key ) ); } 18 Status Search_Bit(BT T,BT &f,bt &p, int key) { // f 是 p 的双亲点指针 p=t; f=t ; while (p) { if (p->data==key) return TRUE; else if (key<(p->data)) { f = p ; p=p->lchild; } else { f = p ; p=p->rchild ; } } return FALSE; } 9

$return ( SearchBST ( T->rchild, key ) ); } 18 Status Search_Bit(BT T,BT &f,bt &p, int key) { // f 是 p 的$

10 19 在二叉排序树中插入关键字为 key 的点 Status Insert_Bit(BT T,int key ){ if (!Search_Bit(T, f, p, key )) { p=(btn *)malloc(sizeof(btn)); p->lchild = p->rchild = NULL; p->data = key ; if (!f ) T= p; else if (key<(f->data) ) else f->rchild=p; return OK; } return ERROR ; } f->lchild=p; 例 : 将序列 (45,24,53,12,24,90) 造成为二叉排序树 20 10

11 21 BST 的特点 : 中序遍历 BST 可得到一个关键字的有序序列在 BST 上插入新点时, 不必移动其他点, 仅需改动某点的指针 ( 因新点总是 BST 上的一个新叶点 ) BST 既具有类似折半的特性 ( 与 BST 的平衡度有关 ) 又采用了链表存储 ( 折半不能为链表存储 ), 因此, 对于经常要进行插入和删除记录的有序表, 采用 BST 尤其合适 22 平衡二叉树 (AVL 树 ): 定义 : 它或是一棵空树, 或者是左子树和右子树的深度差的绝对值不超过 1; 且左子树和右子树都是平衡二叉树平衡因子 BF: 是该点的左子树的深度减去它的右子树的深度平衡二叉树上的所有点的平衡因子只可能是 -1,0,1 在成二叉排序树的过程中进行平衡化处理, 成为二叉平衡树 11

其合适 22 平衡二叉树 (AVL 树 ): 定义 : 它或是一棵空树, 或者是左子树和右子树的深度差的绝对值不超过 1; 且左子树和右子树都是平衡二叉树平衡因子 BF:

12 例 : 平衡二叉树与非平衡二叉树的比较 23 平衡二叉树非平衡二叉树 24 二叉平衡树的平衡调整的四种基本类型插入元素 1 插入元素 9 L L 型 R R 型 12

13 L R 型 25 R L 型 26 L +1 h+1 LL 型平衡旋转 ( 顺时针 ) 失去平衡点的平衡因子为 2, 其左孩子的平衡因子为 1 1 B 2 A B L h B R h-1 a A R h-1 LL 0 B 0 B L h A h B R h-1 A R h-1 13

14 RR 型平衡旋转 ( 逆时针, 与 LL 对称 ) 失去平衡点的平衡因子为 -2, 其右孩子的平衡因子为 -1 A L -2 A h-1-1 B RR 0 A 0 B B R 27 B L h-1 B R h A L h-1 B L 28 B L LR 型平衡旋转失去平衡点的平衡因子为 2, 其左孩子的平衡因子为 -1-1 B h-1 h+1 2 A 1 C C L h-1 h C R A R h-1 h-2 LR 0 B 0 C B L h-1 C L h-1 C R -1 A h-2 A R h-1 中序遍历 :B L B C L C C R A A R B L B C L C C R A A R 14

因子为 2, 其左孩子的平衡因子为 -1-1 B h-1 h+1 2 A 1 C C L h-1 h C R A R h-1 h-2 LR 0 B 0 C

15 29 RL 型平衡旋转失去平衡点的平衡因子为 -2, 其右孩子的平衡因子为 1-2 A A L h-1 C L h-1 1 RL 0 C B B R h-1 A B C C R h-2 A L C L C R h-2 B R 中序遍历 :A L A C L C C R B B R A L A C L C C R B B R 若关键字的输入序列为 : {4,5,7,2,1,3,6} 请造 AVL 树

16 31 平衡化算法 p p 平衡二叉排序树的类型定义 : typedef struct BSTN{ lc A A rc Elemtype data; B B int bf; /* 点的平衡因子 */ struct BSTN *Lc, *Rc; } BSTN,*BST; 1. 右旋处理 :p 指向旋转处理前的左子树的根点 void R_rotate( BST &p){ lc=p->lc ; p->lc=lc->rc ; lc->rc=p ; p=lc;} 2. 左旋处理 :p 指向旋转处理前的右子树的根点 void L_rotate(BST &p) { rc=p->rc ; p->rc= rc->lc ; rc->lc=p ; p=rc ; } 32 对二叉树 T 作左平衡旋转 void LeftBalance( BST &T){ lc =T->Lc; switch(lc->bf){ case 1: T->bf = lc->bf =0; R_rotate(T); break; case -1: rd = lc->rc; switch(rd->bf){ case 1:T->bf = -1 ; lc->bf =0;break; case 0:T->bf = lc->bf =0;break; case -1:T->bf =0;lc->bf =1; } rd->bf =0; L_rotate(T->Lc); R_rotate(T); } } 16

$左旋处理 :p 指向旋转处理前的右子树的根点 void L_rotate(BST &p) { rc=p->rc ; p->rc= rc->lc ; rc->lc=p ; p=rc ; } 32 对二叉树 T 作左平衡旋转 void LeftBalance( BST &T){ lc$

17 在平衡二叉排序树上插入元素 Status InsertAVL(BST &T, ElemType e,boolean &taller) { if(!t) { T=(BST)malloc(sizeof(BSTN)); T->data=e; T->Lc=T->Rc=NULL;T->bf =0;taller =TRUE; } else { if ( e.key==t->data.key){taller=false;return 0;} if((e.key<t->data.key){k =InsertAVL(T->Lc,e,taller); if (!k) return 0; if (taller) switch(t->bf){ case 1: LeftBalance(T);taller =FALSE;break; case 0: T->bf =1;taller =TRUE; break; case -1: T->bf =0;taller =FALSE; } } else {k = InsertAVL(T->Rc, e, taller ); } if (!k) return 0; if (taller) switch (T->bf){ case 1: T->bf =0 ; taller=false;break; case 0:T->bf = -1 ; taller=true ; break; case -1: RightBalace(T) ; taller = FALSE ; } } } return 1; 17

key){k =InsertAVL(T->Lc,e,taller); if (!

18 B- 树 B- 树的定义 : 一棵 m 阶 B- 树, 或为空树, 或为满足下列特性的 m 叉树 : 树中每个点至多有 m 棵子树 ; 若根点不是叶子点, 则至少有两棵子树 ; 除根外的所有非终端点至少有 m/2 棵子树 ; 所有的点中包含下列信息 (P 239) ( n, A0, K1, A1, K2, A2,..., Kn, An ) (Ki<Ki+1) 所有的叶子点都出现在同一层次上例如 :3 阶 B- 树的非终端点 : N A0 Key1 A1 Key2 A2 一棵四阶的 B - 树 F F F F F F F F F F F F 18

19 37 B- 树的 t , 阶 B- 树 50 Key = B 树的插入在 B 树中插入时, 形成的点分裂是由下层点逐步向上层传递的, 在极端情况下, 会一直传递到根点 ( 实际上, 这是 B 树长高的唯一途径 ) 38 45, 57 插入 38, 45, 57 点分裂依次插入 48,25,30 19

20 45 30, 45 25, 30, 38 48, , 50, 57 插入 50, 产生两次点分裂 , 试依次插入 32,15,55,35,20,41,90 57 B - 树的删 40 除操作 , 删除关键字可能形成点的合并 B- 树的高度降低 57 32, , 删除关键字 50 20

21 动态表动态表顺序表动态线性表中已经讨论树型表动态二叉排序树平衡二叉树 41 B 树 B + 树改进实现索引性能分析键树 ( 字树 ) 7.5 哈希表 ( 散列表 ) 42 概念哈希函 : 在记录的存储位置和它的关键字间建立一个确定关系 f, 是每个关键字和中一个唯一的存储位置对应这个对应关系 f 为哈希函根这个思想建立的表为哈希表同义词 : 若 key1!= key2, 而 f(key1)=f(key2), 则这种现象成为冲突, 且 key1 和 key2 对哈希函 f 来说称为同义词关键字集 A m 哈希函 H(k) 地址空间 D n 21

22 43 哈希造表或散列 : 根设定的哈希函 f =H(key) 和处理冲突的方法, 将一组关键字映象到一个有限的连续地址集 ( 区间 ) 上, 以关键字的哈希函值作为记录在表中的位置, 这一映象过程称为哈希造表或散列记录的存储位置叫哈希地址或散列地址关键问题造好哈希函的方法 ; 研究解决冲突的方法 44 装填因子 : 表中填入的记录 = 哈希表的长度标志哈希表的装满程度 : 越小, 发生冲突的可能性就越小 ; 反, 越大, 表中已填入的记录越多, 再填记录时, 发生冲突的可能性就越大 22

23 45 哈希函的造方法判定标准计算简单容易冲突极少直接地址法 : 取关键字或关键字的某个线性函值为哈希地址 H(key)=key 或 H(key)=a*key+b 例 : 开辟 60 个记录的存储区,key = 年号 H(key)=key 哈希地址 H(1949)= 0 H(1962)= 13 H(1950)= 1 H(1963)= 14 H(1951)= 2 H(1964)= H(1998)= 除留余法 : 取关键字被某个不大于哈希表表长 m 的 p 除后所得余为哈希地址 H(key)=key mod p ( p m) 例 : 开辟 38 个记录的存储区, key = 学号 % 1000 H(key)=key % 38 H(031)= 31 H(044)= 6 H(032)=32 H(045)= 7 H(033)= 33 H(046)= 8... H(069)= 31 H(071)=33 //031 和 069 是同义词, 散列时产生冲突通常, 选择 p m 的某个质 23

24 47 字分析法假设关键字是以 r 为基的, 并且哈希表中可能出现的关键字都是事先知道的, 则可取关键字的若干位组成哈希地址平方取中法取关键字平方后的中间几位为哈希地址折叠法将关键字分割成位相同的几部分, 然后取这几部分的叠加和随机法选择一个随机函, 取关键字的随机函值为它的哈希地址即 : H(key)=random(key) 48 处理冲突的方法开放地址法 :( 探测法 ) Hi=(H(key)+di) mod m (1) 线性探测再散列 :di=1,2,3,4,...,m-1 (2) 二次探测再散列 :di=±k*k ( 1 k m/2) (3) 伪随机探测再散列 :di= 伪随机列再哈希法 : 用另一个哈希函 2 计算地址, 直到冲突不再发生链地址法 : 将所有的关键字为同义词的记录存储在同一线性链表中建立一个公共溢出区 :Hash 表分为基本表和溢出表, 所有发生冲突的关键字都填入溢出表 24

25 49 例 : 长度为 16 的哈希表中已有关键字节 19,70,33, H(key)= key mod 13, 现有 18, 用开放地址法处理冲突解 : 其处理方法如下图所示二次探测线性探测 50 例 :H(key)= key mod 13, 采用线性探测再散列法处理冲突, m=16 对关键字 19,14,23,01,68,20,84,27,55,11,10,79 19,14,23,01,68,20,84,27,55,11,10,

26 H(key)= key mod 对关键字 19,14,23,01,68,20,84,27,55,11,10,79 链地址法处理的果为 : Hash 表 52 H(key)= key mod 13 对关键字 19,14,23, 01,68,20,84,27, 55,11,10,79 公共溢出区法处理的果为 : 溢出表顺序

27 53 两种方法平均长度的比较 : 链地址法 : ASL(12)=(1*6+2*4+3+4)/12=1.75 线性探测再散列 : ASL(12)=(1*6+2+3*3+4+9)/12=2.5 因此, 线性探测在散列在处理冲突的过程中易产生记录的二次聚集, 而链地址法处理冲突时不会发生类似情况, 故其平均长度较优 54 哈希表算法描述 1. 计算哈希地址 #define ListLen 13 int Hash(int key) { return(key %Listlen); } 2. 哈希表 int Search_H(int A[ ], int key){ k=hash(key); for (i=0;i<listlen ;i++) { j=(k+i)%listlen; if (A[ j]==0 key==a[j] ) return j; } return k; } 27

28 55 3. 在哈希表中插入关键字 key Insert_Hash( int H[ ] ; int key ){ k=search_h( H, key); if ( H[k]==0 ) H[k]=key ; else if (key==h[k]) printf( 表中已存在该关键字 ); else printf( 哈希表已满!! ); } main( ) { int H[ListLen], i, key; for( i=0; i<listlen; i++) H[ i ]=0; // 置空 for(i=0;i<listlen-2 ; i++){ scanf( %d, &key); Insert_Hash(H, key); } } 56 哈希表哈希函造处理冲突性能分析举例哈希 (Hash) 表定义直接定址法字分析法开放定址法若中存在和 K 相等的纪录, 则必定在 f(k) 的存储位置上, 由此不需要进行比较便可直接取得所记录我们称 f 为哈希函, 这种思想形成的表叫哈希表平方取中法再哈希法折叠法链地址法除留余法公共溢出区随机法 28

29 Hash 表要求掌握的内容熟练掌握除留余法, 会造 Hash 函 2. 根哈希函和处理冲突的方法, (1) 手工造已知序列的哈希表 (2) 编写造哈希表的算法 (3) 编写在哈希表上的算法 ; (4) 在记录的概率相等的前提下, 计算哈希表平均长度本章重点 58 与有关的基本概念及存储静态表 : 顺序表的, 有序表的, 索引顺序表的动态表 : 二叉排序树的造过程, 插入及删除操作 ; 平衡二叉树几种类型的调整 ;B- 树的定义, 插入及删除操作各种方法的性能比较哈希函及哈希表 ; 哈希函的造方法 ; 处理冲突的方法 29

30 第九章作业 60 作业 1. 已知一组关键字为 (38,65,20,18,50,90,35, 80,100,95,61,19), 依次插入关键字生成一棵二叉排序树, 问 : (1) 关键字等于 61 的点记录需比较次 ; (2) 与 61 比较的关键字序列是 ; (3) 如果将关键字为 85 的记录插入到树中, 它将作为点的孩子点 ; (4) 若要删除关键字为 65 的记录, 可以取或替换 65 作为 38 点的右子树的根 2. 什么叫平衡二叉树? 试按下列次序将各关键字插入到平衡二叉树中, 画出重新平衡的情况 ( 8,9,10,2,1,5,3,6,4,7,11,12) 30

31 61 编写算法 1. 在二叉排序树 T( 二叉链存储 ) 中插入一个点 p; 2. 在二叉排序树 T 中删除任一点 q; 3. 根给定关键字序列, 生成一棵二叉排序树 4. 分别对 LL 型 RR 型 LR 型 RL 型的二叉排序树 T( T 所指点的平衡因子为 2 或 -2 ) 进行平衡化处理 5. 设计实现分块的算法 62 哈希表作业设哈希表长为 13, 散列函为 H(k)=k mod 13, 关键字序列为 7,4,1,14,100,30,5,9, 20,134; 试求 : (1) 散列后的表中关键字分布 ( 假定解决冲突的方法为线性探测再散列法 ); 求平均长度 ASL; (2) 求出散列后的表的装填因子 ; (3) 用链地址法解决冲突, 给出相应的哈希表, 求 ASL; (4) 分别计算该序列用顺序法和排序后用折半的 ASL 31

32 实验六 : 实验掌握并实现算法 ( 顺序算法折半哈希表的实现 ), 并对各种技术的时间空间复杂性有进一步认识 63 32

Microsoft PowerPoint - ds-1.ppt [兼容模式]

Microsoft PowerPoint - ds-1.ppt [兼容模式] http://jwc..edu.cn/jxgl/ HomePage/Default.asp 2 说明总学时 : 72( 学时 )= 56( 课时 )+ 16( 实验 ) 行课时间 : 第 1 ~14 周周学时 : 平均每周 4 学时上机安排待定考试时间 : 课程束第 8 11 12 章的内容为自学内容 ; 目录中标有