第1部分　教学内容指导

第1章　绪论

1.1　知识点分析

1.数据

数据是信息的载体，是对客观事物的符号表示。

2.数据元素

数据元素是对现实世界中某独立个体的数据描述，是数据的基本单位。数据元素也称为结点。

3.数据项

数据项是数据不可分割的、具有独立意义的最小数据单位，是对数据元素属性的描述。

数据、数据元素、数据项反映了数据组织的3个层次，即数据可以由若干个数据元素组成，数据元素又由若干数据项组成。

4.数据对象

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

5.数据结构

数据结构是相互之间存在一种或多种特定关系的数据元素的集合。简而言之，数据结构是指数据之间的关系，即数据的组织形式。数据结构包括以下三方面：

（1）数据的逻辑结构

数据元素之间的逻辑关系，称为数据的逻辑结构。即从逻辑关系上描述数据，它与数据的存储无关，是独立于计算机的。

线性结构是指数据元素之间存在“一对一”关系的逻辑结构，非线性结构是指数据元素之间存在“一对多”或“多对多”关系的逻辑结构。

（2）数据的存储结构

数据元素及其关系在计算机存储器内的表示，称为数据的存储结构，也称为数据的物理结构。数据的存储结构是数据的逻辑结构用计算机语言的实现，依赖于计算机语言。

（3）数据的运算

数据的运算是指对数据施加的操作。数据的运算是定义在数据的逻辑结构上的，而运算的实现则是在存储结构上进行的。

6.算法的描述和分析

数据的运算是通过算法来描述的，对于算法的说明可以使用不同的语言，对同一问题可以有不同的算法。

（1）时间复杂度

通常，把算法中所包含简单操作次数的多少称为算法的时间复杂度。但是，当一个算法比较复杂时，其时间复杂度的计算会变得相当困难。一般情况下，算法中原操作重复执行的次数是规模n的某个函数f（n），算法的时间复杂度T（n）的数量级可记作T（n）=O（f（n））。

算法的时间复杂度T（n）是该算法的时间消耗，一个算法的时间耗费就是该算法中所有语句的执行次数（频度）之和。当n→∞时（即当n相当大时），T（n）的数量级（阶），用O表示。由于limT（n）/f（n）=C，C是不为0的常数，所以T（n）=O（f（n））。其实，f（n）就是T（n）中最高阶的一项，是算法中最大的语句频度。

一般情况下，对于循环语句只需要考虑循环体中语句的执行次数，而忽略该语句中循环头的部分。有时，循环体中语句的频度不仅与问题规模n有关，还与输入实例等其他因素有关，此时可以用最坏情况下的时间复杂度作为算法的时间复杂度。

（2）空间复杂度

一个程序的空间复杂度是指程序运行从开始到结束所需要的存储空间。类似于算法的时间复杂度，我们把算法所需存储空间的量度，记作S（n）=O（f（n））。其中，n为问题的规模。在进行时间复杂度分析时，如果所占空间量依赖于特定的输入，一般都按最坏情况来分析。

程序运行时所需要的存储空间包括以下两部分：

①固定部分：主要包括程序代码、常量、变量、结构体变量等所占的空间。空间与所处理的数据大小和个数无关，或者说与问题事例的特征无关。

②可变部分：空间大小与算法在某次执行中处理的特定数据的大小和规模有关。