数据结构介绍 #
基本概念 #
- 数据：是对客观是的抽象表述，在计算机中是指能输入到计算机中并被计算机架构的一切信息的总称
- 数据元素：是数据的基本单位，是一个数据整体中可标识和访问的数据个体。数据和数据元素是相对而言的。
- 数据对象：相同特性的数据元素的集合，是数据的一个子集。
何为数据结构 #
数据结构是一门研究怎样合理组织数据，建立合适的数据存储结构，提高计算机程序执行效率的学科。数据结构主要研究下面翻个方面的内容：
-
数据元素之间的逻辑关系，也称数据的逻辑结构
逻辑结构分为四种，图形结构，线性结构（顺序存储和链式存储），树状结构，集合结构。
-
数据元素及其关系在计算机存储器内的表示，成为数据存储的结构或物理结构
-
数据的运算，即对数据施加的操作
逻辑结构与存储结构 #
逻辑结构：数据元素之间的逻辑关系的描述 , B = (K, R)
存储结构(物理结构)：数据元素在计算机中的存储及其逻辑关系的表述
数据结构形式上的定义是一个二元组
算法 #
算法： 是特定问题求解的方法（步骤）的一种描述，是指令的优先序列，其中每一条指令表示一个或多个操作。算法有五大特征：
有穷性：一个算法总是在执行有穷步后结束
可读性：算法应容易供人阅读和交流
健壮性：算法应有容错处理。输入非法或者错误数据时，算法应能适当的做出反应或进行处理，不会产生莫名其妙是输出结果。
效率和存储量的需求：效率是指算法执行的时间，存储量需求是指算法执行过程中所需要的最大存储空间，一般的，这二者与实际问题的规模有关。
算法效率的度量 #
算法时间复杂度 #
算法执行时间需要通过依据该算法编制的程序在计算机上执行的时间来度量。
时间复杂度是由 嵌套最深层语句 执行的频度而决定。
一般情况下，随着N的增大，时间复杂度（T(N)）增长最慢的算法是最优秀算法。显然算法指数阶算法效率极低。
算法空间复杂度 #
算法空间复杂度是指伏安法编写成层序后，在计算机中运行时收取的存储空间的大小的度量。
记作：S(n) = O(n)