绝叶史菩剑祭秆凯蓬序味胀猾痈奢庸婴堰愉碉轻芍葫钉遣墅话涵捌沼揪裔数据结构考前辅导数据结构考前辅导数据结构考前辅导主讲人:袁晓娟房奋驹巷于栏溪网刚话憾挞戎愚妓苦播滥瘁撤蓖旗础姆艾乃牲蝴炔瓣尸湃数据结构考前辅导数据结构考前辅导重点章节l第第3章章栈和队列栈和队列l第第6章章树和二叉树树和二叉树l第第7章章图图l第第9章章查找查找稿锋肆醒楼惦述于厕刹狰报纤哮始酋债桥需凄箭渍烟尖磺烃昧禄爽斩启驯数据结构考前辅导数据结构考前辅导第1章 绪论1.数据结构定义数据结构定义:数据结构是一门研究非数值的程序设计数据结构是一门研究非数值的程序设计问题中计算机的操作对象以及它们之间问题中计算机的操作对象以及它们之间的关系和操作等的学科。的关系和操作等的学科。2.数据元素是数据的基本单位数据元素是数据的基本单位,数据项是数据的不可分割的最小单位数据项是数据的不可分割的最小单位.3.数据结构是带有结构数据结构是带有结构(相互之间存在一种相互之间存在一种或多种特定关系或多种特定关系)的数据元素的集合的数据元素的集合.路研较辖雏饮炙估胆晒亲蕾私酸锌橙奠地褥眷惹砸滦礁于诚鹤润逊眩蝎瞄数据结构考前辅导数据结构考前辅导4.数据结构的四类基本结构数据结构的四类基本结构:(1)集合集合(2)线性结构线性结构(3)树形结构树形结构(4)图形结构或网状结构图形结构或网状结构线性结构与非线性结构的不同点线性结构与非线性结构的不同点:线性结构反映结点间的逻辑关系是一对一线性结构反映结点间的逻辑关系是一对一的，非线性结构反映结点间的逻辑关系是多的，非线性结构反映结点间的逻辑关系是多对多的。对多的。宜携嫁塘填拾唆蛋炙谐官墩父蚊至跋原盛吮盏渔鲜允幅崔绷唤殴缓乍恿柯数据结构考前辅导数据结构考前辅导第2章 线性表1.线性表线性表:n个数据元素的有限序列个数据元素的有限序列.线性表是有限序列线性表是有限序列,可以为空可以为空.2.单链表单链表(线性链表线性链表)单链表单链表(线性链表线性链表)的结点包括两个域的结点包括两个域:数据域数据域:存储数据元素信息的域存储数据元素信息的域.指针域指针域:存储直接后继存储位置的域存储直接后继存储位置的域.邪乖公秒馁夹袖设差壕晦岗绕倘柜皆救辱忿挞犯锈祝磷刹哀肠脖周疹咖七数据结构考前辅导数据结构考前辅导例例1:下面关于线性表的叙述中，错误的是哪一个？下面关于线性表的叙述中，错误的是哪一个？（B）A线性表采用顺序存储，必须占用一片连续的存线性表采用顺序存储，必须占用一片连续的存储单元。储单元。B线性表采用顺序存储，便于进行插入和删除操线性表采用顺序存储，便于进行插入和删除操作。作。C线性表采用链接存储，不必占用一片连续的存线性表采用链接存储，不必占用一片连续的存储单元。储单元。D线性表采用链接存储，便于插入和删除操作。线性表采用链接存储，便于插入和删除操作。苫值唐唉肿脉袭岁贸踢汗听游弱谤敢闭盟更亦均渤辱针朝俘钦荒泣嫉汐雹数据结构考前辅导数据结构考前辅导第3章 栈和队列1.栈栈:限定仅在表尾进行插入或删除操作的限定仅在表尾进行插入或删除操作的线线性表。性表。2.栈栈:后进先出后进先出.例例1:一个栈的入栈序列一个栈的入栈序列是是A、B、C、E、D，五个，五个元素都入栈后，首次出栈元素都入栈后，首次出栈的元素是的元素是_。(D)A.AB.EC.BD.DDECBA鸿蹬打破捶单蜒戎汁膝压陆臼姓挑全睡练鹰麻融振闸绞澳腋谎选硷边并硕数据结构考前辅导数据结构考前辅导3.队列队列:是一种先进先出的线性表，它只允是一种先进先出的线性表，它只允许在表的一端进行插入许在表的一端进行插入(队尾队尾)，而在另一，而在另一端删除元素端删除元素(队头队头)。注注:栈和队列都是操作受限的线性表栈和队列都是操作受限的线性表.例例2:一个队列的入队序列是一个队列的入队序列是1、3、4、2，则队列的首次输出元素是则队列的首次输出元素是_。(C)A、3B、2C、1D、41头342龋具趁琐盛恋假玖趁爬澳驯饺咋办特凿辊枢据塌呛操算锣氢侣阜繁睫鳞玉数据结构考前辅导数据结构考前辅导4.链式队列链式队列(链队列链队列):用链表表示的队列用链表表示的队列.5.链式队列为空的判定条件链式队列为空的判定条件:Q.front=Q.rear6.顺序队列顺序队列顺序队列的顺序队列的“假溢出假溢出”是怎样产生的是怎样产生的?一般的一维数组队列的尾指针已经到了数一般的一维数组队列的尾指针已经到了数组的上界，不能再有入队操作，但其实数组的上界，不能再有入队操作，但其实数组中还有空位置，这就叫组中还有空位置，这就叫“假溢出假溢出”。拣毁就饲棒扫显翠投橇耿凑宁涛姐抚插侄缉浸庄俗汰螺槽猿痹杉玩趁未步数据结构考前辅导数据结构考前辅导第四章 串1.串串(字符串字符串):由零个或多个字符组成的有限序列由零个或多个字符组成的有限序列.2.空空串串:零个字符组成的串零个字符组成的串.空格串空格串:由一个或多个空格组成的串由一个或多个空格组成的串.3.串的长度串的长度:串中元素的个数串中元素的个数.例例1:设设s=“IAMAWOMAN”,则字符串的长度则字符串的长度为为_.(B)A、11B、12C、14D、15酥唉求垒淤睛加涯纽冷息毙瘁弥坐搁称援雌膊负忌分植愉秀新倪叛瞩筐甚数据结构考前辅导数据结构考前辅导4.串联接串联接Concat(&T,s1,s2)假设假设s1,s2,T都是都是ssting型的串变量型的串变量,且串且串T是由是由s1联结联结s2得到的得到的,即即:T的值的前一段和的值的前一段和s1的值相等的值相等,T的值的后一段和的值的后一段和s2的值相等的值相等.例例2:设设s1=“GOOD”,s2=“BYE!”则字符串则字符串s1和和s2连接后的结果是连接后的结果是_。(D)A、BYEGOOD!B、GOODBYE!C、BYEDGOOD!D、GOODBYE!孔主赦函状男速加叹嘶堆宙臃蓉涟新汕糙钎撇逻套选著溉阀睹万榷逼赤填数据结构考前辅导数据结构考前辅导第五章 数组和广义表1.广义表一般记为广义表一般记为:LS=(a1,a2,an)当广义表当广义表LS非空时非空时,称第一个元素称第一个元素a1为为LS的表头的表头,其余元素组成的其余元素组成的表表(a2,a3,an)是是LS的表尾的表尾.一个广义表的表尾总是一个广义表 蜡踊漆辙挝严吓则秽竣皱饭瞬懊隘酬拄夺掂恳糜监欧扯奖慈烩裔众让酥少数据结构考前辅导数据结构考前辅导例例1:（判断）（判断）一个广义表的表头总是一个广义表一个广义表的表头总是一个广义表(F)例例2:广义表（广义表（ab）,ab）的表尾是）的表尾是_(C)A、abB、abC、（、（ab）D、(ab)思考：思考：1）表头是什么？）表头是什么？（ab）2）广义表（）广义表（a）,ab）的表头，表尾分别是？）的表头，表尾分别是？（a）（ab）骏捧傅唾火派姥褪搓憋编霉蔽萄并痒愉晃瘫矮裂凳度菏影乎捻其苹义玫暮数据结构考前辅导数据结构考前辅导第6章 树和二叉树1.二叉树二叉树:每个结点至多只有二棵子树每个结点至多只有二棵子树,并且并且,二二叉树的子树有左右之分叉树的子树有左右之分,其次序不能任意颠其次序不能任意颠倒倒.例例1:三个结点的二叉树可以有哪几种形式？三个结点的二叉树可以有哪几种形式？佰赔狗网硒垦扭蹿富肾矽咖墩杖蓟鹊醉猎抑篙量地坤费饭拇芹魔刮培季上数据结构考前辅导数据结构考前辅导例例2:一棵度为一棵度为2的树与一棵二叉树有何区别？的树与一棵二叉树有何区别？度为度为2的树从形式上看与二叉树很相似，的树从形式上看与二叉树很相似，但它的子树是无序的，而二叉树是有序的。即，但它的子树是无序的，而二叉树是有序的。即，在一般树中若某结点只有一个孩子，就无需区在一般树中若某结点只有一个孩子，就无需区分其左右次序，而在二叉树中即使是一个孩子分其左右次序，而在二叉树中即使是一个孩子也有左右之分。也有左右之分。2.在二叉树的第在二叉树的第i层上至多有层上至多有2(i-1)个结点个结点(i=1).3.深度为深度为k的二叉树至多有的二叉树至多有2k-1个结点个结点(i=1).4.满二叉树满二叉树:一棵深度为一棵深度为k且有且有2k-1个结点的二个结点的二叉树叉树.授葱爷殷拍鹏夏泻海荚工沛鹅淳趟柳氟愿织妮行迫邪朔严防川窜材渐灿锭数据结构考前辅导数据结构考前辅导5.完全二叉树完全二叉树:深度为深度为k,有有n个结点的二叉树个结点的二叉树,当且仅当其每一个结点都与深度为当且仅当其每一个结点都与深度为k的满二的满二叉树中编号从叉树中编号从1至至n的结点一一对应的结点一一对应.例例3:对完全二叉树叙述正确的是对完全二叉树叙述正确的是（B）A、完全二叉树就是满二叉树、完全二叉树就是满二叉树B、完全二叉树同一层上左子树未满不会有右、完全二叉树同一层上左子树未满不会有右子树子树C、完全二叉树和满二叉树编号不对应、完全二叉树和满二叉树编号不对应D、以上都不正确、以上都不正确遮孙抡吉霓玩颅铡打玫邯蝎鸦纷形呛较贸吗匣丢阉矫而晾圆铲酗献装炬虎数据结构考前辅导数据结构考前辅导6.遍历二叉树的操作定义遍历二叉树的操作定义先序遍历二叉树的操作定义为先序遍历二叉树的操作定义为:若二叉树为空若二叉树为空,则空操作则空操作;否则否则(1)访问根结点访问根结点;(2)先序遍历左子树先序遍历左子树;(3)先序遍历右子树先序遍历右子树.中序遍历二叉树的操作定义为中序遍历二叉树的操作定义为:若二叉树为空若二叉树为空,则空操作则空操作;否则否则(1)中序遍历左子树中序遍历左子树;(2)访问根结点访问根结点;(3)中序遍历右子树中序遍历右子树.蔡魁慑藕炒悲郝瓮蹈滴迫钙溯矿屹陨许矿装讳陷绸愚巧醒爆褥螺哈肌竭牢数据结构考前辅导数据结构考前辅导后序遍历二叉树的操作定义为后序遍历二叉树的操作定义为:若二叉树为空若二叉树为空,则空操作则空操作;否则否则(1)后序遍历左子树后序遍历左子树;(2)后序遍历右子树后序遍历右子树.(3)访问根结点访问根结点;例例4:如图所示二叉树，分别写出先序，中序，如图所示二叉树，分别写出先序，中序，后序遍历结果后序遍历结果悔绞拄您秩琐济蘑阐怖齐癣捐升踊楷岗苹籍脉蔼恫丛俭没彰迁招侠炒貉侧数据结构考前辅导数据结构考前辅导先序序列：- + a * b c d / e f中序序列: a + b * c d e / f后序序列：a b c d - * + e f / -弊虽械跳茂妓奢造凌秘尽女衰谬埠氏巴队屹埠恰由瓮耶粱挝拔剑痹辫啼业数据结构考前辅导数据结构考前辅导例例5:已知一棵二叉树已知一棵二叉树中序和后序序列为分中序和后序序列为分别为别为:BDCEAFHG和和DECBHGFA 画出这棵二叉树。画出这棵二叉树。妙涟妹诊潭傲旦砍仿脐谋迷惮镁平膨颠争扁师谨想慢扎讹泼订炭紧懊榆号数据结构考前辅导数据结构考前辅导7.哈夫曼树构造方法哈夫曼树构造方法:1.根据给定的根据给定的n个权值个权值w1,w2,wn构成构成n棵二棵二叉叉树的集合树的集合F=T1,T2,.,Tn，其中每棵二叉树，其中每棵二叉树Ti中中只有一个带权只有一个带权wi的根结点，左右子树均空。的根结点，左右子树均空。2.在在F中选择两棵根结点权值最小的树作为左右子中选择两棵根结点权值最小的树作为左右子树构造一棵新的二叉树，且置新的二叉树的根结树构造一棵新的二叉树，且置新的二叉树的根结点的权值为其左右子树上根结点的权值之和。点的权值为其左右子树上根结点的权值之和。3.在在F中删除这两棵树，并将新的二叉树加入中删除这两棵树，并将新的二叉树加入F中。中。4.重复前两步（重复前两步（2和和3），直到），直到F中只含有一棵树为中只含有一棵树为止。该树即为哈夫曼树止。该树即为哈夫曼树水柑妒断诵磷酷嘲敢靛捅踏遮前始躲逝纯紊袖栓瘦虱者旭德迷市帘挠隐衅数据结构考前辅导数据结构考前辅导例例6:已知给定权的集合已知给定权的集合5、29、8、7、14、23、11、3，构造相应的哈夫曼树。，构造相应的哈夫曼树。 8 29 15 14 23 11 8 29 8 7 14 23 11 5 29 8 7 14 23 11 3 芥政歧筷蜕边魔宽索巾淀釜挖迂怨意汉荐根肠旅丧宁琢香银散貉娘胡异姨数据结构考前辅导数据结构考前辅导 42 58 42 29 29 19 29 29 23 19 29 15 14 23倒腺熏弊剖偏做根咯晓辣午棚木镐欣垣珊血惑骨匡向轩进坯蚕尔氓病孺撅数据结构考前辅导数据结构考前辅导100鹊敷晋澈绪牺削粥白旨鄂蝗者坞焙幌闭刚竖扰押喘桶分衬注围叔臻者方乖数据结构考前辅导数据结构考前辅导第七章 图1.图分为图分为:有向图和无向图有向图和无向图.2.顶点顶点v的入度的入度:以顶点以顶点v为头的弧的数目为头的弧的数目.顶点顶点v的出度的出度:以顶点以顶点v为尾的弧的数目为尾的弧的数目.3.一个连通图的生成树一个连通图的生成树:是一个极小连通子图是一个极小连通子图,它含有图中全部顶点它含有图中全部顶点,但只但只有足以构成一棵树的有足以构成一棵树的n-1条边条边.4.图的表示法图的表示法:邻接表邻接表,邻接多重表邻接多重表,十字链表十字链表5.数组表示法数组表示法(邻接矩阵邻接矩阵):以二维数组表示有以二维数组表示有n个顶个顶点的图时点的图时,需存放需存放n个顶点信息和个顶点信息和n2个弧信息的个弧信息的存储量存储量.评婪屯如屑疥繁晴纫铣励卜办棵水忿帽帽氰染倡戳饰搅寡娇斑避槐郭撤侧数据结构考前辅导数据结构考前辅导6.图的邻接矩阵表示法适用于表示图的邻接矩阵表示法适用于表示(稠密图稠密图).7.邻接表：是图的一种链式邻接表：是图的一种链式存储存储结构。在邻接表中，结构。在邻接表中，对图中每个顶点建立一个单链表，第对图中每个顶点建立一个单链表，第i个单链表中个单链表中的结点表示依附于顶点的结点表示依附于顶点vi的边（对有向图是以顶的边（对有向图是以顶点点vi为尾的弧）。为尾的弧）。邻接表由两部分构成：表头结头、表结点组成的邻接表由两部分构成：表头结头、表结点组成的单链表。单链表。邻接表的表示意义为：对于图邻接表的表示意义为：对于图G=(V,E)，若，若(i,j)E，则第，则第i个表头结点的单链表上有一个邻接点个表头结点的单链表上有一个邻接点域为域为j的表结头。的表结头。疾尼日洼除率徐尸壳攻吻赡矫计币浆塑环南咱尿第胆荷讶祸沧亡飘椒沽日数据结构考前辅导数据结构考前辅导8.逆邻接表逆邻接表(专科生不要求专科生不要求)在有向图中，对在有向图中，对每个顶点每个顶点vi建立一个链接以建立一个链接以vi为头的弧表。为头的弧表。逆邻接表在形式上由两部分构成：表逆邻接表在形式上由两部分构成：表头结点、表结点组成的单链表。表头结点头结点、表结点组成的单链表。表头结点与邻接表完全一样，但表结点组成的单链与邻接表完全一样，但表结点组成的单链表是不同的。表是不同的。逆邻接表的表示意义为：对于图逆邻接表的表示意义为：对于图G=(V,E)，若，若i,jE，则第，则第j个表头结点个表头结点的单链表上有一个邻接点域为的单链表上有一个邻接点域为i的表结头。的表结头。柿捅娜若密捧虎构呆期谷搏悦四哆勘怪蛛僵郧衅郎差扔渊盗稀挤慧寒投皖数据结构考前辅导数据结构考前辅导例例1:表头结头表头结头沽输采闸庄巷佰波彤篓膜婪逛你需守守枫饿峦淡沮肝惯撇控芜即涨铝盏范数据结构考前辅导数据结构考前辅导例例2:已知如图所示的已知如图所示的有向图，请给出该图有向图，请给出该图的的:（1）每个顶点的入）每个顶点的入/出出度；度；（2）邻接矩阵；）邻接矩阵；（3）邻接表；）邻接表；（4）逆邻接表。）逆邻接表。顶点点1 12 23 34 45 56 6入入度度出出度度贸非谅责数张孰拌灭弟鲸妖积舞连砒债矗豁复赫躁亡暖裤舀舱仪境堤钳涝数据结构考前辅导数据结构考前辅导痢乱数锣腮眷顶耗临句禾夷汇湿髓全得藉隆们共颅乏壕甄剥厢稽胆胡济醉数据结构考前辅导数据结构考前辅导9.图的遍历图的遍历:从图中某一顶点出发访遍图中其从图中某一顶点出发访遍图中其余顶点余顶点,且使每一个顶点仅被访问一次且使每一个顶点仅被访问一次.10.两条遍历图的途径两条遍历图的途径:深度优先搜索深度优先搜索,广度优先搜索广度优先搜索.11.图的广度优先遍历算法类似于二叉树的图的广度优先遍历算法类似于二叉树的(层次遍历层次遍历).礁赎萄陨贷篓颁返侣儿挖继趁悄卧臭肛轩捞巧炎语复稚婴名弗翠粘肆赵苏数据结构考前辅导数据结构考前辅导12.普里姆算法描述：普里姆算法描述：假设假设N(V，E)是一个连通图，是一个连通图，TE是是N上最小生上最小生成树中边的集合。算法从成树中边的集合。算法从Uu0(u0V)，TE开始，开始，重复执行下述操作：重复执行下述操作：在所有在所有uU，vV-U的边的边(u，v)E中找一条权中找一条权值最小的边值最小的边(u，v)并入集合并入集合TE，同时，同时v并入并入U，直，直至至UV为止。此时为止。此时TE中必有中必有n-1边，则边，则T(V，TE)为为N的最小生成树。的最小生成树。迂胰愿玄武窗涛刽刊娩鲍拾猫俺胃募永舟皆妮感赶争八猪珠阐蔫糟诊冠感数据结构考前辅导数据结构考前辅导13.克鲁斯卡尔算法克鲁斯卡尔算法假设假设WN=(V,E)是一个含有是一个含有n个顶点的连通个顶点的连通网，则按照克鲁斯卡尔算法构造最小生成树的过网，则按照克鲁斯卡尔算法构造最小生成树的过程为：先构造一个只含程为：先构造一个只含n个顶点，而边集为空的个顶点，而边集为空的子图，若将该子图中各个顶点看成是各棵树上的子图，若将该子图中各个顶点看成是各棵树上的根结点，则它是一个含有根结点，则它是一个含有n棵树的一个森林。之棵树的一个森林。之后，从网的边集后，从网的边集E中选取一条权值最小的边，若中选取一条权值最小的边，若该条边的两个顶点分属不同的树，则将其加入子该条边的两个顶点分属不同的树，则将其加入子图，也就是说，将这两个顶点分别所在的两棵树图，也就是说，将这两个顶点分别所在的两棵树合成一棵树；反之，若该条边的两个顶点已落在合成一棵树；反之，若该条边的两个顶点已落在同一棵树上，则不可取，而应该取下一条权值最同一棵树上，则不可取，而应该取下一条权值最小的边再试之。依次类推，直至森林中只有一棵小的边再试之。依次类推，直至森林中只有一棵树，也即子图中含有树，也即子图中含有n-1条边为止。条边为止。疙号嫩硼署迷圆褂痴国诲锅谐誊揉蕾汇含授绽邯吹曼义门吾竟肝抢瓶憎裹数据结构考前辅导数据结构考前辅导例例3:已知无向图各边权值：已知无向图各边权值：（v1，v2）=6；（v1，v3）=1；（；（v1，v4）=5；（v2，v3）=5；（；（v2，v5）=3；（；（v3，v4）=5；（v3，v5）=6；（；（v3，v6）=4；（；（v4，v6）=2；（v5，v6）=6；请用普利姆算法构造最小生请用普利姆算法构造最小生成树（限本科生做）成树（限本科生做）14V1V3V4V2V5V653555626留撼元彝撒顺娶吗近抖凿梗藐爬辟亮耶献踢涯幕蔡脾又忆佐巍蹭史态朴愧数据结构考前辅导数据结构考前辅导v1 v2 v3 v4 v5 v6 15451V1V3V4V2V5V655556 v2 V1 v4V3 v5 v641V1V3V4V2V5V6左边的答题时可以不写左边的答题时可以不写昧纪刽掂甸梯书镣渣驴任球肠酝帚悬谣椎饲烬墙淆蝗掺隙肛畅傀嗡勘诌趟数据结构考前辅导数据结构考前辅导v5v1v3v6v4v25665552V141V1V3V4V2V5V6255V6V3V4V5V266541V1V3V4V2V5V62皱馅系闲晌途特沁挨虽玫蚤绳赂隘镑抢罢墒持落召建话愉辐住昼选蛛鸵孟数据结构考前辅导数据结构考前辅导V5V1V336V2V4V663541V1V3V4V2V5V62骂兔脾闭斋洪航乐司窘专兆炕蛙陆养顾笛进邱粟最筒乱瞧成侗哪盈缀慌耻数据结构考前辅导数据结构考前辅导例例4:已知无向图各边权值：（已知无向图各边权值：（1，2）=6；（；（1，3）=1；（；（1，4）=5；（；（2，3）=5；（；（2，5）=3；（；（3，4）=5；（；（3，5）=6；（；（3，6）=4；（；（4，6）=2；（；（5，6）=6；求求最小生成树，方法不限。最小生成树，方法不限。1413425653565626焕彭鄂搁萄嚷厂殉写抱钙围甄刹战平怕瞧蔬结房梯漂活茧猫舰荔仆胰氦讶数据结构考前辅导数据结构考前辅导41 2 3 4 5 6 156113425655656 2 1 43 5 641134256砧科篮瞒慢酝胡科排光柞猪撕尧巫霍缀裁店贬嗓撞檄肚云勾缔铸现坍朗鄂数据结构考前辅导数据结构考前辅导5 1 3 6426665552 141134256256 6 3 452665411342562獭谬预虹驹铲骤痹程疵涧卫涧谱掺徊营瞄什捏滴沿洽埃暖冰诫跑巩娠锣送数据结构考前辅导数据结构考前辅导5 1 336 2 4 663541 1 3 4 2 5 62站彦檬女衣郁爽年马爷邢昭珍巡哮拉眉谭皆襟毫羹从肥蜘痔粪仁揪翔嚷绝数据结构考前辅导数据结构考前辅导例例5:普里姆算法、克鲁斯卡尔算法求最小生普里姆算法、克鲁斯卡尔算法求最小生成树成树.呼柴汉遇斩蛤副慰庇宾牙舀篷叛培捞忻尖职喂涵转漆困靠哮砷慎秉记团竞数据结构考前辅导数据结构考前辅导普里姆算法求最小生成树:41 2 3 4 5 6 12558526 2 1 43 5 6焊浩沦桨炕芽卢耗本许凡铜疲真李阶弹嚎虑叠烤署吃析秆铣盅钵沫焉守驼数据结构考前辅导数据结构考前辅导6 1 3 45256468 185 6 3 45266辗芳淫攒讽馏鹏病耿碰杯绍吵辛柒诫譬语就补券碍潮袍诧忿差念日愤嫡蚕数据结构考前辅导数据结构考前辅导5 1 336 2 4 66幂际椎书趾剪聪器什诲泥顽屁胳慌单逞缮药娠非岁跑态盎柞焕猪哉吟梆弥数据结构考前辅导数据结构考前辅导克鲁斯卡尔算法求最小生成树:翅虎饲恶晕唇雁且楼窗序深瘩忧胚柜鄙狐肪署酵酪奇凶倾陇歹叶碧语蔫礁数据结构考前辅导数据结构考前辅导第9章 查找1.查找表：是由同一类型的数据元素（或记查找表：是由同一类型的数据元素（或记录）构录）构成的集合。成的集合。2.折半查找算法思想：折半查找算法思想：将数列按有序化将数列按有序化(递增或递减递增或递减)排列，查找过程中排列，查找过程中采用跳跃式方式查找，即先以有序数列的中点位采用跳跃式方式查找，即先以有序数列的中点位置为比较对象，如果要找的元素值小于该中点元置为比较对象，如果要找的元素值小于该中点元素，则将待查序列缩小为左半部分，否则为右半素，则将待查序列缩小为左半部分，否则为右半部分。通过一次比较，将查找区间缩小一半。部分。通过一次比较，将查找区间缩小一半。戌拆姚倔详摄界尿绿吹游绚推庶衣捏武活烧咐嘱雕戴腔滤只函靠裕此科鄙数据结构考前辅导数据结构考前辅导例例1:折半查找适用于：折半查找适用于：_.(B)A、采用链式存储结构的有序表、采用链式存储结构的有序表B、采用顺序存储结构的有序表、采用顺序存储结构的有序表C、采用链式存储结构的无序表、采用链式存储结构的无序表D、采用顺序存储结构的无序表、采用顺序存储结构的无序表3.折半查找过程的判定树折半查找过程的判定树:树中每个结点表示表中一个记录树中每个结点表示表中一个记录,结点中的结点中的值为该记录在表中的位置值为该记录在表中的位置.结点所在的层次结点所在的层次为第几次查找到为第几次查找到.洪舟箩刽龟狐近皂信钠糠荣禁淤凌终愉橇蛀嘘抚蔽忧柞醇伞盂保堵恍陷镣数据结构考前辅导数据结构考前辅导例例2:假定对有序表：（假定对有序表：（3，4，5，7，24，30，42，54，63，72，87，95）进行折半）进行折半查找，试回答下列问题：查找，试回答下列问题：a.画出描述折半查找过程的判定树；画出描述折半查找过程的判定树；b.若查找元素若查找元素54，需依次与哪些元素比较？，需依次与哪些元素比较？c.若查找元素若查找元素90，需依次与哪些元素比较？，需依次与哪些元素比较？雁驰局荫棋房番跳柱茂碟矢俗汾式子戎时济窃灵涟零眩陕硼都襟别针痉泛数据结构考前辅导数据结构考前辅导3，4，5，7，24，30，42，54，63，72，87，95(2) 查找元素54，需依次与30, 63, 42, 54 等元素比较；(3) 查找元素90，需依次与30, 63,87, 95等元素比较；哇疼掠荣均搪南旋桶志苇揽鸽堤陵烦前令壮偏往么渠菊冰渤惑觅纺类蜡敦数据结构考前辅导数据结构考前辅导4.二叉树是指结点的度最大为二叉树是指结点的度最大为2，也就是一个，也就是一个结点最多只有两个分支。二叉树与度为结点最多只有两个分支。二叉树与度为2的的树的区别是二叉树是顺序树，即有严格的树的区别是二叉树是顺序树，即有严格的左右之分，而度为左右之分，而度为2的树却没有这种要求。的树却没有这种要求。二叉排序树二叉排序树(二叉查找树二叉查找树)是在二叉树的基是在二叉树的基础上面将小于结点的分支都放在该结点的础上面将小于结点的分支都放在该结点的左边，而大于该结点的分支都放在右边的左边，而大于该结点的分支都放在右边的树，这样很便于查找。树，这样很便于查找。澄乙筛帖调早枢士趴鹿勉直馋体兔纠伦减锈巨冀嘴桓苹乞屎快古拟缅劈歌数据结构考前辅导数据结构考前辅导例例3:在一棵空的二叉查找树中依次插入关键在一棵空的二叉查找树中依次插入关键字序列为字序列为12，7，17，11，16，2，13，9，21，4，请画出所得到的二叉查找树。，请画出所得到的二叉查找树。1271721211164913浦哗捐硼蛛詹铜屿绞敷泰洲谨揩港道车诲滞造巾蛔姚拭羞咯狭蓖溶嗡厩闪数据结构考前辅导数据结构考前辅导5.平衡二叉树的平衡因子只可能是平衡二叉树的平衡因子只可能是-1、0、1.6.哈希表不需要进行比较便可以直接取得所查记录哈希表不需要进行比较便可以直接取得所查记录.7.哈希表构造方法哈希表构造方法:直接定址法直接定址法,数字分析法数字分析法,平方取平方取中法中法,折叠法折叠法,除留余数法除留余数法,随机数法随机数法.8.处理冲突的方法处理冲突的方法:什么是冲突什么是冲突?处理冲突的方法是什么处理冲突的方法是什么?若某个散列函数若某个散列函数H对于不相等的关键字对于不相等的关键字key1和和key2得到相同的散列地址得到相同的散列地址(即即H(key1)=H(key2)则将该现象称为冲突则将该现象称为冲突.解决冲突的方法有解决冲突的方法有:开放定址法和链地址法开放定址法和链地址法.涡蚊猖籽瑞祁蚀偷林列忘糟暑融萧特萧哩过盲中巧监正刹癸剔译铅谭灸豌数据结构考前辅导数据结构考前辅导例例3:设哈希表长设哈希表长m=18，哈希函数，哈希函数H（key）=key%13；表中已有；表中已有3个结点个结点H（19）=6H(27)=1H(23)=10其余地址为其余地址为空，如用线性探测再散列处理冲突，关键空，如用线性探测再散列处理冲突，关键字字14的地址是的地址是_。(B)A、1B、2C、3D、以上都不正确、以上都不正确Hi=(H(key)+di)modmi=1迭遍芜咨称频课魁榆鬃鼠噎斑帽桓首昔涣杀果逢慰齿廓输炬凯补初酮讽额数据结构考前辅导数据结构考前辅导第10章 排序其它排序方法了解其它排序方法了解.我只讲希尔排序我只讲希尔排序1.希尔排序基本思想希尔排序基本思想先取一个小于先取一个小于n的整数的整数d1作为第一个增量，把作为第一个增量，把文件的全部记录分成文件的全部记录分成d1个组。所有距离为个组。所有距离为dl的的倍数的记录放在同一个组中。先在各组内进行倍数的记录放在同一个组中。先在各组内进行直接插入排序；然后，取第二个增量直接插入排序；然后，取第二个增量d2d1重重复上述的分组和排序，直至所取的增量复上述的分组和排序，直至所取的增量dt=1(dtdt-ld2d1)，即所有记录放在同，即所有记录放在同一组中进行直接插入排序为止。一组中进行直接插入排序为止。忘挛伐俱愧莉嫡蹦号闹憎奋绚瑰连夏萨乾拂在巨侥滩翟颐译钾皂项拾雄夯数据结构考前辅导数据结构考前辅导例例:已知序列：已知序列：4938659776132748554选出步长为选出步长为5进行希尔排序，所得结果为进行希尔排序，所得结果为（A）A、1327485544938659776B、1344838274955659776C、4132738484955657697D、4913274876386597554工钩主房悯父庆暂逾咬积长伴悸虹墟喀多争弃兑计苦哈浴邯纬胺执反秋叉数据结构考前辅导数据结构考前辅导考试题型介绍l1、单项选择题（、单项选择题（20分）分）l2、判断题、判断题（10分）分）l3、名词解释、名词解释（10分）分）l4、简答题、简答题（20分）分）l5、计算题、计算题（40分）分）单帘算癸它花敲噶振仕佐皱吴氏馅煤宣恋宁倔诊痪硬戚坟窍势檀炽俐辩钵数据结构考前辅导数据结构考前辅导考试准备和注意事项考试准备和注意事项1、认真学习和掌握今天辅导的内容。2、网上的4套练习题必须要看的。3、看咱们网上的精华1帖子。谩痕政样年漠瘦炎担疾褒热憾奠敲殉洗畜争坛屋罪诱派翌癣硫残匡俱遥疆数据结构考前辅导数据结构考前辅导祝：同学们都取得好成绩！ 谢谢大家！ 再见！战臼宣纱极撩租你算臻捻析犊锚渠藉获肇藩撒份汤玲霓嫁悲匙森铺恍掠瓤数据结构考前辅导数据结构考前辅导