数据结构第10章.docx

《数据结构第10章.docx》由会员分享，可在线阅读，更多相关《数据结构第10章.docx（23页珍藏版）》请在三一办公上搜索。

1、第10章索引与散列一、复习要点索引结构和散列结构是用于外部搜索的搜索结构。数据在外存的组织即文件结构，主要 分顺序、直接存取（散列）和索引文件。在这些文件组织中使用的主要是索引和散列方法。1、基本知识点要求掌握静态索引结构，包括线性索引、倒排索引、静态索引树的搜索和构造方法。掌 握动态索引结构，包括B树的搜索、插入、删除，通过关键码个数估算B树的高度的方法; B+树的搜索、插入与删除。掌握散列法，包括散列函数的构造、处理溢出的闭散列方法； 处理溢出的开散列方法；散列表分析。二、难点与重点1、线性索引 密集索引、稀疏索引、索引表计算 基于属性查找建立倒排索引、单元式倒排表2、动态搜索树 平衡的m

2、路搜索树的定义、搜索算法 B树的定义、B树与平衡的m路搜索树的关系 B树的插入（包括结点分裂）、删除（包括结点调整与合并）方法 B树中结点个数与高度的关系 B+树的定义、搜索、插入与删除的方法3、散列表 散列函数的比较 装载因子a与平均搜索长度的关系，平均搜索长度的关系 表长m、表中已有数据对象个数n和装载因子的关系 解决冲突的（闭散列）线性探查法的运用，平均探查次数的计算 线性探查法的删除问题、散列表类的设计中必须为各地址设置三个状态 线性探查法中的堆积聚集问题 解决冲突的（闭散列）双散列法的运用，平均探查次数计算 双散列法中再散列函数的设计要求与表长m互质，为此m设计为质数较宜 解决冲突的

3、（闭散列）二次散列法的运用，平均探查次数计算 注意：二次散列法中装载因子a与表长m的设置 解决冲突的（开散列）开散列法的运用，平均探查次数计算 由平均探查次数计算装载因子a，再计算表大小的方法三、教材中习题的解析10-1什么是静态索引结构？什么是动态索引结构？它们各有哪些优缺点？【解答】静态索引结构指这种索引结构在初始创建，数据装入时就已经定型，而且在整个系统运 行期间，树的结构不发生变化，只是数据在更新。动态索引结构是指在整个系统运行期间，树的结构随数据的增删及时调整，以保持最佳的搜索效率。静态索引结构的优点是结构定型， 建立方法简单，存取方便；缺点是不利于更新，插入或删除时效率低。动态索引

4、结构的优点 是在插入或删除时能够自动调整索引树结构，以保持最佳的搜索效率；缺点是实现算法复杂。10-2设有10000个记录对象，通过分块划分为若干子表并建立索引，那么为了提高搜索效 率，每一个子表的大小应设计为多大？【解答】每个子表的大小s =n =10000 = 100个记录对象。10-3如果一个磁盘页块大小为1024 (=1K)字节，存储的每个记录对象需要占用16字节， 其中关键码占4字节，其它数据占12字节。所有记录均已按关键码有序地存储在磁盘文件 中，每个页块的第1个记录用于存放线性索引。另外在内存中开辟了 256K字节的空间可用 于存放线性索引。试问：(1) 若将线性索引常驻内存，文

5、件中最多可以存放多少个记录？(每个索引项8字节，其 中关键码4字节，地址4字节)(2) 如果使用二级索引，第二级索引占用1024字节(有128个索引项)，这时文件中最 多可以存放多少个记录？【解答】(1) 因为一个磁盘页块大小为1024字节，每个记录对象需要占用16字节，则每个页块 可存放1024 / 16 = 64个记录，除第一个记录存储线性索引外，每个页块可存储63个记录对 象。又因为在磁盘文件中所有记录对象按关键码有序存储，所以线性索引可以是稀疏索引， 每一个索引项存放一个页块的最大关键码及该页块的地址。若线性索引常驻内存，那么它最 多可存放256 * (1024 / 8 ) = 256

