下载

2下载券

加入VIP
  • 专属下载特权
  • 现金文档折扣购买
  • VIP免费专区
  • 千万文档免费下载

上传资料

关闭

关闭

关闭

封号提示

内容

首页 PPT2

PPT2.ppt

PPT2

418208060
2011-09-29 0人阅读 举报 0 0 暂无简介

简介:本文档为《PPT2ppt》,可适用于高等教育领域

数据结构数据结构黄海平计算机学院计算机科学与技术系江苏省无线传感网高技术研究重点实验室Email:hhpnjupteducn常用电话:教学网站:http:选课密钥:datastructurehttp:wwwwsnsnetcn课程的性质、目的和任务《数据结构》课程从性质来讲是计算机软件专业的一门专业基础课。随着计算机技术在各领域应用的不断深入必然改变非计算机专业(尤其是电子信息类专业)学生的知识结构要求他们掌握软件技术知识以结合本专业的需要从事软件的研究和开发。作为非计算机专业软件技术基础系列课程中的《数据结构》其目的在于培养非计算机专业学生学会用面向对象方法描述各种数据结构使用数据结构进行较为复杂的程序设计的能力。本课程介绍线性表、栈、队列、数组、树及二叉树、图、集合等等基本数据结构包括它们的逻辑结构及其实现介绍它们在实际中的应用初步介绍算法的时间和空间分析方法。本课程将采用C语言描述各种结构和算法。总学时:学时。其中:学时讲课学时上机讲课自学习题课上机合计第一章第二章第三章第四章第五章第六章第七章第八章第九章第十章合计上机实验:实验一:线性表的基本运算及多项式的算术运算实验二:二叉树的基本操作及哈夫曼编码译码系统的实现实验三:图的基本运算及飞机换乘次数最少问题实验四:各种内排序算法的实现及性能比较教材及主要参考书:、教材《数据结构使用C语言描述(第版)》陈慧南人民邮电出版社年、主要参考书《数据结构(用面向对象方法及C描述)》殷人昆等清华大学出版社、DataStructures,AlgorithmsandApplicationsinC,SartajSahni,机械工业出版社、DataStructureswithC,WilliamFord,清华大学出版社准备:复习C的相关内容如指针、类模板等。http:的使用方法http:的使用方法输入网址访问该网页找到“计算机科学与技术系”的链接点击该链接找到《数据结构B黄海平》课程点击进入选课密钥是datastructure学生需要注册用户名一定是你的学号注册后可以提问答疑、下载课件等。引言数据结构的概念及其研究的问题是本章中重要的概念它们贯穿整本书。除了数据结构研究的三个方面我们对每种数据结构都会给出应用的实例。要学会描述数据结构和算法分析算法的时、空复杂度。第章基础知识内容提要.给出数据结构的概念.介绍数据抽象和抽象数据类型.说明数据结构和算法描述的方法.介绍算法和算法分析的基本方法算法和数据结构课堂提要第章基础知识算法和数据结构什么是数据结构数据抽象和抽象数据类型描述数据结构和算法算法分析的基本方法数据结构和算法是计算机学科的基础之一更是软件技术的基础。数据的组织和表示方法直接影响使用计算机求解问题的效率。算法设计通常建立在所处理数据的一定组织形式之上的它们之间有着本质的联系。当讨论一种算法时自然要涉及算法所处理的数据问题。程序=数据结构算法对大家来说数据结构其实并不陌生。比如:设计一个程序能对全校的学生档案进行管理。数据结构由数据元素组成在数据结构上定义一组操作(运算)。数据:计算机加工处理的对象数值数据和非数值数据()数值数据:包括整数、实数或复数。主要用于工程与科学计算。()非数值数据:包括字符、文字、图形、图象、语音等。用于情报检索、企业管理、图形图象、人工智能、远程教育、远程医疗、电子商务、电子图书馆和办公自动化等诸多领域。回顾几个概念:什么是数据结构课堂提要第章基础知识算法和数据结构什么是数据结构数据抽象和抽象数据类型描述数据结构和算法算法分析的基本方法基本概念数据是计算机加工处理的对象一个数据可以是由成分数据组成的。成分数据就是数据项不可再分割。数据元素:由成分数据组成的数据。是组成数据的基本单位。数据元素可以是简单类型的也可以是结构类型的如记录。数据结构举例表学生情况表什么是数据结构数据结构是由数据元素依据某种逻辑联系组织起来的。它主要研究三个方面的内容:逻辑结构:对数据元素间逻辑关系的描述称为数据的逻辑结构。存储结构:数据结构的实现形式是数据结构在计算机内的表示。运算:在数据结构上执行的运算。数据的逻辑结构数据结构的逻辑结构可以用一个二元组表示。即DS=(DR)其中D是数据元素的有限集合R是D中数据元素序偶的集合。例如DS={D,R},D={a,b,c,d},R={<a,b>,<b,c>,<c,d>},其中序偶<a,b>表示a和b之间的关系我们称为a是b的直接前驱b是a的直接后继。小圆圈代表数据元素两个不同元素的序偶称为边。种基本的逻辑结构根据数据结构中数据元素之间关系的不同特征可以划分为以下四种基本逻辑结构:线性结构:数据元素之间存在一对一的关系。一个前驱一个后继。树形结构:数据元素之间存在一对多的关系。图结构:数据元素之间存在多对多的关系。每个结点的前驱和后继的数目都不同。集合结构:结构中的数据元素之间除了“同属于一个集合”的关系外没有其它关系。四种逻辑结构也可以只分成两类:线性结构和非线性结构。数据的存储表示顺序和链接是两种最基本的存储表示方法。顺序存储顺序(或称连续)表示方法需要一块连续的存储空间并把逻辑上相关的数据元素一次存储在该连续的存储区中。例如由个元素组成的线性数据结构(a,a,a,a)存储在某个连续的存储区内设存储区的起始地址是假定每个元素占个存储单元。Loc(ak)=×k链接存储连接存储表示下为在机内存储一个元素除了需要存放该元素本身的信息外还需要存放于该元素相关的其它元素的地址信息。这两部分信息组成一个数据元素的结点。例如线性结构(a,a,a,a)的链接存储表示。结点存储块分成两部分元素本身和该元素后继元素所在结点的存储地址。地址信息称为链。“^”表示空链。除了连接和顺序存储还有索引和散列方法。数据结构的运算逻辑结构描述了数据的静态性那么在数据的逻辑结构上定义的一组运算给出了数据被使用的方式即数据的动态性。数据结构的最常见的运算有:()创建运算创建一个数据结构()清除运算删除数据结构的全部元素()插入运算在数据结构中插入一个新元素()删除运算将数据结构中的某个指定元素删除()搜索运算在数据结构中搜索满足一定条件的元素()更新运算修改数据结构中某个指定元素的值()访问运算访问数据结构中某个元素()遍历运算按照某种次序系统访问数据结构的各个元素使得每个元素恰好被访问一次。如果一个数据结构一旦创建其结构不放生改变则称为静态数据结构否则称为动态数据结构。数据抽象和抽象数据类型抽象:抽取事物的共同的和实质的东西忽略其非本质的细节。例如“学生”这一概念是对学生群体的抽象它抽取了学生这一群体的共性忽略了每个学生的特殊性。课堂提要第章基础知识算法和数据结构什么是数据结构数据抽象和抽象数据类型描述数据结构和算法算法分析的基本方法一、数据类型C语言的数据类型()基本类型:字符、整数、枚举、实数、双精度数()构造类型:数组、结构和联合()指针类型:指针例如二维整型数组inta定义了一个包含个整数的二维数组。又如结构类型structStudent{char*nameintstudentidchargrade}定义了结构类型Student,包括以下三个域:name,studentid和grade。数据类型一个数据类型定义了一个值的集合以及作用于该值集的操作的集合。即一组值和一组操作。例如inta变量a的取值范围是:对变量a执行的操作有:算术运算、、*、、关系运算<、>、<=、>=、==、!=赋值运算=二、数据抽象数据类型是具有相同值集和操作集的数据对象(变量和常量)的抽象。相同的数据类型的变量具有相同的取值范围允许执行相同的操作对变量执行允许的操作可以不必考虑变量在计算机内的存储细节和这些操作是如何执行的。三、抽象数据类型抽象数据类型(AbstractDataType,ADT)是一个数据类型其主要特征是该类型的对象及其操作的规范,与该对象的表示和操作的实现分离即使用和实现分离并实行封装和信息隐蔽。例如inta整型int的规范包括变量a的取值范围是:对变量a执行的操作有:算术运算、、*、、关系运算<、>、<=、>=、==、!=赋值运算=使用和实现分离:使用者通过规范使用该类型的数据而不必考虑其实现细节改变实现将不影响使用。封装和信息隐蔽:将数据和代码组合在一起数据类型的细节对外部是隐蔽的。例如inta其实现是隐蔽的使用者只能通过整型上定义的一组运算对变量a执行操作。整型int的实现是指变量a在计算机内存储表示方法。操作的实现是指整型上定义的操作的具体实现方法。数据结构可分成以下两部分:()数据结构的规范:逻辑结构和运算的定义()数据结构的实现:存储结构和运算算法实现规范是实现的准则和依据。规范指明“做什么”实现解决“怎样做”。描述数据结构和算法数据结构的抽象层次数据结构抽象为一种聚集结构。课堂提要第章基础知识算法和数据结构什么是数据结构数据抽象和抽象数据类型描述数据结构和算法算法分析的基本方法数据结构被看成是一个类属抽象数据类型(ADT)用格式化的自然语言来描述。另外数据结构可以形式地用一个C的抽象模板类描述。数据结构的描述方法堆栈数据结构举例ADT栈抽象数据类型ADTStack{Data:个或多个元素的线性序列(aaan)遵循LIFO原则。Operations:Create():创建一个空栈。Destroy():撤消一个栈。Push(x):元素x插入栈顶。Pop():删除栈顶元素。Top(x):在x中返回栈顶元素。}                用ADT描述数据结构堆栈的例子程序栈的C模板抽象类template<classT>classStack{public:virtualvoidPush(Tx)=virtualvoidPop()=virtualTTop(Tx)const=…}除了构造函数其余成员函数都是纯虚函数。顺序栈类SeqStack是类Stack在顺序存储表示下的一种实现它是从抽象类Stack派生出来的它可以实例化。实现数据结构template<classT>classSeqStack:publicStack<T>{public:…private:T*sintmaxTopinttop}template<classT>SeqStack<T>::SeqStack(intmSize){maxTop=mSizes=newTmSizetop=}算法分析的基本方法内容提要算法及其性能分析算法的空间复杂度算法的时间复杂度渐近时间复杂度课堂提要第章基础知识算法和数据结构什么是数据结构数据抽象和抽象数据类型描述数据结构和算法算法分析的基本方法什么是算法一个算法(algorithm)是对特定问题的求解步骤的一种描述它是指令的有限序列此外算法具有下列五个特征:()输入算法有零个或多个输入。()输出算法至少产生一个输出。()确定性算法的每一条指令都有确切的定义没有二义性。()能行性算法的每一条指令都足够基本它们可以通过已经实现的基本运算执行有限次来实现。()有穷性算法必须总能在执行有限步之后终止。算法及其性能分析算法描述方法算法可以自然语言、流程图或程序设计语言描述。当一个算法用程序设计语言描述时便成为程序。本书中主要使用C语言描述。算法的性能标准()正确性:算法的执行结果应当满足预先规定的功能和性能要求。()简明性:一个算法应当思路清晰、层次分明、易读易懂。()健壮性:当输入不合法数据时应能做适当处理不至于引起严重后果。()效率:有效使用存储空间和有高的时间效率。()最优性:解决同一个问题可能有多种算法应进行比较选择最佳算法。算法的时间复杂度程序步一个程序步是指在语法上或语义上有意义的程序段该程序段的执行时间与问题实例的特征无关。算法的时间复杂度是程序运行从开始到结束所需的时间。程序求一个数组元素的累加之和floatsum(floatlist,constintn){floattempsum=countfor(inti=i<ni){ncounttempsum=listincount}countcountreturntempsum}程序步数为n。渐近时间复杂度大O记号如果存在两个正常数c和n使得对所有的nnn有f(n)cg(n)则有f(n)=O(g(n))。例如设T(n)=nnn则根据大O记号的定义容易证明T(n)=O(n)渐近时间复杂性使用大O记号表示的算法的时间复杂性称为算法的渐近时间复杂性。在大O记号下可用程序步来估计算法的执行时间。很多情况下可以通过考察一个算法中的关键操作(关键操作被认为是一个执行次数最多的程序步)的执行次数来计算算法的渐近时间复杂性。常见的渐近时间复杂性从小到大排列有:O()<O(logn)<O(n)<O(nlogn)<O(n)<O(n)O()是错误写法。例如程序为求一个数组元素的累加之和的算法。floatsum(floatlist,constintn){floattempsum=for(inti=i<ni)ntempsum=listinreturntempsum}()总的程序步数为n≤n则渐近时间复杂性为O(n)。()语句tempsum=listi可认为是关键操作它的执行次数为n次则渐近时间复杂性为O(n)。voidMult(intann,bnn,cnn,intn){nn矩阵a与b相乘得到c。for(inti=i<ni)nfor(intj=j<nj)n(n){cij=nfor(intk=k<nk)n(n)cij=aik*bkjn}}程序步为:nnn渐近时间复杂度为:T(n)=O(n)再看一例:最好、最坏和平均情况时间复杂度比如在一维数组上查找一个给定元素。算法的空间复杂度是程序运行从开始到结束所需的存储量。算法的空间复杂度问题实例的特征与问题的具体实例有关的量。例如对一组特定个数的元素进行排序对该组元素的排序是排序问题的一个实例。元素的个数可视为该实例的特征。程序运行所需的存储空间包括两部分:()固定部分这部分空间与所处理数据的大小和个数无关或者称与问题的实例的特征无关。主要包括程序代码、常量、简单变量、定长成分的结构变量所占的空间。()可变部分这部分空间大小与算法在某次执行中处理的特定数据的大小和规模有关。例如分别为个元素的两个数组相加与分别为个元素的两个数组相加所需的存储空间显然是不同的。()空间复杂度一般按最坏情况来分析

用户评价(0)

关闭

新课改视野下建构高中语文教学实验成果报告(32KB)

抱歉,积分不足下载失败,请稍后再试!

提示

试读已结束,如需要继续阅读或者下载,敬请购买!

文档小程序码

使用微信“扫一扫”扫码寻找文档

1

打开微信

2

扫描小程序码

3

发布寻找信息

4

等待寻找结果

我知道了
评分:

/46

PPT2

VIP

在线
客服

免费
邮箱

爱问共享资料服务号

扫描关注领取更多福利