项目基础知识.ppt

项目1数据结构基础知识 问题的引入 1 书目自动检索系统的数学模型 书目文件 2 人机对奕问题的数学模型 3 十字路口的交通灯管理问题的数学模型 主要考虑的是设计出合适的数据结构及相应的算法 即 首先要考虑对相关的各种信息如何表示 组织和存储 因此 简单说来 数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作的学科 问题的分析 1 为什么要学习数据结构 1 电子计算机的主要用途 早期 主要用于数值计算 后来 处理逐渐扩大到非数值计算领域 能处理多种复杂的具有一定结构关系的数据 问题的提出 用计算机解决问题的过程 建立模型 构造求解算法 选择存储结构 编写程序 测试 描述问题的共性 描述问题的求解方法 将问题涉及的数据存储到计算机中 分析问题的过程 数据结构的作用 进行更为复杂的算法设计 选择合理的存储结构 提高编程技术 2 数据结构课程的形成和发展 形成阶段60年代初期 数据结构 有关的内容散见于操作系统 编译原理和表处理语言等课程 1968年 美唐 欧 克努特教授开创了数据结构的最初体系 计算机程序设计技巧 第一卷 基本算法 数据结构 被列入美国一些大学计算机科学系的教学计划 发展阶段 数据结构的概念不断扩充 包括了网络 集合代数论 关系等 离散数学结构 的内容 70年代后期 80年代初 我国高校陆续开设该课程 3 数据结构课程 所处的地位 介于数学 计算机硬件和计算机软件三者之间的一门核心课程 知识目标 数据 数据元素 数据项 逻辑结构和存储结构在概念上的联系与区别 数据结构及其三个组成部分 抽象数据类型和数据抽象 评价算法优劣的标准及方法 教学目标 技能目标 掌握本课程所涉及到的基本名词 术语和概念 特别是数据的逻辑结构和存储结构之间的关系及性质 了解抽象数据类型的定义 表示和实现方法 理解算法设计的五个要素和基本要求 掌握算法效率的度量方法 着重学习算法的时间复杂度分析 教学目标 素质目标 理解什么是数据结构 数据结构在程序设计中的重要性 了解程序开发的过程 明确数据设计的目的和意义 1 1基本概念1 数据 data 数据是信息的载体 是描述客观事物的数 字符 以及所有能输入到计算机中并被计算机程序识别和处理的符号的集合 是计算机程序加工的 原料 分类 数值性数据非数值性数据 教学知识点 2 数据元素 dataelement 数据的基本单位 在计算机程序中常作为一个整体进行考虑和处理 有时一个数据元素可以由若干数据项 DataItem 组成 数据项是数据不可分割的最小标识单位 数据元素又称为元素 结点 记录 3 数据对象 dataobject 数据对象是具有相同性质的数据元素的集合 整数数据对象N 0 1 2 字母字符数据对象C A B Z 学生成绩数据对象Cj 101 jane 80 102 jack 90 103 jerry 75 4 数据结构 datastructure 数据结构是相互之间存在一种或多种特定关系的数据元素的集合 在任何问题中 数据元素都不是孤立存在的 而是在它们之间存在着某种关系 这种数据元素相互之间的关系称为结构 Structure 数据结构是一堆数据元素和这些数据元素之间的关系的总和 按数据元素之间关系的不同特性 通常有4类基本结构 1 集合结构中的数据元素除了 同属于一个集合 外 别无其它关系 2 线性结构结构中的数据元素之间存在一对一的关系 3 树型结构结构中的数据元素之间存在一对多的关系 4 图状结构或网状结构结构中的数据元素之间存在多对多的关系 5 数据结构的形式定义 用一个二元组表示 记为 Data Structure D S 其中 D是数据元素的有限集 即一个数据对象 S是该对象中所有数据成员之间的关系的有限集合 在计算机科学中 对复数的定义 复数是一种数据结构Complex C R 其中 C是包含两个实数的集合 C1 C2 R P P是定义在C上的一种关系 例1 用数据结构如何描述2行3列矩阵 它是一个含6个数据元素 a1 a2 a3 a4 a5 a6 的集合 且集合上存在 行关系 和 列关系 两个次序关系 其中行关系为 列关系为 意为x和y之间存在 x领先于y 的次序关系 思考 如何描述一个一行六列的矩阵 例2 假设我们需要编制一个事务管理的程序 管理学校科学研究课题小组的各项事务 则首先要为程序的操作对象 课题小组设计一个数据结构 假设每个小组由一位教师 一至三名研究生及一至六名本科生组成 小组成员之间的关系是 教师指导研究生 而由每位研究生指导一至两名本科生 则可以如下定义数据结构 Group P R 其中 P T G1 Gn S11 Snm 1 1 1 i n 1 j m 1 n 3 1 m 2 6 数据的逻辑结构 数据的逻辑结构从逻辑关系上描述数据 可以看作是从具体问题抽象出来的数据模型 与数据的存储无关 也与数据元素本身的形式 内容 相对位置无关 数据的逻辑结构分类 线性结构线性表 栈 队列 串非线性结构树 图 或网络 7 数据的存储结构 数据结构在计算机中的表示 或称映象 称为数据的存储结构 又称为物理结构 它包括数据元素的表示和关系的表示 1 数据元素的表示 位 字长 元素 结点 数据域 2 关系的表示两种基本的存储方法 顺序映像 顺序存储结构 非顺序映像 链式存储结构 顺序存储结构 借助数据元素在存储器中的相对位置来表示数据元素之间的逻辑关系 所有元素存放在一片连续的存贮单元中 逻辑上相邻的元素存放到计算机内仍然相邻 链式存储结构 在每一个数据元素中增加一个存放地址的指针 借助该指针来表示数据元素之间的逻辑关系 所有元素存放在可以不连续的存贮单元中 但元素之间的关系可以通过地址 指针 确定 逻辑上相邻的元素存放到计算机内存后不一定是相邻的 存储结构的描述 存储结构的描述方法随编程环境的不同而不同 通常可用高级编程语言中提供的数据类型描述之 例如 用一维数组类型描述顺序存储结构 用指针描述链式存储结构 例如 定义 日期 为 typedefstruct inty 年号Yearintm 月号Monthintd 日号Day DateType 日期类型同样 此时对数据元素也要借用高级编程语言中的数据类型描述之 8 数据类型 datatype 数据类型是一个值的集合和定义在这个值集上的一组操作的总称 数据类型可分两类 原子类型和结构类型 例如 在C语言中原子类型 整型 实型 字符型等结构类型 数组 结构体 联合等 9 抽象抽象数据类型 AbstractDataType简称ADT 由用户定义 用以表示应用问题的数据模型指一个数学模型以及定义在此数学模型上的一组操作 例如 计算机拥有的整数类型 它与数据类型实质上是一个概念 但其特征是使用与实现分离 实行封装和信息隐蔽 独立于计算机 抽象数据类型的描述方法 抽象数据类型可用 D S P 三元组表示 其中 D是数据对象 S是D上的关系集 P是对D的基本操作集 ADT抽象数据类型名 数据对象 数据对象的定义 数据关系 数据关系的定义 基本操作 基本操作的定义 ADT抽象数据类型名 数据对象和数据关系的定义用伪码 不真正执行的符号 描述 基本操作的定义格式为 基本操作名 参数表 初始条件 初始条件描述 操作结果 操作结果描述 基本操作有两种参数 赋值参数只为操作提供输入值 引用参数以 打头 除了可以提供输入值外 还将返回操作结果 初始条件 描述了操作执行之前数据结构和参数应满足的条件 若不满足 则操作失败 并返回相应出错信息 若初始条件为空 则省略之 操作结果 说明了操作正常完成之后 数据结构的变化状况和应返回的结果 举例 抽象数据类型复数的定义 ADTComplex 数据对象 D e1 e2 e1 e2 RealSet 数据关系 R1 e1 e2 e1是复数的实数部分 e2是复数的虚数部分 基本操作 InitComplex Z v1 v2 操作结果 构造复数Z 其实部和虚部分别被赋以参数v1和v2的值 DestroyComplex Z 操作结果 复数Z被销毁 GetReal Z realPart 初始条件 复数已存在 操作结果 用realPart返回复数Z的实部值 GetImag Z ImagPart 初始条件 复数已存在 操作结果 用ImagPart返回复数Z的虚部值 Add z1 z2 sum 初始条件 z1 z2是复数 操作结果 用sum返回两个复数z1 z2的和值 ADTComplex假设 z1和z2是上述定义的复数 则Add z1 z2 z3 操作的结果将得到z3 z1 z2 1 2抽象数据类型的表示与实现 抽象数据类型可通过固有数据类型来表示和实现 即利用处理器中已存在的数据类型来说明新的结构 用已经实现的操作来组合新的操作 一 类C语言简要说明 1 预定义常量和类型 函数结果状态代码 defineTRUE1 defineFALSE0 defineOK1 defineERROR0 defineINFEASIBLE 1 defineOVERFLOW 2 Status是函数的类型 其值是函数结果状态代码typedefintStatus 2 数据结构的表示 存储结构 用类型定义 typedef 描述 数据元素类型约定为ElemType 由用户在使用该数据类型时自行定义 3 基本操作的算法都用以下形式的函数描述 函数类型函数名 函数参数表 算法说明语句序列 函数名除了函数的参数需要说明类型外 算法中使用的辅助变量可以不作变量说明 必要时对其作用给予注释 一般而言 a b c d e等用作数据元素名 i k 1 m n等用作整型变量名 p q r等用作指针变量名 当函数返回值为函数结果状态代码时 函数定义为Status类型 为了便于算法描述 除了值调用方式外 增添了C 语言的引用调用的参数传递方式 在形参表中 以 打头的参数即为引用参数 4 赋值语句有简单赋值变量名 表达式 串联赋值变量名1 变量名2 变量名k 表达式 成组赋值 变量名1 变量名k 表达式1 表达式k 结构名 结构名 结构名 值1 值k 变量名 表达式 变量名 起始下标 终止下标 变量名 起始下标 终止下标 交换赋值变量名 变量名 条件赋值变量名 条件表达式 表达式T 表达式F 5 选择语句有条件语句1if 表达式 语句 条件语句2if 表达式 语句 else语句 开关语句1switch 表达式 case值1 语句序列1 break case值n 语句序列n break default 语句序列n 1 开关语句2switch 表达式 case条件1 语句序列1 break case条件n 语句序列n break default 语句序列n 1 6 循环语句有for语句for 赋初值表达式序列 条件 修改表达式序列 语句 while语句while 条件 语句 do while语句do 语句序列 while 条件 7 结束语句有函数结束浯句return表达式 return case结束语句break 异常结束语句exit 异常代码 8 输入和输出语句有输入语句scanf 格式串 变量1 变量n 或cin 变量1 变量n 输出语句printf 格式串 表达式1 表达式n 或cout 表达式1 表达式n 9 注释行注释 文字序列 10 基本函数有求最大值max 表达式l 表达式n 求最小值min 表达式1 表达式n 求绝对值abs 表达式 求不足整数值floor 表达式 向下取整求进位整数值ceil 表达式 向上取整判定文件结束eof 文件变量 或eof判定行结束eoln 文件变量 或eoln 抽象数据类型实现示例 例如利用C语言实现的 复数 类型如下描述 存储结构的定义typedefstruct floatrealpart floatimagpart complex 基本操作的函数原型说明voidAssign complex 以sum返回两个复数z1 z2的和基本操作的实现 voidadd complexz1 complexz2 complex 1 3算法和算法分析 算法的定义 是对特定问题求解步骤的一种描述 是一个有穷的指令集 这些指令表示一个或多个操作 算法的特性 要素 有穷性算法应在执行有穷步后结束 且每一步都在有穷时间内完成确定性每步定义都是确切 无歧义的可行性算法中描述的操作应能通过执行有限次已经实现的基本运算而实现输入有0个或多个输入输出有一个或多个输出 处理结果 算法设计的要求 正确性 不含有语法错误 对于各种合法的输入数据能够得到满足规格说明要求的结果 可读性 要求程序有较好的人机交互性 有助于人们对算法的理解 健壮性 对输入的非法数据能作出适当的响应或处理 效率与低存储需求 主要指算法的执行时间和所需的最大存储空间 这两方面主要和问题的规模有关 算法效率的度量 算法的后期测试在算法中的某些部位插装时间函数time 测定算法完成某一功能所花费时间 算法的事前估计 空间复杂度时间复杂度 程序运行所需要的时间取决于下列因素 依据的算法选用何种策略 问题的规模 书写程序的语言 编译程序所生成目标代码的质量 硬件的速度 可以认为一个特定算法 运行工作量 大小 只依赖于问题的规模 通常用整数n表示 或者说 它是问题规模的函数 一个算法所耗费的时间 应该是该算法中每条语句的执行时间之和 而每条语句的执行时间又是该语句的执行次数 频度 与该语句执行一次所需时间的乘积 语句的频度指的是该语句重复执行的次数 我们假定 每条语句一次执行的时间都是相同的 为单位时间 这样我们对时间的分析就可以独立于软硬件系统 时间复杂度是问题规模的函数 T n 语句频度举例 a x s 0 x的频度为1 b for i 1 i n i x s x x的频度为n c for j 1 j n j for k 1 k n k x s x x的频度为n2 时间复杂度 设解决一个问题的规模为n 基本操作被重复执行的次数是n的一个函数f n 假如 随着问题规模n的增长 算法执行时间的增长率和f n 的增长率相同 则可记作 T n O f n 其中T n 叫算法的渐进时间复杂度 简称时间复杂度 O是Order 数量级 的首字母 意思是T n 与f n 只差一个常数倍 比较同一问题的不同算法 通常的做法是 从算法中选取一种对于所研究的问题是基本操作的原操作 以该基本操作重复执行的次数作为算法的时间量度 基本操作的原操作 数情况下它是最深层循环内的语句中的原操作 它的执行次数和包含它的语句的频度相同 渐进时间复杂度的计算 加法规则 针对并列程序段T n m T1 n T2 m O max f n g m 乘法规则 针对嵌套程序段T n m T1 n T2 m O f n g m 注 c log2n n nlog2n n2 n3 2n 3n n 变量计数 x 0 y 0 for intk 0 k n k x for inti 0 i n i for intj 0 j n j y T1 n O 1 T2 n O n T3 n