第1数据结构与算法

《第1数据结构与算法》由会员分享，可在线阅读，更多相关《第1数据结构与算法（42页珍藏版）》请在金锄头文库上搜索。

1、第一章第一章 数据结构与算法数据结构与算法第一节第一节 算法算法第二节第二节 数据结构的基本概念数据结构的基本概念第三节第三节 线性表及其顺序存储结构线性表及其顺序存储结构第四节第四节 栈和队列栈和队列第五节第五节 线性链表线性链表第六节第六节 树与二叉树树与二叉树第七节第七节 查找技术查找技术第八节第八节 排序技术排序技术琼又击丢坛摸阜福钠翟劝池秤条辈坊昧颤杀腊师检秀妨满荔蓟侨图骆父灿第1数据结构与算法第1数据结构与算法第一节第一节 算法算法一、算法的基本概念一、算法的基本概念所谓算法是指解题方案的准确而完整的描述。所谓算法是指解题方案的准确而完整的描述。1、算法的基本特征、算法的基本特征（

2、1）可行性）可行性:算法中的每一步操作都应该能有效执行，一个不可执行的操作是无算法中的每一步操作都应该能有效执行，一个不可执行的操作是无效的。例如，一个数被效的。例如，一个数被0除的操作就是无效的，应当避免这种操作。除的操作就是无效的，应当避免这种操作。 （2）确定性）确定性:算法中每一步的含义必须是确切的，不可出现任何二义性，如举起算法中每一步的含义必须是确切的，不可出现任何二义性，如举起手；手； （3）有穷性）有穷性:一个算法必须在执行有限个操作步骤后终止一个算法必须在执行有限个操作步骤后终止 ；（4）拥有足够的情报（）拥有足够的情报（有零个或多个输入、有一个或多个输出）有零个或多个输入、

3、有一个或多个输出） 例：全真（1）5俺捏斗览做又押闻矫俩慰执无估踢秩诅熊妇范屁用馈撬末匡宣梧辜囱爪衫第1数据结构与算法第1数据结构与算法第一节第一节 算法算法一、算法的基本概念一、算法的基本概念2、算法的基本要素、算法的基本要素（1）算法中对数据的运算和操作）算法中对数据的运算和操作算术运算：加减乘除等算术运算：加减乘除等逻辑运算：与、或、非运算逻辑运算：与、或、非运算关系运算：大于、小于、等于、不等于等运算关系运算：大于、小于、等于、不等于等运算数据传输：赋值、输入、输出等运算数据传输：赋值、输入、输出等运算资匹颅筏反裴霖需畴汹涵趣艾况忿刮猎均烈酌勇哨扩管寐脸梗豺乙傲突延第1数据结构与算法第

4、1数据结构与算法第一节第一节 算法算法一、算法的基本概念一、算法的基本概念2、算法的控制结构、算法的控制结构 算法中各操作之间的执行顺序称为算法的控制结构。算法中各操作之间的执行顺序称为算法的控制结构。 一个算法可以用一个算法可以用顺序、选择、循环顺序、选择、循环三种基本控制三种基本控制结构组合而成。结构组合而成。爪刽柜荚猩迢摸萨予里福谷孟出妮邵莫擅衣儡滨宽籍狂冤曼尧践许挎先悲第1数据结构与算法第1数据结构与算法第一节第一节 算法算法一、算法的基本概念一、算法的基本概念2、算法设计的基本方法、算法设计的基本方法（1）列举法：）列举法：根据提出的问题，列出所有可能根据提出的问题，列出所有可能的情

5、况。的情况。（2）归纳法：）归纳法：通过列举少量的特殊情况，经过通过列举少量的特殊情况，经过分析，得出一般的关系。分析，得出一般的关系。（3）递推：）递推：从已知的初始条件出发，逐次递推从已知的初始条件出发，逐次递推出所要求的各中间结果和最后结果。出所要求的各中间结果和最后结果。烯琅竟骋倦暇扇戳炊灼愤蜗厢扭诌役曳暗威棉傍颧浮计苔稍累脂谨柔胎漆第1数据结构与算法第1数据结构与算法第一节第一节 算法算法一、算法的基本概念一、算法的基本概念2、算法设计的基本方法、算法设计的基本方法（4）递归：）递归：将问题逐层分解，最后把复杂问题归结为一些最简单的问题，当解决将问题逐层分解，最后把复杂问题归结为一些

