数据结构1第1章：绪论课件

1、数据结构与算法Data Structures and Algorithm讲课学时：44 实验学时：12，课程设计：18+1周教学安排：期末考试占60%，实验成绩占30% ，平时作业占10%考核要求：本学期上课时间：1-12周,周二5-6节，周四5-6节. 致知24考 试 时 间：14周课 程 设 计：7-15周计算机导论数字逻辑计算机组成技术操作系统数据库系统课程设计计算机网络编译原理数据结构与算法数据结构与算法课程设计多核程序设计数据库系统Linux操作系统*程序设计语言用户界面设计面向对象技术与UMLJava语言程序设计实践面向服务的计算技术.NetC+语言J2EE软件开发实践软件外包开发

2、技术*英语限选军训大学外语体育政治大学外语体育马哲英语限选体育英语限选体育英语口语英语限选英语口语工科数析代数与几何概率论与数理统计离散数学运筹学算法设计与分析工科数析理论系列系统系列工具系列工程系列管理系列其他课程第一学期第二学期第三学期第四学期第五学期第六学期第七学期第八学期系统分析与设计软件工程概论软件项目管理软件开发过程管理软件质量保证与测试软件工程综合课程设计计算机职业道德市场营销知识产权法交流技巧财务管理商务谈判IT企业管理合同法IT企业创业管理方向课计算机安全概论服务学概论中文信息处理嵌入式操作系统方向1)网络通信与信息安全 2)服务学与企业信息化 3)多媒体与信息处理 4)嵌入

3、式系统与软件 毕业设计物联网专业教 材数据结构与算法（第4版）编著 廖明宏 郭福顺 张岩 李秀坤高等教育出版社参考资料数据结构严尉敏 吴伟民 编著清华大学出版社引进教材Data Structures and Program Design in C+数据结构与程序设计C+语言描述（影印版）Robert L. Kurse, Alexandeer J. RybaISBN 7-04-010039-8/TP.691 P736教材比较1.1 数据结构研究对象1.2 数据结构发展概况1.3 抽象数据型(ADT)1.4 数据结构 与 程序设计1.5 算法描述 与 算法分析主要内容1.1 数据结构研究对象计算机

4、科学：信息在计算机内使用数据来表示, 研究信息表示和信息处理。数据：是用以描述客观事物的数值、字符，以及一切可 以输入到计算机中并由计算机程序加以处理的符 号的集合。 数据的基本单位称为数据元素 数据的最小单位称为数据项数据对象：性质相同的数据元素的集合数据特征：数值、文本、多媒体、超媒体、实时、海量数据类型?高级语言中变量的取值范围和允许的操作 什么是数据？大数据(big data)大数据可分成：大数据技术：解决大数据为题的技术和方法大数据工程：大数据工程指大数据的规划建设运营管理的系统工程；大数据科学：大数据科学关注大数据网络发展和运营过程中发现和验证大数据 的规律及其与自然和社会活动之间

5、的关系大数据应用：大数据的4个“V”：Volume：数据体量巨大。从TB级别，跃升到PB级别；Variety： 数据类型繁多。网络日志、视频、图片、地理位置信息等Value： 价值密度低。以视频为例，连续不间断监控过程中，可能有用的数据 仅仅有一两秒。Velocity：处理速度快，1秒定律。第一，大数据的基本概念第二，大数据计算及其挑战第三，研究问题与部分解大数据无处不在：因特网有很多的大数据，在科学研究领域、医疗领域、商业领域、制造业、智慧城市都有大量的数据。全世界的感知数据增长率是每年58%全世界拥有的存储能力或者是存储总量的增长率是每年只有40%2007年，全世界的感知数据已经超过了全世

6、界所拥有的存储器的容量2010年，全世界的感知数据是1.25千万PB2011年产生的感知数据已经二倍于我们人类所拥有的存储器的容量结论：大数据无处不在，数据量远远超出了现有的存储能力大数据的输入是大数据D，问题的解是f（D）。李建中教授谈大数据数据结构：数据元素彼此之间抽象的相互关系， 解决数据的 存储和组织的方式，不涉及数据元素的具体内容。 描述现实世界事物的数学模型及其操作在计算 机 中的表示和实现数据结构分类：线性表：(a1,a2,a3,ai-1,ai,ai+1an-1,an) 线性结构 线性表的一般概念、字符串、数组，广义表等树： 层次结构 二叉树，树等图： 网状结构 有向图、无向图等

