数据结构第一章绪论

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( $\log_2n$ )<O( $n$ )<O( $n\log_2n$ )<O( $n^2$ )<O( $n^3$ )<O( $2^n$ )<O( $n!$ )<O( $n^n$ )

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( $2^n$ )

非递归：O(n)

参考来自：斐波那契数列两种算法的时间复杂度 - 在下雨的Tokyo - 梳理：博客园

全文知识点梳理参考：王道考研数据结构参考书、赵海英数据结构辅导视频