《第3章数据结构》由会员分享，可在线阅读，更多相关《第3章数据结构（102页珍藏版）》请在金锄头文库上搜索。
1、数据结构与算法数据结构与算法替甜双摈永庙倦叁测符箩每欺鄙校谐品学第珊哺理沿惺本费忙危耗户藏瞅第3章数据结构第3章数据结构1.1 数据结构的研究对象数据结构的研究对象数据结构数据结构的研究内容：的研究内容： 非数值数据之间的结构关系，非数值数据之间的结构关系，及如何表示，如何存储，如何处理。及如何表示，如何存储，如何处理。归纳为三部分：逻辑结构、存储结构和运算集合。归纳为三部分：逻辑结构、存储结构和运算集合。 按某种逻辑关系把一批数据组织起来，按某种逻辑关系把一批数据组织起来，按一定的映象方式把它存放在计算机的存储器中，按一定的映象方式把它存放在计算机的存储器中，并在这些并在这些数据上定义一个运
2、算的集合。数据上定义一个运算的集合。慕宫衷阉谗哟哼名匈垦呀萄庙虚颊竿墩辉结梦洛轮队钨涌禾坟钡卿莎通敌第3章数据结构第3章数据结构 逻辑结构是数据结构的抽象，存储结构是数据结构的实现逻辑结构是数据结构的抽象，存储结构是数据结构的实现存储结构的二种类型存储结构的二种类型: 顺序存储结构顺序存储结构通过在存储器中的相对位置，通过在存储器中的相对位置， 表示数据的逻辑结构。表示数据的逻辑结构。 非顺序存储结构（链式存储结构）非顺序存储结构（链式存储结构） -由指针表示数据间的逻辑关系。由指针表示数据间的逻辑关系。倘层均痊傣豹循均贝隐绘恢魔舟怖团鳃益氓果坍净霹咎锯从腑更滴方座碴第3章数据结构第3章数据结
3、构哆悯慧漫昨化傀弊讼好勾短腕渠银帚持大镣锋公平靴钱论认豌汽盲灯疤郸第3章数据结构第3章数据结构1.3 常用的数据结构常用的数据结构 (1) 线性结构：结构中的数据元素之间存在着一对一的线性关系。线性表、栈、队、字符串、数组 (2) 树形结构：结构中的数据元素之间存在着一对多的层次关系。-非线性结构 (3) 图状结构或网状结构：结构中的数据元素之间存在着多对多的任意关系。- 非线性结构肇稠爷档家惮鼠茹凰欧轿茁隘壳疥涕淄靖珠航媚烦剖稼朗粗怎吞茹袖武佑第3章数据结构第3章数据结构14 算法与算法分析 1.4 1.4 算法与算法分析算法与算法分析一一 算法的概念算法的概念 算法是对特定问题求解步骤的一
4、种描述算法是对特定问题求解步骤的一种描述 算法的基本特征：算法的基本特征：1 1）可行性：组成算法的操作必须能够在计算机上实现。）可行性：组成算法的操作必须能够在计算机上实现。2 2）确定性：算法的每一步操作必须清晰无二义性。）确定性：算法的每一步操作必须清晰无二义性。3 3）有穷性：算法必须在有限步内结束；）有穷性：算法必须在有限步内结束；4 4）有足够的情报：）有足够的情报：0 0个或多个输入；个或多个输入；1 1个或多个输出；个或多个输出； 算法描述的方法很多，如自然语言、框图、类算法描述的方法很多，如自然语言、框图、类C C等等例例: : 求两个正整数求两个正整数 m m，n n 中的
5、最大数中的最大数MAXMAX的算法的算法 （1 1）若若 m n m n 则则 max=m max=m （2 2）若若 m = n m = n 则则 max=n max=n 新弹拿脱贩晰缄现验棒十舀熙筛终盆密康化搐速苦店额远摇烃余忙扣滔袍第3章数据结构第3章数据结构1、正确性：、正确性： (1) 没有语法错误； (2) 对于几组输入数据能够得出满足要求的结果； (3) 对于精心选择的典型而苛刻的几组输入数据能够得到满足要求的结果。 (4) 对于一切合法的输入数据都能产生满足要求的结果。 2、可读性：、可读性：便于阅读、理解、调试、修改；3、健壮性：、健壮性：对不合法的输入能作出正确的反映与处理
6、；4、高效性：、高效性：执行时间短（时间复杂度时间复杂度）、 需求存储空间省（空间复杂度空间复杂度）评价算法标准评价算法标准烃逻雷会墅乏尾政皖藉艘毕毋投衔汲查织枷览直借项越的吁俄詹整遭谣圆第3章数据结构第3章数据结构1时间复杂度时间复杂度T（n）以求解问题的基本操作的执行次数作为算法时间的度量。以求解问题的基本操作的执行次数作为算法时间的度量。 14 算法与算法分析O（n3）称为矩阵相乘算法时间复杂度；称为矩阵相乘算法时间复杂度；O（n3）表示矩阵相乘算法执行时间与）表示矩阵相乘算法执行时间与n3成正比成正比,即即O（n3）与）与n3同一数量级；同一数量级；例例n阶矩阶矩阵相乘的算法阵相乘的算
7、法For(i=1;i=n;i+)For(j=1;j=n;j+)cij=0;For(k=1;k=n;k+)cij+=aik*bkj 乘法乘法加法加法执行次数均为执行次数均为n3 矩阵相乘的基本运算：乘法矩阵相乘的基本运算：乘法加法；加法；绳坐闺矢馈涎坊所仙雌侨备验该清闽寒挫轩怖誊茂鼻总蝴匀昭堑昼堤墙枢第3章数据结构第3章数据结构数据结构中常用的时间复杂度频率计数有数据结构中常用的时间复杂度频率计数有7个：个： O(1) 常数型常数型 O(n)线性型线性型 O(n2)平方型平方型 O(n3)立方型立方型 O(2n)指数型指数型 O(log2n)对数型对数型 O(nlog2n)二维型二维型尿攻鄂答鹃
8、他蒸干嫌篡笑卒契学馅吻钻砂儿穆学舶眼户陪圣筏姨酉霉菠辩第3章数据结构第3章数据结构 14 算法与算法分析2算法空间复杂度算法空间复杂度用执行算法所需的辅助空间的大小作为算法所需空间的度量。用执行算法所需的辅助空间的大小作为算法所需空间的度量。设执行算法所需的辅助空间是问题规模设执行算法所需的辅助空间是问题规模n的某个函数的某个函数g(n),则算法空间复杂则算法空间复杂度记作：度记作：S（n）=O(g(n)表示算法辅助空间的增长率表示算法辅助空间的增长率与与g(n)的增长率相同的增长率相同例计算例计算解法解法1先计算先计算x的幂的幂,存于存于power中中,再分别乘以相应的系数再分别乘以相应的系
9、数#defineN100floatevaluate(floatcoef,floatx,intn)floatpowerN,f;inti;for(power0=1,i=1;i=n;i+)poweri=x*poweri-1;for(f=0,i=0;ideta=a; q-next=p- next; p- next =q;headheadzyxp pyxzp pheadheada q q淹试饭道借皆灌突炽币泅搐猾排丸她叙甭必慰楚渣篇臂哩胜脖束桔憨顽茸第3章数据结构第3章数据结构插入操作功能：在线性链表的第插入操作功能：在线性链表的第i个元素结点之前插入一个个元素结点之前插入一个新元素结点新元素结点e；
10、插入操作图示：2. 3. 1 线性链表插入前插入后 ai-1aia2a1ai+1nanheadheadai-1aia2a1ai+1naneheadhead擦湍赡剐斟霖爱貌馋辙侈哲藩叭结抢靠缘巨拽询忱艇粘定邦轩们廓芬绢饭第3章数据结构第3章数据结构 4）删除结点删除结点q=p-next; p- next =q- next; free(q);headheadzyxq qyxzq qheadheadp pp p氮膏构星泽喧瀑蝇讽焊疏攀严泄滤挞纂份腋拄嘿曾涤秧抚菊气桥畦焰抡仗第3章数据结构第3章数据结构 2. 3. 1 线性链表删除前删除后ai-1aia2a1ai+1nanheadheadai-1ai
11、a2a1ai+1nanheadp pp pq qq q鹅皱婪瑚夷爪屹季数财串楼轨唱赖菱噬卫偏利猩瘫找批裂惩脑荆进泌懂能第3章数据结构第3章数据结构2. 3. 1 线性链表小结线性链表是线性表的一种链式存储结构 线性链表的特点 1 通过保存直接后继元素的存储位置来表示 数据元素之间的逻辑关系； 2 插入、删除操作通过修改结点的指针实现； 3 不能随机存取元素；战廊引卧签青粱翠画术碟帆插踪入朽鸳管椽刺斡尤轴铅需剑觅凝唇粳撰躁第3章数据结构第3章数据结构1循环链表的概念循环链表的概念循环链表的特点是将线性链表的最后一个结点的指循环链表的特点是将线性链表的最后一个结点的指针指向链表的第一个结点（首尾相
12、连的单链表）针指向链表的第一个结点（首尾相连的单链表）2循环链表图示循环链表图示2. 3 . 2 循环链表(a)非空表 （b）空表headheadheadheada1an货文蓖缺背蒂茶的爹旭玛房聘捻锡螺全掸沾袄动凹脉月饵抓鸡枷倘须蛛昆第3章数据结构第3章数据结构循环链表说明 在解决某些实际问题时循环链表可能要比线性链表在解决某些实际问题时循环链表可能要比线性链表方便些。如将一个链表链在另一个链表的后面；方便些。如将一个链表链在另一个链表的后面；对循环链表，有时不给出头指针，而是给出尾指针对循环链表，有时不给出头指针，而是给出尾指针a aa1ana-next给出尾指针的循环链表涛柞圈六瘴探硝肄及
13、赎灼皆陷狙看棵旺泣渣酮钮搭劲天瓢码弟苯凳饵锁其第3章数据结构第3章数据结构2.3.4双向链表双向链表循循环环单单链链表表，虽虽然然从从任任一一结结点点出出发发沿沿着着指指针针链链能能找找到到其其前前件件，但但时时间间耗耗费费是是O(n)。如如果果希希望望从从表表中中快快速速确确定定某某一一个个结结点点的的前前件件，另另一一个个解解决决方方法法是是在在链链表表的的每每个个结结点点里里再再增增加加一一个个指指向向其其前前件件的的指指针针域域prior。这这样样形形成成的的链链表表中中就就有有两两条条方方向向不不同的链，同的链，称为双向链表。称为双向链表。沉祈紧吐猎胡家逢哉值妥釜院淹需蕾闷挞瘤锣连矩
14、咯鬃号箔拙紫刺鸳补胚第3章数据结构第3章数据结构线性表小结线性表小结 线性表的顺序存储结构线性表的顺序存储结构顺序表，顺序表， 链式存储结构链式存储结构-线性链表线性链表,循环链表循环链表, 双向双向链表链表.不同的存储结构，线性表的同一操作的不同的存储结构，线性表的同一操作的算法是不同的算法是不同的:在顺序存储结构下，线性表的插入、删除在顺序存储结构下，线性表的插入、删除操作，通过移动元素实现操作，通过移动元素实现;在线性链表存储结构下，线性表的插入、在线性链表存储结构下，线性表的插入、删除操作，通过修改指针实现。删除操作，通过修改指针实现。缔脉斜舰郴馅杠填坏谷毯劝来渣啄缺倾落扫楔堡扁琶嘉桐
15、橡鲍烛奔觅郝扳第3章数据结构第3章数据结构3.1 栈栈是限定仅能在表尾一端进行插入、删除操栈是限定仅能在表尾一端进行插入、删除操作的线性表作的线性表（a1,a2,.,ai-1,ai,ai+1,an）插入删除3.1.1栈的概念栈的概念一一什么是栈什么是栈?授毙丁烦喇窟棍去忧滚情堤拓死谴嗅傲兵届兼淤留徒涩耸恬传初轮巫今瘸第3章数据结构第3章数据结构3.1栈栈将表中允许进行插入、删除操作的一端称为栈顶将表中允许进行插入、删除操作的一端称为栈顶(Top)，栈顶的当前位置是动态变化的，由一个栈顶指针指示其位置。栈顶的当前位置是动态变化的，由一个栈顶指针指示其位置。表的另一端称为栈底表的另一端称为栈底(B
16、ottom)。当栈中没有元素时称为空栈。当栈中没有元素时称为空栈。栈的插入操作称为进栈或入栈，删除操作称为出栈或退栈。栈的插入操作称为进栈或入栈，删除操作称为出栈或退栈。 结审逾泰诚剥焦淌照石您器巩妈卞坤锥纽疏过腾污椽拼芽设杆伺翠社国裁第3章数据结构第3章数据结构栈栈滁砖踢纬洁留幅挟枪凿齿言虐争赐舞破怒刺貌剖烈膘繁韵尔绷菏邓圃皖柴第3章数据结构第3章数据结构3.1 栈栈的示意图栈的示意图出栈出栈进栈进栈栈的特点栈的特点后进先出后进先出第一个进栈的元素在栈底，第一个进栈的元素在栈底，最后一个进栈的元素在栈顶，最后一个进栈的元素在栈顶，第一个出栈的元素为栈顶元素，第一个出栈的元素为栈顶元素，最后一
17、个出栈的元素为栈底元素最后一个出栈的元素为栈底元素栈栈顶顶栈栈底底ana2a1赃疥泪爆捂掇妇逆骤避茧痰旦拜赠洛咀让虑蔚隶方汾鬼侦躯仙怒宅山似革第3章数据结构第3章数据结构 小小 结结 1栈是限定仅能在表尾一端进行插入、栈是限定仅能在表尾一端进行插入、删除操作的线性表；删除操作的线性表；2栈的元素具有后进先出的特点；栈的元素具有后进先出的特点；3栈顶元素的位置由一个称为栈顶指针的栈顶元素的位置由一个称为栈顶指针的变量指示，变量指示，进栈、出栈操作要修改栈顶指针；进栈、出栈操作要修改栈顶指针；3.1栈栈簧卉摊徽组饭侨币页酞鞠争蓖览瓮钮崖辩钾酬牛蛀夯乓倡廖双玛昧确往涎第3章数据结构第3章数据结构32
18、队列队列3.2.1队列的概念队列的概念一一什么是队列什么是队列队列是限定仅能在表头进行删除，表尾进行插入的线性表队列是限定仅能在表头进行删除，表尾进行插入的线性表（a1,a2,.,ai-1,ai,ai+1,an）插入插入删除删除涵婪炕负橱抢狞绥挣罐宝惧臃狐醉沧顾爽医奠园块怒貉蜀硷谁玫吾疆倍环第3章数据结构第3章数据结构33队列队列 a a1 1 a a2 2 a a3 3 a an n入队列入队列队队头头队队尾尾出队列出队列队队 列列 的的 示示 意意 图图队列的特点队列的特点先进先出先进先出第一个入队的元素在队头，第一个入队的元素在队头，最后一个入队的元素在队尾，最后一个入队的元素在队尾，第
19、一个出队的元素为队头元素，第一个出队的元素为队头元素，最后一个出队的元素为队尾元素最后一个出队的元素为队尾元素隐揣恢盂问万守风足棘诺营滞奖筑相盈杂背供纵掣寇票秘痘园宿础挫搞疏第3章数据结构第3章数据结构rearrearfrontfrontJ1rearrearfrontfrontJ2（a)a)空队列空队列(b)J1,J2(b)J1,J2相继相继入队列入队列(c)J1(c)J1出队出队(d)J3,J4, J5(d)J3,J4, J5和和J6J6相继入队之后相继入队之后,J2,J2出队出队rearrearfrontfront0 01 12 23 34 45 53. 3 队列rearrearfront
20、frontJ5J4J3front,rearfront,rear为整为整数数又有又有J7入队入队,怎么办？怎么办？J2J6狮淄宿剃牡凋递汤园嗣严毋赂沥橙液翱蔷丧蔑遗吴邦奶婚应奔毡蓟鄙羔拴第3章数据结构第3章数据结构3.3队列队列3.循环队列循环队列frontfrontrearJ6J6J4J4J5J53 124 05rearrear54 03 12frontfrontJ6J6J7J7J8J8J9J9J4J4J5J5frontfrontrearrear54 03 12(b)(b)队空队空(a)(a)队满队满J7J7rearrear襟鸯才蓑损檬胎溯忘途彭逛科琢唉炔肃警揍丽尝坎形潞桥谭彰埔涩擂靠眼第3章
21、数据结构第3章数据结构3.3队列队列判分队空、队满方法：判分队空、队满方法：1）另设一个标志）另设一个标志S以区分队空、队满。以区分队空、队满。2）S=0队空：队空：front=rear;S=1队满：队满：front=rear;frontfront54 03 12J6J6J7J7J8J8J4J4J5J5（c c）rearrear菇亭逃省祁寡隶增珍诬侥箍搭酿兼拈惰窒腿痞题尸丹池感锑诺厚踩泽邦祟第3章数据结构第3章数据结构3.3队列队列入队操作入队操作：将元素将元素x插入队尾插入队尾 frontfrontrearrear54 03 12J1J1J3J3J2J2x xfrontfrontrearre
22、ar54 03 12J1J1J3J3J2J2元素元素 x x 入队前入队前元素元素 x x 入队后入队后继结橙兑躲赞态法枉伸憋跟毛量尼濒纂嗅饲碾匠娘悔爹癸氮孵型古伏纂疤第3章数据结构第3章数据结构3.3队列队列出队操作出队操作：删除队头：删除队头元素；元素； frontfrontrearrear54 03 12J1J1J3J3J2J2出队操作前出队操作前frontfrontrearrear54 03 12J1J1J3J3J2J2出队操作后出队操作后剩黍枷靠礼嘛寂鼠治尺霹酞笨陆敢涎鼎豆只涉骂士聋恶途靶兔斟荚瑶暴歹第3章数据结构第3章数据结构 小小 结结 1队列是限定仅能在表尾一端进行插入，表头队
23、列是限定仅能在表尾一端进行插入，表头一端删除一端删除操作的线性表；操作的线性表；2队列中的元素具有先进先出的特点；队列中的元素具有先进先出的特点；3队头、队尾元素的位置分别由称为队头指针队头、队尾元素的位置分别由称为队头指针和队尾指针的变量指示，和队尾指针的变量指示，4入队操作要修改队尾指针，出队操作要修改入队操作要修改队尾指针，出队操作要修改队头指针；队头指针；产使盖葬衣镐号狮顿契募戊瞪涨萝嗣涕何霍煽揽膳兜馒隅惺拇胯否店孪沟第3章数据结构第3章数据结构树和二叉树 曙淄床匣指貌膳述帧赔懈倚啃际勿姻橙途耕嗅钟霉檀措付刑钟榔滋蹿恿努第3章数据结构第3章数据结构1树的定义树的定义 树是是n个个结点的
24、有限集合点的有限集合T，当，当n=0时，称，称为空空树；当；当n0时，T满足如下条件：在任一棵非空足如下条件：在任一棵非空树中：中：（1）有且）有且仅有一个称有一个称为根的根的结点。点。（2）其余）其余结点可分点可分为M个互不相交的个互不相交的子子集合，而且集合，而且这些些子子集集中的每一中的每一个个本身又是一棵本身又是一棵树，也也称称为根的子根的子树。J JI IA AC CB BD DH HG GF FE EK KL LM M镭车世恕佛秃呜喜垦挂迸照翱藉掖熊奥噎傣凋澎滑协膳锁鼓逮尝梢房包饵第3章数据结构第3章数据结构2树的实例树的实例树可表示具有分枝结构关系的对象树可表示具有分枝结构关系的
25、对象例例1家族族谱家族族谱设某家庭有设某家庭有13个成员个成员A、B、C、D、E、F、G、H、I、J、K、L、M，他们之间的关系可用树表示：，他们之间的关系可用树表示：J JI IA AC CB BD DH HG GF FE EK KL LM M豹呵瓦餐棵胺错昔跳摈浊蘑火米添艺山炽业胜溢足纂燥暇颧斩鬃欠掉废沃第3章数据结构第3章数据结构计算机中树是常用的数据组织形式计算机中树是常用的数据组织形式 尽管有些应用中数据元素之间并不存在分支结构关系，但尽管有些应用中数据元素之间并不存在分支结构关系，但为了便于管理和使用数据，将它们用树的形式来组织。为了便于管理和使用数据，将它们用树的形式来组织。例例
26、2计算机的文件系统计算机的文件系统不论是不论是DOS文件系统还是文件系统还是window文件系统，所有的文件都是用文件系统，所有的文件都是用树的形式来组织的。树的形式来组织的。文件夹文件夹1 1 文件夹文件夹n n 文件文件1 1 文件文件2 2文件夹文件夹11 11 文件夹文件夹12 12 文件文件11 11 文件文件1212C C盘盘氖琼胎拔箕捕陵笆蛰信逢惹纪弟抽颐浊乖供村辑销堕冯糕钟四垮巡母阅佬第3章数据结构第3章数据结构3、树的、树的基本术语基本术语 树的结点：包含一个数据元素及若干指树的结点：包含一个数据元素及若干指向子树的分支；向子树的分支；孩子结点：结点的子树的根称为该结点孩子结
27、点：结点的子树的根称为该结点的孩子，的孩子，B、C是是A的孩子；的孩子；双亲结点：双亲结点：B结点是结点是A结点的孩子，则结点的孩子，则A结点是结点是B结点的双亲；结点的双亲；兄弟结点：同一双亲的孩子结点，兄弟结点：同一双亲的孩子结点，H、I、J互为兄弟；互为兄弟；堂兄结点堂兄结点：同一层上结点，同一层上结点，E E、F F、G G、H H、I I、J J、互为堂兄弟；互为堂兄弟；J JI IA AC CB BD DH HG GF FE EK KL LM M碘埂磐佛浓偿总挂焕琅锌粟毙抬球绪图形疟烘墨摆焕桶正肇症隧佰证维哼第3章数据结构第3章数据结构3、树的、树的基本术语基本术语结点的层次：根结
28、点的层次定义为结点的层次：根结点的层次定义为1；根的孩子为第；根的孩子为第二层，依此类推；二层，依此类推；树的深度：树中所有结点的层次的最大值树的深度：树中所有结点的层次的最大值结点的度：结点子树的个数结点的度：结点子树的个数树的度：树的度：树中结点度的最大值。树中结点度的最大值。叶子结点：度为叶子结点：度为0的结点；的结点；分枝结点：度不为分枝结点：度不为0的结点；的结点；J JI IA AC CB BD DH HG GF FE EK KL LM M喊尖谚艾尺鱼绩姐卧促缘帚恰脉傅茁依浆哎疾钻募谍螟桓捍综违岗仇华则第3章数据结构第3章数据结构一一 二叉树的概念二叉树的概念1 1 二叉树的定义二
29、叉树的定义二叉树：二叉树： 或为空树，或由根及两颗互不相交的左子树、右子树构或为空树，或由根及两颗互不相交的左子树、右子树构成，并且左、右子树本身也是二叉树。成，并且左、右子树本身也是二叉树。 A A F F G G E E D D C C B B诵引痛隋郭泉踢期脑塞臻坎腔云胀芋暂溶敌珐朴爪鞭接蔽芥铭增催浪患翔第3章数据结构第3章数据结构一一 二叉树的概念二叉树的概念二叉树说明说明1 1）二叉树中每个结点最多有两个子树；）二叉树中每个结点最多有两个子树；既：二叉树每个结点度小于等于既：二叉树每个结点度小于等于2;2;2 2）左、右子树不能颠倒）左、右子树不能颠倒有序树有序树; ;3 3）二叉树
30、是递归结构，在二叉树的定义中又用到了二叉树的）二叉树是递归结构，在二叉树的定义中又用到了二叉树的概念概念; ;辨法冰芒狙狼峡而漳咎弹窥蹄耐冲泻蔚凹鹿锚熬奎叛措耐啮跃若蕉玖愧攒第3章数据结构第3章数据结构 (a)(a)、(b)(b)是不同的二叉树，是不同的二叉树， (a)(a)的左子树有四个结点的左子树有四个结点，(b)(b)的左子树有两个结点的左子树有两个结点(a)(b) G G E E D D C C B B A A F F G G E E D D C C B B F FA A汰勺捡箩雍骂稳莱卿舟铬绞痊斩辕塔犁呵乙幂邦鞭谊带携外奔理铣殖远襄第3章数据结构第3章数据结构 2二叉树的基本形态二叉
31、树的基本形态(a)空树(b)只有根(c) 右子树空(e) 左子树空(d) 左、右子树非空峭愧二涧咕绕裔穷注犁傈斋绞揉苹完奔才惊晤燕洛刷摘犬孵肖节沤算巨您第3章数据结构第3章数据结构二、二、二叉树的性质二叉树的性质性质性质1:在二叉树的第在二叉树的第i层上至多有层上至多有2i-1个结点个结点(i1)。 性质性质2: 深度为深度为k的二叉树至多有的二叉树至多有2k-1个结点（个结点（k1）。 秋局纱迈棺藻拇量靡睬愁帧炙姚捆卤缎叼誓虑私史促淳衣葛仟诣伊缺角貌第3章数据结构第3章数据结构性性质质3: 对对任任意意一一棵棵二二叉叉树树T，若若叶叶结结点点数数为为n0，而而其其度度为为2的的结点数为结点数
32、为n2，则，则n0=n2+1。垫脾藏尸厕完朵用接乏奄千膳志渭不淹茨暴夯拴嚣京钳露鸯溉揭断苦攘借第3章数据结构第3章数据结构两种特殊的二叉树两种特殊的二叉树满二叉树：深度为满二叉树：深度为k k的二叉树，如有的二叉树，如有2 2k k-1-1个结点则称为满二叉树；个结点则称为满二叉树； A G F E D C B A C BK=3的满二叉树K=2的满二叉树撬帚刃焦祸剧休擞许以赂睬底褂套柿亭谨刁批又慕藏萄叙译渺祭吭皮混沏第3章数据结构第3章数据结构满二叉树的顺序表示：满二叉树的顺序表示：从从二二叉叉树树的的根根开开始始，从从上上到到下下，从从左左到到右右，逐逐层层进进行行编编号号（1，2，n）。例
33、如图（）。例如图（a）所示的满二叉树的顺序表示为）所示的满二叉树的顺序表示为:(1，2，3，4，5，6，7，8，9，10，11，12，13，14，15)。 耿伴婚厉忽婶顽接毅婉舔淫廷咆佳施办播蛆袱龙咆度擒筏分测懊鼎被诡如第3章数据结构第3章数据结构完全二叉树：完全二叉树： 深深度度为为k，结结点点数数为为n的的二二叉叉树树，如如果果其其结结点点1n的的位位置置序序号号分分别别与与满满二二叉叉树树的的结结点点1n的的位位置置序序号号一一一对应，则为完全二叉树，一对应，则为完全二叉树，如上图如上图(b)所示。所示。满二叉树必为完全二叉树，满二叉树必为完全二叉树，而完全二叉树不一而完全二叉树不一定是
34、满二叉树。定是满二叉树。拐银私睁冕黎胶暇栗亢姜翱镶右赠汹疥举七挣澈撑焊濒诲伊谅拉庞叠廊坝第3章数据结构第3章数据结构性质性质4：具有：具有n个结点的完全二叉树的深度为个结点的完全二叉树的深度为log2n+1。 屿琳圆午障锭败苍省罕程伏镜并批绵涸锰刑蜘脂岿妨傣秘角讹律人糕电羹第3章数据结构第3章数据结构性性质质5: 对对于于有有n个个结结点点的的完完全全二二叉叉树树，按按照照从从上上到到下下、从从左左到到右右的的顺顺序序对对二二叉叉树树中中的的所所有有结结点点从从1开开始始顺顺序序编编号号，则则对对于任意的序号为于任意的序号为i的结点有：的结点有：（1）如如i=1，则则序序号号为为i的的结结点点
35、是是根根结结点点，无无双双亲亲结结点点；如如i1，则序号为则序号为i的结点的双亲结点序号为的结点的双亲结点序号为i/2（下取整）（2）如如2in，则则序序号号为为i的的结结点点无无左左孩孩子子；如如2in，则则序序号号为为i的结点的左孩子结点的序号为的结点的左孩子结点的序号为2i。（3）如如2i1n，则则序序号号为为i的的结结点点无无右右孩孩子子；如如2i1n，则序号为则序号为i的结点的右的结点的右孩子结点的序号为孩子结点的序号为2i1。 跋型地坛悲耕卜息朝霹骚纳肠衙汉值云蔗呸昔噎俊尚灸什赛负均茁卡瘟砧第3章数据结构第3章数据结构 二叉树二叉树存储结构存储结构-二叉链表二叉链表二叉链表中每个结
36、点包含三个域：数据域、左指针域、右指二叉链表中每个结点包含三个域：数据域、左指针域、右指针域针域AFEDCB二叉链表图示二叉链表图示 D D A A B B C C E E F F 服策极率枯残诵凶烫台漱踪饼税横笛粉熊骡灿贪亲格何琼考神吵灼衫澜躲第3章数据结构第3章数据结构 若若一一个个二二叉叉树树含含有有n个个结结点点，则则它它的的二二叉叉链链表表中中必必含含有有2n个指针域，个指针域，其中必有其中必有n+1个空的指针域。个空的指针域。 脑鸡税础勘拘廊辣檀撬硷永炮桑插辞罪厕瞥锨嗣铀弥献咨却啼苦庶抹农锗第3章数据结构第3章数据结构二、二叉树的遍历遍历遍历：按某种顺序访问二叉树的每个结点，而且每
37、个结点仅被访按某种顺序访问二叉树的每个结点，而且每个结点仅被访问一次。问一次。访问：含义很广，可以是对结点的各种处理含义很广，可以是对结点的各种处理，如修改结点数据、，如修改结点数据、输出结点数据。输出结点数据。 如何访问二叉树的每个结点， 而且每个结点仅被访问一次？铲囊鹃纫辣矽丈腰笑辟傣撕门自虽迂蓝空补付雪嫌账投翟和擦飘垢秉悉厌第3章数据结构第3章数据结构二叉树的遍历方法二叉树的遍历方法 二叉树由根、左子树、右子树三部分组成 二叉树的遍历可以分解为：访问根，遍历左子树和遍历右子树令：L L：遍历左子树 T：访问根结点 R R：遍历右子树 约定先左后右,有三种遍历方法： T L L R R前序
38、遍历、 L L T R R中序遍历、 L L R R T后序遍历。A F GE DC B槐你被哉鸯微疮剑设镰虑浓矢检父领邯归眨否摄晒怯暴寓剑倾贵墒彪转阶第3章数据结构第3章数据结构 先序遍历（T L L R R） 若二叉树非空 （1）访问根结点； （2）先序遍历左子树； （3）先序遍历右子树；先序遍历序列：A,B,D,E,G,C,F例：先序遍历右图所示的二叉树 （1）访问根结点A （2）先序遍历左子树：即按 T L L R R 的顺序遍历左子树 （3）先序遍历右子树：即按 T L L R R 的顺序遍历右子树A F GE DC B钧巍哉弛瀑蔫魏铆复哟杖冈用敌酌右睛咱危访糟漫竿茨睁氰腑戍蔚涤霖杀
39、第3章数据结构第3章数据结构中序遍历（LTR）若二叉树非空（1）中序遍历左子树（2）访问根结点（3）中序遍历右子树中序遍历序列：D,B,G,E,A,C,F例：中序遍历右图所示的二叉树 （1）中序遍历左子树：即按 LTR的顺序遍历左子树 （2）访问根结点A （3）中序遍历右子树：即按 LTR的顺序遍历右子树A F GE DC B听夸倔静毖坏值角虹僻蝎挤利以虞绽郴旱撑哀破外焉钟忆秽闭沮睡计绊荒第3章数据结构第3章数据结构后序遍历（LRT）若二叉树非空（1）后序遍历左子树（2）后序遍历右子树（3）访问根结点后序遍历序列： D,G,E,B,F,C,A例：后序遍历右图所示的二叉树 （1）后序遍历左子树：
40、即按 LRT的顺序遍历左子树 （2）后序遍历右子树：即按 LRT的顺序遍历右子树 （3）访问根结点AA F GE DC B蛆滇宅津拖那举奎捉时竟佳赃坯弛叉绰傣换晴壳沼丙龚卫棱惮翱邵匣乔檄第3章数据结构第3章数据结构后序遍历序列：a,b,c,d,-,*,+,e,f,/,-中序遍历序列：a,+,b,*,c,-,d,-,e,/,f 例：例：中序遍历、中序遍历、后后序序遍历下图所示的二叉树 e d c b f a + * / - -岭饥梦算枉销介铭捞剁仿驱届亨木饵伸锤实腔抒值涧醉殿椰氦炸肪酸浮非第3章数据结构第3章数据结构二叉树1 1 二叉树：二叉树： 或为空树，或由根及两颗互不相交或为空树，或由根及
41、两颗互不相交的左子树、右子树构成，并且左、右子树本身的左子树、右子树构成，并且左、右子树本身也是二叉树；也是二叉树； 2 2 二叉树可以用链式结构存储；二叉树可以用链式结构存储；3遍历：按某种搜索路径访问二叉树的每个结点，遍历：按某种搜索路径访问二叉树的每个结点，每个结点仅被访问一次。每个结点仅被访问一次。 4 4二叉树的遍历可以分解为：访问根，遍历二叉树的遍历可以分解为：访问根，遍历左子左子树和树和遍历遍历右子树，常用的三种遍历算法：右子树，常用的三种遍历算法：先序先序遍历、中序遍历、后序遍历；遍历、中序遍历、后序遍历；雾家史淮殷诚棵屎腥培陇藤遥崩坯策恼卵屯孵呸耗帐祟是与卵皱充瘦氟竖第3章数
42、据结构第3章数据结构查找查找 猩纂援睦馆惦侠扇降谁焙俘清溃杏套准茄吗匝釉祈景砧卜键挥砸埂共拖赔第3章数据结构第3章数据结构5.1查找的基本概念查找的基本概念 查查找找（列列）表表：由由同同一一类类型型的的数数据据元元素素（或或记记录录）构构成成的的集合，集合，可利用任意数据结构实现。可利用任意数据结构实现。关关键键字字：数数据据元元素素的的某某个个（几几个个）数数据据项项的的值值。如如果果一一个个数数据据项项可可以以唯唯一一标标识识列列表表中中的的一一个个数数据据元元素素，则则称称其其为为关关键键字字。罩刑苇中及瓜膛壬限种规妓昆凰清吓绑屿疚谤红诗磺叙宽困批鲁毫层岩宰第3章数据结构第3章数据结构
43、查查找找：根根据据给给定定的的关关键键字字值值，在在特特定定的的查查找找（列列）表表中中确确定定一一个个其其关关键键字字与与给给定定值值相相同同的的数数据据元元素素，并并返返回回该该数数据据元元素在列表中的位置。素在列表中的位置。若找到相应的数据元素，若找到相应的数据元素，称查找成功，否则称查找失败称查找成功，否则称查找失败 狂蔑捻臣伞际渤二杆搽间薛类拧兰存莹蜕正阶瞳涝盛胆阀门芦哼扒里骇衣第3章数据结构第3章数据结构52线性表的查找线性表的查找5.2.1 顺序查找顺序查找-最简单的查找方法顺序查找的基本思想顺序查找的基本思想 从从表表的的一一端端开开始始，顺顺序序扫扫描描线线性性表表，依依次次
44、将将扫扫描描到到的的结结点点关关键键字字和和待待找找的的值值相相比比较较，若若相相等等，则则查查找找成成功功，若若整整个个表表扫扫描描完完毕毕，仍仍末末找找到到关关键键字字等等于于的的元元素素，则则查查找找失失败。败。顺顺序序查查找找既既适适用用于于顺顺序序表表，也也适适用用于于链链表表。若若用用顺顺序序表表，查查找找可可从从前前往往后后扫扫描描，也也可可从从后后往往前前扫扫描描，但但若若采采用用单单链链表表，则则只只能能从从前前往往后后扫扫描描。另另外外，顺顺序序查查找找的的表表中中元元素素可可以以是是无无序的。序的。诱毗骆卜赐泊患榔盘崖绣魂薛酪菩歼恭嫂铆人案湖播惧埃豁寡虐荤镀家粟第3章数据
45、结构第3章数据结构顺顺序序查查找找算算法法的的性性能能。假假设设列列表表长长度度为为n，那那么么查查找找第第i个个数数据据元元素素时时需需进进行行n-i+1次次比比较较，即即Ci=n-i+1。又又假假设设查查找找每每个个数数据据元元素素的的概概率率相相等等，即即Pi=1/n，则则顺顺序序查查找找算算法法的的平平均均查查找找长长度度为：为：杜值删郧涯秸禄完酸挠赶厘奈绣执次七堰朝翅打烛俘烃迸誊碍窟址税某凛第3章数据结构第3章数据结构顺序查找的特点顺序查找的特点 顺序查找的优点是算法简单，对查找表结构无任何顺序查找的优点是算法简单，对查找表结构无任何要求，无论是用向量还是用链表来存放结点，也无论结要
46、求，无论是用向量还是用链表来存放结点，也无论结点之间是否按关键字有序或无序排，它都同样适用。点之间是否按关键字有序或无序排，它都同样适用。顺序查找的缺点是查找效率低，当顺序查找的缺点是查找效率低，当n较大时，不较大时，不宜采用顺序查找宜采用顺序查找。吼诅搂擞蕊谅耪庞雾素梦檬话损脉扶量壤昨批吮鞍耍登睡库民堕驹幕狂斥第3章数据结构第3章数据结构5.2.2二分二分查找（折半找（折半查找）找）1.二分查找的基本思想二分查找的基本思想高效率的查找方法。要求表中元素按关键字有序高效率的查找方法。要求表中元素按关键字有序(升序或降序升序或降序)。假设表中元素为升序排列。假设表中元素为升序排列。二分查找的基本
47、思想是：二分查找的基本思想是：首先首先将表中间位置记录的关键字与查找关键字比较，将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子表，否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。找前一子表，否则进一步查找后一子表。重复以上过程，直到找到满足条件的记录，使查找重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。成功，或直到子表不存在为止，此时查
48、找不成功。恃沾执篷烘泳戮透盎到奈雷娥炙抗秋晨谋带挛纫羚诛鸡泻邯剃恫沉鲍供漫第3章数据结构第3章数据结构例如，假设给定有序表中关键字为：例如，假设给定有序表中关键字为：05,13,19,21,37,56,64,74,80,88,92，查找，查找K=21的情况：的情况：0 1 2 3 4 5 6 7 8 9 100 1 2 3 4 5 6 7 8 9 10鼎腑姓旦羞塔编壤碰森拔稻毒崇粤挂采囚劝垢幢护幢瞪外评量纵睁滋门诽第3章数据结构第3章数据结构0 1 2 3 4 5 6 7 8 9 100 1 2 3 4 5 6 7 8 9 10廉在冲湍势邦藩更忿按硝虫瘤帚风五组曲阂健殖圣及妙刷硷君擞脖繁危扶第
49、3章数据结构第3章数据结构3.二分查找的性能分析 二二分分查查找找的的过过程程可可以以用用二二叉叉树树来来描描述述。把把当当前前查查找找区区间间的的中中点点作作为为根根结结点点，左左子子区区间间和和右右子子区区间间分分别别作作为为根根的的左左子子树树和和右右子子树树，左左子子区区间间和和右右子子区区间间再再按按类类似似的的方方法法，由由此此得到的二叉树称为二分查找的判定树。得到的二叉树称为二分查找的判定树。例例如如，给给定定的的关关键键字字序序列列05,13,19,21,37,56,64,74,80,88,92，的的判判定定树树。 0 1 2 3 4 5 6 7 8 9 10苫涯墓踢迹棺袱凉喇
50、鞍柳峻郸莹桨郭拌溃吉际惠帕瞳迹亡污埃骡震菏据籍第3章数据结构第3章数据结构 排序排序 霞铺惹湛兄与馈孩婉缴磊正诲惩洋厕脚扑篷懒稚兴掂击欠绦剪桶矩遏纪鸣第3章数据结构第3章数据结构61基本概念基本概念6.1.1排序定义排序定义 排排序序就就是是把把一一组组记记录录（元元素素）按按照照某某个个域域的的值值的的递递增增或或递递减减的的次序重新排列的过程。次序重新排列的过程。(按学号的递增按学号的递增)表7-1 学生档案表学号学号姓名姓名年龄年龄性别性别99001王晓佳王晓佳18男男99002林一鹏林一鹏19男男99003谢宁谢宁17女女99004张丽娟张丽娟18女女99005周涛周涛20男男9900
51、6李小燕李小燕16女女玫垄岭卖笼慢形眼帘屹吨绞势锄擞毙烛著富渺晤部羚倔卧颅求硒樱渐桃孵第3章数据结构第3章数据结构为讨论方便，我们直接将排序码写成一个一维数组的形式，并且在没有声明的情形下，所有排序都按排序码的值递增排列。 排序排序 插入排序（直插排序、二分排序、希尔排序）插入排序（直插排序、二分排序、希尔排序） 交换排序（冒泡排序、快速排序）交换排序（冒泡排序、快速排序） 选择排序选择排序（直选排序、堆排序）（直选排序、堆排序） 归并排序（二路归并排序、多路归并排序） 助冰碰喇抬蚜茫镑钡翻出渊常北丈掣劝就倘金稻烈比榴吧跋涧肖产研曳负第3章数据结构第3章数据结构62插入排序插入排序 6.2.1
52、直接插入排序1直接插入排序（Straight Insertion Sorting）基本思想：把基本思想：把n个待排序的元素看成一个有序表和一个无序表，个待排序的元素看成一个有序表和一个无序表，开始时有序表中只包含一个元素，无序表中包含有开始时有序表中只包含一个元素，无序表中包含有n-1个元素，个元素，排序过程中每次从无序表中取出第一个元素，把它的排序码排序过程中每次从无序表中取出第一个元素，把它的排序码依次与有序表元素的排序码进行比较，将它插入到有序表中依次与有序表元素的排序码进行比较，将它插入到有序表中的适当位置，使之成为新的有序表。的适当位置，使之成为新的有序表。肿炭梢粉伊族媚编浅缎蕾哉嚼
53、灵骑遵疮铺霜肝古牲拨凄园赃炽颐拾捉慈保第3章数据结构第3章数据结构例如，n=6，数组R的六个排序码分别为：17，3，25，14，20，9。它的直接插入排序的执行过程如图7-1所示。京世姓滋总氦柞没午亚钥哑徊幸呆宽劫赛慷衣飞饲令夸蒜帕戚搐汉陛嗡惊第3章数据结构第3章数据结构3直接插入排序的效率分析直接插入排序的效率分析直接插入排序算法十分简单。直接插入排序算法十分简单。空间空间:只需要一个元素的辅助空间，用于元素的位置交换。只需要一个元素的辅助空间，用于元素的位置交换。时时间间:外外层层循循环环要要进进行行n-1次次插插入入，每每次次插插入入最最少少比比较较一一次次（正正序序），移移动动两两次次
54、；最最多多比比较较i次次，移移动动i2次次（逆逆序序）（i=1，2，n-1）。）。直接插入排序的时间复杂度为直接插入排序的时间复杂度为O（n2）。）。最坏情况比较最坏情况比较n(n-1)/2皇四窖釉晕刮扇胀烯胰饯光米态反儒沧逮耽堪小哩儡筐颊疫曲胃浮隅祥锯第3章数据结构第3章数据结构6.2.3希尔排序希尔排序希尔排序希尔排序(缩小增量排序缩小增量排序):1959年由年由D.L.Shell提出来的。提出来的。基基本本思思想想：先先将将整整个个待待排排元元素素序序列列分分割割成成若若干干个个子子序序列列（由由“增增量量”确确定定）分分别别进进行行直直接接插插入入排排序序，待待整整个个序序列列中中的的
55、元元素素基基本本有有序序（增增量量足足够够小小）时时，再再对对全全体体元元素素进进行行一一次次直直接接插插入入排排序序。因因为为直直接接插插入入排排序序在在元元素素基基本本有有序序的的情情况况下下（接接近近最最好好情况），效率是很高的。情况），效率是很高的。酉困贱介提壤前获夫熊绝惮序犀弟兢淑拂妇琶辅嘱饺胜亭气咒晋炯故兜骚第3章数据结构第3章数据结构例如，n=8，数组array 的八个元素分别为：91，67，35，62，29，72，46，57。下面用图7-2给出希尔排序算法的执行过程。贾孙致审缴篮侄锨歌咯呈厨婪器勃羹刘氰皖趁酷且沪篆酿蛊性尊苗冷袖卸第3章数据结构第3章数据结构希尔排序的效率分析希
56、尔排序的效率分析与增量有关，与增量有关，最坏情况，希尔排序的时间复杂性在最坏情况，希尔排序的时间复杂性在O（nlog2n）。）。干薛散四耍唐言陕呵蓝翌遏遭狐缆凄用俭给孟厄屉沿柄处屡甲九葫碟豌挚第3章数据结构第3章数据结构63交换排序交换排序6.3.1 冒泡排序冒泡排序基本思想:对对待待排排序序序序列列从从后后向向前前（从从下下标标较较大大的的元元素素开开始始），依依次次比比较较相相邻邻元元素素的的排排序序码码，若若发发现现逆逆序序则则交交换换，使使排排序序码码较较小小的的元元素素逐逐渐渐从从后后部部移移向向前前部部，就就象象水水底底下下的的气气泡泡一一样样逐逐渐向上冒。渐向上冒。拢耐硅悼增猖茨
57、笨煽伊硬窘左然显嗡耘巾沧搪寨闷哪惑皂既亿粱实镁雕怕第3章数据结构第3章数据结构例例如如，n=6，数数组组R的的六六个个排排序序码码分分别别为为：17，3，25，14，20，9。下面用图。下面用图7-3给出冒泡排序算法的执行过程。给出冒泡排序算法的执行过程。囤冲倍骇认厘帖羡涉军箍然榨雕雌辅全辊辉燕品忻蜂沏榴势谜达绊晓称执第3章数据结构第3章数据结构冒泡排序的效率分析冒泡排序的效率分析若若待待排排序序的的元元素素为为正正序序，则则只只需需进进行行一一趟趟排排序序，比比较较次次数数为为（n-1）次，移动元素次数为）次，移动元素次数为0；若若待待排排序序的的元元素素为为逆逆序序，则则需需进进行行n-1
58、趟趟排排序序，比比较较次次数数为为(n2-n)/2，移动次数为，移动次数为3(n2-n)/2，最坏情况比较最坏情况比较n(n-1)/2因因此此冒冒泡泡排排序序算算法法的的时时间间复复杂杂度度为为O（n2）。由由于于其其中中的的元元素移动较多，所以属于内排序中速度较慢的一种。素移动较多，所以属于内排序中速度较慢的一种。涣簇汪姜遭馈姆车檬粮晚铅啄油物劝毁绸三仔闹藐东奸椭能咒锰挺强最建第3章数据结构第3章数据结构6.3.2 快速排序快速排序基本思想是：取待排序序列中的某个元素（一般第一个元素）基本思想是：取待排序序列中的某个元素（一般第一个元素）作为基准，通过一趟排序，将待排元素分为左右两个子序列，
59、作为基准，通过一趟排序，将待排元素分为左右两个子序列，左子序列元素的排序码均小于或等于基准元素的排序码，左子序列元素的排序码均小于或等于基准元素的排序码，右子序列的排序码则大于基准元素的排序码，右子序列的排序码则大于基准元素的排序码，然后分别对两个子序列继续进行然后分别对两个子序列继续进行快速快速排序，直至整个序列有序。排序，直至整个序列有序。元素的比较和交换是从两端向中间进行的，排序码较大的元素元素的比较和交换是从两端向中间进行的，排序码较大的元素一次就能够交换到后面，排序码较小的记录一次就能够交换到一次就能够交换到后面，排序码较小的记录一次就能够交换到前面，记录每次移动的距离较远，因而总的
60、比较和移动次数较前面，记录每次移动的距离较远，因而总的比较和移动次数较少。少。 撤枉抖认迈桶柬贼抄捅见刚篡丛枯泡溉琐酒认症锭准跌碘跪蛋苇卑弦处搭第3章数据结构第3章数据结构例如，给定排序码为：（46，55，13，42，94，05，17，70），具体划分如图7-4所示。姜挣逮尼母附袭琼帽泪泪摩收哟迁旷粤腆痉携氛紧仗紧渠冰嗜肋囚拐淳成第3章数据结构第3章数据结构3快速排序的效率分析快速排序的效率分析若若快快速速排排序序出出现现最最好好的的情情形形（左左、右右子子区区间间的的长长度度大大致致相相等等），则则结结点点数数n与与二二叉叉树树深深度度h应应满满足足log2nhlog2n+1，所所以以总总的
61、的比比较较次次数数不不会会超超过过(n+1)log2n。因因此此，快快速速排排序序的的最最好好时时间复杂度应为间复杂度应为O（nlog2n）。）。已经证明，快速排序的平均时间复杂度也为O（nlog2n）。若若快快速速排排序序出出现现最最坏坏的的情情形形（每每次次能能划划分分成成两两个个子子区区间间，但但其其中中一一个个是是空空），则则这这时时得得到到的的二二叉叉树树是是一一棵棵单单分分枝枝树树，得得到到的的非非空空子子区区间间包包含含有有n-i个个(i代代表表二二叉叉树树的的层层数数（1in）元元素素，每每层层划划分分需需要要比比较较n-i+2次次，所所以以总总的的比比较较次次数数为为（n2+
62、3n-4）/2。因此，。因此，快速排序的最坏时间复杂度为O(n2)。快速排序所占用的辅助空间为栈的深度，故最好的空间复杂度为O（log2n），最坏的空间复杂度为O(n)。快速排序是一种不稳定的排序方法。 铱克楞练靖酿桔闯哈融鄙刮豫晃追彬瞒佰搀麦彭乔宰禁违浆宋可出琶利公第3章数据结构第3章数据结构64选择排序选择排序 6 . 4.1 直接选择排序基本思想基本思想直直接接选选择择排排序序是是一一种种简简单单的的排排序序方方法法。基基本本思思想想是是：第第一一次次从从array0arrayn-1中中选选取取最最小小值值，与与array0交交换换，第第二二次次从从array1arrayn-1中中选选取
63、取最最小小值值，与与array1交交换换，第第三三次次从从array2arrayn-1中中选选取取最最小小值值，与与array2交交换换，第第i次次从从arrayi-1arrayn-1中中选选取取最最小小值值，与与arrayi-1交交换换，,第第n-1次次从从arrayn-2arrayn-1中中选选取取最最小小值值，与与arrayn-2交交换换，总总共共通通过过n-1次次，得得到到一一个个按按排排序序码码从从小小到到大大排列的有序序列排列的有序序列。例例如如，给给定定n=8，数数组组R中中的的8个个元元素素的的排排序序码码为为：（8，3，2，1，7，4，6，5），则直接选择排序过程如图），则直
64、接选择排序过程如图7-5所示。所示。杠咳认盗逆驳翌屏炭铁增俘呢虐京仑仆富扶净札腮帘枪奖施杭芳缕英蛀浊第3章数据结构第3章数据结构煌誓然奠秩兵挤屏昂斜聊交祸鸯袄晋装竖某搔别达垢状言班殿遵得炽铝宪第3章数据结构第3章数据结构直接选择排序的效率分析直接选择排序的效率分析在在直直接接选选择择排排序序中中，共共需需要要进进行行n-1次次选选择择和和交交换换，每每次选择需要进行次选择需要进行n-i次比较（次比较（1in-1），而每次交换最），而每次交换最多需多需3次移动，因此，总的比较次数次移动，因此，总的比较次数C=(n2-n)/2，总的移动次数总的移动次数M=3(n-1)。直直接接选选择择排排序序的的
65、时时间间复复杂杂度度为为O(n2)数数量量级级，所所以以当当记记录录占占用用的字节数较多时，通常比直接插入排序的执行速度要快一些的字节数较多时，通常比直接插入排序的执行速度要快一些。最坏情况比较最坏情况比较n(n-1)/2畅债瀑秧砷蒂合保遮滞睫斜疯携厨柔参桶拣筛坛泵伺赊涧橡烤忌婚猪相题第3章数据结构第3章数据结构75归并排序归并排序1、基基本本思思想想：将将两两个个有有序序子子区区间间（有有序序表表）合合并并成成一一个个有有序序子子区区间间，一一次次合合并并完完成成后后，有有序序子子区区间间的的数数目目减减少少一一半半，而而区区间间的的长长度度增增加加一一倍倍，当当区区间间长长度度从从1增增加
66、加到到n（元元素个数）时，整个区间变为一个，即为有序序列素个数）时，整个区间变为一个，即为有序序列.端砰万台帚铜壬渺疮校惰绘肪佑语楼寐付洋蕴解俞票佯化塑裔徘鹅巧装番第3章数据结构第3章数据结构例如，给定排序码46，55，13，42，94，05，17，70，二路归并排序过程如图7-10所示。算法P284衡筛构址毫怂亿二盲烘淀冯须长煌冒蔫莉抛龋匪恳癌庞少整运兹鸟潦拂株第3章数据结构第3章数据结构归并排序的效率分析归并排序的效率分析归并排序的时间复杂度为归并排序的时间复杂度为O(nlog2n)。归归并并排排序序时时，需需要要利利用用与与待待排排序序数数组组相相同同的的辅辅助助数数组组作作临临时时单单元元，故故该该排排序序方方法法的的空空间间复复杂杂度度为为O(n)，比比前前面面介介绍绍的的其其它排序方法占用的空间大。它排序方法占用的空间大。已斋方脉蓝裴赁襄涸类难攻淆洁当鸦觅氏瞪嚼丹赔约膀蹭奋幕毫呼即蛛畏第3章数据结构第3章数据结构
