数据结构一--------概念与算法

摘自：http://czk.8866.org/wiki/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E6%A6%82%E8%BF%B0

数据结构（包括逻辑结构，存储结构，运算）

算法（时间复杂度，空间复杂度）

1.计算机是一种处理数据的机器

输入=〉存储 =〉输出
        ||
       处理

2.算法+数据结构=程序

    * 数据结构：是指数据的逻辑结构和存储结构
    * 算法：是对数据运算的描述

解决非数值问题的关键不再是分析数学和计算方法，而是要设计出适当的数据结构来存储数据，并在此基础上设计出有效的算法，来对数据进行需要的处理。

非数值数据：这类数据的类型多样，比如：文字，图像，声音，视频等等。如何描述此类数据，并对此类数据进行有效的处理，成为了严峻的问题。解决此类问题的知识，被称为：数据结构。

3.数据结构中的基本概念
# 数据（Data）：是信息的载体。它能够被计算机识别、存储和加工处理，是计算机程序加工的“原料”。数据的范畴包括：整数、实数、字符串、图像和声音等。
# 数据元素（Data Element）是数据的基本单位。数据元素也称元素、结点、顶点、记录。一个数据元素可以由若干个数据项（也可称为字段、域、属性）组成。

数据元素之间的逻辑关系，也称数据的逻辑结构（Logical Structure）

数据的逻辑结构是从逻辑关系上描述数据，与数据的存储无关，是独立于计算机的。数据的逻辑结构可以看作是从具体问题抽象出来的数学模型。


性结构：若结构是非空集，则有且仅有一个开始结点和一个终端结点，并且所有结点都最多只有一个直接前趋和一个直接后继。线性表是一个典型的线性结构。栈、队列、字符串等都是线性结构。

非线性结构：一个结点可能有多个直接前趋和直接后继。树和图等数据结构都是非线性结构。

数据元素及其逻辑关系在计算机存储器内的表示，称为数据的存储结构（Storage Structure）

数据的基本存储结构

    * 顺序存储结构（Sequential Storage Structure）：该方法把逻辑上相邻的结点存储在物理位置上相邻的存储单元里，结点间的逻辑关系由存储单元的邻接关系来体现。通常借助程序语言的数组描述。该方法主要应用于线性的数据结构。非线性的数据结构也可通过某种线性化的方法实现顺序存储。
    * 链式存储结构（Linked Storage Structure）：该方法不要求逻辑上相邻的结点在物理位置上亦相邻，结点间的逻辑关系由附加的指针字段表示。通常借助于程序语言的指针类型描述。
    * 索引存储结构：该方法通常在储存结点信息的同时，还建立附加的索引表。索引表由若干索引项组成。索引项的一般形式是：(关键字、地址)。关键字是能唯一标识一个结点的那些数据项，地址指示结点所在的存储位置。
    * 散列存储结构：根据结点的关键字直接计算出该结点的存储地址。

最常用的检索、插入、删除、更新、排序等运算实际上只是在抽象的数据上所施加的一系列抽象的操作。所谓抽象的操作，是指我们只知道这些操作是"做什么"，而无须考虑"如何做"。只有确定了存储结构之后，才考虑如何具体实现这些运算。

数据结构就是指按一定的逻辑结构组成的一批数据，使用某种存储结构将这批数据存储于计算机中，并在这些数据上定义了一个运算集合。

数据的逻辑结构、数据的存储结构及数据的运算这三方面是一个整体。

存储结构是数据结构不可缺少的一个方面：同一逻辑结构的不同存储结构可冠以不同的数据结构名称来标识。【例】线性表是一种逻辑结构，若采用顺序方法的存储表示，可称其为顺序表；若采用链式存储方法，则可称其为链表；若采用散列存储方法，则可称为散列表。

数据的运算也是数据结构不可分割的一个方面：在给定了数据的逻辑结构和存储结构之后，按定义的运算集合及其运算的性质不同，也可能导致完全不同的数据结构。

4.算法和算法的度量

为了求解某问题，必须给出一系列的运算规则，这一系列的运算规则是有限的，表达了求解问题方法和步骤，这就是一个算法。 一个算法可以用自然语言描述，也可以用高级程序设计语言描述，也可以用伪代码描述。

五个重要特性

    * 有穷性：算法的执行必须在有限步内结束。
    * 确定性：算法的每一个步骤必须是确定的无二义性的。
    * 输入：算法可以有0个或多个输入。
    * 输出：算法一定有输出结果
    * 可行性：算法中的运算都必须是可以实现的。

评价算法的好坏
  主要考虑如下三点：
    * 执行算法所耗费的时间；
    * 执行算法所耗费的存储空间，其中主要考虑辅助存储空间；
    * 算法应易于理解，易于编码，易于调试等等。

算法的选择
   # 若该程序使用次数较少，则力求算法简明易懂；
   # 对于反复多次使用的程序，应尽可能选用快速的算法；
   # 若待解决的问题数据量极大，机器的存储空间较小，则相应算法主要考虑如何节省空间。

算法执行时间的分析

一个算法所耗费的时间=算法中每条语句的执行时间之和

每条语句的执行时间=语句的执行次数（频度）×语句执行一次所需时间

算法转换为程序后，每条语句执行一次所需的时间取决于机器的指令性能、速度以及编译所产生的代码质量等难以确定的因素。

若要独立于机器的软、硬件系统来分析算法的时间耗费，则设每条语句执行一次所需的时间均是单位时间，一个算法的时间耗费就是该算法中所有语句的频度之和。

问题规模和算法的时间复杂度

算法求解问题的输入量称为问题的规模，一般用一个整数表示。比如：矩阵乘积问题的规模是矩阵的阶数。

一个算法的时间复杂度T(n)是该算法的时间耗费，是该算法所求解问题规模n的函数。当问题的规模n趋向无穷大时，时间复杂度T(n)的数量级(阶)称为算法的渐进时间复杂度。


大O表示法

若T(n)和f(n)是定义在正整数集合上的两个函数，则T(n)=O(f(n))表示存在正的常数C和n0，使得当n≥n0时都满足0≤T(n)≤C·f(n)。

常见的时间复杂度按数量级递增排列依次为：常数0(1)、对数阶0(log2n)、线形阶0(n)、线形对数阶0(nlog2n)、平方阶0(n2)立方阶0(n3)、…、k次方阶0(nk)、指数阶0(2n)。显然，时间复杂度为指数阶0(2n)的算法效率极低，当n值稍大时就无法应用。

各种情况下的算法性能

    * 最坏情况下的时间复杂度称最坏时间复杂度，算法计算量达到最大值
    * 最好情况下的时间复杂度称最好时间复杂度，算法计算量最小
    * 算法在平均情况下的时间复杂度是指在所有可能的情况下的计算量经过加权平均后的平均值

算法的空间复杂度

算法所需空间包括：

    * 输入数据所占空间
    * 辅助变量所占空间
    * 程序所占空间

若输入数据所占空间只取决于问题本身，和算法无关，则只需要分析除输入和程序之外的辅助变量所占额外空间。

算法的时间复杂度和空间复杂度合称为算法的复杂度。