【C语言版】数据结构教程（一）绪论（上）

【内容简介】本文整理数据结构（C语言版）相关内容的复习笔记，供各位朋友借鉴学习。本章内容更偏于记忆和理解，请读者们耐心阅读。

数据结构教程 · 绪论（上）

本节学习目标

1.1 基本概念

1.2 抽象数据类型的表示与实现

本节学习目标

熟悉数据结构相关的一些概念和术语
了解如何书写抽象数据类型的形式定义

1.1 基本概念

下面我们简要介绍一下数据结构相关的一些概念和术语，这在之后的学习过程中都经常会用到。

1、数据（data）是所有能输入到计算机中并被计算机程序处理的符号的总称。例如：声音、图像、字符串等等。

2、数据元素（data system）是数据的基本单位。例如：下面这张“图”中由许多圆圈组成，这些圆圈就可以认为是数据元素。

3、数据项（data item）是组成数据元素的单位，也是数据的不可分割的最小单位。例如：书籍的目录对于这本书而言是一个数据元素，目录中每一章的信息（章名、页码等）就是一个数据项。

4、数据对象（data object）是性质相同的数据元素的集合，是数据的一个子集。例如：整数数据对象是集合 N = {0,1,-1,2,-2,···}。

以上是数据的一些详细概念。而我们着重要学习的数据结构（data structure）是相互之间存在一种或多种特定关系的数据元素的集合。数据元素之间的关系称为结构（structure）。一般而言，数据元素之间存在以下 4 种基本结构：

集合：结构中的数据元素之间除了“同属于一个集合”之外，没有其它关系。
线性结构：结构中的数据元素之间存在一个对一个的关系。
树形结构：结构中的数据元素之间存在一个对多个的关系。
图状结构或网状结构：结构中的数据元素之间存在多个对多个的关系。

数据的定义方式并不唯一，除上述之外，还有一种形式定义：数据结构是一个二元组，

Data_Structure = { D，S }

其中：D 是数据元素的有限集，S是D上存在的关系的有限集。这样的说法比较抽象，我们举个例子：

【例1】现在我们需要编写一个公司职工管理系统，那么我们首先需要构思这个系统中的数据结构。假设这个公司有 1 个董事长，1 个总经理和 3 个员工，那么这个公司的职工之间存在的关系是：董事长管理总经理，总经理管理员工。则可以定义如下的数据结构：

Group = ( P，R )

其中：P 包含这个公司的所有职员，

R = { R1，R2 }，

R1 = { <董事长，总经理> }，

R2 = { <总经理，员工1>，<总经理，员工2>，<总经理，员工3> }。

上述定义仅仅只是一种从对象的角度抽象出来的数学模型。结构定义中的“关系”描述为数据元素之间的逻辑关系，因此又称为数据的逻辑结构。

但是，为了在计算机中实现对其的操作，还需要研究在计算机中如何来表示一个数据结构。数据结构在计算机中的表示称为数据的物理结构，又称为存储结构。它包括数据元素的表示以及关系的表示。在计算机中，表示信息的最小单位是二进制数的一位，叫做位（bit）。由若干个位组成的位串表示一个数据元素，通常称为元素或结点，例如：用 8 位二进制数表示一个字符。

数据元素之间的关系在计算机中有两种不同的表示方法：顺序映像和非顺序映像，并由此得到两种不同的存储结构：顺序存储结构和链式存储结构。

顺序映像的特点是，借助元素在存储器中的相对位置来表示逻辑关系，例如：假设用 2 个字长的位串表示一个实数，则相邻 4 个字长的位串可以表示一个复数。而对于非顺序映像而言，通常通过指针来指示元素存储地址，从而将数据元素之间的逻辑关系表示出来。如下图所示：

而存储结构可以分别用“一维数组”来描述顺序存储结构，用“指针”描述链式存储结构。

数据类型（data type）是和数据结构密切相关的一个概念。它包括了一个值的集合和定义在这个值集上的一组操作的总称。例如：C语言中的整型变量，其值集为某个区间上的整数，定义在上面的操作为加、减、乘、除和取模等算术运算。根据“值”的不同，数据类型可分为两类：一类是不可分解的原子类型，例如：实数；一类是由若干成分按某种结构组成，可以分解的结构类型，例如：数组。

1.2 抽象数据类型的表示与实现

抽象数据类型（abstract data type，简称 ADT）是指一个数学模型以及定义在该模型上的一组操作。也就是说，只要这个数据类型的逻辑特性不发生变化，就不影响它在外部的使用，类似我们常说的“面向对象的设计”原则。

一个含抽象数据类型的软件模块通常应包含定义、表示和实现 3 个部分。由于抽象数据类型的定义由一个值域和定义在该值域上的一组操作组成。按照其值的不同特性，可以分为：原子类型、固定聚合类型、可变聚合类型。后两者分别代表组成值的成分数量一定或是可变。

与数据结构的形式定义类似，抽象数据类型可用以下三元组表示：( D，S，P )。其中，D 是数据对象，S 是 D 上的关系集，P 是对 D 的基本操作集。具体来书写可以如下：

ADT 抽象数据类型名 {数据对象：<数据对象的定义>数据关系：<数据关系的定义>基本操作：<基本操作的定义>
} ADT 抽象数据类型名

其中，数据对象和数据关系的定义用伪码描述，基本操作的定义格式为：

基本操作名（参数表）初始条件：<初始条件描述>操作结果：<操作结果描述>

基本操作有两种参数：赋值参数只为操作提供输入值；引用参数以 & 打头，除了提供输入值以外，还将返回操作结果。

【例2】一个抽象数据类型三元组的定义：

ADT Triplet {

数据对象：D = {e1, e2, e3 | e1, e2, e3 属于这个集合}

数据关系：R1 = {<e1, e2> , <e2, e3>}

基本操作：

InitTriplet (&T, v1, v2, v3)

操作结果：构造三元组 T，元素 e1, e2, e3 分别被赋以参数 v1, v2,v3的值。

DestroyTriplet (&T)

操作结果：三元组 T 被销毁。

Get (T, i , &e)

初始条件：三元组 T 已存在，i = 1,2,3。

操作结果：用 e 返回 T 中第 i 个元素的值。

...

} ADT Triplet