6、 * 128 = 32768个索引项，文件中可存放32768 * 63 = 2064384个记录对象。(2) 由于第二级索引占用1024个字节，内存中还剩255K字节用于第一级索引。第一 级索引有255 * 128 = 32640个索引项，作为稀疏索引，每个索引项索引一个页块，则索引文 件中可存放 32640 * 63 = 2056320010-4假设在数据库文件中的每一个记录是由占2个字节 的整型数关键码和一个变长的数据字段组成。数据字段都 是字符串。为了存放右面的那些记录，应如何组织线性索 引？【解答】将所有字符串依加入的先后次序存放于一个连续的 存储空间store中，这个空间也叫做“堆”

7、，它是存放所有3978210381037Hello World!XYZThis string is rather longThis is Shorter42ABC2222Hello new World!字符串的顺序文件。它有一个指针free，指示在堆store中当前可存放数据的开始地址。初 始时free置为0，表示可从文件的0号位置开始存放。线性索引中每个索引项给出记录关键 码，字符串在store中的起始地址和字符串的长度：关键码串长度串起始地址0fello World! fYZ Jhis string is rather long Jhisis Shorter ABC Hello new W

8、orld *1 free4235682312397120103715411038261522221659索引表ID堆 store10-5设有一个职工文件:记录地址职工号姓名性别职业年龄籍贯月工资（元）10032 _034刘激扬男教师29山东720.0010068064蔡晓莉女教师32辽宁1200.0010104 .073朱力男实验员26广东480.0010140081洪伟男教师36北京1400.0010176092卢声凯男教师28湖北720.0010212 一123林德康男行政秘书33江西480.0010248140熊南燕女教师27上海780.0010284175吕颖女实验员28江苏480.0

9、010320 _209袁秋慧女教师24广东720.00其中，关键码为职工号。试根据此文件，对下列查询组织主索引和倒排索引，再写出搜 索结果关键码。（1）男性职工；（2）月工资超过800元的职工；（3）月工资超过平均工资的职 工；（4）职业为实验员和行政秘书的男性职工；（5）男性教师或者年龄超过25岁且职业为实 验员和教师的女性职工。【解答】主索引职工号记录地址月工资倒排索引职务倒排索引月工资长度指针职务长度指针003410032480.3073教师6034106410068123064207310104175081308110140720.303409240921017609214051231

10、0212209209614010248780.1140实验员20737175102841200.10641758209103201400.1081行政秘书1123性别长度指针男5034073081092123女4064140175209性别倒排索引搜索结果:年龄长度指针24120926107327114028209217529103432106433112331_081年龄倒排索引（1）男性职工（搜索性别倒排索引）：034, 073, 081, 092, 123（2）月工资超过800元的职工（搜索月工资倒排索引）：064, 081（3）月工资超过平均工资的职工（搜索月工资倒排索引）月平均工资7

11、76元:064, 081, 140（4）职业为实验员和行政秘书的男性职工（搜索职务和性别倒排索引）：073, 123, 175 & 034, 073, 081, 092, 123 = 073, 123（5）男性教师（搜索性别与职务倒排索引）：034, 073, 081, 092, 123 & 034, 064, 081, 092, 140, 209 = 034, 081, 092年龄超过25岁且职业为实验员和教师的女性职工（搜索性别、职务和年龄倒排索引）:064, 140, 175, 209 & 034, 064, 073, 081, 092, 140, 175, 209 & 034, 064

12、, 073, 081,092, 123, 140, 175 = 064, 140, 17510-6倒排索引中的记录地址可以是记录的实际存放地址，也可以是记录的关键码。试比较 这两种方式的优缺点。【解答】在倒排索引中的记录地址用记录的实际存放地址，搜索的速度快；但以后在文件中插入 或删除记录对象时需要移动文件中的记录对象，从而改变记录的实际存放地址，这将对所有 的索引产生影响：修改所有倒排索引的指针，不但工作量大而且容易引入新的错误或遗漏， 使得系统不易维护。记录地址采用记录的关键码，缺点是寻找实际记录对象需要再经过主索引，降低了搜索 速度；但以后在文件中插入或删除记录对象时，如果移动文件中的记

