《C语言程序设计与数据结构》课件第12章

1、C语言程序设计与数据结构第第12章章 数据结构绪论数据结构绪论教学目标：通过本章的学习，使读者能够掌握数据结教学目标：通过本章的学习，使读者能够掌握数据结 构的概念和有关的术语。构的概念和有关的术语。 C语言程序设计与数据结构12.1 什么是数据结构 计算机科学技术的广泛应用已从传统的数值计计算机科学技术的广泛应用已从传统的数值计算领域发展到各种非数值计算领域。为了有效地处算领域发展到各种非数值计算领域。为了有效地处理数据，需要为数据建立一定的结构，描述所处理理数据，需要为数据建立一定的结构，描述所处理的对象的特性以及各对象之间的关系。的对象的特性以及各对象之间的关系。 数据结构这门学科主要是

2、研究各种结构、定义数据结构这门学科主要是研究各种结构、定义在各种结构上的操作和这些操作在计算机中的实现在各种结构上的操作和这些操作在计算机中的实现方法。方法。 C语言程序设计与数据结构用计算机解决一个具体问题时要考虑以下步骤 (1)(1)从具体问题中抽象出一个适当的数学模型。即从从具体问题中抽象出一个适当的数学模型。即从具体问题中找出操作对象之间含有的关系，然后具体问题中找出操作对象之间含有的关系，然后用数学语言加以描述。用数学语言加以描述。(2)(2)设计一个适合该数学模型的算法（设计一个适合该数学模型的算法（Algorithm）。）。(3)(3)编写程序。编写程序。 (4) 进行测试、调整

3、、修改，直至解决问题。进行测试、调整、修改，直至解决问题。 所以，数据结构是研究程序设计中计算机操所以，数据结构是研究程序设计中计算机操作的对象以及它们之间的关系和运算的一门学科。作的对象以及它们之间的关系和运算的一门学科。 C语言程序设计与数据结构实际问题中，各个对象之间的关系有：实际问题中，各个对象之间的关系有：线性的：线性的：列车中各车箱之间的关系，排队买车票列车中各车箱之间的关系，排队买车票的人之间的关系，一叠盘子中各盘子之间的关系都的人之间的关系，一叠盘子中各盘子之间的关系都是线性的。是线性的。 层次的：在军队的编制中，军下面是师，师下面是层次的：在军队的编制中，军下面是师，师下面是

4、团，军、师、团之间是层次关系；在人的辈分关系团，军、师、团之间是层次关系；在人的辈分关系中，祖辈下是父辈，父辈下是子辈，这些是层次关中，祖辈下是父辈，父辈下是子辈，这些是层次关系；在学校的编制中，学校分成若干个学院、学院系；在学校的编制中，学校分成若干个学院、学院下又分成若干个系、系下又分成若干个教研室，这下又分成若干个系、系下又分成若干个教研室，这些也都是层次关系。些也都是层次关系。 网状的：在城市铁路交通图中，各城市之间的关系网状的：在城市铁路交通图中，各城市之间的关系是网状关系。在电话网中，各电话之间是网状关系。是网状关系。在电话网中，各电话之间是网状关系。 对象之间的关系C语言程序设计

5、与数据结构12.2 基本概念和术语基本概念和术语 数据数据 数据是人们利用文字符号、数字符号以及其他规定数据是人们利用文字符号、数字符号以及其他规定的符号对现实世界的事物及其活动所做的描述。在的符号对现实世界的事物及其活动所做的描述。在计算机科学中，数据的含义非常广泛，我们把一切计算机科学中，数据的含义非常广泛，我们把一切能够输入到计算机中并被计算机程序处理的信息，能够输入到计算机中并被计算机程序处理的信息，包括文字、表格、图象等，都称为数据。包括文字、表格、图象等，都称为数据。 C语言程序设计与数据结构数据举例一个个人书库管理程序所要处理的数据可能是一张如一个个人书库管理程序所要处理的数据可

6、能是一张如表所示的表格。表所示的表格。C语言程序设计与数据结构结点 结点也叫数据元素，它是组成数据的基本单结点也叫数据元素，它是组成数据的基本单位。在程序中通常把结点作为一个整体进行考虑和位。在程序中通常把结点作为一个整体进行考虑和处理。例如，在上表所示的个人书库中，为了便于处理。例如，在上表所示的个人书库中，为了便于处理，把其中的每一行（代表一本书）作为一个基处理，把其中的每一行（代表一本书）作为一个基本单位来考虑，故该数据由本单位来考虑，故该数据由10个结点构成。个结点构成。 一般情况下，一个结点中含有若干个字段一般情况下，一个结点中含有若干个字段（也叫数据项）。例如，在上表所示的表格数据

