数据结构（1）序章

数据结构序章

数据元素的相关基本概念

数据结构主要研究数据元素之间的关系。

数据结构三要素

逻辑结构（定义一种数据结构）

既然数据结构是研究数据元素之间的基本关系，那基本关系如何表示呢？逻辑结构就是根据数据元素之间关系的不同特性，分为了4类基本结构

• 集合
• 线性结构
• 树形结构
• 图状结构

数据的运算

定义好了逻辑结构，我们能进行什么操作呢？数据的运算就是结合逻辑结构以及实际需求来定义的基本运算，举个栗子🌰，我们定义一个线性表的结构，可以进行的数据运算有查找，增加，删除等等

物理结构（在计算机中实现）

我们定义好了逻辑结构，又想好了该需要有哪些运算，那如何在计算机中实现呢？那这里给出四种基本方法

• 顺序存储
• 链式存储
• 索引存储
• 散列存储

其中后三者都是非顺序存储的。以上：逻辑结构，数据的运算以及物理结构就是数据结构的三要素

数据类型和抽象数据类型

数据类型

先挑熟悉的说：数据类型。相信在学习C语法的时候我们对数据类型已经很熟悉了，常用的int型，float型，char型都是数据类型。这里我们给出一个通俗的定义，我们只关注其中两个东西，即这个数据类型的值的范围以及可进行的操作。还是举个栗子🌰，就拿bool型来说，值的范围是0,1，可进行的操作是：与、或、非等基本逻辑运算。

抽象数据类型（ADT）

看完数据类型，抽象数据类型也很容易理解了，还是先给出一个不太通俗的定义：抽象数据类型是 抽象数据组织 以及 与之相关的操作。通俗点讲就是站在使用者的角度，我只需要知道这个数据元素之间是什么结构关系，以及可以执行什么操作。

算法序章

我们知道，程序 = 数据结构 + 算法。在上面提到，数据结构是如何用数据描述现实世界，然后存进计算机，那么算法通俗点讲就是：如何处理这些数据来解决问题。

算法的5个特性（缺一不可）

• 有穷性
• 确定性
  • 每条指令有确定含义
  • 相同输入必须得出相同输出
• 可行性
• 输入
• 输出

有了上面5个特性，我们才可以说它是一个算法。那么从一个算法进化到一个好的算法又需要什么呢？

• 正确性
• 可读性：语言能看懂 ， 注释
• 健壮性 ：考虑到一些边界条件和非法数据
• 效率与低存储量需要（时空复杂度）

空间复杂度

空间复杂度，顾名思义，就是这个程序运行时需要的内存需求，想知道它需要多少内存，我们应该先知道，一个程序在运行时，哪些东西需要占用内存。那么无非就是两个东西，即：

• 这个程序代码占用的内存，这一部分的大小是固定的，因此不在空间复杂度的研究范围内
• 数据占用的内存：即变量以及参数等等

所以对于非递归程序，找到和所占空间大小相关的变量分析即可

递归程序

对于递归程序，因为每次调用一遍递归函数都要占用新的空间，所以在分析递归程序的空间复杂度时，要找到递归调用的深度和问题规模n的关系。调用深度x的数量级就是空间复杂度

时间复杂度

事后统计的问题

• 和运行机器的性能有关
• 和编程语言有关，越高级的语言执行效率越低
• 有的算法不能事后统计：导弹控制算法
• 和编译程序产生的机器指令质量有关

一言概之，受太多外界因素的影响

事前分析

• 可以只考虑阶数高的部分
• 加法规则：多项相加，只保留最高阶的项，且系数变为1
• 乘法规则：多项相乘，都保留
• 数量级口诀：常对幂指阶

如果有好几千行代码，需要一行一行数吗？

• 顺序执行的代码只会影响常数项，可以忽略
• 只需在循环操作中挑一个语句分析它的执行次数 i 与 n 的关系即可，（列出等式判断）
• 如果有多层嵌套循环，只关注最内层循环即可

三种复杂度

• 最坏时间复杂度：输入数据最坏的情况
• 最好时间复杂度
• 平均时间复杂度：输入数据等概率出现

一般只考虑算法的最坏时间复杂度和平均时间复杂度。