哈工大-数据结构课件-严蔚敏《数据结构》(C语言版).ppt
- 文档编号:11259101
- 上传时间:2023-05-30
- 格式:PPT
- 页数:41
- 大小:528.50KB
哈工大-数据结构课件-严蔚敏《数据结构》(C语言版).ppt
《哈工大-数据结构课件-严蔚敏《数据结构》(C语言版).ppt》由会员分享,可在线阅读,更多相关《哈工大-数据结构课件-严蔚敏《数据结构》(C语言版).ppt(41页珍藏版)》请在冰点文库上搜索。
1.1数据结构及其讨论范畴1.2基本概念和术语1.3抽象数据类型的表示与实现1.4算法和算法分析,第1章绪论,本章重点难点,重点:
数据结构的逻辑结构、存储结构以及基本操作的概念及相互关系;抽象数据类型(ADT)的概念和实现方法,算法的时间复杂性和空间复杂性分析。
难点:
抽象数据类型(ADT)的概念和实现方法;算法的时间复杂性和空间复杂性分析。
1.1数据结构及其讨论范畴1.2基本概念和术语1.3抽象数据类型的表示与实现1.4算法和算法分析,第1章绪论,第1章绪论,1.1数据结构及其讨论范畴,算法+数据结构=程序设计,问题,构建数学模型,算法实现,在解决问题时可能遇到的典型的逻辑结构(数据结构)逻辑结构的存储映象(存储实现)数据结构的相关操作及其实现。
数据结构是一门讨论描述现实世界实体的数学模型(非数值计算)及其上的操作在计算机中如何表示和实现的学科。
第1章绪论,1.1数据结构及其讨论范畴,例1求n个整数中的最大值。
例2交叉路口的红绿灯管理。
例3煤气管道的铺设问题。
说明:
例子中的数学模型正是数据结构要讨论的问题。
第1章绪论,1.1数据结构及其讨论范畴,例,计算机的发展,数据处理的种类,数据,数值数据,非数值数据,数(整数,实数)字符字符串文字图形图象声音,对客观对象的符号表示,结果数据,第1章绪论,1.1数据结构及其讨论范畴,软件硬件应用领域,数值问题与非数值问题,数值问题例1已知:
游泳池的长len和宽wide,求面积area,设计求解问题的方法编程,建模型:
问题涉及的对象:
游泳池的长len宽wide,面积area;对象之间的关系:
area=lenwide,第1章绪论,1.1数据结构及其讨论范畴,学号姓名性别出生日期籍贯入学成绩所在班级00201杨润生男82/06/01广州56100计算机200102石磊男83/12/21汕头51200计算机100202李梅女83/02/23阳江53200计算机200301马耀先男82/07/12广州50900计算机3,非数值问题已知某级学生情况,要求分班按入学成绩排列顺序。
说明:
在此类文档管理的数学模型中,计算机处理的对象之间通常存在着一种最简单的线性关系,该数学模型称为线性模型。
第1章绪论,1.1数据结构及其讨论范畴,例,非数值问题,第1章绪论,1.1数据结构及其讨论范畴,下棋程序-国际象棋:
每次需要考虑的合乎规则的着法平均只有35步回合,计算机预先分析7至8个回合的着法。
若设为7个回合,则有超过1亿亿亿个不同的变化,经简化后,仍有500亿至600亿个变化。
多分析一步,增加18亿个变化。
根据计算机“深蓝”的速度,平均5分钟走一步。
算法:
对弈的规则和策略棋盘及棋盘的格局模型:
根据计算机“深蓝”的速度,例,迷宫问题:
在迷宫中,每走到一处,接下来可走的通路有三条。
计算机处理的这类对象之间通常不存在线性关系。
若把从迷宫入口处到出口的过程中所有可能的通路都画出,则可得一棵“树”。
第1章绪论,1.1数据结构及其讨论范畴,例,第1章绪论,1.1数据结构及其讨论范畴,对每种数据结构,主要讨论如下三方面的问题:
数据的逻辑结构数据元素之间的逻辑关系,是具体关系的抽象。
数据的存储结构(物理结构):
数据元素及其关系在计算机内存中的表示;数据的运算即对数据施加的操作。
定义在数据的逻辑结构上的抽象的操作。
1.1数据结构及其讨论范畴1.2基本概念和术语1.3数据结构的分类及表示1.4抽象数据类型的表示与实现1.5算法和算法分析,第一章绪论,数据:
是信息的载体,能够被计算机识别、存储和加工处理。
如整数,实数,字符串、图象、声音等都是数据。
数据元素:
数据的基本单位。
相当于“记录”,在计算机程序中通常作为一个整体考虑和处理。
数据项:
相当于记录的“域”或字段,是数据不可分割的最小单位。
如学号。
数据对象:
性质相同的数据元素的集合。
如所有班名相同的记录集合。
第1章绪论,1.2基本概念和术语,数据结构类型,第1章绪论,1.2基本概念和术语,数据结构是数据之间的相互关系,即数据的组织形式。
线性结构:
除第一个元素和最后一个元素之外,其他元素都有且仅有一个直接前驱,有且仅有一个直接后继;非线性结构:
其逻辑特征是一个结点可能有多个直接前驱和直接后继;,第1章绪论,1.2基本概念和术语,数据的逻辑结构,学号姓名专业政治面藐001王洪计算机党员002孙文计算机团员003谢军计算机团员004李辉计算机团员005沈祥福计算机党员006余斌计算机团员007巩力计算机团员008孔令辉计算机团员,学生间学号顺序关系是一种线性结构关系,第1章绪论,学生基本情况登记表,记录了每个学生的学号、姓名、专业、政治、面貌,表中的记录是按学生的学号顺序排列的。
1.2基本概念和术语,例,家族的族谱:
假设某家族有10个成员A,B,C,D,E,F,G,H,I,J,他们之间的血缘关系可以用如下图表示。
第1章绪论,1.2基本概念和术语,例,顺序存储方法:
数组链接存储方法:
指针索引存储方法散列存储方法,说明:
同一逻辑结构的不同存储结构,冠以不同的数据结构名称。
如顺序表、链表、散列表。
运算不同,数据结构也不同。
如栈和队列。
更进一步,顺序栈、链栈、顺序队列、链队列。
第1章绪论,1.2基本概念和术语,数据的存储结构,算法:
数据运算的描述数据结构:
数据的逻辑结构和存储结构,算法+数据结构=程序,第1章绪论,1.2基本概念和术语,1.1数据结构及其讨论范畴1.2基本概念和术语1.3抽象数据类型的表示与实现1.4算法和算法分析,第1章绪论,抽象数据型AbstractDataTypes(ADT),定义:
抽象数据型是一个数学模型和在该模型上定义的操作的集合,ADT特点:
降低了软件设计的复杂性;提高了程序的可读性和可维护性;程序的正确性容易保证,第1章绪论,1.3抽象数据类型的表示与实现,在软件设计中,可以对哪三种不同的对象进行抽象?
第1章绪论,1.3抽象数据类型的表示与实现,第1章绪论,1.3抽象数据类型的表示与实现,软件设计,软件设计是对数据抽象、过程抽象和控制抽象。
抽象数据型的规格描述,完整性:
反映所定义的抽象数据型的全部特征;统一性:
前后协调,不自相矛盾;通用性:
适用于尽量广泛的对象;不依赖性:
不依赖于程序设计语言。
语法:
给出操作的名称、I/O参数的数目和类型;语义:
由一组等式组成,定义各种操作的功能及相互之间的关系;,规格描述的两个方面:
语法和语义,第1章绪论,1.3抽象数据类型的表示与实现,抽象描述(高级语言)编写的程序三条原则:
符合规格描述的定义;有尽可能好的通用性;尽可能独立于程序的其它部分,自底向上与自顶向下相结合、由简单到复杂,第1章绪论,1.3抽象数据类型的表示与实现,抽象数据型的实现,多层次抽象技术,抽象数据类型的形式描述ADT=(D,S,P),其中:
D是数据对象;S是D上的关系集;P是D的基本操作集。
第1章绪论,1.3抽象数据类型的表示与实现,数据类型和抽象数据类型,抽象数据类型需要通过高级编程语言中已经实现的数据类型(通常称之谓固有数据类型)来实现;抽象数据类型的实现包括数据结构的实现和操作的实现。
第1章绪论,1.3抽象数据类型的表示与实现,抽象数据类型“复数”的定义为:
ADTComplex数据对象:
D=e1,e2|e1,e2属于RealSet数据关系:
R1=|e1是复数的实部,e2是复数的虚部其中用两个实数来表示复数,将复数定义为两个实数的有序对,并约定实部是前驱,虚部是后继。
例,设计函数DELEVAL(LIST,第1章绪论,1.3抽象数据类型的表示与实现,例,1.1数据结构及其讨论范畴1.2基本概念和术语1.3抽象数据类型的表示与实现1.4算法和算法分析,第1章绪论,第1章绪论,1.4算法与算法分析,算法(algorithm)的概念,算法是对问题求解过程的一种描述,是为解决一个或一类问题给出的一个确定的、有限长的操作序列。
严格说来,一个算法必须满足以下五个重要特性,关于本书采用的类语言描述:
C或C+,自然语言;程序设计语言;类语言。
算法描述,第1章绪论,1.4算法与算法分析,算法的基本特征,有穷性:
算法中的操作步骤为有限个,且每个步骤都能在有限时间内完成。
确定性:
组成算法的操作必须清晰无二义性。
可行性:
算法中的所有操作都必须足够基本,都可以通过已经实现的基本操作运算有限次实现之。
输入:
作为算法加工对象的量值,通常体现为算法中的一组变量。
些算法的字面上可以没有输入,实际上已被嵌入算法之中。
输出:
它是一组与输入有确定关系的量值,是算法进行信息加工后得到的结果,这种确定关系即为算法的功能。
在设计算法时通常应考虑以下原则,算法必须是“正确的”所谓算法是正确的,除了应该满足算法说明中写明的“功能”之外,应对各组典型的带有苛刻条件的输入数据得出正确的结果。
在算法是正确的前提下,算法的可读性是摆在第一位的,这在当今大型软件需要多人合作完成的环境下是换重要的,另一方面,晦涩难读的程序易于隐藏错误而难以调试。
应有很好的“可读性”,第1章绪论,1.4算法与算法分析,在设计算法时通常应考虑以下原则,必须具有“健壮性”算法的健壮性指的是,算法应对非法输入的数据作出恰当反映或进行相应处理,一般情况下,应向调用它的函数返回一个表示错误或错误性质的值。
算法的效率应考虑所设计的算法具有“高效率与低存储量”。
高效率与低存储量是矛盾的,要视具体问题而定。
第1章绪论,1.4算法与算法分析,影响时间特性的四个因素,定义语句频度:
语句重复执行的次数,第1章绪论,1.4算法与算法分析,程序运行时输入数据的总量;对源程序编译所需的时间;计算机执行每条指令所需的时间;程序中指令重复执行的次数。
所有算法均以函数形式给出,算法的输入数据来自参数表;参数表的参数在算法之前均进行类型说明;有关结点结构的类型定义,以及全局变量的说明等均在算法之前进行说明,描述算法的书写规则,第1章绪论,1.4算法与算法分析,评价算法标准,本课程采用以求解问题的基本操作(原操作)的执行次数作为算法时间的度量。
O(n3)称为矩阵相乘算法时间复杂度;O(n3)表示矩阵相乘算法执行时间与n3成正比,即O(n3)与n3同一数量级;,n阶矩阵相乘的算法,For(i=1;i=n;i+)For(j=1;j=n;j+)cij=0;For(k=1;k=n;k+)cij+=aik*bkj,乘法加法执行次数均为n3,例,第1章绪论,1.4算法与算法分析,说明:
有些算法,基本操作执行次数与问题的输入数据有关,这时可考虑算法平均时间复杂度算法在最坏情况下的时间复杂度,算法的时间复杂度T(n),第1章绪论,1.4算法与算法分析,一般来说,设算法中基本操作的执行次数是问题规模n的某个函数f(n),算法的时间复杂度记作:
T(n)=O(f(n)它表示随问题规模n的增大,算法执行时间的增长率与f(n)的增长率相同。
#defineN100voidscheme()inti,j,k,count,money;for(i=0;i=N;i+)for(j=0;j=N;j+)for(k=0;k=N;k+)count=i+j+k;money=3*i+2*j+0.5*k;if(count=N,算法的时间复杂度为O(n3),100元买100支笔,其中钢笔3元/支,圆珠笔2元/支,铅笔0.5元/支,各种组合方案的算法如下,计算时间复杂度。
例,第1章绪论,1.4算法与算法分析,本章小结,数据结构和算法等基本概念;数据的逻辑结构:
线性结构和非线性结构;数据的存储结构可以用以下存储方法;顺序存储链式存储索引存储散列存储抽象数据类型算法的特性算法的复杂度分析,第1章绪论,思考题:
操作系统是否是算法?
第1章绪论,
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 哈工大 课件 严蔚敏 语言版