本文内容总结于：《数据结构》C语言版|第2版
第一章：绪论
数据：是客观事物的符号表示，是所有能输入到计算机中并被计算机程序处理的符号的总称。
数据元素：是数据的基本单位，在计算机中通常作为一个整体进行考虑和处理。
数据项：是组成数据元素的、有独立含义的、不可分割的最小单位。
数据对象：是性质相同的数据元素的集合，是数据的一个子集。
数据结构：是相互之间存在一种或多种特定关系的数据元素的集合。
存储结构：数据对象在计算机中的存储表示称为数据的存储结构，也称物理结构。
存储结构有四种：顺序存储结构，链式存储结构，索引存储结构，散列存储结构。
- 顺序存储结构：顺序存储结构是借助元素在存储器的相对位置来表示数据元素之间的逻辑关系，通常借助程序设计语言的数组类型来描述。
- 链式存储机构：链式存储结构无需占用一整块存储空间。但为了表示节点之间的关系，需要给每个节点附加指针字段，用于存放后继元素的存储地址。所以链式存储结构通常借助于程序设计语言的指针类型来描述。
逻辑结构：数据的逻辑结构是从逻辑关系上描述数据，它与数据的存储无关，是独立于计算机的。因此，数据的逻辑结构可以看作是从具体问题抽象出来的数学模型。
逻辑结构有四种：集合结构，线性结构，树结构，图结构或网状结构。
- 集合结构：数据元素之间除了“属于同一集合”的关系外，别无其他关系。例如，确定一名学生是否为班级成员，只需将班级看做一个集合结构。
- 线性结构：数据元素之间存在一对一的关系。例如，将学生信息数据按照其入学报到的时间先后顺序进行排列，将组成一个线性结构。
- 树结构：数据元素之间存在一对多的关系。例如，在班级的管理体系中，班长管理多个组长，每位组长管理多名组员。从而行成树结构。
- 图结构或网状结构：数据元素之间存在多对多的关系。例如，多为同学之间的朋友关系，任何两位同学都可以是朋友，从而构成图状结构或者网状结构。
其中集合结构、树结构和图结构都属于非线性结构。
数据类型：数据类型是一个值的集合和定义在这个值集上的一组操作的总称。
抽象数据类型：一般指由用户定义的、表示应用问题的数学模型，以及定义在这个模型上的一组操作的总称。
具体包括三部分：数据对象、数据对象上关系的集合以及数据对象的基本操作的集合。
抽象数据类型：数据对象（D） 丨 数据关系（S） 丨 基本操作（P）
- S是D的关系集，P是D的基本操作。
一个算法必须满足的五个特性
有穷性、确定性、可行性、输入、输出。
一个算法的优劣应有：正确性、可读性、健壮性、高效性。
高效性：
- 时间：指算法设计合理，执行效率高，可以用时间复杂度来度量。
- 空间：指算法占用存储容量合理，可以用空间复杂度来度量。
第二章：线性表
线性表、栈、队列、串、数组都属于线性结构。
线性结构的基本特点：是除第一个元素无直接前驱，最后一个元素无直后继之外，其他每个数据元素都有一个前驱和后继。线性表是最基本且最常用的一种线性结构，同时也是其他数据结构的基础，尤其单链表，是贯穿整个数据结构课程的基本技术。
由（n≥0）个数据特性相同的元素构成的优先序列称为线性表。
线性表中元素的各位n（n≥0）定义为线性表的长度，n=0时为空表。
线性表的顺序表示指的是用一组地址连续的存储单元依次存储线性表的数据元素，这种表示也称作线性表的顺序存储结构或顺序映像。通常称这种存储结构的线性表为顺序表。其特点是，逻辑上相邻的数据元素，其物理次序也是相邻的。
假设线性表的每个元素需占用I个存储单元，并以所占的第一个单元的存储地址作为数据元素的存储起始位置。则线性表中第i+1个数据元素的存储位置LOC（ai+1）和第i个数据元素的存储位置LOC(ai)之间满足下列关系：LOC(ai+1)=LOC(ai)+l，一般来说，线性表的第i个数据元素ai的存储位置为：LOC(ai)=LOC(a1)+(i-1)xI。
顺序表按值查找算法的平均时间复杂度为O(n)。
线性表链式存储结构的特点是：用一组任意的存储单元存储线性表的数据元素(这组存储单元可以是连续的，也可以是不连续的)。因此，为了表示每个数据元素ai与其直接后继数据元素ai+l之间的逻辑关系，对数据元素ai来说，除了存储其本身的信息之外，还需存储一个指示其直接后继的信息(即直接后继的存储位置)。这两部分信息组成数据元素ai的存储映像，称为结点。它包括两个域：其中存储数据元素信息的域称为数据域；存储直接后继存储位置的域称为指针域。指针域中存储的信息称为指针或链。n个结点链结成一个链表，即为线性表的链式存储结构。又于此链表的每个结点中只包含一个指针域，故又称线性链表或单链表。
根据链表结点所含指针个数、指针指向和指针连接方式，可将链表分为单链表、循环链表、双向链表、二叉链表、十字链表、领链表、邻接多重表等。其中单链表、循环链表和双向链表用于实现线性表的链式存储结构，其他形式多用于实现树和图等非线性结构。
为了处理方便，在单链表的第一个结点之前附设一个结点，称之为头结点。
头结点其指针域指向首元结点。头结点的数据域可以不存储任何信息，也可以存储与数据元素类型相同的其他附加信息。例如，当数据元素为整数型时，头结点的数据域中可存放该线性表的长度。
头指针是指向链表中第一个结点的指针。若链表设有头结点，则头指针所指结点为线性表的头结点；若链表不设头结点，则头指针所指结点为该线性表的首元结点。
链表增加头结点的作用：便于首元结点的处理；便于空表和非空表的统一处理。
单链表是非随机存取的存储结构，要取得第i个数据必须从头指针出发顺链进行寻找，也称为顺序存取的存取结构。因此，其基本操作的实现不同于顺序表。
单链表取值算法的平均时间复杂度为O(n)。
※循环链表：是另一种形式的链式存储结构。
※小结：线性表的逻辑结构特性是指数据元素之间存在着线性关系，在计算机中表示这种关系的两类不同的存储结构是顺序存储结构（顺序表）和链式存在结构（链表）。
※小结：对于顺序表，元素存储的相邻位置反映出其逻辑上的线性关系，可借助数组来表示。给定数组的下标，便可以存取相应的元素，可称为随机存取结构。而对于链表，是依靠指针来反映其线性逻辑关系的，链表结点的存取都要从头指针开始，顺链而行，所以不属于随机存取结构，可称之为顺序存取结构。
对于非空的线性表或线性结构，其特点是：
- 存在唯一的一个被称作“第一个”的数据元素
- 存在唯一的一个被乘坐“最后一个”的数据元素
- 除第一个之外，结构中的每个数据元素均只有一个前驱。
- 除最后一个之外，结构中的每一个数据元素均只有一个后继。
第三章：栈和队列
栈是限定仅在表尾进行插入或删除操作的线性表。因此，对栈来说，表尾端有其特殊含义，称为栈顶，相应的，表头端称为栈底。不含元素的空表称为空栈。
和栈相反，队列是一种先进先出的线性表。它只允许在表的一端进行插入，而在另一端删除元素。这和日常生活中的排队是一致的，最早进入队列的元素最早离开。在队列中，允许插入的一端称为队尾，允许删除的一端则称为队头。
队空条件：Q.front==Q.rear
队满条件：(Q.rear+1)%MAXSIZE==Q.front
顺序栈是指利用顺序存储结构实现的栈，即利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，同时附设指针top指示栈顶元素在顺序栈中的位置。
顺序栈的初始化：
- 为顺序栈动态分配一个最大容量的MAXSIZE的数组空间，使base指向这段空间的基地址，即栈底。
- 栈顶指针top初始化为base，表示栈为空。
- stacksize置为栈的最大容量MAXSIZE。
顺序栈的入栈：
- 判断栈是否满，若满则返回ERROR。
- 将新元素压入栈顶，栈顶指针加1。
顺序栈的出栈：
- 判断栈是否空，若空则返回ERROR。
- 栈顶指针减1，栈顶元素出栈。
取栈顶元素：当栈非空时，此操作返回当前栈顶元素的值，栈顶指针保持不变。
队列的操作与栈的操作类似，不同的是，删除的是在表的头部（即队头）进行。
队列分配一个空间 插入队尾新元素 假溢出 真溢出【自查】
什么叫假溢出，怎么解决？
当元素被插入到数组中下标最大的位置上之后，队列的空间就用尽了。
解决：将顺序队列变为循环队列。
【问题】对于循环队列不能以头、尾指针的值是否相同来判别队列空间是“满”还是“空”。这种情况下，如何区别队满还是队空？
- 方法1：少用一个元素空间，即队列空间大小为m时，有m-1个元素就认为是队满。这样判断队空的条件不变，即当头、尾指针的值相同时，则认为队空；而当尾指针在循环意义上加1后是等于头指针，则认为队满。
- 方法2：另设一个标志位以区别队列是“空”还是“满”。参考课后题算法设计题七题。
栈、队列、线性表的差别：
- 栈是限定仅在表尾进行插入和删除，后进先出。
- 队列限定在一端插入另一端删除，先进先出。
- 线性表是随机存取。
重点 课后小结要看尤其是表3.3
第四章：串、数组和广义法
串（字符串）是由零个或多个字符组成的有限序列。
称两个串是相等的，当且仅当这两个串的值相等。也就是说，只有当两个串的长度相等， 并且各个对应位置的字符都相等时才相等。
空串和空格串的区别：空格串表示只含空格的串，空串表示所含字符数为0的串。
广义表：广义表就是线性表的推广，也称为列表。广泛的用于人工智能等领域的表处理语言LISP语言，把广义表作为基本的数据结构，就连程序也表示为一系列的广义表。
广义表与线性表的区别：
- 线性表：最简单，也是最常用的一种数据结构。
- 广义表：一种非线性的数据结构，是线性表的一种推广。
- 线性表要求是相同的元素类型，而广义表中的元素类型可以不同。
第五章：树和二叉树
树是n（n≥0）个结点的有限集，它或为空树（n=0）；或为非空树，对于非空树T；
- 有且仅有一个称之为根的结点；
- 除根结点以为的其余结点可分为m（n＞0）个互不相交的有限集T1,T2…,Tm，其中每一个集合本身又是一棵树，并且称之为根的子树。
结点的度：结点拥有的子树数称为结点的度。例如，A的度为3，C的度为1，F的度为0。
树的度：数的度是树内各结点度的最大值。
树的存储结构：双亲表示法，孩子表示法，孩子兄弟法。
二叉树是（n≥0）个结点所构成的集合，它或为空树（n=0）；或为非空树，对于非空树T；①有且仅有一个称之为根的结点；②除根结点以为的其余结点分为两个互不相交的子集T1和T2，分别称为T的左子树和右子树，且T1和T2本身又都是二叉树。
二叉树与树一样具有递归性质，二叉树与树的区别主要有以下两点；
- 二叉树每个结点至多只有两棵子树（即二叉树中不存在度大于2的结点）；
- 二叉树的子树有左右之分，其次序不能任意颠倒。
二叉树可以有五种基本形态，如下图：
二叉树具有下列重要特性：
- 性质1 在二叉树的第i层上至多有2^i-1个结点（i≥1）。
- 性质2 深度为k的二叉树至多有2^k-1个结点（k≥1）。
- 性质3 对任何一棵二叉树T，如果其终端结点数为n0，度为2的结点数为n2，则n0=n2+1.
满二叉树：深度为k且含有2^k-1个结点的二叉树。
完全二叉树：深度为k 的，有n个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应时，称之为完全二叉树。
完全二叉树的特点：
- 叶子结点只可能在层次最大的两层上出现；
- 对任一结点，若其右分支下的子孙的最大层次为l（小L），则其左分支下的子孙的最大层次必为l或l+1 。
在含有n个结点的二叉树链表中有n+1个空链域。
遍历二叉树：是指按某条搜索路径寻访树中每个结点，使得每个结点均被访问一次，而且仅被访问一次。
先序遍历二叉树的操作定义如下：
若二叉树为空，则空操作；否则①访问根结点；②先序遍历左子树；③先序遍历右子树。
中序遍历二叉树的操作定义如下：
若二叉树为空，则空操作；否则①中序遍历左子树；②访问根结点；③中序遍历右子树。
后序遍历二叉树的操作定义如下:
若二叉树为空，则空操作；否则①后序遍历左子树②后序遍历右子树③访问根结点。
了解线索二叉树的基本概念p128
了解 双亲表示法 孩子表示法 孩子兄弟法 p133
哈夫曼树：我们称判定过程最优的二叉树为哈夫曼树，又称最优二叉树，是一类带权路径长度最短的树，在实际中有广泛的用途。
路径： 树中一个结点到另一个结点之间的分支构成这两个结点之间的路径。
路径长度：路径上的分枝数目称作路径长度。
树的路径长度：从树根到每一个结点的路径长度之和。
树的带权路径长度：树中所有叶子结点的带权路径长度之和。
设某二叉树有n个带权值的叶子结点，则该二叉树的带权路径长度记为：
W为第k个叶子结点的权值；
L为第k个结点的路径长度。
哈夫曼树的构造过程步骤：
树和二叉树的区别与联系
- 性质不同：树是一种数据结构，二叉树每个结点至多有俩颗子树，二叉树子树有左右之分，其次序不能颠倒。
- 结点数目不同：树的每个结点有0个或多个子结点，二叉树的每个结点最多有俩个子树。
- 联系：树都可以用二叉链表作为存储结构，从物理结构来看，树和二叉树的二叉链表是相同的。
P145 小结 重点
第六章：图
邻接点：对于无向图G，如果图的边(v，v撇)∈E，则称顶点v和v撇互为邻接点，即v和v撇相邻接。边(v，v撇)依附于顶点v和v撇，或者说边(v，v撇)与顶点v和v撇相关联。
度、入度和出度：顶点v的度是指和v相关联的边的数目，记为TD(v)。
对于有向图，顶点v的度分为入度和出度。
- 入度是以顶点v为头的弧的数目，记作ID(v)；
- 出度是以顶点v为尾的弧的数目，记为OD(v)。
