数据结构知识点总结
发布者：何夕2020-04-21
1.数据结构的基础知识
第一章 什么是数据结构1.1 基本概念和术语1.2 数据的逻辑结构和物理结构 1.1 基本概念和术语1.数据（data）： 是对客观事物的符号的表示，是所有能输入到计算机中并被计算机程序处理的符号的总称。
2.数据元素（data element）： 是数据的基本单位，在计算机程序中通常作为一个整体来处理。一个数据元素由多个 数据项（data item）组成，数据 项是数据不可分割的最小单位。
3.数据结构（data structure）： 是相互之间存在一种或多种特定关系的数据元素的集合。数据结构是一个二元组，记为： data_structure=(D,S).其中D为数据元素的集合，S是D上关系的集合。
数据元素相互之间的关系称为结构（structure）。根据数据元素之间关系的不同特性，通常由下列四类基本结构： （1）集合：数据元素间的关系是同属一个集合。
（图1） (2)线性结构：数据元素间存在一对一的关系。（图2） (3)树形结构：结构中的元素间的关系是一对多的关系。
（图3） (4)图（网）状结构：结构中的元素间的关系是多对多的关系。（图4） 1.2 数据的逻辑结构和物理结构逻辑结构：数据元素之间存在的关系（逻辑关系）叫数据的逻辑结构。
物理结构：数据结构在计算机中的表示（映象）叫数据的物理结构。 一种逻辑结构可映象成不同的存储结构：顺序存储结构和非顺序存储结构（链式存储结构和散列结构）。
2.数据结构知识归纳
第一章：数据结构概述 一、什么是数据结构 1、作者开篇谈到： 一般来说解决一个具体的问题时，大致需要经过下列几个步骤：首先要从具体的问题抽象出一个适当的数学模型，然后设计一个解此数学模型的算法，最后编写出程序代码，进行测试、调整直至得到最终的解决方案。
总结为：现实中具体的问题—>数学模型—>算法程序—>解决方案 动作为：抽象提取、设计编码、测试调整 2、数学角度阐述： 寻求数学模型的实质是分析问题，从中提取操作的对象，并找出这些操作对象之间含有的关系，然后用数学的语言加以描述。 3、定义数据结构： 描述这类非数值计算问题的数学模型不再是数学方程，而是诸如表、树和图之类的数据结构，因此，简单来说，数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间关系和操作等的学科，用一句话来说就是，数据结构是相互之间存在一种或多种特定关系的数据元素的集合。
研究对象：1、集合2、线性结构3、树形结构4、图状结构（网状结构） 结构分类：1、数据的逻辑结构2、数据的物理结构（存储结构） 关系表示：1、顺序映像2、非顺序映像，两者分别对应为顺序存储结构、链式存储结构 二、算法和算法分析 1、算法的五个特性：有穷性、确定性、可行性、输入和输出 2、算法设计的要求：正确性、可读性、健壮性以及效率与低存储量需求 3、算法的度量：时间复杂度和空间复杂度 总结：编写代码设计算法时候首先先考虑算法的正确性，确保程序能够满足要求，在正确性的前提下再进一步考虑算法的可读性、健壮性、拓展性以及算法的效率等。 第二章：线性表 一、线性表的定义 线性结构的特点是：在数据元素的非空有限集中（1）存在唯一的一个被称做“第一个”的数据元素；（2）存在唯一的一个被称做“最后一个”的数据元素；（3）除第一个之外，集合中每个数据元素均只有一个前驱；（4）除最后一个元素之外，集合中每个数据元素均只有一个后继。
线性表是最常用并且最简单的一种数据结构，简单来说，一个线性表是n个数据元素的有限序列。至于每个数据元素的具体含义，在不同的情况下各不相同，既可以是一个数也可以是一个符号等等。
二、线性表的操作 线性表是一个相当灵活的数据结构，它的长度可根据需要增长或者缩短，即对线性表的数据元素不但可以进行访问，还可以进行插入和删除等操作。线性表存储方式有两种，顺序存储和链式存储，下面通过代码进行简单模拟操作。
第三章：栈和队列 栈和队列是两种重要的线性结构，从数据结构的角度看，栈和队列也是线性表，其特殊性在于栈和队列的基本操作是线性表操作的子集，它们是操作受限制的线性表，因此可以称为限定性的数据结构。 一、栈的定义 栈是限定在表尾进行插入或删除操作的线性表，栈的特定是先进后出。
栈的存储方式有两种，一种是顺序栈另外一种是链式栈，下面只通过代码简单模拟栈的操作。 二、栈的应用 栈的应用主要有数制转换、括号匹配的检验、迷宫问题求解以及表达式求值。
另外栈递归实现的经典例子有八皇后问题、汉诺塔问题等。 三、队列的定义 队列和栈有点不同，队列是一种先进先出得线性表，它只能够在表的一端进行插入另外一头进行删除操作。
队列在程序设计中比较常见的例子是操作系统中的作业排队。双端队列、循环队列有时间再进一步演进，暂时先了解些基本概念。
第四章：串 一、串的定义 计算机上的非数值处理的对象基本上都是字符串数据。串是由零个或多个字符组成的有限序列。
串中字符的数目成为字符串的长度，零个字符的串成为空串。串的模式匹配算法经典的是KMP算法。
第五章：数组和广义表 一、数组和广义表定义 数组是读者已经很熟悉的一种数据类型，几乎所有的程序设计语言都把数组类型设为固有的类型。数组的应用中涉及到一个比较重要的数学知识，矩阵的压缩存储问题。
广义表是线性表的推广，在java开发中好像用得不多，有时间再进一步学习。 第六章：树和二叉树 一、树的定义和基本操作 1、树的特点 树是一个结点n的有限集，在任意一颗树非空树中：1、有且只有一个根结点，2、当n>1时，其余结点分为m(m>0)个互不相交的有限集，其中每个集合本身又是一棵树，叫做根的子树。
关键词组：有限集、唯一性、对称性、递归性。 基本术语：结点、度、叶子、分支结点、孩子、双亲、兄弟、层次以及深度等。
基本操作：构造初始化树、取得左子树或右子树、插入结点、删除结点、树的遍历等等。 2、线性结构VS树结构 线性结构是一个“序列”，元素之间存在的是“一对一”的关系，而树是一个层次结构，元素之间存在的是“一对多”的关系。
二、二叉树的定义 1、二叉树的特点 每个结点至多只有二棵子树（即二叉树中不存在度大于2的结点），并且二叉树的子树有左右之分，其次序不能颠倒。 关键词组：对称、次序 2、二叉树的具体实例 满二叉树、完全二叉树、平衡二叉树等，具体区别参考书籍教材详解。
3、二叉树的存储结构 主要分为两种方式，一类是顺序结构（可使用一组地址连续的存储单元依次自上而下、自左至右存储完全二叉。
3.数据结构的考点是什么
在计算机考研专业基础课统考科目中，一共考查数据结构、操作系统、计算机组成原理、计算机网络四门课程，满分为150分，其中数据结构占45分。
一、考查目标 （1）理解数据结构的基本概念，掌握数据的逻辑结构、存储结构及其差异，以及各种基本操作的实现。 （2）掌握基本的数据处理原理和方法的基础上，能够对算法进行设计与分析。
（3）能够选择合适的数据结构和方法进行问题求解。二、知识点解析1.线性表 线性表是一种最简单的数据结构，在线性表方面，主要考查线性表的定义和基本操作、线性表的实现。
在线性表实现方面，要掌握的是线性表的存储结构，包括顺序存储结构和链式存储结构，特别是链式存储结构，是考查的重点。另外，还要掌握线性表的基本应用。
2.栈、队列和数组 栈和队列是两种特殊的线性表，在这方面，要求我们掌握栈和队列的基本概念，以及他们之间的区别。对于栈和队列的存储结构（包括顺序存储结构、链式存储结构）要有较深的理解，对于栈和队列的应用，例如，排队问题、子程序调用问题、表达式问题等，要搞清楚。
一维数组属于线性表范畴，但多维数组不属于线性表。在这方面，主要掌握数组的存储结构，例如按行优先、按列优先等，某个元素存在的地址是什么。
对于特殊矩阵（二维数组）的压缩存储原理也要搞清楚。3、树与二叉树 二叉树和树是两种不同的概念，这一点是必须要搞清楚的。
在这个部分，我们要掌握树的定义、二叉树的定义及主要特征（特殊的二叉树、二叉树的性质）。在二叉树的顺序存储结构和链式存储结构方面，特别是链式存储结构，因为很多应用都是建立在链式存储基础上，例如，二叉树的遍历（前序遍历、中序遍历、后序遍历）就是一种典型的应用。
在特殊的二叉树中，完全二叉树的概念是必须要搞清楚的，其次，线索二叉树的基本概念和构造、二叉排序树、平衡二叉树的基本概念和应用，特别是二叉排序树的基本性质和特点要能很好地理解。 多棵独立的树就组成了森林，树的存储结构和遍历、森林的遍历、树和二叉树的转换、森林和二叉树的转换等知识，也要有了了解。
最后就是树的应用，通常会作为综合应用类试题出现，包括等价类问题、哈夫曼（Huffman）树和哈夫曼编码等。 /sjjg/200808051202101241.htm记得采纳啊。
4.数据结构的知识
数据结构关键是含义，而到真正的代码实现时自然有各种根据实际需要的不同。
也就是说：学数据结构，不是学代码，而是学一种结构思想，就是数据可以这么存，那么取这样一种认识。而编码实现，是具体问题要求的结果。
不能死学。旧思想上来说：表就是各个元素间没有具体关系的一种数据组织方式，即集合；队列就是先进先出的一种线形数据组织方式，它更注重定义的是数据的操作方式，而不是结构。
栈是一种先进后出的线形数据组织方式，也是重在操作方式。具体实现，各种结构都有线性实现，即用数组实现，和链表实现，即用节点加指针实现两种实现方式。
你说到的上面各种定义的不同只是具体实现上的，不属于数据结构讨论的内容，就是说，他们不重要。对于这门课来说，他们都一样。
关键是学操作方法，即：怎么存，怎么取，怎么用。
5.数据结构的考试重点
这是我们老师要求的重点，即考点。
打印出来，背一下就行了，准过！第一章：绪论1.1：数据结构课程的任务是：讨论数据的各种逻辑结构、在计算机中的存储结构以及各种操作的算法设计。1.2：数据：是客观描述事物的数字、字符以及所有的能输入到计算机中并能被计算机接收的各种集合的统称。
数据元素：表示一个事物的一组数据称作是一个数据元素，是数据的基本单位。数据项：是数据元素中有独立含义的、不可分割的最小标识单位。
数据结构概念包含三个方面：数据的逻辑结构、数据的存储结构的数据的操作。1.3数据的逻辑结构指数据元素之间的逻辑关系，用一个数据元素的集合定义在此集合上的若干关系来表示，数据结构可以分为三种：线性结构、树结构和图。
1.4：数据元素及其关系在计算机中的存储表示称为数据的存储结构，也称为物理结构。 数据的存储结构基本形式有两种：顺序存储结构和链式存储结构。
2.1：算法：一个算法是一个有穷规则的集合，其规则确定一个解决某一特定类型问题的操作序列。算法规则需满足以下五个特性：输入——算法有零个或多个输入数据。
输出——算法有一个或多个输出数据，与输入数据有某种特定关系。 有穷性——算法必须在执行又穷步之后结束。
确定性——算法的每个步骤必须含义明确，无二义性。 可行性——算法的每步操作必须是基本的，它们的原则上都能够精确地进行，用笔和纸做有穷次就可以完成。
有穷性和可行性是算法最重要的两个特征。2.2：算法与数据结构：算法建立数据结构之上，对数据结构的操作需用算法来描述。
算法设计依赖数据的逻辑结构，算法实现依赖数据结构的存储结构。2.3：算法的设计应满足五个目标：正确性：算法应确切的满足应用问题的需求，这是算法设计的基本目标。
健壮性：即使输入数据不合适，算法也能做出适当的处理，不会导致不可控结 高时间效率：算法的执行时间越短，时间效率越高。 果。
高空间效率：算法执行时占用的存储空间越少，空间效率越高。 可读性：算法的可读性有利于人们对算法的理解。
2.4：度量算法的时间效率，时间复杂度，（课本39页）。2.5：递归定义：即用一个概念本身直接或间接地定义它自己。
递归定义有两个条件：至少有一条初始定义是非递归的，如1!=1. 由已知函数值逐步递推计算出未知函数值，如用（n-1）！定义n。 第二章：线性表1.1线性表：线性表是由n(n>=0)个类型相同的数据元素a0,a1,a2，…an-1，组成的有限序列，记作： LinearList = (a0,a1,a2，…an-1)其中，元素ai可以是整数、浮点数、字符、也可以是对象。
n是线性表的元素个数，成为线性表长度。若n=0，则LinearList为空表。
若n>0，则a0没有前驱元素，an-1没有后继元素，ai(0 线性表的数据元素数据同一种数据类型，设每个元素占用c字节，a0的存储地址为Loc(a0)，则ai的存储地址Loc(ai)为：Loc(ai) = Loc(a0)+ i*c 数组是顺序存储的随机存储结构，它占用一组连续的存储单元，通过下标识别元素，元素地址是下标的线性函数。1.3：顺序表的插入和删除操作要移动数据元素。 平均移动次数是 属数据表长度的一半。（课本第50页）1.4：线性表的链式存储是用若干地址分散的存储单元存储数据元素，逻辑上相邻的数据元素在物理位置上不一定相邻，必须采用附加信息表示数据元素之间的顺序关系。 它有两个域组成：数据域和地址域。通常成为节点。 （课本第55页及56页）1.5单链表（课本56页）单链表的遍历：Node head = q； }单链表的删除操作：头删除：head = head.next； 中间/尾删除：if(p.next!=null){ p.next = p.next.next；} 循环单链表：如果单链表最后一个节点的next链保存单链表的头指针head值，则该单链表成为环形结构，称为循环单链表。（课本67）若rear是单链表的尾指针，则执行（rear.next=head；）语句，使单链表成为一条循环单链表。 当head.next==head时，循环单链表为空。1.6：双链表结构：双链表的每个结点有两个链域，分别指向它的前驱和后继结点， 当head.next==null时，双链表为空。 设p指向双链表中非两端的某个结点，则成立下列关系：p=p.next.prev=p.prev.next。双链表的插入和删除：1）插入 2）删除q=new DlinkNode(x); p.prev.next = p.next;q.prev=p.prev;q.next =p; if(p.next=null){p.prev.next = q;p.prev=q; (p.next).prev = p.prev；}循环双链表：当head.next==head且head.prev==head时，循环双链表为空。 第三章：栈和队列1。.。 第一章 数据结构基本概念1、基本概念：理解什么是数据、数据对象、数据元素、数据结构、数据的逻辑结构与物理结构、逻辑结构与物理结构间的关系。 2、面向对象概念：理解什么是数据类型、抽象数据类型、数据抽象和信息隐蔽原则。了解什么是面向对象。 由于目前关于这个问题有许多说法，我们采用了一种最流行的说法，即Coad与Yourdon 给出的定义：面向对象 = 对象 + 类 + 继承 + 通信。要点：·抽象数据类型的封装性·面向对象系统结构的稳定性·面向对象方法着眼点在于应用问题所涉及的对象3、数据结构的抽象层次：理解用对象类表示的各种数据结构4、算法与算法分析：理解算法的定义、算法的特性、算法的时间代价、算法的空间代价。 要点：·算法与程序的不同之处需要从算法的特性来解释·算法的正确性是最主要的要求·算法的可读性是必须考虑的·程序的程序步数的计算与算法的事前估计·程序的时间代价是指算法的渐进时间复杂性度量第二章 数组1、作为抽象数据类型的数组：数组的定义、数组的按行顺序存储与按列顺序存储 要点：·数组元素的存放地址计算2、顺序表：顺序表的定义、搜索、插入与删除要点：·顺序表搜索算法、平均比较次数的计算·插入与删除算法、平均移动次数的计算3、多项式：多项式的定义4、字符串：字符串的定义及其操作的实现要点：·串重载操作的定义与实现第三章 链接表1、单链表：单链表定义、相应操作的实现、单链表的游标类。要点：·单链表的两种定义方式（复合方式与嵌套方式）·单链表的搜索算法与插入、删除算法·单链表的递归与迭代算法 2、循环链表：单链表与循环链表的异同3、双向链表：双向链表的搜索、插入与删除算法、链表带表头结点的优点4、多项式的链接表示第四章 栈与队列1、栈：栈的特性、栈的基本运算要点：·栈的数组实现、栈的链表实现·栈满及栈空条件、抽象数据类型中的先决条件与后置条件2、栈的应用：用后缀表示计算表达式，中缀表示改后缀表示3、队列：队列的特性、队列的基本运算要点：·队列的数组实现：循环队列中队头与队尾指针的表示，队满及队空条件·队列的链表实现：链式队列中的队头与队尾指针的表示、4、双向队列：双向队列的插入与删除算法5、优先级队列：优先级队列的插入与删除算法第五章 递归与广义表 1、递归：递归的定义、递归的数据结构、递归问题用递归过程求解要点：·链表是递归的数据结构，可用递归过程求解有关链表的问题2、递归实现时栈的应用要点：·递归的分层（树形）表示：递归树·递归深度（递归树的深度）与递归工作栈的关系·单向递归与尾递归的迭代实现3、广义表：广义表定义、广义表长度、广义表深度、广义表表头、广义表表尾要点：·用图形表示广义表的存储结构·广义表的递归算法第六章 树与森林1、树：树的定义、树的基本运算要点：·树的分层定义是递归的·树中结点个数与高度的关系2、二叉树：二叉树定义、二叉树的基本运算要点：·二叉树性质、二叉树中结点个数与高度的关系、不同种类的二叉树棵数·完全二叉树的顺序存储、完全二叉树的双亲、子女和兄弟的位置·二叉树的前序·中序·后序·层次遍历·前序·中序·后序的线索化二叉树、前驱与后继的查找方法3、霍夫曼树：霍夫曼树的构造方法、霍夫曼编码、带权路径长度的计算4、树的存储：树的广义表表示、树的双亲表示、树与二叉树的对应关系、树的先根·中根·后根·层次遍历。 5、堆：堆的定义、堆的插入与删除算法要点：·形成堆时用到的向下调整算法及形成堆时比较次数的上界估计·堆插入时用到的向上调整算法第七章 集合与搜索1、集合的概念：集合的基本运算、集合的存储表示要点：·用位数组表示集合时集合基本运算的实现·用有序链表表示集合时集合基本运算的实现2、并查集：并查集定义、并查集的三种基本运算的实现3、基本搜索方法 要点：·对一般表的顺序搜索算法（包括有监视哨和没有监视哨）·对有序顺序表的顺序搜索算法、用判定树（即扩充二叉搜索树）描述搜索，以及平均搜索长度（成功与不成功）的计算。·对有序顺序表的折半搜索算法、用判定树（即扩充二叉搜索树）描述搜索，以及平均搜索长度（成功与不成功）的计算。 4、二叉搜索树：要点：·动态搜索树与静态搜索树的特性·二叉搜索树的定义、二叉搜索树上的搜索算法、二叉搜索树搜索时的平均搜索长度（成功与不成功）的计算。·AVL树结点上的平衡因子、AVL树的平衡旋转方法·高度为h的AVL树上的最少结点个数与最多结点个数· AVL树的搜索方法、插入与删除方法第八章 图1、图：图的定义与图的存储表示 要点：·邻接矩阵表示（通常是稀疏矩阵）·邻接表与逆邻接表表示·邻接多重表（十字链表）表示2、深度优先遍历与广度优先遍历要点：·生成树与生成树林的定义·深度优先搜索是个递归的过程，而广度优先搜索是个非递归的过程·为防止重复访问已经访问过的顶点，需要设置一个访问标志数组visited3、图的连通性要点：·深度优先搜索可以遍历一个连通分量上的所有顶点·对非连通图进行遍历，可以建。 第一章 什么是数据结构 1.1 基本概念和术语 1.2 数据的逻辑结构和物理结构 1.1 基本概念和术语 1.数据（data）: 是对客观事物的符号的表示，是所有能输入到计算机中并被计算机程序处理的符号的总称。 2.数据元素（data element）: 是数据的基本单位，在计算机程序中通常作为一个整体来处理。一个数据元素由多个 数据项（data item）组成，数据 项是数据不可分割的最小单位。 3.数据结构（data structure）: 是相互之间存在一种或多种特定关系的数据元素的集合。数据结构是一个二元组，记为： data_structure=(D,S).其中D为数据元素的集合，S是D上关系的集合。 数据元素相互之间的关系称为结构（structure）。根据数据元素之间关系的不同特性，通常由下列四类基本结构： (1)集合：数据元素间的关系是同属一个集合。（图1） (2)线性结构：数据元素间存在一对一的关系。（图2） (3)树形结构：结构中的元素间的关系是一对多的关系。（图3） (4)图（网）状结构：结构中的元素间的关系是多对多的关系。（图4） 1.2 数据的逻辑结构和物理结构 逻辑结构：数据元素之间存在的关系（逻辑关系）叫数据的逻辑结构。 物理结构：数据结构在计算机中的表示（映象）叫数据的物理结构。 一种逻辑结构可映象成不同的存储结构：顺序存储结构和非顺序存储结构（链式存储结构和散列结构）。6.数据结构的复习重点
7.数据结构的基础知识
