《数据结构复习重点》word版

1、.数据结构 复习重点谁让我找到你们了.第一章1.数据是信息的载体,它可以被计算机识别、存储和加工处理。2.数据元素是数据的根本单位。有些情况下，数据元素也称为元素、结点、顶点、记录。3.数据构造指的是数据之间的互相关系，即数据的组织形式。一般包括三个方面的内容：数据元素之间的逻辑关系，也称为数据的逻辑构造；数据元素及其关系在计算机存储器内的表示，称为数据的存储构造；数据的运算，即对数据施加的操作。4.数据类型是一个值的集合以及在这些值上定义的一组操作的总称。按"值"是否可分解，可将数据类型划分为两类：原子类型，其值不可分解；构造类型，其值可分解为假设干个成分。5.抽象数据类

2、型是指抽象数据的组织和与之相关的操作。可以看作是数据的逻辑构造及其在逻辑构造上定义的操作。6.数据的逻辑构造简称为数据构造。数据的逻辑构造可分为两大类：线性构造的逻辑特征是假设构造是非空集，那么有且仅有一个开场结点和一个终端结点，并且所有结点都最多只有一个直接前趋和一个直接后继；非线性构造的逻辑特征是一个结点可能有多个直接前趋和直接后继。7.数据存储构造可用四种根本的存储方法表示：顺序存储方法该方法是把逻辑上相邻的结点存储在物理位置上相邻的存储单元里，结点间的逻辑关系由存储单元的邻接关系来表达。由此得到的存储表示称为顺序存储构造；链接存储方法该方法不要求逻辑上相邻的结点在物理位置上亦相邻，结点

3、间的逻辑关系是由附加的指针字段表示的。由此得到的存储表示称为链式存储构造；索引存储方法该方法通常是在存储结点信息的同时，还建立附加的索引表；散列存储方法该方法的根本思想是根据结点的关键字直接计算出该结点的存储地址。8.非形式地说，算法是任意一个良定义的计算过程，它以一个或多个值作为输入，并产生一个或多个值为输出。因此，一个算法是一系列将输入转换为输出的计算步骤。9.求解同一计算问题可能有许多不同的算法，终究如何来评价这些算法的好坏以便从中选出较好的算法呢?选用的算法首先应该是"正确"的。此外，主要考虑三点：执行算法所消耗的时间；执行算法所消耗的存储空间，其中主要考虑辅助存储

4、空间；算法应易于理解，易于编码，易于调试等等。10.性构造反映结点的逻辑关系是一对一的,非线性构造反映结点间的逻辑关系是多对多的。11.数据的运算最常用的五种，分别是查找、插入、删除、更新、和排序。12.一个算法的效率可分为时间效率和空间效率。第二章线性表1.线性表是由nn0个数据元素结点a1,a2,an组成的有限序列。其中数据元素的个数n定义为表的长度。当n=0是称为空表，常常将非空的线性表n 0记作：a1,a2,an。2.按顺序存储方法存储的线性表称为顺序表，按链式存储的线性表称为链表。3.顺序表上实现的根本运算有：插入、删除。在顺序表做插入运算，平均要挪动表中的一半结点。当表长n较大时，

5、算法的效率相当低。虽然EISn中的n的系数较小，但就数量级而言，它仍然是线性阶的，因此算法的平均时间复杂度是0n；在顺序表做删除运算，平均要挪动表中约一半的结点，平均时间复杂度也是0n。4.线性表中结点集合的元素是有限的，结点间的关系是一对一的。5.链表的每个结点只有一个链域的链表称为单链表。建立单链表有两种方法：头插法建表、尾插法建表。6.在链表的开场结点之前附加一个结点，称为头结点，会带来以下两个优点：由于开场结点的位置被存放在头结点的指针域中，所以在链表的第一个位置上的操作就和在表的其它位置上操作一致，无须进展特殊处理；无论链表是否为空，其头指针是指向头结点的非空指针，因此空表和非空表的

6、处理和非空表的处理也就统一了。7.查找运算分两种：按序号查找链表不是随机存取构造；按值查找。8.循环链表是一种首尾相接的链表。其特点是无须增加存储量，仅对表的链接方式稍作改变，即可使得表处理更加方便灵敏。9.双链表假设希望从表中快速确定一个结点的直接前趋，可以在单链表的每个结点里再增加一个指向其直接前趋的指针域prior。这们形成的链表中有两条方向不同的链，故称之为。和单链表类似，双链表一般也是由头指针head惟一确定的，增加头结点也可以使双链表上的某些运算变得方便，将头结点和尾结点链接起来也能构成循环链表，并称之为双向循环链表。10.顺序表和链表，它们各有所长。在实际应用中终究选用哪一种存储

