《数据结构概述》PPT课件.ppt
《《数据结构概述》PPT课件.ppt》由会员分享,可在线阅读,更多相关《《数据结构概述》PPT课件.ppt(39页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、第二章 常用数据结构及其运算1计算机软件计算机软件技术基础技术基础上海大学上海大学 通信与信息工程学院通信与信息工程学院安安 平平计算机基础教学课件计算机基础教学课件第二章 常用数据结构及其运算2学时数:学时数:4040,其中习题课,其中习题课2 2学时。学时。讲授主要内容:第讲授主要内容:第2 2、3 3、4 4章章自学内容:自学内容:其余各章其余各章 课程的主要内容及安排课程的主要内容及安排第二章 常用数据结构及其运算3常用数据结构及其运算常用数据结构及其运算第二章第二章第二章 常用数据结构及其运算42 21 1 概概 述述2 22 2 线性表线性表2 23 3 栈与队栈与队2 25 5
2、树与二叉树树与二叉树2 26 6 图图2 27 7 查查 找找2 28 8 排排 序序第二章 常用数据结构及其运算52.1 2.1 概概 述述2.1.1 2.1.1 数据结构的概念数据结构的概念1. 数值型与非数值型数据数值型与非数值型数据数值型:数值型:整型、实型、布尔型等整型、实型、布尔型等非数值型:非数值型:文献检索、金融管理、商业系统文献检索、金融管理、商业系统 等数据处理等数据处理2. 数据结构数据结构研究非数值运算的程序设计问题。研究非数值运算的程序设计问题。数据结构就是相互之间存在一种或多种特定数据结构就是相互之间存在一种或多种特定关系的数据元素的集合。关系的数据元素的集合。如如
3、线性关系、层次关系、网状关系线性关系、层次关系、网状关系等。等。第二章 常用数据结构及其运算62.1 2.1 概概 述述数据数据(data)是信息的载体,指所有能输入到计是信息的载体,指所有能输入到计算机中并被计算机程序处理的符号的总称。如算机中并被计算机程序处理的符号的总称。如数、字符、符号等的集合。分为数、字符、符号等的集合。分为数值型数值型和和非数非数值型值型数据两类。数据两类。数据元素数据元素(data element)是数据的基本单位。是数据的基本单位。如数据集合如数据集合N= 1N= 1,2 2,3 3,4 4,5 5 中整数中整数1 1至至5 5均为数据元素。均为数据元素。 数据
4、元素不一定是单个的数字或字符,也可数据元素不一定是单个的数字或字符,也可能是若干个数据项的组合,如学生信息。能是若干个数据项的组合,如学生信息。 数据元素有时也称结点或记录。数据元素有时也称结点或记录。3. 基本概念和术语基本概念和术语第二章 常用数据结构及其运算72.1 2.1 概概 述述数据类型数据类型程序设计语言中允许的变量类型程序设计语言中允许的变量类型 基本数据类型(原子类型):变量值不可分,基本数据类型(原子类型):变量值不可分,如整型、实型、字符型等如整型、实型、字符型等 结构类型:变量值可分,如数组、结构体等结构类型:变量值可分,如数组、结构体等数据对象数据对象(data ob
5、ject)性质相同的数据元素的性质相同的数据元素的集合集合。如大写字母字符的数据对象是集合:如大写字母字符的数据对象是集合:C= AC= A,BB,.,Z Z 。第二章 常用数据结构及其运算82.1 2.1 概概 述述数据结构数据结构(data structure)是指同一数据对象中各是指同一数据对象中各数据元素间存在的关系。数据元素间存在的关系。 数据结构与算法数据结构与算法 程序程序算法算法数据结构数据结构算法算法指解决特定问题的有限运算序列指解决特定问题的有限运算序列第二章 常用数据结构及其运算92.1 2.1 概概 述述1.1.逻辑结构逻辑结构:研究数据元素及其关系的数学特性,:研究数
6、据元素及其关系的数学特性, 即数据元素间的逻辑关系。即数据元素间的逻辑关系。二元组二元组 S =S =(D D,R R) D D数据元素的非空有限集合数据元素的非空有限集合R RD D上关系的非空有限集合。上关系的非空有限集合。2.1.2 2.1.2 数据的逻辑结构和物理结构数据的逻辑结构和物理结构第二章 常用数据结构及其运算102.1 2.1 概概 述述四类基本结构:四类基本结构:线性结构(一对一)线性结构(一对一) 树形结构(一对多)树形结构(一对多) 图形结构(多对多)图形结构(多对多)2.1.2 2.1.2 数据的逻辑结构和物理结构数据的逻辑结构和物理结构集合集合第二章 常用数据结构及
7、其运算11例1:linearity = (D, R),其中D 1,2,3,4,5,6,7,8,9,10R = rr = , , , , , , , , 例2:Tree= (D, R),其中D 1,2,3,4,5,6,7,8,9,10R = rr = , , , , , , , , 第二章 常用数据结构及其运算12例4:S = (D, R),其中D 1,2,3,4,5,6R = r1, r2r 1= , , , , r2=,例3:Graph= (D, R),其中D 1,2,3,4,5; R = rr = , , , , 第二章 常用数据结构及其运算132.1 2.1 概概 述述2.2.物理结构物
8、理结构( (存储结构存储结构) ):是逻辑结构在计算是逻辑结构在计算机中的映象,即具体实现。机中的映象,即具体实现。四种基本存储结构:顺序存储结构 链式存储结构 索引存储结构 散列存储结构3.3.逻辑结构与存储结构的关系逻辑结构与存储结构的关系算法的设计取决于选定的逻辑结构,而算 法的实现依赖于采用的存储结构。同一种逻辑结构可采用不同的存储结构。2.1.2 2.1.2 数据的逻辑结构和物理结构数据的逻辑结构和物理结构第二章 常用数据结构及其运算142.1 2.1 概概 述述2.1.3 2.1.3 算法与算法分析算法与算法分析一、什么是算法一、什么是算法 算法是对特定问题求解步骤的一种描述,是指
9、算法是对特定问题求解步骤的一种描述,是指令的有限序列,其中每条指令表示一个或多个令的有限序列,其中每条指令表示一个或多个操作。操作。 算法的五个特征:算法的五个特征:有穷性、确定性、可行性、有穷性、确定性、可行性、 输入、输出输入、输出 算法描述:算法描述:采用采用类类C C语言语言的形式,有时也用自然的形式,有时也用自然语言。注释部分用语言。注释部分用/或或/ /* *.* */ /表示。表示。第二章 常用数据结构及其运算152.1 2.1 概概 述述2.1.3 2.1.3 算法与算法分析算法与算法分析二、算法设计的要求:二、算法设计的要求:正确性、健壮性、效率与低存储正确性、健壮性、效率与
10、低存储三、算法评价标准:三、算法评价标准:时间复杂度、空间复杂度时间复杂度、空间复杂度一般时间复杂度考虑的较多。一般时间复杂度考虑的较多。 一个可执行的算法不一定是一个好算法,算法的分析一个可执行的算法不一定是一个好算法,算法的分析 通常用计算机执行时在通常用计算机执行时在时间时间和和空间空间两方面的消耗多少两方面的消耗多少作为评价该算法优劣的标准。作为评价该算法优劣的标准。 度量一个程序的执行时间通常有两种方法:度量一个程序的执行时间通常有两种方法: 事后统计事后统计和和事前分析估算事前分析估算着重介绍方法。(算法、问题规模、语言、机器代码质量、机器执行指令的速度)第二章 常用数据结构及其运
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构概述 数据结构 概述 PPT 课件
限制150内