考点大纲
23考研 408新增考点：
并查集，红黑树
第一章
数据结构基本概念
数据元素（data element）是数据的基本单位，也称结点（node）或记录（record），在计算机程序中通常将其作为一个整体进行考虑和处理。一个数据元素可由若干个数据项组成。
数据项（data item）是数据结构中讨论的最小单位，是数据记录中最基本的，不可分的数据单位，也称域（field）。
数据对象（Data Object）是性质相同的数据元素的集合，是数据的一个子集。
数据结构（Data Structure）是指相互之间存在一种或多种特定关系的数据对象。
抽象数据类型
定义抽象类型复数
物理存储结构
数据的物理结构包括数据元素的表示和数据元素间关系的表示。
顺序存储结构和链式存储结构适用在内存结构中，索引存储结构和散列存储（哈希存储）结构适用在外存与内存交互结构中。
顺序存储——数组
数据的物理结构包括数据元素的表示和数据元素之间的关系的表示。
在计算机中用一组地址连续的存储单元依次存储线性表的各个数据元素,称作线性表的顺序存储结构。
把逻辑上相邻的数据元素，存储为在物理上也相邻的存储单元中。
特点：
1、随机存取表中元素。
2、插入和删除操作需要移动元素。
链式存储——链表
在计算机中用一组任意的存储单元存储线性表的数据元素(这组存储单元可以是连续的,也可以是不连续的)。它不要求逻辑上相邻的元素在物理位置上也相邻.因此它没有顺序存储结构所具有的弱点,但也同时失去了顺序表可随机存取的优点。
特点：
1、用指针来表示数据元素之间的逻辑关系。
2、顺序存储结构的存储密度小 (每个节点都由数据域和指针域组成，所以相同空间内假设全存满的话顺序比链式存储更多)。
3、逻辑上相邻的节点物理上不必相邻。
4、插入、删除灵活 (不必移动节点，只要改变节点中的指针)。
5、查找结点时链式存储要比顺序存储慢。
6、每个结点是由数据域和指针域组成。
索引存储结构
除建立存储结点信息外，还建立附加的索引表来标识结点的地址。索引表由若干索引项组成。
特点：
索引存储结构是用结点的索引号来确定结点存储地址，其优点是检索速度快，缺点是增加了附加的索引表,会占用较多的存储空间。
散列存储（哈希存储）结构
散列存储，又称hash存储，是一种力图将数据元素的存储位置与关键码之间建立确定对应关系的查找技术。
特点：
散列是数组存储方式的一种发展，相比数组，散列的数据访问速度要高于数组，因为可以依据存储数据的部分内容找到数据在数组中的存储位置，进而能够快速实现数据的访问，理想的散列访问速度是非常迅速的，而不像在数组中的遍历过程，采用存储数组中内容的部分元素作为映射函数的输入，映射函数的输出就是存储数据的位置，这样的访问速度就省去了遍历数组的实现，因此时间复杂度可以认为为O(1)，而数组遍历的时间复杂度为O(n)。
注意：栈是逻辑结构，而顺序栈和链栈是存储结构。
逻辑结构和存储结构的区分
先说结论：线性表、有序表是逻辑结构；顺序表，链表是存储结构。
逻辑结构与存储结构的判定方法：当一个结构(如数组、链表、树、图)，在逻辑结构中只有一种定义，而在物理结构中却有两种或多种定义，那么这个结构就属于逻辑结构；相反，当此结构在原有基础上加上了某种限定词(如二叉树->线索二叉树)，使得其在物理结构中只有一种定义，那么这个结构就属于物理（存储）结构，或称为数据结构；
栈在逻辑结构中只能属于线性结构，而在物理结构中它可以使用顺序存储（数组），也可以使用链式存储（链表），所以说栈是一种逻辑结构。
二叉树既可以顺序存储又可链式存储，故可以得到二叉树是一种逻辑结构。但是线索二叉树是二叉树加上限定词线索后的链表结构（不能用顺序存储），也就是说，线索二叉树在计算机内部的只有一种存储结构，所以线索二叉树是物理结构。
逻辑结构和存储结构的区别点在于：数据的逻辑结构是独立于在计算机中的存储结构的，数据的存储方式有多种不同的选择。例如栈是一种逻辑结构，它可以用顺序存储也可以用链式存储。
而数据结构是既可以描述逻辑结构又可以描述存储结构和数据运算，必须包含以上三种元素。所以像顺序表、哈希表、单链表都是数据结构。
算法的基本概念
算法的设计需要达到的目标（勿与算法的五个特性搞混）：
- 正确性：算法能够按照规定的功能和性能正确地执行，这是最基本并且最重要的标准！
- 可使用性：也叫用户友好性，算法能够方便地使用
- 可读性：算法是易于理解的，这要求算法在逻辑上是清晰的、结构化的
- 健壮性：算法具有容错性，即异常处理，能够检测不合理的数据，保证程序不发生异常中断等
- 高效率低存储：效率是指算法的执行时间；存储是指算法执行所用的最大存储空间。算法应该在保证前面的条件下，执行时间尽可能低存储空间尽可能小
算法的时间复杂度
算法的时间复杂度取决于算问题的规模（主要）和待处理数据的状态。
所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界。
口诀：常对幂指阶
数量级的递增
算法的空间复杂度
算法原地工作指算法所需辅助空间是常量。
