《软件工程 数据结构(课件第一讲ppt)》由会员分享，可在线阅读，更多相关《软件工程 数据结构(课件第一讲ppt)（41页珍藏版）》请在金锄头文库上搜索。
1、1.1 数据结构及其讨论范畴1.2 基本概念和术语1.3 抽象数据类型的表示与实现1.4 算法和算法分析本章重点难点重点: 数据结构的逻辑结构、存储结构以 及基本操作的概念及相互关系；抽象数据类型 (ADT)的概念和实现方法，算法的时间复杂性和 空间复杂性分析。难点: 抽象数据类型(ADT)的概念和实现 方法；算法的时间复杂性和空间复杂性分析。1.1 数据结构及其讨论范畴1.2 基本概念和术语1.3 抽象数据类型的表示与实现1.4 算法和算法分析第1章 绪论1.1 数据结构及其讨论范畴算法+数据结构 = 程序设计 处理问题的策略给出问题的数学模型编制出用计算机 处理问题的指令问题构建数学模型算
2、法实现 在解决问题时可能遇到的典型的逻辑结构（数据结构） 逻辑结构的存储映象（存储实现） 数据结构的相关操作及其实现。数据结构是一门讨论“描述现实世界实体的数 学模型(非数值计算)及其上的操作在计算机中如何 表示和实现“的学科。 第1章 绪论1.1 数据结构及其讨论范畴例1 求 n 个整数中的最大值。例2 交叉路口的红绿灯管理。例3 煤气管道的铺设问题。说明：例子中的数学模型正是数据结构要讨论的问题 。第1章 绪论1.1 数据结构及其讨论范畴例p计算机的发展p数据处理的种类p数据数值数据非数值数据数 (整数,实数) 字符 字符串 文字 图形 图象 声音对客观对象的符号表示程序原始数据结果数据第
3、1章 绪论1.1 数据结构及其讨论范畴软件 硬件 应用领域p 数值问题与非数值问题数值问题例1 已知：游泳池的长len和宽wide，求面积area 设计 求解问题的方法 编程 建模型：问题涉及的对象：游泳池的长len 宽wide，面积area；对象之间的关系：area=lenwide第1章 绪论1.1 数据结构及其讨论范畴学号 姓名 性别 出生日期 籍贯 入学成绩 所在班级 00201 杨润生 男 82/06/01 广州 561 00计算机2 00102 石磊 男 83/12/21 汕头 512 00计算机1 00202 李梅 女 83/02/23 阳江 532 00计算机2 00301 马耀
4、先 男 82/07/12 广州 509 00计算机3非数值问题已知某级学生情况 , 要求分班按入学成绩排列顺序。说明：在此类文档管理的数学模型中, 计算机处理的对象之间通常存在着一种最简单的线性关系 , 该数学模型称为线性模型。第1章 绪论1.1 数据结构及其讨论范畴例非数值问题第1章 绪论1.1 数据结构及其讨论范畴下棋程序-国际象棋：每次需要考虑的合乎规则的着法平均只有35步回合，计 算机预先分析7至8个回合的着法。若设为7个回合，则有超过 1亿亿亿个不同的变化，经简化后，仍有500亿至600亿个变化 。多分析一步，增加18亿个变化。根据计算机“深蓝”的速 度，平均5分钟走一步。算法：对弈
5、的规则和策略棋盘及棋盘的格局模型：根据计算机“深蓝”的速度例迷宫问题：在迷宫中，每走到一处，接下来可走的通路 有三条。计算机处理的这类对象之间通常不存在线性关 系。若把从迷宫入口处到出口的过程中所有可能的通路 都画出，则可得一棵“树”。 入口出口第1章 绪论1.1 数据结构及其讨论范畴例第1章 绪论1.1 数据结构及其讨论范畴对每种数据结构，主要讨论如下三方面的问题：数据的逻辑结构数据元素之间的逻辑关系，是具体关系的抽象。数据的存储结构(物理结构)：数据元素及其关系在计算机内存中的表示；数据的运算即对数据施加的操作。定义在数据的逻辑结构上的抽象的操作。1.1 数据结构及其讨论范畴1.2 基本概
6、念和术语1.3 数据结构的分类及表示1.4 抽象数据类型的表示与实现1.5 算法和算法分析数据：是信息的载体，能够被计算机识别、存储和加工处理。如整数，实数，字符串、图象、声音等都是数据。数据元素：数据的基本单位。相当于“记录”,在计算机程序中通常作为一个整体考虑和处理。数据项: 相当于记录的“域”或字段, 是数据不可分割的最小单位。如学号。数据对象：性质相同的数据元素的集合。如所有班名相同的记录集合。第1章 绪论1.2 基本概念和术语 数据结构类型树图第1章 绪论1.2 基本概念和术语数据结构是数据之间的相互关系， 即数据的组织形式。 线性表 栈 队列 串 数组 广义表数据结构线性结构非线性
7、结构线性结构：除第一个元素和最后一个元素之外，其他元素都有且仅有一个直接前驱，有且仅有一个直接后继；非线性结构：其逻辑特征是一个结点可能有多个直接前驱和直接后继；第1章 绪论1.2 基本概念和术语p数据的逻辑结构学号 姓名 专业 政治面藐001 王洪 计算机 党员002 孙文 计算机 团员003 谢军 计算机 团员004 李辉 计算机 团员005 沈祥福 计算机 党员006 余斌计算机 团员007 巩力计算机 团员008 孔令辉 计算机 团员001003002004006005008007学生间学号顺序关系 是一种线性结构关系第1章 绪论学生基本情况登记表，记录了每个学生的学号、姓名、专业、
8、政治、面貌，表中的记录是按学生的学号顺序排列的。 1.2 基本概念和术语 例家族的族谱:假设某家族有10个成员A， B， C， D， E， F， G， H，I， J，他们之间的血缘关系可以用如下图表示。JIACBDHGFE第1章 绪论1.2 基本概念和术语例顺序存储方法：数组链接存储方法：指针索引存储方法散列存储方法说明： 同一逻辑结构的不同存储结构，冠以不同的数据结构名 称。如顺序表、链表、散列表。 运算不同，数据结构也不同。如栈和队列。更进一步， 顺序栈、链栈、顺序队列、链队列。第1章 绪论1.2 基本概念和术语p数据的存储结构算法：数据运算的描述数据结构：数据的逻辑结构和存储结构算法+数
9、据结构=程序第1章 绪论1.2 基本概念和术语1.1 数据结构及其讨论范畴1.2 基本概念和术语1.3 抽象数据类型的表示与实现1.4 算法和算法分析p抽象数据型Abstract Data Types（ADT）定义：抽象数据型是一个数学模型和在该模型上定义的操作的集合ADT特点：降低了软件设计的复杂性；提高了程序的可读性和可维护性；程序的正确性容易保证第1章 绪论1.3 抽象数据类型的表示与实现在软件设计中，可以对哪三 种不同的对象进行抽象？第1章 绪论1.3 抽象数据类型的表示与实现第1章 绪论1.3 抽象数据类型的表示与实现软件系统数据结构控制机能操作过程软件设计抽象软件设计是对数据抽象、
10、过程抽象和控制抽象。p抽象数据型的规格描述完整性：反映所定义的抽象数据型的全部 特征；统一性：前后协调，不自相矛盾；通用性：适用于尽量广泛的对象；不依赖性：不依赖于程序设计语言。语法：给出操作的名称、I/O参数的数目和类型；语义：由一组等式组成，定义各种操作的功能及相互之间的关系；p规格描述的两个方面: 语法和语义第1章 绪论1.3 抽象数据类型的表示与实现抽象描述 （高级语言）编写的程序三条原则：符合规格描述的定义；有尽可能好的通用性；尽可能独立于程序的其它部分自底向上与自顶向下相结合、由简单到复杂第1章 绪论1.3 抽象数据类型的表示与实现p抽象数据型的实现多层次抽象技术抽象数据类型的形式
11、描述ADT = ( D，S，P ),其中： D 是数据对象; S是 D 上的关系集;P是 D 的基本操作集。第1章 绪论1.3 抽象数据类型的表示与实现数据类型和抽象数据类型 抽象数据类型需要通过高级编程语言中已经实现的数据类型（通常称之谓固有数据类型）来实现； 抽象数据类型的实现包括数据结构的实现和操作的实现。第1章 绪论1.3 抽象数据类型的表示与实现抽象数据类型“复数”的定义为：ADT Complex 数据对象：D = e1,e2 | e1,e2 属于 RealSet 数据关系：R1 = | e1是复数的实部，e2是复数的虚部 其中用两个实数来表示复数，将复数定义为两个实数的有序对，并约
12、定实部是前驱，虚部是后继。 例设计函数 DELEVAL（LIST p = FIRST( L ) ;while ( P != END( L ) ) if ( same( RETRIEVE( p, L ), d ) )DELETE(p, L ) ;elsep = NEXT(p, L ) ;第1章 绪论1.3 抽象数据类型的表示与实现例1.1 数据结构及其讨论范畴1.2 基本概念和术语1.3 抽象数据类型的表示与实现1.4 算法和算法分析第1章 绪论1.4 算法与算法分析p算法（algorithm）的概念算法是对问题求解过程的一种描述，是为解决一个或 一类问题给出的一个确定的、有限长的操作序列。严
13、格说来，一个算法必须满足以下五个重要特性关于本书采用的类语言描述：C 或 C+自然语言； 程序设计语言； 类语言。p算法描述第1章 绪论1.4 算法与算法分析p 算法的基本特征有穷性：算法中的操作步骤为有限个，且每个步骤都能在有限时间内完成。确定性：组成算法的操作必须清晰无二义性。可行性：算法中的所有操作都必须足够基本，都可以通过已经实现的基本操作运算有限次实现之。输入：作为算法加工对象的量值，通常体现为算法中的一组变量。些算法的字面上可以没有输入，实际上已被嵌入算法之中。输出：它是一组与输入有确定关系的量值，是算法进行信息加工后得到的结果，这种确定关系即为算法的功能。p在设计算法时通常应考虑
14、以下原则算法必须是“正确的”l所谓算法是正确的，除了应该满足算法说明中写明的“功能”之外，应对各组典型的带有苛刻条件的输入数据得出正确的结果。l在算法是正确的前提下，算法的可读性是摆在第一位的，这在当今大型软件需要多人合作完成的环境下是换重要的，另一方面，晦涩难读的程序易于隐藏错误而难以调试。应有很好的“可读性”第1章 绪论1.4 算法与算法分析p在设计算法时通常应考虑以下原则必须具有“健壮性”l算法的健壮性指的是，算法应对非法输入的数据作出恰当反映或进行相应处理，一般情况下，应向调用它的函数返回一个表示错误或错误性质的值。算法的效率l应考虑所设计的算法具有“高效率与低存储量”。高效率与低存储
15、量是矛盾的，要视具体问题而定。第1章 绪论1.4 算法与算法分析p影响时间特性的四个因素 定义 语句频度：语句重复执行的次数第1章 绪论1.4 算法与算法分析 程序运行时输入数据的总量; 对源程序编译所需的时间; 计算机执行每条指令所需的时间; 程序中指令重复执行的次数。所有算法均以函数形式给出, 算法的输入数据来自参数表；参数表的参数在算法之前均进行类型说明；有关结点结构的类型定义,以及全局变量的说明等均在算法之前进行说明p描述算法的书写规则第1章 绪论1.4 算法与算法分析p 评价算法标准本课程采用以求解问题的基本操作（原操作）的执行次数作为算法时间的度量。O(n3) 称为矩阵相乘算法时间复杂度；O(n3)表示矩阵相乘算法执行时间与n3成正比, 即O（n3）与n3
