数据结构概念.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)
《数据结构概念.ppt》由会员分享,可在线阅读,更多相关《数据结构概念.ppt(97页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、数据结构概念1现在学习的是第1页,共97页n n什么是数据结构什么是数据结构n n抽象数据类型及面向对象概念抽象数据类型及面向对象概念n n算法定义算法定义n n模板模板n n算法简单性能分析与度量算法简单性能分析与度量第一章第一章 数据结构概念数据结构概念2022/10/4现在学习的是第2页,共97页“学生”表格学生选课系统学生选课系统学生选课系统学生选课系统2022/10/4现在学习的是第3页,共97页“课程”表格学生选课系统学生选课系统学生选课系统学生选课系统2022/10/4现在学习的是第4页,共97页学生学生(学号学号,姓名姓名,性别性别,籍贯,出生年月籍贯,出生年月)课程课程(课程
2、号课程号,课程名课程名,学时学时)选课单选课单(学号学号,课程号课程号,成绩,时间成绩,时间)“选课单选课单”包含如下信息包含如下信息学号学号 课程号课程号 成绩成绩 时间时间 学生选课系统中实体构成的网状关系学生选课系统中实体构成的网状关系学生选课系统学生选课系统学生选课系统学生选课系统2022/10/4现在学习的是第5页,共97页UNIX文件系统的系统结构图文件系统的系统结构图/(root)binlibuseretcmathdsswyintaoxieStack.cppQueue.cppTree.cpp2022/10/4现在学习的是第6页,共97页数据(数据(datadata)n数据是数据是
3、信息信息的载体,是描述客观事物的数、字的载体,是描述客观事物的数、字符、以及所有能输入到计算机中,被计算机程符、以及所有能输入到计算机中,被计算机程序识别和处理的符号的集合。序识别和处理的符号的集合。n数据的分类:数据的分类:u 数值性数据:数值性数据:整型、浮点型、复数、双精度数等整型、浮点型、复数、双精度数等u 非数值性数据:非数值性数据:字符和字符串、文字、图形、字符和字符串、文字、图形、图像、语音等图像、语音等2022/10/4现在学习的是第7页,共97页姓名姓名工工号号所在院系所在院系性性别出生日期出生日期 年年 月月职务业绩数据元素数据元素 (data element)(data
4、element)n数据的基本单位。在计算机程序中常作为一个数据的基本单位。在计算机程序中常作为一个整体进行考虑和处理。整体进行考虑和处理。n有时一个数据元素可以由若干有时一个数据元素可以由若干数据项数据项(Data Item)组成。数据项是具有独立含义组成。数据项是具有独立含义的最小标的最小标识单位。分为识单位。分为初等项初等项和和组合项组合项。n数据元素又称为元素、结点、记录。数据元素又称为元素、结点、记录。2022/10/4现在学习的是第8页,共97页什么是数据结构什么是数据结构定义定义:由某一数据元素的集合以及该集合中所有由某一数据元素的集合以及该集合中所有数据元素之间的关系组成。记为:
5、数据元素之间的关系组成。记为:Data_Structure=D,R其中,其中,D 是某一数据元素的集合,是某一数据元素的集合,R 是该集合中所是该集合中所有数据元素之间的关系的有限集合有数据元素之间的关系的有限集合。称为数据结构的二元组表示法。称为数据结构的二元组表示法。2022/10/4现在学习的是第9页,共97页例:例:N N 个网站之间的通讯网络个网站之间的通讯网络 树形关系树形关系图状关系图状关系156152436243以最小代价将以最小代价将n个网站连通,个网站连通,形成形成网络中任一网站网络中任一网站出现故障,整个出现故障,整个网络仍然保持畅网络仍然保持畅通,形成通,形成2022/
6、10/4现在学习的是第10页,共97页数据结构是数据的组织形式数据结构是数据的组织形式n包括三个方面:包括三个方面:数据元素间的逻辑关系,即数据的数据元素间的逻辑关系,即数据的逻辑结构逻辑结构;数据元素及其关系在计算机存储内的表示,数据元素及其关系在计算机存储内的表示,即数据的即数据的存储表示(存储结构存储表示(存储结构/物理结构)物理结构);数据的运算,即对数据元素施加的数据的运算,即对数据元素施加的操作操作。2022/10/4现在学习的是第11页,共97页数据的逻辑结构数据的逻辑结构n数据的逻辑结构从逻辑关系上描述数据,与数据数据的逻辑结构从逻辑关系上描述数据,与数据的存储无关;的存储无关
7、;n数据的逻辑结构可以看作是从具体问题抽象出数据的逻辑结构可以看作是从具体问题抽象出来的数据模型;来的数据模型;n数据的逻辑结构与数据元素本身的形式、内容数据的逻辑结构与数据元素本身的形式、内容无关;无关;n数据的逻辑结构与数据元素的相对存储位置无关。数据的逻辑结构与数据元素的相对存储位置无关。2022/10/4现在学习的是第12页,共97页数据的逻辑结构分类数据的逻辑结构分类n线性结构线性结构 线性表线性表n非线性结构非线性结构 树树 图(图(/网络)网络)集合集合层次结层次结构构群结构群结构2022/10/4现在学习的是第13页,共97页线性结构线性结构树形结构树形结构树树 二叉树二叉树
8、二叉搜索树二叉搜索树bindevetclibuser141312112345678910315871011998745662313112022/10/4现在学习的是第14页,共97页堆结构堆结构 “最大最大”堆堆 “最小最小”堆堆1235487111029164101211512369872022/10/4现在学习的是第15页,共97页图结构图结构 网络结构网络结构125436113318146651619211256342022/10/4现在学习的是第16页,共97页数据的存储结构数据的存储结构n数据的存储结构是逻辑结构用计算机语言在计算数据的存储结构是逻辑结构用计算机语言在计算机中的表示和
9、实现。机中的表示和实现。n数据的存储结构依赖于计算机语言。数据的存储结构依赖于计算机语言。顺序存储表示顺序存储表示 链接存储表示链接存储表示 索引存储表示索引存储表示 散列存储表示散列存储表示主要用于内存的存主要用于内存的存储表示储表示主要用于外存主要用于外存(文件文件)的存储表示的存储表示2022/10/4现在学习的是第17页,共97页n随编程环境的不同而不同,当用高级程序进行编随编程环境的不同而不同,当用高级程序进行编程时,通常可用高级编程语言中提供的数据类型程时,通常可用高级编程语言中提供的数据类型描述之。描述之。例如,当以例如,当以“顺序存储结构顺序存储结构”表示长整数时,表示长整数时
10、,可将它定义为可将它定义为数组数组:typedef int Long_int3;同样,此时对数据元素也要借用高级编程同样,此时对数据元素也要借用高级编程语言中的数据类型描述之。语言中的数据类型描述之。数据结构的存储结构的描述方法数据结构的存储结构的描述方法2022/10/4现在学习的是第18页,共97页n对每一个数据结构而言,必定存在与它密切相关的一组操作。若对每一个数据结构而言,必定存在与它密切相关的一组操作。若操作的种类和数目不同,即使逻辑结构相同,数据结构能起的作操作的种类和数目不同,即使逻辑结构相同,数据结构能起的作用也不同。用也不同。n不同的数据结构其操作集不同,但下列操作必不可缺:
11、不同的数据结构其操作集不同,但下列操作必不可缺:1)结构的生成;结构的生成;2)结构的销毁;结构的销毁;3)在结构中查找满足规定条件的数据元素;在结构中查找满足规定条件的数据元素;4)在结构中插入新的数据元素;在结构中插入新的数据元素;5)删除结构中已经存在的数据元素;删除结构中已经存在的数据元素;6)遍历。遍历。数据结构的操作数据结构的操作2022/10/4现在学习的是第19页,共97页综合实例:学生表综合实例:学生表2022/10/4现在学习的是第20页,共97页学号学号姓名姓名性性别班号班号1 1张斌斌男男990199018 8刘刘丽女女990299023434李英李英女女9901990
12、12020陈华男男990299021212王奇王奇男男990199012626董董强男男990299025 5王萍王萍女女99019901学生表的存储结构学生表的存储结构-顺序结构顺序结构2022/10/4现在学习的是第21页,共97页head1张斌张斌男男99018刘丽刘丽女女990234李英李英女女990120陈华陈华男男990212王奇王奇男男990126董强董强男男99025王萍王萍女女9901链式结构链式结构-物理结构物理结构/存储结构:存储结构:学生表构成的链表如学生表构成的链表如右图。其中右图。其中headhead为第为第一个数据元素的指一个数据元素的指针。针。学生表构成的链表学
13、生表构成的链表学生表的存储结构学生表的存储结构-链式结构链式结构2022/10/4现在学习的是第22页,共97页 采用二元组表示表采用二元组表示表1.11.1的学生表。的学生表。学生表中共有学生表中共有7 7个结点个结点,依次用依次用k1k1k7k7表示表示,则对则对应的二元组表示为应的二元组表示为B=(K,R),B=(K,R),其中:其中:K=k1,k2,k3,k4,k5,k6,k7 K=k1,k2,k3,k4,k5,k6,k7 R=,k6,kR=,7具体表示如下:具体表示如下:,学生表的二元组表示学生表的二元组表示2022/10/4现在学习的是第23页,共97页 该构利用图形形象地表示(图
14、形中的每个结点对应该构利用图形形象地表示(图形中的每个结点对应着一个数据元素着一个数据元素,两结点之间的连线对应着关系中的一两结点之间的连线对应着关系中的一个序偶)。个序偶)。上述上述“学生表学生表”数据结构用下图的图形表示。数据结构用下图的图形表示。学生表数据结构图示学生表数据结构图示学生表的图形表示学生表的图形表示2022/10/4现在学习的是第24页,共97页存放学生表的结构体数组存放学生表的结构体数组StudStud定义为:(顺序存储结构的线性表)定义为:(顺序存储结构的线性表)struct struct intint no no;/*;/*存储学号存储学号*/char char na
15、mename8;/*8;/*存储姓名存储姓名*/char char sexsex2;/*2;/*存储性别存储性别*/char char classclass4;/*4;/*存储班号存储班号*/Stud7=1,Stud7=1,“张斌张斌”,“男男”,“99019901”,5,5,王萍王萍,女女,9901;,9901;学生表的计算机语言描述学生表的计算机语言描述C/C+语言语言2022/10/4现在学习的是第25页,共97页 对对于于“学学生生表表”这这种种数数据据结结构构,可可以以进进行行一一系系列列的的运运算算,例例如如,增增加加一一个个学学生生记记录录、删删除除一一个个学学生生记记录录、查查
16、找找性性别别为为“女女”的的学学生生记记录录、查查找找班班号号为为“99029902”的的学学生生记录等等。(基本操作:记录等等。(基本操作:查查 插插 删删 改)改)从从前前面面介介绍绍的的两两种种存存储储结结构构看看到到,同同样样的的运运算算,在在不不同同的的存存储储结结构构(线线性性结结构构、链链式式结结构构)中中,其其实实现现过过程程是不同的。如下页所示:是不同的。如下页所示:学生表的操作:学生表的操作:查查 插插 删删 改(基本操作)改(基本操作)2022/10/4现在学习的是第26页,共97页例如例如,查找查找学号为学号为2020的学生的姓名:的学生的姓名:线线性性结结构构的的查查
17、找找:对对于于StudStud数数组组,可可以以从从Stud0Stud0开开始始比比较较,Stud0.no,Stud0.no不不等等于于20,20,再再与与Stud1.noStud1.no比比较较,直直到到Stud3.noStud3.no等于等于20,20,返回返回Stud3.nameStud3.name。链链式式结结构构的的查查找找:对对于于headhead为为首首结结点点指指针针的的链链表表,从从headhead所所指指结结点点开开始始比比较较,head-no,head-no不不等等于于20,20,从从它它的的nextnext得得到到下下一一个个结结点点的的地地址址,再再与与下下一一个个结
18、结点点的的nono域域比比较较,直到某结点的直到某结点的nono域等于域等于20,20,返回其返回其namename域域。学生表的操作:学生表的操作:查找查找顺序表顺序表链链 表表2022/10/4现在学习的是第27页,共97页抽象数据类型及面向对象概念抽象数据类型及面向对象概念n数据类型数据类型 定义:定义:一组性质相同的值的集合一组性质相同的值的集合,以及定以及定义于这个值集合上的一组操作的总称义于这个值集合上的一组操作的总称.nC语言中的数据类型语言中的数据类型 char int float double void 字符型字符型 整型整型 浮点型浮点型 双精度型双精度型 无值无值 202
19、2/10/4现在学习的是第28页,共97页n构造数据类型由构造数据类型由基本数据类型基本数据类型或或构造数据类构造数据类型型组成。组成。n构造数据类型由构造数据类型由不同成分类型不同成分类型构成。构成。n基本数据类型可以看作是计算机中已实现的基本数据类型可以看作是计算机中已实现的数据结构。数据结构。n数据类型就是数据结构,不过它是从编程者的角数据类型就是数据结构,不过它是从编程者的角度来使用的。度来使用的。n数据类型是模板,必须定义属于某种数据类型的数据类型是模板,必须定义属于某种数据类型的变量,才能参加运算。变量,才能参加运算。程序程序1.152022/10/4现在学习的是第29页,共97页
20、抽象数据类型抽象数据类型 (ADTs:Abstract Data Types)(ADTs:Abstract Data Types)n抽象数据类型是由用户定义,用以表示应用问抽象数据类型是由用户定义,用以表示应用问题的数据模型。题的数据模型。n特点是:特点是:信息隐蔽信息隐蔽和和数据封装数据封装,使用与实现相使用与实现相分离分离(类型的声明与其实现分开)(类型的声明与其实现分开)。n抽象数据类型可用抽象数据类型可用(D,S,P)三元组表示,其三元组表示,其中,中,D 是数据元素的集合(简称数据对象),是数据元素的集合(简称数据对象),S 是是 D上的关系集合,上的关系集合,P 是对是对 D 的基
21、本操作的基本操作集合。集合。2022/10/4现在学习的是第30页,共97页抽抽象象数数据据类类型型查找查找 登录登录 删除删除 修改修改 符符 号号 表表2022/10/4现在学习的是第31页,共97页n封装物理实现,公开界面接口。改变抽象数据类封装物理实现,公开界面接口。改变抽象数据类型的物理实现,不影响其他使用该抽象数据类型型的物理实现,不影响其他使用该抽象数据类型的程序(只要界面中的接口或服务方式不变)。的程序(只要界面中的接口或服务方式不变)。2022/10/4现在学习的是第32页,共97页抽象数据类型的描述抽象数据类型的描述n其其中中数数据据对对象象、数数据据之之间间的的关关系系用
22、用伪伪码码描描述述;基本操作定义格式为基本操作定义格式为ADT 抽象数据类型名抽象数据类型名 数据对象:数据对象:数据对象的定义数据对象的定义 数据关系:数据关系:数据关系的定义数据关系的定义 基本操作:基本操作:基本操作的定义基本操作的定义 ADT 抽象数据类型名抽象数据类型名基本操作名(参数表)基本操作名(参数表)前置条件:前置条件:先决条件描述先决条件描述后置条件:后置条件:操作结果描述操作结果描述2022/10/4现在学习的是第33页,共97页n基基本本操操作作有有两两种种参参数数:赋赋值值参参数数只只为为操操作作提提供供输输入入值值;引引用用参参数数以以&打打头头,除除可可提提供供输
23、输入入值值外外,还还将将返回操作结果。返回操作结果。n “前前置置条条件件”描描述述了了操操作作执执行行之之前前数数据据结结构构和和参参数数应应满满足足的的先先决决条条件件,若若不不满满足足,则则操操作作失失败败,并并返返回相应出错信息。回相应出错信息。n “后后置置条条件件”说说明明了了操操作作正正常常完完成成之之后后,数数据据结结构构的的变变化化状状况况和和应应返返回回的的结结果果。若若前前置置条条件件为为空空,则省略之。则省略之。nC+语言中使用语言中使用struct和和class定义定义抽象数据类型抽象数据类型2022/10/4现在学习的是第34页,共97页自然数的抽象数据类型定义(伪
24、码描述)自然数的抽象数据类型定义(伪码描述)ADT NaturalNumber isobjects:一个整数的有序子集合一个整数的有序子集合,它开始于它开始于0,结束于机器能表示的最大整数结束于机器能表示的最大整数(MaxInt)。Function:对于所有的对于所有的 x,y NaturalNumber;False,True Boolean,+、-、=、=等都是可等都是可用的服务。用的服务。Zero():NaturalNumber /前置条件前置条件:无:无 /后置条件后置条件:返回自然数:返回自然数0 2022/10/4现在学习的是第35页,共97页 IsZero(x):Boolean /
25、前置条件前置条件:x为为NaturalNumber /后置条件后置条件:if(x=0)then 返回返回True else 返回返回False Add(x,y):NaturalNumber /前置条件前置条件:x,y为为NaturalNumber且且x+yMaxInt /后置条件后置条件:返回:返回 x+y Subtract(x,y):NaturalNumber /前置条件前置条件:x,y为为NaturalNumber且且xy /后置条件后置条件:返回:返回 x-y 2022/10/4现在学习的是第36页,共97页 Equal(x,y):Boolean /前置条件前置条件:x,y为为Natur
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 概念
![提示](https://www.deliwenku.com/images/bang_tan.gif)
限制150内