当前课程知识点：数据结构 > 第1章 绪论 > 1.3数据结构的描述 > 1.3数据结构的描述
同学们大家好
我是云南大学信息学院的教师孔兵
下面我们讨论一下数据结构的描述方式
从数据结构的定义可知，数据结构包含两个东西
数据元素和它们之间的关系，怎么描述它呢？
数据结构有两种表示形式，一种称为数据的逻辑结构
这是我们在建模过程中使用的表示形式，是针对程序设计者的
当然，最终我们要利用计算机来处理数据结构
那么必须把数据结构以某种方式存储到计算机的内部
在计算机内部实现的数据结构称为物理结构或者叫存储结构
数据结构涉及到数据元素和它们之间的关系
那么要在计算机中表示数据结构，就涉及到两个问题
一个是数据元素如何在计算机中表示？
一个是数据元素之间的关系在计算机中怎样描述？
数据元素如何在计算机中表示比较简单
可以在程序设计语言当中，根据数据元素的特征定义相应的数据类型即可
例1中，书的信息可以通过定义一个
结构体类型来实现它在计算机中的表示
那么，如何在计算机中表达数据元素之间的关系呢？
所谓表达关系，就是要描述清楚谁是谁的前驱
谁是谁的后继这样的关系
数据元素之间的关系的表示，在计算机中有两种常用的表示方法
顺序映像和非顺序映像
顺序映像的特点是借助元素
在存储器中的相对位置来表示数据元素之间的逻辑关系
非顺序映像的特点是
借助指示元素存储地址的指针来
表示数据元素之间的逻辑关系
这样讲比较抽象
下面我们以线型结构为例来看一下什么是逻辑结构
什么是存储结构，顺序映像和非顺序映像又是怎么回事
我们介绍过线性表就是一个序列，在逻辑结构的层面上
也就是针对程序设计者的描述形式，线性表的描述形式有以下三种
第一种是按照它的序列，a1a2一直到an把它写成一行
对行中元素来说，站在它前面的，就是它的前驱
站在它后面的，就是它的后继
第二种是图示
每一个数据元素加一个圆圈
把它叫做一个顶点
如果两个数据元素之间是前驱和后继的关系
我们就从前驱顶点引一个箭头到后继顶点
从图中可以看出a1有一个箭头指向a2， a2有个箭头指向a3
以此类推一直到an
第三种是形式化的描述
首先是一个集合D，是数据元素的集合
第二个集合S是在D上定义的，数据元素之间关系的有限集
S中怎么描述关系的呢？
它是用一个有序对描述数据元素前驱和后继的关系
有序对是一个尖括号，括号中有两个数据元素
它的含义是第1个元素的后继是第2个元素
对称的第2个元素的前驱是第1个元素
例如， 一个尖括号中的元素是a1a2
这个有序对描述了a1的后继是a2，或者对称的说a2的前驱是a1
同理a2和a3，a3和a4，一直到an-1和an这样的有序对
这些有序对作为集合S的元素，一起描述了a1到an这样一个序列
我们要注意，这三种形式虽然描述形式上有差异
但是他们本质是一样的，都是描述了线性表
是一个序列这样的一个情况
在教材中，这三种描述的形式都会见到
我们要强调的是，三者是完全等价的。
要利用计算机处理数据，逻辑结构最终毕竟要在计算机内部加以实现
这就是所谓的物理结构，或者叫存储结构
前面已经提到数据结构的存储涉及到两个问题
数据元素的存储和数据元素之间关系的表示
数据元素的存储很容易实现，麻烦的是数据元素之间关系的表示
主要有两种办法，顺序映像和非顺序映像
下面我们就以线性表为例，看一下这两种存储结构的实现方式
顺序映像是说借助元素在存储器中的相对位置来描述元素之间的逻辑关系
对于线性结构的存储，我们是这样来处理的
我们利用一个数组来存储线性表，数组的大小是n
数组的类型是数据元素的类型
随后，按照线性表的逻辑结构，也就是a1a2到an这样的顺序
依次把线性表的n个元素，存放在数组0~n-1的n个单元当中
在这里，我们是借助数据元素在数组当中存储位置的相邻
暗示它们之间前驱和后继的关系
从图中
我们可以看到ai存放在i-1这个下标单元，ai-1存放在i-2这个下标单元
这两个单元是相邻的位置，我们就是通过这个相邻
暗示了ai-1的后继是ai，或者对称的说ai的前驱是ai-1
同理其他元素之间也是这样的，借助位置的相邻
暗示前驱和后继的关系
非顺序映像是借助指针来描述关系
对线性表来说，可以申请一个节点存储a1
然后呢，申请另外一个节点把a2存放好
为了描述a1的后继是a2，在存a1的节点中附设一个指针
用这个指针指向存储a2这个节点的地址
通过这个指针明确的指示，a1的后继是a2
同理，a2附设一个指针指向a3的节点
依次类推，直到an-1节点的指针指向an的节点
当然作为线性表的最后一个元素，an是没有后继的
那么，我们就把它指向后继的指针置空
表示已经没有后继元素了
通过线性表的例子我们看到
数据结构也就是数据和他们之间的关系
在逻辑结构的层面上是怎么描述的
在物理结构的层面上又是怎么描述的
当然树和图的描述更复杂一些
我们后面再讨论
下面，我们引入另外一个重要的概念--操作
好了，同学们
我们今天的课就到这
下节课再见
-1.算法概念导入
-2.数据结构课程介绍
-0.1变量、类型和表达式
-0.2 函数
--0.2 函数
-0.3 指针和单链表
-0.4 数组、指向函数的指针
-1.1什么是数据结构
--测试题
-1.2基本概念和术语
--测试题
-1.3数据结构的描述
--测试题
-1.4抽象数据类型的定义和实现
--测试题
-1.5算法和算法分析概念
--测试题
-1.6算法分析示例
--测试题
-2.1 线性表的类型定义
--测试题
-2.2线性表的顺序表示和实现
--测试题
-2.3 线性链表
--2.3 线性链表
--测试题
-2.4 静态链表
--2.4 静态链表
--测试题
-2.5 循环链表和双向链表
--测试题
-3.1 栈
--3.1栈
--测试题
-3.2 栈的实现
--3.2 栈的实现
--测试题
-3.3 栈的应用
--3.3 栈的应用
-3.4 栈与递归的实现
--测试题
-3.5 队列和链队列
--测试题
-3.6 循环队列
--3.6 循环队列
--测试题
-4.1 串
--4.1 串
--测试题
-5.1 数组定义和表示
--测试题
-5.2矩阵的压缩存储
--测试题
-6.1 树的定义和基本术语
-6.2 二叉树和二叉树的性质
--测试题
-6.3 二叉树的存储结构
--测试题
-6.4 遍历二叉树
--测试题
-6.5 线索二叉树
--测试题
-6.6 树的存储
--6.6树的存储
-6.7 树的转换和遍历
--测试题
-6.8 赫夫曼树
--6.8 赫夫曼树
-6.9 赫夫曼编码
--测试题
-7.1 图的定义和术语
--测试题
-7.2 图的存储结构
--测试题
-7.3 图的遍历
--测试题
-7.4 最小生成树
--测试题
-7.5 有向无环图
--测试题
-7.6 最短路径
--测试题
-8.1 查找基本概念和顺序查找
--测试题
-8.2 有序表的查找
--测试题
-8.3 二叉排序树
--测试题
-8.4 平衡二叉树
--测试题
-8.5 哈希表
--测试题
-9.1插入排序
--测试题
-9.2 希尔排序
--9.2 希尔排序
--测试题
-9.3 快速排序
--9.3 快速排序
--测试题
-9.4 选择排序
--9.4 选择排序
--测试题
-9.5 堆排序
--9.5 堆排序
--测试题
-9.6 归并排序
--9.6 归并排序
--测试题
-9.7 基数排序
--9.7 基数排序
--测试题
-9.8 排序方法总结
