数据结构和算法概述

数据结构是什么

���据结构，就是数据存储的方式，为了使用数据我们通常会申请一块空间用来存储数据，比如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