复习数据结构A

数据结构

什么是数据结构基本概念和术语性能分析与度量第一章绪论学生成绩表格UNIX文件系统结构图/rootbinlibuseretcmathdsswyintaoxieStack.cppQueue.cppTree.cpp基本概念和术语数据(Data)是信息的载体，是描述客观事物的数、字符、以及所有能输入到计算机中，被计算机程序识别和处理的符号的集合。

数值性数据（整数、定点数、浮点数）非数值性数据（文字数据）四个基本结构集合线性结构树形结构网状结构数据的逻辑结构分类线性结构

线性表非线性结构

树图（或网络）例题：从逻辑上可以把数据结构分为____线性结构_____和_____非线性结构____。时间复杂度O(1):常数时间O(log2n)：对数时间O(n)：线性时间O(nlog2n)：线性对数时间O(n2):平方时间O(n3):立方时间O(2n):指数时间上述的时间复杂度的优劣次序如下（n>=16):O(1)<O(log2n)<O(n)<O(nlog2n)<O(n2)<O(n3)<O(2n)<O(3n)<O(n!)第二章线性表顺序表链表顺序表与链表的比较线性表定义：

n（0）个数据元素的有限序列，记作（a1,…ai-1,ai,ai+1,…,an）

其中,ai

是表中数据元素，n是表长度。特点:同一线性表中元素具有相同特性。相邻数据元素之间存在序偶关系。除第一个元素外，其他每一个元素有一个且仅有一个直接前驱。除最后一个元素外，其他每一个元素有一个且仅有一个直接后继。 例题:线性表是具有n个元素的____有限序列_____。顺序表定义：将线性表中的元素相继存放在一个连续的存储空间中。

存储结构：数组。特点：线性表的顺序存储方式。存取方式：顺序存取,随机存取顺序存储结构示意图458990674078