7、 二叉树 有向图结构：关系，组成整体的各部分的搭配和安排 国际象棋：每次需要考虑的合乎规则的着法平均只有35 步“回合”，计算机预先分析7至8个回合的着 法。若设为7个回合，则有超过1亿亿亿个不 同的变化，经简化后，仍有500亿至600亿个 变化。多分析一步，增加18亿个变化资料：下棋程序围 棋：分析7个回合的着法，则需要考虑超过200的 14 次方个变化，经简化后，仍有1000亿亿个 变化。多分析一步，增加64万亿个变化根据计算机“深蓝”的速度，平均5分钟走一步根据计算机“深蓝”的速度，平均1.5年走一步Blue Gene,共装有32个并行处理器，速度：2亿步棋 /秒深蓝 vs 卡斯帕罗夫:

8、第一次1996年：2月10日17日， 比分2 : 4，卡斯帕罗夫赢第二次1997年：5月 3日11日， 比分3.5 : 2.5双方先后共进行6局对弈第一局，卡斯帕罗夫执白先行，经过3个多小时的苦战击败“深蓝”，力 拔头筹；第二局，“深蓝”却以凌厉的攻势和明显的优势战胜卡氏，扳回一局；第三、第四和第五局，双方下得异常激烈，鏖战数小时，平局；第六局，“深蓝”执白先行，一路强攻，仅用一个多小时， 双方仅走19步，就让卡氏俯首称臣，取得了决定性的胜利。 “神来之手”IBM“深蓝”-棋王卡斯帕罗夫卡斯帕罗夫深蓝身高5英尺10英寸6英尺5英寸体重176磅1.27吨年龄34岁4岁行棋速度2 步/每秒2 亿步

9、/每秒1980年，台湾大学电机系毕业，获得了电子工程学士学位;美国卡内基梅隆大学博士曾在IBM工作现在微软亚洲研究院卡斯帕罗夫:他在观察电脑下棋时感觉电脑的决定有智慧及创意，是他所不能理解的。他亦认为电脑在棋局中可能有人类的帮助，因此要求重赛。IBM:拒绝，并把深蓝退役。2003年一部纪录片 “游戏结束：卡斯巴罗夫与电脑” (Game Over: Kasparov and the Machine)许峰雄深蓝1996年，美国IBM公司建基于RS/6000SPAIX操作系统重1270公斤，32个微处理器每秒钟可以计算2亿步。1.1 数据结构研究对象数据结构研究方法逻辑结构：对操作对象的一种数学描述

10、，或从操作对象 中抽象出的数学模型，用以描述数据元素之 间的逻辑关系，与存储方式无关。物理结构：数据结构在计算机中的表示或映象，逻辑结构的 存储方式 物理结构又称存储结构，分为顺序映象和 非顺序映象，或称顺序存储结构和链式存储结构计算机解题过程：问题 数学模型 算法 程序 测试 计算分析数据并确定存储结构输入到计算机中数据结构研究的范畴程序设计：为计算机处理问题编制一组指令集算 法：怎么处理的策略数据结构：问题的数学模型程序设计、算法、数据结构数值计算的程序设计问题：问题算法数学模型求解一元二次方程？求根公式一组整数排序“冒泡”方法数组结构静力分析计算？线性代数方程组全球天气预报？环流模式方程

11、非数值计算的程序设计问题：问题算法数学模型求一组整数的最大值比较两个数的大小？计算机对弈对弈的规则和策略棋子、棋盘的表示足协的数据库管理什么项目？如何管理？接口？条例？规则？表格，数据库1.2 数据结构发展概况数据结构侧重解决非数值问题FORTRAN,ALGOL等高级语言是以程序为中心 侧重于解决数值问题 LISP,SONBOL表或串处理语言是以数据为中心 侧重于解决非数值问题 1968年以前，数据结构的内容大多包含在形如表、树、图论、集合代数论、格、关系等方面。1968年开始，“数据结构”逐渐开始成为独立的一门课程。 作为一门专业基础课，“数据结构”是计算机专业的核心课程之一，是其他专业课的

12、基础。是数学、硬件和软件三者的交叉，很受重视。从PASCAL语言开始逐渐形成二者结合知识结构1.3 抽象数据型Abstract Data Types（ADT） 软件系统由数据结构、操作过程和控制机能三者组成，软件设计是对三者的抽象过程，即数据抽象、过程抽象和控制抽象。定义：抽象数据型是一个数学模型和在该模型上定义 的操作的集合ADT特点：降低了软件设计的复杂性 提高了程序的可读性和可维护性 程序的正确性容易保证抽象：从众多事物中舍弃个别的、非本质的属性，抽出 共同的、本质性的特征。 是形成概念的重要手段，其目的是使复杂度降低。线性表 LIST = ( D , R)D = ai | ai Ele

