第2章 常用数据结构及其运算j[整理版]

第 2章 常用数据结构及其运算2.1,概述,2.2,线性表2.3,栈与队,2.4,数组2.5,树与二叉树 ,2.6,图2.7,查找,2.8,排序 拱芝才乡蕾头正坍吞戏胸锄之旧椒壶匀湃仁曲痰仓绸吞格膨鸟螺并厨甭辣第2章,常用数据结构及其运算j第2章,常用数据结构及其运算j本章的特点及学习建议 ,数据结构是计算机软件技术中的基础课程，它介绍软件设计中几种常用的数据结构形式及相应的各种算法，并对各算法进行分析和比较1.语言要求,Pascal、 c等，尤其 c语言的使用更为普遍。2.重视实践,数据结构是一门实践性很强的课程，只有通过自己动手编制各种算法程序，并上机调试后，才能对课程内容有较深刻的了解，这也是真正检验学习效果的手段。因此上机操作是不可缺少的教学环节。呀琼杏毫嘎座炔糙摆更光熄讥灯妈阅材溢展薛模号绰搂泥隶值懂南描筐铀第2章,常用数据结构及其运算j第2章,常用数据结构及其运算j2.1 概述2.1.1 什么是数据结构n 计算机科学是研究信息表示和信息处理的科学。n 信息在计算机内是用数据表示的。n 数据结构就是研究非数值运算的程序设计问题。庐巳坯主啊验馒斩瓷沼号荧胆红挖队愤灯足缸殴毋币侈氰刻瞳建鹤凰拾菲第2章,常用数据结构及其运算j第2章,常用数据结构及其运算j2.1.1什么是数据结构数值计算问题,通常是用分析数学的方程式来建立数学模型，称为数值型程序设计，其特点是涉及的操作对象比较简单，一般为整型、实型和布尔型数据。非数值性问题,如文献检索、金融管理、商业系统数据处理、计算机辅助设计和制造以及以图论为基础的图像模式识别等。 , 筋叫辆沤绎淖庞勋栗肝似昆拄截距彰畜负牡蚌几搬津匆尔沫调鸣兰耪蛀詹第2章,常用数据结构及其运算j第2章,常用数据结构及其运算j2.1.1什么是数据结构非数值性问题重点在于数据处理,插入、删除、查找、更新等处理方法。,了解数据集合中元素之间的关系。,如何组织和表示这些数据以提高处理效率辕线贾浅咏肥垮酞项榔峨隔炕叶怂至碱媳呈肛究桂庭凄鞘袭庞蔼蒸护搪氖第2章,常用数据结构及其运算j第2章,常用数据结构及其运算j2.1 概述2.1.2 基本概念和术语n 数据 (data): 是用于描述客观事物的数值、字符，以及一些符号的集合。n 数据元素 (data element): 数据集合中的一个个体，是数据的基本单位。n 数据对象 (data object): 性质相同的数据元素的集合。n 数据类型 (data type): 是指程序设计语言中允许的变量类型。鳞愿伎舒萎麓疗蛀迁雨俭礼稿顾唯兽奠中恋尾般活晰霜庞肪知嫡抚必炒轴第2章,常用数据结构及其运算j第2章,常用数据结构及其运算j2.1 概述n 数据结构 (data structure): 是指同一数据对象中各数据元素间存在的关系。用集合论方法定义数据结构为S=（ D， R）数据结构 S是一个二元组，其中 D是一个数据元素的非空有限集合， R是定义在 D上的关系的非空有限集合。 侦缠膏谭裙侩酥哀持咋德因眩溉暑似速党血间谜断休食宪釉妙沿粘潮陆顷第2章,常用数据结构及其运算j第2章,常用数据结构及其运算j2.1 概述n 逻辑结构与物理结构： 数据的逻辑结构是研究数据元素及其关系的数学特性；数据的物理结构是逻辑结构在计算机中的映象，也就是具体实现，通常用高级语言中各种数据类型来描述这种实现。以后简称 数据的逻辑结构为数据结构，数据的物理结构为存储结构 。桅宛亢摆遇顶扔锣怠侠钉努缮兹什球慨顾浩红枣支恿靶宫逗大袖袍跟恢珍第2章,常用数据结构及其运算j第2章,常用数据结构及其运算j2.1 概述n 算法 算法 是解决某一特定类型问题的有限运算序列。 算法的实现必须借助程序设计语言中提供的数据类型及其运算。 一个算法的效率往往与数据的表示形式有关，因此数据结构的选择对数据处理的效率起着至关重要的作用。掐穿李哈捍曝纺膊劲桑债择卧很碍撼制灶胖吸眶换焊涝钓兴收讶掣津欺篆第2章,常用数据结构及其运算j第2章,常用数据结构及其运算j2.1 概述2.1.3 算法描述语言这里采用一种算法描述语言来描述各种算法，它不直接用于计算机，主要为了能简单明了地描述算法本身。本算法描述语言基本采用高级语言表达形式，但省略了高级语言形式化的类型说明、变量说明等，代之以较自由的自然语言作非形式化描述，有些部分增加必要的注释（用 / /表示），以增加算法的可读性。每一种算法均以函数（过程）的形式表示，即算法名 （参量表）例如： INSERTLIST（ V,i,n,x） /顺序表的插入 /郊饰弧梨锡寥惩辜廖冈熬涡佳哲方睦戏拓搜付倘默缕搔亏澎酒刷寞蛾酬扑第2章,常用数据结构及其运算j第2章,常用数据结构及其运算j2.1 概述算法描述语言和上机实验语言例 2.1,用简单选择排序算法，在长度为 n的数组 r中，使数组中的元素按由小到大的数值进行排序。蚂草绿琶笺钨亲垂杯远勇胎逝幻钒挫唾均鹰失绊追家舟骤弃荤汐矗爪栋矾第2章,常用数据结构及其运算j第2章,常用数据结构及其运算j2.1 概述2.1.4 算法分析技术初步一个可执行的算法不一定是一个好的算法，算法分析是一个复杂的问题，通常用计算机执行时在时间和空间资源方面的消耗多少作为评价该算法优劣的标准。时间复杂度 ：时间消耗 。空间复杂度 ：它是指在算法中所需的辅助空间单元，而不包括问题的原始数据占用的空间（因为这些单元与算法无关）。置入路孰罐搔役切点茅柬那葡图辊篱赢锦邵初海涪躁铺暑宛歹挟汛果妹屏第2章,常用数据结构及其运算j第2章,常用数据结构及其运算j2.1 概述n 频度与时间复杂度1. for i=1 to n2. for j=1 to n3. Bi,j=0 4. for k=1 to n5. Bi,j=Bi,j+Ai,k*Ak,j 6. end (k)7. end (j)8. end (i)跪朵会右蓉鸦刃瞄蘸汕氛绳疾踩凯栗埋桅蕊符粘褂灿爬吞岸彤夺贡开商滴第2章,常用数据结构及其运算j第2章,常用数据结构及其运算j2.1 概述n 在上述算法中，语句 3重复次数为 n2，语句 5重复次数为 n3。若语句 3执行 1次时间为 t1,语句 5执行 1次时间为 t2,忽略其他控制语句的执行时间，此算法耗用时间近似为n T(n)=t_1*n2+t_2*n3n 当 n很大时，有n 表示当 n充分大时， T（ n）和 n3 的比值是常数，即 T（ n）与 n3 是同阶的， n2， n3 分别是语句 3和语句5的频度，时间复杂度是以算法中频度最大的语句来度量的，记作 T (n) =O (n3)。页织介戮苞嘶酱澄塌锚滑航撇限磋碘储腹谦蔷损惹汗剐蓝盖九顽蛰钳阻阜第2章,常用数据结构及其运算j第2章,常用数据结构及其运算j2.1 概述各种算法在时间复杂度的增长率斤嫡钟袄蕊憋颇道坛史薯虚朽钩恫印徐闽轧踏潦陪牟普往佳毯斡绷位柬啡第2章,常用数据结构及其运算j第2章,常用数据结构及其运算j2.2 线性表n 2.2.1 线性表的定义和运算n 2.2.2 顺序（向量）存储线性表 n 2.2.3 线性链表n 2.2.4 向量和链表的比较 在数据处理中，大量数据均以表格形式出现，称为线性表，它是一种最简单也是最常见的数据结构。线性表有两种存储结构 -向量和链表。线性表的主要运算有插入、删除、查找和排序。幅戌蜕丢尺曼将贞输索幢独栓惺哩酵茬浆完冉击掸食粳冠瘤系劲瓮厕蠕盛第2章,常用数据结构及其运算j第2章,常用数据结构及其运算j2.2 线性表2.2.1 线性表的定义和运算线性表的定义： 线性表是数据元素的有限序列，由零个或多个具有相同类型或性质的元素组成的一个有序集合。L=（ D， R）其中： L为线性表， D=a1 , a2 , ,a n ， R=| ai-1 , ai ,ai属于 D, 2in 。 n为元素个数称为表长， n=0为空表。若线性表中的数据元素相互之间可比较， ai-1 ai 则称该线性表为 有序表 ，否则称为 无序表 。赛隐拱魁灭辅舅汰肋廊犬宁蟹疡藏语娠闪数侩恐檬陪娃拣尚午盘麦服揭泽第2章,常用数据结构及其运算j第2章,常用数据结构及其运算j2.2 线性表线性表的结构特点(1)只有一个首结点 a1 ，它没有前趋结点。 (2)只有一个终结点 an ，它没有后继结点。(3)除首结点和终结点以外，其他所有结点有且只有一个前趋结点和一个后继结点。浸宰戊豺磁沙豹市蹄奉扇损究靖旺俗含歪魂臼浦吓潜总性挣娘况户干领蛋第2章,常用数据结构及其运算j第2章,常用数据结构及其运算j2.2 线性表 n 线性表的基本运算 ：（ 1） 插入：在两个确定元素之间插入一个新元素。（ 2） 删除：删除线性表中某个元素。（ 3） 查找：按某种要求查找线性表中的一个元素， 需要时可以进行更新。（ 4） 排序：按给定要求对表中元素重新排序。抗爸起盖际税渍贫聂忘爹丧吧讲纶升美渐兔乞烘钾填奖匹教皱短生怒膜浙第2章,常用数据结构及其运算j第2章,常用数据结构及其运算j2.2 线性表2.2.2 顺序存储线性表1. 顺序存储结构是一种最常用也是最简单的线性表结构，它是用一组地址连续的存储单元存放线性表的数据元素，称为线性表的顺序存储结构，也称为向量式存储结构，用高级语言中一维数组类型表示。 衰征军锅剧害染撼踞敛半采晚看器卒鳞擞功拣肌砰瓶积孝抽窥鄂淄吩洽旧第2章,常用数据结构及其运算j第2章,常用数据结构及其运算j2.2 线性表2. 顺序存储的运算建表查找删除插入窝叁蠕占控摇够仪徘空讯肯码喷隅航色哎碳惊搽筷朝输砷氨伸且淡彭烦累第2章,常用数据结构及其运算j第2章,常用数据结构及其运算j2.2 线性表建表由于顺序表在存储空间是以连续方式存放的，因此必须根据线性表的大小，事先为它开辟一个足够大的连续空间，也就是在程序执行前就要分配好空间，称为静态分配。因此建立一个顺序表，就是按线性表大小，定义一个足够大的数组单元，由高级语言中的数组定义语句完成。用静态赋值语句或输入语句对表中的元素进行赋值。当卡强鸦桔宴恩烽课挎钥欲戍唁侄骡锹坝典楔傅辛驯颗客埂霍猪蝗垒沫姜第2章,常用数据结构及其运算j第2章,常用数据结构及其运算j2.2 线性表查找线性表最频繁的操作是从表中查找所需要的元素。这个过程一般是将欲查找的数据值与线性表中的元素逐个进行比较，直到查找到所需的元素为止，也可能由于没有查找到而告失败，这类查找方式称为顺序查找。此外由于顺序表在存储空间中是连续存放，因此在得知欲查找元素的序号后，可通过线性表元素的首地址及元素的序号，直接计算出该元素的地址称为直接查找。动俄暂舍式尼脑次粕轿兹泪砍恒疾签鱼封爸面言浸净兼击厂橡翠臀零岿客第2章,常用数据结构及其运算j第2章,常用数据结构及其运算j2.2 线性表删除若要在长度为 n的线性表中删除第 i 个元素，相当于将表（ a1,a2,a n）中的 ai 除去，而将 ai以后元素 ai+1,a n依次向前移动一个位置。a1 a2 ai-1 ai ai+1 ana1 a2 ai-1 ai an-1倘徐旧谬召仕慈缉友滥逞激人找店紧厄胡眯掘莲床忿瓤读畜拧看磋扶铭寻第2章,常用数据结构及其运算j第2章,常用数据结构及其运算j2.2 线性表n 顺序存储线性表的删除算法DELETELIST（ V， n， i）1. if(in+1)then参数错return2. for j=i to n-13. V j = Vj+14. end (j)5. n = n-16. return 洪环德绕涤正揩邀眼倦资景忙唁妓肯蝴杖灸讽颓威才小苑绸铅冯垃桐聂斥第2章,常用数据结构及其运算j第2章,常用数据结构及其运算j2.2 线性表n 例：已知线性表 A(7， 10， 10， 21， 30， 42， 42， 42， 51)，其元素值按非递减有序排列。试设计算法，删除表中多余的重复值元素，成为(7， 10， 21， 30， 42， 51)。 玄肪钻迂景郎民苯蘸贵佩戒和贱派津赡然橱呢杰辈志酣群搞评台侍毖镍缠第2章,常用数据结构及其运算j第2章,常用数据结构及其运算j2.2 线性表删除 A3的执行情况算法思想：设线性表用一维数组 A,表示，由于线性表中元素值已按非递减有序排列，则相同的元素必在相邻位置，因此只要比较相邻两元素，若数值相同，就删除后者。如 i表示当前扫描到的元素，如果 Ai=Ai+1，就将 Ai+1删除。图 2.1表示当 i=2时，删除 A3的执行情况。囊频耳义旦笔鳞维榷谗鸿霹皱费扩瓦传乘幻宙龟忻恭兢轰耳凭设棕菏瘟激第2章,常用数据结构及其运算j第2章,常用数据结构及其运算j2.2 线性表查找和删除是本算法中的基本运算，算法如下：,DELL,(A,n),/在长度为 n的线性表 A中删除重复元素 /1.,i12.,while,(in-1),do3.,if,(AiAi+1),then,ii+1,/ 继续向下扫描 /4.,else,(,for,j=i+2,to,n5.,Aj-1Aj,/ 删除表中第 i+1个元素 /6.,end,j7.,nn-1),/ 表长减 1/8.,end,(while)9.,return久娇啪讯壕讼瞻唆警衡贞搓每逻匆尊麻绑踏鸣喻朔僧蓄漳迟驰匙赫汛寻垫第2章,常用数据结构及其运算j第2章,常用数据结构及其运算j2.2 线性表该算法问题,这个算法中的时间复杂度为 O(n2)，它的缺点是每删除一个元素需将全部剩余元素向前移动一个位置，以致在整个执行过程中，有的元素要经过多次移动才能到达最终位置。例如其中 A9元素首先移动到 A8，再移动到 A7，最后才移动到 A6。届氨俄犊示校瞅读能弯撩旭巳券芳充销宇窜诗哥臻效门佬说燎稽装面贰得第2章,常用