数据结构复习

《数据结构复习》由会员分享，可在线阅读，更多相关《数据结构复习（10页珍藏版）》请在装配图网上搜索。

1、第一章、1、数据的概念数据是信息的载体，是描述客观事物的数、字符、以及所有能输入到计算机中，被计算 机程序识别和处理的符号的集合。数值性数据（如int、float、double）非数值性数据（如N、0、I、R）2数据结构的概念：由某一数据元素的集合以及该集合中所有数据元素之间的关系组成。记为：Data_Structure = D, R其中，D是某一数据元素的集合，R是该集合中所有数据元素之间的关系的有限集 合。3、数据结构的分类线性结构线性表非线性结构层次结构群结构根据对线性结构中数据元素存取方法的不同，又可以分为：直接存取结构（如数组，文件）顺序存取结构（如栈、队列和优先级队列）字典结构一一

2、通过关键码（Key ）进行索引，我们可设定数据元素中的某一数据项或某 一组合数据项为关键码，如学生记录可用学号作为key4、数据结构涉及的三个方面：数据的运算，即对数据元素施加的操作。数据的逻辑结构数据的存储结构是指数据应该如何在计算机中存放，是数据逻辑结构的物理存储方式，是属于具体实现 的视图，是面向计算机的。四种基本的存储方法：顺序存储表示：该方法把逻辑上相邻的元素存放到物理位置上相邻的存储单元中；链接存储表示：该方法不要求逻辑上相邻的元素在物理位置上也相邻；索引存储表示：该方法在存储元素信息的同时，还建立附加的索引表。索引表中每一项 称为索引项，索引项的一般形式是：（关键码，地址）；散列

3、存储表示：根据结点的关键码通过一个函数计算直接得到该结点的存储地址。5、数据类型数据类型是一组性质相同的值的集合，以及定义于这个值集合上的一组操作的总称.6、线性表数据类型的两种表示方式基于数组的顺序表示和基于链表的链接表示7、抽象数据类型的概念由用户定义，用以表示应用问题的数据模型，是将数据结构作为一个软件构建的实现, 由基本的数据类型组成，并包括一组相关的服务(或称操作)抽象数据类型的的特征是使用与实现相分离，信息隐蔽和数据封装，8、类的特征信息隐蔽和数据封装，使用与实现相分离。9、自然数的抽象数据类型定义ADT NaturalNumber isobjects: 一个整数的有序子集合，它开

4、始于0, 结束于机器能表示的最大整数(MaxInt)。Function:对于所有的 x, y NaturalNumber;False, True Boolean, +、-、V、=、=等都是可用的服务。Zero( ) : NaturalNumber 返回自然数 0面向对象面向对象=对象+类+继承+消息通信10、对象在应用问题中出现的各种实体、事件、规格说明等，由一组属性值和在这组值上的一组 服务(或称操作)构成类(class)，实例(instance)具有相同属性和服务的对象归于同一类，形成类类中的对象为该类的实例11、继承(公有继承public、私有继承private、保护继承protecte

5、d)补充：(1) 静态分配，系统资源不足会提示，知道原因；(2)动态分配，程序忘记释放，会出现内存漏洞， 静态分配是编译器自己管理的；(2) 、类模板模板是将程序中的数据类型参数化，使得它能够处理某个范围内的数据类型，而不必为 每种可能的数据类型都建立一个实例；模板分为函数模板和类模板两种；12、算法的概念一个有穷的指令集，这些指令为解决某一特定任务规定了一个运算序列13、算法的的特征输入有0个或多个输入输出 有一个或多个输出(处理结果) 确定性每步定义都是确切、无歧义的 有穷性算法应在执彳丁有穷步后结束 能行性每一条运算应足够基本14、算法的性能标准正确性、；要求算法能正确地执行预定的功能和

