数据结构Ｃ语言版

大家好，欢迎来到IT知识分享网。

一． 绪论

总：程序=算法+数据结构

1.1基本术语

数据：是客观事物的符号表示，是所有能输入到计算机中并且被计算机程序处理的符号。

数据元素：数据的基本单位，在计算机中通常作为一个整体进行考虑和处理

数据项：是组成元素的、具有独立意义的不可分割的最小单位

数据对象：是性质相同的数据元素的集合，是数据的一个子集

1.2数据结构

数据结构：是相互之间存在一种或者多种特定关系的元素的集合。换句话说就是带有结构的数据元素的集合，结构指的是数据元素之间的关系

数据结构包括逻辑结构和存储结构两部分

逻辑结构是从逻辑关系上描述数据，它与数据的存储无关，即数学模型

逻辑结构层次图：

存储结构是数据对象在计算机中的存储表示，即物理结构

（1）  顺序存储结构：是借助在存储器中的相对位置来表示数据元素之间的逻辑关系，通常借助程序设计语言的数组来进行描述，存储过程是有顺序的

（2）  链表存储结构：顺序存储结构要求所有的元素依次存放在一片连续的存储空间里，而链式存储结构无需占用一整块存储空间，为了表示结点之间的关系，需要给每个结点附加指针字段，用于存放后继元素的存储地址。即：不仅要存储数据元素本身，还要存储关系信息（易修改）

1.3数据类型和抽象数据类型

数据类型是一个值的集合和定义在这个值集上的一组操作的总称

抽象数据类型一般指由用户定义的，表示应用问题的数学模型，具体包括三个部分：数据对象，数据对象关系的集合以及对数据对象的基本操作的集合

抽象数据类型的定义格式：

   ADT 抽象数据类型名{

       数据对象：{数据对象的定义}

       数据关系：{数据关系的定义}

       基本操作：{基本操作的定义}

}ADT 抽象数据类型名

1.4算法和算法分析

算法是为了解决某类问题而规定的一个有限长的操作序列

算法具备的五个重要的特性：

（1）  有穷性：执行的有穷步后结束

（2）  确定性：对于所执行的操作，都有明确的规定

（3）  可行性：对于所有操作都可以通过实现的基本操作运算执行有限次来实行

（4）  输入：一个算法有零个或者多个输入

（5）  输出：一个算法有一个或者多个输出

评定一个算法优劣的基本标准

（1）  正确性：合理的数据输入下，能够在有限的运行时间内得到正确答案

（2）  健壮性：当输入非法时，可以做出一些良好的处理

（3）  可读性：便于人们的理解和交流

（4）  高效性：时间高效（执行效率高）和空间高效（占存储容量合理）

衡量算法效率的方法主要有两类：事后统计法和事前分析估算法

一般情况下，算法中基本语句重复执行的次数是问题规模n的某个函数f(n)

算法的时间量度记作     T(n)=O(f(n))

它表示随问题规模n的增大，算法执行时间的增长率和f(n)的增长率相同，称做算法的渐进时间复杂度，简称时间复杂度。

算法的时间复杂度不仅与问题的规模有关，还与问题的其他因素有关，称算法在最好情况下的时间复杂度为最好时间复杂度，指的是算法计算量可能达到的最小值；称算法在最坏情况下的时间复杂度为最坏时间复杂度，指的是算法计算量可能达到的最大值。平均时间复杂度指的是算法计算量的加权平均值。

关于算法的存储空间需求，采用渐进空间复杂度作为算法所需空间存储的量度，简称空间复杂度。  S(n)=O(f(n))

对于一个算法而言，其时间复杂度和空间复杂度往往是相互影响的，当追求一个较好的时间复杂度时，可能会导致占用较多的存储空间，可能会使空间复杂度的性能变低，通常情况下，由于运算空间较为充足，人们通常时算法的时间复杂度作为算法优劣的标准。