数据结构教案（苏1）.ppt

数 据 结 构;第一章 绪 论; 计算机是一门研究用计算机进行信息表示和处理的科学。这里面涉及到两个问题： 信息的表示和信息的处理 而信息的表示和组织又直接关系到处理信息的程序的效率。随着计算机的普及，信息量的增加，信息范围的拓宽，使许多系统程序和应用程序的规模很大，结构又相当复杂。因此，为了编写一个“好”的程序，必须分析待处理的对象的特征及各对象之间存在的关系，这就是数据结构这门课所要研究的问题。 ; 在计算机发展的初期，人们使用计算机的主要目的是处理数值计算问题。使用计算机解决一个具体问题时，一般需要经过下列几个步骤： 由于当时所涉及的运算对象是简单的整型、实型或布尔等类型的数据，所以程序设计者的主要精力是集中于程序设计的技巧上，而无须重视数据结构。随着计算机应用领域的扩大和软、硬件的发展，非数值计算问题越来越显得重要。据统计，处理非数值计算性问题占了90%以上的计算机运行时间，这类问题涉及到的数据结构更为复杂，数据元素之间的相互关系一般无法用数学方程式加以描述。因此，解决这类问题的关键不再是数学分析和计算方法，而是要设计出合适的数据结构，才能有效地解决问题。 ; 1.1 引言 著名的瑞士计算机科学家沃思(N.Wirth)教授曾提出，算法+数据结构=程序。这里的数据结构指的是数据的逻辑结构和存储结构，而算法则是对数据运算的描述。由此可见，程序设计的实质是对实际问题选择一种好的数据结构和设计一个好的算法，而好的算法在很大程度上取决于描述实际问题的数据结构。因此，要设计出一个“好”的程序，就必须有好的算法，而好的算法必须建立在研究数据的特性及数据之间存在的关系的基础上。这些正是数据结构结构这门课程所要研究的内容。 到底什么是数据结构呢？先通过一个例子来说明有关数据结构的概念。 ;例【1.1】电话号码查询系统 设有一个电话号码薄，它记录了N个人的名字和其相应的电话号码，假定按如下形式安排： (a1，b1)(a2，b2)…(an，bn) 其中ai，bi(i=1，2…n) 分别表示某人的名字和对应的电话号码要求设计一个算法，当给定任何一个人的名字时，该算法能够打印出此人的电话号码，如果该电话簿中根本就没有这个人，则该算法也能够报告没有这个人的标志。 算法的设计，依赖于计算机如何存储人的名字和对应的电话号码，或者说依赖于名字和其电话号码的结构。; 数据的结构，直接影响算法的选择和效率。 上述的问题是一种数据结构问题。可将名字和对应的电话号码设计成：二维数组、表结构、向量。 假定名字和其电话号码逻辑上已安排成 n 元向量的形式，它的每个元素是一个数对 (ai，bi)， 1≤i≤n 数据结构还要提供每种结构类型所定义的各种运算的算法。 ;【例1.2】图书馆信息检索系统。 当我们根据书名查找某本书有关情况的时候；或者根据作者或某个出版社查找有关书籍的时候，或根据书刊号查找作者和出版社等有关情况的时候，只要我们建立了相关的数据结构，按照某种算法编写了相关程序，就可以实现计算机的自动检索。若使用计算机处理上述图书检索问题，首先要建立一张图书基本信息表，列在每一行上的是一本书的信息，一般包括：登录号、书名、作者、分类号、出版社和出版时间等项，登录号是唯一的。如表1.1所示。; 表1.1 图书目录卡片表; 表中的数据元素(一行)可按登录号、书名、作者名等建立相应的索引表。这些表构成的文件就是图书目录检索的数学模型。计算机的主要操作是按某个特定要求（如书名、作者）对书目文档进行查询检索。诸如此类的问题还有各种查号系统、仓库管理系统、帐务处理等。这类问题中的处理对象之间都是一种最简单的线性关系，它们所对应的数学模型称为线性的数据结构。;【例1.3】图的m着色问题。 图的着色问题是由地图的着色问题引申而来的：用m种颜色为地图着色，使地图的每个区域着一种颜色，且相邻区域的颜色不同。如果把一个区域收缩为一个顶点，将相邻两个区域用一条边相连接，就可以把一个区域图抽象为一个平面图和一个区域邻接关系图，如图1.1(a)、(b)所示。; (a) 抽象的平面图 (b) 区域邻接关系图