第8章--数据结构概述-计算机软件技术基础教程-教学课件.ppt

《第8章--数据结构概述-计算机软件技术基础教程-教学课件.ppt》由会员分享，可在线阅读，更多相关《第8章--数据结构概述-计算机软件技术基础教程-教学课件.ppt（31页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第第8 8章章 数据结构概述数据结构概述8.1 数据结构的引入数据结构的引入8.2 数据结构的基本概念数据结构的基本概念8.3 关于算法的描述及算法分析关于算法的描述及算法分析第第8章章 数据结构概述数据结构概述返回主目录返回主目录第第8 8章章 数据结构概述数据结构概述第8章数据结构概述8.1 数据结构的引入数据结构的引入 例 8.1计算机管理图书目录问题。要利用计算机帮助我们查询书目，首先必须将书目存入计算机，那么这些书目如何存放呢？我们既希望查询时间短，又要求节省空间。一个简单的办法就是建立一张表，每本书的信息只用一张卡片表示，在表中占一行，如表8.1所示。此时计算机操作的对象（数据元素

2、）便是卡片，卡片之间的关系是顺序排列的。计算机对数据的操作是按某个特定要求（如给定书名）进行查询，找到表中满足要求的一行信息。由此，从计算机管理图书目录问题抽象出来的模型即是包含图书目录的表和对表进行查找运算。第第8 8章章 数据结构概述数据结构概述第第8 8章章 数据结构概述数据结构概述 例 8.2 计算机和人对弈问题。计算机之所以能和人对弈是因为有人将对弈的策略已事先存入计算机。由于对弈过程是在一定规则下随机进行的，因此，为使计算机能灵活对弈，就必须将对弈过程中所有可能发生的情况以及相应的策略考虑周全，而且在决定对策时，不仅要看当时的棋盘状态，还要考虑将来的发展趋势，直至最后取胜的可能性。

3、由此，计算机操作的对象（数据元素）是对弈过程中每一步的棋盘状态（格局）。数据元素之间的关系是由比赛规则决定的。通常情况下，这个关系不是线性的，因为从一个棋盘格局可以派生出几个格局，如图8.1(a)所示是井字棋的一个格局。下一步由持x子的甲方走棋，则有五种可能出现的格局，如图8.1(b)所示。这个图好像由树的主叉派生出五个分叉，我们称它为树，它可以用来表示某一类问题中数据元素间的关系。第第8 8章章 数据结构概述数据结构概述第第8 8章章 数据结构概述数据结构概述 例 8.3 多叉路口交通灯管理问题。通常在十字交叉路口只要设置红绿两色的交通灯便可保持正常的交通秩序，但是对于多叉路口，需设几种颜色

4、的交通灯，才能既使车辆相互不碰撞，又能达到最大流通量呢？图8.2(a)是一个实际的多叉路口，我们如何设置交通灯，即最少应设置几种颜色的交通灯，才能保证正常的交通秩序呢？这个问题可以转换成一个地图染色问题。假设五叉路口中的一条可通行的通路用圆圈染色，要求同一连线上的两个圆圈不能同色且颜色的种类最少。从图8.2(b)中可得出至少需四种颜色。从上面三个例子可看出：计算机已不仅仅用于科学计算，而且更多地用于数据处理和实时控制。与此相对应，计算机加工处理的对象也从简单的数值发展到字符、图像、声音等各种复杂的具有一定结构的数据。第第8 8章章 数据结构概述数据结构概述图8.2五叉路口交通灯管理问题第第8

5、8章章 数据结构概述数据结构概述数据结构”就是一门研究数值或非数值性程序设计中计算机操作的对象以及它们之间的关系和运算的一门学科。它是设计和实现编译程序、操作系统、数据库系统及其他程序系统的重要基础。第第8 8章章 数据结构概述数据结构概述第第8 8章章 数据结构概述数据结构概述例如，一个利用数值分析的方法解代数方程的程序处理的对象只是整数和实数，而一个编译程序或文字处理程序的对象是字符串。因此，对计算机而言，数据的含义极为广泛，如图形、声音等都属于数据的范畴。数据元素(DataElement)是数据的基本单位，即数据这个集合中的一个个体（客体）。有时一个数据元素可由若干个数据项（DataIt

6、em）组成，数据项是数据的最小单位。数据对象(DataObject)具有相同特性的数据元素的集合，是数据的一个子集。例如，整数的数据对象是集合N 0,1,2,3,，字 母 字 符 的 数 据 对 象 是 集 合 CA,B,Z。第第8 8章章 数据结构概述数据结构概述数据结构(DataStructure)是指数据之间的相互关系，即数据的组织形式。我们可以从集合的观点加以形式化描述，即是一个二元组DataStructure=（D,R）其中，D是数据元素的集合，R是D上关系的集合。数据结构所要研究的主要内容可以简要地归纳为以下三个方面：(1)研究数据元素之间固有的客观联系，即数据的逻辑结构（Logi