7、中，（也叫数据项）。例如，在上表所示的表格数据中，每个结点都有登录号、书号、书名、作者、出版社每个结点都有登录号、书号、书名、作者、出版社和价格等六个字段构成。和价格等六个字段构成。 字段是构成数据的最小单位。字段是构成数据的最小单位。C语言程序设计与数据结构逻辑结构 结点和结点之间的逻辑关系称为数据的逻辑结构。结点和结点之间的逻辑关系称为数据的逻辑结构。 在上表所示的表格数据中，各结点之间在逻辑在上表所示的表格数据中，各结点之间在逻辑上有一种线性关系，它指出了上有一种线性关系，它指出了10个结点在表中的排个结点在表中的排列顺序。根据这种线性关系，可以看出表中第一本列顺序。根据这种线性关系，可

8、以看出表中第一本书是什么书，第二本书是什么书，等等。书是什么书，第二本书是什么书，等等。 C语言程序设计与数据结构存储结构 数据在计算机中的存储表示称为数据的存储结构。数据在计算机中的存储表示称为数据的存储结构。 在上表所示的表格数据在计算机中可以有多在上表所示的表格数据在计算机中可以有多种存储表示，例如，可以表示成数组，存放在内种存储表示，例如，可以表示成数组，存放在内存中；也可以表示成文件，存放在磁盘上，等等。存中；也可以表示成文件，存放在磁盘上，等等。 C语言程序设计与数据结构数据处理 数据处理：是指对数据进行查找、插入、删除、合数据处理：是指对数据进行查找、插入、删除、合并、排序、统计

9、以及简单计算等的操作过程。并、排序、统计以及简单计算等的操作过程。例：例：从数据结构从数据结构S中找出满足条件的结点在中找出满足条件的结点在 S 中位置的中位置的运算是型运算。运算是型运算。从数据结构从数据结构S S中读出结构中指定位置上内容运算是中读出结构中指定位置上内容运算是型运算。型运算。 从数据结构从数据结构S S中修改结构中某指定结点内容的运算中修改结构中某指定结点内容的运算是型运算。是型运算。 C语言程序设计与数据结构数据结构（Data Structure） 数据结构：是研究数据元素（数据结构：是研究数据元素（Data Element）之间之间抽象化的相互关系和这种关系在计算机中的

10、存储表抽象化的相互关系和这种关系在计算机中的存储表示（即所谓数据的逻辑结构和物理结构），并对这示（即所谓数据的逻辑结构和物理结构），并对这种结构定义相适应的运算，设计出相应的算法，而种结构定义相适应的运算，设计出相应的算法，而且确保经过这些运算后所得到的新结构仍然是原来且确保经过这些运算后所得到的新结构仍然是原来的结构类型。的结构类型。 为了叙述上的方便和避免产生混淆，通常我们为了叙述上的方便和避免产生混淆，通常我们 把数据的逻辑结构统称为数据结构；把数据的物理把数据的逻辑结构统称为数据结构；把数据的物理结构统称为存储结构（结构统称为存储结构（Storage Structure）。）。 C语言

11、程序设计与数据结构数据类型数据类型 数据类型是指程序设计语言中各变量可取的数数据类型是指程序设计语言中各变量可取的数据种类。数据类型是高级程序设计语言中的一个基据种类。数据类型是高级程序设计语言中的一个基本概念，它和数据结构的概念密切相关。本概念，它和数据结构的概念密切相关。 一方面，在程序设计语言中，每一个数据都属一方面，在程序设计语言中，每一个数据都属于某种数据类型。类型明显或隐含地规定了数据的于某种数据类型。类型明显或隐含地规定了数据的取值范围、存储方式以及允许进行的运算。可以认取值范围、存储方式以及允许进行的运算。可以认为，数据类型是在程序设计中已经实现了的数据结为，数据类型是在程序设

12、计中已经实现了的数据结构。构。 另一方面，在程序设计过程中，当需要引入另一方面，在程序设计过程中，当需要引入某种新的数据结构时，总是借助编程语言所提供的某种新的数据结构时，总是借助编程语言所提供的数据类型来描述数据的存储结构。数据类型来描述数据的存储结构。 C语言程序设计与数据结构算法 简单地说就是解决特定问题的方法。特定的简单地说就是解决特定问题的方法。特定的问题可以是数值的，也可以是非数值的。问题可以是数值的，也可以是非数值的。解决数值问题的算法叫做数值算法，科学和工程计解决数值问题的算法叫做数值算法，科学和工程计算方面的算法都属于数值算法，如求解数值积分，算方面的算法都属于数值算法，如求

13、解数值积分，求解线性方程组、求解代数方程、求解微分方程等。求解线性方程组、求解代数方程、求解微分方程等。解决非数值问题的算法叫做非数值算法，数据处理解决非数值问题的算法叫做非数值算法，数据处理方面的算法都属于非数值算法。例如各种排序算法、方面的算法都属于非数值算法。例如各种排序算法、查找算法、插入算法、删除算法、遍历算法等。查找算法、插入算法、删除算法、遍历算法等。 数值算法和非数值算法并没有严格的区别。数值算法和非数值算法并没有严格的区别。 C语言程序设计与数据结构12.3 算法和算法的描述算法和算法的描述 算法是执行特定计算的有穷过程。这个过程有算法是执行特定计算的有穷过程。这个过程有5个

