【DAY04 软考中级备考笔记】数据结构基本结构和算法

数据结构基本结构和算法 2月25日 – 天气：晴

周六玩了一天，周天学习。

1. 什么是数据结构

数据结构研究的内容是一下两点：

• 如何使用程序代码把现实世界的问题信息化
• 如何用计算机高效地处理这些信息从创造价值

2. 什么是数据

数据是信息的载体，是描述客观事物属性的数字，字符和所有能够输入到计算机中并且被计算机处理和识别到符号的集合。

简单来说，数据是计算机程序加工的原谅。

下面是关于数据的一些基本概念：

• 数据元素：数据元素是数据的基本单位，通常作为一个整体来显示。（可以理解为是数据库中的一条记录）
• 数据项：数据项是数据的最小单位，一个数据元素可能由多个数据项组成。（可以理解为数据库中的某一个字段）

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

3. 数据结构三要素

数据结构的三要素是：

• 逻辑结构
• 物理结构
• 数据的运算

3.1 数据的逻辑结构

• 集合结构：各个元素同处于一个集合中，别无其它的关系。
• 线性结构：数据元素之间是一对一的关系。除了第一个元素和最后一个元素，其它的元素都有唯一的前驱和后继。第一个元素只有唯一的后继，最后一个元素只有唯一的前驱。
• 树形结构：数据之间是一对多的关系。
• 图结构：数据之间是多对多的关系。

3.2 数据的物理结构

• 顺序存储：逻辑上相邻的元素存储的物理位置上也是在相邻的存储单元中
• 链式存储：逻辑上相邻的元素在物理位置上可以相邻，也可以不相邻
• 索引存储：在存储元素信息的同时，还建立附加的索引表
• 散列存储：根据元素的关键字直接通过哈希函数计算得到其存储地址，又名哈希存储

4. 算法

4.1 什么是算法？

程序 = 算法 + 数据结构

数据结构研究的是如何将现实世界中的问题信息化，同时还要提供对这些数据的基本操作，如增删改查。

算法研究的是如何处理这些信息化后的数据以解决实际问题

4.2 算法的特点

• 有穷性：算法必须总是在执行完有穷步骤后结束，并且每一步骤都可以在有限的时间内结束
• 确定性：算法中每一条指令必须有明确的含义，且对于相同的输入，必须只能得到相同的输出
• 可行性：算法中描述的操作都必须通过已经实现的基本运算执行有限次来实现
• 输入：一个算法有零个或多个输入，这些输入取自于某一个特定的对象集合
• 输出：一个算法有一个或多个输出，这些输出取自于某一个特定的对象集合

4.3 算法复杂度

算法复杂度分为了时间复杂度和空间复杂度