数据结构第一章绪论
1、数据结构=逻辑结构+存储结构+操作
2、数据的基本单位：数据元素
3、数据元素的最小单位：数据项
4、在数据库中：数据元素为行，数据项为列（简称行为元素，列为项）
5、数据元素的集合称为：数据对象
6、数据类型是 （3种）：原子类型、结构类型、抽象数据类型
7、抽象数据类型包含：数据对象、数据对象上的关系集合、以及数据对象的基本操作
抽象数据类型与已有的数据类型（如float、int）有什么区别？ 二者无区别，只是float、int是已实现的类型
定义格式：ADT抽象数据类型名{
数据对象的定义：
数据关系的定义：
基本操作的定义：}
8、逻辑结构是（4种2大类）
2大类：线性和非线性结构
分为4种：线性结构、集合、树、图
9、存储结构是（4种）优缺点有哪些：顺序存储、链式存储、索引存储、散列存储
10、如何解决一个问题：先画关系而后选存储方式
11、栈是限制了插入删除点的线性表，只是逻辑结构，与存储结构无关
12、举例说明，相同的逻辑结构，不同的存储方式在相同的操作下，其运算效率不同
线性表的顺序存储和链式存储：插入，删除操作
13、如何定义一个结构是逻辑结构还是物理结构
当一个结构，如数组、链表、树、图，在逻辑结构中只有一种定义，而在物理结构中却有两种选择，那么这个结构就属于逻辑结构；
相反，当此结构在原有基础上加上了某种限定，使得其在物理结构中只有一种定义，那么这个结构就属于物理（存储）结构；
14、如何判断数据结构不同：
看如何定义，如果是名字不同：比如栈和队列，逻辑结构都是线性表，存储结构都可以是顺序或者链表
如果是分类不同：比如线性表和二叉树，逻辑结构不同，但是都可以顺序或者链式存储
15、数据结构的操作：
（1）建立数据结构；（2）清除数据结构；（3）插入数据元素；（4）删除数据元素；（5）更新数据元素；
（6）查找数据元素；（7）按序重新排列；（8）判定某个数据结构是否为空，或是否已达到最大允许的容量；
（9）统计数据元素的个数。
16、算法的基本概念（4个）：有穷性、确定性、可行性、输入/输出
17、算法的设计要求（4个）：正确性、可读性、健壮性、效率与低存储量需求
18、算法的度量：时间复杂度和空间复杂度
19、时间复杂度的分析方法：大O法和语句频度法
20、语句的频度：一个语句在该算法中被重复执行的次数
21、大O法：它表示随问题规模n的增大，算法执行时间的增长率和基本运算的频度f(n)的增长率相同，称作算法的渐进时间复杂度，简称时间复杂度
22、语句频度法：计算该语句重复执行的次数
23、时间复杂度的定义：(不仅依赖于问题规模，还依赖于待输入的数据性质)
24、分析程序的时间复杂性是有两条原则：
加法规则：T(n)=T1(n)+T2(n)=O(f(n))+O(g(n))=O(max(f(n),g(n)))
乘法规则：T(n)=T1(n)+T2(n)=O(f(n))xO(g(n))=O(f(n)xg(n))
25、常见的渐近时间复杂度：对数函数<幂函数<指数函数
O(1)<O()<O(
)<O(
)<O(
)<O(
)<O(
)<O(
)<O(
)
26、空间复杂度：即3个组成部分（P<personal>+I/O+add）
存放本身所用的指令和常数、输入输出占用的空间、信息的辅助空间
27、算法原地工作：是指算法所需辅助空间为常量，记作O(1)
28、时间复杂度计算方法：
1、循环主体中的变量参与循环条件的判断
找出主体语句中与T(n)成正比的循环变量，将其带入条件中进行计算
2、循环主体中的变量与循环条件无关
递归程序：使用公式进行递推（数学归纳法或直接累计循环次数）
非递归程序：直接累计次数
递归：是直接或者间接调用自身的函数，当操作有某种重复模式的数据结构和问题时十分有效。
29、递归的例子
1、 1到n求和： s（n） = n + s（n-1）
2、 n的阶乘： f（n） = n * f（n-1）
3、 快速排序： quicksort（a，low，high） => quicksort（a，low，pivot-1） ⊙ quicksort（a，pivot+1， high）
4、 树的前序、中序、后续遍历： preorder（T） = > read（T->data） preorder（T->leftChild） preorder（T->rightChild）
参考来自：递归程序的含义、实现机制以及复杂度计算 - 苍穹逸影 - 博客园
30、王道拓展题：斐波那契数列算法的时间复杂度
斐波那契数列的定义：F(n+1)=F(n)+F(n-1)
递归：O()
非递归：O(n)
参考来自：斐波那契数列两种算法的时间复杂度 - 在下雨的Tokyo - 梳理：博客园
全文知识点梳理参考：王道考研数据结构参考书、赵海英数据结构辅导视频
