数据结构

数据结构理论知识：

第一章  绪论

1.数据：所有能被计算机识别，储存和处理的符号的集合（包括数字，字符，声音，图像等信息）

2.数据结构：数据中的一个“个体”，具体完整的实际意义（又称元素，顶点，记录等），是数据的基本单位，在计算机中通常作作为一个整体处理和考虑。

3.数据项：构成数据元素的项目。是具有独立含义的最小标识单位（又称字段、域、属性等）。数据项是数据的最小单位。

备注：三者之间的关系：数据 > 数据元素  >  数据项

4.  数据对象：具有相同特征的数据元素的集合称为数据对象。如：字母数据对象、学生数据对象等。

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

    数据元素之间的相互关系称为结构。

数据元素之间的关系不同，结构不同。

也可以说：数据结构是带“结构”的数据元素的集合。

数据结构包括逻辑结构、物理结构（即存储结构）和对数据的操作三个方面、

6、数据的逻辑结构：

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

逻辑结构两要素：数据元素、关系

7、数据的物理结构 ：

    数据元素及其关系在计算机存储器内的表示，即数据的存储表示；它依赖于计算机。

数据元素之间的关系在计算机中的表示有顺序映像和非顺序映像，对应不同的存储结构：

l顺序存储结构：借助元素在存储器中的相对位置来表示它们之间的逻辑关系

l链式存储结构：借助指针来表示数据元素之间的逻辑关系。

›四种存储结构分别为：顺序、链式、索引、散列

8、数据类型

一组性质相同的值的集合, 以及定义在这个值集上的一组操作的总称。

9、抽象数据类型（ADT）

由用户定义，用以表示应用问题的数据模型。它由基本的数据类型构成，并包括一组相关的服务（或称操作）。

10.算法定义：算法是对问题求解步骤的一种描述，是指令的有限序列。

11.算法的5个重要特性：

1‘有穷性：一个算法必须在执行有穷步后结束，算法的每一步必须在有限的时间内完成

2’确定性：每一条指令必须有确切的含义，不会产生二义性，算法的执行者和阅读者都能明确其含义及如何执行

3’可行性：算法中的每一个操作都可以通过已经实现的基本操作执行有限次来实现

4‘有零个或多个输入：用函数描述算法时，往往通过函数的参数表获得

5’有一个或多个输出：

算法优劣的评价标准：

（1）正确性：能够满足应用需求

（2）可读性：思路清晰、简单明了，必要的地方加注释

（3）健壮性：对非法输入能够做出适当的处理

（4）高效性：时间高效性和空间高效性

算法分析

1‘算法的时间效率：

事后统计：利用计算机的计时功能

缺点：必须执行由算法编写的程序，受到软硬件因素的影响

事前分析估算；

2‘问题规模和语句频度

不考虑计算机的软硬件等因素，特定算法的效率取决于：问题的规模

问题规模是算法求解问题输入量的多少，是问题大小的本质表示，一般用整数n表示。

语句频度：一条语句重复执行的次数

  因此，算法的执行时间可以用算法中所有语句频度之和来度量

例题：

for(i=1; i<=n; i++)    频度为：n+1次

  for(j=1; j<=n; j++)    频度为：n*(n+1)次

  {

  c[i][j] = 0;                频度为：n^2次

  for(k=1; k<=n; k++)  频度为：n^2 *（n+1）次

  c[i][j] += a[i][k] * b[k][j] ;    频度为：n^3次

  }

所有语句频度之和f(n) = 2n3 + 3n2 + 2n + 1

缺点：太复杂，工作量太大

3.时间复杂度：

一般情况下，求算法的时间复杂度只需考虑问题规模充分大时，基本操作重复执行的次数关 于n的增长率即可，即在渐进意义下的阶（忽略所有低次幂，以及高次幂的系数）。

例题：  若语句频度 = 2n2 + 2n ，则时间复杂度为：        T(n)=O(n2)

4.常见的时间复杂度：

O(1)、O(n)、O(nk)、O(log n)、O(2n)

判断算法的效率那个高时，应考虑n趋于无穷大时。

时间复杂度T(n)按数量级递增顺序为：

算法的时间复杂度一般指最坏情况下的时间复杂度。

5、空间效率

渐进空间复杂度作为算法所需存储空间的度量，简称空间复杂度，它也是问题规模n的函数，记作：  S(n) = O(f(n))

一般情况下，只分析算法所需的辅助空间就可以了，不考虑程序本身所占空间和输入数据所占空间。

若所需辅助空间对于输入数据量而言是个常数，则称该算法为原地工作。