前言

这一篇的发布就意味着我的数据结构专栏开始更新了，从最基础的开始入门，之后按顺序把每一个该学习的知识都总结一遍，复习巩固。

无论你是学过了还是准备开始学习，都可以一起。学过了你可以复习巩固，没学过可以跟我一起学习。不清楚不明白都可以私信交流，欢迎前来，共同进步。

本节学习内容请看目录！

目录

• 前言
• 数据结构
• • 什么是数据结构？
  • 数据结构的三要素
  • • 逻辑结构
    • • 线性结构
      • 非线性结构
    • 存储结构
    • • 顺序存储
      • 链式存储
      • 索引存储
      • 散列存储
    • 数据运算
• 算法
• • 什么是算法？
  • • 算法的特征
  • 算法与程序
• 算法效率
• • 算法的设计要求
  • 时间复杂度
  • 空间复杂度
• 结言

数据结构

什么是数据结构？

在知道数据结构之前我们得先知道几个关于数据概念：

1. 数据（Date）：是所有能输入到计算机中并被计算机程序处理的符号的集合。是信息的载体；是对客观事物的符号化表示；可以被计算机识别、存储和加工。数据不仅仅包含整型、实型等数值类型，还包含图形、图像、声音、视频及动画等非数值类型。

2. 数据对象(DataObject)：是性质相同的数据元素的集合，是数据的一个子集。只要集合内元素的性质均相同，都可称之为一个数据对象。

3. 数据元素(DataElement)：是数据的基本单位，在计算机中通常作为一个整体进行考虑和处理。在有些情况下，数据元素也称为元素、记录、节点、顶点等。

4. 数据项(Data Item)：是组成数据元素的、有独立含义的、不可分割的最小单位。

只有概念可能不太容易理解，我们举个简单的例子：

数据是能输入到计算机中符号的集合，那就是能输入到计算机中的全部了，我们可以把数据比作这个世界。这个世界是数据的话，那么人类就可以作为一个数据对象了，因为人类有相同的性质（都是人），那么每一个人就是每一个数据元素，因为每一个人是组成人类这个数据对象的基本单位，那么我们每一个人的特征，特点，属性等就是数据项了，因为这种东西加起来共同组成了每一个人。

同时这些人与人之间也不是没有任何关系，人与人之间可以组成家庭，可以是朋友，兄弟之类的。他们之间存在着某一种或者多种关系，我们通常把这种关系称之为结构。

由此数据结构的概念就出来了：

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

其实数据结构是带结构的数据集合，而结构是数据之间的关系。

数据结构的三要素

逻辑结构

数据的逻辑结构是从逻辑关系上描述数据，它与数据的存储无关，是独立于计算机的。因此，数据的逻辑结构可以看作是从具体问题抽象出来的数学模型。数据的逻辑结构有两个要素：一是数据元素；二是关系。

逻辑结构我们把他们分为两种，这里知道一下就行了，后面我们会一个一个的讲的，先初步有个认识就行。分别是线性结构和非线性结构。

线性结构

线性结构是指元素之间只存在一对一的关系，属于线性结构的有：

线性表 栈 队列 数组 广义表 字符串

非线性结构

非线性结构是指元素之间存在一对多或者多对多的关系，属于非线性结构的有：

树，二叉树 图

存储结构

数据的逻辑结构在计算机中(内存)的存储形式。分为顺序存储结构、链式存储结构，索引存储结构、散列存储结构。其中后两中不常见，我们只需要了解一下就行了。

顺序存储

既然逻辑结构是数据在计算机内存的存储形式，那么顺序存储结构就是把数据元素存放在连续的存储单元里，数据元素之间的逻辑关系是通过数据元素的位置来展现的。

C语言中用数组来实现顺序存储结构。同时他也是按顺序存储的。

链式存储

用一组任意的存储单元存储数据元素(可能连续也可能不连续)，数据元素之间的逻辑关系用指针来表示(用指针存放后继元素的存储地址)。

也就是说，每一个数据块分为两部分，一部分是数据域用来存放数据，另外一部分是指针域用来存放逻辑结构的下一个元素的地址。

C语言中用指针来实现链式存储结构 。

索引存储

索引存储就是在存储节点信息的同时，还建立附加一个索引页。索引表中的每一项称为一个索引项。

