《2019数据结构复习重点》由会员分享，可在线阅读，更多相关《2019数据结构复习重点（19页珍藏版）》请在金锄头文库上搜索。
1、数据结构复习重点谁让我找到你们了第一章1. 数据是信息的载体，它能够被计算机识别、存储和加工处理。 数据元素是数据的基本单位。有些情况下，数据元素也称为元素、结点、顶点、记录。3.数据结构指的是数据之间的相互关系，即数据的组织形式。一般包括三个方面的内容：数据元素之间的逻辑关系，也称为数据的逻辑结构；数据元素及其关系在计算机存储器内的表示，称为数据的存储结构；数据的运算，即对数据施加的操作。数据类型是一个值的集合以及在这些值上定义的一组操作的总称。按值是否可分解，可将数据类型划分为两类：原子类型，其值不可分解；结构类型，其值可分解为若干个成分。4. 抽象数据类型是指抽象数据的组织和与之相关的操
2、作。可以看作是数据的逻辑结构及其在逻辑结构上定义的操作。数据的逻辑结构简称为数据结构。数据的逻辑结构可分为两大类：线性结构（的逻辑特征是若结构是非空集，则有且仅有一个开始结点和一个终端结点，并且所有结点都最多只有一个直接前趋和一个直接后继）；非线性结构（的逻辑特征是一个结点可能有多个直接前趋和直接后继）。 数据存储结构可用四种基本的存储方法表示：顺序存储方法（该方法是把逻辑上相邻的结点存储在物理位置上相邻的存储单元里，结点间的逻辑关系由存储单元的邻接关系来体现。由此得到的存储表示称为顺序存储结构）；链接存储方法（该方法不要求逻辑上相邻的结点在物理位置上亦相邻，结点间的逻辑关系是由附加的指针字段
3、表示的。由此得到的存储表示称为链式存储结构）；索引存储方法（该方法通常是在存储结点信息的同时，还建立附加的索引表）；散列存储方法(该方法的基本思想是根据结点的关键字直接计算出该结点的存储地址)。5. 非形式地说，算法是任意一个良定义的计算过程，它以一个或多个值作为输入，并产生一个或多个值为输出。因此，一个算法是一系列将输入转换为输出的计算步骤。6. 求解同一计算问题可能有许多不同的算法，究竟如何来评价这些算法的好坏以便从中选出较好的算法呢？选用的算法首先应该是正确的。此外，主要考虑三点：执行算法所耗费的时间；执行算法所耗费的存储空间，其中主要考虑辅助存储空间；算法应易于理解，易于编码，易于调试
4、等等。7. 性结构反映结点的逻辑关系是一对一的，非线性结构反映结点间的逻辑关系是多对多的。8. 数据的运算最常用的五种，分别是查找、插入、删除、更新、和排序。9. 一个算法的效率可分为时间效率和空间效率。第二章线性表1. 线性表是由n(n0)个数据元素(结点)a1,a2,an组成的有限序列。其中数据元素的个数n定义为表的长度。当n=0是称为空表，常常将非空的线性表(n0)记作：(a1,a2,an)。2. 按顺序存储方法存储的线性表称为顺序表，按链式存储的线性表称为链表。顺序表上实现的基本运算有：插入、删除。在顺序表做插入运算，平均要移动表中的一半结点。当表长n较大时，算法的效率相当低。虽然EI
5、S(n)中的n的系数较小，但就数量级而言，它仍然是线性阶的，因此算法的平均时间复杂度是0(n);在顺序表做删除运算，平均要移动表中约一半的结点，平均时间复杂度也是0(n)。3. 线性表中结点集合的元素是有限的，结点间的关系是一对一的4. 链表的每个结点只有一个链域的链表称为单链表。建立单链表有两种方法：头插法建表、尾插法建表。5. 在链表的开始结点之前附加一个结点，称为头结点，会带来以下两个优点：由于开始结点的位置被存放在头结点的指针域中，所以在链表的第一个位置上的操作就和在表的其它位置上操作一致，无须进行特殊处理；无论链表是否为空，其头指针是指向头结点的非空指针，因此空表和非空表的处理和非空
6、表的处理也就统一了。6. 查找运算分两种：按序号查找(链表不是随机存取结构)；按值查找7. 循环链表是一种首尾相接的链表。其特点是无须增加存储量，仅对表的链接方式稍作改变，即可使得表处理更加方便灵活。双链表若希望从表中快速确定一个结点的直接前趋，可以在单链表的每个结点里再增加一个指向其直接前趋的指针域prior。这们形成的链表中有两条方向不同的链，故称之为。和单链表类似，双链表一般也是由头指针head惟一确定的，增加头结点也能够使双链表上的某些运算变得方便，将头结点和尾结点链接起来也能构成循环链表，并称之为双向循环链表。顺序表和链表，它们各有所长。在实际应用中究竟选用哪一种存储结构呢？答：这要
7、根据具体问题的要求和性质来决定。通常从以下几个方面来考虑：基于空间的考虑；基于时间的考虑。存储密度是指结点数据本身所占的存储量和整个结点结构所占的存储量之比；显然，顺序表的存储密度为1,而链表的存储密度小于1。当线性表的长度变化不大，易于事先确定其大小时，为了节约存储空间，宜采用顺序表作为存储结构；顺序表是由向量实现的，它是一种随机存取结构，对表中任一结点都可在0(1)时间内直接地存取，而链表中的结点，需从头指针起顺着链扫描才能取得。因此，若线性表的操作主要是进行查找，很少做插入和删除操作时，采用顺序表做存储结构为宜；对于频繁进行插入和删除的线性表，宜采用链表做存储结构；若表的插入和删除主要发
8、生在表的首尾两端，则采用尾指针表示的单循环链表为宜。存储密度是指结点数据本身所占的存储量和整个结点结构所占的存储量之比。即：存储密度=(结点数据本身所占的存储量)/(结点结构所占的存储总量)。存储密度越大，存储空间的利用率就越高。显然，顺序表的存储密度为1，而链表的存储密度小于1。8. 顺序表相对于链表的优点有节省存储空间和随机存取。链表相对于顺序表的优点有插入和删除操作方便。9. 双链表中要删除已知结点*p，其时间复杂度为0(1)。10. 在循环链表中，可根据任一结点的地址遍历整个链表，而单链表中需知道头指针。第三章和队列1. 栈和队列是两种特殊的线性表，它们的逻辑结构和线性表相同，只是其运
9、算规则较线性表有更多的限制，故又称它们为运算受限的线性表。2. 栈是限制仅在表的一端进行插入和删除运算的线性表，通常称插入、删除的这一端为栈顶，另一端称为栈底。当表中没有元素时称为空栈。栈的基本运算有六种：InitStack(S)构造一个空栈S;StaclEmpty(S)判栈空。若S为空栈，则返回TRUE否则返回FALSEStackFull(S)判栈满。若S为满栈，则返回TRUE否则返回FALSE该运算只适用于栈的顺序存储结构；Push(S,x)进栈。若栈S不满，则将元素X插入S的栈顶；Pop(S)退栈。若栈S非空，则将S的栈顶元素删去并返回该元素；StackTop(S)取栈顶元素。若栈S非空
10、，则返回栈顶元素，但不改变栈的状态。3. 栈的顺序存储结构简称为顺序栈，它是运算受限的顺序表。4. 在顺序栈上实现的六种基本运算:5. 栈的链式存储结构称为链栈，它是运算受限的单链表，其插入和删除操作仅限制在表头位置上进行。6. 队列也是一种运算受限的线性表。队列也称作先进先出的线性表，简称为FIFO表。它只允许在表的一端进行插入，而在另一端进行删除。允许删除的一段称为队头，允许插入的一段称为队尾。队列的基本运算有六种：InitQueue(Q)置空队。构造一个空队列QQueueEmpty(Q判队空。若队列Q为空，则返回真值，否则返回假值。QueueFull(Q)判队满。若队列Q为满，则返回真值
11、，否则返回假值。此操作只适用于队列的顺序存储结构。EnQueue(Q,X)若队列Q非满，则将元素X插入Q的队尾。此操作简称入队。DeQueue(Q若队列Q非空，则删去的队头元素,并返回该元素。此操作简称出他。QueueFront(Q)若队列Q非空，则返回队头元素，但不改变队列Q的状态。7. 递归是指若在一个函数、过程或者数据结构定义的内部又直接(或间接)出现有定义本身的应用，则称它们是递归的，或者是递归定义的。10递归算法的设计一般有两步：将规模较大的原问题分解一个或多个规模更小、但具有类似于原问题特性的子问题，即较大的问题递归地用较小的子问题来描述，解原问题的方法同样可用来解这些子问题；确定
12、一个或多个无须分解、可直接求解的最小子问题。上述第一步称为递归步骤，第二步中所述的最小子问题称为递归的终止条件。第四章串1. 串是零个或多个字符组成的有限序列。一般记为S=a1a2an2. 将仅由一个或多个空格组成的串称为空白串；不包括任何字符的串称为空串。3. 串中任意个连续字符组成的子序列称为该串的子串，包含子串的串相应地称为主串。4. 通常在程序中使用的串可分为两种：串变量和串常量串的顺序存储结构称为顺序串。子串定位运算又称串的模式匹配或串匹配。在匹配中，一般将主串称为目标串，子串称为模式串。第五章多维数组和广义表1. 一般都是采用顺序存储的方法来表示数组。通常有两种顺序存储方法：行优先
13、顺序；列优先顺序。按上述两种方式顺序存储的数组，只要知道开始结点的存放地址（即基地址），维数和每维的上、下界，以及每个数组元素所占用的单元数，就可以将数组元素的存储地址表示为其下标的线性函数。2. 特殊矩阵是指非零元素或零元素的分布有一定规律的矩阵。有：对称矩阵；三角矩阵；对角矩阵。稀疏矩阵设矩阵Amn中有s个非零元素，若s远远小于矩阵元素的总数（即sm*n），则称A为稀疏矩阵。若将表示稀疏矩阵的非零元素的三元组按行优先（或列优先）的顺序排列（跳过零元素），则得到一个其结点均是三无组的线性表。将该线性表的顺序存储结构称为三元组表。3. 广义表（Lists又称列表）是线性表的推广。4. 一个表的
14、深度是指表展开后所含括号的层数，例如，表L、A、B、C的深度为分别为1、2、3、4表D的深度为。5. 通常把与树对应的广义表称为纯表，它限制了表中万分的共享和递归；把允许结点共享的表称为再入表；而把允许递归的表称为递归表。6. 广义表的两个特殊的基本运算：取表头head（LS）和取表尾tail（LS）。7. 值得注意的是广义表（）和（）不同。前者是长度为0的空表，对其不能做求表头和表尾的运算；而后者是长度为1的非空表（只不过该表中惟一的一个兀素是空表），对其可进行分解，得到的表头和表尾均是空表（）。第六章树1. 树(Tree)是n(n0)个结点的有限集T,T为空时称为空树，否则它满足如下两个条
15、件：有且仅有一个特定的称为根(Root)的结点；其余的结点可分为m(诈0)互不相交的子集T1、T2、Tm其中每个子集本身又是一棵树，并称其为根的子树(Subtree)。2. 一个结点拥有的子树数称为该结点的度。一棵树的度是指该树中结点的最大度数。度为零的结点称为叶子或终端结点。度不为零的结点称为分支结点或非终端结点，除根结点之外的分支结点统称为内部结点，根结点又称为开始结点。树中某个结点的子树之根称为该结点的孩子或儿子，相应地，该结点称为孩子的双亲或父亲。3. 森林是m(m0)棵互不相交的树的集合。树和森林的概念很相近，删去一棵树的根，就得到一个森林。反之，加上一个结点作树根，森林就变为一棵树
16、。4. 二叉树是n(n0)个结点的有限集，它或者是空集(n=0)，或者由一个根结点及两棵互不相交的、分别称作这个根的左子树和右子树的二叉树组成。二叉树具有以下几个重要性质：二叉树第I层上的结点数目最多为2i-1(i1);证明：可用数学归纳法证明(归纳基础：i=1时，有2i-仁20=1。因为第一层上只有一个根结点，所以命题成立。归纳假设：假设对所有的j(1ji)命题成立，即第j层上至多有2j-1个结点，证明j=i时命题亦成立。归纳步骤：根据归纳假设，第i-1层上至多有2i-2个结点。由于二叉树的每个结点至多有两个孩子，故第I层上结点数，至多是第i-1层上的最大结点数的2倍，即j=i时，该层上至多有2*2i
