hit数据结构PPT 1第1章绪论-2019

数据结构与算法DataStructuresandAlgorithm,黄虎杰hjhuang,唐纳德克努特（DonaldErvinKnuth）1938年12月7日出生于美国威斯康星州密尔沃基市；29岁提出“算法”(Algorithm)和“数据结构”(DataStructure)；1973年首创双向链表；著名算法Knuth-Bendix和Knuth-Morris-Pratt的发明者；排版系统TEX和METAFONT发明人。,1956年：进入俄亥俄州克利夫兰的凯斯理工学院（现并入凯斯西储大学）物理专业；1958年：改学数学，并从此与计算机结缘；1960年：Knuth被破例同时授予学士和硕士学位，进入加州理工学院数学系；1963年：取得博士学位,1966年副教授；1968年：斯坦福大学计算机科学系教授。开始撰写著名的计算机程序设计艺术系列图书；,计算机程序设计艺术1968年第一卷基本算法出版；1969年第二卷半数字化算法出版；1973年第三卷排序与搜索出版；目前第四卷组合算法已出版。,1971年：首届美国计算机协会格蕾丝赫柏奖；1973年：当选为美国科学艺术学院院士；1974年：图灵奖历史上最年轻的获奖者；1975年：当选为美国国家科学院院士。,计算机程序设计艺术一书与牛顿的自然哲学的数学原理等书一起，被评为“世界历史上最伟大的十种科学著作”之一。看了这部书后，再谈起编程序都会变得谦虚谨慎。比尔盖茨曾说：“如果你能读懂整套书的话，请给我发一份你的简历”。,教学安排：讲课学时40，实验学时16考核要求：期末考试占70%实验成绩占20%平时作业占10%,本课程在整个培养方案中的作用,2017年计算机专业数据结构与算法成绩,2017年软件工程专业数据结构与算法成绩,2018年计算机专业数据结构与算法成绩,2018年软件工程专业数据结构与算法成绩,数据结构与算法是计算机大类的专业基础课，既是对前序课程的深入和扩展，也是为将来更加深入地学习其他专业课程打下基础。通过本课程的学习，学生将基本掌握数据结构和算法基础知识，能够提高程序设计的质量；根据问题的性质，能够选择合理的数据结构，并对时间复杂性进行必要的控制，培养解决实际问题的能力。课程具体目标如下：课程目标1：能够根据算法的实际操作需求，选择、设计合理地数据结构，并能实现相关算法；课程目标2：能够对算法进行时间（空间）复杂性的分析；课程目标3：能够通过具体案例，学习并掌握基本数据结构（线性、树、图）的设计与使用；课程目标4：通过实验验收与实验报告的撰写，培养学生的书面表达能力和口头表达能力。,课程目标（2016版）,教材,数据结构与算法（第4版）编著廖明宏郭福顺张岩李秀坤高等教育出版社,参考资料,严蔚敏,吴伟民.数据结构(C语言版).清华大学出版社.2011.EllisHorawitz,SartajSahni,SusanAnderson-Freed著,李建中,张岩,李治军译.FundamentalsofDataStructuresinC.机械工业出版社.2006.SartajSahni著,汪诗林,孙晓东.DataStructures,Algorithms,andApplicationsinC+.机械工业出版社.2006.李秀坤,张岩,李治军,娄久.数据结构与算法实验教程.高等教育出版社.2009.,了解数据结构的基本概念、研究对象以及数据结构课程的发展历史，对数据结构与算法课程有一个宏观的认识；掌握贯穿全书的重要概念-抽象数据型，包括其概念的定义和实现方法，初步掌握抽象技术方法；了解算法、算法复杂性，掌握算法性能的评价方法；了解解决问题的一般过程和算法的逐步求精方法，掌握问题求解的基本过程和方法。,教学要求,1.1数据结构研究对象,计算机科学：信息在计算机内使用数据来表示,研究信息表示和信息处理。,数据：是用以描述客观事物的数值、字符，以及一切可以输入到计算机中并由计算机程序加以处理的符号的集合；数据的基本单位称为数据元素；数据的最小单位称为数据项。,数据对象：性质相同数据元素的集合,数据特征：数值、文本、多媒体、超媒体、实时、海量,数据类型?,高级语言中变量的取值范围和允许的操作,什么是数据？,大数据(bigdata),大数据可分成：大数据技术：解决大数据问题的技术和方法；大数据工程：大数据的规划建设运营管理的系统工程；大数据科学：关注大数据网络发展和运营过程中发现和验证大数据的规律及其与自然和社会活动之间的关系；大数据应用：解决实际问题。,大数据的4个“V”：Volume：数据体量巨大。从TB级别，跃升到PB级别；Variety：数据类型繁多。网络日志、视频、图片、地理位置信息等Value：价值密度低。以视频为例，连续不间断监控过程中，可能有用的数据仅仅有一两秒。Velocity：处理速度快，1秒定律。即要在秒级时间范围内给出分析结果,超出这个时间,数据就失去价值了。,数据结构：数据元素彼此之间抽象的相互关系，解决数据的存储和组织的方式，不涉及数据元素的具体内容。描述现实世界事物的数学模型及其操作在计算机中的表示和实现,数据结构分类：,线性表：(a1,a2,a3,ai-1,ai,ai+1an-1,an)线性结构线性表的一般概念、字符串、数组，广义表等,树：层次结构二叉树，树等,图：网状结构有向图、无向图等,结构：关系，组成整体的各部分的搭配和安排,国际象棋：每次需要考虑的合乎规则的着法平均只有35步“回合”，计算机预先分析7至8个回合的着法。若设为7个回合，则有超过1亿亿亿个不同的变化，经简化后，仍有500亿至600亿个变化。多分析一步，增加18亿个变化。,资料：下棋程序,围棋：分析7个回合的着法，则需要考虑超过200的14次方个变化，经简化后，仍有1000亿亿个变化。多分析一步，增加64万亿个变化。,根据计算机“深蓝”的速度，平均5分钟走一步！,根据计算机“深蓝”的速度，平均1.5年走一步！,BlueGene,共装有32个并行处理器，速度：2亿步棋/秒,深蓝vs卡斯帕罗夫:第一次1996年：2月10日17日，比分2:4，卡斯帕罗夫赢第二次1997年：5月3日11日，比分3.5:2.5双方先后共进行6局对弈：第一局：卡斯帕罗夫执白先行，经过3个多小时的苦战击败深蓝力拔头筹；第二局：深蓝却以凌厉的攻势和明显的优势战胜卡氏，扳回一局；第三、第四和第五局：双方下得异常激烈，鏖战数小时，平局；第六局：深蓝执白先行，一路强攻，仅用一个多小时，双方仅走了19步，就让卡氏俯首称臣，取得了决定性的胜利。,-1980年，台湾大学电机系毕业;-获得了电子工程学士学位;-美国卡内基梅隆大学博士;-曾在IBM工作;-现在微软亚洲研究院。,卡斯帕罗夫:他在观察电脑下棋时感觉电脑的决定有智慧及创意，是他所不能理解的。他亦认为电脑在棋局中可能有人类的帮助，因此要求重赛。IBM:拒绝，并把深蓝退役。2003年纪录片“游戏结束：卡斯巴罗夫与电脑”(GameOver:KasparovandtheMachine)。,许峰雄,深蓝,-1996年，美国IBM公司；-基于RS/6000SP设计；-AIX操作系统；-重1270公斤，32个微处理器；-每秒钟可以计算2亿步。,“神来之着”,阿尔法围棋（AlphaGo）是一款围棋人工智能程序，由英国伦敦的谷歌（Google）旗下DeepMind公司的戴维西尔弗、艾佳黄和戴密斯哈萨比斯与他们的团队开发，这个程序利用“价值网络”计算局面，用“策略网络”选择下子。2015年10月阿尔法围棋以5:0完胜欧洲围棋冠军、职业二段选手樊麾；2016年3月对战世界围棋冠军、职业九段选手李世石，并以4:1的总比分获胜。,面对AlphaGo碾压式的实力，19岁的“大魔王”柯杰：“AlphaGo实在下得太好。我担心的每一步棋他都会下，还下出我想不到的棋，我仔细慢慢思索，发现原来又是一步好棋。我只能猜出AlphaGo一半的棋，另一半我猜不到，就是差距，我和他差距实在太大。”,2017年5月23、25、27日,AlphaGo设计者：戴维西尔弗（DavidSilver），剑桥大学计算机科学学士，硕士，加拿大阿尔伯塔大学计算机科学博士。现为伦敦大学学院讲师及GoogleDeepMind研究员。艾佳黄（黄士杰，AjaHuang），台湾交通大学计算机科学学士，台湾师范大学计算机科学硕士和博士，加拿大阿尔伯塔大学计算机科学博士后。现为GoogleDeepMind研究员。,AlphaGo使用1820多块CPU及280多块GPU（GraphicProcessingUnit），据说，这次围棋对战分析只用了服务器总的百分之三十资源，其余的在空闲。,谷歌AlphaGo计算能力超IBM深蓝2.5-3万倍！,经过短短3天的自我训练，AlphaGoZero就强势打败了此前战胜李世石的旧版AlphaGo，战绩是100:0的。经过40天的自我训练，AlphaGoZero又打败了AlphaGoMaster版本。“Master”曾击败过世界顶尖的围棋选手，甚至包括世界排名第一的柯洁。,Master,补充1：适用于并行计算并发数据结构或多线程数据结构,设计并发数据结构（互斥锁）,设计不使用互斥锁的并发数据结构,以队列为例：并发队列并发阻塞队列有超时限制的并发阻塞队列有大小限制的并发阻塞队列有操作限制的并发阻塞队列,如何设计支持并发访问的数据结构？设计可以基于互斥锁，也可以是无锁的。无论哪种方式，要考虑的问题不仅仅是这些数据结构的基本功能具体来说，必须一直记住线程会争夺执行权，要考虑线程重新执行时如何恢复操作。,试图从没有数据的队列读取数据，仅仅会抛出异常并继续执行。但是，这种做法不总是我们想要的，读线程很可能希望等待，直到有数据时为止。这种队列称为阻塞的队列。,补充2：适用于分布式系统分布式Hash表或者分布式B+树,Hash算法：模N（N为机器数）Hash或者一致性Hash,模N哈希的主要问题：机器上下线时机器数变化导致所有的数据都需要重新分布，一致性Hash用来解决这个问题。,分布式Hash存储系统由于只支持随机读取，一般用选择相对较好的磁盘，分布式B+树存储系统同时支持随机读取和顺序扫描，当用来支持使用模式主要为顺序扫描的应用时，可以选择相对较差的磁盘，比如SATA盘。,Hash空间组织成一个环，环上相邻节点包含的数据构成一个桶；比如Hash空间为A,B,C，那么有A,B,B,C,以及C,A三个桶；每个桶内的数据结构为Log-StructuredHashTable；当然，可根据需要修改每个桶的单机数据结构；桶是负载均衡和任务调度的基本单元；每个桶存放3个副本。,1.1数据结构研究对象,1、数据结构研究方法,逻辑结构：对操作对象的一种数学描述，或从操作对象中抽象出的数学模型，用以描述数据元素之间的逻辑关系，与存储方式无关。,物理结构：数据结构在计算机中的表示或映象，逻辑结构的存储方式。又称存储结构，分为顺序映象和非顺序映象；或称顺序存储结构和链式存储结构；,计算机解题过程：,2、数据结构研究的范畴,程序设计：为计算机处理问题编制一组指令集算法：怎么处理的策略数据结构：问题的数学模型,程序设计、算法、数据结构,1.2数据结构发展概况,数据结构侧重解决非数值问题,FORTRAN,ALGOL等高级语言是以程序为中心侧重于解决数值问题；,LISP,SONBOL表或串处理语言是以数据为中心侧重于解决非数值问题；,1968年以前，数据结构的内容大多包含在形如表、树、图论、集合代数论、格、关系等方面。1968年开始，“数据结构”逐渐开始成为独立的一门课程；,作为一门专业基础课，“数据结构”是计算机专业的核心课程之一，是其他专业课的基础。是数学、硬件和软件三者的交叉，很受重视。,从PASCAL语言开始逐渐形成二者结合；,知识结构,数据结构所处的地位,1.3抽象数据型AbstractDataTypes（ADT）,软件系统由数据结构、操作过程和控制机能三者组成，软件设计是对三者的抽象过程，即数据抽象、过程抽象和控制抽象。,【定义】抽象数据型是一个数学模型和在该模型上定义的操作的集合。,ADT特点：降低了软件设计的复杂性；提高了程序的可读性和可维护性；程序的正确性容易保证。,抽象：从众多事物中舍弃个别的、非本质的属性，抽出共同的、本质性的特征。是形成概念的重要手段，其目的是使复杂度降低。,线性表LIST=(D,R)D=ai|aiElementSet,i=1,2,n,n0R=HH=|ai-1,aiD,i=2,n,操作：设L的型为LIST线性表实例，x的型为ElementType的元素实例，p为位置变量。所有操作描述为：Insert(x,p,L)；Locate(x,L)；Retrieve(p,L)；Delete(p,L)；Previous(p,L),Next(p,L)；MakeNull(L)；First(L)；,数学模型,【例1-1】定义任意线性表类型为LIST，其中元素类型为Elementtype，设有线性表L，函数Purge用以删除线性表L中所有重复出现的元素。,VoidPurge(LISTL)Positionp,q;p=First(L);while(p!=End(L)q=Next(p,L);while(q!=End(L)if(same(Retrieve(p,L),Retrieve(q,L)Delete(q,L);elseq=Next(q,L);p=Next(p,L);,【例1-2】假设利用两个线性表LA和LB分别表示两个集合，设计算法求一个新的集合A=AB。,VoidUnion(LIST,抽象数据型的规格描述,完整性：反映所定义的抽象数据型的全部特征；统一性：前后协调，不自相矛盾；通用性：适用于尽量广泛的对象；不依赖性：不依赖于程序设计语言，可以用任意的语言来描述；,规格描述的两个方面:语法和语义,语法：给出操作的名称、I/O参数的数目和类型；语义：由一组等式组成，定义各种操作的功能及相互间的关系；,例如：抽象数据型栈(Stack),【定义】栈是一个后进先出（LIFO）的线性表，所有插入、删除操作是在表的一端（栈顶）进行。,聚集数组，链表(结构体、记录)，文件,栈(Stack)示意图,规格描述,给出操作的名称,I/O参数的数目和类型,定义各种操作的功能及相互间的关系,1.4数据结构与程序设计,Algorithms+DataStructures=Programs算法+数据结构=程序设计,系统程序设计导论（SystematicProgramming：AnIntroduction，Prentice-Hall，1973；算法+数据结构=程序（Algorithms+DataStructures=Programs，Prentice-Hall，1976）；算法和数据结构（AlgorithmsandDataStructures，Prentice-Hall，1986）；Modula-2程序设计（ProgramminginModula-2，Springer，1988，第4版）。PASCAL用户手册和报告：ISOPASCAL标准（PASCALUserManualandReport：ISOPASCALStandard，Springer，1991）；Oberon计划：操作系统和编译器的设计（ProjectOberon：theDesignofanOperatingSystemandCompiler，ACMPr.，1992）；Oberon程序设计：超越Pascal和Modula（ProgramminginOberon：StepsbeyondPascalandModula，ACMPr.，1922）；数字电路设计教材（DigitalCircuitDesignforComputerScienceStudents：AnIntroductoryTextbook，Springer，1995）。,尼古拉斯沃斯（NiklausWirth，1934年2月15日）；生于瑞士温特图尔，瑞士计算机科学家；苏黎世工学院获得学士学位，美国加州大学伯克利分校获得博士学位；代表性著作有：,获奖：1984年：获图灵奖（ACM）；1987年：获计算机科学教育杰出贡献奖（ACM）；1983年：EmanualPiore奖（IEEE）；1988年：计算机先驱奖（IEEE）；1992年：加州大学伯克利分校命名沃斯为“杰出校友”。,1984,问题总是先于算法,程序设计的四个里程碑：子程序、高级语言、结构程序设计、面向对象(OOP),结构化程序设计：限制使用GOTO语句（基于三种基本结构）；逐步求精的设计方法；自顶向下的设计、编码与调试；主程序员组的组织形式；,程序结构基于数据结构的根源,1.4数据结构与程序设计,“我们对复杂性问题的最重要的办法是抽象，对一个复杂问题，不应马上用计算机指令、数字与逻辑字来表示，而应该用较为自然的抽象语句来表示，从而得出抽象程序。抽象程序对抽象的数据进行某些特定的运算并用某些合适的记号(可能是自然语言)来表示。,基于数据结构的jackson设计方法：研究问题环境，确定要处理的数据结构；基于数据结构，形成程序结构（骨架）；用初等操作来定义要完成的任务，并分配初等操作。,“从上到下，逐步求精”,对抽象程序作进一步的分解，并进入下一层的抽象，这样的精细化过程一直进行下去，直到程序能被计算机接受为止。此时的程序可能是某种高级语言或机器指令书写的。”N.wirth,算法（Algorithm）：是对特定问题求解步骤的一种描述，它是指令（规则）的有限序列，其中每一条指令表示一个或多个操作。,算法是在有限步骤内求解某一问题所使用的一组定义明确的规则；通俗点说,就是计算机解题的过程；在这个过程中，无论是形成解题思路还是编写程序,都是在实施某种算法。前者是推理实现的算法，后者是操作实现的算法。,1.5算法描述与算法分析,早期的语言学家：algiros(费力的)+arithmos(数字)组合派生而成，但另一些人认为这个词是从“喀斯迪尔国王Algor”派生而来的；数学史学家发现了algorism(算术)一词的真实起源：它来源于著名的PersianTextbook(波斯教科书)的作者的名字AbuJafarMohammedibnMsal-Khowrizm（约公元前825年）意思是“Jafar的父亲，Mohammed和Ms的儿子，Khowrizm的本地人”。Khowrizm是前苏联XBA(基发)的小城镇。Al-Khowrizm写了著名的书Kitabaljabrwal-muqabala(复原和化简的规则)；另一个词，“algebra”(代数)，是从他的书的标题引出来的；牛津英语字典:这个词是由于同arithmetic(算术)相混淆而形成的错拼词。由algorism又变成algorithm；,德文数学词典VollstandigesMathematischesLexicon(数学大全辞典)，给出了Algorithmus(算法)一词的如下定义：“在这个名称之下，组合了四种类型的算术计算的概念，即加法、乘法、减法、除法”。拉顶短语algorithmusinfinitesimalis(无限小方法)，在当时就用来表示Leibnitz(莱布尼兹)所发明的以无限小量进行计算的微积分方法；1950年左右，algorithm一词经常地同欧几里德算法(Euclidsalgorithm)联系在一起。这个算法就是在欧几里德的几何原本中所阐述的求两个数的最大公约数的过程(即辗转相除法)。,资料：Algorithm与Logarithm,(1175-1250）意大利数学家,从Fibonacci数列开始,神奇的数列！,Fibonacci:0,1,1,2,3,5,8,13,21,34,55,89,.,0如果n=01如果n=1Fn-1+Fn-2如果n1,Fibonacci数列的生成规则：Fn=,Fn20.694n,Fibonacci数增长的速度几乎与2的幂增长的速度相当!,F30超过了100万，F100已经达到21位数字！F200是多少？谁能告诉Fibonacci?,Longintfib1(intn)if(n=0)return(0);if(n=1)return(1);return(fib1(n-1)+fib(n-2);,fib1(200)执行的基本操作次数:T(200)=T(199)+T(198)+3=2138,以每秒33.86千万亿次的计算机测算Fib1(200)的计算时间=282秒,另外一个计算方法：longintfib2(intn)longintF200,i;if(n=0)return(0);F0=0；F1=1;for(i=2;i1.11*256年,Fn20.694n(1.6)n,计算Fn+1的时间是计算Fn的1.6倍，Fn+1=1.6Fn摩尔定律(Mooreslow)：计算机的运算速度每年增长约1.6倍。,“神威太湖之光”击败的是霸占榜首3年的“天河2号”。“神威太湖之光”运算速度达到93petaflop（每秒运算一千万亿次），理论最高速达125.4petaflops。这一数值约为“天河2号”的两倍。,2016年6月20日德国法兰克福国际超级计算机大会（ISC）公布了新一期世界计算机500强榜单，我国最新的超级计算机“神威太湖之光”登顶。最受关注的是，“神威太湖之光”实现了核心处理器的全国产化。,超算2018,新一期全球超级计算机500强榜单2018年6月25日发布，美国超级计算机“顶点”超过中国的“神威太湖之光”名列第一，这是美国超级计算机多年后重回榜首。,美国能源部下属橡树岭国家实验室的超算“顶点”，浮点运算速度为每秒12.23亿亿次，峰值接近每秒18.77亿亿次。,排名第二的是曾4次蝉联冠军的中国超算“神威太湖之光”，其浮点运算速度没有变化，仍维持在每秒9.3亿亿次。,随后排在第三至五位的超算依次是美国能源部下属劳伦斯利弗莫尔国家实验室的“山脊”、中国超算“天河二号”、日本超算“人工智能桥接云基础设施”（ABCI）。,5月在天津举办的第二届世界智能大会上，中国国家超算天津中心对外展示了我国新一代百亿亿次超级计算机“天河三号”原型机，有望在2020年研制成功并重回超算榜首。,“好”的算法的标准：正确性，算法能满足具体问题的需求；可读性，首先方便阅读与交流，其次才是机器执行；健壮性，输入错误时，能作出反应，避免异常出错；效率与低存储量要求。,算法的特征：有穷性、确定性、输入、输出、能行性,算法效率衡量和准则：事后统计法必须执行程序，可能有其他因素掩盖算法的本质；事前分析估算法,对算法“正确性”的要求：不含语法错误；对于几组输入数据能得到满足要求的结果；对精心选择苛刻并带有刁难的数据能得到满足要求的结果；对于一切合法的输入均得到满足要求的结果；,算法描述：自然语言；程序设计语言；类语言*；,关于本书采用的类语言描述：结构类型说明；输入输出约定(cinv,coutv)；new和delete；引入引用类型；其他；,影响算法执行的因素：算法实现后所消耗的时间*；算法实现后所占存储空间的大小*；算法是否易读、易移植等等其它问题。,影响时间特性的五个因素：算法选用的策略；程序运行时输入数据的总量，即问题的规模；对源程序编译所需的时间，产生机器代码的质量；计算机执行每条指令所需的时间/速度；程序中指令重复执行的次数*。,【定义】语句频度：语句重复执行的次数。,程序运行时间,渐近时间复杂度（时间复杂度）T（n）,算法中基本操作重复执行的次数是问题规模n的某个函数f（n），算法的时间度量记作：T（n）=O（f（n）它表示随问题规模n的增大，算法执行时间的增长率和f（n）的增长率相同。,渐近空间复杂度（空间复杂度）S（n）,S（n）=O（g（n）,运算法则：设：T1(n)=O(f(n)，T2(n)=O(g(n)加法规则：T1(n)+T2(n)=O(maxf(n),g(n)乘法规则：T1(n)T2(n)=O(f(n)g(n),设：,T(x)：取变量或常量x之值所消耗时间T(.V)：取变量V之地址所消耗的时间T(=)：赋值所消耗时间T()：执行基本运算所耗时间T(call/return)：执行函数调用和返回所耗时间T(par)：将参数par传给函数所消耗时间,(1)表达式和赋值语句exp:=常数|变量|F-name(e1,e2,em)|(expexp)T(v=exp)=T(.v)+T(=)+T(exp)T(expexp)=T(exp)+T()+T(exp)T(F-name(e1,e2,em)=T(call/return)+mT(par)+T(F-body)例：T(c=a+b)=T(.c)+T(=)+T(a)+T(+)+T(b)相应的汇编程序为：loadainR1loadbinR2addR2toR1loadcinR2storeR1inR2,通常取O(1),(2)语句序列T(s1,s2,sk)=maxT(s1),T(s2),T(sk)(3)条件语句T(if(B)s1elses2)=T(B)+T(else)+maxT(s1),T(s2)通常取T(B)+T(else)=O(1)T(