数据结构和算法概述

数据结构是什么

数据结构，就是数据存储的方式，为了使用数据我们通常会申请一块空间用来存储数据，比如int a;这样可以申请一块空间来存放一个整数，而int arr[10]则是申请了一块连续的空间来存放多个数据。

我们之前存储数据的时候并没有体现出数据之间逻辑关系,如我有以下数据:{小明，小红，小黑，小白}，其中小明是小红和小黑的父亲，而小黑又是小白和小蓝的父亲，关系图如下:

对于这种具有关系的数据如果用数组来存储可以存储但是看不出他们之间的逻辑关系，显然不行，对此种数据，数据结构提供了树结构来存储这种类型的数据。

数据结构它可以让我知道如何存储此类复杂关系的数据更利于后期对数据的使用

数据结构存储的结构：

如上我们知道数据结构就是存储数据的方式，数据结构大致包含如下几种存储结构:

线性表：

线性表存储结构一般都是一次排列的，基本上前面和后面都有数据（除了首元数和尾元素）具备"一对一"关系的数据就可以使用线性表存储。就像{1,4,6,7,9}这样的数据可以使用线性存储。线性表其实是顺序表和链表的统称因为他们的存储结构都跟线性类似。

顺序表:顺序表就是存储的位置按照顺序进行存储，如使用顺序表存储了数据:{1,3,5,2,8,5,9,0,7}，由于顺序表底层结构实现就是数组,存储图如下所示:

链表:顺序表存储数据的空间物理地址是连续的如上所示链表则不同，使用链表存储数据时，是随用随申请的，因此数据存储的位置是不在一块的，数据的存储位置是随机的。因此链表是使用指针来链接数据的，如给每一个链表一个指针用来指向下一块数据最后一块数据指向NULL(空)，这样就建立起了数据之间的关系了。如要使用链表存储数据{1,4,6,9}，结构图如下:

栈和队列:栈和队列是特殊的线性表，因为他们对线性表中的元素进出做了明确要求。

栈中的元素只能从线性表的一端进出(另一端封死)，遵循"先入后出"的原则， 即先进栈的元素后出栈，栈结构图如下:

图中是C最先进栈然后再试B和A,根据"先进后出"的原则,3个元素的出栈顺序应该是:A最先出栈然后是B，最后才是C。

队列中的元素只能从线性表的一端进，从另一端出，且要遵循"先入先出"的特点，即先进队列的元素也要先出队列。如下图所示:

队列里有3个元素，A，B，C，从队列中看C先进队列，然后B进，最后C进，根据"先进先出"的原则，3个元素出队列的顺序应该是C最先然后B，最后C。

树结构：

如要存储此类数据:{小明，小红，小黑，小白}，其中小明是小红和小黑的父亲，而小黑又是小白和小蓝的父亲这种复杂的关系就需要使用具有"一对多"关系型的数据，一个数据可以指向多个数据，就需要使用数据存储结构来存储，关系图如下:

图存储结构：

有些数据它不仅跟其他多种数据有关还有数据跟他有关所以要存储这种数据就要使用图结构来存储具有"多对多"关系的数据，如有五个城市他们分别通向其他四个城市他们之间的关系图如下:

怎么衡量一个算法

时间复杂度和空间复杂度:

什么是算法：

时间复杂度和空间复杂度可以用来衡量一个算法的运行效率的。而所谓算法其实就是解决问题的方法，同一个问题使用不同的算法，虽然得到的结果相同但是耗费的时间和资源肯定所有差异，如:计算1到100的和，可以使用1+2+3+......+98+99+100=5050次方法要一路计算上来耗费时间非常大还容易出错另一种方法如:50*100+50=5050此方法出错的概率低计算速度快。这就意味着解决问题的算法有很多种，我们就需要从中选择最后的那一个，那么该如何判断算法的好坏。

一个好的算法标准：首先它必须能彻底解决这个问题(准确性)，且根据编写出的程序在任何情况下都不能崩溃(健壮性)。

注意：程序和算法是完全不同的概念，算法是解决某个问题的想法，思路。而程序是在根据算法编写出来的真正可以运行的代码，如要输出一个数与另一个数的和那我们会使用+这个符号，最终完成相加，算法是解决一个问题想法 想法可以有多个，程序则是把这个想法实现。

程序的运行效率具体可以从2个方面来衡量，分别是:程序运行的时间，程序运行时所需内存的大小。

时间复杂度：

判断一个算法程序运行时间的多少并不是程序在计算机上运行所消耗的时间来度量，因为这有很多其他因素:不同计算机软硬件的差异，即使是同一台计算机，不同时间段其系统环境也不相同，程序运行时间可能会所影响导致数值的不准确。

一般来说一个算法并不能计算出它准确的运行时间，所用一般不使用准确值，而是根据每条语句的执行次数估算出大概的值从而来表示程序的运行时间。如下有一段简单的程序:

