数据结构基础-Day1

数据结构

什么是数据结构

数据结构，直白的说，就是数据的存储方式。数据的存储只有一个目的，就是为了我们以后能够更加方便便捷的读取以及操作数据。无缘由的数据存储行为是对存储空间的不负责任。如何才能设计出一个合理的数据结构，我们需要先了解数据结构的组成。

数据结构的基本术语

数据结构的图如下所示：

• 数据：信息的载体，是描述客观事物属性的数、字符及所有能输入到计算机中并被计算机程序识别和处理的符号的集合。e.g.：大自然。
• 数据对象：具有相同性质的数据元素的集合，是数据的一个子集。e.g.：人类
• 数据元素：数据的基本单位，通常作为一个整体进行考虑和处理。e.g.：特定的某人，张三
• 数据项：构成数据元素的不可分割的最小单位。e.g.：人的基本信息，身高、年龄等

数据类型

数据类型是指一组性质相同值的集合以及定义在该集合中的一系列操作的总称。

• 原子类型：原子就是不可再分割的意思，它是原子类型值的集合和定义在该集合上的操作。例如在 C 语言中的 int、char、float 等都是原子类型。
• 结构类型：它是结构的集合和定义在集合上的操作。结构就是多个原子类型值的组合，其中有 list、map、set 等。
• 抽象数据类型：指一个数学模型以及定义在此模型上的操作，可以理解为实际开发里经常使用的结构体和类，根据业务需求定义合适的数据类型以及动作。

数据结构的三要素

逻辑结构

逻辑结构是指数据元素之间的逻辑关系，它更贴近于现实，即从逻辑关系上来描述数据。它是独立于计算机的，与计算机内部如何存储是无关的。

在逻辑结构中，具体分为四种：线性结构、集合、树形结构、图状结构。其中，把集合、树形结构、图状结构统称为非线性结构。

• 集合

  

  集合是指除了所有的元素均在一个集合之内，没有其他的关系。在数学中，所有的小数都是一个集合，所有的整数也是一个集合。
• 线性结构

  

  线性结构存储的数据往往是依次排列的，每个元素的前面和后面有且仅有一个元素与之相邻(除了头尾元素)，是一对一的关系。
• 树形结构

• 图

物理结构

存储结构是指数据结构在计算机内的表示，也称为物理结构。它既包括数据元素本身的表示，也包括数据元素之间关系的表示。
存储结构也分为四种：顺序存储、链式存储、索引存储、散列存储。

• 顺序存储

顺序存储结构的主要优点是节省存储空间，因为分配给数据的存储单元全用存放结点的数据（不考虑c/c++语言中数组需指定大小的情况），结点之间的逻辑关系没有占用额外的存储空间。采用这种方法时，可实现对结点的随机存取，即每一个结点对应一个序号，由该序号可以直接计算出来结点的存储地址。但顺序存储方法的主要缺点是不便于修改，对结点的插入、删除运算时，可能要移动一系列的结点。

优点：随机存取表中元素、储存密度大。缺点：插入和删除操作需要移动元素。

• 链式存储

为了给各个数据块建立“依次排列”的关系，链表给各数据块增设一个指针，每个数据块的指针都指向下一个数据块（最后一个数据块的指针指向 NULL）。

链式存储解决了顺序存储插入和删除操作需要移动元素的缺点，移动响应存储单元的next指针即可。但是它的读取效率相比于顺序存储则极为低下，因为需要从头节点开始一步一步寻找目标节点，不支持随机存取。

• 索引存储

但是，索引存储有一个缺点，就是既要存放数据元素，又要存放索引表，在存放索引表的时候会消耗内存资源。

• 散列存储

数据的运算

数据结构研究的内容：就是如何按一定的逻辑结构，把数据组织起来，并选择适当的存储表示方法把逻辑结构组织好的数据存储到计算机的存储器里。算法研究的目的是为了更有效的处理数据，提高数据运算效率。数据的运算是定义在数据的逻辑结构上，但运算的具体实现要在存储结构上进行。一般有以下几种常用运算：

• 检索。检索就是在数据结构里查找满足一定条件的节点。一般是给定一个某字段的值，找具有该字段值的节点。
• 插入。往数据结构中增加新的节点。
• 删除。把指定的结点从数据结构中去掉。
• 更新。改变指定节点的一个或多个字段的值。
• 排序。把节点按某种指定的顺序重新排列。例如递增或递减。

算法

算法，即解决问题的方法，是解决特定问题求解步骤的描述,在计算机中表现为指令的有限序列列, 并且每个指令表示⼀一个或多个操作。同一个问题，使用不同的算法，虽然得到的结果相同，但是耗费的时间和资源是不同的。

算法特性

• 输入输出：有0个或者多个输入输出
• 有穷性：算法必须能在执行有限个步骤之后终止
• 确定性：每一步骤必须有确切的定义
• 可行性：每个计算步骤都可以在有限时间内完成

算法设计要求

• 正确性：算法的正确性是评价一个算法优劣的最重要的标准。
• 可读性：算法的可读性是指一个算法可供人们阅读的容易程度。
• 健壮性：健壮性是指一个算法对不合理数据输入的反应能力和处理能力，也称为容错性。
• 时间效率高和储存量低

时间复杂度

算法的时间复杂度是指执行算法所需要的计算工作量。一般来说，计算机算法是问题规模n 的函数f(n)，算法的时间复杂度也因此记做T(n)=Ο(f(n))。 因此，问题的规模n 越大，算法执行的时间的增长率与f(n) 的增长率正相关，称作渐进时间复杂度（Asymptotic Time Complexity）。

空间复杂库

算法的空间复杂度是指算法需要消耗的内存空间。其计算和表示方法与时间复杂度类似，一般都用复杂度的渐近性来表示。同时间复杂度相比，空间复杂度的分析要简单得多。

好算法的标准

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

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

运行效率体现在两方面： 算法的运行时间。 运行算法所需的内存空间大小。

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

调查表明，人们对于软件或者 APP 的运行效率有极高的要求，例如对于网页打开的忍耐极限是 6 秒甚至更短，如果你设计的网页打开的时间超过 6 秒，多数人会在 4 秒甚至 3 秒的时候毫不犹豫地关掉而去浏览其他网页。在这个大背景下，一个好的“算法”更注重的是时间复杂度，而空间复杂度只要在一个合理的范围内就可以。

数据结构和算法的关系

再看算法这一块，根据输入，设计可行的计算方法并用优先的可执行步骤描述出来，最终得到确切的输出。

• 输入：土豆+辣椒+配菜
• 输出：酸辣土豆丝
• 有穷性：酸辣土豆丝的菜谱也就几个步骤
• 确定性：每一个步骤都有特定的目的
• 可行性：跟着菜谱走，几分钟就能搞定 （以上属于个人见解）

时间复杂度的计算可以分为三步：

1. 常数项用1替代
2. 只保留最高阶
3. 最高阶系数置为1

百度百科-算法
百度百科-数据结构
算法时间复杂度和空间复杂度
数据结构的基本概念
一句话+一张图理解——数据结构与算法