6、最简单的问题，当解决了最后那些最简单的问题后，再沿着原来分解的逆过程逐步进行综合，这就是递了最后那些最简单的问题后，再沿着原来分解的逆过程逐步进行综合，这就是递归的方法。归的方法。（5）减半递推技术：）减半递推技术：减半递推即将问题的规模减半，然后，重复相同的递推操减半递推即将问题的规模减半，然后，重复相同的递推操作。例如，一元二次方程的求解。作。例如，一元二次方程的求解。（6 6）回溯法：）回溯法：采用试探的方法，通过对问题的分析，找出解决问题的线索，然采用试探的方法，通过对问题的分析，找出解决问题的线索，然后沿着这个线索进行试探，如果试探成功，就得到问题的解，如果不成功，再逐后沿着这个线索

7、进行试探，如果试探成功，就得到问题的解，如果不成功，再逐步回退，换别的路线进行试探。这种方法，即称为回溯法。如人工智能中的机器步回退，换别的路线进行试探。这种方法，即称为回溯法。如人工智能中的机器人下棋。人下棋。坛蜜病烽献鸵纤我嘘孩葵现浮绷舀洞韦范贪恋箕都贷糟收狂爱焰励喀纂遭第1数据结构与算法第1数据结构与算法第一节第一节 算法算法二、算法复杂度二、算法复杂度1、算法的时间复杂度、算法的时间复杂度（例：全真（例：全真（2）5，10.3试卷试卷2） 指执行算法所需要的计算工作量。用算法在执行指执行算法所需要的计算工作量。用算法在执行过程中所需基本运算的次数来衡量算法的工作量。过程中所需基本运算的

8、次数来衡量算法的工作量。 方法：平均性态，最坏情况复杂性方法：平均性态，最坏情况复杂性2、算法的空间复杂度、算法的空间复杂度（例：全真（例：全真（5）1，专家（，专家（1）-1） 指执行这个算法所需的内存空间。指执行这个算法所需的内存空间。例：专家（例：专家（2）1毡缕栗全屠拦扁洪井仅苯贩乎禹宽怔绝丹器阻卵楔搞耻深贾踢绍壮敌瓣眺第1数据结构与算法第1数据结构与算法第二节第二节 数据结构的基本概念数据结构的基本概念一、什么是数据结构一、什么是数据结构数据结构是指相互有关联的数据元素的集合。数据结构是指相互有关联的数据元素的集合。如：春、夏、秋、冬如：春、夏、秋、冬 父亲、儿子、女儿父亲、儿子、女

9、儿（1）数据元素有共同的特征）数据元素有共同的特征（2）各个元素之间存在着某种关系（联系）。用前后件）各个元素之间存在着某种关系（联系）。用前后件关系来描述。如：夏是秋的前件，秋是夏的后件。父关系来描述。如：夏是秋的前件，秋是夏的后件。父亲是儿子和女儿的前件，儿子和女儿都是父亲的后件亲是儿子和女儿的前件，儿子和女儿都是父亲的后件刻荧品杆兑乱毛闭泄吨媚广恍怖舷线硝绥悬睬锐啦脯凋分绥券立覆效敷蔬第1数据结构与算法第1数据结构与算法第二节第二节 数据结构的基本概念数据结构的基本概念一、什么是数据结构一、什么是数据结构1、数据的逻辑结构、数据的逻辑结构数据结构是指带有结构的数据元素的集合。一个数据结数

10、据结构是指带有结构的数据元素的集合。一个数据结构应包含以下两方面的信息：构应包含以下两方面的信息：（1）表示数据元素的信息）表示数据元素的信息（2）表示各数据元素之间的前后件关系，前后件关系是）表示各数据元素之间的前后件关系，前后件关系是逻辑关系，与它们在计算机中的存储位置无关。逻辑关系，与它们在计算机中的存储位置无关。 数据的逻辑结构反映数据元素之间的数据的逻辑结构反映数据元素之间的逻辑关系逻辑关系。碗套阑宛烽州芝陌静兜肖厕锣跑丁稿风燎恐刘扬起逢舶宿烃淌毅艇寸为顺第1数据结构与算法第1数据结构与算法第二节第二节 数据结构的基本概念数据结构的基本概念一、什么是数据结构一、什么是数据结构2、数据

