1.1 数据结构分类数据结构讨论现实世界和计算机世界中的数据及其相互之间的联系，这体现在逻辑和存储两个层面上，相应称之为逻辑结构和存储结构。也就是说，在现实世界中讨论的数据结构是指逻辑结构，在计算机世界中讨论的数据结构是指存储结构，又称为物理结构。数据的逻辑结构总体上分为 4 种类型：集合结构、线性结构、树结构和图结构。数据的存储结构总体上也分为 4 种类型：顺序结构、链接结构、索引结构和散列结构。原则上，一种逻辑结构可以采纳任一种存储结构来存储（表示）。对于现实世界中的同一种数据，根据讨论问题的角度不同，将会选用不同的逻辑结构；对于一种逻辑结构，根据处理问题的要求不同，将会选用不同的存储结构。对于复杂的数据结构，不论从逻辑层面上还是从存储层面上看，都可能包含有多个嵌套层次。如假定一种数据结构包含有两个层次，第一层（顶层）的逻辑结构可能是树结构，存储结构可能是链接结构；第二层（底层）的逻辑结构可能是线性结构，存储结构可能是顺序结构。第一层结构就是数据的总体结构，第二层结构就是第一层中数据元素的结构。数据的逻辑结构通常采纳二元组来描述，其中一元为数据元素的集合，另一元为元素之间逻辑关系的集合，每一个逻辑关系是元素序偶的集合，如就是一个序偶，其中 x 为前驱，y 为后继。当数据的逻辑结构存在着多个逻辑关系时，通常对每个关系分别进行讨论。逻辑结构的另一种描述方法是图形表示，图中每个结点表示元素，每条带箭头的连线表示元素之间的前驱与后继的关系，其箭头一端为后继元素，另一端为前驱元素。数据的存储结构通常采纳一种计算机语言中的数据类型来描述，通过建立数据存储结构的算法来具体实现。数据的逻辑结构或存储结构也时常被简称为数据结构，读者可根据上下文来理解。下面通过例子来说明数据的逻辑结构。假定某校教务处的职员简表如表 1.1 所示。该表中共有 10 条记录，每条记录都由 6 个数据项组成。此表整体上被看为一个数据，每个记录是这个数据中的数据元素。由于每条记录的职工号各不相同，所以可把职工号作为记录的关键字，在下面构成的各种数据结构中，将用记录的关键字代表整个记录。表 1.1 教务处职员简表职 工 号姓 名性 别出 生 日 期职 务部 门01万明华男处长02赵 宁男科长教材科03张 利女科长考务科04赵书芳女主任办公室05刘永年男科员教材科06王明理女科员教材科07王 敏女科员考务科08张 才男科员考务科09马...
