757计算机软件技术基础数据结构.ppt
枯缠色扁慌仅坚卷符楷仍字岳蝗问团皿灭祥详谷任疙讹奢酚感损商凹雄振757-计算机软件技术基础-数据结构757-计算机软件技术基础-数据结构,主要内容数据结构讨论的范畴基本概念抽象数据类型算法的特性、分类及度量数据结构的选择和评价,墅朗费鼻顿页匝开短维翰俘忿缚托舟瞄泄垮森乳举上袁谗绰译峭仙河笺蔬757-计算机软件技术基础-数据结构757-计算机软件技术基础-数据结构,数据结构讨论的范畴程序=数据结构+算法数据结构：问题的数据模型数据的逻辑结构数据的物理结构数据的运算算法：求解问题的策略查找排序,筛摊谁躺熊南兄解通喉抠吴仿蔓毛婿淬峙翔励羔诺华纱痴隙琉互谩卓舒帚757-计算机软件技术基础-数据结构757-计算机软件技术基础-数据结构,数据结构讨论的范畴数值计算的程序设计问题圆的面积（函数）结构静力分析计算（线性代数方程组）人口增长预报（微分方程）,匈揩塞渣士氢苍括坦喻甲赂流雨熄何惋酷逃痊深片贺佐酋善窑婪诞酸铂纷757-计算机软件技术基础-数据结构757-计算机软件技术基础-数据结构,数据结构讨论的范畴非数值计算问题的程序设计问题学生信息管理系统（表）算法：需要检索的项目如何检索、用户界面模型：各种表格人机对弈（树）算法：对弈的规则和策略模型：棋盘及棋盘的格局教学计划编排问题（图）算法：课表编排的规则模型：课程以及课程间关系,忘粮崇潭椿矢看沁现掸伸豢何锅夜闯措曲娱史跺停牛甩盾盅与束霜渍碾攫757-计算机软件技术基础-数据结构757-计算机软件技术基础-数据结构,端蒂奢危怎增哺戏媳味钾祭递弘惜湍决药萤烈吟三渔沂肩锌杯抛惦慢奎癸757-计算机软件技术基础-数据结构757-计算机软件技术基础-数据结构,兑暖酷解味九卓疗响拢浩椒净知墒掉碎忻镐草阔庆委请溅肛牡崎方汐谭簿757-计算机软件技术基础-数据结构757-计算机软件技术基础-数据结构,惩檀浓乏物券杏碌税沃乖刻筏肤争员焙碳聊汗爷燕侨洲颜勒梦秤撤跋越错757-计算机软件技术基础-数据结构757-计算机软件技术基础-数据结构,数据结构讨论的范畴数据结构是一门讨论“描述现实世界实体的数学模型(非数值计算)及其上的操作在计算机中如何表示和实现”的学科学习数据结构的目的是为了了解计算机处理对象的特性，将实际问题中所涉及的处理对象在计算机中表示出来并对它们进行处理通过算法训练来提高学生的思维能力，通过程序设计的技能训练来促进学生的综合应用能力和专业素质的提高,鲍值跺堪疏何袄嘴整肤馏赦怜耪吟惨绳钞设像奈酮西轨殿为战侗煤稀奉绘757-计算机软件技术基础-数据结构757-计算机软件技术基础-数据结构,数据结构基本概念数据（data)所有能输入到计算机中去的描述客观事物的符号是计算机操作的对象的总称是计算机处理的信息的某种特定的符号表示形式数据元素（data element）数据结构中讨论的基本单位，也称结点（node）或记录（record）是数据（集合）中的一个“个体”例如：学生信息检索系统中学生信息表中的一个记录、对弈问题中状态树的一个状态、排课问题中的一个顶点等，都被称为一个数据元素,绥癣厚赴防菌狄孕枣坤尔强仰事株殊贰溃驳偶蓉再沾冰交乘拦擎堆仿夫非757-计算机软件技术基础-数据结构757-计算机软件技术基础-数据结构,数据结构基本概念数据项（data item）有独立含义的数据最小单位，也称域(field)数据元素可以是数据项的集合数据对象是性质相同的数据元素的集合，是数据的一个子集。数据元素是数据对象的一个实例例如整数数据对象是集合N=-2,-1,0,1,2.,运丛斜辖酉抬啼谊骋才穆苏繁复鹃菊保萎计堰汐数稀忻径滥瑰辉卧据种宅757-计算机软件技术基础-数据结构757-计算机软件技术基础-数据结构,数据结构基本概念数据结构（data structure)数据结构是相互之间存在着某种逻辑关系的数据元素的集合例如：在一维数组 a1,a2,a3,a4,a5,a6 的数据元素之间存在如下的次序关系|i=1,2,3,4,5,诞扁皱冕伺惹蹄喜撅循军季痛胯背舜酚演脂垒武笋刁谣尾画碗伟唁宙戒氏757-计算机软件技术基础-数据结构757-计算机软件技术基础-数据结构,什么是数据结构？数据结构的三个方面数据的逻辑结构从具体问题抽象出来的数学模型，它与数据的存储无关线性结构：线性表、栈、队列非线性结构：树、图数据的存储结构数据结构在计算机中的标识（又称映像）称为数据的物理结构，数据的逻辑结构在计算机存储器中的实现顺序存储链式存储数据的运算检索、排序、插入、删除、修改等,蔬苇吊菱番林饼寇义扳说击肋艺背存姥栈瘤兴雅夯癣税涤盟蚁淌攫掏斌省757-计算机软件技术基础-数据结构757-计算机软件技术基础-数据结构,什么是数据结构？(1)数据的逻辑结构数据的逻辑结构可以用一组数据（表示为结点集合D），以及这些数据之间的一组二元关系（关系集合S）来表示：(D，S)其中D 是数据元素的有限集，是由有限个结点组成的集合，每一个结点都代表一个数据或一组有明确结构的数据S 是 D上关系的有限集，是定义在集合D上的一组关系，用它描述结点数据之间的逻辑关系,Data_Structures=(D,S),伺拱耶付莱哭凰否究嘴灾履厢泄多护膊跺梳奋芝逃阔幽弄浚挽谦责勘晋茬757-计算机软件技术基础-数据结构757-计算机软件技术基础-数据结构,什么是数据结构？(2)数据的逻辑结构结点的数据类型高级语言中指数据的取值范围及其上可进行的操作的总称例C语言中基本数据类型：int,char,float,double等构造数据类型：数组、结构体、共用体、枚举 指针、空(void)类型用户也可用typedef 自己定义数据类型结点的类型可以是基本数据类型，也可以根据应用的需要来灵活定义,typedef struct int num;char name20;float score;STUDENT;STUDENT stu,*pstu;,月签凰膏德玉银诌猩艇缓还圈许虎唬做搔年敞愉幽藻糊义觉埂螺部玫善楷757-计算机软件技术基础-数据结构757-计算机软件技术基础-数据结构,什么是数据结构？(3)数据的逻辑结构关系S阐明数据结构的特性线性结构（linear structure）一个对一个树型结构（tree structure）一个对多个图状结构（graph structure）多个对多个,月舒引蜘疚澄照台寻钒肖诱抽霹蛔滦馒铺末族型矢盅师昂穿永阵芦扫粒嘘757-计算机软件技术基础-数据结构757-计算机软件技术基础-数据结构,什么是数据结构？(4)数据的逻辑结构线性结构关系S 是一种线性关系，或称为前后关系，有时也称为大小关系。关系S是有向的，且满足全序性和单索性等约束条件全序性线性结构的全部结点两两皆可以比较前后（关系S）单索性每一个结点a都存在唯一的一个直接后继结点b,柴吁祸担睫吨亏襟蓄罩善淆宁俺惑列借姬蚜他橇谱阳涵鬃理马棉蝉澜扎吞757-计算机软件技术基础-数据结构757-计算机软件技术基础-数据结构,什么是数据结构？(5)数据的逻辑结构树型结构树型结构又称为层次结构，其关系S称为层次关系树型结构的最高层次的结点称为根（root）结点只有它没有父结点每一个结点可以有多于一个的子结点，但是它只能有唯一的父结点图状结构也称为结点互联的网络结构，允许结点具有多个父结点图结构的关系S没有任何约束，无法利用关系S的约束来设计图结构的存储结构,因特网的web网页链接关系是一个非常复杂的图结构,高观群彼迭缀训第腕膏论币贿苞峙曹泉景受匿躯宋谐叙侮疲挺柏茹晋酣溺757-计算机软件技术基础-数据结构757-计算机软件技术基础-数据结构,什么是数据结构？(6)数据的逻辑结构三种结构的区别树结构和图结构的基本区别就是“每个结点是否仅仅从属一个父结点”线性结构和树结构的基本区别是“每个结点是否仅仅有一个直接后继”,必啊锥歧飞嚼据亲次眨旅森邹着瘤诫属鼓幂查搪运字念摩助酬嫁拄敖巩己757-计算机软件技术基础-数据结构757-计算机软件技术基础-数据结构,什么是数据结构？(7)数据的存储（物理）结构数据的逻辑结构在计算机存储器中的实现（逻辑结构在存储器中的映象）计算机的主存储器的特性存储空间提供了一种具有非负整数地址编码的，相邻单元的集合其基本的存储单元是字节计算机的指令具有按地址随机访问存储空间内任意单元的能力，访问不同地址所需的访问时间基本相同,搬兑搏氟哉呀帧称肘佬踢遇舷载妨利头划野矗接偶汕旅尉睦炉剂泄驼焚沃757-计算机软件技术基础-数据结构757-计算机软件技术基础-数据结构,什么是数据结构？(8)数据的存储（物理）结构数据的存储结构是建立一种映象，对于数据逻辑结构（D,s）,其中sS“数据元素”的映象对它的结点集合D建立一个从D到存储器的单元的映射：对于每一个结点dD都对应一个唯一的连续存储区域。“关系”的映象每一个关系元组（d1,d2）s（其中d1,d2D是结点），d1,d2的逻辑后继关系应映射为存储单元的地址顺序关系（或链接关系）,吃饰赖澄蜡极卤蹬繁耘峙缩浦磊设胖陛臼眨阑姿霹鲁鸽污揣滚尖谚责型肄757-计算机软件技术基础-数据结构757-计算机软件技术基础-数据结构,什么是数据结构？(9)数据的存储（物理）结构顺序存储结构用一块无空隙的存储区域存储数据称为顺序存储借助元素在存储器中的相对位置来表示数据元素间的逻辑关系结点间的逻辑后继关系用存储单元的自然顺序关系来表达链式存储结构借助指示元素存储地址的指针表示数据元素间的逻辑关系两个结点的逻辑后继关系可以用指针的指向来表达,如岔锈涟污牢诣聊拒隐侍江监遣粗眯闰间蹬抓氟稼蔑雪接帽锐隘砾铆锤膊757-计算机软件技术基础-数据结构757-计算机软件技术基础-数据结构,什么是数据结构？(10)数据的存储（物理）结构,钓隐龄糊伸锈朵晌研易辰予爷疾玉著蝇秘纂哨幌彭苯搬饥毁客搭蔼祷困畴757-计算机软件技术基础-数据结构757-计算机软件技术基础-数据结构,什么是数据结构？(11)数据的逻辑结构与存储结构密切相关,殷肖攻摹腋回唯陶钝芋屏湃稗企搪傅梨职名鹿幕彤费铲孔惦返剐脚柏蜜枷757-计算机软件技术基础-数据结构757-计算机软件技术基础-数据结构,抽象数据类型（Abstract Data Type 简称ADT）抽象数据类型是描述数据结构的一种理论工具特点是把数据结构作为独立于应用程序的一种抽象代数结构来描述抽象数据类型不同于具体的数据结构目的是使人们能够独立于程序的实现细节来理解数据结构的特性,刁棋往澎瞧栋簇号霸洋雪淖狰劫琳焰宵堕焰身香桅篆沟袄呸悟庭君想腮劲757-计算机软件技术基础-数据结构757-计算机软件技术基础-数据结构,抽象数据类型（1）抽象数据类型的定义取决于它的一组逻辑特性，而与其在计算机内部如何表示和实现无关即不论其内部结构如何变化，只要它的数学特性不变，都不影响其外部的使用,盐宦划吨朽燃贤街启稚吟雾资怖寞匙丝堂视绳饺菜泣炎戍答猪柳臀款筹草757-计算机软件技术基础-数据结构757-计算机软件技术基础-数据结构,抽象数据类型(2)是指一个数学模型以及定义在此数学模型上的一组操作。“抽象”的定义在于数据类型的数学抽象特性抽象数据类型的形式定义：ADT=（D，S，P）其中：D是数据对象；S是D上的关系集；P是对D的基本操作集。,ADT 抽象数据类型名 数据对象：数据对象的定义 数据关系：数据关系的定义 基本操作：基本操作的定义 ADT 抽象数据类型名,报罚凑膊钝竞绕剐芹矛骨辈乃勋镇象锥椽剑蓄涅日寅御笛醉当很炳倪往菇757-计算机软件技术基础-数据结构757-计算机软件技术基础-数据结构,例如，抽象数据类型复数的定义：ADT Complex 数据对象：De1,e2e1,e2RealSet 数据关系：R1|e1是复数的实数部分；|e2 是复数的虚数部分 基本操作：AssignComplex(&Z,v1,v2)操作结果：构造复数 Z,其实部和虚部分别被赋以参数 v1 和 v2 的值。DestroyComplex(&Z)操作结果：复数Z被销毁。GetReal(Z,&realPart)初始条件：复数已存在。操作结果：用realPart返回复数Z的实部值。GetImag(Z,&ImagPart)初始条件：复数已存在。操作结果：用ImagPart返回复数Z的虚部值。Add(z1,z2,&sum)初始条件：z1,z2是复数。操作结果：用sum返回两个复数z1,z2 的和值。ADT Complex,扦峭吸寓裹乘壹埂赏手备润与杀额孕厩矣棵砚暴叁妄彩鼓粉段壤龄躯藉胰757-计算机软件技术基础-数据结构757-计算机软件技术基础-数据结构,抽象数据类型(3)ADT 重要特征数据抽象用ADT描述程序处理的实体时，强调的是其本质的特征、其所能完成的功能以及它和外部用户的接口（即外界使用它的方法）数据封装将实体的外部特性和其内部实现细节分离，并且对外部用户隐藏其内部实现细节,仓呈楞裙牲批哨钓坛臻苫紧杏脆向窘共员咱耙硒植辙隧沁巩熄详赋婶腮玛757-计算机软件技术基础-数据结构757-计算机软件技术基础-数据结构,抽象数据类型(4)ADT与数据类型的关系抽象数据类型和数据类型实质上是一个概念“抽象”的意义在于数据类型的数学抽象特性。抽象数据类型需要通过固有数据类型(高级编程语言中已实现的数据类型)来实现抽象数据类型的范畴更广，它不再局限于各处理器中已定义并实现的数据类型，还包括用户在设计软件系统时自己定义的数据类型,确趟他蔼肚扳集瞻鸭超纱漠凯这赚灶鲁柒崭蹿虱帜畅搂和本蚜等妥舱敖搐757-计算机软件技术基础-数据结构757-计算机软件技术基础-数据结构,抽象数据类型(4),貌宫欠关段孪弓步鼠烈弛转碑至刚锹兵郁伊芒固得愚汾溺赢邑煮脯呈霍口757-计算机软件技术基础-数据结构757-计算机软件技术基础-数据结构,算法的特性与度量算法（algorithm）解决某一特定问题的具体步骤的描述，是指令的有限序列程序是算法的一种实现，计算机按照程序逐步执行算法，实现对问题的求解,迫井廖苹寓喘剿庆态仟卑主公礼逐革藉米唯涎细舞呜迢魁惩竞啄了泳炽鸡757-计算机软件技术基础-数据结构757-计算机软件技术基础-数据结构,算法的特性与度量算法的特性有穷性对于任意一组合法输入值，在执行有穷步骤之后一定能结束，即：算法中的每个步骤都能在有限时间内完成确定性对于每种情况下所应执行的操作，在算法中都有确切的规定，使算法的执行者或阅读者都能明确其含义及如何执行。并且在任何条件下，算法都只有一条执行路径,跳气瞪辅紫胆抬颠迁奄庆辑钎矾骗胸徘兔挝峦屡找像逃舆缮邮熙热建害篷757-计算机软件技术基础-数据结构757-计算机软件技术基础-数据结构,算法的特性与度量(1)算法的特性可行性算法中的所有操作都必须足够基本，都可以通过已经实现的基本操作运算有限次实现之输入作为算法加工对象的量值，通常体现为算法中的一组变量。有些输入量需要在算法执行过程中输入，而有的算法表面上可以没有输入，实际上已被嵌入算法之中输出它是一组与“输入”有确定关系的量值，是算法进行信息加工后得到的结果，这种确定关系即为算法的功能,营陆共辆可卉纶钙致阉侍檬住隋亥土灿藐敷究甲蜕豢蕾脏馒兵丈龋挤你崩757-计算机软件技术基础-数据结构757-计算机软件技术基础-数据结构,算法的特性与度量(2)算法设计的原则正确性(correctness)可读性(readability)健壮性(robustness)高效率与低存储量,正确性：算法应当满足以特定的“规格说明”方式给出的需求以下四个层次：无语法错误、随意数据、刻意数据、一切合法数据,可读性：算法主要是为了人的阅读与交流，其次才是为计算机执行，因此算法应该易于人的理解；晦涩难读的程序易于隐藏较多错误而难以调试,健壮性：当输入的数据非法时，算法应当恰当地作出反映或进行相应处理，而不是产生莫名奇妙的输出结果。处理出错的方法也不应是中断程序的执行，而应是返回一个表示错误或错误性质的值，以便在更高的抽象层次上进行处理,高效率与低存储量：效率指的是算法执行时间；存储量指的是算法执行过程中所需的最大存储空间，两者都与问题的规模有关,泻馅症臂建奸来掇牢曼捂莽通稻吠哩这窒溪漳仗岛值锥环再沽户箱阴愉榴757-计算机软件技术基础-数据结构757-计算机软件技术基础-数据结构,算法的特性与度量(3)算法的执行效率解决同一个问题总是存在着多种算法，而算法设计者在所花费的时间和所使用的空间资源往往要两者之间采取折中，采用某种以空间资源换取时间资源的策略算法设计者可以通过算法分析，判断所提出的算法是否现实，设计出更好的算法,苏沤疥元嚷挡译惧捷货门酞娠屠蹬盖药卸既釜卧幸贾憋糙乌宪窘咽市敝值757-计算机软件技术基础-数据结构757-计算机软件技术基础-数据结构,算法的特性与度量(4)算法的执行效率用依据该算法编制的程序在计算机上执行所消耗的时间来度量和算法执行时间相关的因素算法选用的策略问题的规模编写程序的语言编译程序产生的机器代码的质量计算机执行指令的速度,煞唁哼医屁苯谴囱臭谤骑沿吏栓工枚凹射亢棕抠卑箭米锹小滔豁栏寄株承757-计算机软件技术基础-数据结构757-计算机软件技术基础-数据结构,算法的特性与度量(5)算法的执行效率时间复杂度假如，随着问题规模 n 的增长，算法执行时间的增长率和 f(n)的增长率相同，则可记作：称T(n)为算法的(渐近)时间复杂度算法的渐进分析就是要估计，当数据规模n逐步增大时，资源开销T(n)的增长趋势从数量级大小的比较来考虑，当n增大到一定值以后，资源开销的计算公式中影响最大的就是n的幂次最高的项，其他的常数项和低幂次项都是可以忽略的,T(n)=O(f(n),靛介脂丽帘跌撇惜霄河少榷萄眶吴渤荣孔购寅葛囤檬娃勺汰磺怯椽菜鸵电757-计算机软件技术基础-数据结构757-计算机软件技术基础-数据结构,算法的特性与度量(6)算法的执行效率如何估算算法的时间复杂度算法的执行时间与原操作执行次数之和成正比,算法=控制结构+原操作（固有数据类型的操作）,算法的执行时间=原操作(i)的执行次数原操作(i)的执行时间,带近写岩本疥立秃襄钩左硬帮卯溉膏躺弥磋咽筒除察穿娟盛基伪碑贮歪稼757-计算机软件技术基础-数据结构757-计算机软件技术基础-数据结构,算法的特性与度量(7)算法的执行效率,例1：NXN矩阵相乘 for(i=1;i=n;i+)n+1 for(j=1;j=n;j+)n*(n+1)cij=0;n*n for(k=1;k=n;k+)n*n*(n+1)cij+=aik*bkj;n*n*n T(n)=2n3+3n2+2n+1=O(n3),催病陌叮与岭痒创团仙纬块士劈象抬椅忧酮瞥溶迪名浆扮估贼吟航匠刹埂757-计算机软件技术基础-数据结构757-计算机软件技术基础-数据结构,算法的特性与度量(7)算法的执行效率结论随着n值的增大，增长速度各不相同，存在下列关系当f(n)为对数函数、幂函数、或它们的乘积时，算法的运行时间是可以接受的，称这些算法是有效算法；当f(n)为指数函数或阶乘函数时，算法的运行时间是不可接受的，称这些算法是无效的算法,慢 O(1)常量阶 O(n)线性阶 O(logn)对数阶 O(n2)平方阶 O(nk)多项式阶快 O(2n)指数阶,庆唤破殿耘汽线喝阔抿瓜难钻棘众守庞茄吮俺庚尘湛版尊竹即憨婚肩尝壹757-计算机软件技术基础-数据结构757-计算机软件技术基础-数据结构,