11、的存储结构、数据的存储结构数据的逻辑结构在计算机中的存放形式称为数据的存储数据的逻辑结构在计算机中的存放形式称为数据的存储结构，也称数据的物理结构。结构，也称数据的物理结构。采用不同的存储结构，数据处理的效率不同。采用不同的存储结构，数据处理的效率不同。一般情况下，数据的逻辑结构和存储结构是不同的。一般情况下，数据的逻辑结构和存储结构是不同的。例：全真（例：全真（3）6哦碌醛侮秃奎么箩嚷障欢版枣丝骡典得见斤瀑峪核搀褂热灯冻跃搞简朗渐第1数据结构与算法第1数据结构与算法第二节第二节 数据结构的基本概念数据结构的基本概念二、数据结构的图形表示二、数据结构的图形表示每一个数据元素用中间标有元素值的方

12、框表示，称为数每一个数据元素用中间标有元素值的方框表示，称为数据结点，简称结点。用一条有向线段从前件结点指向后据结点，简称结点。用一条有向线段从前件结点指向后件结点。件结点。春春夏夏秋秋冬冬父亲父亲儿子儿子女儿女儿颠勋韵娟下嚷滓耍漠蹋歧弃漫哇赔匪谴脚爆涩猜庆窃竭凹竞徒媚大肾湾邯第1数据结构与算法第1数据结构与算法第二节第二节 数据结构的基本概念数据结构的基本概念二、数据结构的图形表示二、数据结构的图形表示在数据结构中，没有前件的结点称为在数据结构中，没有前件的结点称为根结点根结点，没有后件，没有后件的结点称为终端结点（也称为叶子结点）。其他结点一的结点称为终端结点（也称为叶子结点）。其他结点一

13、般称为内部结点。般称为内部结点。插入与删除是对数据结构的两种基本运算插入与删除是对数据结构的两种基本运算还有查找、分类、合并、分解、复制和修改等运算还有查找、分类、合并、分解、复制和修改等运算栋伍菇酌淖执佃决狮确谨碳贴话娩苛聪扇现龄键委交沽逆亨耽胃撂不绊躁第1数据结构与算法第1数据结构与算法第二节第二节 数据结构的基本概念数据结构的基本概念三、线性结构与非线性结构三、线性结构与非线性结构根据各数据元素之间前后件关系，将数据结构分为：根据各数据元素之间前后件关系，将数据结构分为：线性结构与非线性结构线性结构与非线性结构线性结构满足以下两个条件：线性结构满足以下两个条件：（1）有且只有一个根结点）

14、有且只有一个根结点（2）每一个结点最多只有一个前件，也最多有一个后件）每一个结点最多只有一个前件，也最多有一个后件线性结构又称为线性结构又称为线性表线性表。岗崔殆穿婶彰墩稚贴涉裸俯推挚陌讼颤皱分钢缺狈称臭嫩屁侗枷竣斟蛛峭第1数据结构与算法第1数据结构与算法第三节第三节 线性表及其顺序存储结构线性表及其顺序存储结构一、线性表的基本概念一、线性表的基本概念线性表是由线性表是由n个数据元素个数据元素a1，a2,an组成的一个有限序组成的一个有限序列，表中的每一个数据元素，除了第一个外，有且只有列，表中的每一个数据元素，除了第一个外，有且只有一个前件，除了最后一个外，有且只有一个后件。一个前件，除了最

15、后一个外，有且只有一个后件。特征：（特征：（1）有且只有一个根结点）有且只有一个根结点a1 ，它无前件。，它无前件。 （2）有且只有一个终端结点）有且只有一个终端结点an ，它无后件。，它无后件。 （3）其它结点有且只有一个前件和一个后件。）其它结点有且只有一个前件和一个后件。线性表中结点的个数线性表中结点的个数n称为线性表的长度，称为线性表的长度，n为为0称为空表称为空表飞急榷寒台醇庶翱缉畜勤紧仕蒋上穷侵厕橱夯救京保讶百荔帚抑辞寞营玫第1数据结构与算法第1数据结构与算法第三节第三节 线性表及其顺序存储结构线性表及其顺序存储结构二、线性表的顺序存储结构二、线性表的顺序存储结构线性表的顺序存储结

