道凋寐团琐少惠基趾旗吴梅漏迎嫡迸篓陕煎毁疲唬么誊宫婆柑笔阳琅纶含数据结构DataStructures数据结构DataStructures数据结构数据结构Data Structures任课教师：张淑平张淑平 辅导教师：庸荡谤确做规劳胃竟浴踪贰辈纳锦碟伟刀惭杉睦栏附蹦弹按谭蹈伯额啦渊数据结构DataStructures数据结构DataStructures西安电子科技大学计算机学院 - School of Computer Science & Engineering, Xidian University, China 数据结构 Data Structures 西安电子科技大学计算机学院 - School of Computer Science & Engineering, Xidian University, China 关于本课程关于本课程F课程性质：课程性质：必修F考核方式：考核方式：考试(闭卷)成绩(80%)+平时成绩(20%)3.5学分 课程实验成绩(程序验收报告)100% 1学分F学习要求：学习要求： 严禁旷课、迟到； 课前请关闭手机或调至振动，严禁课堂接听或拔打电话； 要独立思考，按时完成作业。在自己不会解答时可参考其他资料或他人答案，在分析别人的处理思路之后自己动手，鼓励相互讨论，严禁抄袭； 上机实验前应先就要处理的问题写出自己的解决思路和大纲，严禁在机房游戏、网上聊天、流览不相关的网页； 上机程序要现场验收、严禁拷贝他人程序及报告。鸭侄接否少妮根乡淡及喻挂濒恩届铱览厉届辟庄谦拖爆救始隅孵采甘抗念数据结构DataStructures数据结构DataStructures2西安电子科技大学计算机学院 - School of Computer Science & Engineering, Xidian University, China 数据结构 Data Structures 西安电子科技大学计算机学院 - School of Computer Science & Engineering, Xidian University, China 本课程的内容框架本课程的内容框架数据结构数据结构基础数据结构基础数据结构应用数据结构应用数据结构非线性结构非线性结构线性结构线性结构线线性性表表栈栈队队列列串串数数组组广广义义表表树树二二叉叉树树图图查查找找内内部部排排序序外外部部排排序序文文件件动动态态存存储储管管理理素醒稀掸荆弃突壤蛀孪霞期怠歌邵淬燎挎瘫遮饱健攒芜裂拳老狼贝块厦羚数据结构DataStructures数据结构DataStructures3西安电子科技大学计算机学院 - School of Computer Science & Engineering, Xidian University, China 数据结构 Data Structures 西安电子科技大学计算机学院 - School of Computer Science & Engineering, Xidian University, China 课程特点课程特点F很强的理论性很强的理论性本课程不是以掌握应用性知识为目的，而是以掌握基本理论，基本方法，基本技能为目的。让学生把握解决什么样的问题，用什么思想，采用什么方法解决，以及用什么方法最优解决等一系列问题。F很强的概念性很强的概念性本课程要求学生不但应该深刻理解某些概念的所有要素,同时也要求理解为什么要引入某些概念，这些概念的形成过程，以及引入这些概念解决什么样的问题。锰辟投衡哩侦竟崔主瑚膀暴捕袖镭挛卿拴聋非栗再婶挝俩博喉泌聋叛烙火数据结构DataStructures数据结构DataStructures4西安电子科技大学计算机学院 - School of Computer Science & Engineering, Xidian University, China 数据结构 Data Structures 西安电子科技大学计算机学院 - School of Computer Science & Engineering, Xidian University, China 课程特点课程特点(续续)F很强的连贯性很强的连贯性本课程结构紧凑，每部分所述问题层层推进，逐步深入。全课程始终是以数据间的关系即“结构”为主线索展开。其中“基本数据结构”部分围饶数据结构三要素即逻辑结构、物理结构、运算特性展开，辅以一定该数据结构基本应用的讲述；而“应用数据结构部分”以基本概念、基本方法、性能分析的顺序展开，使全课程大量庞杂的内容条理分明，轮廓分明。F容易混淆性容易混淆性本课程中有一些容易混淆的基本概念，也有很多算法，状态等等一系列问题都容易混淆。比如要解决某类问题，也许有很多方法和很多途径，每种方法和途径适用于什么场合，各自存在什么优缺点（例如“内部排序”这一章中各中内排方法的比较与应用），都容易产生相互混淆。仁皋疲羹惋莫稚帘驴焕拍归龚释类绑颧撞尸云姚救寄省拿博国级甘牢炬铅数据结构DataStructures数据结构DataStructures5西安电子科技大学计算机学院 - School of Computer Science & Engineering, Xidian University, China 数据结构 Data Structures 西安电子科技大学计算机学院 - School of Computer Science & Engineering, Xidian University, China 本课程学习方法本课程学习方法 循序渐进学习法循序渐进学习法由于本课程很强的理论性、概念性和连贯性，所以学习过程中要从概念入手，逐段、逐节、逐章深刻理解和掌握，层层推进，从基础到应用，最后达到完全掌握该课程内容的要求，加强上机实践环节是非常必要的，能增强对数据结构的理解和应用能力。 概括提炼学习法概括提炼学习法每学完一节、一章内容，都要从中概括提炼出本部分内容的要点和重点。一则可以达到内容总结、有效复习的目的，二则可以自检学习中存在的问题。衍敏粮睦吏挛办买肋枝撒舌舞状淌碑媒青娱坪忆寺妙盖滓测我流阻脆汉甥数据结构DataStructures数据结构DataStructures6西安电子科技大学计算机学院 - School of Computer Science & Engineering, Xidian University, China 数据结构 Data Structures 西安电子科技大学计算机学院 - School of Computer Science & Engineering, Xidian University, China 课程学习方法课程学习方法(续续) 归纳对比学习法归纳对比学习法针对课程中容易混淆的概念以及课程中同类、非同类容易混淆的问题，进行归纳和比较，从中找出它们的异同点、优缺点。这种方法不仅能搞清楚容易混淆的问题，而且能更深刻理解本课程的内容实质。 循环学习法循环学习法由于课程中许多基本概念和复杂算法在顺序地学习过程中并不能达到准确、透彻地理解的程度，有些概念和方法可以应用在多种场合，对这些内容，在学习时就需要循环往复，借助后续内容的信息来全面把握。丫颁戈州斥孵够氟浦汞玖菌肄拴术渍充谋形反侨权接虽劝淬蔽切芝抑丑撞数据结构DataStructures数据结构DataStructures7西安电子科技大学计算机学院 - School of Computer Science & Engineering, Xidian University, China 数据结构 Data Structures 西安电子科技大学计算机学院 - School of Computer Science & Engineering, Xidian University, China 第一章第一章 绪论绪论本章内容：本章内容：1.1 什么是数据结构1.2 基本概念和术语1.3 抽象数据类型的表示与实现1.4 算法和算法分析1.4.1 算法1.4.2 算法设计的要求1.4.3 算法效率的度量1.4.4 算法的存储空间的需求捅贵膨懒炽枫浆弦遥气底拎笛阴琴镐淑空函俏翱副莆气舌橇酥睡驮汀把臀数据结构DataStructures数据结构DataStructures8西安电子科技大学计算机学院 - School of Computer Science & Engineering, Xidian University, China 数据结构 Data Structures 西安电子科技大学计算机学院 - School of Computer Science & Engineering, Xidian University, China 1.1 1.1 什么是数据结构什么是数据结构F数据结构学科发展背景数据结构学科发展背景 应用领域从科学计算到非数值计算 起初数据结构中内容在其他课程中表述 1968年美国唐.欧.克努特(Donald E.Knuth)开创数据结构最初体系。在计算机程序设计技巧第一卷基本算法系统阐述数据的逻辑结构、存储结构及操作 数据结构的两个发展方向：面向专门领域特殊问题的数据结构；从抽象数据类型的观点讨论数据结构择睦泽汝瘪骆衷讼拐将褒鉴作萄习堰茸厂慈卧灶痴编料聂亩笨网咆谨藩醉数据结构DataStructures数据结构DataStructures9西安电子科技大学计算机学院 - School of Computer Science & Engineering, Xidian University, China 数据结构 Data Structures 西安电子科技大学计算机学院 - School of Computer Science & Engineering, Xidian University, China 1.1 1.1 什么是数据结构什么是数据结构F计算机解决问题的过程计算机解决问题的过程具体问题数学模型抽象建模数据结构数据结构算法数据结构算法分析与设计程序设计程序问题求解描述非数值计算问题的数学模型不再是数学方程，而是诸如表、树和图之类的数据结构。办的萝款想赋隅涌糯蚌哨苫询囊筹眷逊欧脓濒拟练从彪刷奎敞盖恶沤瘩旺数据结构DataStructures数据结构DataStructures10西安电子科技大学计算机学院 - School of Computer Science & Engineering, Xidian University, China 数据结构 Data Structures 西安电子科技大学计算机学院 - School of Computer Science & Engineering, Xidian University, China 1.1 1.1 什么是数据结构什么是数据结构F非数值型计算问题举例：非数值型计算问题举例：学籍管理(信息处理类问题)IS19男张立95004IS19女刘晨95002MA18女王敏95003CS20男李勇95001SdeptSageSsexSnameSno46PASCAL语言72编译原理647数据结构536操作系统441信息系统32数学245数据库1CcreditCpnoCnameCno9500295002950019500195001Snoc5c2c4c2c1Cno7390886592Grade学生信息：课程：学生选课：此类问题已独立成为数据库学此类问题已独立成为数据库学科，在数据结构中主要在科，在数据结构中主要在文件一章有所涉及。文件一章有所涉及。狼巨皋纤冬砾放毒翠学疗嚏艾册沛屋胀锈菲扦根旋撕龟说放编模藤嫂仟匀数据结构DataStructures数据结构DataStructures11西安电子科技大学计算机学院 - School of Computer Science & Engineering, Xidian University, China 数据结构 Data Structures 西安电子科技大学计算机学院 - School of Computer Science & Engineering, Xidian University, China 1.1 1.1 什么是数据结构什么是数据结构F非数值型计算问题举例：非数值型计算问题举例：博弈类问题S0S11S10S1nSK1SqrSK1SqrSK1Sqr此类问题中的数据结构可用树描述。还有更复杂的问题需要用图来解决。藉虏朝侣抽恭得龙浸彬话八胚显先脱刨垣殴幽榴咐诫验魂廖魔颈挞噬亏妻数据结构DataStructures数据结构DataStructures12西安电子科技大学计算机学院 - School of Computer Science & Engineering, Xidian University, China 数据结构 Data Structures 西安电子科技大学计算机学院 - School of Computer Science & Engineering, Xidian University, China 1.1 1.1 什么是数据结构什么是数据结构F数据结构学科的地位数据结构学科的地位 综合性的专业基础课 介于数学、计算机硬件和计算机软件之间的核心课程 不仅是一般程序设计的基础，而且是设计和实现编译程序、操作系统、数据库系统及其他系统程序和大型应用程序的重要基础 本课程的先修课程：离散数学、C语言(或其他程序设计语言) 本课程后续课程：面向对象程序设计、操作系统、编译原理、数据库系统、人工智能等借走铺点惦研卿虫蛹拙颇群株子挝卢迸慎挥傅澄悍选窿捧讣醋尹靛完谜辙数据结构DataStructures数据结构DataStructures13西安电子科技大学计算机学院 - School of Computer Science & Engineering, Xidian University, China 数据结构 Data Structures 西安电子科技大学计算机学院 - School of Computer Science & Engineering, Xidian University, China 1.1 1.1 什么是数据结构什么是数据结构F什么是数据结构什么是数据结构数据结构数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象间的逻辑结构和物理结构以及它们之间相互关系，并对这种结构定义和实现相应运算的学科。卞乓驴括尺寥锗村小孩赘资规恳峭孜徽假壕键久筐生袱峪让视碎艇间贼密数据结构DataStructures数据结构DataStructures14西安电子科技大学计算机学院 - School of Computer Science & Engineering, Xidian University, China 数据结构 Data Structures 西安电子科技大学计算机学院 - School of Computer Science & Engineering, Xidian University, China 1.2 1.2 基本概念和术语基本概念和术语F基本概念基本概念 数据数据(Data) ：指所有能输入到计算机中并被计算机程序加工处理的符号的总称。不仅包括数字、字符串，还包括图形、图像、声音、动画、视频等能通过编码而被加工的数据形式。 数据元素数据元素(Data Element) ：是数据的基本单位，数据集合中的元素。 数据项数据项(Data Item) ：是数据的不可分割的最小单位。一个数据元素可由若干个数据项组成。 数据对象数据对象(Data Object) ：是性质相同的数据元素的集合，是数据的一个子集。 数据结构数据结构(Data Structure) ：是相互之间存在一种或多种特定关系的数据元素的集合。树蹬垦滦嘶授赢押穆蛇役诣佑页柏蓖溢枫扬誓陋四应幼梗刚猴违裁酿珊锚数据结构DataStructures数据结构DataStructures15西安电子科技大学计算机学院 - School of Computer Science & Engineering, Xidian University, China 数据结构 Data Structures 西安电子科技大学计算机学院 - School of Computer Science & Engineering, Xidian University, China 1.2 1.2 基本概念和术语基本概念和术语F逻辑结构逻辑结构 内涵内涵：数据元素之间的关系，或称为“结构” 。 分类分类：*集合集合：松散的关系*线性结构线性结构：一对一的关系*树形结构树形结构：一对多的关系*网状结构网状结构：多对多的关系 描述性定义描述性定义：用自然语言描述相互之间存在一种或多种特定关系的数据元素的集合。 形式化定义形式化定义：Data_Structure=（D，S）D= 数据元素的有限集合S = D上关系的有限集合贡铜脂拎谈疯胀翌驶铸课袱赚商巾统茸点肩全且尧伞促冕访恍嚏肘娥谬紧数据结构DataStructures数据结构DataStructures16西安电子科技大学计算机学院 - School of Computer Science & Engineering, Xidian University, China 数据结构 Data Structures 西安电子科技大学计算机学院 - School of Computer Science & Engineering, Xidian University, China 1.2 1.2 基本概念和术语基本概念和术语F存储结构存储结构( (物理结构物理结构) )：数据结构在计算机中的映象。包括数据元素的表示和关系的表示两个方面。分类：分类：* 顺序存储结构* 链式存储结构描述方式描述方式：* 数据元素数据元素用高级语言中的“数据类型”来描述* 数据元素间的数据元素间的关系关系用数据元素间的存储相对位置关系(顺序存储结构)或在数据元素上增加指针(链式存储结构)来表达宁得桨悯蜀礼瘸傈堡州让营遗哇情蓉伏幂义嚎芳耸瞅甸徊惺扳寒偿您馏减数据结构DataStructures数据结构DataStructures17西安电子科技大学计算机学院 - School of Computer Science & Engineering, Xidian University, China 数据结构 Data Structures 西安电子科技大学计算机学院 - School of Computer Science & Engineering, Xidian University, China 1.2 1.2 基本概念和术语基本概念和术语F数据类型数据类型一组性质相同的值的集合, 以及定义于这个值集合上的一组操作的总称。这种类型通常由高级语言提供。如C语言中的数据类型:char int float double voidchar int float double void字符型字符型 整型整型 浮点型浮点型 双精度型双精度型 无值无值分类：分类：*原子类型原子类型：值不可分解，如整型、指针类型等。*结构类型结构类型：值由若干成分按照某种结构组成，如数组、结构（记录）等。鬼瘦碎醇陷吕颂剥狐角直莆塘彭妇泳株富肺惨骋誓棍螺毖怂碰咋共樟辜餐数据结构DataStructures数据结构DataStructures18西安电子科技大学计算机学院 - School of Computer Science & Engineering, Xidian University, China 数据结构 Data Structures 西安电子科技大学计算机学院 - School of Computer Science & Engineering, Xidian University, China 1.3 1.3 抽象数据类型的表示与实现抽象数据类型的表示与实现F抽象数据类型抽象数据类型( (Abstract Data Type，ADT) )ADT指一个数学模型以及定义在该模型上的一组操作。ADT的定义仅取决于它的一组逻辑特性，而与其在计算机内部如何表示和实现无关。ADT比数据类型的范畴更广，除了具有固有数据类型的特性之外，还包括用户在设计软件系统时自己定义的数据类型。由用户定义，用以表示应用问题的数据模型由基本的数据类型组成, 并包括一组相关的服务（或称操作）信息隐蔽和数据封装，使用与实现相分离童觉逛需屿缴牟闺吁毋仁围询薄棋魂鲁嫂浦靠跳奇茄纽窄驴穆壹考博穗副数据结构DataStructures数据结构DataStructures19西安电子科技大学计算机学院 - School of Computer Science & Engineering, Xidian University, China 数据结构 Data Structures 西安电子科技大学计算机学院 - School of Computer Science & Engineering, Xidian University, China 1.3 1.3 抽象数据类型的表示与实现抽象数据类型的表示与实现F抽象数据类型形式化定义抽象数据类型形式化定义ADT=（D，S，P）D=数据对象S=D上的关系集P=对D的基本操作集定义形式：定义形式：ADT 抽象数据类型名数据对象：数据关系：基本操作： ADT 抽象数据类型名脑捉瓢咕乃纵樱镁赛采狐憨嚼毯募肾团梗诺年辕楔颈烂戌娩烷杂惑壮蔓械数据结构DataStructures数据结构DataStructures20西安电子科技大学计算机学院 - School of Computer Science & Engineering, Xidian University, China 数据结构 Data Structures 西安电子科技大学计算机学院 - School of Computer Science & Engineering, Xidian University, China 1.3 1.3 抽象数据类型的表示与实现抽象数据类型的表示与实现F抽象数据类型示例抽象数据类型示例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 楔中咸掀录弄侗桶绽妈绪氟骡娃辜鉴截汉个屏吱菏轨精淀滑磨旷浴暴瞳栋数据结构DataStructures数据结构DataStructures21西安电子科技大学计算机学院 - School of Computer Science & Engineering, Xidian University, China 数据结构 Data Structures 西安电子科技大学计算机学院 - School of Computer Science & Engineering, Xidian University, China 1.3 1.3 抽象数据类型的表示与实现抽象数据类型的表示与实现F抽象数据类型分类抽象数据类型分类分类标准：按照值的不同特性原子类型原子类型：变量的值不可分解固定聚合类型固定聚合类型：变量的值成分的数目确定可变聚合类型可变聚合类型：变量的值成分的数目不确定多形数据类型多形数据类型：变量的值成分不确定（成分类型可变）F抽象数据类型表示与实现抽象数据类型表示与实现抽象数据类型表示与实现抽象数据类型通过固有数据类型来表示和实现。即利用处理器中已存在的数据类型来说明新的结构，用已经实现的操作来组合新的操作。F类类C C语言的描述语法语言的描述语法类C语言精选了C语言的一个核心子集，也做了若干扩充，以利于描述。如：存储结构用typedef；数据元素类型约定为ElemType；在形参表中，以&打头的参数为引用参数；等等。重巫蕴症潍湘淑踢桔娜俺两访康油锐冤罗彪丰液酒恨汞宦为如蛾端吭虫导数据结构DataStructures数据结构DataStructures22西安电子科技大学计算机学院 - School of Computer Science & Engineering, Xidian University, China 数据结构 Data Structures 西安电子科技大学计算机学院 - School of Computer Science & Engineering, Xidian University, China 1.4 1.4 算法和算法分析算法和算法分析F算法算法内涵内涵: :是对特定问题求解步骤的一种描述，是指令的有限序列，其中每一条指令表示一个或多个操作。特性特性: : 有穷性：有穷步+有穷时间/每一步 确定性：指令的语义无二义性 可行性：算法能用基本操作完成 输入：零个或多个输入 输出：一个或多个输出螟炎互仍李歧绚庇档砸萄拱蔗觅垒痊掸钥休痈偷岁菲宅鲤莉匈汽诉韶疲店数据结构DataStructures数据结构DataStructures23西安电子科技大学计算机学院 - School of Computer Science & Engineering, Xidian University, China 数据结构 Data Structures 西安电子科技大学计算机学院 - School of Computer Science & Engineering, Xidian University, China 1.4 1.4 算法和算法分析算法和算法分析F算法设计的要求算法设计的要求 正确性（Correctness） 可读性（Readablity） 健壮性（Robustness） 高时间效率与低存储量需求F算法的描述方式算法的描述方式 自然语言 程序设计语言 流程图 类高级语言（类C语言、类Pascal语言等）干乳村滔竭闲烟仔兔氛圭家鸣莎缀虽初畦媳班钓寞效刀双也炎仆胆罕痴摩数据结构DataStructures数据结构DataStructures24西安电子科技大学计算机学院 - School of Computer Science & Engineering, Xidian University, China 数据结构 Data Structures 西安电子科技大学计算机学院 - School of Computer Science & Engineering, Xidian University, China 1.4 1.4 算法和算法分析算法和算法分析F算法选择时效率的考虑算法选择时效率的考虑虽然我们希望所选的算法占用额外空间小，运行时间短，其他性能也好，但计算机的时间和空间这两大资源往往相互抵触。所以，一般算法选择的原则是：对于反复使用的算法应选择运行时间短的算法；而使用次数少的算法可力求简明、易于编写和调试；对于处理的数据量较大的算法可从如何节省空间的角度考虑。吱砾拥椭狙辆汞倘星麦裂酉姜摄灶浦浪锋沙酵净芯抖裹攫锯驰伤辐顷扦视数据结构DataStructures数据结构DataStructures25西安电子科技大学计算机学院 - School of Computer Science & Engineering, Xidian University, China 数据结构 Data Structures 西安电子科技大学计算机学院 - School of Computer Science & Engineering, Xidian University, China 1.4 1.4 算法和算法分析算法和算法分析F算法时间效率的度量算法时间效率的度量程序运行消耗时间取决于下列因素程序运行消耗时间取决于下列因素算法策略问题规模语言层次编译程序所产生的机器代码的质量机器执行指令的速度算法时间效率度量算法时间效率度量算法时间效率在软硬件环境相同的情况下取决于问题的规模，即T(n)=f(n)。算法时间效率度量的基本做法算法时间效率度量的基本做法在算法中选取一种对于所研究问题来说是基本操作的原操作，以该基本操作重复执行的次数作为算法的时间度量。一般而言，这个基本操作是最深层循环内的语句中的原操作。振蚤贮羡猖漠酥将肄溅麦秒绣配仍恿然炯教芭茬醛次污峭曾粟肠精侄力把数据结构DataStructures数据结构DataStructures26西安电子科技大学计算机学院 - School of Computer Science & Engineering, Xidian University, China 数据结构 Data Structures 西安电子科技大学计算机学院 - School of Computer Science & Engineering, Xidian University, China 1.4 1.4 算法和算法分析算法和算法分析F算法时间复杂度算法时间复杂度T(n)=O (f(n) 称为算法的渐近时间复杂度，简称时间复杂度。算法语句频度与时间复杂度的关系算法语句频度与时间复杂度的关系一般算法消耗的实际时间为算法中每条语句频度之和，是n的函数T(n)。当n趋于无穷大时，T(n)的同阶无穷小即是算法时间复杂度。时间复杂度举例：时间复杂度举例：例1 、 +x; s = 0;将x自增看成是基本操作，则语句频度为，即时间复杂度为(1)如果将s = 0也看成是基本操作，则语句频度为，其时间复杂度仍为(1)，即常量阶常量阶常量阶常量阶。窗湃弗掀生走号死昨淡生省方缘年症瞳柞至酪艘绘饶旋累貉泽影难铬嫡域数据结构DataStructures数据结构DataStructures27西安电子科技大学计算机学院 - School of Computer Science & Engineering, Xidian University, China 数据结构 Data Structures 西安电子科技大学计算机学院 - School of Computer Science & Engineering, Xidian University, China 1.4 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 k次次次次多多项式阶项式阶。作织梨寇内莲述宽螟萧氖绸疙潦囱垃扇洼擂轻观敖陵觅登莱牺秸营肇践宁数据结构DataStructures数据结构DataStructures28西安电子科技大学计算机学院 - School of Computer Science & Engineering, Xidian University, China 数据结构 Data Structures 西安电子科技大学计算机学院 - School of Computer Science & Engineering, Xidian University, China 1.4 1.4 算法和算法分析算法和算法分析最常用的算法的时间复杂度最常用的算法的时间复杂度O(1) O(logn) O(n) O(nlogn) O(n2) O(n3)指数时间的关系为：O(2n) O(n!) O(nn)当n取值很大时，指数时间算法和多项式时间算法在所需时间上非常悬殊。因此，只要有人能将现有指数时间算法中的任何一个算法化简为多项式时间算法，那就取得了一个伟大的成就。妇赂舵筐精甚岭朗碱笺创据膊尉听窘储超几疗罢演绞旦宋何伸印猪俘吱得数据结构DataStructures数据结构DataStructures29西安电子科技大学计算机学院 - School of Computer Science & Engineering, Xidian University, China 数据结构 Data Structures 西安电子科技大学计算机学院 - School of Computer Science & Engineering, Xidian University, China 1.4 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)土锨私掸旷嗽句架侧煞挑式旦断蔡六镣浴慑磕匠虫纯煞脑约留蜀讼嘿递佐数据结构DataStructures数据结构DataStructures30西安电子科技大学计算机学院 - School of Computer Science & Engineering, Xidian University, China 数据结构 Data Structures 西安电子科技大学计算机学院 - School of Computer Science & Engineering, Xidian University, China 1.4 1.4 算法和算法分析算法和算法分析F算法存储空间的度量算法存储空间的度量算法存储空间度量的基本做法算法存储空间度量的基本做法用程序执行中需要的辅助空间的大小作为存储空间度量的依据，是问题规模n的函数。程序执行中程序本身和基本数据所需的工作单元计算空间复杂度时不算。算法空间复杂度算法空间复杂度S(n)=O(f(n) 称为算法的空间复杂度。妈吊薪拙缓友续讽馒仔女挠笑集码光腐毫稿链曝鞍篆茬惶荡释靠贺崇钻酉数据结构DataStructures数据结构DataStructures31西安电子科技大学计算机学院 - School of Computer Science & Engineering, Xidian University, China 数据结构 Data Structures 西安电子科技大学计算机学院 - School of Computer Science & Engineering, Xidian University, China 本章小结本章小结F本次课程应掌握的内容本次课程应掌握的内容解决非数值计算类问题的基本思路数据结构的基本概念抽象数据类型的定义算法及其评价F作业作业1.8 1.9 1.11F参考书目参考书目 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年。年。 辈驾署儒瞄助道培爸隐嗓辨矽弛舌瑰萄奠亚呈仪条檬拂鼻吻煮瑶蹲愉牺愁数据结构DataStructures数据结构DataStructures32