2014抽象数据类型.docVIP

专题1 数据结构分类与抽象数据类型 1.1 数据结构分类 数据结构讨论现实世界和计算机世界中的数据及其相互之间的联系，这体现在逻辑和存储两个层面上，相应称之为逻辑结构和存储结构。也就是说，在现实世界中讨论的数据结构是指逻辑结构，在计算机世界中讨论的数据结构是指存储结构，又称为物理结构。 数据的逻辑结构总体上分为4种类型：集合结构、线性结构、树结构和图结构。数据的存储结构总体上也分为4种类型：顺序结构、链接结构、索引结构和散列结构。原则上，一种逻辑结构可以采用任一种存储结构来存储（表示）。 对于现实世界中的同一种数据，根据研究问题的角度不同，将会选用不同的逻辑结构；对于一种逻辑结构，根据处理问题的要求不同，将会选用不同的存储结构。 对于复杂的数据结构，不论从逻辑层面上还是从存储层面上看，都可能包含有多个嵌套层次。如假定一种数据结构包含有两个层次，第一层（顶层）的逻辑结构可能是树结构，存储结构可能是链接结构；第二层（底层）的逻辑结构可能是线性结构，存储结构可能是顺序结构。第一层结构就是数据的总体结构，第二层结构就是第一层中数据元素的结构。 数据的逻辑结构通常采用二元组来描述，其中一元为数据元素的集合，另一元为元素之间逻辑关系的集合，每一个逻辑关系是元素序偶的集合，如x,y就是一个序偶，其中x为前驱，y为后继。当数据的逻辑结构存在着多个逻辑关系时，通常对每个关系分别进行讨论。 逻辑结构的另一种描述方法是图形表示，图中每个结点表示元素，每条带箭头的连线表示元素之间的前驱与后继的关系，其箭头一端为后继元素，另一端为前驱元素。 数据的存储结构通常采用一种计算机语言中的数据类型来描述，通过建立数据存储结构的算法来具体实现。 数据的逻辑结构或存储结构也时常被简称为数据结构，读者可根据上下文来理解。 下面通过例子来说明数据的逻辑结构。 假定某校教务处的职员简表如表1.1所示。该表中共有10条记录，每条记录都由6个数据项组成。此表整体上被看为一个数据，每个记录是这个数据中的数据元素。由于每条记录的职工号各不相同，所以可把职工号作为记录的关键字，在下面构成的各种数据结构中，将用记录的关键字代表整个记录。 表1.1 教务处职员简表 职 工 号 姓 名 性 别 出 生 日 期 职 务 部 门 01 万明华 男 1962.03.20 处长 02 赵 宁 男 1968.06.14 科长 教材科 03 张 利 女 1964.12.07 科长 考务科 04 赵书芳 女 1972.08.05 主任 办公室 05 刘永年 男 1959.08.15 科员 教材科 06 王明理 女 1975.04.01 科员 教材科 07 王 敏 女 1972.06.28 科员 考务科 08 张 才 男 1967.03.17 科员 考务科 09 马立仁 男 1975.10.12 科员 考务科 10 邢怀常 男 1976.07.05 科员 办公室 【例1.1】一种数据结构的二元组表示为set=(K,R),其中 K={01,02,03,04,05,06,07,08,09,10} R={} 在数据结构set中，只存在有元素的集合，不存在有关系，或者说关系为空。这表明只考虑表中的每条记录，不考虑它们之间的任何关系。把具有此种特点的数据结构称为集合结构。 集合结构中的元素可以任意排列，无任何次序。 【例1.2】一种数据结构的二元组表示为linearity=(K,R),其中 K={01,02,03,04,05,06,07,08,09,10} R={05,01,01,03,03,08,08,02,02,07,07,04, 04,06,06,09,09,10} 对应的图形表示如图1.1所示。 图1.1 数据的线性结构示意图 结合表1.1，细心的读者不难看出：R是按职员年龄从大到小排列的关系。 在数据结构linearity中，数据元素之间是有序的，每个数据元素有且仅有一个直接前驱元素（除结构中第一个元素05外），有且仅有一个直接后继元素（除结构中最后一个元素10外）。这种数据结构的特点是数据元素之间的1对1（1∶1）联系，即线性关系。我们把具有这种特点的数据结构叫做线性结构。 【例1.3】一种数据结构的二元组表示为tree=(K,R),其中 K={01,02,03,04,05,06,07,08,09,10} R={01,02,01,03,01,04,02,05,02,06,03,07, 03,08,03,09,04,10} 对应的图形表示如图1.2所示。 图1.2 数据的树结构示意图 结合表1.1，细心的读者不难看出：R是职员之间