14、特点：个特点：（1）动态有穷：当执行一个算法时，不论是何种情动态有穷：当执行一个算法时，不论是何种情况，在经过了有限步骤后，这个算法一定要终止。况，在经过了有限步骤后，这个算法一定要终止。 （2）确定性：算法中的每条指令都必须有确切的确定性：算法中的每条指令都必须有确切的含义，不能有二义性。含义，不能有二义性。 （3）输入：具有输入：具有0个或个或0个以上由外界提供的输入个以上由外界提供的输入量。量。 （4）输出：产生输出：产生1个或多个结果。个或多个结果。 （5）可行性：算法中描述的操作都是可以通过已可行性：算法中描述的操作都是可以通过已经实现的基本运算执行有限次来实现的。经实现的基本运算执

15、行有限次来实现的。 C语言程序设计与数据结构算法的描述 一个算法可以用自然语言、数字语言或约定一个算法可以用自然语言、数字语言或约定的符号来描述，也可以用计算机高级程序语言来描的符号来描述，也可以用计算机高级程序语言来描述，如述，如Pascal语言、语言、C语言或伪代码等。语言或伪代码等。 本书选用本书选用C语言作为描述算法的工具。语言作为描述算法的工具。 C语言程序设计与数据结构算法评价 设计一个好的算法应考虑以下几个方面：设计一个好的算法应考虑以下几个方面：正确性正确性 运行时间运行时间 占用的存储空间占用的存储空间 简单性简单性 C语言程序设计与数据结构正确性 “正确正确”的含义在通常的

16、用法中有很大的差别，的含义在通常的用法中有很大的差别，大体可分为以下四个层次：大体可分为以下四个层次：程序不含语法错误；程序不含语法错误；程序对于几组输入数据能够得出满足规格说明要求程序对于几组输入数据能够得出满足规格说明要求的结果；的结果；程序对于精心选择的典型、苛刻而带有刁难性的几程序对于精心选择的典型、苛刻而带有刁难性的几组数据能够得出满足规格说明要求的结果；组数据能够得出满足规格说明要求的结果；程序对一切合法的输入数据都能产生满足规格说明程序对一切合法的输入数据都能产生满足规格说明要求的结果。要求的结果。 C语言程序设计与数据结构运行时间 运行时间是指一个算法在计算机上运算所花费的时间

17、。运行时间是指一个算法在计算机上运算所花费的时间。它大致等于计算机执行一种简单操作（如赋值操作、转向它大致等于计算机执行一种简单操作（如赋值操作、转向操作、比较操作等等）所需要的时间与算法中进行简单操操作、比较操作等等）所需要的时间与算法中进行简单操作次数的乘积。通常把算法中包含简单操作次数的多少叫作次数的乘积。通常把算法中包含简单操作次数的多少叫做算法的时间复杂性，它是一个算法运行时间的相对量度。做算法的时间复杂性，它是一个算法运行时间的相对量度。 在算法分析中绝对的量不能反映时间复杂度，使用一在算法分析中绝对的量不能反映时间复杂度，使用一个函数个函数(n)表示一个算法的复杂度。一个算法所解

18、决问题表示一个算法的复杂度。一个算法所解决问题的规模的规模n增大时，时间的增长率越小，时间复杂度越好，反增大时，时间的增长率越小，时间复杂度越好，反之时间复杂度越坏。也就是说，时间复杂度是之时间复杂度越坏。也就是说，时间复杂度是n的一个函数。的一个函数。 从好到坏表示时间复杂度的函数依次是：常量从好到坏表示时间复杂度的函数依次是：常量阶阶O(1)；对对数阶数阶O(log n)；线性阶线性阶O(n)；平方阶平方阶O(n2 )；多项式阶多项式阶O(nk)；指数阶指数阶O(2n)等。等。 C语言程序设计与数据结构时间复杂度举例下列三段程序的时间复杂度分别是：下列三段程序的时间复杂度分别是： x+;s

19、=x+2; 时间复杂度为时间复杂度为(1) for(k=1;k=n;k+) s=k+2: 时间复杂度为时间复杂度为(n) for (k=1;k=n; k+) for(j=1;j=n;j+) s=k+j: 时间复杂度为时间复杂度为(n2) C语言程序设计与数据结构占用的存储空间 一个算法在计算机存储器上所占用的存储空一个算法在计算机存储器上所占用的存储空间，包括存储算法本身所占用的存储空间，算法的间，包括存储算法本身所占用的存储空间，算法的输入、输出数据所占用的存储空间和算法运行过程输入、输出数据所占用的存储空间和算法运行过程中临时占用的存储空间。中临时占用的存储空间。 分析一个算法所占用的存储空间要从各方面综分析一个算法所占用的存储空间要从各方面综合考虑。合考虑。 算法在运行过程中所占用的存储空间的大小被算法在运行过程中所