7、构造呢?答：这要根据详细问题的要求和性质来决定。通常从以下几个方面来考虑：基于空间的考虑；基于时间的考虑。存储密度是指结点数据本身所占的存储量和整个结点构造所占的存储量之比；显然，顺序表的存储密度为1，而链表的存储密度小于1。当线性表的长度变化不大，易于事先确定其大小时，为了节约存储空间，宜采用顺序表作为存储构造；顺序表是由向量实现的，它是一种随机存取构造，对表中任一结点都可在01时间内直接地存取，而链表中的结点，需从头指针起顺着链扫描才能获得。因此，假设线性表的操作主要是进展查找，很少做插入和删除操作时，采用顺序表做存储构造为宜；对于频繁进展插入和删除的线性表，宜采用链表做存储构造；假设表的

8、插入和删除主要发生在表的首尾两端，那么采用尾指针表示的单循环链表为宜。11.存储密度是指结点数据本身所占的存储量和整个结点构造所占的存储量之比。即：存储密度=结点数据本身所占的存储量/结点构造所占的存储总量。存储密度越大，存储空间的利用率就越高。显然，顺序表的存储密度为1，而链表的存储密度小于1。12.顺序表相对于链表的优点有节省存储空间和随机存取。链表相对于顺序表的优点有插入和删除操作方便。13.双链表中要删除结点*p，其时间复杂度为01。14.在循环链表中，可根据任一结点的地址遍历整个链表，而单链表中需知道头指针。第三章和队列1.栈和队列是两种特殊的线性表，它们的逻辑构造和线性表一样，只是

9、其运算规那么较线性表有更多的限制，故又称它们为运算受限的线性表。2.栈是限制仅在表的一端进展插入和删除运算的线性表，通常称插入、删除的这一端为栈顶，另一端称为栈底。当表中没有元素时称为空栈。3.栈的根本运算有六种：InitStackS构造一个空栈S；StaclEmptyS判栈空。假设S为空栈，那么返回TRUE，否那么返回FALSE；StackFullS判栈满。假设S为满栈，那么返回TRUE，否那么返回FALSE。该运算只适用于栈的顺序存储构造；PushS,x进栈。假设栈S不满，那么将元素X插入S的栈顶；PopS退栈。假设栈S非空，那么将S的栈顶元素删去并返回该元素；StackTopS取栈顶元素

10、。假设栈S非空，那么返回栈顶元素，但不改变栈的状态。4.栈的顺序存储构造简称为顺序栈，它是运算受限的顺序表。5.在顺序栈上实现的六种根本运算：6.栈的链式存储构造称为链栈，它是运算受限的单链表，其插入和删除操作仅限制在表头位置上进展。7.队列也是一种运算受限的线性表。队列也称作先进先出的线性表，简称为FIFO表。它只允许在表的一端进展插入，而在另一端进展删除。允许删除的一段称为队头，允许插入的一段称为队尾。8.队列的根本运算有六种：InitQueueQ置空队。构造一个空队列Q。QueueEmptyQ判队空。假设队列Q为空，那么返回真值，否那么返回假值。QueueFullQ判队满。假设队列Q为满

11、，那么返回真值，否那么返回假值。此操作只适用于队列的顺序存储构造。EnQueueQ,X假设队列Q非满，那么将元素X插入Q的队尾。此操作简称入队。DeQueueQ假设队列Q非空，那么删去的队头元素，并返回该元素。此操作简称出他。QueueFrontQ假设队列Q非空，那么返回队头元素，但不改变队列Q的状态。9.递归是指假设在一个函数、过程或者数据构造定义的内部又直接或间接出现有定义本身的应用，那么称它们是递归的，或者是递归定义的。10递归算法的设计一般有两步：将规模较大的原问题分解一个或多个规模更小、但具有类似于原问题特性的子问题，即较大的问题递归地用较小的子问题来描绘，解原问题的方法同样可用来解

12、这些子问题；确定一个或多个无须分解、可直接求解的最小子问题。上述第一步称为递归步骤，第二步中所述的最小子问题称为递归的终止条件。第四章串1.串是零个或多个字符组成的有限序列。一般记为S="a1a2an"2.将仅由一个或多个空格组成的串称为空白串；不包括任何字符的串称为空串。3.串中任意个连续字符组成的子序列称为该串的子串，包含子串的串相应地称为主串。4.通常在程序中使用的串可分为两种：串变量和串常量。5.串的顺序存储构造称为顺序串。子串定位运算又称串的形式匹配或串匹配。在匹配中，一般将主串称为目的串，子串称为形式串。第五章多维数组和广义表1.一般都是采用顺序存储的方法来表示

