本文共 3065 字，大约阅读时间需要 10 分钟。

一 数据结构

1. 数据结构的基本概念

    1.1 数据结构中数据相关的基本概念

                 数据（Data）：数据是信息的载体，是描述事务客观属性的数，字符及所有能输入到计算机中并被计算机程序识别和处理的符号的集合。如数学计算中用到的整数和实数，文本编辑中用到的字符串，多媒体程序处理的图形，图像，声音及动画等通过特殊编码定义后的数据。

                 数据对象(Data Object)：是性质相同的数据元素的集合，是数据的一个子集。

                 数据元素(Data Element)：数据的基本单位，通常作为一个整体考虑和处理。

                 数据项(Data Item): 构成数据元素不可分割的最小部分。

           1.2 数据对象，数据元素，数据项的关系

           1.3 数据类型(Data Type)：数据类型是一个值的集合和定义在这个值集上的一组操作的总称。例如，C语言中的整型变量，其值集为某个区间上的整数（区间大小依赖于不同的机器），定义在其上的操作可以为加，减，乘，除，取模等算术运算。

                 原子类型：原子类型是指不可再分的值的集合和定义在集合上的操作。s如：int, char, float等。

                 结构类型：结构类型是指结构（多个原子类型值的组合）的集合和定义在集合上的操作。如 list，map，set等。

                 抽象数据类型（Abstract Data Type，ADT）：一般是指由用户定义的，表示应用问题的数学模型，以及定义在这个模型上的一组操作的总称，对于抽象数据类型，我们一般只是考虑其逻辑特性，内部具体的实现是不考虑的。其三要素为：数据对象，数据对象上关系的集合以及数据对象的基本操作的集合。

2. 数据结构的三要素（重点）

    从上述关系途中我们可以分析出，数据对象，数据元素以及数据项之间的关系，同时每条数据并不是都独立的，他们之间存在着某种关系（如学号01排在学号02的前面），这种相互关系我们就可以称之为结构。

    数据结构是相互之间存在一种或者多种特定关系的数据元素的集合。

    数据结构的三要素：逻辑结构，物理结构，数据的运算。

     2.1 逻辑结构

            逻辑结构是指数据元素之间的逻辑关系，从逻辑关系上来描述数据，独立于计算机，与计算机内部是存储数据是无关的。     

逻辑结构类型	逻辑结构	逻辑结构关系图	关系图解释
线性结构	线性表，栈，队列		A排在B的前面，B排在C的前面
非线性结构	集合		所有的数据除了在同一个集合之内外，无其他任何关系
	树形结构		树状结构是一对多的关系，A分别与B，C，D都有关系
	图状结构		图状结构也称为网状结构，是多对多的关系

              2.2 物理结构（存储结构）

                    物理结构是指数据结构在计算机内的表示，也称作为存储结构，它既包括数据本身的表示，也包括数据关系的表示。

物理（存储）结构类型	物理（存储）结构图示	结构解释
顺序存储（重点）		内存中的数据，计算机会将数据保存在一个一个的存储单元中，顺序存储是指逻辑上相邻的数据在物理存储上也相邻的。即数据a,b,c,d,e在逻辑上是相邻的，则地址addr0,addr1,addr2,addr3,addr4也是相邻的。当我们知道第一个元素的位置时，我们可以通过相邻的特性经过简单的运算就可知道相邻元素的存储位置。如果我们想要知道c的位置，当我门知道了a的位置后就可以通过简单的计算得到c的位置
链式存储（重点）		链式存储则是逻辑上相邻的数据在物理上是不相邻的。存放数据元素a的位置同时存储着下一个元素的地址，我们通过该地址将元素之间达到指针的效果，在链式存储当中每一个元素的物理存储单元位置是不确定的。但是我们是可以通过指针来确定不同元素的位置。如果我们想要知道c的位置时，当我们知道a元素指向下一个元素b的地址为addr7,然后通过b元素指向下一个元素c的地址为addr9来确定c元素的位置。
索引存储		索引存储在内存中不仅要保存每一个数据元素，还要建立一张索引表，在索引表中会有多个索引项，每个索引项中保存着关键字和该关键字查找数据对应的地址。当我们要查找c的位置时，我们通过关键字n找到了c的存储位置为addr8。索引存储在存储数据时要额外的存储索引表，所以要消耗更多的内存空间。
散列存储		散列存储也时hash存储，该存储方式是通过关键字的相应函数运算直接得到元素的存储地址。这种查找速度是比较快的。 如查找c是，通过关键字n的对应函数f(n)直接得到c的存储地址为addr8。

              2.3 数据的运算

                     运算包括运算的定义和实现，运算的定义针对逻辑结构，运算的实现针对存储结构。

