数据结构概念精.ppt
《数据结构概念精.ppt》由会员分享,可在线阅读,更多相关《数据结构概念精.ppt(72页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、1第1页,本讲稿共72页n n什么是数据结构什么是数据结构n n抽象数据类型及面向对象概念抽象数据类型及面向对象概念n n算法定义算法定义n n模板模板n n算法简单性能分析与度量算法简单性能分析与度量第一章第一章 数据结构概念数据结构概念第2页,本讲稿共72页“学生”表格第3页,本讲稿共72页“课程”表格第4页,本讲稿共72页学生学生(学号学号,姓名姓名,性别性别,籍贯籍贯)课程课程(课程号课程号,课程名课程名,学分学分)选课选课(学号学号,课程号课程号,成绩成绩)“选课单选课单”包含如下信息包含如下信息 学号学号 课程编号课程编号 成绩成绩 时间时间 学生选课系统中实体构成的网状关系学生选
2、课系统中实体构成的网状关系学生选课系统中实体构成的网状关系学生选课系统中实体构成的网状关系第5页,本讲稿共72页UNIX文件系统的系统结构图文件系统的系统结构图/(root)binlibuseretcmathdsswyintaoxieStack.cppQueue.cppTree.cpp第6页,本讲稿共72页数据(数据(datadata)n数据是数据是信息信息的载体,是描述客观事物的数、字的载体,是描述客观事物的数、字符、以及所有能输入到计算机中,被计算机程符、以及所有能输入到计算机中,被计算机程序识别和处理的符号的集合。序识别和处理的符号的集合。n数据的分类:数据的分类:u 数值性数据数值性数
3、据u 非数值性数据非数值性数据第7页,本讲稿共72页姓名姓名 所在院系所在院系 性别性别 出生日期出生日期 年年 月月职务职务业绩业绩数据元素数据元素(data element)(data element)n数据的基本单位。在计算机程序中常作为一个整数据的基本单位。在计算机程序中常作为一个整体进行考虑和处理。体进行考虑和处理。n有时一个数据元素可以由若干有时一个数据元素可以由若干数据项数据项(Data Item)组成。数据项是具有独立含义组成。数据项是具有独立含义的最小标的最小标识单位。识单位。n数据元素又称为元素、结点、记录。数据元素又称为元素、结点、记录。第8页,本讲稿共72页什么是数据结
4、构什么是数据结构定义定义:由某一数据元素的集合以及该集合中所有数据元由某一数据元素的集合以及该集合中所有数据元素之间的关系组成。记为:素之间的关系组成。记为:Data_Structure=D,R 其中,其中,D 是某一数据元素的集合,是某一数据元素的集合,R 是该集合是该集合中所有数据元素之间的关系的有限集合中所有数据元素之间的关系的有限集合。第9页,本讲稿共72页例:例:N N 个网点之间的连通关系个网点之间的连通关系 树形关系树形关系网状关系网状关系156152436243第10页,本讲稿共72页数据结构是数据的组织形式数据结构是数据的组织形式n包括三个方面:包括三个方面:数据元素间的逻辑
5、关系,即数据的数据元素间的逻辑关系,即数据的逻辑结构逻辑结构;数据元素及其关系在计算机存储内的表示,即数据元素及其关系在计算机存储内的表示,即数据的数据的存储表示存储表示;数据的运算,即对数据元素施加的数据的运算,即对数据元素施加的操作操作。第11页,本讲稿共72页数据的逻辑结构数据的逻辑结构n数据的逻辑结构从逻辑关系上描述数据,与数数据的逻辑结构从逻辑关系上描述数据,与数据的存储无关;据的存储无关;n数据的逻辑结构可以看作是从具体问题抽象出来数据的逻辑结构可以看作是从具体问题抽象出来的数据模型;的数据模型;n数据的逻辑结构与数据元素本身的形式、内容无数据的逻辑结构与数据元素本身的形式、内容无
6、关;关;n数据的逻辑结构与数据元素的相对存储位置无关。数据的逻辑结构与数据元素的相对存储位置无关。第12页,本讲稿共72页数据的逻辑结构分类数据的逻辑结构分类n线性结构线性结构 线性表线性表n非线性结构非线性结构 树树 图(或网络)图(或网络)第13页,本讲稿共72页线性结构线性结构树形结构树形结构树树 二叉树二叉树 二叉搜索树二叉搜索树bindevetclibuser14131211234567891031587101199874566231311第14页,本讲稿共72页堆结构堆结构 “最大最大”堆堆 “最小最小”堆堆123548711102916410121151236987第15页,本讲
7、稿共72页图结构图结构 网络结构网络结构12543611331814665161921125634第16页,本讲稿共72页数据的存储结构数据的存储结构n数据的存储结构是逻辑结构用计算机语言的实现;数据的存储结构是逻辑结构用计算机语言的实现;n数据的存储结构依赖于计算机语言。数据的存储结构依赖于计算机语言。顺序存储表示顺序存储表示 链接存储表示链接存储表示 索引存储表示索引存储表示 散列存储表示散列存储表示主要用于内存的存主要用于内存的存储表示储表示主要用于外存主要用于外存(文文件件)的存储表示的存储表示第17页,本讲稿共72页抽象数据类型及面向对象概念抽象数据类型及面向对象概念n数据类型数据类
8、型 定义:定义:一组性质相同的值的集合一组性质相同的值的集合,以及定以及定义于这个值集合上的一组操作的总称义于这个值集合上的一组操作的总称.nC语言中的数据类型语言中的数据类型 char int float double voidchar int float double void 字符型字符型 整型整型 浮点型浮点型 双精度型双精度型 无值无值 第18页,本讲稿共72页n构造数据类型由构造数据类型由基本数据类型基本数据类型或或构造数据类型构造数据类型组成。组成。n构造数据类型由构造数据类型由不同成分类型不同成分类型构成。构成。n基本数据类型可以看作是计算机中已实现的基本数据类型可以看作是计算
9、机中已实现的数据结构。数据结构。n数据类型就是数据结构,不过它是从编程者数据类型就是数据结构,不过它是从编程者的角度来使用的。的角度来使用的。n数据类型是模板,必须定义属于某种数据类型的数据类型是模板,必须定义属于某种数据类型的变量,才能参加运算。变量,才能参加运算。第19页,本讲稿共72页抽象数据类型抽象数据类型 (ADTs:Abstract Data Types)(ADTs:Abstract Data Types)n抽象数据类型是由用户定义,用以表示应用问抽象数据类型是由用户定义,用以表示应用问题的数据模型。题的数据模型。n特点是:特点是:信息隐蔽信息隐蔽和和数据封装数据封装,使用与实现相
10、使用与实现相分离分离。n抽象数据类型可用抽象数据类型可用(D,S,P)三元组表示,其三元组表示,其中,中,D 是数据元素的集合(简称数据对象),是数据元素的集合(简称数据对象),S 是是 D上的关系集合,上的关系集合,P 是对是对 D 的基本操作集的基本操作集合。合。第20页,本讲稿共72页抽抽象象数数据据类类型型查找查找 登录登录 删除删除 修改修改 符符 号号 表表第21页,本讲稿共72页抽象数据类型的描述抽象数据类型的描述n其其中中数数据据对对象象、数数据据之之间间的的关关系系用用伪伪码码描描述述;基本操作定义格式为基本操作定义格式为ADT 抽象数据类型名抽象数据类型名 数据对象:数据对
11、象的定义数据对象:数据对象的定义 数据关系:数据关系的定义数据关系:数据关系的定义 基本操作:基本操作的定义基本操作:基本操作的定义 ADT 抽象数据类型名抽象数据类型名基本操作名(参数表)基本操作名(参数表)前置条件:先决条件描述前置条件:先决条件描述后置条件:操作结果描述后置条件:操作结果描述第22页,本讲稿共72页n基基本本操操作作有有两两种种参参数数:赋赋值值参参数数只只为为操操作作提提供供输输入入值值;引引用用参参数数以以&打打头头,除除可可提提供供输输入入值值外外,还将返回操作结果。还将返回操作结果。n “前前置置条条件件”描描述述了了操操作作执执行行之之前前数数据据结结构构和和参
12、参数数应应满满足足的的先先决决条条件件,若若不不满满足足,则则操操作作失失败败,并返回相应出错信息。并返回相应出错信息。n “后后置置条条件件”说说明明了了操操作作正正常常完完成成之之后后,数数据据结结构构的的变变化化状状况况和和应应返返回回的的结结果果。若若前前置置条条件件为为空空,则则省略之。省略之。第23页,本讲稿共72页自然数的抽象数据类型定义自然数的抽象数据类型定义ADT NaturalNumber isobjects:一个整数的有序子集合一个整数的有序子集合,它开始于它开始于0,结束于机器能表示的最大整数结束于机器能表示的最大整数(MaxInt)。Function:对于所有的对于所
13、有的 x,y NaturalNumber;False,True Boolean,+、-、=、=等都是可用等都是可用的服务。的服务。Zero():NaturalNumber /前置条件前置条件:无:无 /后置条件后置条件:返回自然数返回自然数0 第24页,本讲稿共72页 IsZero(x):Boolean /前置条件前置条件:x为为NaturalNumber /后置条件后置条件:if(x=0)then 返回返回True else 返回返回False Add(x,y):NaturalNumber /前置条件前置条件:x,y为为NaturalNumber且且x+yMaxInt /后置条件后置条件:返
14、回返回 x+y Subtract(x,y):NaturalNumber /前置条件前置条件:x,y为为NaturalNumber且且xy /后置条件后置条件:返回返回 x-y 第25页,本讲稿共72页 Equal(x,y):Boolean /前置条件前置条件:x,y为为NaturalNumber /后置条件后置条件:if(x=y)返回返回True else 返回返回 False Successor(x):NaturalNumber /前置条件前置条件:x为为NaturalNumber /后置条件后置条件:if(x=MaxInt)返回返回 x else 返回返回 x+1end NaturalNu
15、mber第26页,本讲稿共72页面向对象的概念面向对象的概念n面向对象面向对象=对象类继承通信对象类继承通信n对象对象在应用问题中出现的各种在应用问题中出现的各种实体实体、事件事件、规规格说明格说明等。等。由一组由一组属性值属性值和在这组值上的一组和在这组值上的一组服务服务(或称操作)构成。(或称操作)构成。与与C中构造数据类型不同在于:中构造数据类型不同在于:C中的构造中的构造数据类型的变量仅涉及属性值,与操作分数据类型的变量仅涉及属性值,与操作分离,而离,而C+中的对象则不然。中的对象则不然。第27页,本讲稿共72页n类类(class),实例,实例(instance)具有相同属性和服务的对
16、象归于同一类,具有相同属性和服务的对象归于同一类,形成类。形成类。类中的对象为该类的实例。类中的对象为该类的实例。同一类的实例同一类的实例n共享类的属性和类的操作;共享类的属性和类的操作;n通过继承共享其父类的公共的和保护通过继承共享其父类的公共的和保护性的属性和操作;性的属性和操作;n同一类的不同实例有不同的属性值。同一类的不同实例有不同的属性值。第28页,本讲稿共72页四边形类及其对象四边形类及其对象属性aPoint1 aPoint2aPoint3 aPoint4服务服务Draw()move(x,y)contains(aPoint)属性值属性值quadrilateral1quadrilat
17、eral2(35,10)(50,10)(35,25)(50,25)(45,65)(50,45)(65,66)(60,70)Draw()move(x,y)contains(aPoint)Draw()move(x,y)contains(aPoint)服务服务服务服务quadrilateral第29页,本讲稿共72页n继承继承u派生类(子类):派生类(子类):四边形,三角形,四边形,三角形,u基类(父类):基类(父类):多边形多边形派生类派生类继承的特性继承的特性+特有的特性特有的特性基类基类多边形多边形四边形四边形三角形三角形六边形六边形第30页,本讲稿共72页n通信通信u消息传递消息传递uC+中
18、消息传递的方式:中消息传递的方式:定义:定义:Point p;void move(int x,inty);使用:使用:p.move(x,y);uC中则不同,需使用函数调用方式:中则不同,需使用函数调用方式:定义:定义:Point p;void move(Point q,int x,inty);使用:使用:move(p,x,y);第31页,本讲稿共72页Draw()move(x,y)contains(aPoint)PolygonreferencePointVerticesPolygon 类类referencePointVerticesDraw()move(x,y)contains(aPoint)
19、Polygon的子类的子类Quadrilateral类类Quadrilateral第32页,本讲稿共72页算法定义算法定义n定义:定义:一个有穷的指令集一个有穷的指令集,这些指令为解决某,这些指令为解决某一特定任务规定了一个运算序列一特定任务规定了一个运算序列n特性:特性:u输入输入 有有0个或多个输入个或多个输入u输出输出 有一个或多个输出有一个或多个输出(处理结果处理结果)u确定性确定性 每步定义都是确切无歧义的每步定义都是确切无歧义的u有穷性有穷性 算法应在执行有穷步后结束算法应在执行有穷步后结束u有效性有效性 每一条运算应足够基本每一条运算应足够基本第33页,本讲稿共72页n事例学习:
20、事例学习:选择排序问题选择排序问题n明确问题:明确问题:递增排序递增排序n解决方案:解决方案:逐个选择最小数据逐个选择最小数据n算法框架:算法框架:for(int i=0;i n-1;i+)/n-1趟趟 从从ai检查到检查到an-1;若最小整数在若最小整数在ak,交换交换ai与与ak;n细化程序:细化程序:程序程序 SelectSort 算法设计算法设计 自顶向下,逐步求精自顶向下,逐步求精 第34页,本讲稿共72页 void selectSort(int a,const int n)/对n个整数a0,a1,an-1按递增顺序排序 for(int i=0;i n-1;i+)int k=i;/从
21、ai查到an-1,找最小整数,在ak for(int j=i+1;j n;j+)if(aj ak)k=j;int temp=ai;ai=ak;ak=temp;第35页,本讲稿共72页模板模板 (template)(template)定义定义 适合适合多种数据类型多种数据类型的的类定义类定义或或算法算法,在特定环,在特定环境下通过简单地代换,变成境下通过简单地代换,变成针对具体某种数据针对具体某种数据类型类型的的类定义类定义或或算法。算法。第36页,本讲稿共72页用模板定义用于排序的数据表类用模板定义用于排序的数据表类#ifndef DATALIST_H#define DATALIST_H#in
22、clude /K是表项关键码类型template /E是表项类型class dataList private:E*element;int listSize;void swap(int m1,int m2);int minKey(int low,int high);第37页,本讲稿共72页 public:dataList(int size=10):listSize(size),element(new Esize)dataList()delete element;void sort();friend ostream&operator (ostream&outStream,dataList&outL
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 概念
限制150内