数据结构和算法

如果没有接触过数据结构这门课程，或者说只是单单听过这个名词。那么在含义方面，数据结构对于我们来说是非常陌生的。在了解一门课程之前，我们总是要知道这门课程要学习什么。

一、什么是数据结构？

在了解数据结构之前，我们需要知道什么是数据。对于人类来说，一切可以让我们获取信息的东西都是数据。我们可以通过一个动物的叫声判断是什么动物，我们可以通过一本书了解到作者想要表达的东西，我们也可以通过一张图片了解到一个人的模样…

我们现在研究数据结构是建立在计算机的基础之前，所以对于计算机来讲（拿C语言打比方），所以的基本数据类型的变量、派生类型变量、结构类型变量等…我们都可以称为数据。

数据结构是研究数据集合中各个元素之间关系的一门学科。我们必须注意两个地方，第一个是集合，我们所研究的数据一般都是以集合的形式，这个集合可以为空，也可以只有一个元素。第二个就是关系，我们研究的数据之间通常会有一定的关系，有些是杂乱无章的集合关系，有些是依次排列的线性关系，也有交错混杂的树形关系…但是他们必须要有一定的关系。

注意：在谈到集合的时候，我们说可以有一个元素，但是不能是只能有一个元素。像我们使用到的int类型，我们不能将它称为数据结构。

二、 一些概念和术语

数据是对客观事物的符号表示，在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。

数据元素是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。一个数据元素可由若干个数据项组成，数据项是数据不可分割的最小单位。

数据对象是性质相同的数据元素的集合。

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

数据通常有四类结构：

1. 集合：结构中数据元素同属一个集合；
2. 线性结构：结构中的数据元素之间存在一对一的关系；
3. 树形结构：结构中的数据元素之间存在一对多的关系；
4. 网状结构或图状结构：结构中的数据元素之间存在多对多的关系；

数据项作为不可分割的最小单位，组成了一个数据元素。而多个数据元素组成的有一定关系的集合，又被我们称之为数据结构。按照集合中不同的关系，我们通常把数据的结构分为四类：集合、线性结构、树形结构、网状或图状结构。而上述的一切，都被我们称作数据。不过，数据远不止这些。

注意：数据结构我们可以简单理解为数据关系，后面很多时候我们都可以直接用关系替代结构这个词。

各个结构的图如上。

三、逻辑结构和物理结构（存储结构）

在上述的数据结构中，四类结构都是脱离计算机独立存在的。即在我们现实生活中也通用，像我们平时用的名单、购物清单、账单等…这个层面上的关系（结构），我们称为逻辑结构。简单来说，就是数据之间对应的关系（一对一、一对多…）。而我们用计算机，通过实际的方式（主要是两种）实现这种关系。这种通过具体方式，在计算机中实现的数据结构就称为物理结构，又称为存储结构。

而根据具体实现方式不同，又分为顺序存储结构和链式存储结构。顺序存储结构使用数组存储元素，所以数据元素在连续的内存地址上。而链式存储结构通过一个个节点实现，在节点中存储数据和下一个元素的指针。存储数据的地方被称为数据域，存储地址的地方被称为指针域。这样通过指针域来实现数据之间的连接，所以链式存储数据元素通常不在连续的内存地址上。

四、算法和算法效率的度量

4.1、算法

算法是一组指令，其目的就是针对确定的问题，用确定的指令解决该问题。算法本身是个非常容易理解的概念，而难的是具体某种算法。算法有以下几个特性：

1. 有穷性：即步骤是有穷的。
2. 确定性：即每一条指令都有确定的含义，不会产生歧义。
3. 可行性：这个我也就不解释了。
4. 有输入：这里的有输入并不一定需要输入，可以有0个输入，也可以有多个输入。
5. 有输出：一个算法需要有至少一个输出。虽然输出不会影响算法本身的正确性，但是对人来说输出是最直观的东西。

4.2、算法的设计

不同情况对算法的要求是不同的，通常情况下我们算法设计分为以下几个层次：

