第8章--数据结构概述

第8章数据结构概述8.1数据结构的引入8.2数据结构的基本概念8.3关于算法的描述及算法分析第8章数据结构概述返回主目录第8章数据结构概述第8章数据结构概述8.1数据结构的引入[例8.1]计算机管理图书目录问题。要利用计算机帮助我们查询书目，首先必须将书目存入计算机，那么这些书目如何存放呢？我们既希望查询时间短，又要求节省空间。一个简单的办法就是建立一张表，每本书的信息只用一张卡片表示，在表中占一行，如表8.1所示。此时计算机操作的对象（数据元素）便是卡片，卡片之间的关系是顺序排列的。计算机对数据的操作是按某个特定要求（如给定书名）进行查询，找到表中满足要求的一行信息。由此，从计算机管理图书目录问题抽象出来的模型即是包含图书目录的表和对表进行查找运算。第8章数据结构概述第8章数据结构概述[例8.2]计算机和人对弈问题。计算机之所以能和人对弈是因为有人将对弈的策略已事先存入计算机。由于对弈过程是在一定规则下随机进行的，因此，为使计算机能灵活对弈，就必须将对弈过程中所有可能发生的情况以及相应的策略考虑周全，而且在决定对策时，不仅要看当时的棋盘状态，还要考虑将来的发展趋势，直至最后取胜的可能性。由此，计算机操作的对象（数据元素）是对弈过程中每一步的棋盘状态（格局）。数据元素之间的关系是由比赛规则决定的。通常情况下，这个关系不是线性的，因为从一个棋盘格局可以派生出几个格局，如图8.1(a)所示是井字棋的一个格局。下一步由持x子的甲方走棋，则有五种可能出现的格局，如图8.1(b)所示。这个图好像由树的主叉派生出五个分叉，我们称它为树，它可以用来表示某一类问题中数据元素间的关系。第8章数据结构概述图8.1井字棋对弈树XOXOXOXOXOXOXOXOXOXOXOXOXXXXX(a)对弈树的数据元素(b)对弈树的一部分XOXO第8章数据结构概述[例8.3]多叉路口交通灯管理问题。通常在十字交叉路口只要设置红绿两色的交通灯便可保持正常的交通秩序，但是对于多叉路口，需设几种颜色的交通灯，才能既使车辆相互不碰撞，又能达到最大流通量呢？图8.2(a)是一个实际的多叉路口，我们如何设置交通灯，即最少应设置几种颜色的交通灯，才能保证正常的交通秩序呢？这个问题可以转换成一个地图染色问题。假设五叉路口中的一条可通行的通路用圆圈染色，要求同一连线上的两个圆圈不能同色且颜色的种类最少。从图8.2(b)中可得出至少需四种颜色。从上面三个例子可看出：计算机已不仅仅用于科学计算，而且更多地用于数据处理和实时控制。与此相对应，计算机加工处理的对象也从简单的数值发展到字符、图像、声音等各种复杂的具有一定结构的数据。第8章数据结构概述图8.2五叉路口交通灯管理问题CDBE(a)五叉路口AB1BC2BD2BA1AC1EA2DB3AD1DC1ED1DA3EC4EB4A(b)通路图第8章数据结构概述数据结构”就是一门研究数值或非数值性程序设计中计算机操作的对象以及它们之间的关系和运算的一门学科。它是设计和实现编译程序、操作系统、数据库系统及其他程序系统的重要基础。第8章数据结构概述8.2数据结构的基本概念计算机处理的对象是数据，那么什么是数据呢？数据是客观事物在计算机中的表示，是信息的载体，具有可识别性、可加工处理性和可存储性等特征，是计算机程序加工处理的对象。可识别性是指计算机能够识别数据，为此必须对客观事物进行编码；可存储性是指数据能够存储在计算机的存储设备上；可加工处理性是指计算机能够以程序设计人员设计的算法，对数据进行加工处理，以得到预期的结果。数据(Data)是描述客观事物的数、字符以及所有能输入到计算机中并被计算机程序处理的符号的集合。它是计算机程序加工的“原料”。第8章数据结构概述例如，一个利用数值分析的方法解代数方程的程序处理的对象只是整数和实数，而一个编译程序或文字处理程序的对象是字符串。因此，对计算机而言，数据的含义极为广泛，如图形、声音等都属于数据的范畴。数据元素(DataElement)是数据的基本单位，即数据这个集合中的一个个体（客体）。有时一个数据元素可由若干个数据项（DataItem）组成，数据项是数据的最小单位。数据对象(DataObject)具有相同特性的数据元素的集合，是数据的一个子集。例如，整数的数据对象是集合N＝｛0,±1,±2,±3,…｝，字母字符的数据对象是集合C＝｛A,B,…,Z｝。第8章数据结构概述数据结构(DataStructure)是指数据之间的相互关系，即数据的组织形式。我们可以从集合的观点加以形式化描述，即是一个二元组DataStructure=（D,R）其中，D是数据元素的集合，R是D上关系的集合。数据结构所要研究的主要内容可以简要地归纳为以下三个方面：(1)研究数据元素之间固有的客观联系，即数据的逻辑结构（LogicalStructure）。(2)研究数据在计算机内部的存储方法，即为数据的存储结构（StorageStructure），又称物理结构。第8章数据结构概述(3)研究如何在数据的各种结构（逻辑的和物理的）上施加有效的操作或处理（算法）。数据的逻辑结构是从逻辑关系上描述数据的，它与数据的存储无关，是独立于计算机的，因此，数据的逻辑结构可以看做是从具体问题抽象出来的数学模型。数据的存储结构是逻辑结构用计算机语言的实现（亦称映像），它是依赖于计算机语言的，对机器语言而言，存储结构是具体的，但我们只在高级语言的层次上来讨论存储结构。数据的运算是定义在数据的逻辑结构上的，每一种逻辑结构都有一个运算的集合。例如，最常用的运算有检索、插入、删除、更新、排序等，这些运算实际上是在抽象的数据上所施加的一系列抽象的操作。所谓抽象的操作，是指我们只知道这些操作是“做什么”，而无须考虑“如何做”。第8章数据结构概述只有确定了存储结构之后，我们才考虑如何具体实现这些运算。本书中讨论的数据运算，均以C语言描述的算法来实现。为了增加对数据结构的感性认识，下面我们来看表8.2所示的学生成绩表的例子。我们将表8.2称为一个数据结构，表中的每一行是一个结点（或记录），它由学号、姓名、性别、课名及成绩等数据项组成。该表中数据元素之间的逻辑关系是：对表中任一个结点，与它相邻且在它前面的结点，称为直接前趋(Immediateredecessor)，最多只有一个；与表中任意结点相邻且在其后的结点，称为直接后继(ImmediateSuccessor)，也最多只有一个。表中只有第一个结点没有直接前趋，称之为开始结点；也只有最后一个结点没有直接后继，称之为终端结点。上述结点间的关系构成了这张学生成绩表的逻辑结构。第8章数据结构概述第8章数据结构概述对于满足这种逻辑关系的表在计算机中如何进行存储表示则是存储结构研究的内容，根据不同的方式可采用顺序存储与非顺序存储。另外，在这张表中可能要经常查阅某一学生的成绩，如有新生加入时要增加数据元素，或有学生退学时要删除相应元素。因此，进行查找、插入和删除就是数据的运算问题。把上表中数据的逻辑关系、存储结构和运算这三个问题搞清楚，也就弄清了学生成绩表这个数据结构，从而可以有针对性地进行问题的求解。综上所述，我们可以将数据结构定义为：按某种逻辑关系组织起来的一批数据，应用计算机语言，可按一定的存储表示方式把它们存储在计算机的存储器中，并在该数据上定义了一个运算的集合。第8章数据结构概述为了不产生混淆，通常我们将数据的逻辑结构简称为数据结构。数据的逻辑结构有以下两大类：1)线性结构线性结构的逻辑特征是有且仅有一个开始结点和一个终端结点，且所有结点都最多只有一个直接前趋和一个直接后继。线性表就是一种典型的线性结构。本书第7章到第8章介绍的都是线性结构。2)非线性结构非线性结构的逻辑特征是一个结点可能有多个直接前趋和直接后继。第9章到第11章介绍的都是非线性结构。数据的存储结构可用以下四种基本的存储方法得到：第8章数据结构概述1)顺序存储方法该方法是把逻辑上相邻的结点存储在物理位置相邻的存储单元里，结点间的逻辑关系由存储单元的邻接关系来体现。由此得到的存储表示称为顺序存储结构（SequentialStorageStructure），通常顺序存储结构是借助于程序语言的数组来描述的。该方法主要应用于线性的数据结构，非线性的数据结构也可以通过某种线性化的方法来实现顺序存储。2）链接存储方法该方法不要求逻辑上相邻的结点在物理位置亦相邻，结点间的逻辑关系是由附加的指针字段表示的。由此得到的存储表示称为链式存储结构（LinkedStorageStructure），通常要借助于程序语言的指针类型来描述。第8章数据结构概述3）索引存储方法该方法通常是在存储结点信息的同时，建立附加的索引表。索引表中的每一项称为索引项，索引项的一般形式是：（关键字，地址），关键字是能惟一标识一个结点的那些数据项。若每个结点在索引表中都有一个索引项，则该索引表称为稠密索引（DenseIndex）。若一组结点在索引表中只对应一个索引项，则该索引表称为稀疏索引（SparseIndex）。稠密索引中索引项地址指出结点所在的存储位置，而稀疏索引中索引项的地址则指示一组结点的起始存储位置。4）散列存储方法该方法的基本思想是根据结点的关键字直接计算出该结点的存储地址。第8章数据结构概述上述四种基本的存储方法，既可以单独使用，也可以组合起来对数据结构进行存储映像。同一种逻辑结构采用不同的存储方法，可以得到不同的存储结构。选择何种存储结构来表示相应的逻辑结构，视具体要求而定，主要考虑的是运算的方便性及算法的时空要求。值得指出的是，很多教科书上是将数据的逻辑结构和存储结构定义为数据结构，而将数据的运算定义为数据结构上的操作。但是，无论怎样定义数据结构，都应该将数据的逻辑结构、存储结构及数据的运算这三个方面看成一个整体。因此，我们学习时，不要孤立地去理解一个方面，而要注意它们之间的联系。第8章数据结构概述正是因为存储结构是数据结构不可缺少的一个方面，所以我们常常将同一逻辑结构的不同存储结构，冠以不同的数据结构名称来标识。例如，线性表是一种逻辑结构，若采用顺序方法的存储表示，则称该结构为顺序表；若采用链接方法的存储表示，则称该结构为链表；若采用散列方法的存储表示，则称该结构为散列表。同理，由于数据的运算也是数据结构不可分割的一个方面，在给定了数据的逻辑结构和存储结构之后，按定义的运算集合及其运算的性质不同，也可能导致完全不同的数据结构。例如，若将线性表上的插入、删除运算限制在表的一端进行，则称该线性表为栈；若将插入限制在表的一端进行，而删除限制在表的另一端进行，则称该线性表为队列。更进一步，若线性表采用顺序表或链表作为存储结构，则对插入和删除运算做了上述限制之后，可分别得到顺序栈或链栈、顺序队列或链队列。第8章数据结构概述8.3关于算法的描述及算法分析8.3.1算法的概念算法是由若干条指令组成的有限序列，它必须满足以下性质：(1)输入性：具有零个或多个输入量，即算法开始前对算法给出的初始量。(2)输出性：至少产生一个输出。(3)有穷性：每条指令的执行次数必须是有限的。(4)确定性：每条指令的含义必须明确，无二义性。(5)可行性：每条指令都应在有限的时间内完成。第8章数据结构概述请看一个例子：给定两个正整数m和n，求它们的最大公因子。求解这个问题通常所用的方法为辗转相除法，在西方被称为欧几里得算法。下面用三个计算步骤描述这个算法：(1)求余数：以n除m，余数为r，0≤r≤n；(2)判断余数是否等于零：若r=0，输出n的当前值，算法结束；否则执行第(3)步；(3)更新被除数和除数：n→m，r→n，执行第(1)步。第8章数据结构概述上述计算过程给出了三个计算步骤，而且每一步骤都意义明确，切实可行，虽然出现循环，但m和n都是给定的有限数，每次相除后得到的余数r若不为零，也总有rmin(m, n)，保证了经过有限次循环以后，必会终止。因此上述计算过程是一个算法。算法的含义与程序十分相似，但二者是有区别的。一个程序不一定满足有穷性。例如，系统程序中的操作系统，只要整个系统不遭破坏，它