数据结构教案_中科大.ppt

数 据 结 构 主讲人：苏仕华 第一章 绪 论 1.1 引言 1.2 基本概念和术语 1.3 抽象数据类型 1.4 算法和算法分析 1.4.1 算法 1.4.2 算法设计的要求 1.4.3 算法效率的度量 1.4.4 算法的存储空间的需求 计算机是一门研究用计算机进行信息表示和处理的科学。这里面涉及到两个问题： 信息的表示和信息的处理 而信息的表示和组织又直接关系到处理信息的程序的效率。随着计算机的普及，信息量的增加，信息范围的拓宽，使许多系统程序和应用程序的规模很大，结构又相当复杂。因此，为了编写一个“好”的程序，必须分析待处理的对象的特征及各对象之间存在的关系，这就是数据结构这门课所要研究的问题。 在计算机发展的初期，人们使用计算机的主要目的是处理数值计算问题。使用计算机解决一个具体问题时，一般需要经过下列几个步骤： 由于当时所涉及的运算对象是简单的整型、实型或布尔等类型的数据，所以程序设计者的主要精力是集中于程序设计的技巧上，而无须重视数据结构。随着计算机应用领域的扩大和软、硬件的发展，非数值计算问题越来越显得重要。据统计，处理非数值计算性问题占了90%以上的计算机运行时间，这类问题涉及到的数据结构更为复杂，数据元素之间的相互关系一般无法用数学方程式加以描述。因此，解决这类问题的关键不再是数学分析和计算方法，而是要设计出合适的数据结构，才能有效地解决问题。 例【1.1】电话号码查询系统 设有一个电话号码薄，它记录了N个人的名字和其相应的电话号码，假定按如下形式安排： (a1，b1)(a2，b2)…(an，bn) 其中ai，bi(i=1，2…n) 分别表示某人的名字和对应的电话号码要求设计一个算法，当给定任何一个人的名字时，该算法能够打印出此人的电话号码，如果该电话簿中根本就没有这个人，则该算法也能够报告没有这个人的标志。 算法的设计，依赖于计算机如何存储人的名字和对应的电话号码，或者说依赖于名字和其电话号码的结构。 【例1.2】图书馆信息检索系统。 当我们根据书名查找某本书有关情况的时候；或者根据作者或某个出版社查找有关书籍的时候，或根据书刊号查找作者和出版社等有关情况的时候，只要我们建立了相关的数据结构，按照某种算法编写了相关程序，就可以实现计算机的自动检索。若使用计算机处理上述图书检索问题，首先要建立一张图书基本信息表，列在每一行上的是一本书的信息，一般包括：登录号、书名、作者、分类号、出版社和出版时间等项，登录号是唯一的。如表1.1所示。 表中的数据元素(一行)可按登录号、书名、作者名等建立相应的索引表。这些表构成的文件就是图书目录检索的数学模型。计算机的主要操作是按某个特定要求（如书名、作者）对书目文档进行查询检索。诸如此类的问题还有各种查号系统、仓库管理系统、帐务处理等。这类问题中的处理对象之间都是一种最简单的线性关系，它们所对应的数学模型称为线性的数据结构。 【例1.3】图的m着色问题。 图的着色问题是由地图的着色问题引申而来的：用m种颜色为地图着色，使地图的每个区域着一种颜色，且相邻区域的颜色不同。如果把一个区域收缩为一个顶点，将相邻两个区域用一条边相连接，就可以把一个区域图抽象为一个平面图和一个区域邻接关系图，如图1.1(a)、(b)所示。 19世纪50年代，英国学者提出了任何地图都可以用4种颜色来着色的4着色猜想问题。过了100多年，这个问题才由美国学者在计算机上予以证明，这就是著名的4色定理。如在图1.1中，颜色用数字表示，字母表示区域，则图中表示了不同区域的不同着色情况。 再例如，家族的血统关系、博奕树问题（人一机下棋）、计算机的文件系统等都是一种树形结构；而城市之间的交通网络、工程管理中的活动安排以及多叉路口交通灯管理等问题是图形结构的。它们都是一种非线性的数据结构。 通过以上几例可以直接地认为：数据结构就是研究数据的逻辑结构和物理结构以及它们之间相互关系，并对这种结构定义相应的运算，而且确保经过这些运算后所得到的新结构仍然是原来的结构类型。 数据项是数据的不可分割的最小单位。如前例中的目录卡片表中的一张卡片（表格中的一行）、树中的一个节点、图的一个顶点等都是数据元素，有时一个数据元素可由若干个数据项（也称为字段、域、属性）组成，数据项是具有独立含义的最小标识单位。如图书卡片信息中的登录号、书名、作者