数据结构使用C语言朱战立.ppt

2、设有数据逻辑结构为tree={D,R},其中D={01,02,03,04,05,06,07,08}; R={r}； r={01,02,01,03,01,04,02,05, 02,06,03,07,07,08}.试分析该数据结构属于哪种逻辑结构. 树型 * 作业 什么是逻辑结构与存储结构，他们之间的关系如何？ * 设有数据逻辑结构为：line=(D,R);其中D={a，b，c，d，e，f,g}；R={r}；r={a，b，b，c,c,d,d,e,e,f,f,g}.试画出对应的图形并说明属于哪种逻辑结构. * 将上述关系改为r={a，b，a，c,b,d,b,e,c,f,c,g}.试画出对应的图形并说明属于哪种逻辑结构. * * 1.4 什么是抽象数据类型 1 数据类型与抽象数据类型的区别？ 2 抽象数据类型如何定义？ 3 抽象数据类型如何表示和实现？ 讨论： * 1 数据类型与抽象数据类型的区别 数据类型：是一个值的集合和定义在该值上的一组操作的总称。 抽象数据类型：由用户定义，用以表示应用问题的数据模型。它由基本的数据类型构成，并包括一组相关的服务（或称操作） 它与数据类型实质上是一个概念，但其特征是使用与实现分离，实行封装和信息隐蔽（独立于计算机） * 2 抽象数据类型如何定义 抽象数据类型可以用以下的三元组来表示： ADT = （D，R，P） ADT抽象数据类型名{ 数据对象：数据对象的定义 数据关系：数据关系的定义 基本操作 ：基本操作的定义 } ADT抽象数据类型名 ADT常用定义格式 数据对象 D上的关系集 D上的操作集 * 1.4.3 抽象数据类型如何表示和实现 抽象数据类型可以通过固有的数据类型（如整型、实型、字符型等）来表示和实现。 （参看课本P28，线性表的抽象数据类型，思考用具体C语言如何实现） 注意：上机时要必须用具体语言实现，如C或C++等 队列的抽象数据类型定义 ADT Queue{数据对象：D={ai|ai∈ElemSet, i=1,2, …,n, n≥0}数据关系：R1={ai-1,ai|ai-1,ai∈D, i=1,2, …,n }?????????? 约定a1为队列头，an为队列尾。?? 基本操作：??? InitQueue( Q )????? 操作结果：构造一个空队列Q。??? DestroyQueue ( Q )????? 初始条件：队列Q已存在。????? 操作结果：销毁队列Q。 QueueLength( Q )????? 初始条件：队列Q已存在。????? 操作结果：返回Q的数据元素个数，即队列的长度。 * * 1.5 算法效率的度量 1 什么是算法？如何评判算法的好坏？ 2 时间复杂度和空间复杂度如何表示？ 3 计算举例 讨论： * 1 什么是算法？如何评判一个算法的好坏？ 常用时间复杂度来衡量 算法的基本特性： 算法评价指标： 有穷性、确定性、可行性、必有输出 正确性、可读性、健壮性、高效率与低存储量需求(见课本P20) 常用空间复杂度来衡量 好的程序设计：好算法＋好结构 　　算法：是对特定问题求解步骤的一种描述，它是指令的有限序列，是一系列输入转换为输出的计算步骤。 有穷性：一个算法必须总是(对任何合法的输入值)在执行有穷步之后结束，且每一步都可在有穷时间内完成。 确定性：每条指令必须有确切的含义 可行性：算法是能行得通的 必有输出 * 正确性：算法应当满足具体问题的需求 可读性：算法的可读性有利于人们对算法的理解 健壮性：当输入数据非法时，算法也能适当地做出反应或进行处理，而不会产生莫名其妙的结果。 效率与低存储需求：时间短，存储空间少（两者不能兼得） * 1.3.3 算法效率的度量 求解同一个问题,可以有许多不同的算法,究竟如何评价这些算法的好坏呢? 显然,选用的算法首先应该是“正确的”.此外,主要考虑如下三点: (1) 执行算法所消耗的时间; (2) 执行算法所消耗的存储空间,其中主要考虑辅助存储空间. (3) 算法应该易于理解,易于编码,易于调试等. * 时间复杂度 (time complexity) 语句频度(Frequency Count) 语句重复执行的次数 语句的执行时间 语句频度×执行一次所需时间 算法的执行时间 所有语句执行时间的总和 算法的渐近时间复杂度(asymptotic time complexity)，简称时间复杂度 因为语句的执行时间取决于机器的硬件速度、指令类型、以及编译所产生的代码质量，所以将算法中基本操作的最大语句频度作为