《数据结构——用C语言描述（第二版）》-宁正元-电子教案 第1章 绪论

第1章 绪论,1.1 什么是数据结构 1.2 基本概念和术语 1.3 数据类型和抽象数据类型 1.4 算法描述与算法评价,本章将介绍数据结构研究的对象、基本概念和术语、算法的概念及其描述方法（C语言描述）、数据类型以及抽象数据类型，并概述数据结构的发展概况及其在计算机科学中的地位。,第1章 绪 论,随着计算机应用领域的不断扩大，计算机处理的对象更多的是非数值计算问题，它们的数学模型无法用数学方程来进行描述，此时就必须建立相应的数据结构来进行描述，分析问题中所用到的数据是如何组织的，研究数据之间的关系如何，进而为解决这些问题设计出合适的数据结构。,1.1 什么是数据结构,例1 职工信息管理,图1.1 职工花名册表,将每位职工的信息组织成如图1.1所示的花名册。花名册中每个职工的信息由编号、姓名、性别、年龄、月收入等项目组成，占表的一行，表中的结点和结点之间是一种简单的线性关系,这就是上述花名册表的线性逻辑结构。当用计算机对上述花名册表中的数据进行运算时，就要考虑那些结点在计算机中的存储表示，即存储结构。另外，还必须考虑如何进行结点的插入、删除、修改、检索或查找，这就涉及到数据的运算,例2 旅游交通网络图 如图1.2所示，为一个旅游交通网络咨询系统，可采用一种称之为图的结构来表示实际的交通网络， 此时，这个交通网络图就表示一个数据结构。在这个数据结构中，结点之间的关系可以是任意的，图中任意两个结点之间都可以相关。同样，必须考虑构造后将这张图存放入计算机中，这就要涉及到图的存储结构问题，以及图的运算。 从以上例子可见，要描述诸如此类的非数值计算问题的数学模型，涉及到一些诸如表、图还有树之类的数据结构。 数据结构课程实际上是一门研究非数值计算问题的程序设计中计算机的操作对象以及它们之间的关系和运算操作等的一门学科。在计算机科学中，数据结构不仅是一般程序设计（特别是非数值计算的程序设计）的基础，而且是设计和实现编译程序、操作系统、数据库系统及其它系统程序和大型应用程序的重要基础。,数据是指信息的载体，是对客观事物的符号表示，是对有效地输入到计算机中并能被计算机程序处理的符号的总称。如声音、图形、图像。 数据元素是数据的基本单位，数据项是数据的不可分割的最小单位。有时也称之为结点、元素、顶点、记录等。一个数据元素可由若干个数据项组成，如上面职工花名册中的每个人的信息就是一个数据元素，而每个人的信息包括编号、姓名、性别、年龄、月收入等，这每一个项目就属于数据项。,1.2 基本概念和术语,数据对象是性质相同的数据元素的集合，是数据的一个子集。 数据类型（数据类型）是对在计算机中表示的同一数据对象及其在该数据对象上的一组操作的总称。 数据类型有时还分为原子数据类型和结构数据类型。 数据结构指的是数据及数据之间的相互关系。一般地，数据结构包括以下三个方面的内容： （1）数据元素之间的逻辑关系，有时也称为数据的逻辑结构。 （2）数据元素及其关系在计算机内存中的表示（又称为映象），称之为数据的物理结构，又称为数据的存储结构，它包括数据元素的表示和数据元素之间关系的表示。 （3）数据的运算及实现，即对数据元素可以施加的操作及其这些操作在相应的存储结构上的实现。,数据的逻辑结构是从逻辑关系上描述数据，可以看作是从具体问题抽象出来的数学模型。如上例中的职工花名册表。根据数据元素之间的不同特性，通常有下列四类基本逻辑结构： （1）线性结构：结构中的数据元素存在一个对一个的关系，即所谓的线性关系。 （2）树型结构：结构中的数据元素之间存在一个对多个的关系，是结点之间有分支、并具有层次关系的结构，它非常类似于自然界中的树。 （3）图或网状结构：该结构中的数据元素之间的关系存在多个对多个的关系，如交通网络图就是一个图状结构。 （4）集合：结构中的数据元素之间除了“同属于一个集合”的相互关系外，别无其它关系。 有时将树形结构、集合和图或网状结构称为非线性结构，此时数据逻辑结构就可分为线性结构和非线性结构两类。,数据的存储结构是指逻辑结构用计算机语言的实现，就是数据元素及其关系如何存放入计算机内存的问题。一般地，数据的存储结构可按以下四种基本存储方法而得到： （1）顺序存储方法：是把逻辑上相邻的结点存储在物理位置上相邻的存储单元中，结点间的逻辑关系由存储单元的相邻关系而体现。由此得到的存储表示称为顺序存储结构，通常可借助计算机语言的数组来描述。 （2）链状存储方式：不要求逻辑上相邻的结点在物理位置上也相邻，数据元素可以存储在任意位置。为了实现数据元素之间逻辑关系的存储，必须通过一些附加的手段来存储这种相互关系，由此得到的存储表示称为链状存储结构。一般可以用指针来实现，通常可借助计算机程序语言的指针类型或者游标来来描述。,（3）索引存储方法：该方法通常是在存储结点信息的同时，建立附加的索引表。索引表一般有稠密索引和稀疏索引两种。 （4）散列存储方法：该方法是依据结点的关键字直接计算出该结点的存储地址，而后将结点按某种方式存入该地址的一种存储方法。 数据的运算是指定义在数据的逻辑结构上的一组操作的集合。例如，检索（查找）、插入、删除、定位、修改、排序等。要注意的是，这些运算实际上是在逻辑结构上对抽象数据所施加的一系列抽象的操作，运算的实现依赖于所选取的存储结构，是依赖于不同的计算机程序设计语言的。,数据类型是具有相同性质的计算机数据的集合及在这个数据集合上的一组运算。 在高级程序语言中，数据类型可以分为原子类型和结构类型。原子类型即值不可分解的类型，如C语言中的整型、字符型、实型、指针类型等；而结构类型则指的是其值可由若干成分按某种结构组成的类型，是可以分解的，如C语言中提供的结构体。 抽象数据类型（ADT）是指一个数学模型及定义在该数学模型上的一组操作。抽象数据模型的定义取决于它的一组逻辑特性，与其在计算机内部如何表示和实现无关。,1.3 数据类型和抽象数据类型,算法是对特定问题求解方法和步骤的一种描述，它是指令的一组有限序列。一个算法必须具备以下五个重要特性： （1）输入：一个算法必须具有零个或多个的外界输入。 （2）输出：一个算法必须有一个或多个的输出。 （3）有穷性：一个算法对任何合法的输入值必须总是在执行有穷步之后结束，并且每步都必须在有穷时间内完成。利用这一点，我们可以区别算法与程序。 （4）确定性：算法中每一条指令必须有确切的含义，不会产生二义性。 （5）可行性：算法中描述的操作都必须可以通过已经实现的基本运算有限次执行来实现，而且算法必须在有限时间内完成。 一个算法可以用自然语言、数学语言或约定的符号来描述，也可用计算机高级程序语言来描述，如PASCAl语言、C语言、C、Java或伪代码等。本书选用C语言作为描述算法的工具。,1.4.1 算法描述,1.4 算法描述与算法评价,1.4.2 算法的设计要求,设计一个好的算法可以从以下几个方面考虑： （1）正确性。算法是为了针对解决具体问题而提出的，算法的正确与否必须满足解决实际问题的需要，要经得起一切可能的输入数据的考验。 （2）可读性。算法要让人阅读得懂，程序要尽可能地简单通俗，当然也必须有效。 （3）健壮性。当输入数据非法时，算法应能适当地作出反应或进行处理。 （4）高效率。要求算法的执行时间要尽可能地短，对于存储空间要尽可能地少，即做到既省时又节省空间。 要设计一个好的算法，必须对这几个方面综合考虑，才可以设计出较好较优的算法。,考虑算法的效率应从下几个方面考虑： （1）时间效率。考虑算法所耗费的运行时间。 （2）空间效率。考虑运行算法需要耗费的存储空间，其中主要考虑算法所需的辅助存储空间。 （3）算法应尽可能地简单，易于理解，易于编码和调试并能得出正确结果。 一个算法的运行时间是指一个算法在计算机上运行所耗费的时间。它可以认为是算法中每条语句的执行时间之和。,1.4.3 算法的评价,例如，两个n×n矩阵相乘的算法： for（i=1；i=n；i+） /* n+1次 */ for（j=1；j=n；j+） /* n（n+1）次*/ ci j = 0； /* n×n次 */ for（k=1；k=n；k+） /* n2（n+1）次*/ ci j = ci j + i k * b k j；/* n*n*n次*/ 上述算法的时间耗费T(n)为： T（n）= 2n3 + 3n2 + 2n + 1 当n时，T(n)/n32，表示当n充分大时，T(n)与n3是同阶或者说同数量级，它是矩阵的阶数n的函数。 若引入大“O”记号，则T(n)可记作：T(n)= O(n3) ，此时称T(n)= O(n3)是求解矩阵相乘这个特定问题的渐近时间复杂度。有时将一个算法的渐近时间复杂度O(n)=O(f(n)认为就是时间复杂度。 常见的时间复杂度按数量级递增排列，依次为：常数阶O(1)，对数阶O(log2n)，线性阶O(n)，线性对数阶O(nlog2n)，平方阶O(n2)，立方阶O(n3)，指数阶O(2n)等等。,有时，可以依据算法转化为程序时各个语句的特点，利用一些简单的程序分析法则进行简单算法分析： （1）对于一些简单的输入、输出语句或赋值语句，它们执行时，近似认为需要O(1)时间； （2）对于顺序结构，需要依次执行一系列语句所用的时间可采用大O下的“求和法则”进行估计； （3）对于选择结构，如如果语句，它的主要时间耗费是在执行然后子句或别的子句所花费的时间，但须注意检验条件也还需要用O(1)的时间； （4）对于循环结构，循环语句的运行时间主要体现在多次迭代中执行循环体以及检验循环条件的时间耗费，一般地可用大O下的“乘法法则”进行估计； （5）对于复杂的算法，可以将它分成几个容易估算的部分，然后利用大O的求和法则和乘法法则计算整个算法的时间复杂度。,衡量一个算法好坏的另一个因素是程序运行时所占用的存贮空间大小。 度量一个算法在运行或执行过程中所占用的存储空间的大小类似于时间复杂度，可以用空间复杂度来度量。算法的空间复杂度一般也以相对于问题规模的数量级的形式给出，如O(1)，O(n)等。,