13、数组。通常有两种顺序存储方法：行优先顺序；列优先顺序。按上述两种方式顺序存储的数组，只要知道开场结点的存放地址即基地址，维数和每维的上、下界，以及每个数组元素所占用的单元数，就可以将数组元素的存储地址表示为其下标的线性函数。2.特殊矩阵是指非零元素或零元素的分布有一定规律的矩阵。有：对称矩阵；三角矩阵；对角矩阵。3.稀疏矩阵设矩阵Amn中有s个非零元素，假设s远远小于矩阵元素的总数即s mn，那么称A为稀疏矩阵。4.假设将表示稀疏矩阵的非零元素的三元组按行优先或列优先的顺序排列跳过零元素，那么得到一个其结点均是三无组的线性表。将该线性表的顺序存储构造称为三元组表。5.广义表Lists又称列表是

14、线性表的推广。6.一个表的"深度"是指表展开后所含括号的层数，例如，表L、A、B、C的深度为分别为1、2、3、4表D的深度为。7.通常把与树对应的广义表称为纯表，它限制了表中万分的共享和递归；把允许结点共享的表称为再入表；而把允许递归的表称为递归表。8.广义表的两个特殊的根本运算：取表头headLS和取表尾tailLS。9.值得注意的是广义表和不同。前者是长度为0的空表，对其不能做求表头和表尾的运算；而后者是长度为1的非空表只不过该表中惟一的一个元素是空表，对其可进展分解，得到的表头和表尾均是空表。第六章树1.树Tree是nn0个结点的有限集T，T为空时称为空树，否那么它满

15、足如下两个条件：有且仅有一个特定的称为根Root的结点；其余的结点可分为mm0互不相交的子集T1、T2、Tm，其中每个子集本身又是一棵树，并称其为根的子树Subtree。2.一个结点拥有的子树数称为该结点的度。一棵树的度是指该树中结点的最大度数。度为零的结点称为叶子或终端结点。度不为零的结点称为分支结点或非终端结点，除根结点之外的分支结点统称为内部结点，根结点又称为开场结点。树中某个结点的子树之根称为该结点的孩子或儿子，相应地，该结点称为孩子的双亲或父亲。3.森林是mm0棵互不相交的树的集合。树和森林的概念很相近，删去一棵树的根，就得到一个森林。反之，加上一个结点作树根，森林就变为一棵树。4.

16、二叉树是nn0个结点的有限集，它或者是空集n=0，或者由一个根结点及两棵互不相交的、分别称作这个根的左子树和右子树的二叉树组成。5.二叉树具有以下几个重要性质：二叉树第I层上的结点数目最多为2i-1i1；证明：可用数学归纳法证明归纳根底：i=1时，有2i-1=20=1。因为第一层上只有一个根结点，所以命题成立。归纳假设：假设对所有的j1j i命题成立，即第j层上至多有2j-1个结点，证明j=i时命题亦成立。归纳步骤：根据归纳假设，第i-1层上至多有2i-2个结点。由于二叉树的每个结点至多有两个孩子，故第I层上结点数，至多是第i-1层上的最大结点数的2倍，即j=i时,该层上至多有2*2i-1=2

17、j-1个结点，故命题成立。深度为k的二叉树至多有2k-1个对点k1；证明：在肯有一样深度的二叉树中，仅当每一层都含有最大结点数时其树中结点数最多。因此利用性质1可得，深度为k的二叉树的结点数至多为20+21+2k-1=2k-1故命题正确。在任意一棵二叉树中，假设终端结点的个数为n0，度为2的结点数为n2，那么n0=n2+1；证明：因为二叉树中所有结点的度数均不大于2，所以结点总数记为n应等于0度结点数，1度结点记为n1和2度结点数之和：n=n0+n1+n2,另一方面，1度结点有一个孩子，2度结点有两个孩子，故二叉树中孩子结点的总数是n1+2n2，但树中只有根结点不是任何结点的孩子，故二叉树中的