7、calStructure）。(2)研究数据在计算机内部的存储方法，即为数据的存储结构（StorageStructure），又称物理结构。第第8 8章章 数据结构概述数据结构概述第第8 8章章 数据结构概述数据结构概述只有确定了存储结构之后，我们才考虑如何具体实现这些运算。本书中讨论的数据运算，均以C语言描述的算法来实现。为了增加对数据结构的感性认识，下面我们来看表8.2所示的学生成绩表的例子。我们将表8.2称为一个数据结构，表中的每一行是一个结点（或记录），它由学号、姓名、性别、课名及成绩等数据项组成。该表中数据元素之间的逻辑关系是：对表中任一个结点，与它相邻且在它前面的结点，称为直接前趋(I

8、mmediateredecessor)，最多只有一个；与表中任意结点相邻且在其后的结点，称为直接后继(ImmediateSuccessor)，也最多只有一个。表中只有第一个结点没有直接前趋，称之为开始结点；也只有最后一个结点没有直接后继，称之为终端结点。上述结点间的关系构成了这张学生成绩表的逻辑结构。第第8 8章章 数据结构概述数据结构概述第第8 8章章 数据结构概述数据结构概述对于满足这种逻辑关系的表在计算机中如何进行存储表示则是存储结构研究的内容，根据不同的方式可采用顺序存储与非顺序存储。另外，在这张表中可能要经常查阅某一学生的成绩，如有新生加入时要增加数据元素，或有学生退学时要删除相应元

9、素。因此，进行查找、插入和删除就是数据的运算问题。把上表中数据的逻辑关系、存储结构和运算这三个问题搞清楚，也就弄清了学生成绩表这个数据结构，从而可以有针对性地进行问题的求解。综上所述，我们可以将数据结构定义为：按某种逻辑关系组织起来的一批数据，应用计算机语言，可按一定的存储表示方式把它们存储在计算机的存储器中，并在该数据上定义了一个运算的集合。第第8 8章章 数据结构概述数据结构概述为了不产生混淆，通常我们将数据的逻辑结构简称为数据结构。数据的逻辑结构有以下两大类：1)线性结构线性结构的逻辑特征是有且仅有一个开始结点和一个终端结点，且所有结点都最多只有一个直接前趋和一个直接后继。线性表就是一种

10、典型的线性结构。本书第7章到第8章介绍的都是线性结构。2)非线性结构非线性结构的逻辑特征是一个结点可能有多个直接前趋和直接后继。第9章到第11章介绍的都是非线性结构。数据的存储结构可用以下四种基本的存储方法得到：第第8 8章章 数据结构概述数据结构概述第第8 8章章 数据结构概述数据结构概述3）索引存储方法该方法通常是在存储结点信息的同时，建立附加的索引表。索引表中的每一项称为索引项，索引项的一般形式是：（关键字，地址），关键字是能惟一标识一个结点的那些数据项。若每个结点在索引表中都有一个索引项，则该索引表称为稠密索引（DenseIndex）。若一组结点在索引表中只对应一个索引项，则该索引表称

11、为稀疏索引（SparseIndex）。稠密索引中索引项地址指出结点所在的存储位置，而稀疏索引中索引项的地址则指示一组结点的起始存储位置。4）散列存储方法该方法的基本思想是根据结点的关键字直接计算出该结点的存储地址。第第8 8章章 数据结构概述数据结构概述上述四种基本的存储方法，既可以单独使用，也可以组合起来对数据结构进行存储映像。同一种逻辑结构采用不同的存储方法，可以得到不同的存储结构。选择何种存储结构来表示相应的逻辑结构，视具体要求而定，主要考虑的是运算的方便性及算法的时空要求。值得指出的是，很多教科书上是将数据的逻辑结构和存储结构定义为数据结构，而将数据的运算定义为数据结构上的操作。但是，

12、无论怎样定义数据结构，都应该将数据的逻辑结构、存储结构及数据的运算这三个方面看成一个整体。因此，我们学习时，不要孤立地去理解一个方面，而要注意它们之间的联系。第第8 8章章 数据结构概述数据结构概述正是因为存储结构是数据结构不可缺少的一个方面，所以我们常常将同一逻辑结构的不同存储结构，冠以不同的数据结构名称来标识。例如，线性表是一种逻辑结构，若采用顺序方法的存储表示，则称该结构为顺序表；若采用链接方法的存储表示，则称该结构为链表；若采用散列方法的存储表示，则称该结构为散列表。同理，由于数据的运算也是数据结构不可分割的一个方面，在给定了数据的逻辑结构和存储结构之后，按定义的运算集合及其运算的性质

