更多优质自考资料尽在百度贴吧自考乐园俱乐部
（http://tieba.http://m.cmpx.com.cn//club/5346389）欢迎?加入...欢迎?交流...止不住的惊喜等着你.........
11. 对角矩阵: 所有的非零元素集中在以主对角线为中心的带状区域中，即除了主对角线和主对角线相邻两侧的若干条对角线上的元素之外，其余元素皆为零的矩阵为对角矩阵。
若|i-j|>(k-1)／2，则元素aij=0。对角矩阵可按行优先顺序或对角线的顺序，将其压缩存储到一个向量中，并且也能找到每个非零元素和向量下标的对应关系。
12. 稀疏矩阵:设矩阵Amn中有s个非零元素，若s远远小于矩阵元素的总数(即s< 其中每一个非零元素所在的行号、列号和值组成一个三元组(i，j，aij)，并由此三元组惟一确定。稀疏矩阵进行压缩存储通常有两类方法：顺序存储和链式存储。 13. 三元组表：将表示稀疏矩阵的非零元素的三元组按行优先(或列优先)的顺序排列(跳过零元素)，并依次存放在向量中，这种稀疏矩阵的顺序存储结构称为三元组表。 14.压缩存储结构上矩阵的转置运算 一个m×n的矩阵A，它的转置矩阵B是一个n×m的矩阵，且：A[i][j]=B[j][i]，0≤i 三元组表表示的矩阵转置的思想方法 第一步：根据A矩阵的行数、列数和非零元总数确定B矩阵的列数、行数和非零元总数。 第二步：当三元组表非空（A矩阵的非零元不为0）时，根据A矩阵三元组表的结点空间data（以下简称为三元组表），将A的三元组表a->data置换为B的三元组表b->data 15.三元组表的转置: 由于A的列是B的行，因此，按a->data的列序转置，所得到的转置矩阵B的三元组表b->data必定是按行优先存放的。 按这种方法设计的算法，其基本思想是：对A中的每一列 col(0≤col≤a->n-1)，通过从头至尾扫描三元组表a->data，找出所有列号等于col的那些三元组，将它们的行号和列号互换后依次放人b->data中，即可得到B的按行优先的压缩存贮表示。该算法的时间主要耗费在col和p的二重循环上：若A的列数为n，非零元素个数t，则执行时间为O(n×t)，即与A的列数和非零元素个数的乘积成正比。通常用二维数组表示矩阵时，其转置算法的执行时间是O(m×n)，它正比于行数和列数的乘积。 ════════════════════════════════════════════════════════════════════ 自考乐园,自考学习交流、资料共享的好去处！自考乐园,自考人自己的家园.... 俱乐部id：5346389（请牢记它哦~在百度贴吧的搜索框中输入俱乐部id,可以直接进入俱乐部 更多优质自考资料尽在百度贴吧自考乐园俱乐部 （http://tieba.http://m.cmpx.com.cn//club/5346389）欢迎?加入...欢迎?交流...止不住的惊喜等着你......... 16.带行表的三元组表: 为了方便某些矩阵运算，在按行优先存储的三元组表中，加入一个行表来记录稀疏矩阵中每行的非零元素在三元组表中的起始位置。这就是带行表的三元组表。相应的算法描述较为简单，但这类顺序存储方式对于非零元的位置或个数经常发生变化的矩阵运算就显得不太适合。 17. 广义表(Lists，又称列表)是线性表的推广。即广义表中放松对表元素的原子限制，容许它们具有其自身结构。 广义表是n(n≥0)个元素a1，a2，?，ai，?，an的有限序列。 其中： ①ai--或者是原子或者是一个广义表。 ②广义表通常记作：Ls=( a1，a2，?，ai，?，an)。 ③Ls是广义表的名字，n为它的长度。 ④若ai是广义表，则称它为Ls的子表。 注意： ①广义表通常用圆括号括起来，用逗号分隔其中的元素。 ②为了区分原子和广义表，书写时用大写字母表示广义表，用小写字母表示原子。 ③若广义表Ls非空(n≥1)，则al是LS的表头，其余元素组成的表(a1，a2，?，an)称为Ls的表尾。 ④广义表是递归定义的 广义表的深度：一个表的\深度\是指表展开后所含括号的层数。 18. 广义表的图形形状划分： ①与树对应的广义表称为纯表，它限制了表中成分的共享和递归 ②允许结点共享的表称再入表，上图(d),子表A是共享结点，它既是C的一个元素，又是子表B的元素； ③允许递归的表称为递归表 上图(e)，表D是其自身的子表。 19. 广义表的两个特殊的基本运算：取表头head(Ls)和取表尾tail(Ls)。 根据表头、表尾的定义可知：任何一个非空广义表的表头是表中第一个元素，它可以是原子，也可以是子表，而其表尾必定是子表。 head=(a，b)=a，tail(a，b)=(b) head(A，y)=A， tail(A，y)=(y) 由于tail(L)是非空表，可继续分解得到： head(tail(L))=b， tail(tail(L))=() 对非空表A和(y)，也可继续分解。 注意: 广义表()和(())不同。前者是长度为0的空表，对其不能做求表头和表尾的运算；而后者是长度为l的非空表(只不过该表中惟一的一个元素是空表)，对其可进行分解，得到的表头和表尾均是空表()。 ════════════════════════════════════════════════════════════════════ 自考乐园,自考学习交流、资料共享的好去处！自考乐园,自考人自己的家园.... 俱乐部id：5346389（请牢记它哦~在百度贴吧的搜索框中输入俱乐部id,可以直接进入俱乐部 更多优质自考资料尽在百度贴吧自考乐园俱乐部 （http://tieba.http://m.cmpx.com.cn//club/5346389）欢迎?加入...欢迎?交流...止不住的惊喜等着你......... 第六章 树 1. 树的递归定义： 树(Tree)是n(n≥0)个结点的有限集T，T为空时称为空树，否则它满足如下两个条件： (1)有且仅有一个特定的称为根(Root)的结点； (2)其余的结点可分为m(m≥0)个互不相交的子集Tl，T2，?，Tm，其中每个子集本身又是一棵树，并称其为根的子树(Subree)。 树的递归定义刻画了树的固有特性：一棵非空树是由若干棵子树构成的，而子树又可由若干棵更小的子树构成。 2. 广义表表示法: 用广义表的形式表示的。上图(a)树的广义表表示法如图(d) （A（B（E，F（I，J）），C，D（G，H））） 3. 树结构的基本术语 （1） 结点的度(Degree) 树中的一个结点拥有的子树数称为该结点的度(Degree)。 一棵树的度是指该树中结点的最大度数。 度为零的结点称为叶子(Leaf)或终端结点。 度不为零的结点称分支结点或非终端结点。 除根结点之外的分支结点统称为内部结点。 根结点又称为开始结点。 （2） 孩子(Child)和双亲(Parents) 树中某个结点的子树之根称为该结点的孩子(Child)或儿子，相应地，该结点称为孩子的双亲(Parents)或父亲。同一个双亲的孩子称为兄弟(Sibling)。 （3）祖先(Ancestor)和子孙(Descendant) ①路径（path）若树中存在一个结点序列k1，k2，?，ki，使得ki是ki+1的双亲(1≤i 路径的长度指路径所经过的边(即连接两个结点的线段)的数目，等于j-1。 ②祖先(Ancestor)和子孙(Descendant) 若树中结点k到ks存在一条路径，则称k是ks的祖先(Ancestor)，ks是k的子孙(Descendant)。 一个结点的祖先是从根结点到该结点路径上所经过的所有结点，而一个结点的子孙则是以该结点为根的子树中的所有结点。 （4）结点的层数(Level)和树的高度（Height） 结点的层数(Level)从根起算： 根的层数为1，其余结点的层数等于其双亲结点的层数加1。 双亲在同一层的结点互为堂兄弟。 树中结点的最大层数称为树的高度(Height)或深度(Depth)。 （5）有序树(OrderedTree)和无序树(UnoderedTree) 若将树中每个结点的各子树看成是从左到右有次序的(即不能互换)，则称该树为有序树(OrderedTree)；否则称为无序树(UnoderedTree)。若不特别指明，一般讨论的树都是有序树。 （6）森林(Forest) 森林(Forest)是m(m≥0)棵互不相交的树的集合。树和森林的概念相近。删去一棵树的根，就得到一个森林；════════════════════════════════════════════════════════════════════ 自考乐园,自考学习交流、资料共享的好去处！自考乐园,自考人自己的家园.... 俱乐部id：5346389（请牢记它哦~在百度贴吧的搜索框中输入俱乐部id,可以直接进入俱乐部 更多优质自考资料尽在百度贴吧自考乐园俱乐部 （http://tieba.http://m.cmpx.com.cn//club/5346389）欢迎?加入...欢迎?交流...止不住的惊喜等着你......... 反之，加上一个结点作树根，森林就变为一棵树。 4. 树形结构的逻辑特征 树形结构的逻辑特征可用树中结点之间的父子关系来描述： （1） 树中任一结点都可以有零个或多个直接后继(即孩子)结点，但至多只能有一个直接前趋(即双亲)结点。 （2） 树中只有根结点无前趋，它是开始结点；叶结点无后继，它们是终端结点。 （3） 祖先与子孙的关系是对父子关系的延拓，它定义了树中结点之间的纵向次序。 （4） 有序树中，同一组兄弟结点从左到右有长幼之分。 5. 二叉树(BinaryTree)是n(n≥0)个结点的有限集，它或者是空集(n=0)，或者由一个根结点及两棵互不相交的、分别称作这个根的左子树和右子树的二叉树组成。 二叉树与度数为2的有序树不同：在有序树中，虽然一个结点的孩子之间是有左右次序的，但是若该结点只有一个孩子，就无须区分其左右次序。而在二叉树中，即使是一个孩子也有左右之分。 6.二叉树的性质： i-14 性质1 二叉树第i层上的结点数目最多为2(i≥1)。例如5层的二叉树，第5层上的结点数目最多为2=16 k5 性质2 深度为k的二叉树至多有2-1个结点(k≥1)。例如深度为5的二叉树，至多有2-1=31个结点 性质3 在任意-棵二叉树中，若终端结点的个数为n0，度为2的结点数为n2，则no=n2+1。例如一棵深度为4的二叉树（a），其终端结点数n0为8,度为2的结点树为7，则8=7+1，no=n2+1成立 （b）其终端结点数n0为6,度为2的结点树为5，则6=5+1，no=n2+1成立 k 满二叉树：一棵深度为k且有2-1个结点的二又树称为满二叉树。满二叉树的特点： （1） 每一层上的结点数都达到最大值。即对给定的高度，它是具有最多结点数的二叉树。 （2） 满二叉树中不存在度数为1的结点，每个分支结点均有两棵高度相同的子树，且树叶都在最下一层上。 完全二叉树：若一棵二叉树至多只有最下面的两层上结点的度数可以小于2，并且最下一层上的结点都集中在该层 最左边的若干位置上，则此二叉树称为完全二叉树。特点： （1） 满二叉树是完全二叉树，完全二叉树不一定是满二叉树。 （2） 在满二叉树的最下一层上，从最右边开始连续删去若干结点后得到的二叉树仍然是一棵完全二叉树。 （3） 在完全二叉树中，若某个结点没有左孩子，则它一定没有右孩子，即该结点必是叶结点。 性质4 具有n个结点的完全二叉树的深度为。?lgn?+1 或?lg(n+1)? 例，具有100个结点的完全二叉树的深度为:?lg100?+1=7,2=64 2=128所以?lg100?=6 ,?lg(100+1)?=7 7．完全二叉树的编号特点：完全二叉树中除最下面一层外，各层都充满了结点。每一层的结点个数恰好是上一层结 点个数的2倍。从一个结点的编号就可推得其双亲，左、右孩子，兄弟等结点的编号。 ①若i>1，则ki的双亲编号为?i/2?；若i=1，则Ki是根结点，无双亲。 ②若2i≤n，则Ki的左孩子的编号是2i；否则，Ki无左孩子，即Ki必定是叶子。因此完全二叉树中编号i>?n/2?的结点必定是叶结点。 ③若2i+1≤n，则Ki的右孩子的编号是2i+1；否则，Ki无右孩子。 ════════════════════════════════════════════════════════════════════ 自考乐园,自考学习交流、资料共享的好去处！自考乐园,自考人自己的家园.... 俱乐部id：5346389（请牢记它哦~在百度贴吧的搜索框中输入俱乐部id,可以直接进入俱乐部 6 7 更多优质自考资料尽在百度贴吧自考乐园俱乐部 （http://tieba.http://m.cmpx.com.cn//club/5346389）欢迎?加入...欢迎?交流...止不住的惊喜等着你......... ④若i为奇数且不为1，则Ki的左兄弟的编号是i-1；否则，Ki无左兄弟。 ⑤若i为偶数且小于n，则Ki的右兄弟的编号是i+1；否则，Ki无右兄弟。 8. 完全二叉树的顺序存储：将完全二叉树中所有结点按编号顺序依次存储在一个向量bt[0..n]中。其中：bt[1．．n]用来存储结点，bt[0]不用或用来存储结点数目。 9. 一般二叉树的顺序存储: ① 将一般二叉树添上一些 \虚结点\，成为\完全二叉树\ ② 为了用结点在向量中的相对位置来表示结点之间的逻辑关系，按完全二叉树形式给结点编号 ③ 将结点按编号存入向量对应分量，其中\虚结点\用\∮\表示 10. 链式存储结构: 二叉树的每个结点最多有两个孩子。用链接方式存储二叉树时，每个结点除了存储结点本身的数据外，还应设置两个指针域lchild和rchild，分别指向该结点的左孩子和右孩子。结点的结构为： typedef char DataType； //用户可根据具体应用定义DataType的实际类型 typedef struct node{ DataType data； Struct node *lchild，*rchild； //左右孩子指针 }BinTNode； //结点类型 typedef BinTNode *BinTree；//BinTree为指向BinTNode类型结点的指针类型 11. 在一棵二叉树中，所有类型为BinTNode的结点，再加上一个指向开始结点(即根结点)的BinTree型头指针(即根指针)root，就构成了二叉树的链式存储结构，并将其称为二叉链表。 ════════════════════════════════════════════════════════════════════ 自考乐园,自考学习交流、资料共享的好去处！自考乐园,自考人自己的家园.... 俱乐部id：5346389（请牢记它哦~在百度贴吧的搜索框中输入俱乐部id,可以直接进入俱乐部
自考数据结构重点（珍藏版）