for(int i=0;i

{

        a++;                //从0到n-1，执行n次

}

可以看到程序中仅有2行代码，其中:

for循环从i的0一直逐增至n(循环退出的时候i值为n)，因此循序for循环语句执行了n+1次；而循环内部仅有一条语句，a++从i的值为0就开始执行，i的值每增1该语句就执行一次，一直到i的值为n-1，因此，a+语句一共执行了n次。

因此整段代码中所有语句共执行了(n+1)+n此，即2n+1次。

数据结构中，每条语句的执行次数，又被称为该语句的频段，整段代码的总执行次数，即整段代码的频度。

再如下一段代码:

for(int i=0;i

{

        for(int j=0;j

        {

                num++;                //n*m

        }

}

通过计算得到此程序的频度为(n+1)+n*(m+1)+n*m,简化后得2*n*m+2*n+1,不同程序的运行时间，在更多场景中比较最坏条件下程序的运行时间，以上为例，最坏条件即使当n，m都为无限大时此程序的运行时间。

要知道，当n，m都无限大时，我们完全可以认为n==m,这段:2*n*m+2*n+1可以简化成:2*+2*n+1,这就是最坏情况下的运行时间，也就是这个程序的频度。

如果要比较上述两端程序的运行时间，即比较2n+1和2*+2*n+1的大小，当n无限大时，前者要远远小于后者，如下图所示:

显然，第一段程序的运行时间更短，运行更快。

2n+1跟2*+2*n+1这样的频度，还可以简化，如2n+1当n无限大的时候在2n上+1并无意义，而且n无限大2n跟n的值是无限接近的，甚至给n*2也是不太重要的操作，因为n是无限大，2*n也是一样。

如此便可简化2*+2*n+1，当n无限大,1可以忽略，甚至对于指数级的2*来说，2*n,并无关紧要，甚至给乘2，也可以忽略。因此最终频度为:.

频度表达式可以用以下方式简化:

去掉频度表达式中，所有加法常数式子，如2+2n+1,变成2+2n；

如果表达式含有多项无限大的变量的式子，只保留一个拥有指数最高的式子，如2+2n简化为2;

如果最高项存在系数，且不为1，直接去掉系数，如2系数为2，简化为;

事实上，对于一个算法(或者一段程序)来说，其最简频度往往就是最深层次的循环结构中某一条语句的执行次数，如2n+1最简为n，实际上就是a++语句执行的次数，同样2+2n+1简化为,实际上就是最内存循环中num++语句的执行次数。

得到了最简频度的基础上，数据结构用O记法来表示算法，取最简之后的频度，至今已被大多数人采纳。格式如:O(频度)，上面第一段程程序的时间复杂度为O(n),第二段程序的时间复杂度为O().

如下采取了最坏频度作为时间复杂度，而在某些地方还可以用最好频度或者最坏频度下的平均值作为算法的频度时间复杂度。

O(1)常数阶)平方阶)(立方阶))(指数阶)

空间复杂度：

程序算法的空间复杂度，也常常用大O记法表示。

一个程序，运行过程中会占用大小不一的空间，如:程序代码本身占用的存储空间，程序如果需要输入和输出数据，也会占用存储空间，程序在运行过程中还会申请很多临时的存储空间。

程序自身所占用的空间取决于包含的代码量，如果要缩小这部分，就需要写程序的时候减少代码。

程序在运行过程中输入输出的数据，往往要由解决的问题而决定的，即使算法不同，程序输入输出所占用的存储空间也是相近的。

对算法的空间复杂度影响最大的还是程序运行过程中所申请的临时存储空间，不同算法的程序所需要申请的临时空间通常不同。

如下程序申请的空间大小有一个确定的值,申请的空间并不会发生变化:

int i;

scanf("%d",&n);

int arr[10];

如果将arr[10]变为arr[i]此时程序运行申请的临时空间，和i相关。

所以，如果程序所占的存储空间和输入的值无关，则该程序的空间复杂度就为O(1);反之，如果有关，则需要使用以下方法来判断他们之间的关系:

如果随着输入n的增大，程序申请的临时空间也称比例增长，则程序空间复杂度用O(n)表示；

如果随着输入n的增大，程序申请的临时空间成关系增长，则程序的空间复杂度用O()表示；

如果随着输入n的增大，程序申请的临时空间成关系增长，则程序空间复杂度用O()表示；

一个算法往往更注重时间复杂度，而空间复杂度只要在一个合理的范围之内就可以。

数据结构和算法的作用

通常，每个问题的解决都经过以下两步:

1.分析问题，从问题中提取出有价值的数据，将其存储。

2.对存储的数据进行处理，最终得出问题的答案。

数据结构可以负责解决第一个，即存储的问题，因为数据结构可以根据数据不同的逻辑结构和物理结构，优先选出最优的存储结构来存储数据。

而第二个，属于算法的职责，字面理解是解决问题的方法，我们知道在取决于解决相同问题的前提下，哪一种算法效率最高，这里的效率就是处理数据，分析数据的能力。

数据结构是用于解决数据存储问题，算法是思考如何利用存储的数据快速准确的解决问题，他们是不同的。

数据结构能让我们知道如何以更优的方式存储数据。数据结构包含的存储数据的思想，已经将所有可能都囊括其中，能解决99%有关数据存储的问题。