数据结构与算法（一）入门-数据结构与算法一什么是数据结构.md
title: 数据结构与算法（一）入门date: 2021-06-22 00:17:08.321
updated: 2021-06-22 22:20:38.131
url: /?p=254
categories: 数据结构与算法
tags: 数据结构与算法
什么是数据结构？
数据结构，直白地理解，就是研究数据的存储方式。通过研究这些存储方式，实现大量数据或复杂数据的高效使用。
数据结构常用存储结构
线性表：顺序表、链表、栈、队列。
树结构：普通树、二叉树、线索二叉树等。
图存储结构。
线性表
- 顺序存储结构
内存空间连续。
2. 链式存储结构
内存空间不连续。
3. 栈
先入后出。
4. 队列
先入先出。
树存储结构
书存储适合“一对多”关系的数据。
图存储结构
图存储结构适合存储具有“多对多”关系的数据。
逻辑结构和存储结构
通过学习数据结构，我们可以学到 3 种存储结构分别存储这 3 类逻辑关系的数据，换句话说：
- 线性表用于存储具有“一对一”逻辑关系的数据；
- 树结构用于存储具有“一对多”关系的数据；
- 图结构用于存储具有“多对多”关系的数据；
逻辑结构
数据的逻辑结构，简单地理解，就是指的数据之间的逻辑关系。
数据之间的逻辑关系可细分为三类，“一对一”、“一对多”和“多对多”：
- 一对一： 类似集合
{1,2,3,...,n}这类的数据，每个数据的左侧有且仅有一个数据与其相邻（除 1 外）；同样，每个数据的右侧也只有一个数据与其相邻（除 n 外），所有的数据都是如此，就说数据之间是“一对一”的逻辑关系； - 一对多： 图 1 中的数据就属于“一对多”，因为对于张平来说，有且仅有一个父亲（张亮），但是有 2（多）个孩子；
- 多对多： 拿图 2 来说，从 V1 可以到达 V2、V3、V4，同样，从 V2、V3、V4 也可以到达 V1，对于V1、V2、V3和V4来说，它们之间就是“多对多”的关系；
存储结构（物理结构）
数据的存储结构，也就是物理结构，指的是数据在物理存储空间上选择集中存放还是分散存放，如下图。
衡量算法的运算效率
一个算法首先必须保证准确性和健壮性，在此基础上，衡量算法的运算效率有两个方面：
- 程序的运行时间。
- 程序的运行占用的内存大小。
算法编写出的程序，运行时间更短，运行期间占用的内存更少，该算法的运行效率就更高，算法也就更好。
而在数据结构中，用时间复杂度和空间复杂度分别衡量程序的运行时间和程序的运行占用的内存大小，从而衡量算法的运行效率。
时间复杂度
因为运行环境（软硬件）的不同，相同的算法在不同的机器运行的时间是不一样的，所以都是使用时间复杂度。所以说表示一个算法所编程序运行时间的多少，用的并不是准确值（事实上也无法得出），而是根据合理方法得到的预估值。
数据结构中，每条语句的执行次数，又被称为该语句的频度。
大 O 记法的表示方法也很简单，格式如下：
O(频度)
其中，这里的频度为最简之后所得的频度。
空间复杂度
如果程序所占用的存储空间和输入值无关，则该程序的空间复杂度就为 O(1)；反之，如果有关，则需要进一步判断它们之间的关系：
- 如果随着输入值 n 的增大，程序申请的临时空间成线性增长，则程序的空间复杂度用 O(n) 表示;
- 如果随着输入值 n 的增大，程序申请的临时空间成 n2 关系增长，则程序的空间复杂度用 O(n2) 表示；
- 如果随着输入值 n 的增大，程序申请的临时空间成 n3 关系增长，则程序的空间复杂度用 O(n3) 表示；
数据结构与算法的关系和区别
数据结构用于解决数据存储问题，而算法是思考如何利用存储的数据快速无误地解决问题，它们是完全不同的两类学科。非说它们有关系，那也只是互利共赢、“1+1>2”的关系。