数据结构课程简介课件.ppt
《数据结构课程简介课件.ppt》由会员分享,可在线阅读,更多相关《数据结构课程简介课件.ppt(74页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、-电子课件电子课件 数据结构是一门研究数据结构是一门研究非数值计算非数值计算的程序设计问题中计算机的程序设计问题中计算机的的操作对象操作对象及其之间及其之间关系与操作关系与操作的学科,是介于的学科,是介于数学、计算机数学、计算机硬件和计算机软件硬件和计算机软件三者之间的一门核心课程,属于计算机学科三者之间的一门核心课程,属于计算机学科中的一门综合性专业基础课程,它不仅是一般程序设计的基础,中的一门综合性专业基础课程,它不仅是一般程序设计的基础,也是设计和实现编译程序、操作系统、数据库系统及其他系统也是设计和实现编译程序、操作系统、数据库系统及其他系统程序和大型应用程序的重要基础。是计算机专业专
2、升本、考研程序和大型应用程序的重要基础。是计算机专业专升本、考研必考课程。必考课程。数据结构课程简介 学业基础学业基础先修课程:先修课程:离散数学、高级语言程序设计离散数学、高级语言程序设计 (如如C C语言语言)后续课程:后续课程:操作系统、数据库原理、人工智能等。操作系统、数据库原理、人工智能等。数据结构数据结构(C(C语言版语言版)教材:教材:数据结构数据结构(C(C语言版语言版)参考书:参考书:1数据结构题集数据结构题集严蔚敏严蔚敏2数据结构数据结构与算法分析与算法分析C语言描述语言描述(英文版(英文版.第第2版)人邮社陈越改编版)人邮社陈越改编3数据结构数据结构使用使用C语言(第语言
3、(第3版)版),西,西安交大出版社,安交大出版社,2003年朱战立编著年朱战立编著 内内 容容 安安 排排章章内内 容容 学时学时 章章 内内 容容 学时学时 1绪绪 论论2+22+27图图10+210+22线性表线性表8+28+28动态存储管理动态存储管理2 23栈和队列栈和队列10+410+49查找查找12+212+24串串4+24+210内部排序内部排序8+28+25数组和广义表数组和广义表 4 411外部排序外部排序1 16树和二叉树树和二叉树 12+412+412文件文件1 1学习要求1 1、上课认真听讲,适当做好笔记,按时交作业。、上课认真听讲,适当做好笔记,按时交作业。2 2、复
4、习和预习。、复习和预习。3 3、课后需要多读课本和参考书,上网查看相关内容,、课后需要多读课本和参考书,上网查看相关内容,在理解基本内容的基础上,多看、多做习题。在理解基本内容的基础上,多看、多做习题。4 4、上机实践。、上机实践。1.1数据结构讨论的范畴数据结构讨论的范畴1.2基本概念基本概念1.3算法和算法的量度算法和算法的量度第一章 绪论1.11.1 数据结构讨论的范畴数据结构讨论的范畴Niklaus Wirth:Algorithm+DataStructures=Programs程序设计程序设计:算法算法:数据结构数据结构:为计算机处理问题编制 一组指令集 处理问题的策略处理问题的策略问
5、题的数学模型问题的数学模型 f(x)=ax2+bx+c 例如例如:数值计算的程序设计问题数值计算的程序设计问题 一元二次方程求解 一元线性回归分析经济预测 例一:例一:计算机对弈算法:?模型:?对弈的规则和策略棋盘及棋盘的格局非数值计算的程序设计问题非数值计算的程序设计问题例二:例二:学生的数据库管理算法:?模型:?需要管理的项目?如何管理?用户界面?各种表格概括地说:概括地说:数据结构是一门讨论数据结构是一门讨论“描述现实世描述现实世界实体的数学模型界实体的数学模型(非数值计算非数值计算)及其及其上的操作在计算机中如何表示和实现上的操作在计算机中如何表示和实现”的学科。的学科。数据结构数据结
6、构=逻辑结构逻辑结构+存储结构存储结构+运算运算1.2 基本概念基本概念一、数据与数据结构一、数据与数据结构二、数据类型二、数据类型三、抽象数据类型三、抽象数据类型一、数据与数据结构一、数据与数据结构所有能被输入被输入到计算机中,且能被计算机处理的符号处理的符号的集合。数据数据:是数据(集合)中的一个“个体个体”数据元素数据元素:是数据结构中讨论的基本基本单位 数据项:数据项:是数据结构中讨论的最小最小单位数据元素可以是数据项的集合数据元素可以是数据项的集合例如:描述一个学生的数据元素可以是称之为组合项称之为组合项姓名姓名 性别性别 出生日期出生日期 入学日期入学日期系科系科成绩成绩 数据结构
7、:数据结构:带结构结构的数据元素的集合假设用三个三个4位的十进制数位的十进制数表示一个含 12位位数的十进制数。数的十进制数。3214,6587,9345 a1(3214),a2(6587),a3(9345)则在数据元素 a1、a2 和 a3 之间存在着“次序次序”关系关系 a1,a2、a2,a3 3214,6587,9345 a1 a2 a3 6587,3214,9345 a2 a1 a3例如例如:再例,在一维数组 a1,a2,a3,a4,a5,a6 的数据元素之间存在如下的次序关系次序关系:|i=1,2,3,4,5 或者说,数据结构数据结构是相互之间存在着某相互之间存在着某种种逻辑逻辑关系
8、的数据元素的集合关系的数据元素的集合。数据结构:数据结构:带结构结构的数据元素的集合可见,不同的“关系关系”构成不同的“结构结构”数据的逻辑结构逻辑结构可归结为以下四类四类:线性线性结构树形树形结构图状图状结构集合集合结构1 1对对1 11 1对多对多多对多多对多松散松散非非线线性性例:例:UNIX文件系统的系统结构图文件系统的系统结构图例:例:n个网站之间的连通关系个网站之间的连通关系树形关系树形关系树形关系树形关系网状关系网状关系网状关系网状关系数据结构的形式定义数据结构的形式定义为:数据结构数据结构是一个二元组 Data_Structures=(D,S)其中:D 是数据元素的有限集数据元
9、素的有限集,S 是 D上关系的有限集关系的有限集。逻辑结构示例:逻辑结构示例:S=(D,R)D=a,b,c,d,e,fR=(a,e),(b,c),(c,a),(e,f),(f,d)解:解:上述表达式可用图形表示为:上述表达式可用图形表示为:bcaefd此结构为此结构为线性线性的。的。例例1:用图形表示下列数据结构,并指出它们是属于线性:用图形表示下列数据结构,并指出它们是属于线性结构还是非线性结构。结构还是非线性结构。d1d5d2d4d3该结构该结构是非线性是非线性的。的。解:上述表达式可用图形表示为:解:上述表达式可用图形表示为:(2)S=(D,R)D=di|1i5 R=(di,dj),ij
10、课堂练习课堂练习数据的存储结构存储结构 逻辑结构在存储器中的映象逻辑结构在存储器中的映象“数据元素数据元素”的映象的映象?“关系关系”的映象的映象?数据元素的映象方法:数据元素的映象方法:用二进制位(bit)的位串表示数据元素(321)10 =(501)8 =(101000001)2关系的映象方法:关系的映象方法:(表示(表示 x,y 的方法的方法)顺序映象顺序映象以相对的存储位置表示后继关系以相对的存储位置表示后继关系链式映象链式映象以附加信息以附加信息(指针指针)表示后继关系表示后继关系对于一个数据结构对于一个数据结构B=(K,R)其中其中K=k1,k2,k3,k4,k5,k6,k7,k8
11、,k9R=rr=,它的顺序存储方式如图所示它的顺序存储方式如图所示例例2-(1)对于一个数据结构对于一个数据结构B=B=(K K,R R)其)其中中K=k1,k2,k3,k4,k5K=k1,k2,k3,k4,k5R=rR=rr=,kr=,4,k5它的链式存储方式如图所示它的链式存储方式如图所示例例2-(2)在不同的编程环境中,在不同的编程环境中,存储结构可有不同的描述方法。存储结构可有不同的描述方法。通常可用高级编程语言中提供的通常可用高级编程语言中提供的数据类型数据类型描述之描述之。二、数据类型二、数据类型 在用高级语言的源程序中,对程序中出现的每个变量、常量或表达式,需要说明说明它们所属的
12、数据类型数据类型。数据类型数据类型 是一个是一个 值的集合值的集合和定义在此集合上的和定义在此集合上的 一组操作一组操作的总称。的总称。三、抽象数据类型三、抽象数据类型 (AbstractDataType简称简称ADT)是指一个数学模型以及是指一个数学模型以及定义在此数学模型上的一定义在此数学模型上的一组操作。组操作。ADT有两个重要特征:数据抽象数据抽象 用ADT描述程序处理的实体时,强调的是其本质的特征本质的特征、其所能完成的其所能完成的功能功能以及它和外部用户的接口外部用户的接口。数据封装数据封装 将实体的外部特性和其内部外部特性和其内部实现细节分离实现细节分离,并且对外部用户隐藏对外部
13、用户隐藏其内部实现细节。其内部实现细节。抽象数据类型的描述方法抽象数据类型的描述方法抽象数据类型可用抽象数据类型可用(D,S,P)三元组表示。三元组表示。其中:其中:D是数据对象;是数据对象;S是是 D上的关系集;上的关系集;P是对是对 D的基本操作集。的基本操作集。ADT 抽象数据类型名抽象数据类型名 数据对象:数据对象:数据对象的定义 数据关系:数据关系:数据关系的定义 基本操作:基本操作:基本操作的定义ADT 抽象数据类型名其中基本操作的定义格式为:基本操作名基本操作名(参数表)初始条件:初始条件:初始条件描述 操作结果操作结果:操作结果描述 赋值参数赋值参数 只为操作提供输入值。引用参
14、数引用参数 以&打头,除可提供输入值外,还将返回操作结果。初始条件初始条件 描述了操作执行之前数据结构和参数应满足的条件,若不满足,则操作失败,并返回相应出错信息。操作结果操作结果 说明了操作正常完成之后,数据结构的变化状况和应返回的结果。若初始条件为空,则省略之。例如,例如,抽象数据类型复数复数的定义:数据对象:数据对象:De1,e2e1,e2RealSet 数据关系:数据关系:R1|e1是复数的实数部分|e2 是复数的虚数部分 ADTComplex基本操作:基本操作:AssignComplex(&Z,v1,v2)操作结果:构造复数 Z,其实部和虚部 分别被赋以参数 v1 和 v2 的值。D
15、estroyComplex(&Z)操作结果:复数Z被销毁。GetReal(Z,&realPart)初始条件:复数已存在。操作结果:用realPart返回复数Z的实部值。GetImag(Z,&ImagPart)初始条件:复数已存在。操作结果:用ImagPart返回复数Z的虚部值。Add(z1,z2,&sum)初始条件:z1,z2是复数。操作结果:用sum返回两个复数z1,z2 的 和值。ADTComplex抽象数据类型的表示和实现抽象数据类型的表示和实现 抽象数据类型需要通过固有数据固有数据类型类型(高级编程语言中已实现的数据类型)来实现。例如,对以上定义的复数。例如,对以上定义的复数。type
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 课程 简介 课件
限制150内