2010年自学考试《数据结构》各章复习要点总结
2010年自学考试《数据结构》各章复习要点总结(2) 2010年自学考试《数据结构》四至六章复习要点总结。
第四章串
串是零个或多个字符组成的有限序列。
·空串：是指长度为零的串，也就是串中不包含任何字符(结点)。
·空白串：指串中包含一个或多个空格字符的串。
·在一个串中任意个连续字符组成的子序列称为该串的子串，包含子串的串就称为主串。
·子串在主串中的序号就是指子串在主串中首次出现的位置。
·空串是任意串的子串，任意串是自身的子串。
串分为两种：
·串常量在程序中只能引用不能改变;
·串变量的值可以改变。
串的基本运算有：
·求串长strlen(char*s)
·串复制strcpy(char*to，char*from)
·串联接strcat(char*to，char*from)
·串比较charcmp(char*s1，char*s2)
·字符定位strchr(char*s，charc)
。串是特殊的线性表(结点是字符)，所以串的存储结构与线性表的存储结构类似。串的顺序存储结构简称为顺序串。
顺序串又可按存储分配的不同分为：
·静态存储分配：直接用定长的字符数组来定义。优点是涉及串长的操作速度快，但不适合插入、链接操作。
·动态存储分配：是在定义串时不分配存储空间，需要使用时按所需串的长度分配存储单元。
串的链式存储就是用单链表的方式存储串值，串的这种链式存储结构简称为链串。链串与单链表的差异只是它的结点数据域为单个字符。
为了解决“存储密度”低的状况，可以让一个结点存储多个字符，即结点的大小。
顺序串上子串定位的运算：又称串的“模式匹配”或“串匹配”，是在主串中查找出子串出现的位置。在串匹配中，将主串称为目标(串)，子串称为模式(串)。这是比较容易理解的，串匹配问题就是找出给定模式串P在给定目标串T中首次出现的有效位移或者是全部有效位移。最坏的情况下时间复杂度是O((n-m+1)m)，假如m与n同阶的话则它是O(n^2)。链串上的子串定位运算位移是结点地址而不是整数。
第五章多维数组和广义表
数组一般用顺序存储的方式表示。存储的方式有：
·行优先顺序，也就是把数组逐行依次排列。PASCAL、C
·列优先顺序，就是把数组逐列依次排列。FORTRAN
地址的计算方法：
·按行优先顺序排列的数组：LOCa(ij)=LOCa(11)+((i-1)*n+(j-1))*d.
·按列优先顺序排列的数组：LOCa(ij)=LOCa(11)+((j-1)*n+(i-1))*d. 矩阵的压缩存储：为多个相同的非零元素分配一个存储空间;对零元素不分配空间。
特殊矩阵的概念：所谓特殊矩阵是指非零元素或零元素分布有一定规律的矩阵。
稀疏矩阵的概念：一个矩阵中若其非零元素的个数远远小于零元素的个数，则该矩阵称为稀疏矩阵。
特殊矩阵的类型：
·对称矩阵：满足a(ij)=a(ji)。元素总数n(n+1)/2.I=max(i，j)，J=min(i，j)，LO Ca(ij)=LOC(sa[0])+(I*(I+1)/2+J)*d.
·三角矩阵：
·上三角阵：k=i*(2n-i+1)/2+j-i，LOCa(ij)=LOC(sa[0])+k*d.
·下三角阵：k=i*(i+1)/2+j，LOCa(ij)=LOC(sa[0])+k*d.
·对角矩阵：k=2i+j，LOCa(ij)=LOC(sa[0])+k*d.
稀疏矩阵的压缩存储方式用三元组表把非零元素的值和它所在的行号列号做为一个结点存放在一起，用这些结点组成的一个线性表来表示。但这种压缩存储方式将失去随机存储功能。加入行表记录每行的非零元素在三元组表中的起始位置，即带行表的三元组表。
广义表是n(n≥0)个元素的有限序列，其中的元素是原子或者是一个广义表。
广义表表头和表尾的概念：
·若广义表LS非空(n≥1)，则这个广义表的第一个元素就是表头。
·其余的元素组成的表称为LS的表尾，所以表尾必是一个子表。
广义表有两种表示法，一种是括号表示法，一种是图形表示法。
广义表与树(形结构)相对应，这个广义表就是纯表。
如果一个广义表的结点又可以被其他结点所共享，则这个表称为再入表。
允许递归的表称为递归表。
线性表∈纯表(树)∈再入表∈递归表。可见，广义表是对线性表和树的推广。
广义表有两个特殊的基本运算：
·取表头head(LS)：取表中的第一个数据元素，不能对空表操作。
·取表尾tail(LS);取除表头外，其余数据元素构成的子表，不能对空表操作。
第六章树
树是n个结点的有限集合，非空时必须满足：只有一个称为根的结点;其余结点形成m 个不相交的子集，并称根的子树。
根是开始结点;结点的子树数称度;度为0的结点称叶子(终端结点);度不为0的结点称分支结点(非终端结点);除根外的分支结点称内部结点;
有序树是子树有左，右之分的树;无序树是子树没有左，右之分的树;森林是m个互不相交的树的集合;
树的四种不同表示方法：
·树形表示法;
·嵌套集合表示法;
·凹入表示法;
·广义表表示法。
二叉树的定义：是n≥0个结点的有限集，它是空集(n=0)或由一个根结点及两棵互不相交的分别称作这个根的左子树和右子树的二叉树组成。
二叉树不是树的特殊情形，与度数为2的有序树不同。
二叉树的4个重要性质：
·二叉树上第i层上的结点数目最多为2^(i-1)(i≥1);
·深度为k的二叉树至多有(2^k)-1个结点(k≥1);
·在任意一棵二叉树中，若终端结点的个数为n0，度为2的结点数为n2，则n0=n2+1;
·具有n个结点的完全二叉树的深度为int(log2n)+1。满二叉树是一棵深度为k，结点数为(2^k)-1的二叉树;完全二叉树是满二叉树在最下层自右向左去处部分结点;
二叉树的顺序存储结构就是把二叉树的所有结点按照层次顺序存储到连续的存储单元中。(存储前先将其画成完全二叉树)
树的存储结构多用的是链式存储。BinTNode的结构为lchild|data|rchild，把所有BinTNode类型的结点，加上一个指向根结点的BinTree型头指针就构成了二叉树的链式存储结构，称为二叉链表。它就是由根指针root唯一确定的。共有2n个指针域，n+1个空指针。
根据访问结点的次序不同可得三种遍历：先序遍历(前序遍历或先根遍历)，中序遍历(或中根遍历)、后序遍历(或后根遍历)。时间复杂度为O(n)。
利用二叉链表中的n+1个空指针域来存放指向某种遍历次序下的前趋结点和后继结点的指针，这些附加的指针就称为“线索”，加上线索的二叉链表就称为线索链表。线索使得查找中序前趋和中序后继变得简单有效，但对于查找指定结点的前序前趋和后序后继并没有什么作用。
树和森林及二叉树的转换是唯一对应的。
转换方法：
·树变二叉树：兄弟相连，保留长子的连线。
·二叉树变树：结点的右孩子与其双亲连。
·森林变二叉树：树变二叉树，各个树的根相连。
树的存储结构：
·有双亲链表表示法：结点data | parent，对于求指定结点的双亲或祖先十分方便，但不适于求指定结点的孩子及后代。
·孩子链表表示法：为树中每个结点data | next设置一个孩子链表firstchild，并将data | firstchild存放在一个向量中。
·双亲孩子链表表示法：将双亲链表和孩子链表结合。
·孩子兄弟链表表示法：结点结构leftmostchild |data | rightsibing，附加两个分别指向该结点的最左孩子和右邻兄弟的指针域。树的前序遍历与相对应的二叉树的前序遍历一致;树的后序遍历与相对应的二叉树的中序遍历一致。
树的带权路径长度是树中所有叶结点的带权路径长度之和。树的带权路径长度最小的二叉树就称为最优二叉树(即哈夫曼树)。
在叶子的权值相同的二叉树中，完全二叉树的路径长度最短。
哈夫曼树有n个叶结点，共有2n-1个结点，没有度为1的结点，这类树又称为严格二叉树。
变长编码技术可以使频度高的字符编码短，而频度低的字符编码长，但是变长编码可能使解码产生二义性。如00、01、0001这三个码无法在解码时确定是哪一个，所以要求在字符编码时任一字符的编码都不是其他字符编码的前缀，这种码称为前缀码(其实是非前缀码)。
哈夫曼树的应用最广泛地是在编码技术上，它能够容易地求出给定字符集及其概率分布的最优前缀码。哈夫曼编码的构造很容易，只要画好了哈夫曼树，按分支情况在左路径上写代码0，右路径上写代码1，然后从上到下到叶结点的相应路径上的代码的序列就是该结点的最优前缀码。