13、不同，也可能导致完全不同的数据结构。例如，若将线性表上的插入、删除运算限制在表的一端进行，则称该线性表为栈；若将插入限制在表的一端进行，而删除限制在表的另一端进行，则称该线性表为队列。更进一步，若线性表采用顺序表或链表作为存储结构，则对插入和删除运算做了上述限制之后，可分别得到顺序栈或链栈、顺序队列或链队列。第第8 8章章 数据结构概述数据结构概述8.3 关于算法的描述及算法分析关于算法的描述及算法分析8.3.1 算法的概念算法的概念算法是由若干条指令组成的有限序列，它必须满足以下性质：(1)输入性：具有零个或多个输入量，即算法开始前对算法给出的初始量。(2)输出性：至少产生一个输出。(3)有

14、穷性：每条指令的执行次数必须是有限的。(4)确定性：每条指令的含义必须明确，无二义性。(5)可行性：每条指令都应在有限的时间内完成。第第8 8章章 数据结构概述数据结构概述请看一个例子：给定两个正整数m和n，求它们的最大公因子。求解这个问题通常所用的方法为辗转相除法，在西方被称为欧几里得算法。下面用三个计算步骤描述这个算法：(1)求余数：以n除m，余数为r，0rn；(2)判断余数是否等于零：若r=0，输出n的当前值，算法结束；否则执行第(3)步；(3)更新被除数和除数：nm，rn，执行第(1)步。第第8 8章章 数据结构概述数据结构概述第第8 8章章 数据结构概述数据结构概述8.3.2 算法分

15、析算法分析衡量一个算法的好坏，除其“正确性”外，还应考虑：(1)执行算法所消耗的时间；(2)执行算法所耗费的存储空间，其中主要应考虑辅存量的大小；(3)其他诸如：算法是否易读，是否易于调试、测试等。从主观上讲，我们希望选用一个既不占很多存储空间，运行时间又短，其他性能也好的算法。然而，实际上不可能做到十全十美，因为上述要求有时会相互抵触。例如，一个运行时间较短的程序往往占用的辅存量却较大。第第8 8章章 数据结构概述数据结构概述因此，在不同情况下应有不同的选择。若程序使用次数较少，则力求算法简明易读；若程序需反复运行多次，则应尽可能选用快速的算法；若待解决问题的数据量较大，而机器的存储空间较小

16、，则其算法应主要考虑如何节省空间。本书我们主要讨论算法的时间特性，偶尔也讨论空间特性。一个算法所耗费的时间，应该是该算法中每条语句的执行时间之和，而每条语句的执行时间则是该语句的执行次数与该语 句 执 行 一 次 所 需 时 间 的 乘 积。在 此，我 们 引 入 频 度(FrequencyCount)的概念。语句的频度即为语句重复执行的次数。请看一个例子：求两个n阶方阵的乘积，其算法描述如下：第第8 8章章 数据结构概述数据结构概述definen自然数MATRIXMLT(A,B,C)FloatAn,Bn,Cn;inti,j,k;(1)for(i=0;in;i+)n+1(2)for(j=0；j

17、n;j+)n(n+1)(3)Cij=0;n2(4)for(k=0;kn;k+)n2(n+1)(5)Cij=Cij+Aik*Bkj;n3第第8 8章章 数据结构概述数据结构概述第第8 8章章 数据结构概述数据结构概述例如，算法MATRIXMLT的时间复杂度T(n)，当n趋向无穷大时，显然有这表明，当n充分大时，T(n)和n3之比是一个不等于零的常数，即T(n)和n3是同阶的，或者说T(n)和n3的数量级相同，可记为T(n)=O(n3)。我们称T(n)=O(n3)是算法MATRIXMLT的渐近时间复杂度。其中记号“O”是数学符号，其严格的数学定义是若T(n)和f(n)是定义在正整数集合上的两个函数

18、，当存在两个正的常数c和n0时，使得对所有的nn0，都有T(n)cf(n)成立，则T(n)=O(f(n)。当我们评价一个算法的时间性能时，主要标准是算法时间复杂度的数量级，即算法的渐近时间复杂度。通常我们可以通过判定程序段中重复次数最多的语句的频度来估算算法的时间复杂度。第第8 8章章 数据结构概述数据结构概述例如，算法MATRIXMLT的时间复杂度一般是指T(n)=O(n3)，这里的f(n)=n3是该算法中语句(5)的频度。下面我们举例说明如何求算法的时间复杂度。例：交换i和j的内容。temp=i;i=j;j=temp;以上三条单个语句的频度均为1，该程序段的执行时间是一个与问题规模n无关的常数，因此，算法的时间复杂度为常数阶，记作T(n)=O(1)。事实上，只要算法的执行时间不随着问题规模n的增加而增加，即使算法中有成千上万条语句，其执行时间也不过是一个较大的常数，此时，算法的时间复杂度也只是O(1)。第第8 8章章 数据结构概述数据结构概述第第8 8章章 数据结构概述数据结构概述图8.3各种数量级的T(n)