作为一个程序员，每天都在和不同的数据打交道。那么你真的了解数据么？为什么我们总在说数据结构呢？数据结构是不是就是我们的基本数据类型、字符串、数组呢？下面我们就来聊聊数据结构的那些事。
概念
数据结构是一门研究非数值计算的程序设计问题中的操作对象，以及它们之间的关系和操作等相关问题的学科。
《大话数据结构》这本书中对数据结构做了如此定义。其实早在1968年，美国一名叫Donald E. Knuth教授写了一本书《计算机程序设计艺术》，在其中第一卷《基本算法》就比较系统的阐述了数据的逻辑结构和存储结构及其操作，开创了数据结构的体系。而瑞士计算机科学家Niklaus Wirth在1976年也写了一本书，名为《算法+数据结构=编程》。人们早早的就意识到数据结构之于计算机编程的重要性。
我们可以通俗的认为，数据结构就是计算机存储、组织数据的方式，是相互之间存在一种或多种特定关系的数据元素的集合。
为了弄清楚数据结构，我们必须先来认识数据结构的一些基本概念。
数据
数据是描述客观事物的符号，是计算机中可以操作的对象，是能被计算机识别，并输入给计算机处理的符号集合。数据不仅仅包括整型、实型等数值类型，还包括字符及声音、图像、视频等非数值类型。
数据有2个特点：
- 可以输入到计算机中
- 能呗计算机程序处理
对于整型，浮点型数据，可以直接进行数值计算。对于字符串类型的数据，我们就需要进行非数值的处理。而对于声音、图像、视频这样的数据，我们需要通过编码的手段将其变成二进制数据进行处理。
数据元素
数据元素: 是组成数据的，且有一定意义的基本单位，在计算机中通常作为整体处理。也被称为记录。比如在人类中，人就是数据元素了。
数据项
数据项: 一个数据元素可以由若干数据项组成。比如人这样的数据元素,可以有眼睛、耳朵、鼻子、嘴巴、手臂这些数据项。当然也可以拆解为别的数据项：姓名、年龄、性别等。数据项是数据不可分割的最小单位。
数据对象
数据对象: 是性质相同的数据元素的集合，是数据的子集。性质相同是指数据元素具有相同数量和类型的数项。
总结如图：
数据结构关系.png
逻辑结构与物理结构
按照视点的不同，我们把数据结构分为逻辑结构和物理结构。
逻辑结构
逻辑结构是指数据对象中数据元素之间的相互关系。逻辑结构可以分为以下4种：
1. 集合结构
集合结构中的数据元素除了同属于一个集合外，它们之间没有其他关系，它们之间唯一的相同点就是"同属于一个集合"。
集合结构.png
2. 线性结构
线性结构中的数据元素之间的关系是一对一的。常用的线性结构有：线性表、栈、队列、双队列、数组、串。
线性结构.png
3. 树形结构
树形结构中的数据元素是一对多的层级关系。常见的树形结构: 二叉树、B树、哈夫曼树、红黑树等。
树形结构.png
4. 图形结构
图形结构中的数据元素之间的关系是多对多的。常见的图形结构：邻近矩阵、邻接表。
图形结构.png
物理结构
物理结构也叫存储结构，指的是数据的逻辑结构在计算机的存储形式。数据元素的存储结构形式有2种: 顺序存储结构和链式存储结构。
1. 顺序存储结构
顺序存储结构是指把数据元素存放在地址连续的存储单元里，其数据间的逻辑关系和物理关系是一致的。比如一个数组，它的元素是一个接一个，在内存空间中的地址也是连续的，我们可以通过数组的下标访问每一个元素，也可以使用地址递增的方式访问。
顺序存储.png
2. 链式存储结构
链式存储结构是把数据元素放在任意的存储单元里，这组存储单元可以是连续的，也可以是不连续的。数据元素的存储关系并不能反映逻辑关系，因此需要用一个指针存放数据元素的地址，这样通过地址就可以找到相关联数据元素的位置。
链式结构.png
算法
说到数据结构，就不得不提起算法，我们设计各种各样数据结构的最终目的也是进行运算。那么什么是算法呢？现如今普通认可的算法的定义如下：
算法是解决特定问题求解步骤的描述，在计算机中表现为指令的有限序列，并且每条指令表示一个或多个操作。
算法的特性
算法具有5个基本特性: 输入、输出、有穷性、确定性和可行性。
- 输入输出
算法具有零个或者多个输入，至少有一个或多个输出。
- 有穷性
有穷性指的是算法在执行有限的步骤之后，自动结束而不会出现无限循环,且每一个步骤都在可接受的时间内完成。
- 确定性
确定性是指算法的每一个步骤都具有确定的含义，不能出现二义性。 算法在一定条件下，只有一条执行路径，相同的输入只能有唯一的输出结果。
- 可行性
可行性: 算法的每一步都必须是可行的，即每一步都能通过执行有限次数完成。
算法的设计要求
- 正确性
算法的正确性是指算法至少应该具有输入，输出和加工处理无歧义性，能正确反映问题的需求、能够得到问题的正确答案。正确性分为4个层次:
- 算法程序没有语法错误;
- 算法程序对于合法的输入数据能够产生满足要求的输出结果;
- 算法程序对于非法的输入数据能够得出满足规格说明的结果;
- 算法程序对于精心选择的,甚至刁钻的测试数据都有满足要求的输出结果;
- 可读性
可读性: 算法设计的另一个目的是为了便于阅读，理解和交流。可读性高有助于人们理解算法，晦涩难懂的算法往往隐含错误，不容易发现，并且难于调试和修改。
可读性是算法好坏的很重要的标志!
- 健壮性
一个好的算法还应该能对输入数据的不合法的情况做出合适的处理，考虑边界性，也是在写代码经常要做的一个处理。当输入数据不合法时，算法也能做出相关处理，而不是产生异常和莫名其妙的结果。
- 时间效率高和存储量低
用最少的存储空间和最少的时间，办成同样的事，就是好算法!
算法的时间复杂度
使用高级程序语言编写的程序在计算机上运行时所消耗的时间取决于下列的因素:
- 算法采用的策略、方法
- 编译产生的代码质量
- 问题的输入规模
- 机器执行指令的速度
算法的时间复杂度的定义如下：
在进行算法分析时，语句的总执行次数T(n)是关于问题规模n的函数，进而分析T(n)随着n变化情况并确定T(n)的数量级。算法的时间复杂度，也就是算法的时间量度，即为T(n) = O(f(n))。它表示随问题规模n的增大，算法执行时间的增长率和f(n)的增长率相同，称作算法的渐近时间复杂度，简称为时间复杂度。其中f(n)是问题规模n的某个函数。
大写O( )来体现算法时间复杂度的记法，我们称之为大O记法。
推导大O阶的方法：
- 用常数1取代运行时间中所有加法常数
- 在修改后的运行次数函数中，只保留最高阶项
- 如果在最高阶项存在且不是1，则去除与这个项相乘的常数
常数阶
int sum = 0, n = 100;
sum = (1 + n) * n / 2;
printf("%d", sum);
这个算法的每行代码都会执行一次，运行次数函数是f(n) = 3，依据推导大O阶的方法，第一步就是将常数替换为1，由于没有最高阶项，所以该算法的时间复杂度为O(1)。
需要注意的是，常数阶的算法不管常数是多少，我们都记做O(1)，并没有O(2)、O(3)之类的复杂度。
线性阶
for (int i = 0; i < n; i++) {
// 时间复杂度为O(1)的操作
}
分析算法的复杂度，就是要分析循环结构的运行情况。上述代码的时间复杂度为O(n)，是因为循环体中的代码要执行n次。
对数阶
int i = 1;
while (i < n) {
i = i * 2;
}
在循环体内，i每次都乘以2倍，即为2^x = n，可以得出次数x为以2为低n的对数x = log2n。根据推导大O阶的方法，去除最高阶项的常数，即为O(logn)。
平方阶
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
// 时间复杂度为O(1)的操作
}
}
循环嵌套n*n，时间复杂度为O(n^2)。
常见的时间复杂度所耗时从小到大依次是：
O(1) < O(logn) < O(n) < O(n*logn) < O(n²) < O(n³) < O(2的n次方) < O(n!) < O(n的n次方)
对于算法的分析，一种方法就是计算所有情况的平均值，这种时间复杂度的计算的方法称为平均时间复杂度。另一种方法是计算最坏的情况下时间复杂度， 这种方法称为最坏时间复杂度。一般没有特殊情况下，都是指最坏时间复杂度。
算法空间复杂度
算法的空间复杂度通过计算算法所需的存储空间实现，算法空间复杂度的计算公式记做: S(n) = n(f(n))，其中n为问题的规模，f(n)为语句关于n所占存储空间的函数。
一般情况下，一个程序在机器上执行时，除了需要寄存本身所用的指令、常数、变量和输入数据外，还需要一些对数据进行操作的辅助存储空间。其中，对于输入数据所占的具体存储量取决于问题本身，与算法无关。 这样我们只需要分析该算法在实现时所需要的辅助空间就可以了。
下面算法仅仅通过开辟了一个临时变量temp，与问题规模n大小无关,所以其空间复杂度为S(1)。
int temp;
for(int i = 0; i < n/2 ; i++){
temp = a[i];
a[i] = a[n-i-1];
a[n-i-1] = temp;
}
而这个算法中，我们需要开辟一个大小为n的辅助变量b，所以空间复杂度为S(n)。
int b[10] = {0};
for(int i = 0; i < n;i++){
b[i] = a[n-i-1];
}
for(int i = 0; i < n; i++){
a[i] = b[i];
}
非广告提示，文中大部分概念性东西参考自《大话数据结构》这本书，感兴趣的同学可以买来一读。
参考文献：
- 《大话数据结构》
网友评论