2015年国家电网考试备考计算机之数据结构与算法(8)

　　B-树是一种平衡多路查找树，它在文件系统中很有用。一棵m阶B-树(图d为4阶B-树)，具有下列性质：

　　(1)树中每个节点至多有m棵子树;

　　(2)若根节点不是叶子节点，则至少有2棵子树;

　　(3)除根节点之外的所有非终端节点至少有棵子树;

　　(4)每个节点中的信息结构为(A0,K1,A1,K2......Kn,An)，其中n表示关键字个数，Ki为关键字，Ai为指针;

　　(5)所有的叶子节点都出现在同一层次上，且不带任何信息，也是为了保持算法的一致性。

　　5、B+树

　　B+数是B-树的一种变形，它与B-树的差别在于(图e为3阶B+树)：

　　(1)有n棵子树的节点含有n个关键字;

　　(2)所有的叶子节点包含了全部关键字的信息，及指向这些关键字记录的指针，且叶子节点本身按关键字大小自小到大顺序链接;

　　(3)所有非终端节点可以看成是索引部分，节点中仅含有其子树(根节点)中最大(或最小)关键字，所有B+树更像一个索引顺序表;

　　(4)对B+树进行查找运算，一是从最小关键字起进行顺序查找，二是从根节点开始，进行随机查找。

　　6、字典树(trie树)

　　字典树是一种以树形结构保存大量字符串。以便于字符串的统计和查找，经常被搜索引擎系统用于文本词频统计。它的优点是：利用字符串的公共前缀来节约存储空间，最大限度地减少无谓的字符串比较，查询效率比哈希表高。具有以下特点(图f)：

　　(1)根节点为空;

　　(2)除根节点外，每个节点包含一个字符;

　　(3)从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串。

　　(4)每个字符串在建立字典树的过程中都要加上一个区分的结束符，避免某个短字符串正好是某个长字符串的前缀而淹没。

　　7、后缀树

　　后缀树则是一个字符串的所有后缀组成的字典树。具体内容再前几章已讲过。

　　8、广义后缀树

　　广义后缀树是好几个字符串的的所有后缀组成的字典树，同样每个字符串的所有后缀都具有一个相同的结束符，不同字符串的结束符不同。

　　6.图 (Graph)

　　图是由结点的有穷集合V和边的集合E组成。其中，为了与树形结构加以区别，在图结构中常常将结点称为顶点，边是顶点的有序偶对，若两个顶点之间存在一条边，就表示这两个顶点具有相邻关系。

　　1.图的存储结构

　　1.1 邻接矩阵

　　图的邻接矩阵存储方式是用两个数组来表示图。一个一维数组存储图中顶点信息，一个二维数组(邻接矩阵)存储图中的边或弧的信息。

　　设图G有n个顶点，则邻接矩阵是一个n*n的方阵，定义为：