13、录对象，导致许多记录 对象的实际存放地址发生变化，只需改变主索引中的相应记录地址，其他倒排索引中的指针 一律不变，使得系统容易维护，且不易产生新的错误和遗漏。10-7 m = 2的平衡m路搜索树是AVL树，m = 3的平衡m路搜索树是2-3树。它们的叶结 点必须在同一层吗？ m阶B树是平衡m路搜索树，反过来，平衡m路搜索树一定是B树吗？ 为什么？【解答】m = 3的平衡m路搜索树的叶结点不一定在同一层，而m阶B_树的叶结点必须在同一 层，所以m阶B_树是平衡m路搜索树，反过来，平衡m路搜索树不一定是B_树。10-8下图是一个3阶B树。试分别画出在插入65、15、40、30之后B树的变化。【解答

14、】插入65后:插入15后:插入40后:插入30后:10-9下图是一个3阶B树。试分别画出在删除50、40之后B树的变化。【解答】删除50后:删除40后:10-10对于一棵有1999999个关键码的199阶B树，试估计其最大层数(不包括失败结点) 及最小层数(不包括失败结点)。【解答】设B树的阶数m = 199，则m/2 = 100。若不包括失败结点层，则其最大层数为Llog前2 (N+1)/2)=Llog10 1000000=3若使得每一层关键码数达到最大，可使其层数达到最小。第0层最多有(m-1)个关键 码，第1层最多有m(m-1)个关键码，第2层最多有m2(m-1)个关键码，第h-1层最

15、多有mh-1 (m-1)个关键码。层数为h的B树最多有(m-1) + m(m-1) + m2(m-1) + mhT (m-1) = (m-1) (mh-1) / (m-1) = mh-1 个关键码。反之，若有 n 个关键码，nWmh-1，则 h N log m(n+1)，所以，有1999999个关键码的199阶B树的最小层数为log m(n+1) =log199 (1999999 +1) =log 199 2000000= 3 10-11给定一组记录，其关键码为字符。记录的插入顺序为 C, S, D, T, A, M, P I, B, W, N, GU, R, K, E, H, O, L, J

16、 ，给出插入这些记录后的4阶B+树。假定叶结点最多可存放3个记录。【解答】插入C, S, D 插入TCDS插入A插入M插入P插入I插入B, W N, G插入U插入R插入K插入E插入H插入O, L插入J10-12设有一棵B+树，其内部结点最多可存放100个子女，叶结点最多可存储15个记录。对于1, 2, 3, 4, 5层的B+树，最多能存储多少记录，最少能存储多少记录。【解答】一层B+树：根据B+树定义，一层B+树的结点只有一个，它既是根结点又是叶结点， 最多可存储ml = 15个记录，最少可存储m1/2 = 8个记录。二层B+树：第0层是根结点，它最多有m= 100棵子树，最少有2个结点；第1

17、层是 叶结点，它最多有m个结点，最多可存储m*m1 = 100*15 = 1500个记录，最少有2个结点， 最少可存储2*m1/2 = 16个记录。三层B+树：第2层是叶结点。它最多有m2个结点，最多可存储m2* m1 = 150000个记 录。最少有2*m/2 = 100个结点，最少可存储2*m/2 *m1/2 = 800个记录。四层B+树：第3层是叶结点。它最多有m3个结点，可存储m3* m1 = 15000000个记录。 最少有 2*m/2 2 = 2 * 502 = 5000 个结点，存储 2*m/2 2 *m1/2 = 40000 个记录。五层B+树：第4层是叶结点。它最多有m4个结

18、点，可存储m4* m1 = 1500000000个记 录。最少有 2*m/2 3 = 2 * 503 = 250 0 00 个结点，存储 2*m/2 3*m1/2 = 2000000 个记录。10-13设散列表为HT13,散列函数为H (key) = key %13。用闭散列法解决冲突，对下列关 键码序列 12, 23, 45, 57, 20, 03, 78, 31, 15, 36 造表。(1) 采用线性探查法寻找下一个空位，画出相应的散列表，并计算等概率下搜索成功的 平均搜索长度和搜索不成功的平均搜索长度。(2) 采用双散列法寻找下一个空位，再散列函数为RH (key) = (7*key)