13、mentset , i = 1, 2, , n, n 0 R = H H = | ai-1, ai D , i = 2 , , n 操作：设L的型为LIST线性表实例，x 的型为elementtype的元素 实例，p 为位置变量。所有操作描述为： INSERT(x, p, L) LOCATE(x, L) RETRIEVE(p, L) DELETE(p, L) PREVIOUS(p, L), NEXT(p, L) MAKENULL( L) FIRST( L)数学模型1.3 抽象数据型（ADT）举例 定义任意线性表类型为LIST，其中元素类型为Elementtype，设有线性表L，函数PURGE用

14、以删除线性表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 &A；

15、LIST B) position p ; elementtype e ; p = FIRST( B ) ; while ( p != END ( B ) e = RETRIEVE( p, B ) ; if ( same(LOCATE( e, A ) , END( A ) ) ) INSERT( e, END( A ), A ) ; p = NEXT( p, B ) ; 1.3 抽象数据型（ADT）抽象数据型的规格描述完 整 性：反映所定义的抽象数据型的全部特征统 一 性：前后协调，不自相矛盾通 用 性：适用于尽量广泛的对象不依赖性：不依赖于程序设计语言，可以用任意的语言来描述规格描述的两个方面

16、: 语法 和 语义语法：给出操作的名称、I/O参数的数目和类型语义：由一组等式组成，定义各种操作的功能及相互间的关系例如：抽象数据型栈(Stack)定义：栈是一个后进先出（LIFO）的线性表，所有插入、 删除操作是在表的一端（栈顶）进行聚集 数组， 链表(结构体、记录)，文件1.3 抽象数据型（ADT）a1a2an-1anInsertDeletetopbottom栈底栈顶栈示意图栈 ( Stack ) 示意图1.3 抽象数据型（ADT）1.3 抽象数据型（ADT）type Stack Elementtype;NEWSTACK( ) Stack,PUSH(Elementtype, Stack)

17、Stack,POP(Stack) Stack UNDEFINED,TOP(Stack) Elementtype UNDEFINED,EMPTY(Stack) Boolean; 抽象数据型栈语法：declare stk:Stack, elm:Elementtype;POP(NEWSTACK) = NEWSTACK,POP(PUSH(elm,stk) = stk,TOP(NEWSTACK) = UNDEFINED,TOP(PUSH(elm, stk) = elm,EMPTY(NEWSTACK) = TRUE,EMPTY(PUSH(elm,stk) = FALSE;抽象数据型栈语义： 规格描述给出操

18、作的名称,I/O参数的数目和类型定义各种操作的功能及相互间的关系抽象数据型的实现抽象描述 （高级语言）编写的程序三条原则：符合规格描述的定义 有尽可能好的通用性 尽可能独立于程序的其他部分多层次抽象技术自底向上与自顶向下相结合、由简单到复杂1.3 抽象数据型（ADT）1.4 数据结构与程序设计Algorithms + Data Structures = Programs算法 + 数据结构 = 程序设计 系统程序设计导论（Systematic Programming：An Introduction，Prentice-Hall，1973。算法+数据结构=程序（Algorithms Data+Str

19、uctures=Programs，Prentice-Hall，1976）。算法和数据结构（Algorithms and Data Structures，Prentice-Hall，1986）。Modula-2程序设计（Programming in Modula-2， Springer，1988，第4版）。PASCAL用户手册和报告：ISO PASCAL标准 （PASCAL User Manual and Report：ISO PASCAL Standard，Springer，1991）。Oberon计划：操作系统和编译器的设计（Project Oberon：the Design of an O

20、perating System and Compiler，ACM Pr.，1992）。Oberon程序设计：超越Pascal和Modula（Programming in Oberon：Steps beyond Pascal and Modula，ACM Pr.，1922）。数字电路设计教材（Digital Circuit Design for Computer Science Students：An Introductory Textbook，Springer，1995）。尼古拉斯沃斯（Niklaus Wirth，1934年2月15日）生於于瑞士温特图尔，瑞士计算机科学家苏黎世工学院获得学士学

21、位，美国加州大学伯克利分校获得博士学位代表性著作有：获奖 ：1984年：获图灵奖（ACM） 1987年：获计算机科学教育杰出贡献奖（ACM）。1983年：Emanual Piore奖（IEEE） 1988年：计算机先驱奖（IEEE） 1992年：加州大学伯克利分校命名威茨为“杰出校友”。1984问题解决问题的算法实现算法的程序问题总是先于算法程序设计的四个里程碑 子程序、高级语言、结构程序设计、面向对象(OOP)结构程序设计 限制使用GO TO语句（基于三种基本结构） 逐步求精的设计方法 自顶向下的设计、编码与调试 主程序员组的组织形式1.4 数据结构与程序设计问题环境数据结构程序结构读和写

22、程 序 要完成的任务可执行的操作程序结构基于数据结构的根源1.4 数据结构与程序设计 “我们对复杂性问题的最重要的办法是抽象，对一个复杂问题，不应马上用计算机指令、数字与逻辑字来表示，而应该用较为自然的抽象语句来表示，从而得出抽象程序。抽象程序对抽象的数据进行某些特定的运算并用某些合适的记号（可能是自然语言）来表示。对抽象程序作进一步的分解，并进入下一层的抽象，这样的精细化过程一直进行下去，直到程序能被计算机接受为止。此时的程序可能是某种高级语言或机器指令书写的。”N.wirth基于数据结构的jackson设计方法： 研究问题环境，确定要处理的数据结构 基于数据结构，形成程序结构（骨架） 用初

23、等操作来定义要完成的任务，并分配初等操作“从上到下，逐步求精”算法（Algorithm）：是对特定问题求解步骤的一种描述，它是指令（规则）的有限序列，其中每一条指令表示一个或多个操作。算法是在有限步骤内求解某一问题所使用的一组定义明确的规则。通俗点说,就是计算机解题的过程。在这个过程中，无论是形成解题思路还是编写程序,都是在实施某种算法。前者是推理实现的算法，后者是操作实现的算法。1.5 算法描述与算法分析资料：Algorithm与Logarithm早期的语言学家：algiros(费力的)+arithmos(数字)组合派生而成，但另一些人认为这个词是从“喀斯迪尔国王Algor”派生而来的；数学

24、史学家发现了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”(代数)，是从他的书的标题引出来的；牛津英语字典:这个词是由于同arithmetic(算术)

25、相混淆而形成的错拼词。由algorism又变成algorithm；德文数学词典 Vollstandiges Mathematisches Lexicon (数学大全辞典) ，给出了Algorithmus (算法)一词的如下定义：“在这个名称之下，组合了四种类型的算术计算的概念，即加法、乘法、减法、除法”。拉顶短语algorithmus infinitesimalis (无限小方法) ，在当时就用来表示Leibnitz(莱布尼兹)所发明的以无限小量进行计算的微积分方法；1950年左右，algorithm一词经常地同欧几里德算法(Euclids algorithm)联系在一起。这个算法就是在欧几里

26、德的几何原本中所阐述的求两个数的最大公约数的过程(即辗转相除法)。递归技术 最常用的算法设计思想，体现于许多优秀算法之中 分治法 分而制之的算法思想，体现了一分为二的哲学思想 模拟法 用计算机模拟实际场景，经常用于与概率有关的问题 贪心算法 采用贪心策略的算法设计 状态空间搜索法 被称为“万能算法”的算法设计策略 随机算法 利用随机选择自适应地决定优先搜索的方向 动态规划 常用的最优化问题解决方法 “好”的算法的标准： 正确性，算法能满足具体问题的需求 可读性，首先方便阅读与交流，其次才是机器执行 健壮性，输入错误时，能作出反应，避免异常出错 效率与低存储量要求算法的特征： 有穷性、确定性、输

27、入、输出、能行性算法效率衡量和准则：事后统计法 必须执行程序，可能有其他因素掩盖算法的本质事前分析估算法 对算法“正确性”的要求： 不含语法错误； 对于几组输入数据能得到满足要求的结果； 对精心选择苛刻并带有刁难的数据能得到满足要求的结果； 对于一切合法的输入均得到满足要求的结果；算法描述： 自然语言；程序设计语言；类语言*；关于本书采用的类语言描述： 结构类型说明 输入输出约定( cin v , cout v ) new 和 delete 引入引用类型 其他影响算法执行的因素： 算法实现后所消耗的时间* 算法实现后所占存储空间的大小* 算法是否易读、易移植等等其它问题影响时间特性的五个因素：

28、 算法选用的策略 程序运行时输入数据的总量，即问题的规模 对源程序编译所需的时间，产生机器代码的质量 计算机执行每条指令所需的时间/速度 程序中指令重复执行的次数*定义 语句频度：语句重复执行的次数程序运行时间渐近时间复杂度（时间复杂度）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(

29、n) = O( max f(n), g(n) ) 乘法规则：T1(n) T2(n) = O( f(n) g(n) )程序运行时间比较 T（n）= O（f（n）T(n)n01000200030005101520252nn3100n5n2logn2100n T(n)设：T(x) ： 取变量或常量x之值所消耗时间T(.V)： 取变量V之地址所消耗的时间T(=) ： 赋值所消耗时间T() ： 执行基本运算所耗时间T(call/return)：执行函数调用和返回所耗时间T(par) ： 将参数par传给函数所消耗时间(1) 表达式和赋值语句 exp:=常数 | 变量 | F-name(e1,e2,em)

30、 | (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 (

31、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) ki=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

32、(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; T