18、结点叫数又可表示为：n=n1+2n2+1具有n个结点的完全二叉树的深度为lgn+1或lgn+1。证明：设所求完全二叉树的深度为k，由完全二叉树的定义知道，它的前k-1层是深度为k-1的满二叉树，一共有2k-1-1个结点。由于完全二叉树深度为k，故第k层上还有假设干个结点，因此该完全二叉树的结点个数n 2k-1-1。另一方面，由性质2知道n2k-1，即：2k-1-1 n2k-1由此可推出：2k-1n 2k，取对数后有：k-1lgn k，因为k-1和k是相邻的两个整数，故有k-1=lgn，由此即得：k=lgn+1 6.树、森林到二叉树的转换：在所有兄弟结点之间加一连线；对每个结点，除了保存与其长子

19、的连线外，去掉该结点与其它孩子的连线。7.森林的两种遍历方法：前序遍历森林，假设森林非空，那么：访问森林中第一棵树的根结点；前序遍历第一棵树中根结点的各子树所构成的森林；前序遍历除第一棵树外其它树构成的森林。后序遍历森林，假设森林非空，那么：后序遍历森林中第一棵树的根结点的各子树所构成的森林；访问第一棵树的根结点；后序遍历除第一棵树外其它树构成的森林。8.树的途径长度是从树根到树中每一结点的途径长度之和。第七章图1.对图进得深度优先遍历时，按访问顶点的先后次序得到的顶点序列称为该图的深度优先遍历序列，或DFS序列。2.深度优先搜索的特点是尽可能先对纵深方向进展搜索。3.广度优先搜索的特点是尽可

20、能先对横向进展搜索。4.广度优先遍历图所得的顶点序列，定义为图的广度优先遍历序列，或BFS序列。5.由深度优先搜索得到的生成树称为深度优先生成树，或DFS生成树。6.对一个有向无环图G进展拓扑排序，是将G中所有顶点排成一个线性序列，使得对图中任意一对顶点u和v，假设u，vEG，那么u在线性序列中出如今v之前。通常将这样的线性序列称为满足拓扑次序的序列，简称拓扑序列。第八章排序1.排序就是要整理文件中的记录，使之按关键字递增或递减次序排列起来。2.排序方法可以按照不同的原那么加以分类：在排序过程中，假设整个文件都是放在内存中处理，排序时不涉及数据的内、外存交换，那么称之为内部排序；反之，假设排序

21、过程中要进展数据的内、外存交换，那么称之为外部排序。3.内部排序方法可以分为五类：插入排序、选择排序、交换排序、归并排序和分配排序。4.插入排序的根本思想是：每次将一个待排序的记录，按其关键字大小插入到前面已经排好序的子文件中的适当位置，直到全部记录插入完成为止。5.快速排序采用了一种分冶的策略，通常称其为分冶法。分冶法的根本思想是：将原问题分解为假设干个规模更小但构造与原问题相似的子问题；递归地解这些子问题，然后将这些子问题的解组合为原问题的解。6.对于n个记录的集合进展冒泡排序，在最坏情况下所需要的时间是On2；对于n个记录的集合进展归并排序，所需要的附加空间是On。7.堆排序是一树形选择

22、排序，它的特点是，在排序过程中，将R看成是一棵完全二叉树的顺序存储构造，利用完全二叉树中双亲结点和孩子结点之间的内在关系，在当前无序区中选择关键字最大的记录。8.在堆排序、快速排序和归并排序中，假设只从存储空间考虑，那么应首先选取堆排序方法，其次选取快速排序方法，最后选取归并排序方法；假设只从排序结果的稳定性考虑，那么应选取归并排序方法；假设只从平均情况下最快考虑，那么应选取快速排序方法；假设只从最坏情况下最快并且要节省内存考虑，那么应选取堆排序方法。9.大多数排序算法都有两个根本的操作：比较两个关键字的大小和改变向记录的指针或挪动记录本身。第九章查找1.查找的定义是：给定一个值K，在含有n个

23、结点的表中找出关键字等于给定值K的结点。2.假设在查找的同时对表做修改操作，那么相应的表称之为动态查找表，否那么称之为静态查找表。3.和排序类似，查找也有内查找和外查找之分。假设整个查找过程都在内存进展，那么称之为内查找；反之，假设查找过程中需要访问外存，那么称之为外查找。4.二分查找又称折半查找。5.二叉排序树又称二叉查找搜索树，其定义为：二叉排序树或者是空树，或者是满足如下性质的二叉树。假设经的左子树非空，那么左子树上所有结点的值均小于根结点的值；假设它的右子树非空，那么右子树上所有结点的值均大于根结点的值；左、右子树本身又各是一棵二叉排序树。6.平衡二叉树是指树中任一结点的左右子树的高度