6、性能要求。 可使用性：界面(UI)友好，完备的用户文档 可读性：注释效率：主要指算法执行时计算机资源的消耗，包括存储和运行时间的开销，前者叫算法的空 间代价，后者叫做算法的时间代价健壮性：容错性(详细记录，不放过每个错误)简单性：便于用户编写、分析和调试，最简单的算法不一定是最有效的，即可能需要占用较 长的运算时间和较多的内存空间15、算法的后期测试算法效率的度量分为事前估计和后期测试；16、算法的事前估计算法的复杂性的度量属于事前估计，可分为空间复杂度和时间复杂度。时间复杂度：是指当问题的规模以某种单位从1增加到n时，解决这个问题的算法在执 行时所耗费的时间也以某种单位由1增加到T(n)，则

7、称此算法的时间复杂度为T(n)。空间复杂度：是指当问题的规模以某种单位从1增加到n时，解决这个问题的算法在执 行时所占用的存储空间也以某种单位由1增加到S(n)，则称此算法的空间复杂度为S(n)；17、大O渐进表示若存在两个正的常数c和nO,对于任意的n= n0，都有T(n)v=c*f(n),则称该算法的 时间增长率在O(f(n)中，记为T(n)=O(f(n)。第二章、线性表1、线性表的概念线性表是n （三0）个数据元素的有限序列，记为：L =（al, a2, ，an）L是表名，ai是表中数据元素，n是表长度线性表的第一个表项称为表头，最后一个表项称为表尾；2、线性表的特点线性表是一个有限的序

8、列，每两个相邻表项之间都有直接前驱和后继关系；除第一个元素外，其他每一个元素有一个且仅有一个直接前驱；除最后一个元素外，其它每 一个元素有一个且仅有一个直接后继。直接前驱和直接后继描述了结点之间的逻辑关系（即邻接关系）。注：线性表的存储表示有两种：顺序存储方式和链表存储方式；顺序表的定义和特点定义:把线性表中的所有表项按照其逻辑顺序依次存储到从计算机存储中指定位置开始的一 块连续的存储空间中。特点所有元素的逻辑先后顺序与其物理存放顺序一致；（逻辑结构&存储结构）对顺序表中的所有项，既可以进行顺序访问，也可以进行随机访问；3、顺序表的优缺点优点：无需为表示结点间的逻辑关系而增加额外的存储空间，存

9、储利用率高； 可以方便地随机存取表中的任一结点，存取速度快。缺点：表中插入新元素或删除无用元素时，为了保持其他元素的相对次序不变，平均需要移动 一半元素；存储空间分配问题（表长超出预先分配空间容易造成溢出）；利用数组或顺序表方式来组织数据结构：优点：存储利用率高；存储速度快缺点：元素个数动态增长；插入删除需多次移动；n个长度变化的有序表，最大可能长度会 大量浪费空间链表：适用于插入或删除频繁，存储空间需求不定的情形4、单链表的概念单链表的一个存储结点（node）有两个域：一个线性表（a1,a2,an ）的单链表结构: 特点：结点的逻辑顺序与物理顺序可以不一致表可扩充 单链表的特点实现单链表的插

10、入和删除算法，不需要移动元素，只需修改结点指针，比顺序表方便。 情况复杂，要专门讨论空表和在表头插入的特殊情形。寻找插入或删除位置只能沿着链顺序检测。第三章栈和队列1、栈栈可定义为只允许在表的末端进行插入和删除的线性表。允许插入和删除的一端称为栈顶(top)，另一端称为栈底(bottom)特点后进先出(LIFO)2、表达式中缀表达式a + b * ( c - d ) - e / f后缀表达式a b c d - * + e f / -前缀表达式-+ a * b - c d / e f3、利用栈将中缀表示转换为后缀表示4、递归与递归过程递归：若一个对象部分地包含它自己，或用它自己给自己定义，则称这

11、个对象是递归的； 递归过程：若一个过程直接地或间接地调用自己，则称这个过程是递归过程。5、递归工作栈与递归工作记录在每次递归过程调用时，必须做参数保存、参数传递等工作。利用一个“递归工作栈” 来进行处理的。每层递归调用所需保存的信息构成一个递归工作记录。(1) 返回地址：上一层中本次调用自己的语句的后继指令处;(2) 在本次调用时，为与形参结合的实参创建副本；(3) 本层的局部变量值。2-递归工作桟与递归工作i垠柱毎坎赛归过程调用时，必烦锻靠数保存、靠数倍递辱工作 -制用一牛策邃归工作ST来进軒趾理的.皐层递归调用所需保存的信息枸成一牛递归工作记录-工作醫返回地址参数的副本空间局部变量0)个元

12、素组成的有限非空集合，称为顶点集合。E = (vi, vj) I vi, vj V, 1Wi, jWn是n-1个序对的集合，称为边集合，E中的元素(vi, vj)称 为边或分支。2有根树一棵有根树T,简称为树，它是n 三0)个结点的有限集合。当n = 0时，T称 为空树；否则，T是非空树，记作：， rTi，,T2，：.Tm ,r是一个特定的称为根(root)的结点，它只有直接后继，但没有直接前驱；根以外的其他结点划分为m (m0)个互不相交的有限集合T1, T2, , Tm,每个集合又是一棵树，并且称之为根的子树。每棵子树的根结点有且仅有一个直接前驱，但可以有0个或多个直接后继。子女：若结点的

