《数据结构清华第一章绪论.ppt

第一章 绪论 §1.1 什么是数据结构 例2 书目自动检索系统 例3 人机对奕问题 例4 教学计划编排问题 数据的逻辑结构：只抽象反映数据元素的逻辑关系。 有两种衡量算法效率的方法: 1.事后统计法：利用计算机内记时功能，用一组或多组相同的统计数据区分。 2.事前分析估计法：求出算法的一个时间界限函数。 三、抽象数据类型 (Abstract Data Type 简称ADT) ADT定义： 指一个数学模型以及定义在该模型上的一组操作。 “抽象”的意义在于数据类型的数学抽象特性。 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 例如： 矩阵 +（求转置、加、乘、求逆、求特征值） 构成一个矩阵的抽象数据类型。 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. ADT的描述方法： 抽象数据类型可用三元组 （D，S，P） 表示。 其中：D 是数据对象； S 是 D 上的关系集； P 是对 D 的基本操作集。 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. ADT 抽象数据类型名 { 数据对象：〈数据对象的定义〉 数据关系：〈数据关系的定义〉 基本操作：〈基本操作的定义〉 } ADT 抽象数据类型名 其中基本操作的定义格式为: 基本操作名（参数表） 初始条件：〈初始条件描述〉 操作结果：〈操作结果描述〉 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 赋值参数:只为操作提供输入值。 引用参数:以打头，除可提供输入值外， 还将返回操作结果。 初始条件:描述了操作执行之前数据结构和参数应满足的条件，若不满足，则操作失败，并返回相应出错信息。 操作结果:说明了操作正常完成之后，数据结构的变化状况和应返回的结果。若初始条件为空，则省略之。 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 例如，抽象数据类型复数的定义： 数据对象： D＝{e1,e2｜e1,e2∈RealSet } 数据关系： R1＝{e1,e2 | e1是复数的实数部分 | e2 是复数的虚数部分 } ADT Complex { Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 基本操作： AssignComplex( Z, v1, v2 ) 操作结果：构造复数 Z,其实部和虚部 分别被赋以参数 v1 和 v2 的值。 DestroyComplex( Z) 操作结果：复数Z被销毁。 GetReal( Z, realPart ) 初始条件：复数已存在。 操作结果：用realPart返回复数Z的实部值。 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. GetImag( Z, ImagPart ) 初始条件：复数已存在。 操作结果：用ImagPart返回复数Z的虚部值。 Add( z1,z2, sum ) 初始条件：z1, z2是复数。 操作结果：用sum返回两个复数z