24、大致一样。假设任一结点的左右子树的高度均一样，那么二叉树是完全平衡的。平衡的二叉排序树是指满足BST性质的平衡二叉树。第十章文件1.文件是性质一样的记录的集合。2.数据项有时也称为字段，或者称为属性。其值能惟一标识一个记录的数据项或数据项的组合称为主关键安项，其它不能惟一标识一个记录的数据项那么称为次关键字项，主关键字项的值称为主关键字。3.文件上的操作主要有两类：检索和维护。4.检索就是在文件中查找满足给定条件的记录，它既可以按记录的逻辑号查找，也可以按关键字查找。5.文件的根本组织方式有四种：顺序组织、索引组织、散列组织和链组织。文件组织的各种方式往往是这四种根本方式的结合。6.磁道是盘片

25、上同心圆，同一盘组上半径一样的磁道合在一起称为一个柱面。7.顺序文件是指按记录进入文件的先后顺序存放、其逻辑顺序和物理顺序一致的文件。假设顺序文件中的记录按其主关键字有序，那么称此顺序文件为顺序有序文件；否那么称为顺序无序文件。8.索引表是用索引的方法组织文件时，通常是在文件本身之外，另外建立一张表，它指明逻辑记录和物理记录之间的一一对应关系，这张表就叫做索引表，它和主文件一起构成的文件称作索引文件。9.索引表中的每一项称作索引项。10.对于索引非顺序文凭，由于主文件中记录是无序的，那么为每个记录建立一个索引项，这样建立的索引表称为稠密索引。11.散列文件是利用散列存储方式组织的文件，称为直接

26、存取文件。12.对于文件来说，磁盘上的文件记录通常是成组存放的，假设干个记录组成一个存储单位，在散列文件中，这个存储单位叫做桶。13.多重表文件是将索引方法和链接方法相结合的一种组织方式，它对每个需要查询的次着急字建立一个索引，同时将具有一样次关键字的记录链接成一个链表，并将此链表的头指针、链表长度及次关键字，儿为索引表的一个索引项。例题：完成以下中序遍历二叉树的算法，注意在遍历中只有一个栈，而不用任何其他变量。#define max 100 typedef struct tnodestruct tnode*lchild,*rchild：tnode；typedef struct stacktn

27、ode*elemmax；int top；stack；void indrdertnode*btstack s；s.top=0；s.elems.top+=bt dowhiles.elems.top-1！=nulls.elems.top+=s.elems.top-1！lchild ifs.top 1s.top-printfs.top-1-data；s.elems.top-1=elems.top-1-vchildwhile！s.top=1&&s.elems.top-1=nulls.top=02.以下算法的功能是求出指定结点在给定的二叉排序树中所在的层次。Void levelBSTree

28、 root.p；int level=0；if！Root；return0；elselevel+；whileroot-key！=p-key；ifroot-key p-key；root=root-lchid：else root=root-rchild；level+；returnlevel；3.t利用一维数组int an可以对n个整数进展排列，其中一种排列算法的处理思想是将n个整数分别作为数组a的个元素的值，每次即第I次从元素aan-1中找出最小的一个元素akI kn,然后将a与k换位。这样反n次完成排序。请编写实现上述算法的过程，并分析完成排序所需要的次数。解：void sortint anint

29、I,j,t,min,minpos；forI=o；I n；I+min=a：minpos=1；forj=I+1；I n；j+ifajminmin=a；minpos=j；ifminpos！=It=a；t=a；a=aminposa=aminpos；aminpos=t：4.设给定的散列存储空间为：H0.m,每个H单元可存放一记录，选取的散列函数为Hr_KEY，其中R_KEY为记录关键字，解决冲突的方法为线性探测法，试编写将某记录R入表H中的算法。解：void buildhashkeytype R.key,int I,int j,int nforI=0；I n；I+j=HR.key；ifHJ=r_key；

30、elsedoj=j+1%m+1whileHj；Hj=r_key；5试写出二分查找的递归算法。解：int binsrchint low,int hig,keytype kint mid；iflow higreturn0；elsemid=low+hig/2；ifk=rmid.keyreturnmidifk rmid.key rerurnbinsrchmid+1.hig.k；ifk rmid.keyreturnbinsrchlow.mid-1,k；6.写一个遍历B-树的算法，使输出的关键字序列递增有序。算法中的读盘操作可假写为DiskRead.解：void inorderBtree tint I：ift：