DS-数据结构概述.ppt
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_05.gif)
《DS-数据结构概述.ppt》由会员分享,可在线阅读,更多相关《DS-数据结构概述.ppt(38页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、软件学院软件学院 李媛媛李媛媛本章重点难点重点重点: : 数据结构的逻辑结构、存储结构以及基本操数据结构的逻辑结构、存储结构以及基本操作的概念及相互关系;作的概念及相互关系; 抽象数据类型抽象数据类型(ADT)(ADT)的概念和实现方法,算的概念和实现方法,算法的时间复杂性和空间复杂性分析。法的时间复杂性和空间复杂性分析。难点难点: : 抽象数据类型抽象数据类型(ADT)(ADT)的概念和实现方法;的概念和实现方法; 算法的时间复杂性和空间复杂性分析算法的时间复杂性和空间复杂性分析。软件学院软件学院 李媛媛李媛媛1.1 为什么要学习数据结构为什么要学习数据结构算法+数据结构 = 程序设计 处理
2、问题的策略给出问题的数学模型编制出用计算机处理问题的指令问题问题构建数学模型构建数学模型算法实现算法实现软件学院软件学院 李媛媛李媛媛p计算机的发展p数据处理的种类p数据数值数据数值数据非数值数据非数值数据数 (整数,实数) 字符 字符串 文字 图形 图象 声音对客观对象的符号表示程序程序原始数据原始数据结果数据结果数据软件 硬件 应用领域软件学院软件学院 李媛媛李媛媛 学习数据结构的原因:学习数据结构的原因: 计算机处理的数据量越来越大。计算机处理的数据量越来越大。 数据类型越来越多。数据类型越来越多。 数据的结构越来越复杂。数据的结构越来越复杂。 数据结构是一门研究数据结构是一门研究“非数
3、值计算程序设计问题非数值计算程序设计问题中计算机的操作对象以及它们之间的关系和操作中计算机的操作对象以及它们之间的关系和操作 的学科。的学科。 1.1 为什么要学习数据结构为什么要学习数据结构软件学院软件学院 李媛媛李媛媛 已知数据如下:已知数据如下:结论结论1 1:杂乱无章的数据不能表达和交流。:杂乱无章的数据不能表达和交流。例例119850700163172978233000340304195902261011工号:工号:1985070016电话号码:电话号码:3172978邮编:邮编:233000身份证号码:身份证号码:340304195902261011软件学院软件学院 李媛媛李媛媛
4、例例2电话号码簿(电话号码簿(a1,b1)()( a2,b2 )( )( an,bn ),其中,其中,ai为某人姓名,为某人姓名,bi为该人的电话号码。为该人的电话号码。结论结论2 2:数据之间是有联系的。:数据之间是有联系的。软件学院软件学院 李媛媛李媛媛 例例3家族的族谱家族的族谱: 假设某家族有假设某家族有10个成员个成员A, B,C,D,E,F,G,H,I,J,他们之间的血缘关系可以用如下图表示。他们之间的血缘关系可以用如下图表示。JIACBDHGFE结论结论3 3:数据之间是有结构的。:数据之间是有结构的。软件学院软件学院 李媛媛李媛媛学号学号 姓名姓名 性别性别 出生日期出生日期
5、入学成绩入学成绩 所在班级所在班级 00201 杨润生杨润生 男男 82/06/01 561 00计算机计算机200102 石磊石磊 男男 83/12/21 512 00计算机计算机100202 李梅李梅 女女 83/02/23 532 00计算机计算机200301 马耀先马耀先 男男 82/07/12 509 00计算机计算机3 已知某级学生情况已知某级学生情况, ,要求分班按入学成绩排列顺序。要求分班按入学成绩排列顺序。说明:在此类文档管理中说明:在此类文档管理中, ,可以有查找、修改、插入、删可以有查找、修改、插入、删除等操作。除等操作。例例4结论结论4 4:在某种数据结构上可以定义一组
6、运算。:在某种数据结构上可以定义一组运算。软件学院软件学院 李媛媛李媛媛1.2 1.2 数据结构的有关概念和术语数据结构的有关概念和术语1 1、数据数据:对客观事物的符号表示,信息的载体,能被计算机识别、存:对客观事物的符号表示,信息的载体,能被计算机识别、存储和加工处理。如整数,实数,字符串、图象、声音等都是数据。储和加工处理。如整数,实数,字符串、图象、声音等都是数据。2 2、数据元素数据元素:数据的基本单位,又可称为元素、结点、顶点、记录等。:数据的基本单位,又可称为元素、结点、顶点、记录等。3 3、数据项数据项: : 是数据不可分割的最小单位。如学号、姓名等。是数据不可分割的最小单位。
7、如学号、姓名等。 一个数据元素可以由若干个数据项构成。一个数据元素可以由若干个数据项构成。4 4、数据对象数据对象:性质相同的数据元素的集合。如所有班名相同的记录集:性质相同的数据元素的集合。如所有班名相同的记录集合。合。5 5、数据类型数据类型:是指一个类型和定义在这个类型上的操作集合。:是指一个类型和定义在这个类型上的操作集合。 分为:分为:原子类型原子类型和和结构类型结构类型6 6、抽象数据类型抽象数据类型:是指一个逻辑概念上的类型和这个类型上的操作集:是指一个逻辑概念上的类型和这个类型上的操作集合合。优点:优点:将数据和操作封装在一起实现了信息隐藏。将数据和操作封装在一起实现了信息隐藏
8、。软件学院软件学院 李媛媛李媛媛 抽象数据类型的定义可以由元素、元素之间的关系及操作三部分构抽象数据类型的定义可以由元素、元素之间的关系及操作三部分构成。成。 抽象数据类型的定义格式抽象数据类型的定义格式 ADT ADT 抽象数据类型名抽象数据类型名 数据对象数据对象: 数据关系数据关系: 基本操作基本操作: ADTADT 抽象数据类型名抽象数据类型名 例如:例如:P4 P4 例例1-41-41.2 1.2 数据结构的有关概念和术语数据结构的有关概念和术语软件学院软件学院 李媛媛李媛媛1.2 1.2 数据结构的有关概念和术语数据结构的有关概念和术语数据结构:数据结构:相互之间存在一种或多种特定
9、关相互之间存在一种或多种特定关系的数据元素的集合。系的数据元素的集合。 形式定义为:形式定义为:Data_StructureData_Structure(D, (D, R R) ) 例如:例如:P5 P5 例例1-51-5软件学院软件学院 李媛媛李媛媛数据结构包括以下内容:数据结构包括以下内容:(1 1)数据的逻辑结构)数据的逻辑结构。从逻辑关系上描述数。从逻辑关系上描述数据,与数据存储无关,独立于计算机。它包括据,与数据存储无关,独立于计算机。它包括以下四类基本结构:以下四类基本结构:集合:集合:同属一个集合同属一个集合线性结构:线性结构:一对一一对一树形结构:树形结构:一对多一对多图状结构
10、或网状结构:图状结构或网状结构:多对多多对多1.2 1.2 数据结构的有关概念和术语数据结构的有关概念和术语软件学院软件学院 李媛媛李媛媛数据结构类型数据结构类型树图线性表栈队列串数组广义表数据结构线性结构非线性结构软件学院软件学院 李媛媛李媛媛(2 2)数据的物理结构)数据的物理结构,数据结构在计算机存,数据结构在计算机存储器中的表示,又称存储结构。它包括:储器中的表示,又称存储结构。它包括:顺序存储结构:顺序存储结构:借助数据元素在存储器中相对借助数据元素在存储器中相对位置表示逻辑关系位置表示逻辑关系链式存储结构:链式存储结构:依靠数据元素中的指针表示元依靠数据元素中的指针表示元素之间的逻
11、辑关系素之间的逻辑关系索引索引散列散列1.2 1.2 数据结构的有关概念和术语数据结构的有关概念和术语软件学院软件学院 李媛媛李媛媛对每种数据结构,主要讨论如下三方面的问题:对每种数据结构,主要讨论如下三方面的问题:数据的逻辑结构数据的逻辑结构 数据元素之间的逻辑关系,是具体关系的抽象。数据元素之间的逻辑关系,是具体关系的抽象。数据的存储结构数据的存储结构( (物理结构物理结构) ): 数据元素及其关系在计算机内存中的表示;数据元素及其关系在计算机内存中的表示;数据的运算(或算法)数据的运算(或算法) 即对数据施加的操作。定义在数据的逻辑结构上的即对数据施加的操作。定义在数据的逻辑结构上的抽象
12、的操作。抽象的操作。软件学院软件学院 李媛媛李媛媛1.3 1.3 算法和算法描述算法和算法描述1 1、算法、算法算法是对特定问题求解步骤的一种描述,是算法是对特定问题求解步骤的一种描述,是指令的集合。指令的集合。算法的特性:算法的特性:有穷性、确定性、可行性、输有穷性、确定性、可行性、输入、输出入、输出软件学院软件学院 李媛媛李媛媛 算法的基本特征算法的基本特征有穷性:有穷性:算法中的操作步骤为有限个,且每个步骤都能在有限时算法中的操作步骤为有限个,且每个步骤都能在有限时间内完成。间内完成。确定性:确定性:组成算法的操作必须清晰无二义性。组成算法的操作必须清晰无二义性。可行性:可行性:算法中的
13、所有操作都必须足够基本,都可以通过已经实算法中的所有操作都必须足够基本,都可以通过已经实现的基本操作运算有限次实现之。现的基本操作运算有限次实现之。输入:输入:作为算法加工对象的量值,通常体现为算法中的一组变量作为算法加工对象的量值,通常体现为算法中的一组变量。些算法的字面上可以没有输入,实际上已被嵌入算法之中。些算法的字面上可以没有输入,实际上已被嵌入算法之中。输出:输出:它是一组与输入有确定关系的量值,是算法进行信息加工它是一组与输入有确定关系的量值,是算法进行信息加工后得到的结果,这种确定关系即为算法的功能。后得到的结果,这种确定关系即为算法的功能。软件学院软件学院 李媛媛李媛媛2 2、
14、算法设计的要求、算法设计的要求 正确性正确性 可读性可读性 健壮性健壮性 高高效效性性1.3 1.3 算法和算法描述算法和算法描述软件学院软件学院 李媛媛李媛媛算法必须是算法必须是“正确的正确的”l所谓算法是正确的,除了应该满足算法说明中写明的所谓算法是正确的,除了应该满足算法说明中写明的“功能功能”之外,应之外,应对各组典型的带有苛刻条件的输入数据得出正确的结果。对各组典型的带有苛刻条件的输入数据得出正确的结果。在算法是正确的前提下,算法的可读性是摆在第一位的,这在当今大型软在算法是正确的前提下,算法的可读性是摆在第一位的,这在当今大型软件需要多人合作完成的环境下是换重要的,另一方面,晦涩难
15、读的程序件需要多人合作完成的环境下是换重要的,另一方面,晦涩难读的程序易于隐藏错误而难以调试。易于隐藏错误而难以调试。应有很好的应有很好的“可读性可读性”l 一个一个算法算法应当思路清晰、层次分明、简单明了、易读易懂。应当思路清晰、层次分明、简单明了、易读易懂。算法的设计要求算法的设计要求软件学院软件学院 李媛媛李媛媛必须具有必须具有“健壮性健壮性”l算法的健壮性指的是,算法应对非法输入的数据作出恰当反映算法的健壮性指的是,算法应对非法输入的数据作出恰当反映或进行相应处理,一般情况下,应向调用它的函数返回一个表或进行相应处理,一般情况下,应向调用它的函数返回一个表示错误或错误性质的值。示错误或
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- DS 数据结构 概述
![提示](https://www.deliwenku.com/images/bang_tan.gif)
限制150内