19、% 10 + 1,寻找下 一个空位的公式为H.= (H.1 + RH (key) % 13, H1 = H (key)。画出相应的散列表，并计算等概 率下搜索成功的平均搜索长度。【解答】使用散列函数H(key) = key mod 13，有H(12) = 12,H(20) = 7,H(15) = 2,H(23) = 10,H(03) = 3, H(36) = 10.H(45) = 6,H(78) = 0,H(57) = 5,H(31) = 5,(1) 利用线性探查法造表：012345678910111278150357452031233612(1)(1)(1)(1)(1)(1)(4)(1)(2

20、)(1)搜索成功的平均搜索长度为人$1、吓=(1 + 1 + 1 + 1 + 1 + 1 + 4 + 1 + 2 + 1) = 14succ 1010搜索不成功的平均搜索长度为ASL = (2 + 1 + 3 + 2 + 1 + 5 + 4 + 3 + 2 + 1 + 5 + 4 + 3) = 36 unsuc c1313(2)利用双散列法造表：H.= (H. -1 + RH (key) % 13, H1 = H (key)012345678910111278150357452031362312(1)(1)(1)(1)(1)(3)(5)(1)搜索成功的平均搜索长度为ASLsucc = (1 +

21、 1 + 1 + 1 + 1 + 1 + 3 + 5 + 1 + 1) = 16succ 101010-14设有150个记录要存储到散列表中，要求利用线性探查法解决冲突，同时要求找到所 需记录的平均比较次数不超过2次。试问散列表需要设计多大？设a是散列表的装载因子， 则有ASL = 1(1 +)succ 21 a【解答】已知要存储的记录数为n = 150，查找成功的平均查找长度为ASLsucc 2,则有ASL =1 1 + 2，解得 a 2。又有 a = n =些 225。2 V 1 a 73m m310-15若设散列表的大小为m，利用散列函数计算出的散列地址为h = hash(x)。(1)

22、试证明：如果二次探查的顺序为(h + q2), (h + (qT)2),(h+1), h, (h-1),(h-q2)， 其中，q = (m-1)/2。因此在相继被探查的两个桶之间地址相减所得的差取模(m)的结果为m-2, m-4, m-6, ，5, 3, 1, 1, 3, 5, ，m-6, m-4, m-2(2) 编写一个算法，使用课文中讨论的散列函数h(x)和二次探查解决冲突的方法，按给 定值x来搜索一个大小为m的散列表。如果x不在表中，则将它插入到表中。【解答】(1)将探查序列分两部分讨论：(h + q2), (h + (q-1)2),(h+1), h 和(h-1), (h-22), ,(

23、h-q2)。对于前一部分，设其通项为h + ( q - d )2, d = 0, 1,q，则相邻两个桶之间地址相减所 得的差取模：(h + (q - (d -1) )2 - ( h + (q - d )2) ) % m = ( (q - (d -1 ) )2 - (q - d )2) % m=(2*q -2*d +1) % m = ( m - 2*d ) % m, (代换 q = (m-1)/2 )代入d = 1, 2,q，则可得到探查序列如下：m-2, m-4, m-6, ，5, 3, 1。 ( m - 2*q = m - 2* (m-1)/2 = 1 )对于后一部分，其通项为h - ( q

24、 - d )2, d = q, q+1,2q，则相邻两个桶之间地址相减 所得的差取模：(h - ( q - d )2 - ( h - ( q - (d+1) )2 ) ) % m = ( ( q - (d+1)2 - (q - d )2 )% m=(2*d - 2*q +1) % m = ( 2*d - m + 2) % m(代换q = (m-1)/2 )代入d = q, q+1,，2q-1，则可得到2*d-m+2 = 2*q - m +2 = m - 1 - m +2 = 1,2*d-m+2 = 2*q + 2 - m +2 = m - 1 + 2 - m +2 = 3,2*d-m+2 =

25、2*(2*q-1) - m +2 = 2*(m-1-1) - m + 2 = 2*m - 4 - m +2 = m - 2。证毕(2) 编写算法下面是使用二次探查法处理溢出时的散列表类的声明。template class HashTable /散列表类的定义public:enum KindOfEntry Active, Empty, Deleted ;/表项分类(活动 / 空 / 删)HashTable ( ) : TableSize ( DefaultSize ) AllocateHt ( ); CurrentSize = 0; /亦构造函数 HashTable ( ) delete ht;

26、/析构函数const HashTable & operator = ( const HashTable & ht2 ); /重载函数：表赋值7 int Find (const Type & x );/在散列表中搜索 xint IsEmpty ( ) return !CurrentSize? 1 : 0; /判散列表空否，空则返回 1private:struct HashEntry /散列表的表项定义Type Element;/表项的数据，即表项的关键码KindOfEntry info;三种状态：Active, Empty, DeletedHashEntry ( ) : info (Empty

27、) /表项构造函数HashEntry ( const Type &E, KindOfEntry i = Empty ) : Element (E), info (i) ;enum DefualtSize = 31; HashEntry *ht;/散列表存储数组int TableSizG/数组长度，是满足4k+3的质数，k是整数int CurrentSize;已占据散列地址数目void AllocateHt ( ) ht = new HashEntryTableSize ; 为散列表分配存储空间；int FindPos (const Type & x );/散列函数;template const

28、 HashTable & HashTable :operator = ( const HashTable &ht2 ) /重载函数：复制一个散列表ht2if (this != &ht2 ) delete ht; TableSize = ht2.TableSiz(; AllocateHt ( ); /重新分配目标散列表存储空间for (int i = 0; i TableSize; i+ ) hti = ht2.hti;/从源散列表向目标散列表传送CurrentSize = ht2.CurrentSize;传送当前表项个数return *this;/返回目标散列表结构指针template int

29、 HashTable : Find ( const Type& x ) /共有函数：找下一散列位置的函数int i = 0, q = ( TableSize-1 ) / 2, h0;/ i 为探查次数int CurrentPos = h0 = HashPos ( x );/利用散列函数计算x的散列地址while ( htCurrentPos.info != Empty & htCurrentPos.Element != x )/搜索是否要求表项if ( i = TableSize ) CurrentPos -= TableSize;实现取模else CurrentPos = h0 - ( i

30、-q ) * ( i - q );while ( CurrentPos 0 ) CurrentPos += TableSize;/实现取模i+;if ( htCurrentPos.info = Active & htCurrentPos.Element = x )return CurrentPos;/返回桶号else htCurrentPos.info = Active; htCurrentPos.Element = x;/插入 xif ( +CurrentSize TableSize / 2 )return CurrentPos;当前已有项数加1,不超过表长的一半返回HashEntry *O

31、ldht = ht;分裂空间处理：保存原来的散列表int OldTableSize = TableSizqCurrentSize = 0;TableSize = NextPrime ( 2 * OldTableSize ) /原表大小的 2 倍，取质数Allocateht ( );/建立新的二倍大小的空表for ( i = 0; i = 5if ( N % 2 = 0 ) N+;/偶数不是质数for (; !IsPrime (N); N += 2 );寻找质数return N ;测试N是否质数/若N能分解为两个整数的乘积，其中一个一定、/N能整除i, N不是质数/N是质数int IsPrime

32、 (int N ) for ( int i = 3; i*i = N; i += 2 )if ( N % i = 0 ) return 0;return 1;10-16编写一个算法，以字典顺序输出散列表中的所有标识符。设散列函数为hash(x) = x 中的第一个字符，采用线性探查法来解决冲突。试估计该算法所需的时间。【解答】用线性探查法处理溢出时散列表的类的声明。#define DefaultSize 1000#include #include #include class HashTable/散列表类定义public:enum KindOfEntry Active, Empty, Dele

33、ted ;/表项分类(活动 / 空 / 删)HashTable ( ) : TableSize ( DefaultSize ) ht = new HashEntryTableSize; /亦构造函数HashTable ( ) delete ht;/淅构函数int Find-Ins ( const char * id );/在散列表中搜索标识符idvoid HashSort ();private:struct HashEntry /表项定义Type Element;/表项的数据，即表项的关键码KindOfEntry info;三种状态：Active, Empty, DeletedHashEntr

34、y ( ) : info (Empty ) /表项构造函数，置空；HashEntry *ht;/散列表存储数组int TableSizq/最大桶数int FindPos (string s) const return atoi (*s) - 32; /散列函数int HashTable: Find-Ins ( const char * id ) int i = FindPos ( id ), j = i;/i是计算出来的散列地址while ( htj.info != Empty & strcmp ( htj.Element, id ) != 0 )7中突j = ( j + 1 ) % Tabl

35、eSize;/当做循环表处理，找下一个空桶if ( j = i ) return -TableSize;/转一圈回到开始点，表已满，失败if ( htj.info != Active ) /插入if ( j i ) while ( int k = j; k i; k-) htk.Element = htk-1.Element; htk.info = htk-1.info; hti.Element = id; hti.info = Active;/插入 else HashEntry temp ;temp.Element = htTableSize- 1.Element; temp.info =

36、htTableSize- 1.info;while ( int k = TableSize-1; k i; k-) htk.Element = htk-1.Element; htk.info = htk-1.info; hti.Element = id; hti.info = Active;/插入while ( int k = j; k 0; k-) htk.Element = htk-1.Element; htk.info = htk-1.info; ht0.Element = temp.Element; ht0.info = temp.info;return j ;void HashTab

37、le: HashSort ( ) int n， i; char * str ;cin n str;for ( i = 0; i n; i+ ) if ( Find-Ins ( str ) = - Tablesize ) cout ”表已满 str;for ( i = 0; i TableSize; i+ )if ( hti.info = Active ) cout hti.Element endl;10-17设有1000个值在1到10000的整数，试设计一个利用散列方法的算法，以最少的数 据比较次数和移动次数对它们进行排序。【解答1】建立TableSize = 10000的散列表，散列函数定义

38、为int HashTable : FindPos ( const int x ) return x-1; 相应排序算法基于散列表类#define DefaultSize 10000#define n 1000class HashTable public:enum KindOfEntry Active, Empty, Deleted ;/散列表类的定义/表项分类（活动/空/删）-HashTable ( ) delete ht; void HashSort (int A , int n );private:struct HashEntry int Element;KindOfEntry info

39、;HashEntry ( ) : info (Empty ) ;HashEntry *ht;int TableSize;int FindPos ( int x );/淅构函数/散列法排序/散列表的表项定义/表项的数据，整数三种状态:Active, Empty, Deleted/表项构造函数/散列表存储数组/数组长度/散列函数HashTable ( ) : TableSize ( DefaultSize ) ht = new HashEntryTableSize /亦构造函数;voidHashTable : HashSort (int A , int n ) /散列法排序for ( int i

40、= 0; i n; i+ ) int position = FindPos( Ai );htposition.info = Active; htposition.Element = Ai;int pos = 0;for ( int i = 0; i TableSize; i+ )if ( hti.info = Active ) cout hti.Element endl; Apos = hti.Element; pos +; 【解答2】利用开散列的方法进行排序。其散列表类及散列表链结点类的定义如下:#define DefaultSize 3334#define n 1000class Hash

41、Table;/散列表类的前视声明class ListNode /各桶中同义词子表的链结点（表项）定义friend class HashTable; private:int key;ListNode *link;public:/整数数据/链指针ListNode ( int x ) : key(x), link(NULL) /构造函数;链表指针typedef ListNode *ListPtr;class HashTablepublic:HashTable( int size = DefaultSize ) TableSize = size; ht = new ListPtrsize; void HashSort ( int A ; int n )private:int TableSize;ListPtr *ht;int F