[TOC]

数据结构概述

数据结构是指所有数据及这些数据之间的关系的集合

逻辑结构

数据元素之间的逻辑结构是多种多样的，根据数据元素之间的不同关系特性，通常可将数据逻辑结构分为4类，即集合、线性结构、树形结构和图状（或网状）结构

线性结构：该结构中的数据元素之间存在一对一的逻辑关系，并且起始元素和终端元素都是唯一的，除了这两个元素外，剩余的每一个元素都有且仅有一个在其之前和在其之后的元素

树形结构：该结构中的数据元素之间存在一对多的逻辑关系，并且除了起始元素外，其余每一个元素都有且仅有一个在其之前的元素，除了终端元素外，其余每一个元素都有一个或多个在其之后的元素

网状结构：该结构中的数据元素之间存在多对多的逻辑关系，每个元素都可能有一个或多个在其之前或在其之后的元素。在这一结构中可能没有起始元素和终端元素，也可能有多个起始元素和多个终端元素

存储结构

数据的存储结构是指数据在计算机中的表示（又称为映像）方法

存储时应包含两方面的内容——数据元素本身及数据元素之间的关系

总共包含四类：

顺序存储结构

采用一组物理上连续的存储单元来依次存放所有的数据元素

链式存储结构

每一数据元素均使用一个结点来存储，并且每个结点的存储空间是单独分配的，因此存储这些结点的空间不一定是连续的。

结点包含：数据域、指针域

索引存储结构

不仅需要存储所有数据元素（称之为主数据表），还需要建立附加的索引表。在存储时，每个数据元素都由一个唯一的关键字来标识，由该关键字和对应的数据元素的地址构成一个索引项，并将其存入索引表中

在查找数据元素时，首先由关键字的有序性，在索引表中查找出关键字所在的索引项，并取出该索引项中的地址，再依据此地址在主数据表中找到对应的数据元素。
哈希（或散列）存储结构

是指依据数据元素的关键字，通过事先设计好的哈希（或散列）函数计算出一个值，再将其作为该数据元素的存储地址

数据类型概述

类型是指一组值的集合，而数据类型则是指一组值的集合及定义在这组值上的一组操作的总称

计算机提供原子类型：“位”“字节”和“字”等，高级语言提供的数据类型。

python中的数据类型有：

数字：整型、浮点型、复数型
字符串
列表
元组：()一经创建，不可修改
集合：{}无序且不重复
字典：键值对

抽象数据类型

抽象数据类型（Abstract Data Type，ADT）是指一个数学模型及定义在该模型上的一组操作

ADT抽象数据类型名{

数据对象：<数据对象的定义>

数据关系：<数据关系的定义>

基本操作：<基本操作的定义>

}

基本操作名（参数表）

初始条件：<初始条件描述>

操作目的：<操作目的描述>

操作结果：<操作结果描述>

举例：复数

简单来说，就是对一个数据类型，比如int或自定义，进行抽象描述，不关心具体实现

算法概述

算法是对待特定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指令表示一个或多个操作。

算法应具备的特性
有穷性：一个算法对于任何合法的输入必须在执行有穷步之后结束，且每一步都可在有穷的时间内完成。
确定性：算法中每一条指令都必须具有确切的含义，不能有二义性，并且，在任何条件下，算法的任意一条执行路径都是惟一的，即对于相同的输入所得的输出相同。
可行性：是指算法中描述的操作都可以通过基本运算执行有限次操作来实现。
输入：有零个或多个输入，这些输入取自于某个特定对象的集合。
输出：零个或多个输出，这些输出是同输入有着某些特定关系的量。
衡量算法好坏
正确性：要求算法能够正确地执行，并满足预先设定的功能和性能要求。
可读性：算法主要是为了给人们阅读和交流的，其次才是在计算机上执行。
健壮性：当输入的数据不合法或运行环境改变时，算法能恰当地做出反应或进行处理，而不是产生莫名其妙的输出结果。
时间复杂度：对一个算法执行效率的度量。
空间复杂度：是指一个算法在执行过程中所占用的存储空间的度量。

算法的时间复杂度

算法的执行时间是通过依据该算法编写的程序在计算机上执行时所需要的时间来计算的

由于我们所使用的编程语言、计算机的硬件和软件等环境因素，难以得出一个绝对的时间，所以我们只考虑算法本身的问题规模

一个算法通常是由控制结构（顺序、分支和循环3种）和原操作（指固有数据类型的操作）构成的

假设问题规模为n，对应的函数关系记为T(n)，则算法的执行时间大致等于执行基本操作所需的时间×T(n)。

由于上述对算法执行时间的计算并不是该算法执行的绝对时间，因此通常进一步将算法的执行时间用T(n)的数量级来表示，记作T(n)=O(f(n))（其中O是数量级Order的缩写）。

总结来说，执行一次基本操作记为T(n)=1，0到n的循环则记为T(n)=n，一个算法的时间复杂度取决于T(n)的量级。

对于无循环的算法，它的量级是个常量，所以时间复杂度为O(1)

对于单循环的算法，它的量级最高为n，所以时间复杂度为O(n)

对于多重循环，例如双重循环，则为O(n^2)

对于有输入的算法，其时间复杂度还与输入数据集（一个或多个输入）有关，因为对于不同的输入数据集，算法的基本操作重复的次数可能不一样，即算法的时间复杂度可能也不一样。所以就有了最好时间复杂度、最坏时间复杂度和平均时间复杂度

算法的空间复杂度

算法的空间复杂度一般也认为是问题规模n的函数，并以数量级的形式给出

依据某算法编写的程序在计算机运行时所占用的存储空间包括以下部分：

输入数据所占用的存储空间
程序本身所占用的存储空间
临时变量所占用的存储空间

在对算法的空间复杂度进行研究时，只分析临时变量所占用的存储空间

总结

数据结构是相互之间存在一种或多种特定关系的数据元素的集合，通常包括数据的逻辑结构和存储结构两个层次，逻辑结构是从具体问题抽象出来的数学模型，是从逻辑关系上描述数据，并不涉及数据在计算机中的存储。根据数据元素之间关系特性的不同，通常分为4类基本的逻辑结构——集合、线性结构、树形结构和图状（或网状）结构。存储结构则是逻辑结构在计算机中的存储表示，大致有4类——顺序存储结构、链式存储结构、索引存储结构和哈希（或散列）存储结构。

数据类型是程序设计语言中固有的，每种数据类型包含一组值及定义在这组值上的一组操作。抽象数据类型则是由用户自己定义的，是实际问题的数学模型及定义在该模型上的一组操作，具体包括3个方面：数据对象，数据对象上关系的集合，以及对数据对象的基本操作的集合。

算法是为了解决特定问题而设计的方法。算法具有5个特性——有穷性、确定性、可行性、输入和输出。在评价一个算法的优劣时，可以考虑其正确性、可读性、健壮性、时间复杂度和空间复杂度。这里简要介绍了算法的时间复杂度和空间复杂度。