2.数据结构课程介绍在线视频

同学们，大家好

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

上一节课我们引入了算法的概念

算法是对解决问题方法和步骤的描述

我们强调，所谓算法就是过程性的知识

算法在计算机科学当中是以程序的形态呈现的

而程序不外乎就是用程序设计语言描述的算法

作为我们唯一的工具

用计算机求解任何问题都离不开程序设计

我们需要把解决问题的算法

用程序设计语言加以描述

并在计算机这个工具上执行它

从而获得我们想要的结果

数据的组织和建模是程序设计的基础

大家都学过程序设计，自己编制过程序

应该注意到程序当中包含两个部分

一个部分是定义和说明需要处理的对象也就是数据

另外一部分呢

是程序设计语言所描述的处理数据的过程，就是算法

合理且适当的数据组织

有助于我们设计精巧和高效的程序

这里所谓的数据组织就是数据结构课程要讨论的内容

同样，合理且适当的数据组织也是我们设计和实现如编译程序

操作系统、数据库系统及其他系统程序

和大型应用程序的重要基础

从上述的讨论可以看出

合理且适当的数据组织对我们编程而言是非常重要的

我们的课程目标也就是

通过课程的学习使我们掌握数据组织的方法和技巧

提高我们程序设计的水平

著名计算机科学家尼克拉斯.维斯曾经说过

数据结构加算法就是程序

从这也可以看出数据结构对程序设计而言是基础

是不可或缺的，体现了数据结构的重要性

下面我们看一下本课程学习当中的主要内容

数据是需要我们处理的对象，在实际的问题背景下

数据之间实际上不是孤立的，他们是有关系的

也就是说他们是有结构的

在课程当中，会涉及到4种数据结构

第1种称为集合，所谓集合

就是说我们不强调数据之间的关系

他们之间是没有关系的，在排序和查找这两个章节中

处理的对象就是集合结构的数据

第2种称为线性结构

线性结构中所有的数据能形成一个序列

每个数据在这个序列中有一个唯一的位置

可以从图中看到，我们用一个箭头表示关系

箭头的尾部我们称为前驱

箭头所指的那个数据我们称为后继

后面讨论中我们把箭头称为弧

除了第1个和最后一个数据元素以外

在线性结构当中每个数据元素

都有一个唯一的前驱和一个唯一的后继

第1个元素没有前驱，最后一个元素没有后继

他们形成一个序列

线性结构的一个具体例子是图书馆中的书籍

我们知道图书馆中的每本书都有一个书号

整个图书馆的书按照这样一个书号

形成了一个序列

对每本书而言

它前一本书（前驱）的书号比它小一些

后一本书（后继）的书号比他大一些

第3种称为树结构，它有一个明显的层次关系

在树结构当中，每个结点有一个唯一的前驱

但一个元素可能有多个后继

如图所示，整体结构很像一颗倒的树

所以被叫做树结构

树结构的一个典型例子是家谱

在家谱当中

我们通过父子关系来描述一个家族成员之间的关系

那么对于家族中的成员来说

他有一个唯一的父亲

前驱

但是他可能有多个孩子

后继

它的特征是一个前驱，多个后继

刚才我们在线性结构中说

线性结构的特征是一个前驱，一个后继

从描述来看，线性结构是树结构的一种特殊形态

比如说一个家族当中，每一代都只有一个成员的话

那他们的家谱就自然退化成了一个线性结构

第4种称为图结构

这里我们也是通过前驱和后继来描述图结构关系的特征

它是多个前区和多个后继

现在我们看一下图结构示例，看一下这个图

假设图中的数据是对人的描述

弧描述的是一个爱慕的关系

从张三画一个箭头到李四

表示张三爱慕李四

当然张三可能爱慕其他的几个人

也就是说张三可能有多个后继

自然，也可能有多人爱慕张三

也就是说张三可能有多个前驱

这样就形成了有向图

特点是多个前驱，多个后继

再看下一个图

图中没有箭头

它可以说是有向图的一种特例

如果在一些背景下，关系总是成对出现的

也就是说a到b有关系

则b到a必有关系

这个时候呢，可以用一条直线来代表两条弧

我们把这样的直线称为边，形成了无向图

例如朋友关系图

假设从张三到李四的弧表示张三认为李四是朋友

那么一般而言李四也会认为张三是朋友

如果是单向的，这样的关系恐怕不能被称为朋友关系

在数据结构定义实现的基础上

我们会定义基于数据结构的基本操作

基本操作是指该结构上最基础

当然也是最重要的操作

以线性结构为例，比如说图书馆买了一本书

那么就会产生一个插入的操作

一本书如果已经坏了

那么需要从图书馆里把它剔除

这就产生了一个删除的操作

哪些操作应该被定义为基本操作呢

实际上并没有一个明确的原则

一般是在该结构上使用最频繁，经常被调用的操作

定义基本操作的目的是什么呢

本质上是提供一个对外的接口

给应用程序使用

应用程序要实现的功能可能是比较复杂的

它可以通过调用组合基本操作

来实现更复杂的针对问题的功能

在这种情况下，应用程序唯一要打交道的是接口

而内部基本操作和数据结构

如何实现

对于应用程序而言

实际上是透明的

这样的程序组织形式有利于降低问题的复杂性

形成良好的程序结构

下面看一下课程的参考书

教材在前面已经介绍过

在这儿列出了几本参考书

每本都有它的长处

大家在学习的过程中

可以根据自己的需要有选择的去阅读

好了，同学们

我们今天的课程就到这里

下节课再见