012345链表（LinkedList）链表是线性表的链接存储表示顺序表与链表的比较基于空间的比较存储分配的方式顺序表的存储空间是静态分配的链表的存储空间是动态分配的存储密度=结点数据本身所占的存储量/结点结构所占的存储总量顺序表的存储密度=1链表的存储密度<1顺序荷表与缸链表编的比课较基于绵时间纱的比础较存取神方式顺序辜表可鄙以随肚机存谋取，递也可盛以顺大序存坐取链表昆是顺警序存谷取的插入/删除冤时移陷动元萝素个区数顺序忠表平较均需扰要移事动近恭一半士元素链表乳不需析要移唱动元密素，叔只需越要修大改指序针栈队列递归第三拜章栈些和队柱列17栈(炒St贸ac品k各)（线迈性结染构）定义:是限宇定仅猴在表酬尾进弄行插碍入或盘删除劈燕操作速的线镰性表短。允许衫插入岸和删管除的俭一端称为辛栈顶(t芝op闲)，另绘一端称为浅栈底(b循ot屑to钳m)特点眠：后进音先出(L惕IF滤O)a1to肉pbo输tt姑oman....进栈出栈18例题栈的吴性质错是：__抗_后进悄先出__朵_，进编栈的怒一端繁成为__椒_栈顶__体_，出聚栈的嘉一端翁称为__事_栈顶__献_。栈的尚应用恋举例数制幻玉转换表达厅式求宗值20采用司对十楼进制泛数除8取余藏的方稼法，称可得散到八银进制膨数的揪倒序鞠。N能=竿(N链d齿iv壮d辉)×劳d夏+链N具mo涌d爷d例如锅：（13择48表)10=贴(2棵50御4)8，其筑运算众过程扛如下械：N店N授di土v牧8沈N扬m闷od失813艺48素16庄8笨4浊16眼8段2每1蹈0毫21激2景5煎2迷0介2计算顺序输出顺序21数制删转换十进睁制数源转换看为八谅进制故数。vo候id与c糟on涉ve毫rs敢io之n基()鞋{In弟it顾St短ac搂k(坝S)荷;sc催an赚f孔("干%d献",碌N)怜;wh贸il鹊e雹(N瓶)右{Pu紫sh轧(S骨,短N每%累8)哗;N炉=绣N/舍8;}wh温il沈e级(!逢St呢ac卸kE煮mp着ty辣(S窝))田{Po驾p(罚S,峰e)保;pr浑in伯tf暴(壮"比%d挖",掠e锅)迫;}}攻//私c郊on气ve遭rs著io骑n22例题锅：1.使用功除留汽余数溪法将10进制诊数45容6转换紫为8进制古数。答：45劝6/垒8结果施为57余数怖为057韵/8结果寒为7余数趣为17/怀8结果州为0余数骡为7转换黑结果努为8进制险数71颠02.请编盲写10进制朗转换齿为8进制辞数的参程序切。限于里二元法运算由符的拢表达却式定讲义:表达寨式::绳=夸(操作码数)福+疯(运算肾符)脏+赏(操作览数)操作吃数::匪=简单呜变量|表达勉式简单呆变量::窑=标识旅符|无符揪号整毕数Ex滋p鹊=骗S1打+理O世P夺+欺S2前缀复表示攀法OP+S1+S2中缀饭表示花法S1+OP+S2后缀劝表示效法S1+S2+OP表达谁式求湿值24例如:动E溪xp绿=ab+(cd管/衣e)f前缀淡式:+a罢bc赵/放d酱e吐f中缀件式:ab+cd浮/猫ef后缀辜式:a竿bc迈d喉e佣/f+表达趟式标芳识方沈法b-ca/*def*+25例题冲：请跟将a*蛛(b脾/c思+d崖*e桨)+按f*意g转换蓝为后兽缀表验达式答：1.胖b堆/cb香c/2.身d*互e败de脏*3.雹b/弟c+错d*纱e罗bc允/d访e*饲+4.使a*袖(b弊/c唇+d暗*e跪)淡ab旨c/码de骑*+岩*5.首f*俱g亮fg燥*6.a*伏(b罚/c浴+d愧*e端)+遣f*起ga怜bc弱/d宅e*采+*范fg炸*+递怀归定义若一早个对俩象部耀分地症包含板它自睁己,或用贡它自按己给凭自己匆定义,则称仿这个晕对象临是递姿归的椒；誉若一排个过涛程直玩接地歉或间谜接地德调用网自己,则称搅这个梦过程容是递竖归的怕过程。27例.搜索拾链表爽最后眠一个今结点缎并打奥印其短数值vo她id苦S谎ea锻rc秆h弃(窜Li哄st懒No蜓de吐*课f养)类{if痰(政f->li钓nk煮=计=殊NU黑LL马)pr臭in耗tf相(爽“%紫d\忽n”柴,叹f->da漫ta钥)研;el溉se胁S妈ea帖rc矩h弃(阁f->li炊nk兔)造;}fffffa0a1a2a3a4递归绵找链本尾28递归芬函数先调童用无后操酱作例vo毒idFu窗nc(c较ha怀rch){赛i吊f(ch<=‘z俗’){Fu貌nc(ch+1);co辨ut张<<ch;}}调用Fu贺nc(‘a篮’);输出zy猛xw束vu有ts罩rq岗po梯nm摇lk应ji育hg特fe辽dc虾ba例题虏：请惧给出年下面将程序肤运行闹结果vo听id妻F革un比c(朗ch予ar星c傻h){朗i约f(偿ch详<=僻‘z讽’){列c子ou嘉t<戚<c铸h;Fu削nc岂(c术h+懒1)带;co延ut程<<嫁ch抱;}}调用Fu课nc撑(‘梁a’及);答：ab妻cd桐ef痛gh销ij诱kl单mn慰op某qr饥st仇uv渴wx遮yzzy急xw晕vu后ts问rq呈po己nm陕lk傲ji者hg攀fe仿dc府ba第四赚章怠字符圾串(S插tr雀in工g)字符尝串是n具(蛾0区)个字隔符的饥有限瘦序列俭，记作S半:通“c1c2c3…cn”其中痒，S是串冶名字“c1c2c3…cn”是串晶值ci是串方中字时符n是串允的长忧度。例如,励S纸=虾“流Ts撤in俗gh即ua拌_U糟ni奖ve杯rs次it冻y”侵S的长帖度是19例题失：下面扰关于惜串的隙的叙摔述中沈，哪包一个腐是不欺正确代的？喊（B）A．串抗是字适符的许有限筋序列B．空弯串是攻由空财格构墨成的催串C．模炉式匹时配是绿串的忠一种杨重要均运算D．串旅既可德以采吼用顺通序存馒储，墙也可杨以采河用链渔式存吹储字符译串(S议tr柔in沃g)子串钥：如果榜字符局串S1是字瓣符串S的一唤部分个，则S1是S的子状串。空串淋和字跑符串即本身惧也是当字符贴串的溉子串第五尚章顶数组数标组定义相同蜘类型缩慧的数练据元来素的躬集合石。一维委数组兄的示例35释2湿7兄4伪9总18屈6抛0扬5拾4兼77玻83木4腐1铜020形1贺2缴3绘4柴5循6衰7慌8匆9一维沟数组一维努数组藏存储射方式352749186054778341020123456789llllllllll

LOC(i)=LOC(i-1)+l=a+i*lLOC(i)=

LOC(i-1)+l=a+i*l,i>0

a,i=0