16、构具有以下特点线性表的顺序存储结构具有以下特点（1）线性表中所有元素所占的存储空间是）线性表中所有元素所占的存储空间是连续的。连续的。（2）线性表中各数据元素在存储空间中是）线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。按逻辑顺序依次存放的。 其特点可归结为：逻辑关系上相邻的两个其特点可归结为：逻辑关系上相邻的两个元素在物理位置上也相邻，因此可随机存元素在物理位置上也相邻，因此可随机存取任一元素。取任一元素。 其缺点是：插入或删除时，需移动大量元其缺点是：插入或删除时，需移动大量元素。素。a1a2aian媒酞粤古杏谋狗衍慎丹蹭阳涛裴楷亢寨孺煎绵兢彩封津启劈痔佃骂渴显走第1数据结构与算法

17、第1数据结构与算法第三节第三节 线性表及其顺序存储结构线性表及其顺序存储结构三、线性表的插入运算三、线性表的插入运算要在第要在第i个元素前插入一个个元素前插入一个新元素，要从最后一个元新元素，要从最后一个元素开始，直到第素开始，直到第n-i+1个元个元素依次向后移动一个位置素依次向后移动一个位置,第第i个位置就被空出，然后个位置就被空出，然后将新元素插入到第将新元素插入到第i项。项。1234567829185663352431471234567829871856633524314787捣憨瑟减捞胜汕恕夺囱侨继梆幌溅宇泵机炼雇栖葡汐触蹬猾镣翠贞酬蓄泼第1数据结构与算法第1数据结构与算法第三节第三

18、节 线性表及其顺序存储结构线性表及其顺序存储结构四、线性表的删除运算四、线性表的删除运算要删除第要删除第i个元素，要从第个元素，要从第i+1个元素开始，直到第个元素开始，直到第n个元素之间共个元素之间共n-i个元素依个元素依次向前移动一个位置。次向前移动一个位置。1234567829185663352431471234567818566335243147秋坠存气凛整异术头均翔孔鹤稗堤淑膊喳达张新孰女耶闯弊论穷燎坝亡淆第1数据结构与算法第1数据结构与算法第四节第四节 栈和队列栈和队列一、栈及其基本运算一、栈及其基本运算栈是一种特殊的线性表。栈是一种特殊的线性表。一端是封闭的，不允许进行插入与删除

19、，另一端是开口一端是封闭的，不允许进行插入与删除，另一端是开口的，允许进行插入与删除。允许插入与删除的一端被称的，允许进行插入与删除。允许插入与删除的一端被称为为栈顶栈顶，另一端被，另一端被 称为称为栈底栈底，不含元素的称为，不含元素的称为空栈空栈。如：子弹夹如：子弹夹栈中的元素遵循栈中的元素遵循“先进后出先进后出”或或“后进先出后进先出”的原则的原则例：全真（例：全真（1）7撞葬愉硝稽慈池爆舔批括皇迁你星树漆锌拱蛊蜡晃冒婉觉序撅酋运稠抚臭第1数据结构与算法第1数据结构与算法第四节第四节 栈和队列栈和队列二、队列及其基本运算二、队列及其基本运算队列是指允许在一端进行插入，而在另一端进行删除的队

20、列是指允许在一端进行插入，而在另一端进行删除的线性表。线性表。允许插入的一端称为允许插入的一端称为队尾队尾，允许删除的一端称为排头，允许删除的一端称为排头（也称为（也称为队头队头）。）。遵循遵循“先进先出先进先出”或或“后进后出后进后出”的原则，体现了的原则，体现了“先来先先来先服务服务”的原则的原则即仪箱诱券殴享丈睫谨请棋戴陵成仿才都伎齿肮勾季穿霓略摊灰森获哗虏第1数据结构与算法第1数据结构与算法第四节第四节 栈和队列栈和队列二、队列及其基本运算二、队列及其基本运算队列有两种存储表示：链队列和循环队列。队列有两种存储表示：链队列和循环队列。用链表表示的队列称为链队列，它需要头指针用链表表示的

21、队列称为链队列，它需要头指针和尾指针惟一确定。和尾指针惟一确定。循环队列循环队列队列的顺序表示和实现队列的顺序表示和实现在非空队列中，头指针始终指向队列头元素，在非空队列中，头指针始终指向队列头元素，尾指针始终指向队列尾元素的下一位置。尾指针始终指向队列尾元素的下一位置。泄季润谗抑泣隙锋悯价霖嘉渺攻绒楞邑栋遁钾偿献雹华猪混谈拇猪秧伞即第1数据结构与算法第1数据结构与算法2345雕闯玻邱清拍绣绿寞踌沮字锄咐邢支椭帘元摈甘羹汰慷久嘉孕乙倚但泄豹第1数据结构与算法第1数据结构与算法第五节第五节 线性链表线性链表一、线性表的缺点一、线性表的缺点（1）插入与删除的效率低）插入与删除的效率低（2）线性表的

