镇楼图

数据结构是计算机的存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的的数据元素的集合。

１概念术语

数据结构中最基本的５个概念：数据、数据元素、数据项、数据对象、数据结构。

数据结构概念

数据：程序操作的对象，用于描述客观事物。数据的特点：１可以输入到计算机、２可以被计算机处理。

数据项：数据的最小单位。一个数据元素可以由若干数据项组成。

数据元素：是组成数据对象的基本单位。

数据对象：性质相同的数据元素的集合（类似于数组）。

结构：数据元素之间不是独立的，存在特定的关系。这些关系即是结构。

数据结构：数据对象中数据元素之间的关系。是一对一、一对多、还是多对多的关系。

数据结构分为逻辑结构和物理结构。

２逻辑结构

逻辑结构是指数据元素之间逻辑关系的一种数据结构，逻辑关系是指数据元素前后间关系，与数据元素本身和存储位置无关。逻辑结构包括：

集合结构

集合结构：数据元素同属一个集合，再无其它关系。

线性结构

线性结构：数据元素之间存在一对一的相互关系。

树形结构

树形结构：数据元素之间存在一对多的相互关系。

图形结构

图形结构：数据元素之间存在多对多的相互关系。

３物理结构

物理结构指数据的逻辑结构在计算机存储空间的有些话形式，也称为存储结构，一种数据结构的逻辑结构根据需要可以表示成多种存储结构，常用的存储结构有顺序存储、链式存储。

顺序存储

顺序存储结构：是指把数据元素存放在地址连续的存储单元里，其数据间的逻辑关系和物理关系是一致的。

链式存储

链式存储结构：借助指示数据元素存储地址的指针来表示数据元素之间的逻辑关系，所以链式存储单元可以是连续，也可以是不连续的，数据元素的存储关系并不能反映逻辑关系。

４抽象数据类型

4.1数据类型

数据类型：是指一组性质相同值的集合以及定义在此集合的一些操作的总称。

在Ｃ语言中，按照取值不同，数据类型可以分为两类：

原子类型：是不可以再分解的基本数据类型，包含整型、浮点型、字符型等。

结构类型：由若干类型组合而成，是可以再分解的，例如：整型数组就是由若干整型数据组成的。

4.2抽象数据类型

抽象数据类型：是指一个数学模型以及定义在该模型上的一组操作。例如：我们在编写计算机绘图软件系统时，经常会使用到坐标，也就是说，会经常使用（ｘ，ｙ）来描述横纵坐标。而在3D系统中，ｚ深度就会出现，既然这３个整型数字是始终出现在一起，那就可以定义成一个 Point 数据变量。

抽象数据类型可以理解成实际开发里经常使用的结构体和类；根据业务需求定义合适的数据以及动作。

５算法

算法：是解决特定问题求解步骤的描述，在计算机中表现为指令的有限序列，并且每条指令表示一个或多个操作。

5.1 算法与数据结构的关系

算法与数据结构的关系

什么是算法？算法是解决特定问题的求解步骤的描述。而数据结构就是在计算机中表示特定问题数据的一种形式。所以：

程序设计＝数据结构＋算法

5.2 两种算法之间比较

在学习Ｃ语言时，大家遇到的第一个算法问题便是：求解从１－Ｎ相加的结果，需最简单的办法则是使用Ｃ语言模拟１累加到Ｎ这个过程，从而得到结果。

第一种求和

这样的解决方案是算法吗？当然是的，这就是算法。但与此同时我们也许会想到使用等差数列来解决。例如：

第二种求和

对比以上两种方式，如果不仅仅是累积到一百，而是一千、一万，第一种方式显然需要计算机循环成千上万次才能得到结果，而第二种方式不管ｎ是多少，也只需要执行一些，显然比第一种要快的多。

5.3 算法定义

什么是算法？算法就是描述解决问题的方法。通过刚刚的例子，我们可以知道对于一个给定的问题，是可以有多种算法来解决的。

5.4 算法特性

算法必须具备几个基本特性：输入、输出、有穷性、确定性、可行性。

输入输出：输入输出很好理解，在解决问题时必须有已知条件，有些算法可以没有输入，但是必须有输出，不然没有结果，这个算法也就没用了。

有穷性：指的是算法必须在有限的步骤执行后自动结束需不会出现无限循环，且每一个步骤在可接受的时间内完成。

确定性：算法的第一个步骤都具有确定的含义，不能出现二义性；算法在一定条件下，只有一条执行路径，相同的输入只能有唯一的输出结果。

可行性：算法的第一步都必须是可行的，

5.5 算法设计要求

算法的设计要求：正确性、可读性、健壮性、时间效率高和存储时低。

5.6 算法效率衡量方法

习惯上将算法语句重复执行的次数作为算法的时间量度

我们在分析一个算法的运行时,重要的是把基本操作的数量与输入规模关联起来,即是基本操作的数量必须表示成输入规模的函数;

5.7 算法时间复杂度

时间复杂度 常用的时间复杂度

指数阶和阶乘阶等除非是非常小的n值，否测哪怕n只有100，都会千万噩梦般的运行时间，所以这种不切实际的算法时间复杂度，一般都不会考虑且讨论。

5.8 最坏情况与平均情况

例如：大家在查找一个ｎ个随机数字数组中的某个数字，最好的情况是第一个数字就是，那么算法的时间复杂度为O(1)。但也有可能这个数字就在最后一个位置上，也就是算法时间复杂度为O(n)。这是最坏的情况了，

假设ｎ＝６循环在第１次就可以找到它的位置！

假设ｎ＝１循环在第10次就可以找到它的位置！

平均复杂度

最坏的情况运行时间是一种保证，那就是运行时间将不会比这更坏了，在应用中，这是一种最重要的需求，熊掌除非特别指定，我们提到的运行时间都是最坏情况下的运行时间。

而平均运行时间也就是从概率的角度来看，这个数字在每个位置的可能性都是相同的，所以平均的查找时间为n/2次后会发现这个目标元素。

平均运行时间是所有情况中最有意义的，因为它是期望的运行时间。现实中平均运行时间都是通过一定数量的分析估算出来的。

对于算法的分析，一种方法就是计算所有情况的平均值，这种时间复杂度的计算方法称为平均时间复杂度。另一种方法是计算最坏的情况五时间复杂度，这种方法称为最坏时间复杂度。一般没有特殊情况下，都是指最坏时间复杂度。

5.9 算法空间复杂度

算法的空间复杂度通过计算算法所需要的存储空间实现，算法空间复杂度的计算公式记做：，其中ｎ为问题的规模，f(n)为语句关于ｎ所占存储空间的函数。

一般情况下，一个程序在机器上执行时，除了需要寄存本身所用的指令、常数、变量和输入数据外还需要一些对数据进行操作的辅助存储空间，其它对于输入数据所占的具体存储量取决于问题本身，与算法无关，这样只需要分析该算法在实现时所需要的辅助空间就可以了。

如果算法执行时所需要的辅助空间相对于输入数据量是一个常数，则这个算法辅助空间为O(1)。

注意：算法的空间复杂度指的并不是整个算法在内存占用空间，而是指该算法在实现时所需要的辅助空间就可以。