章绪论中医药学课程.pptVIP

数据结构 宋旸 南京理工大学 用计算机解决问题的步骤 书目检索问题 计算机和人机对弈问题 多叉路口交通灯的管理问题 第1章　绪　论 1.1 什么是数据结构 1.2 学习数据结构的意义 1.3 数据结构涵盖的主要内容 1.4 什么是抽象数据类型 1.5 算法效率的度量 1.1 什么是数据结构 是相互之间存在一种或多种特定关系的数据元素的集合，表示为： 例： 在计算机科学中，复数可取如下定义：复数是一种数据结构 Complex = (C , R) 其中：C是含有两个实数的集合{c1, c2}； R={P}，而P是定义在集合C上的一种关系{c1, c2}，其中有序偶c1, c2表示c1是复数的实部，c2是复数的虚部 数据(data)——所有能被计算机识别、存储和处理的符号的集合（包括数字、字符、声音、图像等信息 ）。 数据元素(data element)——是数据的基本单位，具有完整确定的实际意义(又称元素、结点，顶点、记录等）。 数据项(Data item)——构成数据元素的项目。是具有独立含义的最小标识单位（又称字段、域、属性 等）。 1.2 学习数据结构的意义 　　计算机内的数值运算依靠方程式，而非数值运算（如表、树、图等）则要依靠数据结构。 　　数据结构是一门学科，针对非数值计算的程序设计问题，研究计算机的操作对象以及它们之间的关系和操作等等。 1.3 数据结构涵盖的内容 （1） S=(D, R) D={ a, b, c, d, e, f } R={(a,e), (b,c), (c,a), (e,f), (f,d)} d1 d5 d2 d4 d3 　　　答：物理结构亦称存储结构，是数据的逻辑结构在计算机存储器内的表示（或映像）。它依赖于计算机。 答：在数据的逻辑结构上定义的操作算法。 它在数据的存储结构上实现。 1.4 什么是抽象数据类型 1.4.1 数据类型与抽象数据类型的区别 抽象数据类型：是指一个数学模型以及定义在该模型上的一组操作。 抽象数据类型的定义仅取决于它的一组逻辑特性，而与其在计算机内如何表示和实现无关。 1.4.2 抽象数据类型如何定义 例：给出自然数(Natural Number )的抽象数据类型定义。 1.4.3 抽象数据类型如何表示和实现 抽象数据类型可以通过固有的数据类型（如整型、实型、字符型等）来表示和实现。 1.5 算法效率的度量 讨论： 1.5.1 什么是算法？如何评判算法的好坏？ 1.5.2 时间复杂度和空间复杂度如何表示？ 1.5.3 计算举例 1.5.1 什么是算法？如何评判一个算法的好坏？ 算法的基本特性 有穷性: 一个算法必须总是(对任何合法的输入值)在执行有穷步骤后结束，且每一步都可在有穷时间内完成。 确定性: 算法中每一条指令必须有确切的含义，不会产生二义性，并且在任何条件下，算法只有唯一的执行路径，即对于相同的输入只能得到相同的输出。 可行性: 算法中描述的操作都是可以通过已经实现的基本运算执行有限次来实现。 输入: 有零个或多个输入。 输出: 有一个或多个输出。 算法的评价指标 正确性 可读性 健壮性 效率与低存储量需求 算法效率的度量 事后统计方法—— 利用计时功能 缺点：必须先运行依赖算法编制的程序 依赖硬件、软件环境因素 事前分析估算的方法 依赖因素：依据选取算法采用何种策略 问题的规模 书写程序的语言 编译效率 机器指令执行速度 一个算法是由控制结构（顺序、分支、循环）和原操作构成（固有数据类型的操作），则算法时间取决于两者综合的效果。 通常选取算法中基本操作的重复执行次数作为算法的时间量度。 该次数是规模n的某种函数f( n )，算法的时间度量为 T( n )=O( f( n ) ) 表示算法执行时间的增长率和f( n )的增长率相同，为算