a+i*la例题头：有翼一个彻一维服数组士，其两起始惨地址卫是20震0，每比个元哲素占3个存饭储单萌元，扩问下谎标为7的元杠素起竞始地藏址是搁多少蓄？答：俭因为伟数组段下标桑从0开始泉，下阔标为7的元松素前密面有7个元喇素，离每个菜元素左占3个存蛾储单长元，致一共罩占21个存骆储单老元，额再加艳上整牢个数关组的治起始董地址20粘0，下孟标为7的元览素起佳始地蚕址为22讨1.第六味章惭二叉兆树概念角和基泻本术蜓语二叉巴树霍夫浊曼树树的性概念屯和基仿本术挪语树的忠定义树是亚由n归(n0)个结博点的浴有限饱集合辈。如矩果n子=味0，称强为空局树；摊如果n容>杏0，则有且纺仅有霞一个铃特定煎的称框之为持根(R会oo暂t)的结折点，袄它只洒有直胳接后思继，沙但没刻有直宿接前眯驱；当n显>竞1，除改根以碍外的本其它匠结点活划分状为m花(m腹>厌0)个互匹不相怒交的猜有限累集T1,算T2,…柿,葵Tm，其金中每唤个集顽合本填身又生是一甲棵树俊，并海且称喂为根诊的子门树(S寻ub忌Tr捎ee普)。ACGBDEFKLHMIJ例如A只有弟根结扇点的沙树有13个结刮点的黄树其中重：A是根迟；其认余结旗点分填成三念个互艰不相得交的究子集杜，T1焰={遮B,凑E,喷F,爷K,霸L}；T2期={裂C,丧G}；T3思={巨D,碰H,侵I,驰J,第M}部,T1擦,T元2,抹T3都是滋根A的子润树，老且本僵身也炮是一壁棵树树的似基本图术语1层2层4层3层he伙ig鬼ht=妥4ACGBDEFKLHMIJ结点结点细的度叶结劲点分支揭结点子女双亲兄弟祖先子孙结点怜层次树的博深度有序树无序耕树结点尿：一林个数械据元酬素及优指向征其子螺树的拼分支浩。结点菠的度针：结沟点拥退有的肿子树赏个数早。叶结倾点：哨度为异零的抄结点章。子女歪：结舱点子古树的亏根。兄弟军：同荷一结沾点子箱女。祖先茶：根源到该屋结点晌路径棕上的光所有响结点蜡。子孙稼：某看结点逗为根凑的子舒树上饲的任负意结宽点。结点椅层次瘦：从浪根开君始，狼根为孔第一亦层，斧根的粱子女腊为第消二层触，以农此类厌推。树的罗深度典（高犹度）烛：树商中结挺点的荷最大棵层次比数。有序腐树：极树中剑结点蜜的子瓜树由吵左向内右有逮序。二叉含树(B轮in崭ar瓶y险Tr类ee滩)定义五种能形态一棵结二叉乱树是应结点古的一浪个有币限集棒合，逃该集上合或樱者为坡空，婆或者摘是由塌一个粥根结妙点加功上两通棵分沉别称醒为左民子树娇和右餐子树捏的、画互不瓜相交伟的二愧叉树额组成由。LLRR特点每个法结点芳至多捷只有显两棵芳子树角（二渐叉树庄中不存字在度银大于2的结佛点）性质对任升何一绑棵二悠叉树T,如果勤其叶寄结点勺数为n0,度为2的结川点数泛为n2,则n0＝n2＋1.证明泰：若顿度为1的结暖点有n1个，事总结股点个拦数为n，总肤边数椅为e，则粒根据垂二叉凑树的头定义洽，n相=剑n0+浆n1+丧n2e馋=梁2n2+刑n1=柿n-1因此挖，有2n2+歪n1=广n0+个n1+授n2-1n2=士n0-1柏n0=魄n2+将1例题甜：一田棵二诉叉树严中有8个度塞为0的结浮点，7个度溉为1的结敢点，摊问度上为2的结斧点个漠数有龄多少有？答：哄根据典题目婚描述n0=8，n1=7根据怠二叉缸树性眠质n0=牲n2+伯1有n2=n0-1只需腔将n0带入乞上式扛得n2=7霍夫魄曼树(H棕uf茫fm拌an籍T铃re踪蝶e)路径底长度(P遥at壤h杂Le堵ng编th降)两个碎结点岸之间兔的路径打长度PL是连暖接两底结点型的路象径上祖的分纺支数政。树的桶外部煌路径肤长度惠是各闲叶结蒙点(外结戒点)到根着结点阔的路价径长叛度之优和EP室L。树的掌内部陷路径爪长度批是各抹非叶约结点(内结孤点)到根匹结点蒸的路傲径长泪度之茧和IP率L。树的垮路径扎长度PL为=士E谋PL姐+锻I愤PL123456782345678树的搏外部纷路径对长度EP卡L均=喊3*挖1+雹2*刚3御=祸9树的隆外部匆路径疫长度EP止L姻=签1*萄1+踢2*骄1+张3*滤1+下4*扫1欠=碑101带权奖路径呆长度(We糟ig匪ht夹ed灰P陕at豪h傅Le租ng坊th凶,耻WP牛L)二叉掘树的彩带权(外部)路径脱长度掠是树退的各驼叶结演点所漠带的抖权值wi与该僵结点茂到根营的路肝径长咬度li的乘伸积的刚和。WP职L污=注2*烛2+塞WP唉L岩=亮2*讲1+屑W爽PL蝇=臭7胶*1两+4*邀2+滔5*烘2+古4虾*2刺+5盟*3程+伞5束*2高+2串*3梅+7*蹦2隆=壶36储7疗*3款=兴4棵6捎4军*3股=鸽3芬5222444555777带权(外部)路径长度隶达到迈最小霍夫柏曼树带权谦路径蛮长度志达到单最小星的二聚叉树著即为戏霍夫皂曼树拥。在霍赔夫曼以树中务，权们值大消的结犁点离适根最荡近。(1授)由给辩定的n个权串值{w0,弦w1,依w2,观…,荡wn-默1}，构把造具经有n棵扩垃充二凑叉树圾的森窃林F御=垄{役T0,血T1,浸T2,糖…,绕Tn-赖1}，其头中每拆棵扩鞠充二唐叉树Ti只有晶一夺个带铅权值wi的根洗结点,其左洁、右守子树剑均为智空。霍夫陪曼算法(2捷)重复脑以下居步骤,直到F中仅质剩下备一棵欢树为稀止：①努在F中选峡取两歼棵根暮结点房诚的权轧值最捕小的辱扩充必二叉腰树,做为贞左、约右子肚树构轿造一颠棵新拆的二卡叉树居。置训新的瞒二叉厦树的姑根结虏点的家权值灰为其挡左、宜右子和树上依根结去点的灾权值叠之和夫。②村在F中删禾去这菠两棵甚二叉疏树。③篇把新雀的二彩叉树申加入F。F跪:非{7贺}塘{5踩}熊{2梨}娘{4秃}F锋:扇{7撤}大{5倡}脚{6观}F非:欠{7澡}踪蝶{1嚷1}7524初始合并{2坝}泛{4浸}75246F瓶:弯{1渣8}1175246合并{5肥}肌{6欠}5合并{7剩}晒{1武1}27461118举例佳霍夫闪曼树县的构愤造过旦程例题门：已知葬关键斩字序陕列R=哑{1沟1,帐4,所3,境2,倘17广,3装0,版19法}，请纷按算证法步祸骤构剃造一凭棵哈窃夫曼截树，剃并计卸算出侍它的店带权蚊路径皱长度WP因L答：1.选最贿小2个根扩节点3，2合并宣为1个根瓣节点5，集债合变女为{1蓝1,野4,碗5,版17比,3由0，19贼}2.选最岗小2个根信节点4,错5合并迎为1个根拍节点9，集冰合变遇为{1纺1,叙9,禽17况,3偏0,蹈19叔}3.选最保小2个根蜓节点9,敬11合并钥为1个根柱节点20，集五合变呀为{2及0,件17型,3学0,测19键}4.选最惩小2个根洽节点17蝇,1秘9合并葡为1个根蛋节点36，集级合变冈为{2岗0,诵36许,3守0}5.选最鸡小2个根胆节点20鸽,3梁0合并驴为1个根痕节点50，集失合变矩为{5损0,僚36拳}6.最后晴合并虑为一虫棵树诞根节刺点为86862354911191730203650Wp哑l=结点延权值锋*路绣径长己度=2蚀*5胁+3浩*5觉+4励*4甚+1许1*咽3+遥30浓*2宁+1敬7*帮2+很19眠*2运=2虽0655图的格基本狭概念活动徒网络第七掉章杨图56图的蚁基本鞋概念图定烛义图是出由顶僻点集象合(v填er敬te飞x)及顶刚点间热的关走系集梯合组权成的除一种危数据期结构报：Gr壮ap喂h＝(劈燕V,砍E呈)其中V古=暗{芬x悬|及x某个洪数据头对象}是顶丈点的联有穷硬非空蓬集合色；E1述=劝{辜(x耕,降y)末|盛x捷,江yV怎}或E2急=锈{鸭<x鄙,坡y>蹦|定x粗,变yV稼&&姑P繁at缘瑞h准(x匀,膏y)格}其中爪，E1是顶格点之敢间关极系的皮有穷营集合救，也俩叫做排边(e戴dg牲e)集合大，此乞时的月图称涨为无口向图粘。E2表示尽从x到y的一咬条弧宪，且盲称x为弧星尾，y为弧膛头，辱这样渣的图合称为践有向笨图。例题坛：图吹的主贴要应接用都炊有哪秩些，至他们仅主要厕用于脸解决晒什么递问题茎？答：1.最小话生成疼树：然找到妨结点榴间最室小的迈连通吹网络2.拓扑塔排序码：通茧过在俗图中耕找有尘向环限（回港路）罗判断骆工程饿可行概性3.关键尖路径咽：找辣到工兆程花券费最绣少时抵间和倘关键去工序4.最短卸路径烧：在皱图中评找到铸两点化间最兵短路赛径5.遍历山：将位图的笋每个收结点罪打印计一遍58活动嘱网络(A抽ct保iv约it鲜y肃Ne说tw别or涌k)计划剑、施蔬工过挪程、监生产泰流程鞭、程浑序流唐程等萝都是赏“工抚程”腐。除匪了很偏小的扒工程粮外，阵一般糖都把覆工程影分为斩若干水个叫鸡做“桥活动忽”的辫子工珠程。贪完成壤了这拣些活近动，自这个社工程专就可蔽以完桌成了帽。例如葬，计惊算机讲专业惩学生码的学砌习就挤是一醋个工慢程，摸每一王门课列程的信学习澡就是交整个碗工程动的一快些活台动。陈其中搞有些共课程线要求著先修誓课程烧，有惰些则霞不要廊求。挑这样渐在有困的课薪程之句间有碍领先射关系卧，有芽的课诊程可电以并岸行地亭学习网。用顶滔点表灵示活浴动的色网络(A扶OV网络)59C1高等微数学C2程序邻设计马基础C3离散传数学C1,字C2C4数据企结构C3,生C2C5高级探语言恢程序巨设计C2C6编译艳方法C5,芝C4C7操作件系统C4,朴C9C8普通志物理C1C9计算煮机原叙理C8课程动代号扶课周程名拾称曾先修丢课程60学生忧课程鼠学习馒工程贝图C8C3C5C4C9C6C7C1C261可以晨用有工向图迈表示汉一个朗工程遍。在幸这种妇有向中图中敏，用姑顶点搬表示脆活动狸，用宪有向宗边<Vi,匙Vj>表示葡活动Vi必须赌先于棕活动Vj进行捧。这葱种有扯向图愈叫做顶点弃表示霉活动洪的AO蛮V网络(A笔ct掠iv庭it东y济O痰n此Ve尘rt挠ic见es敏)。在AO痛V网络浆中不偿能出委现有卖向回湖路,即有词向环驻。如授果出汗现了循有向过环，蹲则意匙味着知某项供活动核应以密自己封作为稳先决陶条件诞。因此徐，对给伏定的AO耻V网络遣，必饰须先叹判断丽它是香否存窃在有步向环是。62检测渔有向移环的胃一种溪方法具是对AO发V网络鞋构造尾它的偿拓扑去有序会序列协。即绩将各习个顶锹点(代表损各个拼活动)排列施成一小个线偷性有溜序的左序列左，使找得AO似V网络压中所欲有应辉存在弱的前夹驱和兔后继窜关系携都能显得到忠满足闷。这种伞构造AO若V网络继全部其顶点榴的拓葱扑有控序序逼列的郑运算弯就叫恢做拓更扑排者序。如果抬通过朗拓扑少排序汗能将AO倡V网络航的所勾有顶既点都拖排入扰一个岛拓扑惑有序锡的序樱列中,则该煎网络长中必卧定不吸会出丛现有烂向环迈。63如果AO纯V网络递中存钉在有暮向环土，此AO萄V网络肆所代重表的著工程第是不边可行池的。例如,对学惊生选抹课工爪程图脚进行乒拓扑耕排序,得到臭的拓善扑有瓜序序葬列为C1,混C2,繁C3,爽C4,联C5,姿C6,明C8,原C9,鹊C7或C1,厨C8,找C9,耻C2,挤C5,州C3,堪C4,脾C7,钥C6C8C3C5C4C9C6C7C1C264拓扑当排序胖的方唱法①输入AO孤V网络冒。令n为顶肆点个趟数。②之在AO翠V网络越中选屠一个字没有水直接扭前驱士的顶霉点,并输雨出之;③从图龙中删持去该盟顶点,同时甚删去哪所有奶它发偷出的份有向乖边;④重复坦以上申②颠、③晕步,直到全部策顶点然均已棒输出则，拓幕扑有查序序瘦列形甩成，姓拓扑湖排序闸完成偶；或图中雅还有肯未输惑出的蜻顶点,但已坐跳出魂处理扮循环辉。说蹦明图阴中还茫剩下广一些库顶点,它们俘都有见直接嗓前驱袋。这历时网藏络中钓必存舞在有必向环籍。65C0C1C2C3C4C5例题交：对供下图(a弱)做拓我扑排雪序并尿给出援过程(a拳)有向魂无环才图C2C5C1C0C3(b点)输出计顶点C4C1C2C5C3(c厅)输出除顶点C0C4C0C2C5C1C3(d给)输出陈顶点C366C1C2C5(e叔)输出鸡顶点C2C5C1(f为)输出拜顶点C1C5(g京)输出辽顶点C5答：最后得到创的拓退扑有披序序烦列为C4,毅C0,跌C3,派C2,筛C1,毕C5。(h珍)拓扑转排序倾完成67第九览章唐查找查找揪的概并念静态编查找掏表哈希截表68查找崭表是由闷同一暴类型射的数定据元声素(或记辱录)构成抵的集粮合,由于鄙“集乘合”挽中的棒数据宋元素耍之间锹存在杀着松该散的迟关系让，因那此查挑找表晴是一缸种应须用灵陷便的魄数据嫩结构两。对查热找表众的操猪作:查询惠某个玻“特岭定的忽”数涉据元悉素是徒否在得查找条表中仅；检索锯某个房诚“特羊定的神”数诱据元颂素的贞各种铺属性或；在查障找表螺中插米入一雾个数坡据元厚素；从查屯找表完中删扩去某拾个数掘据元绿素查找警的概搂念69关键圈字是数侧据元蠢素（件或记久录）逮中某亲个数明据项托的值印，用姐以标耳识（西识别馋）一貌个数还据元授素（承或记闲录）杏。若敏此关物键字尤可以视识别双唯一怎的一染个记码录，第则称鲁之谓拍“主盛关键傻字”暖。若傅此关饶键字恋能识哲别若撤干记绣录，池则称感之谓港“次与关键帆字”哥。70根据楼给定钢的某坝个值员，在费查找皱表中分确定因一个手其关徒键字壤等于敞给定屡值的扩数据施元素沿或（贡记录虹）。若查斩找表腹中存知在这用样一钻个记凤录，僻则称餐“查找耗成功”，锤查找筝结果拐：给出溜整个闻记录庙的信歉息，弄或指踩示该宰记录见在查邮找表君中的狐位置；否则屠称“查找众不成香功”，岸查找稀结果秤：给出乔“空朵记录杀”或风“空崖指针框”。查找71静饿态趋查妙找染表72若以掉有序京表表深示静恶态查记找表章，则裳查找苗过程萌可以杆基于井“折携半”哲进行横。有序喇表的顺查找折半灭查找查找禽过程弱：每次脚将待励查记望录所斤在区倚间缩糟小一往半。适用也条件澡：采用补顺序纯存储奏结构游的有核序表骂。731.设表谅长为n，lo股w、hi壶gh和mi觉d分别臣指向绪待查串元素悦所在身区间粗的上霜界、竭下界华和中蓬点,k为给犁定值雨。2.初始泥时，侧令lo年w=老1,痛hi炒gh接=n际,m着id同=(掏lo血w+庙hi鞭gh完)/组2让k与mi脑d指向龄的记尊录比榆较若k=许=r掌[m魄id这].惕ke片y，查找足成功若k<窃r[梨mi载d]建.k朝ey，则hi凉gh乘=m巴id格-1若k>配r[滔mi满d]响.k谜ey，则lo禁w=稠mi跟d+秃1企3.重复耐上述智操作售，直歪至lo优w>辉hi慎gh时，误查找贯失败圆。折半严查找践算法挎实现74lo导whi用ghmi予d例1234567891011513192137566475808892找211币2沉3音4汤5阴6宋7刷8旗9营1明0肃115至1讽3收19凡2削1捆37侨5赖6歌6斜4绸7偿5笨80效8馒8乳92lo鞠whi科ghmi倘d1穿2叼3舒4跑5何6敞7隆8灾9降1狡0矛115侵1我3未19猾2救1陈37烘5县6伐6神4菠7记5讽80盾8疏8诊92lo稳whi猛ghmi润d例如ke粉y崭=2妄1的查游找过剪程lo吸w指示灯查找睛区间船的下腾界;hi干gh指示般查找骡区间锹的上旺界;mi蜜d=斗(l勿ow吗+h斜ig什h)浸/2。75例ke阀y访=7派0的查志找过锦程1企2殖3境4刮5孩6步7拌8役9印1仔0多115死1借3许19缎2霉1印37绕5衬6钢6柏4黎7朴5辈80烧8锅8痕92lo欠whi缓ghmi倡d找701照2么3忌4鸦5虎6翠7退8醒9效1众0纸115恢1秆3双19纷2晓1腥37正5别6斧6脸4倦7去5丢80衣8寒8贺92lo画whi旁ghmi榆d1跃2淋3马4荒5色6漠7屠8湾9触1嗓0销115浩1融3联19桂2扛1孝37倡5佣6贺6洽4挽7截5中80引8数8迁92lo数whi败ghmi薪d1兼2叠3进4河5茧6短7箩8盯9季1绕0揭115碑1悠3智19弊2葱1破37华5枯6削6睡4依7厨5泼80戏8驳8望92lo岛whi嫁ghmi宋d761改2腐3底4暗5贷6貌7略8觉9竖1筑0扛115茂1工3强19吸2昌1牢37笼5汉6百6栗4闹7窝5夕80榴8号8枝92lo邀whi击gh1它2进3垂4喘5拼6过7彼8辛9尸1异0摄115漏1斗3摧19赤2命1校37渗5僵6晚6窄4窗7孙5葬80拒8蒙8废92当下尖界lo宫w大于务上界hi听gh时，此则说睡明表吓中没蔽有关蓝键字言等于Ke屯y的元茂素，经查找但不成腿功。77in循t意Se桌ar晃ch贴_B坊in加(顾S格ST限ab女le辆S萄T,叉K魄ey朗Ty挂pe妄k相va酷l务)级{lo增w因=倚1;微hi摸gh泛=巨S源T.片le妖ng调th宣;吹//置区滴间初庭值wh期il颗e叮(l述ow谅<件=蛋hi爬gh价)课{mi决d图=轮(l尝ow降+义h堡ig杏h)味/龟2忠;if（kv便al何=柿=朗ST宫.e塞le率m[渡mi挺d]前.k盟ey绝)re葡tu叫rn竭mi废d;例//找到攀待查赏元素el母se叹if乐(柴k匀va奶l滴<天ST垃.e冤le浆m[则mi倍d]猛.k厌ey势)曲)hi叨gh煤=暖m截id请-本1口;产//继续仔在前姜半区测间进维行查亭找el湖se毅lo挥w锡=熊mi改d初+捆1;矛/须/继续侵在后尚半区任间进插行查袜找}re凳tu先rn括0播;夺//顺序腥表中碑不存裙在待示查元温素}场//缎S光ea丑rc吸h_颗Bi轻n折半摘查找持算法78例题纲：请渴列出战折半门查找狐特点肢。答：折半敬查找绑的效寒率比罚顺序过查找虽高。折半耳查找最只能谁适用趣于有页序表滴，并纲且以特顺序微存储矿结构呼存储仓。折半饭查找浴的时维间复旨杂度恒为O（lo壤gn）79哈希钉表的级相关迁定义处理考冲突知的方中法哈希洁表的何查找哈希读表的边插入哈恋希横表80哈希缓查找又叫骄散列涂查找糠，利跳用哈烂希函嫂数进院行查些找的锤过程清。基本存思想研：在坊记录翠的存怒储地傅址和吼它的包关键留字之吨间建久立一婆个确羊定的界对应国关系磁；这杨样，扇不经日过比码较，帝一次孟存取辞就能滔得到兵所查干元素支的查粒找方符法。哈希豆函数在记盈录的质关键娃字与糊记录州的存败储地坏址之慕间建变立的家一种扒对应化关系睁。哈兔希函便数是邻一种玻映象潮，是彼从关泛键字粒空间挎到存盏储地扯址空苗间的咳一种尘映象袖。可写熊成，ad畜dr呢(ai)=粒H(在ki)其中覆：ai是表粉中的滚一个门元素ad酱dr亮(ai)是ai的存谊储地拦址ki是ai的关蓄键字哈希妨表的照相关除定义81哈希阴表根据委设定杨的哈著希函写数H(朱ke康y)和所初选中尿的处逮理冲搁突的漠方法馒，将传一组话关键滚字映攻象到激一个诵有限榴的、困地址鱼连续酿的地迅址集(区间)上，乏并以冤关键删字在叨地址嚼集中君的“码象”奥作为策相应壳记录站在表扎中的熟存储概位置纳，如霸此构起造所荐得的然查找评表称莲之为炒“哈粮希表右”。82处理始冲突卖的方幕法“处理岗冲突群”告的实音际含饼义是键：为产腐生冲拍突的脉地址大寻找搭下一宿个哈滤希地用址。开放赚定址棵法83为产俗生冲掉突的宇地址H(磁ke窜y)求得势一个东地址浩序列得：H0,仓H1,孤H2,纤…,Hs1≤蓬s≤腥m-熔1Hi=仰(辰H(图ke巡寿y)节+述di)必MO瓣D招m其中流：i=摇1,娱2拉,章…,符sH(得ke闭y)为哈思希函勇数;m为哈瞒希表雹长;di为增户量序船列:开放燃定址灵法84对增敬量di：线性帝探测读再散鞭列di=旷ci最简怪单的根情况c=锅185例圈表稀长为11的哈需希表笼中已惜填有援关键弄字为17，60，29的记暮录，H(巴ke它y)屯=k惩ey勉MO论D原1亚1,现有宿第4鹿个记椅录，尝其关橡键字腐为3倚8，开按三缴种处讯理冲唤突的嗽方法掌，将卡它填等入表冰中012345678910601729H(38)=38MOD11=5冲突H1=(5+1)MOD11=6冲突H2=(5+2)MOD11=7冲突H3=(5+3)MOD11=8不冲突383838例题它：哈察希表的地裂址区铜间为0-鼓17芝,哈希函数闭为H(棍K)酸=K藏m屈od湾1散7。采格用线屈性探验测法直处理赵冲突母，并边将关糖键字神序列26，25，72，38，8，18，59依次经存储项到哈希表中智。答：26婶/1涝7=威1余925讨/1贼7=枯1余872是/1劳7=串4余438徐/1迁7=休2余4冲突利，地结址为4+康1=亲58/蚁17卧=0余8冲突卧，地蝴址为8+袄1=凝9冲突订，地向址为9+顽1=渣1018破/1咸7=残1余159却/1捧7=惹3余8冲突动，地狗址为8+伟1=润9冲突窄，地窜址为9+李1=帝10冲突尤，地指址为10投+1洁=1藏1０１２３４５６７８９１０１１１２１３１４１５１６１７187238２５２６85987概述插入只排序快速全排序选择考排序第十色章内飘部排贴序88概倘述排序(s倚or惧ti匙ng对)：将一柿个数仿据元蜡素的叫任意抵序列挡，重稼新排陡列成矩一个扛按关严键字魄有序血的序影列。89排序捞方法存的稳奔定性:如果寨在对纽奉象序国列中蜓有两果个碑对象r[催i]和r[纷j]最,它们战的排田序码k[锄i]==固k棚[j诊],且在从排序愉之前,对象r[虑i]排在r[配j]前面欣。如稀果在较排序将之后,对象r[某i]仍在玩对象r[井j]的前警面,则称施这个因排序靠方法晴是稳曾定的,否则繁称这忽个排药序方念法是贸不稳衣定的浮。如待印排序希列:49,3皮8,发65裕,9羊7,智76扑,1小3,洪27讨,49使用村直接饿插入侮排序极得到别的序兄列：13需,2语7,挎38圾,49,49,6粉5,眉76童,9支790内排订序分婚类依不监同原虑则插入苦排序、交换卖排序、选择膊排序、归并脸排序吩等。依所涉须工府作量简单揪排序--绣-时间权复杂吸度O(言n2)先进杠排序些方法--磁-时间螺复杂惨度O(浑n吴lo当gn洋)91插入启排序(I捡ns割er常t中So尊rt详in奶g)基本顷思想每步袖将一池个待词排序撒的对商象,按其辰排序窝码大秆小,插入熊到前折面已劳经排朝好序碰的一滑组对棵象的看适当嘉位置斯上,直到依对象辟全部芳插入威为止尽。92基本拐思想艇：当待肿排记讨录数n很小抗时，栗直接杀插入瞒排序滥的效玩率较绘高。当待启排序盏列按欣关键乐字基恭本有恶序时膨直接苹插入泳排序盟的效完率也决较高腹。所以服从这差两点孝出发澡可对最直接薄插入酱排序户改进支，先令将整秋个待纵排记骑录序橡列分虫割成营为若叫干子写序列廉分别凤进行蹦直接炮插入谣排序渐，待喇整个寸序列更中的广记录裳基本励有序奔时，及再对暗全体养记录隐进行蓬一次椅直接刻插入批排序关。希尔滤排序(S加he报ll职S凭or牛t)（缩删小增桥量排勤序）93设待特排序裤对象蔬序列邮有n个对挺象,首先匀取一娇个整可数ga伟p丘<廊n作为饮间隔,将全胜部对昆象分浸为ga昂p个子决序列,所有钳距离救为ga诞p的对康象放颜在同捕一个除子序迈列中,在每距一个稀子序奇列中屠分别尽施行樱直接蹄插入续排序美。然遗后缩洋小间敢隔ga绣p,例如息取ga杏p令=ga淘p/颤2，重诱复上稠述的窃子序反列划甘分和端排序傲工作律。直垫到最臭后取ga链p串==凤1漆,将所沃有对粒象放趟在同县一个昼序列痛中排数序为叉止。94i=窑3Ga姐p木=火30123452108254925*161刺2述3剩4耍5滤62108254925*16i=弦2Ga建p敬=歼22108254925模*162108254925*16i=遗1Ga票p饥=体12108254925*162108254925*16希尔勿排序耐过程95希尔腊排序绕是一标种不返稳定铅的排叼序方陶法96快速夕排序(夕Ex教ch俘an捡ge故S恶or播t宪)基本诞方法设待肿排序匪对象套序列认中的质对象油个数缴为n。一吸般地胡，第i趟起象泡排逢序从1到n-嘉i+散1依次棒比较叔相邻岭两个普记录火地关上键字柏，如果都发生拉逆序齐，则驼交换坡之，字其结钥果是甚这n-蝇i+宾1个记皮录中止，关斜键字泊最大越的记膜录被唉交换模到第n-毁i+主1的位丢置上洗，最多捷作n-喂1趟。基本姓思想是两宰两比上较待批排序站对象授的排展序码,如发瘦生逆圆序(即排蝴列顺株序与吵排序咳后的狠次序龟正好颜相反)，则黑交换钢之,直到介所有徐对象某都排苏好序教为止按。起泡木排序(B协ub羡bl按e航So钱rt朝)97210825492516214925251608214925251608214925251608214925251608初始关键字第一趟排序第四趟排序第二趟排序第三趟排序214925251608第五趟排序起泡高排序蓬的过蛋程98起泡岂排序魔是一警个稳帜定的障排序挥方法序。时间结复杂侍度为O(派n2)。99快速腊排序(Q昆ui饱ck屯S乳or恰t)基本乓思想是任隐取待讯排序馒对象谈序列抱中的的某个邮对象(例如蚕取第梅一个畅对象)作为孙基准,按照挨该对燃象的花排序押码大岭小,将整歼个对译象序痕列划诸分为施左右胜两个博子序耗列：左侧母子序晓列中狡所有织对