1第一章 绪论6学时.docx

1第一章 绪论6学时.docx

《1第一章 绪论6学时.docx》由会员分享，可在线阅读，更多相关《1第一章 绪论6学时.docx（13页珍藏版）》请在冰点文库上搜索。

1第一章绪论6学时

2008至2009学年第一学期

课

时

教

案

课程名称（编码）：

数据结构与算法（84160）

总学时／周学时：

68/4

开课时间：

2008-2009学年第1学期第2周至第19周

授课年级、专业、班级：

2007级计算机科学与技术（嵌入式）

使用教材：

数据结构（C语言版）

授课教师：

薛明亮

课时教案

周次

第周第1次课

课题

课程简介

§1.1什么是数据结构？

授课

类型

理论课（√）、实践课（）、实习（）

时间设计

授

课

内

容

与

教

学

设

计

课程简介

一、07级计算机科学技术专业培养方案

二、《数据结构与算法》的内容与历史简介

1、本课程的地位：

2、《数据结构与算法》的基本内容

3、《数据结构与算法》的历史简介

三、学习方法

四、教材与参考书

本课程选用的教材：

赵坚姜梅主编《数据结构（C语言版）》北京：

中国水利水电出版社2005（2006重印）

参考书：

１、赵坚姜梅主编《数据结构（C语言版）学习指导与习题解答》。

北京：

中国水利水电出版社2005（2006重印）

２、马秋菊等编《数据结构（C语言描述）》。

北京：

中国水利水电出版社2006（2007重印）

五、作业要求全交/全批。

六、课程安排、考核及成绩评定方法

总学分：

4；总学时：

68。

考核：

闭卷考试。

期中（第十周前后）测验，期末期终考试。

成绩评定：

平时成绩（作业、到课率、课堂提问回答等）10%，期中测验20%，期末考试70%。

第1章绪论

教学目的与要求

本章主要介绍数据结构课程中的一些常用术语以及集合、线性结构、树型结构和图形结构等常用结构的表示，用C语言实现算法描述的一般规则，算法的时间和空间复杂度分析与评价。

要求学生掌握数据结构中的常用术语；集合、线性结构、树型结构和图形结构等每一种常用数据结构的逻辑特点；抽象数据类型的定义、使用，算法的定义、特性及用C语言描述的规则；评价算法优劣的规则，算法的时间、空间复杂度的定义及数量及的表示；复习C语言中的有关语法规则，以便满足在数据结构课程中进行算法描述的需要。

§1.1什么是数据结构

1.1.1数据结构示例

【例1-1】图书目录表

表1-1图书目录表

由于表中每条记录（表示每一本书）的登录号各不相同，所以可用登录号来唯一地标识每条记录（一本图书）。

在计算机的数据管理中，能唯一地标识一条记录的数据项被称为关键字。

因为每本图书的登录排列位置有先后次序，所以在表中会按登录号形成一种次序关系，即整个二维表就是图书数据的一个线性序列。

这种关系被称为线性结构。

【例1-2】磁盘目录结构和文件管理系统

描述磁盘目录和文件结构时，假设每个磁盘包括一个根目录（root）和若干个一级子目录，每个一级子目录中又包含若干个二级子目录….这种关系很像自然界中的树，所以称为目录树。

如图1-1目录树所示。

在这种结构中，目录和目录以及目录和文件之间呈现出一对多的非线性关系。

即根root有多个下属（也称为后代），每一后代又有属于自己的后代；而任一个子目录或文件都只有一个唯一的上级（也称为双亲）。

称这种数学模型为树型数据结构。

图1-1目录树

【例1-3】教学计划编排问题

表1-2教学计划编排表图1-2图形结构

假如一个教学计划中包含许多课程。

在课程之间，有些必须按规定的先后次序排课，如：

学C6课程必须先学C3课，学C3课程必须先学C1课。

这些课程之间存在先修和后续的关系。

在这种结构中，表示课程的数据之间呈现多对多的非线性关系，称这类数学模型为图形结构。

图结构还有：

多岔路口交通灯的控制和管理、煤气管道的铺设造价等。

通过以上几例可以认为：

数据结构就是研究数据的逻辑结构和物理结构以及它们之间相互关系，并对这种结构定义相应的运算，而且确保经过这些运算后所得到的新结构仍然是原来的结构类型。

1.1.2基本概念和术语

1．数据（Data）

数据（Data）：

是对信息的一种符号表示。

在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。

包括文字、表格、图像等。

例如，一个图书管理程序所要处理的数据可能是一张表格。

如表1-1所示。

2．数据元素（DataElement）

数据元素（DataElement）：

是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。

一个数据元素可由若干个数据项组成。

数据项是数据的不可分割的最小单位。

例如，在表1-1所示的图书目录表中，为了便于处理，把其中的每一行（代表一本书）作为一个基本单位来考虑，故该数据由7个结点构成。

