资源描述
数据结构与算法 Data structures and Algorithm,理论系列,系统系列,工具系列,工程系列,管理系列,其他课程,第一 学期,第二 学期,第三 学期,第四 学期,第五 学期,第六 学期,第七学期,第八学期,方向1选修：网络通信与信息安全 网络管理与设计 网络布线系统 网络应用开发 电信业务运营及支撑系统,方向2选修：服务学与企业信息化 企业资源计划 企业与服务建模 供应链与客户关系管理 服务管理 服务工程综合实践,方向3选修：多媒体与信息处理 多媒体技术 信息检索 计算机图形学 游戏设计,方向4选修：嵌入式系统与软件 J2ME移动终端开发技术 嵌入式软件开发 嵌入式系统与应用 嵌入式系统测试技术,毕业设计,教 材,数据结构与算法 （第4版） 编著 廖明宏 郭福顺 张岩 李秀坤 高等教育出版社,参考资料,数据结构 严尉敏 吴伟民 编著 清华大学出版社,引进教材,Data Structures and Program Design in C+ 数据结构与程序设计C+语言描述（影印版） Robert L. Kurse, Alexandeer J. Ryba ISBN 7-04-010039-8/TP.691 P736,教材比较,1.1 数据结构研究对象 1.2 数据结构发展概况 1.3 抽象数据型(ADT) 1.4 数据结构 与 程序设计 1.5 算法描述 与 算法分析,主要内容,1.1 数据结构研究对象,计算机科学：信息在计算机内使用数据来表示, 研究信息表示和信息处理。,数据：是用以描述客观事物的数值、字符，以及一切可 以输入到计算机中并由计算机程序加以处理的符 号的集合。 数据的基本单位称为数据元素 数据的最小单位称为数据项,数据对象：性质相同的数据元素的集合,数据特征：数值、文本、多媒体、超媒体、实时、海量,数据类型?,高级语言中变量的取值范围和允许的操作,什么是数据？,数据结构：研究的数据对象中的数据元素彼此之间抽象的 相互关系，并不涉及数据元素的具体内容,数据结构分类：,线性表：(a1,a2,a3,ai-1,ai,ai+1an-1,an) 线性结构 线性表的一般概念、字符串、数组，广义表等,树： 层次结构 二叉树，树等,图： 网状结构 有向图、无向图等,结构：关系,国际象棋：每次需要考虑的合乎规则的着法平均只有35 步“回合”，计算机预先分析7至8个回合的着 法。若设为7个回合，则有超过1亿亿亿个不 同的变化，经简化后，仍有500亿至600亿个 变化。多分析一步，增加18亿个变化,资料：下棋程序,围 棋：分析7个回合的着法，则需要考虑超过200的 14 次方个变化，经简化后，仍有1000亿亿个 变化。即使“深蓝”也得1.5年时间想好一步。 多分析一步，增加64万亿个变化,根据计算机“深蓝”的速度，平均5分钟走一步,根据计算机“深蓝”的速度，平均1.5年走一步,Blue Gene, 共装有32个并行处理器，速度：2亿步棋 /秒,深蓝 vs 卡斯帕罗夫: 第一次1996年：2月10日17日， 比分2 : 4 第二次1997年：5月 3日11日， 比分3.5 : 2.5 双方先后共进行6局对弈 第一局，卡斯帕罗夫执白先行，经过3个多小时的苦战击败“深蓝”，力 拔头筹； 第二局，“深蓝”却以凌厉的攻势和明显的优势战胜卡氏，扳回一局； 第三、第四和第五局，双方下得异常激烈，鏖战数小时，平局； 第六局，“深蓝”执白先行，一路强攻，仅用一个多小时， 双方仅走19步，就让卡氏俯首称臣，取得了决定性的胜利。,IBM：“深蓝”与棋王卡斯帕罗夫的对比: 身高：卡斯帕罗夫5英尺10英寸，“深蓝”6英尺5英寸；体重：卡斯帕罗夫176磅，“深蓝”1.4吨； 年龄：卡斯帕罗夫34岁，“深蓝”4岁； 每秒行棋速度：卡斯帕罗夫 2 步，“深蓝” 2 亿步。,“神来 之手”,1.1 数据结构研究对象,数据结构研究方法：,逻辑结构：对操作对象的一种数学描述，或从操作对象 中抽象出的数学模型，用以描述数据元素之 间的逻辑关系,物理结构：数据结构在计算机中的表示或映象， 物理结构又称存储结构，分为顺序映象和 非顺序映象，或称顺序存储结构和链式存储结构,计算机解题过程：,1.2 数据结构发展概况,数据结构侧重解决非数值问题,FORTRAN,ALGOL等高级语言是以程序为中心 侧重于解决数值问题, LISP,SONBOL表或串处理语言是以数据为中心 侧重于解决非数值问题, 1968年以前，数据结构的内容大多包含在形如表、树、 图论、集合代数论、格、关系等方面。1968年开始，“数据 结构”逐渐开始成为独立的一门课程。, 作为一门专业基础课，“数据结构”是计算机专业的核心 课程之一，是其他专业课的基础。是数学、硬件和软件三者 的交叉，很受重视。,从PASCAL语言开始逐渐形成二者结合,知 识 结 构,1.3 抽象数据型Abstract Data Types（ADT）, 软件系统由数据结构、操作过程和控制机能三者组 成，软件设计是对三者的抽象过程，即数据抽象、过程 抽象和控制抽象。,定义：抽象数据型是一个数学模型和在该模型上定义 的操作的集合,ADT特点：降低了软件设计的复杂性 提高了程序的可读性和可维护性 程序的正确性容易保证,抽象：从众多事物中舍弃个别的、非本质的属性，抽出 共同的、本质性的特征。 是形成概念的重要手段，其目的是使复杂度降低。,举例 ,1.3 抽象数据型（ADT）,定义任意线性表类型为LIST，其中元素类型为Elementtype， 设有线性表L，函数PURGE用以删除线性表L中所有重复出 现的元素。,Void PURGE ( LIST L ) Position p, q ; p = FIRST(L) ; while ( p != END(L) ) q = NEXT(p , L) ; while (q != END(L) ) if (same(RETRIEVE(p,L),RETRIEVE(q,L) DELETE(q,L) ; else q = NEXT(q,L) ; p = NEXT(p,L) ; ,举例 ,1.3 抽象数据型（ADT）,假设利用两个线性表LA和LB分别表示两个集合，设计算法 求一个新的集合 A = A B。,Void UNION( LIST ,1.3 抽象数据型（ADT）,抽象数据型的规格描述,完 整 性：反映所定义的抽象数据型的全部特征 统 一 性：前后协调，不自相矛盾 通 用 性：适用于尽量广泛的对象 不依赖性：不依赖于程序设计语言，可以用任意的语言来描述,规格描述的两个方面: 语法 和 语义,语法：给出操作的名称、I/O参数的数目和类型 语义：由一组等式组成，定义各种操作的功能及相互间的关系,例如：抽象数据型栈(Stack),定义：栈是一个后进先出（LIFO）的线性表，所有插入、 删除操作是在表的一端（栈顶）进行,聚集 数组， 链表(结构体、记录)，文件,栈 ( Stack ) 示意图,1.3 抽象数据型（ADT）,规格描述,给出操作的名称,I/O参数的数目和类型,定义各种操作的功能及相互间的关系,1.3 抽象数据型（ADT）,1.4 数据结构与程序设计,问题总是先于算法,程序设计的四个里程碑 子程序、高级语言、结构程序设计、面向对象(OOP),结构程序设计 限制使用GO TO语句（基于三种基本结构） 逐步求精的设计方法 自顶向下的设计、编码与调试 主程序员组的组织形式,N.Wirth： Programming = Algorithm + Data Structure 程序设计 = 算法 + 数据结构,1.4 数据结构与程序设计,程序结构基于数据结构的根源,1.4 数据结构与程序设计,“我们对复杂性问题的最重要的办法是抽象，所以，对一个复杂 问题，不应马上用计算机指令、数字与逻辑字来表示，而应该用较 为自然的抽象语句来表示，从而得出抽象程序。抽象程序对抽象的 数据进行某些特定的运算并用某些合适的记号（可能是自然语言） 来表示。对抽象程序作进一步的分解，并进入下一层的抽象，这样 的精细化过程一直进行下去，直到程序能被计算机接受为止。此时 的程序可能是某种高级语言或机器指令书写的。”N.wirth,基于数据结构的jackson设计方法： 研究问题环境，确定要处理的数据结构 基于数据结构，形成程序结构（骨架） 用初等操作来定义要完成的任务，并分配初等操作,“从上到下，逐步求精”,算法（Algorithm）：是对特定问题求解步骤的一种描述，它是 指令（规则）的有限序列，其中每一条指令表示一个或多个操作。,算法是在有限步骤内求解某一问题所使用的一组定义明确的规则。通俗点说,就是计算机解题的过程。在这个过程中，无论是形成解题思路还是编写程序,都是在实施某种算法。前者是推理实现的算法，后者是操作实现的算法。,Persian Textbook(波斯教科书)的作者的名字Abu Jafar Mohammed ibn Ms al-Khowrizm （约公元前825年） 从字面上看，这个名字的意思是“Jafar 的父亲，Mohammed 和 Ms 的儿子，Khowrizm 的本地人”。Khowrizm 是前苏联XBA(基发) 的小城镇 。Al-Khowrizm 写了著名的书Kitab al jabr wal-muqabala (复原和化简的规则)；,1.5 算法描述与算法分析,资料：Algorithm与Logarithm 这个词一直到1957年之前在Websters New World Dictionary(韦氏新世界词典)中还未出现，我们只能找到带有它的古代涵义的较老形式的“Algorism”(算术)，指的是用阿拉伯数字进行算术运算的过程。在中世纪时，珠算家用算盘进行计算，而算术家用算术进行计算。中世纪之后，对这个词的起源已经拿不准了，早期的语言学家试图推断它的来历，认为它是从把algiros(费力的)+arithmos(数字)组合起来派生而成的，但另一些人则不同意这种说法，认为这个词是从“喀斯迪尔国王Algor”派生而来的。最后，数学史学家发现了algorism(算术)一词的真实起源：它来源于著名的Persian Textbook(波斯教科书)的作者的名字Abu Jafar Mohammed ibn Ms al-Khowrizm （约公元前825年）从字面上看，这个名字的意思是“Jafar 的父亲，Mohammed 和 Ms 的儿子，Khowrizm 的本地人”。Khowrizm 是前苏联XBA(基发) 的小城镇 。Al-Khowrizm 写了著名的书Kitab al jabr wal-muqabala (复原和化简的规则)；另一个词，“algebra”(代数)，是从他的书的标题引出来的，尽管这本书实际上根本不是讲代数的。 逐渐地，“algorism”的形式和意义就变得面目全非了。如牛津英语字典所说明的，这个词是由于同arithmetic(算术)相混淆而形成的错拼词。由algorism又变成algorithm。一本早期的德文数学词典 Vollstandiges Mathematisches Lexicon (数学大全辞典) ，给出了Algorithmus (算法)一词的如下定义：“在这个名称之下，组合了四种类型的算术计算的概念，即加法、乘法、减法、除法”。拉顶短语algorithmus infinitesimalis (无限小方法) ，在当时就用来表示Leibnitz(莱布尼兹)所发明的以无限小量进行计算的微积分方法。 1950年左右，algorithm一词经常地同欧几里德算法(Euclids algorithm)联系在一起。这个算法就是在欧几里德的几何原本(Euclids Elements ,第VII卷，命题i和ii)中所阐述的求两个数的最大公约数的过程(即辗转相除法)。,递归技术 最常用的算法设计思想，体现于许多优秀算法之中 分治法 分而制之的算法思想，体现了一分为二的哲学思想 模拟法 用计算机模拟实际场景，经常用于与概率有关的问题 贪心算法 采用贪心策略的算法设计 状态空间搜索法 被称为“万能算法”的算法设计策略 随机算法 利用随机选择自适应地决定优先搜索的方向 动态规划 常用的最优化问题解决方法,“好”的算法的标准： 正确性，算法能满足具体问题的需求 可读性，首先方便阅读与交流，其次才是机器执行 健壮性，输入错误时，能作出反应，避免异常出错 效率与低存储量要求,算法的特征： 有穷性、确定性、输入、输出、能行性,对算法“正确性”的要求： 不含语法错误； 对于几组输入数据能得到满足要求的结果； 对精心选择苛刻并带有刁难的数据能得到满足要求的结果； 对于一切合法的输入均得到满足要求的结果；,算法描述： 自然语言；程序设计语言；类语言*；,关于本书采用的类语言描述： 结构类型说明 输入输出约定( cin v , cout v ) new 和 delete 引入引用类型 其他,影响算法执行的因素： 算法实现后所消耗的时间* 算法实现后所占存储空间的大小* 算法是否易读、易移植等等其它问题,影响时间特性的四个因素： 程序运行时输入数据的总量 对源程序编译所需的时间 计算机执行每条指令所需的时间 程序中指令重复执行的次数*,定义 语句频度：语句重复执行的次数,程序运行时间,渐近时间复杂度（时间复杂度）T（n）,算法中基本操作重复执行的次数是问题规模n的某个函数 f（n），算法的时间度量记作： T（n）= O（ f（n） 它表示随问题规模n的增大，算法执行时间的增长率和 f（n）的增长率相同。,渐近空间复杂度（空间复杂度）S（n）,S（n）= O（ g（n）,运算法则： 设：T1(n)=O( f(n) )，T2(n)=O( g(n) ) 加法规则：T1(n)+T2(n) = O( max f(n), g(n) ) 乘法规则：T1(n) T2(n) = O( f(n) g(n) ),设：,T(x) ： 取变量或常量x之值所消耗时间 T(.V)： 取变量V之地址所消耗的时间 T(=) ： 赋值所消耗时间 T() ： 执行基本运算所耗时间 T(call/return)：执行函数调用和返回所耗时间 T(par) ： 将参数par传给函数所消耗时间,(1) 表达式和赋值语句 exp:=常数 | 变量 | F-name(e1,e2,em) | (exp exp) T(v=exp)=T(.v)+T(=)+T(exp) T(exp exp)=T(exp)+T()+T(exp) T(F-name(e1,e2,em)=T(call/return)+mT(par)+T(F-body) 例： T(c=a+b)=T(.c)+T(=)+T(a)+T(+)+T(b) 相应的汇编程序为： load a in R1 load b in R2 add R2 to R1 load .c in R2 store R1 in R2,通常取O(1),(2) 语句序列 T(s1,s2,sk)=maxT(s1),T(s2),T(sk) (3) 条件语句 T( if (B) s1 else s2)=T(B)+T(else)+maxT(s1),T(s2) 通常取T(B)+T(else)=O(1) T(if(B) s )=O(1)+T(s) (4) Switch语句 设语句s switch(E) case E1: S1; case Ek: Sk; default : Sm T(s)=T(E)+T(Ei)+maxT(s1),T(sk),T(sm) O(1),k i=1,(5) for语句 T( for(i=1;i=n;i+) s ) =(T(s)+T(i=1)+T(i=n)+T(i+)+T(for),O(1),(6) while语句 while(B) s i=0;while(B) s ; i+ 设RT0表示某一次循环开始执行时的绝对时间 关于循环的定时不变式RT为 RT=RT0+(i+1)(T(B)+T(while)+i(T(s)+T(j) 其中：T(while)代表测试循环终止条件所耗时间 T(j)代表跳回循环头所耗时间 可简化成：T(j)=T(while) T(while(B)s)=RT-RT0=(i+1)T(B)+iT(s)+(2i+1)T(while),(7) 函数调用 非递归调用：被调用子函数运行时间 递归调用：求解递归方程 (8) goto语句 goto语句破坏了程序结构 一般对goto语句限制使用 对有条件的goto转移可忽略不计,举例： s = 0 ; f(n) = 1; T1(n) = O(f(n) = O(1) 常量阶 for ( i=1 ; i = n ; +i ) +x; s += x; f(n) = 3n+1; T2(n) = O(f(n) = O(n) 线性阶 for ( i=1; i=n ; +i ) for( j=1 ; j =n ; +j ) +x ; s += x; f(n) = 3n2+2n+1; T3(n) = O(f(n) = O(n2) 平方阶 for ( i=1; i=n ; +i ) for ( j=1 ; j =n ; +j ) cij = 0; for ( k=1 ; k = n; +k ) cij += aik * bkj ; f(n) = 2n3+3n2+2n+1; T4(n) = O(f(n) = O(n3) 立方阶,Void BUBBLE(A) int An; int I,j,temp; for(i=0;i=i+1;j-) O(n-i-1) if(Aj-1Aj) O(n-i-1) 1) O(n(n-1)/2) temp=Aj-1; O(1) O(1) =(n-i-1) =O(n2) Aj-1=Aj; O(1) O(1) Aj=temp; O(1) ,n-2 i=0,举例： Long fact ( int n) if ( n=0 ) | ( n =1 ) return( 1 ); else return( n * fact( n 1 ) ); ,f( n ) = n G T( n ) = O( f( n ) ) = O( n ),数据结构基本思路,逻辑结构 存储结构 特殊结构 结构应用举例,型,线性表 线性结构 树及二元树 层次结构 图 网状结构,三大数据结构类型,数据结构附加内容,查找（检索） 排序（分类） 文件,练习题目：实现线性表的链式存储结构线性链表。从文件输入 一批整数，建立有序链表（升序），并完成： 查找一个指定元素 插入一个给定元素 删除一个指定元素 统计链表的长度 输出线性链表 实现安逆序链表的重建 要求： 输入/输出文件名由键盘输入 操作的结点由键盘输入 所有操作由键盘控制,命令行： Create,Delete, Insert, Search,Display,deleteAll,Count,Revers,Free,课后习题：P22（1-7）,
展开阅读全文