13、子树非空，结点子树的根即为该结点的子女。双亲：若结点有子女，该结点是子女双亲。兄弟：同一结点的子女互称为兄弟。度：结点的子女个数即为该结点的度；树中各个结点的度的最大值称为树的度。1 层B) (c(V)2 层(e) Qfj Qg) (h) (jj Qj3层分支结点：度不为0的结点即为分支结点，亦称为非终端结点。 叶结点：度为0的结点即为叶结点，亦称为终端结点。祖先：某结点到根结点的路径上的各个结点都是该结点的祖先。“子孙：某结点的所有下属结点，都是该结点的子孙。结点的层次：规定根结点在第一层，其子女结点的层次等于它的层次加一。以下类推。结点 所处的层次亦称为结点的深度。树的深度：结点的深度即为

14、结点的层次；离根最远结点的层次即为树的深度。树的高度：叶结点的高度为1,非叶结点的高度等于它的子女结点高度的最大值加一这样可 定义树的高度等于根结点的高度。高度与深度计算的方向不同，但数值相等。有序树：树中结点的各棵子树T0, T1, 是有次序的，即为有序树。 无序树：树中结点的各棵子树之间的次序是不重要的，可以互相交换位置。 森林：森林是m (m三0)棵树的集合。二、二叉树的定义二叉树 一棵二叉树是结点的一个有限集合，该集合或者为空，或者是由一个根结点加 上两棵分别称为左子树和右子树的、互不相交的二叉树组成。二、森林与二叉树的转换p2251、将一般树转化为二叉树表示就是用树的子女-兄弟表示来

15、存储树的结构。2、森林与二叉树表示的转换可以借助树的二叉树表示来实现。三、路径长度(Path Length) p226路径(path)从树中一个结点到另一个结点之间的分支构成该两结点之间的路径。路径长度(Pathlength)是指路径上的分支条数。树的路径长度从树的根结点到每一个结点的路径长度之和。 从树的根结点到达树中每一结点有且仅有一条路径。一、填空栈顶、栈尾、队头、队尾数据结构、线性表、顺序表、栈、二叉树、空间复杂度、时间复杂度二、字符串、树、二叉树三、简答题四、算法分析五、程序完善题插入、删除进队、出队进栈、出栈数的高度、父结点前、中、后序遍历六、程序编写题二叉树（前、中、后序遍历）访问二叉树的左、右子树的语句