一般情况下，一个结点中含有若干个字段（也叫数据项）。

字段是构成数据的最小单位。

3．数据对象（DataObject）

数据对象（DataObject）：

是性质相同的数据元素的集合。

是数据的一个子集。

4．数据类型（DataType）

数据结构（DataStructure）：

是相互之间存在一种或多种特定关系的数据元素的集合。

例如，整型、字符型、浮点型、双精度型等数据类型，分别是一组相同结构的值以及在这些值上允许进行操作的总称。

5．抽象数据类型（AbstructDataType，简称ADT）

ADT是指一个数学模型以及定义在该模型上的一组的操作。

可以看作是数据的逻辑结构及其在逻辑结构上定义的操作。

抽象数据类型的定义仅取决于它的一组逻辑特性，而与其在计算机内部如何表示和实现无关。

1.1.3数据结构（DataStructure）

数据结构是研究数据元素（DataElement）之间抽象化的相互关系（逻辑结构）和这种关系在计算机中的存储表示（物理结构），并对这种结构定义相适应的运算，设计出相应的算法。

数据结构主要指逻辑结构和物理结构。

1.逻辑结构：

数据之间的相互关系称为逻辑结构。

通常分为4类基本结构：

＊集合：

结构中的数据元素除了同属于一种类型外，别无其它关系。

＊线性结构：

结构中的数据元素之间存在一对一的关系。

＊树型结构：

结构中的数据元素之间存在一对多的关系。

＊图状结构或网状结构：

结构中的数据元素之间存在多对多的关系。

在表1-1所示的表格中，由7个结点（数据元素）组成，每个数据元素又包括6个数据项（字段）。

各结点之间在逻辑上有一种线性关系，它指出了7个结点在表中的排列顺序。

这张表的逻辑结构就是数据元素（或是结点、记录）之间的关系。

对于表中的任一个结点（记录），都只有一个前驱结点，也只有一个后继结点，整个表只有一个开始结点和一个终端结点。

此表的逻辑结构是线性的。

四类数据基本结构的示意图：

（a）集合结构（b）线性结构（c）树型结构（d）图形结构

由以上例子可见，描述这类非数值计算问题的数学模型和方法不再是数学方程，而是诸如线性表、树和图之类的数据结构。

数据对象可以是有限的，也可以是无限的。

数据结构不同于数据类型，也不同于数据对象，它不仅要描述数据类型的数据对象，而且要描述数据对象各元素之间的相互关系。

2.存储结构：

数据结构在计算机中的存储表示称为数据的存储结构。

它包括数据元素的表示和关系的表示。

表1-1所示的表格数据在计算机中可以有多种存储表示：

数据既可以存放在一块连续的内存单元中，通过元素在存储器中的位置来表示它们之间的逻辑关系（顺序）；也可以随机分布在内存中的不同位置，通过指针元素表示数据元素之间的逻辑关系（链式）。

这两种不同的表示方法对应有四种不同的存储结构（亦称方式）：

顺序存储结构、链式存储结构、索引存储结构和散列存储结构。

（1）顺序存储结构是把逻辑上相邻的结点存储在物理上相邻的存储单元里，结点之间的逻辑关系由存储单元位置的邻接关系来体现。

优点：

占用较少的存储空间；

缺点：

由于只能使用相邻的一整块存储单元，因此可能产生较多的碎片现象。

顺序存储结构通常借助程序语言中的数组来描述。

顺序存储结构主要应用于线性的数据结构。

（2）链式存储结构将结点所占的存储单元分为两部分，一部分存放结点本身的信息，另一部分存放结点的后继结点地址，结点间的逻辑关系由附加的指针字段表示。

链式存储结构常借助于程序语言的指针类型描述。

优点：

不会出现碎片现象，充分利用所有的存储单元；缺点：

每个结点占用较多的存储空间。

（3）索引存储方式是用结点的索引号来确定结点的存储地址。

在储存结点信息的同时，要建立附加的索引表。

优点：

检索速度快。

缺点：

增加了附加的索引表，占用较多的存储空间；在增加和删除数据时需要修改索引表而花费较多时间。

（4）散列存储方式是根据结点的关键字值直接计算出该结点的存储地址。

通过散列函数把结点间的逻辑关系对应到不同的物理空间。

优点:

检索、增加和删除结点的操作都很快；缺点:

当采用不好的散列函数时可能出现结点存储单元的冲突，为解决冲突需要附加时间和空间的开销。

3．数据的运算

数据运算定义在数据的逻辑结构上，即施加于数据的操作。

例如对一张表的记录进行查找、增加、删除、修改，这就是对数据的运算。

4．数据结构三方面的关系

数据的逻辑结构、数据的存储结构及数据的运算三方面构成一个数据结构的整体。

存储结构是对数据项的存储。

同一逻辑结构可用不同存储结构就对应不同的存储标识。

