数据结构简介

数据结构是计算机学科中的一门专业课程，更是程序设计中不可或缺的一个专业知识，瑞士的一名计算机专家则更直接地说：算法＋数据结构＝程序设计，可想数据结构在程序中的重要性。

本书的内容不是程序设计，而是数据恢复技术，所以不能花费大量篇幅系统介绍数据结构，只能针对数据恢复技术中用到的一些数据结构知识进行讲解。

数据结构的基本概念

（1）什么是数据：数据结构中的数据，是指所有能被输入到计算机中，且能被计算机处理的符号（数字、字符等）的集合，它是计算机操作对象的总称。

（2）数据元素：数据元素是数据集合中的一个“个体”，在计算机中通常作为一个整体进行考虑和处理，是数据结构中讨论的基本单位。

数据元素有两类，一类是不可分割的“原子”型数据元素，如数值“1”，字符“N”等；另一类是由多个款项构成的数据元素，其中每个款项被称为一个“数据项”。

例如描述一个学生的信息的数据元素可由“姓名、学号、性别、班级、出生日期、入学成绩”6个数据项组成。其中的出生日期又可以由三个数据项：年、月和日组成，则称“出生日期”为“组合项”，而其他不可分割的数据项为“原子项”。

所以，数据项是数据结构中讨论的最小单位。

（3）关键字：关键字是指能识别一个或多个数据元素的数据项。若能起唯一识别作用，则称为“主关键字”，否则称为“次关键字”。

（4）数据对象：数据对象是具有相同特性的数据元素的集合，如整数、实数等。数据对象是数据的一个子集。

（5）数据结构：若在特性相同的数据元素集合中的数据元素之间存在一种或多种特定的关系，则称该数据元素的集合为“数据结构”。也就是说，数据结构是带“结构”的数据元素的集合，“结构”即指数据元素之间存在的关系。

数据结构的分类

按照数据结构的关系分类

数据结构按关系分类有四种：线性结构、树结构、图结构和集合结构。

线性结构如图1-2所示。

图1-2　线性结构

树结构如图1-3所示。

图1-3　树结构

图结构如图1-4所示。

图1-4　图结构

集合结构如图1-5所示。

集合结构

按照数据结构的层次分类

数据结构按层次分类有两种：数据的逻辑结构和数据的物理结构。

数据的逻辑结构是对数据元素之间存在的逻辑关系的描述，它可以用一个数据元素的集合来定义在此集合上的若干关系。

数据的逻辑结构又分为线性关系和非线性关系。前面讲过的线性结构就是线性关系，而非线性关系包括图结构和树结构。

例如，某学校的一个年级有两个班，由同一个班主任带班，每个班按所住宿舍分组，他们之间的关系就是非线性关系，如图1-6所示。

非线性关系图

数据物理结构是数据逻辑结构在计算机中的表示和实现，故又称数据“存储结构”。

之前对数据结构的定义还只是数学上的抽象概念，并没有涉及计算机。完整的数据结构定义还应该包括它在计算机中的表示，即数据的“存储结构”。

存储结构有四种方法，它们是顺序（Sequential）、链式（Linked）、索引（Indexed）和散列（Hashing）。在本书后面将要重点讲解的分区结构和文件系统结构中，都会用到这些存储方法。

①顺序存储方法：把逻辑上相邻的节点存储在物理位置相邻的存储单元里，节点间的逻辑关系由存储单元的邻接关系来体现，由此得到的存储表示叫作顺序存储结构。

提示：在FAT文件系统中对子目录的管理就用到了这种存储结构。

②链式存储方法：它不要求逻辑上相邻的节点在物理位置上也相邻，节点间的逻辑关系是由附加的指针字段表示的，由此得到的存储表示叫作链式存储结构。

提示：在FAT文件系统中对文件所占簇的管理，就是用指针的方式实现链式存储的。

③索引存储方法：除建立节点存储信息外，还建立附加的索引表来表示节点的地址，由此得到的存储表示叫作索引存储结构。

提示：NTFS文件系统中对目录结构的管理就用到了索引存储结构。

④散列存储方法：根据节点的关键字直接计算出该节点的存储地址，由此得到的存储表示叫作散列存储结构。

提示：Linux的EXT3文件系统中对目录结构的管理就用到了散列存储结构。