1.1什么是数据结构在线视频

同学们，大家好

我是云南大学信息学院的教师孔兵

这一节我们开始进入教材的学习

第一章绪论

从计算机学科的角度来看，计算机科学是一门研究

用计算机进行信息表示和处理的科学

那么在这里就涉及到了两个问题，一个是信息的表示

一个是信息的处理，这两个问题是有次序的

首先是信息的表示和组织，在此基础上

才谈得上对信息的处理

而信息的表示和组织又直接关系到信息处理的效率

因此，为了编写一个好的程序，我们必须分析待处理对象的特征

以及各对象之间存在的关系

数据结构这门课程所研究的问题主要是信息的表示问题

从上面的讨论可以看出

数据结构这门课程在计算机学科中是非常重要的

数据结构，从名字上看可以分成两个词，数据和结构

数据是我们待处理的对象，也就是问题中涉及到的数据

在很多问题中，为了完成用户的功能需求，不仅需要考虑数据

还需要考虑数据之间的关系，也就是说数据并不是孤立的

它们之间是有关系的，数据结构中的“结构”说的就是它们之间的关系

那么，数据结构简单概括地解释一下就是

“数据以及它们之间的关系”

本章我们主要介绍这样的几个内容，第1节什么是数据结构

首先看看使用计算机解决一个问题的过程

一般有这样的三个步骤，一是从具体问题当中抽象出一个适当的数学模型

在程序设计这个领域，所谓的数学模型实际上指的是数据以及它们之间关系

也就是说的数据以及它们之间关系构成了具体问题的数学模型

有了这样一个描述具体问题的数据

以及它们之间关系的数学模型以后，为了完成用户的功能需求

需要在此数学模型上设计解此数学模型的算法

也就是处理数据，完成用户的功能需求

最后一步是用程序设计语言描述数据结构

也就是数学模型，实现步骤1的内容，描述算法

实现步骤2的内容，当然程序还需要测试等工作

最后获得问题的解

后面的课程中，我们会讨论用程序设计语言描述数据结构

也会针对具体的功能需求，讨论用程序设计语言描述算法

下面我们来通过几个具体问题的例子来看一下什么是数据结构

什么是解此数据结构的算法

第1个例子是图书馆中图书的例子

我们可能都有这样的直观印象

每本图书根据图书分类法都有一个书号

整个图书馆的书，按照这样一个书号排成一个序列

在书架上就是一排一排的样子，在这个序列中

书与书之间是有关系的，对任意一本书来说

排在它前面的书，书号比它小一点，排在它后面的书

书号比它大一点，我们能直观的感到

这样一个序列对图书管理非常重要，它确定了每本书在书架上的位置

没有这样的序列，图书的管理一定是混乱不堪的

这样的序列就是我们前面提到的线性结构，在这个问题当中

它的数学模型或者说数据结构就是线性结构

有了这样的数据结构，可能需要实现一些功能

比如说查找某一本书

我们可以通过一个算法来实现这个功能

在第九章，我们会介绍高效的查找算法

编制程序这个步骤我们就不讨论了，后面再讲

下面看一个人机对弈的例子，这个例子是一个井字棋的例子

有两种棋子，圈和叉，当一方的3个棋子占同行、同列或斜线时为胜

那么，计算机怎样实现人机对弈呢？

它背后需要数据结构的支持，这个数据结构是树形结构

我们把某一时刻棋盘上的状态称为一个格局

代表棋盘上双方棋子分布的一个状况

初始的时候棋盘上没有棋子是一个空格局

假设从持圈这方开始，根据目前的格局

它可以下子的地方是9个格子中任何一个

我们就说从这个空的格局，根据落子情况的不同

可以演化为9个不同的格局

这九个格局是初始空格局所有可能的变化

我们用一个箭头来表示这种演化，箭头尾部叫做双亲

箭头头部就叫做孩子

那么空格局有9个孩子

我们观察图中第2排第1个格局

现在轮到叉落子

一个格子已经被圈占了，它可以落子的还剩下8个格子

同理，我们说从这个格局，可以演化为如图所示的8个格局

这样的过程，可以不断的重复下去，到某个格局

如果能够确定胜、负或平，则停止演化过程

这样的格局称为树的叶子，那么整个演化过程的结果就是一棵树

这颗树描述了所有可能的对弈情况

从空格局开始沿着箭头到达某个叶子的路线，描述了一次对弈的过程

我们经常说一个人下棋很厉害，他可以看几步

人机对弈的时候，人机对弈程序内部存储有这样的一棵树

当人落子以后，程序在这棵树上进行搜索判断

它可以看到最后一步，随后选择最合理的应对招数

这种情况下，人不太可能战胜机器

当然，这样的方式是受限制的，

比如说围棋

因为围棋变化的状况格局太多，造成所谓的组合爆炸

这样的数据规模是计算机所不能处理的

现在的高水平的围棋程序采用的是另外的思路和算法

就是所谓的深度学习的方法

教材中的例3是一个图的例子，多叉路口交通灯的管理问题

首先给每个路口一个英文字母的编号，图中有A,B,C,D,E五个路口

用两个字母描述一条通道

例如DA，表示从D路口出来进入A路口的这条通道

为了交通安全，有的通道可以同时开放

有的通道不能同时开放，例如DA和AB就不能同时开放

问题的目的是设计这个五岔路口的交通灯管理程序

进行交通灯的控制。当某个颜色的交通灯发光时，一些通道开放

当然这些通道必须是可以同时开放的，其它通道关闭

我们把这个问题建模为一个图，每条通道是图中一个顶点

如图AB

如果两条通道不能同时开放

则在这两个顶点之间画一条边

图中AB和DA不能同时开放，我们画了一条边

如果两个顶点之间有边，我们称它们为相邻顶点

完整的图在教材第三页图1.3

有了这个图结构以后，可以利用图着色算法

给每个顶点着一个颜色，只需要保证相邻顶点之间的颜色不同即可

图1.3中给出了一个着色的方案，用1-4的数字表示不同的颜色

就是说可以在路口设置包含4种颜色的交通灯

当某种颜色的交通灯发光时

其对应的通道可以开放

例如颜色2的交通灯发光时，BC,BD,EA可以通行，其它通道关闭

在这个问题中，我们把多叉路口交通灯的管理问题建模为图结构

通过在图结构上设计一个图着色的算法解决了这个问题

是非常有创意的办法

好了同学们

我们今天的课程就到这里

下节课再见