二 算法和算法评估

1. 算法的基本概念

    算法是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每条指令表示一个或者多个操作。它是解决问题的一种方法或者一个过程，考虑如何将输入转换成输出，一个问题可以有很多个算法。

    此外程序是某种程序设计语言对算法的具体实现，程序可以是无穷的，且可以存在错误。

    1.1 算法的五个特性

          有穷性：有穷性是指一个算法要在有穷时间和有穷步骤内完成相应的操作。如果出现无限循环的语句就不能被称作算法。

          可行性：就是指该算法是实际可行的，也可以理解为每一个不操作都是可以通过有限次逻辑运算实现的。

          确定性：在算法中每一个语句，每一条指令都是具有确切的含义。且同样的输入要保证由同样的输出，不能产生二义性。

           一个算法必须有零个或者多个输出，同时必须有一个或者多个输出。

           算法可以使用伪代码或者程序语言来进行描述。

2. 算法效率的度量（重点）

            2.1 好算法的设计原则

                  正确性：算法应该能够正确的解决求解问题。

                  可读性：算法应该具有良好的可读性，以帮助人理解算法的实际内容，方便人们阅读掌握该算法。

                  健壮性：在输入非法数据时，算法能够适应的做出反应或进行相应的处理。

                  效率与存储量：效率是指算法执行时间，存储量需求是指算法执行过程中所需最大的存储空间。

            2.2 算法的时间复杂度 

                  语句的频度：该条语句可能重复的次数。

                  T(n) ：所有语句的频度之和，其中n为问题的规模。

                  时间复杂度：T(n) = O(f(n))，其中O表示T(n)与f(n)在n—>正无穷时为同阶无穷大（若lim T(n)=∞且lim f(n)=∞(f(x)在极限附近处必须满足f(x)不等于0），当lim [T(n)/f(n)]=c(c为实数)，称f(n)是T(n)的同阶无穷大）

                   时间复杂度可以分为：最好时间复杂度，最坏时间复杂度（往往用来分析一个算法）以及平均时间复杂度（求所有时间复杂度的等概率期望）。

             2.3 时间复杂度的运算

                   平均时间复杂度计算：不同时间复杂度 X 对应时间复杂度出现的概率之和。

                   加法规则：T(n) = T1(n) + T2(n) = O(f(n)) + O(g(n)) = O (max(f(n)，g(n)))。

                   乘法规则：T(n) = T1(n) + T2(n) = O(f(n)*O(g(n))) = O(f(n)*g(n ))(考虑同阶无穷大)

                   通常采用基本运算频度（即最深运算频度）来分析时间复杂度。

                   常见的时间复杂度：O(1)<O(log2^n)<O(n)<O(nlog2^n)<O(n^2)<O(n^3)<O(2^n)<O(n!)<O(n^n)

             2.4 算法的空间复杂度

                   算法消耗的存储空间，记为S(n) = O(g(n))

                   除了本身所用的指令，常数，变量和输入数据外，还需要一些数据进行操作的工作单元和存储为实现算法所需的一些信息的辅助空间。

                   算法原地工作是指算法所需辅助空间为常量，O(1)。

转载地址：http://frsiz.baihongyu.com/