什么是数据结构

数据结构，直白地理解，就是研究数据的存储方式。

数据存储只有一个目的，就是方便后期对数据的再利用。

综合来看，数据结构是一门学科，它教会我们“如何存储具有复杂关系的数据更有助于后期对数据的再利用”。

数据结构有哪些

数据结构大致包含以下几种存储结构：

  • 线性表：包括顺序表、链表、栈和队列

  • 树结构：包括普通树、二叉树、二叉查找树、平衡二叉树、B-Tree、B+Tree 等

  • 图结构：包括无向图、有向图、完全图、连通图 、稀疏图、稠密图等

时间复杂度和空间复杂度

算法，即解决问题的方法。同一个问题，使用不同的算法，虽然得到相同的结果，但是耗费的时间和资源是不同的。

算法 VS 程序

算法是解决某个问题的方式、思路；程序是在心中有算法的前提下编写出来的可以运行的代码。

好算法的标准

首先它必须能够解决这个问题（称为准确性），其次，通过这个算法编写的程序要求在任何情况下不能崩溃（称为健壮性）。

若准确性和健壮性都满足，就要考虑最重要的一点：通过算法编写的程序，运行的效率怎么样。

运行的效率体现在两方面：

  • 算法的运行时间（称为时间复杂度）

  • 运行算法所需的内存空间大小（称为空间复杂度）

综上，好算法的标准就是：在符合算法本身的要求的基础上，使用算法编写的程序运行的时间短，运行过程中占用的内存空间少，就可以称这个算法是“好算法”。

时间复杂度的计算

算法的时间复杂度的标识方法为：O(次数/频度)，这种标识方式称为大”O”标记法。

常用的时间复杂度的排序

O(1)(常数阶) < O(logn)(对数阶) < O(n)(线性阶) < O(n^2)(平方阶) < O(n^3)(立方阶) < O(2^n)(指数阶)

拿时间换空间，用空间换时间

数据的逻辑结构与物理结构（存储结构）

逻辑结构

数据的逻辑结构，简单地理解，就是指数据之间的逻辑关系。

数据之间的逻辑关系可细分为三类：

l 一对一（线性表存储）

l 一对多（树结构存储）

l 多对多（图结构存储）

物理结构（存储结构）

数据的物理结构，指的是数据在物理存储空间上选择集中存放还是分散存放。

根据存储设备的状态和数据的用途选择：

  1. 集中存储（底层实现使用的是数组）需要使用一大块连续的存储空间，假设要存储 1G 的数据，如存储设备上没有大小超过 1G 的空间，就无法使用顺序存储，此时选择链式存储，占用的是存储设备中比较小的存储空间，有可能可以存储成功。

  2. 将数据进行集中存储有利于后期对数据进行遍历操作，将数据进行分散存储有利于后期对数据进行增加或删除操作。因此，若后期需要对数据进行大量的检索（遍历），选择集中存储；若后期需要对数据做更新（增加或删除），选择分散存储。

数据结构和算法的关系和区别

数据结构和算法完全是两个独立的学科，如果非说它们有关系，那也只是互利共赢、“1+1>2”的关系。

结论：数据结构用于解决数据存储问题；算法用于处理和分析数据，它们是完全不同的两类学科。