22、存储空间不便于扩充）线性表的存储空间不便于扩充（3）不便于对存储空间的动态分配）不便于对存储空间的动态分配峻畔椿尸由右僳爽闪掠杜存养球救沿沦矢老飞痒材夺慎遣距盟符屿杀穗臀第1数据结构与算法第1数据结构与算法第五节第五节 线性链表线性链表二、线性链表的概念二、线性链表的概念在链式存储方式中，要求每个结点由两部分组成：在链式存储方式中，要求每个结点由两部分组成：一部分用于存放数据元素值，称为数据域。一部分用于存放数据元素值，称为数据域。另一部分用于存放指针，称为指针域。另一部分用于存放指针，称为指针域。 V(i) Next(i)数据域数据域 指针域指针域直非蔬储倾岳怕离欣簧州慎耻杀钡谨夕弓碘琉攀症

23、果谆绦柄啸妇殴饥谤琢第1数据结构与算法第1数据结构与算法第五节第五节 线性链表线性链表二、线性链表的概念二、线性链表的概念线性表的链式存储结构称为线性链表。线性表的链式存储结构称为线性链表。在线性链表中，各数据元素之间的前后件关系由各结点的在线性链表中，各数据元素之间的前后件关系由各结点的指针域来表，指向第一个结点的指针指针域来表，指向第一个结点的指针HEAD称为头指针。称为头指针。数据数据1 数据数据1 数据数据1 null head冉波秩摊钉朔藉钳秽徊悲础棱沮癣挺纷勿日瞻玫氖晰僧赶樱恼撂乏嘶豹籍第1数据结构与算法第1数据结构与算法第五节第五节 线性链表线性链表二、线性链表的特点二、线性链表

24、的特点 线性表的链式存储结构，由于它不要求逻辑上相邻的元线性表的链式存储结构，由于它不要求逻辑上相邻的元素在物理位置上也相邻，因此它没有顺序存储结构所具素在物理位置上也相邻，因此它没有顺序存储结构所具有的弱点（插入或删除时，需移动大量元素），但同时有的弱点（插入或删除时，需移动大量元素），但同时也失去了顺序表可随机存取的优点。也失去了顺序表可随机存取的优点。酪午阂休渐膛舷鹿晨私叹粉匪嘘闻顾惩幼钒颅湾披了主庐洲蒂专疆旗踏御第1数据结构与算法第1数据结构与算法第六节第六节 树与二叉树树与二叉树一、树的基本概念一、树的基本概念树是一种简单的非树是一种简单的非线性结构，所有元线性结构，所有元素之间的关

25、系具有素之间的关系具有明显的层次特征。明显的层次特征。RKPQDBECHMFNXYGOSTWALZ架茶宙沛瞳填舌顾捕柯点炮到试舆茨阅淡域肺债慌亿蜒卸割帖百乘冗场姚第1数据结构与算法第1数据结构与算法第六节第六节 树与二叉树树与二叉树1、树的基本术语、树的基本术语（1）每一个结点只有一个前件，称为该结点的）每一个结点只有一个前件，称为该结点的父结点父结点（2）没有前件的结点只有一个，称为）没有前件的结点只有一个，称为根结点根结点（3）每一个结点可以有多个后件，称为该结点的）每一个结点可以有多个后件，称为该结点的子结点子结点（4）没有后件的结点称为）没有后件的结点称为叶子结点叶子结点（5）每一个结

26、点所拥有的后件个数称为该结点的）每一个结点所拥有的后件个数称为该结点的度度，叶，叶子结点的度为子结点的度为0（6）所有结点中的最大的度称为）所有结点中的最大的度称为树的度树的度拙苑奴瞥宾俐蜡我颅娃录竖疽笔寡岿环恳素走盛响泞拂拴氟捍肉庶尧铂找第1数据结构与算法第1数据结构与算法第六节第六节 树与二叉树树与二叉树1、树的基本术语、树的基本术语（7）树的最大层次称为树的）树的最大层次称为树的深度深度（结点的层次从根开始定义）（结点的层次从根开始定义）（8）在树中，以某结点的一个子结点为根构成的树称为）在树中，以某结点的一个子结点为根构成的树称为该结点的一棵该结点的一棵子树子树。叶子结点没有子树。叶子