索引项的一般形式是：(关键字，地址）
关键字是能唯一标识一个结点的那些数据项。

查找时，通过查找关键字确定元素地址，直接通过地址找到元素。

散列存储

散列存储就是通过一个函数算出来对应数据的地址，通过地址直接找到元素。

这个不重要，大家知道一下就行了，不必太纠结。

数据运算

数据运算包括，运算的定义与实现，运算的定义依靠数据的逻辑结构实现，运算的实现针对于数据的存储结构。

这句话晦涩难懂，我们举个例子：

假如我们按顺序存储了一组数据依次为：1，5，9，6

假设我们要找5的下一个元素是多少（假装你不知道是9）

这里的“下一个”肯定说的是我们存储时候的存放顺序了，即：存放完5之后存放的是谁。在这里其实就是运算的定义我们是根据逻辑结构实现的，从逻辑上来讲5的下一个元素。

但是当我们真正开始找5的下一个元素（也就是9）时候，怎么找呢？

这里肯定就得看我们存储数据时候是怎么存的了，也就是得看存储结构了。如果说我们是顺序存储结构，那么我们在5的内存基础上直接到下一个存储位置就可以了（因为顺序储存在内存上是按顺序的存放的），但是如果我们是链式存储结构那我们肯定不能直接到下一个内存位置了（链式存储结构内存上不一定为连续的）。这就是运算的实现得针对每个存储结构。

相信到这里大家肯定也就明白了数据运算，注意理解。

算法

什么是算法？

算法的定义：对特定问题求解步骤的一种描述，它是指令的有限序列，其中的每条指令表示一个或多个操作

解释一下，算法就是对于某一个问题，我们解决这个问题的办法，这个办法或许包括了很多步骤。

算法的特征

一个合格的算法特性有：确定、有穷、可行、输入、输出

1. 有穷性：算法在执行有限步骤之后，自动结束而不会出现无限循环，并且每一个步骤都在可接受的时间范围内完成。

2. 确定性：算法的每一个步骤都有确定的含义，不会出现二义性(不会有歧义)。

3. 可行性：算法中的所有操作都可以通过已经实现的基本操作运算执行有限次来实现。

4. 输入：一个算法有零个或多个输入。当用函数描述算法时，输入往往是通过形参表示的，在它们被调用时，从主调函数获得输入值。

5. 输出：一个算法有一个或多个输出，它们是算法进行信息加工后得到的结果，无输出的算法没有任何意义。

算法与程序

对于刚入坑的选手算法与程序可能傻傻分不清，今天我们来区分一下。

算法：解决问题的一种方法或一个过程，考虑如何将输入转换成输出，一个问题可以有很多个算法。
程序：是某种程序设计语言对算法的具体实现。

也就是说算法是通过程序来实现的，算法是领导，程序是那些实施者。

算法与程序的区别：

1. 算法必须是有穷的，程序可以是无穷的
2. 算法必须是正确的，程序可以是错误的
3. 算法可以用伪代码、程序语言等描述，程序只能用程序语言编写并可以运行

算法效率

知道什么是算法之后那我们该如何设计出一个好的算法呢？一个好算法的度量又是什么呢？

算法的设计要求

一个好的算法应该具有正确性、可读性、健壮性、时间效率高和存储量低的特征。

正确性：算法应能够正确地解决求解问题

可读性：算法应具有良好的可读性，以帮助人们理解

健壮性：输入非法数据时，算法能适应的做出反应或进行处理

效率与存储量：效率是指算法执行时间，存储量需求是指算法执行过程中所需最大存储空间

前三个特性我们能直观的看出来，那效率与存储量我们又该怎么样来衡量呢？

为此我们引入了空间复杂度与时间复杂度两个概念，接下来我们重点介绍一下这两个。

时间复杂度

为了学习时间复杂度引入新概念——语句频度

语句频度：该条语句可能重复执行的次数
T（n）：所有语句的频度之和，其中n为问题的规模
时间复杂度：T(n) = O(f(n))，其中O表示T(n)与f(n)在n->正无穷时为同阶无穷大

举个简单例子：
f （ n ） = 3n2 + n 那 么 时 间 复 杂 度 T ( n ) = O (n2 ) f（n）=3n ^ {2}+n 那么时间复杂度T(n) = O(n^{2}) f（n）=3n2+n那么时间复杂度T(n)=O(n2)
因为当n->正无穷时f（n）与n^2为同阶无穷大

一般对于多语句频度时我们这样处理：

T(n) = T1(n) + T2(n) = O(f(n)) + O(g(n)) = O (max ( f(n), g(n) ) T(n)
= T1(n) * T2(n) = O(f(n)) * O(g(n)) = O (f(n) *g(n))

常见时间复杂度

最后大家看个例子，下面这个程序的时间复杂度是多少呢？

int i;for(i=0;i<n;i++){printf(i);}for(i=0;i<n;i++){for(int j=0;j<n;j++){int num=i+j;printf(num);}}

在C语言中我们通常使用 ；来分别一个语句。
这 个 程 序 的 f ( n ) = 1 + n +n2 +n2 = 2n2 + n + 1 这个程序的f(n)=1+n+n^2+n^2=2n^2+n+1 这个程序的f(n)=1+n+n2+n2=2n2+n+1所 以 T ( n ) = O (n2 ) 所以T(n)=O(n^2) 所以T(n)=O(n2)

我们找一个程序的时间复杂度只需要找执行次数最多，对算法运行时间贡献最大，嵌套最深的语句就行了。

空间复杂度

空间复杂度：算法消耗的存储空间，记 S(n) = O(g(n))

算法原地工作时指算法所需辅助空间为常量，O(1)。

除本身所用的指令、常数、变量和输入数据外，还需要一些对数据进行操
作的工作单元和存储为实现算法所需的一些信息的辅助空间，这个不深入了解。

空间复杂度相对于时间复杂度没那么重要，我们了解一下就可！

结言

学习数据结构有很多东西需要我们记住的，但是我们不能靠死背概念记忆，我们要靠理解来记忆，只有这样在以后我们才会使用。

有问题欢迎交流，共同进步！
持续更新中…