1. 正确：这是对算法最基本的要求，即输入合理的数据，可以得到预期的输出
2. 可读：即在算法正确的基础上，注意编码的规范，让程序易于解读
3. 健壮：有些算法在运行时，用户并不会输入程序员设想的数据。这个时候就需要程序员对这些极端数据，采取相应的措施。
4. 效率和存储：效率和存储是算法中一个非常值得重视的问题，但是同时又是一大难题。有时候需要舍弃效率节约存储，有时候需要舍弃存储提升速度。这也就是我们为什么要学习数据结构的原因。学习数据结构后，我们可以针对不同的情况，采取相应的数据结构，从而达到效率的最大化。

4.3、算法效率的度量

算法的效率度量有两个重要的数据，一个是运行时间的度量，一个是占用存储的度量，一个好的算法一定是要权衡两者哪个更重要，将效率最大化。

（1）事后分析法

事后分析法我们可以从字面意思来了解，就是我们运行完程序，然后看看这个程序到底花了多少时间。我们可以在运行开始获取一次时间，运行结束后再获取一次时间，再把时间相减就可以了。我简单演示一下，我们先编写一个获取时间的函数：

/**
*	获取当前时间的秒数
*/
int getNowSec(){time_t t;struct tm *p;time(&t);p = gmtime(&t);int sec = p->tm_sec;return sec;
}

这个该死的写法我也不解释了，我们只需要知道可以获取当前时间的秒数。然后我们测试一下：

int main(){//获取开始时间int t1 = getNowTime();//老版本C语言不支持这种写法for(int i = 0; i < 100000; i++){printf("this is a test sentence\n");}//获取结束时间int t2 = getNowTime();printf("it's spend %d\n", t2-t1);return 0;
}

我们这里输出了十万条语句，在我电脑上运行时间是9秒。

注意：如果是参加考试，不要将循环写成**for(int i = 0)**这种形式。

我们很容易发现，这种方法和在不同设备、不同环境中测试结果是不一样的，这种不确定的度量肯定是不可取的。

（2）渐进时间复杂度

渐进时间复杂度通常称为时间复杂度，使用这个方式度量时，我们通常将一条指令执行时间看成1，然后我们可以在执行算法之前对算法的执行时间有一个大概的估计。我们通常使用大O表示法来表示时间复杂度。大O表示法是一种通过问题规模表示一个算法的方式。

我们先看一个简单的算法：

void dis(int n){for(int i = 0; i < n; i++){printf("test\n");}
}

上述代码我们执行了n条输出语句，该算法的问题规模就是n，在实际执行时，这个算法一次循环应该会执行4条指令（for循环中三条），那他执行时间应该是4n，但是我们使用大O表示法通常不考虑系数，表示如下：

T=O(n)

我们再来看一个算法：

void dis(int n){//part1for(int i = 0; i < n; i++){for(int j = 0; j < n; j++){printf("test\n");}}//part2for(int i = 0; i < n; i++){printf("test\n");}
}

上面算法中我们有两个部分，第一部分是一个双重循环，该部分执行时间应该是n²（不考虑系数），第二部分是一个简单的循环，执行时间为n，按理我们的时间复杂度应该是：

T=O(n² + n)

但是我们用大O表示法时，只考虑最高次项，那么实际上应该写成如下：

T=O(n²)

另外，大O表示法还有一个规则，即只考虑最坏的情况，我们看如下算法：

void dis(int n){for(int i = 0; i < n; i++){for(int j = n; j > 0; j--){printf("test\n");}}
}

在这个算法中，内层循环是逐渐递减的其算法的执行时间如下：

n*(n-1)*(n-2)*.....1

但是我们写它的时间复杂度还是表示为：

T=O(n²)

除了我们上面说的n、n²外，还有一些其它的时间复杂度，常数、指数、对数等…

我们总结大O表示法有如下几个规则：

• 不考虑系数
• 只考虑最高次项
• 只考虑最坏的情况

另外，当一个算法执行时间是一个常数时，那么他的时间复杂度为O(1)。