第讲绪论课件.

《第讲绪论课件.》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构与算法(C++版)课件第1章绪论数据结构讨论的范畴对于数值计算问题的解决方法，主要是用数学方程建立数学模型，例如天气预报的数学模型为二阶椭圆偏微分方程预测人口增长的数学模型为常微分方程求解这些数学模型的方法是计算数学研究的范畴，比如采用差分算法有限元算法无限元算法对于非数值计算问题，主要采用数据结构的方法建立数学模型下面通过实例加以说明“学生”表格UNIX文件系统的系统结构图/(root)binlibuseretcmathdsswyintaoxieStack.cppQueue.cppTree.cpp要在n个网站建立通信网格，要求使得网络中任一网站出现故障时，整个网络

2、仍能正常通信，如图所示，这些网站之间形成一种图结构综合以上例子可见，描述这类非数值计算问题的数学模型是诸如表、树和图之类的数据结构因此简单说来，数据结构的研究范畴主要是非数值计算问题的操作对象及其它们之间的关系以及在计算机中的表示和实现数据结构基本概念数据（data）数据是信息的载体，是描述客观事物的数、字符、以及所有能输入到计算机中，被计算机程序识别和处理的符号的集合数值性数据非数值性数据数据元素(dataelement)数据的基本单位。在计算机程序中常作为一个整体进行考虑和处理有时一个数据元素可以由若干数据项(DataItem)组成。数据元素又称为元素、结点、记录什么是

3、数据结构定义:由某一数据元素的集合及该集合中所有数据元素之间的关系组成记为：Data_Structure=(D,S)其中，D是某一数据元素的有限集合，S是该集合中所有数据元素之间的关系组成的有限集合数据的逻辑结构数据的逻辑结构从逻辑关系上描述数据，与数据的存储无关数据的逻辑结构可以看作是从具体问题抽象出来的数学模型数据的逻辑结构可归结为以下四类线性结构树形结构图状结构集合结构数据的存储结构数据的存储结构是逻辑结构用计算机语言的实现数据的存储结构依赖于计算机语言顺序存储结构链式存储结构顺序存贮所有元素存放在一片连续的存贮单元中，逻辑上相邻的元素存放到计算机内存仍然相邻链式存贮

4、所有元素存放在可以不连续的存贮单元中，但元素之间的关系可以通过地址确定，逻辑上相邻的元素存放到计算机内存后不一定是相邻的数据类型数据类型定义：一组性质相同的值的集合,以及定义于这个值集合上的一组操作的总称如C语言中有如下数据类型charintfloatdoublevoid字符型整型浮点型双精度型无值构造数据类型由不同成员构成基本数据类型可以看作是计算机中已实现的数据类型是指一个数学模型以及定义在此数学模型上的一组操作。抽象数据类型(ADT:AbstractDataType)ADT有两个重要特征抽象性用ADT描述程序处理的实体时，强调的是其本质的特征、其所能完成的功能以及它和

5、外部用户的接口（即外界使用它的方法）封装性将实体的外部特性和其内部实现细节分离，并且对外部用户隐藏其内部实现细节抽象数据类型的表示和实现抽象数据类型需要通过固有数据类型(高级编程语言中已实现的数据类型)来实现,本书由类模板或类来实现。算法算法是为了解决某类问题而规定的一个有限长的操作序列算法定义算法应具有的性质正确性具体性确定性有限性可读性健壮性正确性正确性指必须完成所期望的功能，对算法是否“正确”的理解可以有如下四个层次：（1）程序中不含任何语法错误。（2）程序对于几组输入数据能够得出满足要求的结果。（3）程序对于精心选择的、典型的、苛刻的并带有刁难性的几组输入数据能够得

6、出满足要求的结果。（4）程序对于一切输入数据都能得出满足要求的结果。具体性一个算法必须由一系列具体操作组成，这时的“具体”指的所有操作都必须经过已实现的基本操作有限次来实现，并且所有操作都是可读的、可执行的，每一操作必须在有限时间内完成。确定性算法中的所有操作都必须有确切的含义，不能产生歧义，算法的执行者或阅读者都能明确其含义及如何执行。有限性对于任意一组合法输入值，在执行有限步骤之后一定能结束，即：算法中的每个步骤都能在有限时间内完成可读性算法应具备良好的可读性，这样的算法有利于算法的查错及对算法的理解，一般算法的逻辑必须清楚、结构简单，所有标识符必须具有实际含义，能见名

7、知义。健壮性健壮性指当输入数据非法时，算法能作适当的处理并作出反应，而不应死机或输出异常结果算法描述方法用自然语言描述算法用我们日常生活中的自然语言（可以是中文形式，也可以是英文形式）也可以描述算法用流程图描述算法一个算法可以用流程图的方式来描述，输入输出、判断、处理分别用不同的框图表示，用箭头表示流程的流向。这是一种描述算法的较好方法，目前在一些高级语言程序设计中仍然采用。也有其他的图形辅助工具用其它方式描述算法我们还可以用数学语言或约定的符号语言来描述算法用C++描述算法在本课中，我们将采用C++来描述算法,所