数据结构DataStructures.ppt

数据结构Data Structures,任课教师：张淑平 辅导教师：,2,关于本课程,课程性质：必修考核方式：考试(闭卷)成绩(80%)+平时成绩(20%)3.5学分 课程实验成绩(程序验收报告)100%1学分学习要求：严禁旷课、迟到；课前请关闭手机或调至振动，严禁课堂接听或拔打电话；要独立思考，按时完成作业。在自己不会解答时可参考其他资料或他人答案，在分析别人的处理思路之后自己动手，鼓励相互讨论，严禁抄袭；上机实验前应先就要处理的问题写出自己的解决思路和大纲，严禁在机房游戏、网上聊天、流览不相关的网页；上机程序要现场验收、严禁拷贝他人程序及报告。,3,本课程的内容框架,4,课程特点,很强的理论性本课程不是以掌握应用性知识为目的，而是以掌握基本理论，基本方法，基本技能为目的。让学生把握解决什么样的问题，用什么思想，采用什么方法解决，以及用什么方法最优解决等一系列问题。很强的概念性本课程要求学生不但应该深刻理解某些概念的所有要素,同时也要求理解为什么要引入某些概念，这些概念的形成过程，以及引入这些概念解决什么样的问题。,5,课程特点(续),很强的连贯性本课程结构紧凑，每部分所述问题层层推进，逐步深入。全课程始终是以数据间的关系即“结构”为主线索展开。其中“基本数据结构”部分围饶数据结构三要素即逻辑结构、物理结构、运算特性展开，辅以一定该数据结构基本应用的讲述；而“应用数据结构部分”以基本概念、基本方法、性能分析的顺序展开，使全课程大量庞杂的内容条理分明，轮廓分明。容易混淆性本课程中有一些容易混淆的基本概念，也有很多算法，状态等等一系列问题都容易混淆。比如要解决某类问题，也许有很多方法和很多途径，每种方法和途径适用于什么场合，各自存在什么优缺点（例如“内部排序”这一章中各中内排方法的比较与应用），都容易产生相互混淆。,6,本课程学习方法,循序渐进学习法由于本课程很强的理论性、概念性和连贯性，所以学习过程中要从概念入手，逐段、逐节、逐章深刻理解和掌握，层层推进，从基础到应用，最后达到完全掌握该课程内容的要求，加强上机实践环节是非常必要的，能增强对数据结构的理解和应用能力。概括提炼学习法每学完一节、一章内容，都要从中概括提炼出本部分内容的要点和重点。一则可以达到内容总结、有效复习的目的，二则可以自检学习中存在的问题。,7,课程学习方法(续),归纳对比学习法针对课程中容易混淆的概念以及课程中同类、非同类容易混淆的问题，进行归纳和比较，从中找出它们的异同点、优缺点。这种方法不仅能搞清楚容易混淆的问题，而且能更深刻理解本课程的内容实质。循环学习法由于课程中许多基本概念和复杂算法在顺序地学习过程中并不能达到准确、透彻地理解的程度，有些概念和方法可以应用在多种场合，对这些内容，在学习时就需要循环往复，借助后续内容的信息来全面把握。,8,第一章 绪论,本章内容：1.1 什么是数据结构1.2 基本概念和术语1.3 抽象数据类型的表示与实现1.4 算法和算法分析1.4.1 算法1.4.2 算法设计的要求1.4.3 算法效率的度量1.4.4 算法的存储空间的需求,9,1.1 什么是数据结构,数据结构学科发展背景 应用领域从科学计算到非数值计算 起初数据结构中内容在其他课程中表述 1968年美国唐.欧.克努特(Donald E.Knuth)开创数据结构最初体系。在计算机程序设计技巧第一卷基本算法系统阐述数据的逻辑结构、存储结构及操作 数据结构的两个发展方向：面向专门领域特殊问题的数据结构；从抽象数据类型的观点讨论数据结构,10,1.1 什么是数据结构,计算机解决问题的过程,具体问题,描述非数值计算问题的数学模型不再是数学方程，而是诸如表、树和图之类的数据结构。,11,1.1 什么是数据结构,非数值型计算问题举例：学籍管理(信息处理类问题),此类问题已独立成为数据库学科，在数据结构中主要在文件一章有所涉及。,12,1.1 什么是数据结构,非数值型计算问题举例：博弈类问题,此类问题中的数据结构可用树描述。,还有更复杂的问题需要用图来解决。,13,1.1 什么是数据结构,数据结构学科的地位 综合性的专业基础课 介于数学、计算机硬件和计算机软件之间的核心课程 不仅是一般程序设计的基础，而且是设计和实现编译程序、操作系统、数据库系统及其他系统程序和大型应用程序的重要基础 本课程的先修课程：离散数学、C语言(或其他程序设计语言)本课程后续课程：面向对象程序设计、操作系统、编译原理、数据库系统、人工智能等,14,1.1 什么是数据结构,什么是数据结构数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象间的逻辑结构和物理结构以及它们之间相互关系，并对这种结构定义和实现相应运算的学科。,15,1.2 基本概念和术语,基本概念 数据(Data)：指所有能输入到计算机中并被计算机程序加工处理的符号的总称。不仅包括数字、字符串，还包括图形、图像、声音、动画、视频等能通过编码而被加工的数据形式。数据元素(Data Element)：是数据的基本单位，数据集合中的元素。数据项(Data Item)：是数据的不可分割的最小单位。一个数据元素可由若干个数据项组成。数据对象(Data Object)：是性质相同的数据元素的集合，是数据的一个子集。数据结构(Data Structure)：是相互之间存在一种或多种特定关系的数据元素的集合。,16,1.2 基本概念和术语,逻辑结构 内涵：数据元素之间的关系，或称为“结构”。分类：*集合：松散的关系*线性结构：一对一的关系*树形结构：一对多的关系*网状结构：多对多的关系 描述性定义：用自然语言描述相互之间存在一种或多种特定关系的数据元素的集合。形式化定义：Data_Structure=（D，S）D=数据元素的有限集合S=D上关系的有限集合,17,1.2 基本概念和术语,存储结构(物理结构)：数据结构在计算机中的映象。包括数据元素的表示和关系的表示两个方面。分类：*顺序存储结构*链式存储结构描述方式：*数据元素用高级语言中的“数据类型”来描述*数据元素间的关系用数据元素间的存储相对位置关系(顺序存储结构)或在数据元素上增加指针(链式存储结构)来表达,18,1.2 基本概念和术语,数据类型一组性质相同的值的集合,以及定义于这个值集合上的一组操作的总称。这种类型通常由高级语言提供。如C语言中的数据类型:char int float double void字符型 整型 浮点型 双精度型 无值分类：*原子类型：值不可分解，如整型、指针类型等。*结构类型：值由若干成分按照某种结构组成，如数组、结构（记录）等。,19,1.3 抽象数据类型的表示与实现,抽象数据类型(Abstract Data Type，ADT)ADT指一个数学模型以及定义在该模型上的一组操作。ADT的定义仅取决于它的一组逻辑特性，而与其在计算机内部如何表示和实现无关。ADT比数据类型的范畴更广，除了具有固有数据类型的特性之外，还包括用户在设计软件系统时自己定义的数据类型。由用户定义，用以表示应用问题的数据模型由基本的数据类型组成,并包括一组相关的服务（或称操作）信息隐蔽和数据封装，使用与实现相分离,20,1.3 抽象数据类型的表示与实现,抽象数据类型形式化定义ADT=（D，S，P）D=数据对象S=D上的关系集P=对D的基本操作集定义形式：ADT 抽象数据类型名数据对象：数据关系：基本操作：ADT 抽象数据类型名,21,1.3 抽象数据类型的表示与实现,抽象数据类型示例ADT Triplet 数据对象：D=e1,e2,e3|e1,e2,e3属于ElemSet数据关系：R=,基本操作：InitTriplet(&T,v1,v2,v3)DestroyTriplet(&T)Get(T,i,&e)Put(&T,i,e)ADT Triplet,22,1.3 抽象数据类型的表示与实现,抽象数据类型分类分类标准：按照值的不同特性原子类型：变量的值不可分解固定聚合类型：变量的值成分的数目确定可变聚合类型：变量的值成分的数目不确定多形数据类型：变量的值成分不确定（成分类型可变）抽象数据类型表示与实现抽象数据类型表示与实现抽象数据类型通过固有数据类型来表示和实现。即利用处理器中已存在的数据类型来说明新的结构，用已经实现的操作来组合新的操作。类C语言的描述语法类C语言精选了C语言的一个核心子集，也做了若干扩充，以利于描述。如：存储结构用typedef；数据元素类型约定为ElemType；在形参表中，以&打头的参数为引用参数；等等。,23,1.4 算法和算法分析,算法内涵:是对特定问题求解步骤的一种描述，是指令的有限序列，其中每一条指令表示一个或多个操作。特性:有穷性：有穷步+有穷时间/每一步 确定性：指令的语义无二义性 可行性：算法能用基本操作完成 输入：零个或多个输入 输出：一个或多个输出,24,1.4 算法和算法分析,算法设计的要求 正确性（Correctness）可读性（Readablity）健壮性（Robustness）高时间效率与低存储量需求算法的描述方式 自然语言 程序设计语言 流程图 类高级语言（类C语言、类Pascal语言等）,25,1.4 算法和算法分析,算法选择时效率的考虑虽然我们希望所选的算法占用额外空间小，运行时间短，其他性能也好，但计算机的时间和空间这两大资源往往相互抵触。所以，一般算法选择的原则是：对于反复使用的算法应选择运行时间短的算法；而使用次数少的算法可力求简明、易于编写和调试；对于处理的数据量较大的算法可从如何节省空间的角度考虑。,26,1.4 算法和算法分析,算法时间效率的度量程序运行消耗时间取决于下列因素算法策略问题规模语言层次编译程序所产生的机器代码的质量机器执行指令的速度算法时间效率度量算法时间效率在软硬件环境相同的情况下取决于问题的规模，即T(n)=f(n)。算法时间效率度量的基本做法在算法中选取一种对于所研究问题来说是基本操作的原操作，以该基本操作重复执行的次数作为算法的时间度量。一般而言，这个基本操作是最深层循环内的语句中的原操作。,27,1.4 算法和算法分析,算法时间复杂度T(n)=O(f(n)称为算法的渐近时间复杂度，简称时间复杂度。算法语句频度与时间复杂度的关系一般算法消耗的实际时间为算法中每条语句频度之和，是n的函数T(n)。当n趋于无穷大时，T(n)的同阶无穷小即是算法时间复杂度。时间复杂度举例：例1、+x;s=0;将x自增看成是基本操作，则语句频度为，即时间复杂度为(1)如果将s=0也看成是基本操作，则语句频度为，其时间复杂度仍为(1)，即常量阶。,28,1.4 算法和算法分析,例2、for(i=1;i=n;+i)+x;s+=x;语句频度为：2n其时间复杂度为：O(n)即时间复杂度为线性阶。例3、for(i=1;i=n;+i)for(j=1;j=n;+j)+x;s+=x;语句频度为：2n2，其时间复杂度为：O(n2)即时间复杂度为平方阶。定理：若A(n)=a m n m+a m-1 n m-1+a1n+a0是一个m次多项式，则A(n)=O(n m)。时间复杂度O(nk)，k为常数，称为该时间复杂度为k次多项式阶。,29,1.4 算法和算法分析,最常用的算法的时间复杂度O(1)O(logn)O(n)O(nlogn)O(n2)O(n3)指数时间的关系为：O(2n)O(n!)O(nn)当n取值很大时，指数时间算法和多项式时间算法在所需时间上非常悬殊。因此，只要有人能将现有指数时间算法中的任何一个算法化简为多项式时间算法，那就取得了一个伟大的成就。,30,1.4 算法和算法分析,大O的运算规则加法准则(并列程序段)a)前提：T1(m)=O(f(m);T2(n)=O(g(n)结论：T(n)=T1+T2=O(max(f(m),g(n)b)前提：T1(n)=O(f(n);T2(n)=O(g(n)结论：T(n)=T1+T2=O(f(n)+g(n)乘法准则(嵌套程序段)前提：T1(n)=O(f(n);T2(n)=O(g(n)结论：T(n)=T1*T2=O(f(n)*g(n),31,1.4 算法和算法分析,算法存储空间的度量算法存储空间度量的基本做法用程序执行中需要的辅助空间的大小作为存储空间度量的依据，是问题规模n的函数。程序执行中程序本身和基本数据所需的工作单元计算空间复杂度时不算。算法空间复杂度S(n)=O(f(n)称为算法的空间复杂度。,32,本章小结,本次课程应掌握的内容解决非数值计算类问题的基本思路数据结构的基本概念抽象数据类型的定义算法及其评价作业1.8 1.9 1.11参考书目 1.Mark Allen Weiss,Data Structures and Problem Solving Using C+,published by Addison Wesley Longman,2000.2.Adam Drozdek 著Data Structures and Alogorithms in C+（Second Edition）（数据结构与算法C+版第二版），北京：清华大学出版社，2003年。,