王道数据结构第一章个人向笔记

目录1.1.0 导读1.1.1 绪论1.1.2 数据结构的三要素逻辑结构数据的运算物理结构（存储结构）1.2.1 算法的基本概念1.2.2 时间复杂度1.2.3 空间复杂度

1.1.0 导读

数据结构在学什么？

如何用程序代码把显示世界的问题信息画

如何用计算机高效地处理这些信息从而创造价值

1.1.1 绪论

数据：是信息的载体，是描述客观事物属性的数、字符及所有能输入到计算机中并被计算机程序识别和处理的符号的集合。数据是计算机程序加工的原料

数据元素是数据的基本单位，通常作为一个整体进行考虑和处理

一个数据元素可由若干数据项组成，数据项是构成数据元素的不可分割的最小单位

数据对象是具有相同性质的数据元素的集合，是数据的一个子集

数据结构是相互之间存在一种或多种特定关系的数据元素的集合

1.1.2 数据结构的三要素

逻辑结构

集合

各个元素同属一个集合，别无其他关系

线性结构

数据元素之间是一对一的关系，出了第一个元素，所有元素都有唯一的前驱，除了最后一个元素，所有元素都有唯一后继

树形结构

数据元素之间是一对多的关系

图结构

数据元素之间是多对多的关系

数据的运算

针对某种逻辑结构，结合实际需求，定义基本运算

物理结构（存储结构）

数据的物理结构（存储结构）：如何用计算机表示数据元素的逻辑关系

数据类型是一个值的集合和定义在此集合上的一组操作的总称

抽象数据类型（ADT）是抽象数据组织及与之相关的操作

1.2.1 算法的基本概念

程序=数据结构+算法

算法是对特定问题求解步骤的一种描述，它是指令的有限序列，其中的每条指令表示一个或多个操作

算法的特性

有穷性：一个算法必须总在执行有穷步之后结束

确定性：算法中的每条指令必须有确切的含义。对于相同的输入只能得出相同的输出

可行性：算法中描述的操作都可以通过已经实现的基本运算执行有限次来实现

输入

输出

1.2.2 时间复杂度

事前预估算法时间开销\(T(n)\)与问题规模n的关系

可以只考虑阶数高的部分

大O表示法：

大O表示同阶，同等数量级，当\(n->无穷\)二者之比为常数

常对幂指阶

结论1：顺序执行的代码只会影响常数项，可以忽略

结论2：只需挑循环中的一个基本操作分析它的执行次数与n的关系即可

结论3：如果有多层循环只需要考虑最深层循环即可

1.2.3 空间复杂度

算法原地工作--算法所需内存空间为常量

只需关注存储空间的大小和问题规模相关的变量

函数递归调用会带来内存开销

空间复杂度=递归调用的深度（一般来说，每层递归空间都是常数）