天津理工大学数据结构.pptVIP

计算机科学与工程系 计算机科学与工程系 第一章 绪 论 数据结构研究内容 基本概念和术语 算法定义 算法性能分析与度量 1.1 数据结构研究内容 1）计算机解决问题的步骤 分析具体问题 问题可分为两类： 可以用数学方程描述—数值计算类问题 例：总额为一元的硬币，问1,2,5分硬币各几枚？ X+2Y+5Z=100 不可以用数学方程描述—非数值计算类问题 例1：学生选课问题 “学生”表格 “课程”表格 “选课”表格 例2：UNIX文件系统的系统结构图 1.2 基本概念与术语 1) 数据：能输入到计算机中，被计算机程序识别和处理的一切事物的符号化表示。 数值性数据：整型数、实数 非数值性数据：学生信息、比赛项目 2) 数据元素：亦称元素，是构成数据的基本单位。 数据 ? 集合 元素? 集合中的一个 3) 数据项: 数据元素可细分成由若干数据项(字段)组成。数据项是具有独立含义的最小标识单位。 学生：学号，姓名，性别，年龄… 5) 数据类型: 在高级语言中，是具有相同性质的一组数据值的集合, 以及定义于这个值集合上的一组操作的总称. 根据值的特性不同，可分为： 原子类型：值不可分 结构类型：值可分解，如数组等 6) 抽象数据类型(ADT: Abstract Data Types)：由用户定义，用以表示应用问题的数据模型及定义在该模型上的一组操作。抽象数据类型的定义仅取决于它的逻辑特性，而与其在计算机内部的表示和实现无关。形式定义（D,S,P）其中：D:数据对象；S:D上的关系集；P:对D的基本操作集 本书抽象数据类型定义格式 ADT 抽象数据类型名 { 数据对象: 数据对象的定义 数据关系: 数据关系的定义 基本操作: 基本操作的定义 } ADT 抽象数据类型名 基本操作的定义： 操作名（参数表） 操作结果：操作结果描述 例 :自然数的抽象数据类型定义 ADT NaturalNumber { objects: 一个整数的有序子集合,它开始于0, 结束于机器能表示的最大整数(MaxInt)。 Function: 对于所有的 x, y ? NaturalNumber; False, True ? Boolean, +、-、、==、=等 都是可用的服务。 Zero( ) : 返回自然数0 NaturalNumber IsZero(x) : if (x==0) 返回True Boolean else 返回False Add (x, y) : if (x+y=MaxInt)返回 x+y NaturalNumber else 返回MaxInt Subtract (x, y) : if (x y) 返回 0 NaturalNumber else 返回 x - y Equal (x, y) : if (x==y) 返回True Boolean else 返回 False } NaturalNumber 1.3 算法与性能评价 1) 定义:对特定问题求解步骤的一种描述 特性： 有穷性：在有穷步、有穷时间内完成 确定性：每步定义是确切、无歧义的 可行性：每一条运算应足够基本（所描述的操作可以通过已实现的基本操作实现）例如：被零除的计算动作不能被有效执行。 输入：有0个或多个输入 输出：有一个或多个输出(处理结果) 2) 算法的设计要求（性能标准） 正确性：满足具体问题要求 可读性：人易读懂 健壮性：对非法数据也能做出反应和处理。 效率与存储量要求：执行时间、空间耗费。 可修改可扩展性：如果问题P 的一个算法是A，为了解答一个与P类似的问题，希望对A稍做改动就可正确运行，如算法A满足这一点，则说A的可修改性好。 3) 算法效率的度量 ① 度量方法 算法的后期测试（事后统计） 在算法中的某些部位插装时间函数time ( )，测定算法完成某一功能所花费的时间 缺点： 必须先运行依算法编制的程序 时间依赖于软硬件因素，易掩盖算法本身优略 算法的事前估计（事前分析） 决定一个算法执行时间的因素 算法选用的策略 问题的规模：求解的输入量 采用的程序语言 编译程序的好坏 机器执