数据结构与算法（一）基础知识
数据结构与算法（一）基础知识
程序 = 数据结构 + 算法
想让你的程序拥有天才般的灵魂，就一起学习数据结构和算法吧
基本概念和术语
1. 数据
数据：是描述客观事物的符号，是计算机中可操作的对象，是能被计算机识别，并输入给计算机处理的符号集合。
整型、浮点型等数值类型及字符、声音、图像等非数值数据都属于数据。
2. 数据元素
数据元素：是组成数据的，有一定意义的基本单位，在计算机中通常作为整体处理，也被称为记录。
例如学校学生作为数据，某个学生就可以看作组成学生数据的基本单位。
3. 数据项
数据项：一个数据元素可以由若干个数据项组成。
例如学生元素(也就是学生记录)可以看作由学号、姓名、性别、院系和班级等数据项组成。
4. 数据对象
数据对象：是性质相同的数据元素的集合，是数据的子集。
例如将大一学生就可以看作数据对象，因为他们有这大一新生的共同性质；当然也可以把所有男生学生看作数据对象，因为他们共性就是男的。
5. 数据结构
数据结构：相互之间存在一种或多种特定关系的数据元素集合
现实世界中，任何事物都有内在联系，不会孤立存在，同样计算机中，数据元素也不是孤立存在，杂乱无序的，而是具有内在联系的数据集合。例如一个学校的组成
学校组成结构
数据的逻辑结构和存储结构
逻辑结构
-
集合结构
集合结构中的数据元素除了同属于一个集合外，没有其他关系。例如下面的正整数集合。
集合结构
- 线性结构
线性结构中的数据元素是一对一的关系。数据元素有一种先后次序关系，如下图，其中a是b的前驱，b是a的后继
线性结构
-
树形结构
树形结构中的数据元素之间存在一种一对多的层次关系
树形结构
-
图结构
图形结构的数据元素是多对多的关系
图结构
存储结构(也称为物理结构)
-
顺序存储结构
把数据元素存放在一段连续的存储单元中，数据元素间逻辑关系和物理关系一致。
顺序存储结构
-
链式存储结构
把数据元素存储在任意的存储单元中，存储单元可以连续，也可以不连续，存储关系并不能反映其逻辑关系，因此需要借助指针来表示数据元素之间的逻辑关系。如下图，箭头指向可以看作指针指向。
链式存储结构
算法介绍
程序=算法+数据结构
数据结构是算法实现的基础，算法总要依赖某种数据结构来实现。算法操作对象是数据结构。
算法：算法是解决特定问题求解步骤的描述，在计算机中表现为指令的有限序列，并且每条指令表示一个或多个操作。
算法的五大特性
- 有穷性
执行步骤是有限的，可在接受时间内完成。 - 确定性
相同的输入只能有一个唯一的输出结果。 - 可行性
算法每一步都必须是可行的。 - 输入
算法具有零个或多个输入。 - 输出
算法至少有一个或多个输出。
算法设计的4个目标
- 正确性
对于精心挑选的典型的，苛刻的带有刁难性的几组输入数据能到满足规格要求的结果。 - 可读性
晦涩难懂的程序往往隐含错误，不易发现，难以调试和修改。 - 健壮性
当输入数据不合法时，也能给出提示，而不是产生错误或异常。 - 时间高效率和低存储量
设计算法时应尽量选择执行时间少，存储量低的算法。
算法效率度量
1. 事后统计方法
- 必须依据算法事先编制好算法程序，需要花费大量时间与精力
- 执行时间长短依赖计算机硬件和软件等环境因素，有时会掩盖算法本身优劣
故常采用事前分析估算方法评价算法好坏
2. 事前分析估算方法
除去语言级别、机器执行指令速度等影响，算法效率可以通过问题的规模来衡量。也就是评估其时间复杂度和空间复杂度，关于该部分下节分析。