例如，线性表若采用顺序存储方式，称为顺序表；若采用链式存储方式，称为链表；若采用散列存储方式，可称为散列表。

1学时

5学时

2学时

授课重点、难点

教学重点：

熟悉数据结构常用术语，掌握基本概念，了解算法时间复杂度和空间复杂度的分析与评价。

教学难点：

数据元素间的四种结构关系。

课堂讨论、思

考题、

作业

思考题：

1、大千世界的数据可以划分为几种？

2、数据结构有几种基本类型？

3、数据的存储结构有几种？

教

学

后

记

课时教案

周次

第周第2次课

课题

§1.2算法描述

§1.3算法分析与评价

授课

类型

理论课（√）、实践课（）、实习（）

时间设计

授

课

内

容

与

教

学

设

计

§1.2算法描述

1.2.1算法

1、定义：

算法（Algorithm）是对特定问题求解步骤的一种描述，是指令的有限序列。

一个好的算法通常要达到以下的要求：

•正确。

执行结果应当满足预先规定的功能和性能要求。

•可读。

应当思路清晰、层次分明、简单明了、易读易懂。

•健壮。

当输入不合法数据时，应能作适当处理，不至引起严重后果。

•高效。

有效使用存储空间和有较高的时间效率。

2、算法的特点

算法是执行特定计算的有穷过程。

这个过程有5个特点：

1）动态有穷：

当执行一个算法时，不论是何种情况，在经过了有限步骤后，这个算法一定要终止。

2）确定性：

算法中的每条指令都必须是清楚的，指令无二义性。

3）输入：

具有0个或多个由外界提供的量（输入）。

4）输出：

产生1个或多个结果。

5）可行性：

每条指令都充分基本，即：

序列中的每个操作都是可以简单完成的，都可以通过已经实现的基本操作运算的有限次来实现。

注意：

算法和程序是有区别的，即程序未必能满足动态有穷。

在本书中只讨论满足动态有穷的程序，因此“算法”和“程序”是通用的。

1.2.2算法描述

一个算法可以用自然语言、数字语言或流程图等来描述，也可以用计算机高级程序语言来描述，如Pascal语言、C语言或伪代码等，本书选用C语言作为描述算法的工具。

1．用自然语言描述算法

用日常的自然语言来描述算法（可以是英文,也可以是其它文字语言）。

优点：

简单，便于人们对算法的阅读。

缺点：

不够严谨。

2．用流程图描述算法

使用程序流程图，N-S图等描述算法。

特点是描述过程简洁、明了。

目前在一些高级语言程序设计中仍然被采用。

但用这两种方法描述的算法不能直接在计算机上执行，必须通过编程将它转换成可执行程序。

3．用程序设计（C或C++）语言描述算法。

可以直接使用程序设计语言（如C或C++）描述算法，但直接使用程序设计语言不太容易且不直观，且需要借助于注释才能看明白。

为解决理解与执行的矛盾，常使用一种称为伪码（类）语言的描述方法来进行算法描述。

类语言介于高级程序设计语言和自然语言之间，它忽略高级程序设计语言中一些严格的语法规则与描述细节，因此它比程序设计语言更容易描述和被人理解，而且比自然语言更接近程序设计语言。

它虽然不能直接执行但很容易被转换成高级语言。

1.3算法分析与评价

1.3.1算法设计的要求

•正确性。

执行结果应当满足预先规定的功能和性能要求。

•可读性。

应当思路清晰、层次分明、简单明了、易读易懂。

•健壮性。

当输入不合法数据时，应能作适当处理，不至引起严重后果。

•高效性和存储量需求。

有效使用存储空间和有较高的时间效率。

1.3.2算法效率的度量

1．时间复杂度（Timecomplexity）

一个算法的时间复杂度是指算法运行从开始到结束所需要的时间。

通常是所处理问题规模的一个函数T（n），常采用数量级的形式表示。

记作：

T（n）=O（f（n）），称T（n）为算法的（渐近）时间复杂度。

2．空间复杂度（Spacecomplexity）

一个算法的空间复杂度是指算法运行从开始到结束所需的存储量。

算法的存储量指的是算法执行过程中所需的最大存储空间。

算法执行期间所需要的存储量应该包括以下三部分：

（1）输入数据所占空间；

（2）程序本身所占空间；

（3）辅助变量所占空间。

类似于算法的时间复杂度，通常以算法的空间复杂度作为算法所需存储空间的量度。

定义：

S（n）=O（g（n）），称S（n）为算法的空间复杂度。

2学时

1学时

授课重点、难点

教学重点：

熟悉数据结构常用术语，掌握基本概念，了解算法时间复杂度和空间复杂度的分析与评价。

教学难点：

数据元素间的四种结构关系。

课堂讨论、思

考题、

作业

作业：

P12-14一、二、三、四。

教

学

后

记