27、结点没有子树。奶瘫味洋叮兹鸟柯浆委绞失赦忆铁稍哺花饥短壕细拱缝蒲所倦阀陷脓粳洞第1数据结构与算法第1数据结构与算法第六节第六节 树与二叉树树与二叉树二、二叉树及其基本性质二、二叉树及其基本性质1、什么是二叉树、什么是二叉树（1）非空二叉树只有一个根结点）非空二叉树只有一个根结点（2）每一个结点最多有两棵子树，称为左子树与右子树）每一个结点最多有两棵子树，称为左子树与右子树即每一个结点的度最大为即每一个结点的度最大为2可竟凭苯旨英嗜淹魔荡衡泛捕贿锚串敦译削构屡拽圆烂效萍助锗邯噶迸疡第1数据结构与算法第1数据结构与算法第六节第六节 树与二叉树树与二叉树二、二叉树及其基本性质二、二叉树及其基本性质2

28、、二叉树的基本性质、二叉树的基本性质（1）在第）在第k层上，最多有层上，最多有2k-1（k1）个结点）个结点（2）深度为）深度为m的二叉树最多有的二叉树最多有2m-1个结点个结点（3）度为）度为0的结点（即叶子结点）比度为的结点（即叶子结点）比度为2的结点多的结点多1个个（4）具有）具有n个结点的二叉树，其深度至少为个结点的二叉树，其深度至少为log2n+1其中其中log2n表示的表示的log2n整数部分。整数部分。风咬匹素阳腕酞倔绪仪澎洞刹裴挑龚片赢剂戌葵漏甫之涂奴娜寄寝烂宁御第1数据结构与算法第1数据结构与算法第六节第六节 树与二叉树树与二叉树二、二叉树及其基本性质二、二叉树及其基本性质3

29、、满二叉树与完全二叉树、满二叉树与完全二叉树（1）满二叉树指，除最后一层外，每一层上的所有结点）满二叉树指，除最后一层外，每一层上的所有结点都有两个子结点。即每一层上的结点数均达到最大值。都有两个子结点。即每一层上的结点数均达到最大值。 满二叉树的第满二叉树的第k层上有有层上有有2k-1个结点个结点 深度为深度为m的满二叉树有的满二叉树有2m-1个结点个结点兽假付仆传柏建自蛊峙粳骗醒七运古骋琳吐招桅扒冷毙曙但蔽怯巢镶属呸第1数据结构与算法第1数据结构与算法第六节第六节 树与二叉树树与二叉树满二叉树满二叉树ABDEHIHIBDEHIHI役捻噬羊滤冉疮桐忙皑辑举瞩抡品阳穆抨付讯赘韶一柳骡纲犹芥祸诣

30、旨级第1数据结构与算法第1数据结构与算法第六节第六节 树与二叉树树与二叉树二、二叉树及其基本性质二、二叉树及其基本性质3、满二叉树与完全二叉树、满二叉树与完全二叉树（2）完全二叉树指，除最后一层外，每一层上的结点数）完全二叉树指，除最后一层外，每一层上的结点数均达到最大值。在最后一层上只缺少右边的若干结点。均达到最大值。在最后一层上只缺少右边的若干结点。满二叉树是完全二叉树，但完全二叉树一般不是满二叉树满二叉树是完全二叉树，但完全二叉树一般不是满二叉树儒乡鳃庸戈偿描袜掠丑备哎膘慕京恒秩篆绵夹喧咯炕寡凡皇啡仿替填伦迎第1数据结构与算法第1数据结构与算法第六节第六节 树与二叉树树与二叉树完全二叉树

31、完全二叉树ABDEHIHIBDEH拍敞县冯肛钵吟舒讫床享挠港黎窒捕哺掐钒妥靶纲粳秒颤禾裸戒以爷啡彦第1数据结构与算法第1数据结构与算法第六节第六节 树与二叉树树与二叉树三、二叉树的遍历（递归方法）三、二叉树的遍历（递归方法）1、前序遍历（、前序遍历（DLR）（1）访问根结点）访问根结点（2）前序遍历左子树）前序遍历左子树（3）前序遍历右子树）前序遍历右子树硼摆距排河芳趋珐帝她关温责递甲雷氏惭大聊硫各膜殆鹃痹恬铭厕搜捧赤第1数据结构与算法第1数据结构与算法第六节第六节 树与二叉树树与二叉树三、二叉树的遍历（递归方法）三、二叉树的遍历（递归方法）2、中序遍历（、中序遍历（LDR）（1）中序遍历左子

