第一章：数据结构包含：逻辑结构，数据的存储结构，对数据进行的操作。数据元素：相对独立的基本单位，即可简单也可复杂，简单的数据元素只有
一个数据项，数据项是数据的不可分割的最小单位。数据对象：性质相同的数据元素的集合。数据结构：相互存在一种或者多种特定关系的数据元素的
集合（集合，线性结构，树结构，图结构） 。顺序存储结构：数据元素按照逻辑顺序依次存放在存储器的一段连续存储单元中。链式存储结构：存储在
存储空间的任意位置上，包含一个数据域和至少一个指针域，要访问，必须从第一个元素开始查找。数据类型：一组值加一组操作。
第二章：线性表：有限多个性质相同的数据元素构成的一个序列，数据元素的个数就是长度。线性表的顺序存储结构：用一组地址连续的存储单元能随
机存取的结构。 链式存储结构：具有链式存储结构的线性表称为链表， 是用一组地址任意的存储单元来存线性表中的数据元素。 每个数据元素存储结构
包括数据元素信息域和地址域， 存放一个数据元素的存储结构称为结点， 每个结点只定义一个指针域， 存放的是当前结点的直接后记结点的地址 （直接
后继结点），线性表的最后一个结点指针域存放空（ 0，NULL）标志结束。不支持随机存取，访问必须从第一个结点开始，一次访问。双向链表：每个
结点设置两个方向的指针（直接前驱和直接后继） 。
第三章：栈：堆栈的简称，限定在表尾进行插入和删除的线性表。特点是后进先出。当栈定指针指向栈底时，为空栈。队列：限定只能在一端进行插入
和在另一端进行删除的线性表，进行插入的是队尾，删除的是队头。特点是先进先出。队列的链式结构：用一个链表依次存放从队头到队尾的所有的数
据元素。存放队头地址（队头指针）队尾地址（队尾指针） ，空链队列： 有头结点，空队列条件是头结点存放 0，无头结点为队头指针指向空。队列
的顺序存储结构： 用一组地址连续的存储空间依次存放从队头到队尾的所有数据元素， 再用队头指针和队尾指针记录队头和队尾的位置。 队头指针指向
队头元素前一个数组元素的位置，队尾始终指向队尾，当队尾和队头指向同一位置，空队列。入队和出队，队尾指针都会向数组元素下标的增加方向移
动，当队尾指针超出数组上界面无法进行操作（假溢出） ，解决方法是使用具有顺存储存结构的循环队列：将存放队列元素的数组首尾连接，形成一个
环形结构。
第四章：数组的存储结构：一般为顺序存储结构，依次将数组元素存放在一段连续的存储区域中。通常有两种存放方式： 1.以行序为主， 2.列序为主。
矩阵的压缩存储：对值相同的元素可以自分配一个存储空间， 0 不分配。对称的压缩存储：对于每一个位置对称的矩阵元素只分配一个存储单元。稀疏
矩阵：若一个矩阵存在大量的 0，就称为稀疏矩阵。稀疏矩阵的三元组表示若以顺序储存结构表示由非零元三元组构成的表，则得到稀疏矩阵的一种压
缩储存方式，三元组表。稀疏矩阵的十字链表表示：链式表，每一个结点除了表示存储非零元素的三元组以外，还设置两个指针，分别指向同一行的下
一个非零元素结点和同一列的下一个非零元素结点。
第五章：串：空串的长度为 0，空格串的字符为空格。串的顺序存储结构（串的主要存储结构） ：将字符串的所有字符依次存放在一段连续的存储单元
中。非紧缩存储（访问方便） ：以存储单元为单位依次存放所有字符。紧缩存储（节省空间） ：根据机器字的长度尽可能的将多个字符存放在一个字中。
静态数组： 表示串终结。动态数组：用 new 和 delete 动态分配空间和释放空间。串的链式存储结构：用一个线性表来一次存储串值。
第六章：广义表：在线性表中，每个数据元素都是结构上不能分割的原子元素，如果放宽这个限制，允许表中的数据元素既可以是数据元素又可以是原
子元素， 也可以是一个表， 这种数据结构就是广义表。 子表： 某个元素本身是表。 广义表的长度： 最外层元素的个数。 空表： 没有元素。 广义表的表尾：
将第一个元素除去之后剩下全部元素构成的表，广义表的表尾一定是广义表。层： （a,(b,(c,e))）a 和 (b,(c,e))第一层， b 和 (c,e)第二层。广义表的深度：广
义表的最大层数，其值与广义表书写形势中括号的最大嵌套层数相同。
第七章：树 : 树是由 n（n>=0）个结点组成的有限集，若 n=0，则为空树， n>0,则树满足：有且仅有一个根节点；其他的结点划分为 m 个互不相交的
有限集，每个有限集本身是一棵树，称为根的子树。基本术语：结点：存放数据元素的逻辑单元。分支：节点之间的二元关系。结点的度：结点拥有的
子树棵数。叶子的结点：度为 0 的结点。分支的结点：度不为 0 的结点。树的度：树内各结点度的最大值。结点的层次：根为第一层，对其他任何结
点，若其父亲是 k 层结点，它就是 K+1层。树的深度 (高度 )：树中结点的最大层次。有序数：任意一个结点的各棵子树从左到右是有序的，其次序不能
任意颠倒。森林： m 棵互不相交树的集合。二叉树的定义：一种度小于或等于 2 的有序树。特点是树的每一个结点最多有两棵子树，且子树有左右之
分，不能任意颠倒。满二叉树：一棵二叉树所有的结点都有非空的左子树和右子树，且所有的叶子结点都位于二叉树的最下面一层。完全二叉树：只有
最下面两层结点的度可以小于 2，且最下面一层的结点都集中在该层最左边的位置上。二叉树的性质： 1.第 i 层上最多有 2 的 i-1 次方个结点。 2.深度为
k 的二叉树最多有 2 的 k 次方减 1 个结点。 3.若叶子结点数为 n,度为 2 的节点数为 m,则 n=m+1.具有 n 个结点的完全二叉树的深度为 log 以 2 为底， n 的
对数再加上 1.二叉树的顺序存储结构： 将一棵完全二叉树的全部结点按层次从上到下， 每层从左到右， 依次存放在一组地址连续的存储单元中。对于一
般的二叉树，可以增加一些不存在的虚节点变成二叉树。链式存储结构：二叉树一般采用链式存储方式存放，每一个树结点对应一个链结点，每个链结
点除了存放数据元素以外，还要根据需要定义若干指针，分别存放当前结点的左孩子，右孩子，双亲结点地址。定义 lchild 和 rchild 指针指向当前结点
的左右孩子，称为二叉链表，再定义一个 parent, 称为三叉链表。二叉树的遍历：按照某种搜索方式，访问二叉树中的每个结点，且每个结点只访问一
次。访问还可以修改结点额的值，输出结点的内容。遍历方式：先序，中序，后序。先序遍历二叉树：若二叉树为空，则空操作；否则访问根结点，先
序遍历根结点的左子树，先序变了根结点的右子树。中序遍历二叉树：若 ,, 中序遍历根节点的左子树，访问根结点，中序遍历根节点的右子树。后序
遍历二叉树：若 ,, 后序遍历根结点的左子树，后序遍历根结点的右子树，访问根结点。树的存储结构：孩子兄弟表示法：每个树结点构成了链表中的
一个链结点，每个链结点设置了三个域，一个是数据域，还有两个指针域，分别表示当前结点第一个孩子的地址和下一个兄弟的地址。任何一棵树，可
以找到一棵唯一的二叉树，他们的存储结构完全相同。树，森林与二叉树的转换：任何一棵二叉树可以找到一棵唯一对应的二叉树，他们的存储结构完
全相同， 只是解释不同。 树的根结点对应着二叉树的根结点， 树上某结点的第一个孩子对应二叉树的上是相同的结点的左孩子， 树上的某结点的下一个
兄弟结点在对应二叉树上是用同结点的右孩子。任何一棵与树对应的二叉树，其根结点的右子树必然是空树。哈夫曼树：路径长度：从一个结点向下到
达某子孙结点的分支，成称为这两个结点之间的路径，分支的数目称为路径长度。结点的权：赋予给结点的一个数值。结点的带权路径长度：从树根到
该结点的路径长度与结点权的乘积。树的带权路径长度：树中所有叶子结点的带权路径长度之和。现在有 N 个数值，将他们作为 n 结点的权，以这 n
个结点为叶子结点构造一个二叉树，其中带权路径长度最短的那颗二叉树为哈夫曼树（最优二叉树） 。要使二叉树的带权路径长度达到最小，权值大的
叶子结点尽量离根近些。
第八章： 图是由若干个顶点和若干条边构成的数据结构。 顶点是实际对象的抽象， 边是对象之间的关系的抽象。有向图： 若图中带表一条边的偶对 <x,y>
是有序的，则图中的边具有方向性，可以将其称为又向边（弧） ，常将顶点 x 到顶点 y 的弧表示为 <x.y>，其中顶点 x 称为弧尾， y 为弧头。完全图：任
