专题1数据结构分类与抽象数据类型

《专题1数据结构分类与抽象数据类型》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、9专题1数据结构分类与抽象数据类型专题1数据结构分类与抽象数据类型1.1数据结构分类数据结构讨论现实世界和计算机世界中的数据及其相互之间的联系，这体现在逻辑和存储两个层面上，相应称之为逻辑结构和存储结构。也就是说，在现实世界中讨论的数据结构是指逻辑结构，在计算机世界中讨论的数据结构是指存储结构，又称为物理结构。数据的逻辑结构总体上分为4种类型：集合结构、线性结构、树结构和图结构。数据的存储结构总体上也分为4种类型：顺序结构、链接结构、索引结构和散列结构。原则上，一种逻辑结构可以采用任一种存储结构来存储（表示）。对于现实世界中的同一种数据，根据研究问题的角度不同，将会选

2、用不同的逻辑结构；对于一种逻辑结构，根据处理问题的要求不同，将会选用不同的存储结构。对于复杂的数据结构，不论从逻辑层面上还是从存储层面上看，都可能包含有多个嵌套层次。如假定一种数据结构包含有两个层次，第一层（顶层）的逻辑结构可能是树结构，存储结构可能是链接结构；第二层（底层）的逻辑结构可能是线性结构，存储结构可能是顺序结构。第一层结构就是数据的总体结构，第二层结构就是第一层中数据元素的结构。数据的逻辑结构通常采用二元组来描述，其中一元为数据元素的集合，另一元为元素之间逻辑关系的集合，每一个逻辑关系是元素序偶的集合，如就是一个序偶，其中x为前驱，y为后继。当数

3、据的逻辑结构存在着多个逻辑关系时，通常对每个关系分别进行讨论。逻辑结构的另一种描述方法是图形表示，图中每个结点表示元素，每条带箭头的连线表示元素之间的前驱与后继的关系，其箭头一端为后继元素，另一端为前驱元素。数据的存储结构通常采用一种计算机语言中的数据类型来描述，通过建立数据存储结构的算法来具体实现。数据的逻辑结构或存储结构也时常被简称为数据结构，读者可根据上下文来理解。下面通过例子来说明数据的逻辑结构。假定某校教务处的职员简表如表1.1所示。该表中共有10条记录，每条记录都由6个数据项组成。此表整体上被看为一个数据，每个记录是这个数据中的数据元素。由于每条记录的职工

4、号各不相同，所以可把职工号作为记录的关键字，在下面构成的各种数据结构中，将用记录的关键字代表整个记录。9专题1数据结构分类与抽象数据类型表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.

5、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>,<0

6、2,07>,<07,04>, <04,06>,<06,09>,<09,10>}对应的图形表示如图1.1所示。图1.1数据的线性结构示意图结合表1.1，细心的读者不难看出：R是按职员年龄从大到小排列的关系。在数据结构linearity中，数据元素之间是有序的，每个数据元素有且仅有一个直接前驱元素（除结构中第一个元素05外），有且仅有一个直接后继元素（除结构中最后一个元素10外）。这种数据结构的特点是数据元素之间的1对1（1∶1）联系，即线性关系。我们把具有这种特点的数据结构叫做线性结构。9专题1数据结构分类与抽象数据类型【例1.3】一种数据结构的二元组表示为tree=(

7、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是职员之间领导与被领导的关系。图1.2像倒着画的一棵树，在这棵树中，最上面的一个没有前驱只有后继的结点叫做树根结点，最下面一层的只有前驱没有后继的结点叫做树叶结点，除树根和树叶之外的结点叫做树枝结点。在一棵树中，每个结点有且只有一个前