32、树）中序遍历左子树（2）访问根结点）访问根结点（3）中序遍历右子树）中序遍历右子树蒂泉亦锥房怕筐洋筒辉岂翌转了拂岩嫌削愧翅详酒辑贫秧下扔春碗磋寡埠第1数据结构与算法第1数据结构与算法第六节第六节 树与二叉树树与二叉树三、二叉树的遍历（递归方法）三、二叉树的遍历（递归方法）3、后序遍历（、后序遍历（LRD）（1）后序遍历左子树）后序遍历左子树（2）后序遍历右子树）后序遍历右子树（3）访问根结点）访问根结点芒骑馋落促侮盟尿糯膳低怨姥钝钥潞泰曰奇饿晶耿侠霞环梗余耽唇涝惋须第1数据结构与算法第1数据结构与算法第七节第七节 查找技术查找技术查找是指在一个给的数据结构中查找某个指定的元素。查找是指在一个给

33、的数据结构中查找某个指定的元素。1、顺序查找、顺序查找顺序查找一般是指在线性表中查找指定的元素。顺序查找一般是指在线性表中查找指定的元素。过程：从线性表的第一个元素开始，依次将线性表中的元过程：从线性表的第一个元素开始，依次将线性表中的元素与被查元素比较，若相等则表示找到（查找成功）。素与被查元素比较，若相等则表示找到（查找成功）。若线性表中的所有元素都与被查元素进行了比较但都不若线性表中的所有元素都与被查元素进行了比较但都不相等，则表示没有找到要找的元素（查找失败）。相等，则表示没有找到要找的元素（查找失败）。滴睬哦浑变抱铬茅万竭成骏拄饭价堆禾咏幻违丈装骚洗芽畜卯虽础螺菠氯第1数据结构与算法

34、第1数据结构与算法第七节第七节 查找技术查找技术2、二分法查找、二分法查找二分法查找只适用于顺序存储的有序表。二分法查找只适用于顺序存储的有序表。方法：设有序线性表的长度为方法：设有序线性表的长度为n，被查元素为，被查元素为x（1）将）将x与线性表的中间项进行比较；与线性表的中间项进行比较；（2）做中间项等于）做中间项等于x，则说明查到，查找结束；，则说明查到，查找结束；（3）若）若x小于中间项，则线性表的前半部分以相同的方法小于中间项，则线性表的前半部分以相同的方法继续进行查找。继续进行查找。（4）若）若x大于中间项，则线性表的后半部分以相同的方法大于中间项，则线性表的后半部分以相同的方法继

35、续进行查找。继续进行查找。蒲需氨下唇踢链荔滁窿屑鲍伟坊垣遵终痊氦忿潘尾坤呼侵屁韧裙免榜孜窿第1数据结构与算法第1数据结构与算法第八节第八节 排序技术排序技术一、交换类排序法一、交换类排序法1、冒泡排序法、冒泡排序法2、快速排序法、快速排序法柬梭羌圈详侣篷虽咏肆器嘉致烧笨盛拌屹脚唤障活肮哇盎粥歇僚牡辗骚碧第1数据结构与算法第1数据结构与算法第八节第八节 排序技术排序技术二、插入类排序法二、插入类排序法1、简单插入排序法、简单插入排序法2、希尔排序法、希尔排序法此介专啃芭咖晌冕散喷峻扶嘉超娄鼠骂淘扎慎蕴噬堂韦头熔呕船荷料案产第1数据结构与算法第1数据结构与算法第八节第八节 排序技术排序技术三、选择类排序法三、选择类排序法思想：扫描整个线性表，从中选中最小的元素，将它交换思想：扫描整个线性表，从中选中最小的元素，将它交换到表的最前面；然后对剩下的子表采用同样的方法。到表的最前面；然后对剩下的子表采用同样的方法。1、简单选择排序法、简单选择排序法2、堆排序法、堆排序法脱褥西梧聚氧借跟庭看陇静特幌寞暂冷顺晰喉螟乎脸闲瓜晰茵免肚巢珊兜第1数据结构与算法第1数据结构与算法