《数据结构与算法(C语言版)》第1章绪论.ppt

数据结构与算法（C+语言版）,第1章 绪论,教科书介绍,出版社：电子工业出版社著者：肖南峰 教授 赵洁 讲师等ISBN：978-7-121-08301-3,主要著者介绍,肖南峰博士，男，1962年11月生，华南理工大学计算机科学与工程学院教授，博士生导师。1982年7月毕业于华中工学院（现为华中科技大学）自动控制与计算机工程系，获工学学士学位；1989年1月毕业于东北工学院（现为东北大学），获工学硕士学位；2001年6月毕业于日本横浜国立大学，获工学博士学位。2001年9月至2002年9月在澳大利亚Deakin大学从事科学研究。,主要著者介绍（续）,他作为主持人先后完成了2项国家自然科学基金项目、2项广东省自然科学基金重点项目，1项教育部留学回国人员科研启动基金项目，以及由广东省教育厅和华南理工大学等资助的20多项教学与科研课题，在国内外发表学术论文120多篇，其中被三大索引收录近50篇，出版专著和教材5部，申请或获得发明及实用新型专利5项，软件版权10项。,课程内容,第一章绪论第二章线性表第三章栈和队列第四章串第五章多维数组和广义表第六章树和二叉树第七章图第八章查找第九章内部排序第十章文件组织与外排序第十一章 贪婪算法第十二章 分而治之算法第十三章 动态规划第十四章 回溯,第一章 绪论,背景：从世界上第一台计算机诞生至今，已有60多年的历史。在这期间，计算机的发展和应用已经渗透到了人类社会的各个领域，计算机加工和处理的对象也从纯粹的数值发展到了字符、图像、声音等各种具有一定结构的数据。为了更好地设计程序，以提高计算机在解决复杂问题时的处理效率，研究数据的特性和数据之间存在的关系至关重要。“数据结构”作为计算机科学与技术领域中的一门专业基础课，它专门研究数据的特性和数据之间存在的关系，以及如何在计算机中有效地存取数据和处理数据。因此，“数据结构”是设计和实现编译程序、操作系统、数据库系统和大型应用程序的重要基础，它也是介于数学、计算机硬件和计算机软件之间的一门核心课程，并将随着人类社会的各个领域中计算问题的不断深入研究而继续发展。,什么是数据结构,基本概念（1）数据：信息的载体，是客观事物的符号表示。数据能够被计算机识别、存取和处理，数据也是计算机程序加工和处理的“原料”。例如实数、字符串、图像和声音等。（2）数据项：具有独立的含义的最小标识单位。例如，字段、域、属性等。（3）数据元素：数据的基本单位。一个数据元素可由若干个数据项组成。,什么是数据结构,（4）数据对象：性质相同的数据元素的集合，是数据的一个子集。例如，26个英文字母构成的字符集合，一个学校全体学生或教师构成的学生集合或教师集合等。（5）数据结构：相互之间存在一种或多种特定关系的数据元素的集合，即数据的组织形式。数据结构的形式化定义通常用一个二元组Data_Structure=(D,R)来表示，式中，D是数据元素的有限集（也即数据对象），R是D上关系的有限集。,什么是数据结构,数据结构的内涵 数据结构一般包含数据的逻辑结构和存储结构及数据运算。数据的逻辑结构:数据的逻辑结构是指数据元素以及它们相互之间的逻辑关系，数据的逻辑结构与数据的存储无关。根据数据元素之间关系的不同特性，通常有4类逻辑结构：集合，集合的逻辑结构中所有数据元素都属于同一个集合，所有数据元素杂乱无章地聚集在一起，各个数据元素之间无任何联系；线性结构，逻辑结构中的数据元素之间存在着一个对一个的关系，各个数据元素之间通常有严格的先后次序关系；树形结构，逻辑结构中的数据元素之间存在着一个对多个的关系，各个数据元素之间通常有严格的层次关系；图状结构，逻辑结构中的数据元素之间存在着多个对多个的关系，各个数据元素之间均可能存在相互联系。,什么是数据结构,根据数据元素（结点）之间的前后相邻关系，数据的逻辑结构还可分为线性结构和非线性结构两大类：线性结构的逻辑特征是，若结构是非空集，则有且仅有一个开始结点和一个终端结点，并所有结点都最多只有一个直接前驱结点和一个直接后继结点。线性表是一个典型的线性结构，栈、队列和串等都是线性结构；非线性结构的逻辑特征是，一个结点可能有多个直接前驱和直接后继。树和图都是非线性结构。,例1-1 怎样描述数据的逻辑结构,对数据元素之间关系的描述是数据的逻辑结构，它可形式地用一个二元组表示为K=(D,R)，式中，D是由有限个结点所构成的集合，R是由有限个关系所构成的集合。有时为了直观起见，也用以图示法来表示数据的逻辑结构。逻辑结构与使用的计算机无关。例如，一批数据的逻辑结构K=(D,R)，式中，D=d1,d2,d9，R=,，则该批数据的逻辑结构如上图所示。对于R中包含有多种关系的情况，也可用类似的方法描述。,什么是数据结构,数据的存储结构数据的存储结构（物理结构）是指数据在计算机中的存储表示，它包括数据元素的表示和关系的表示。数据的存储结构有以下4种基本存储方法。顺序存储。该存储方法把逻辑上相邻的结点存储在物理位置上相邻的存储单元中，结点间的逻辑关系由存储单元的邻接关系来体现。链接存储。该方法不要求逻辑上相邻的结点在物理位置上也相邻，结点之间的逻辑关系由附加的指针字段表示。索引存储。该方法通常在存储结点信息的同时，还要建立附加的索引表。散列存储。该方法根据结点的关键字直接计算出该结点的存储地址。,什么是数据结构,数据的运算数据的运算是对数据施加的操作。数据的运算定义在数据的逻辑结构上，每种逻辑结构都有一个运算的集合。在数据结构中，运算不仅仅是加、减、乘、除等运算，大多数的运算都涉及算法的实现问题，算法的实现与数据的存储结构是密切相关的。,什么是数据结构,数据类型和抽象数据类型数据类型是一个值的集合和定义在这个值的集合上的一组操作的总称，通常它可看作是高级程序设计语言中已经实现的数据结构。按“值”的不同特性，在高级程序语言中可分为：原子类型，其值不可分解。结构类型，其值是由若干个成分按某种结构组成的，故可分解，其成分可以是非结构的，也可以是结构的。,什么是数据结构,抽象数据类型（abstract data type，ADT）是指一个数学模型以及定义在该模型上的一组操作。抽象数据类型的定义仅取决于它的一组逻辑特性，而与其在计算机内部如何表示和实现无关，也即，不论其内部结构如何变化，只要它的数学特性不变，都不会影响其外部的使用。抽象数据类型可表示为一个三元组（D,R,P），式中，D是数据对象，R是D上的关系集，P是对D的基本操作集。本书采用以下格式定义抽象数据类型：ADT抽象数据类型名 数据集合：数据关系：数据操作：ADT抽象数据类型名,什么是数据结构,其中，数据对象和数据关系的定义用伪码描述，基本操作的定义格式为：数据操作名(参数表)输入：输出：,例1-2 抽象数据类型的与数据结构的区别,ADT是高级程序设计语言中数据类型概念的推广，它是一个数学模型和定义在该模型上操作集合的总称。ADT的实现方法是，将ADT转换成现有高级程序设计语言的说明语句，加上对应于该ADT中每个操作的过程或函数，也即，用现有高级程序设计语言能够支持的适当数据结构来表示ADT中的数学模型，并用一组过程或函数来实现定义在该模型上的各个操作。数据结构则是利用该语言的基本数据类型和复合数据的构造机制来构成的。例如，数组和记录就是C+语言中两种主要的复合数据的构造机制。根据ADT定义，如果在相同的数学模型上定义两个不同的操作集，则认为它们代表两个不同的抽象数据类型。故相同的数学模型以及在其上所定义的操作有可能在不同的ADT中出现。,算法和算法分析,算法（algorithm）定义：为了解决某一类问题而设计的一个有限长的操作序列。一个算法须满足以下5个重要特性。有穷性。算法对于任意合法的输入值，在执行有限步之后一定能结束。确定性。算法中的每一个操作必须有确切的含义，无二义性，并在任何条件下，算法都只有一条执行路径。可行性。算法中的所有操作都可通过已经实现的基本运算有限次地实现。输入。算法具有零个或多个输入，这些输入为一组特定的数据对象集合。输出。算法具有一个或多个输出，它是一组与“输入”有确定关系的量值。,算法和算法分析,算法设计的要求（1）正确性（correctness）算法的执行结果应当满足预先规定的4个要求：程序不含语法错误；程序对于几组输入数据能够得出满足规格说明要求的结果；程序对于精心选择的典型、苛刻且带有刁难性的几组输入数据能得出满足规格说明要求的结果；程序对于一切合法的输入数据都能产生满足规格说明要求的结果。（2）可读性（readability）算法应有助于人们阅读、理解和调试，晦涩难懂的算法易于隐藏较多错误，难以调试和修改。,算法和算法分析,（3）健壮性（robustness）当输入不合法的数据时，算法能够做出适当的反应或处理，不至于产生莫名其妙的结果。同时，处理出错的方法应该是返回一个表示错误或错误性质的值，并终止程序的执行，以便在更高的抽象层次上进行处理。（4）时空效率（efficiency）要求算法执行的时间应该尽可能短、算法执行过程中占用的存储空间应该尽可能少。时空要求与求解问题的规模有关，两者通常相互矛盾，因此，应在它们之间有所平衡。,算法和算法分析,算法分析算法分析的两个主要方面是分析算法的时间复杂度和空间复杂度，主要考察算法的时间效率和空间效率，以便比较和改进算法。通常，在算法的运算空间较为充裕的情况下，更多地关注算法的时间复杂度。,算法和算法分析,时间复杂度算法执行的时间可通过依据该算法编制的程序在计算机上从开始运行到结束运行所消耗的时间来度量，也就是算法中每条语句的执行时间之和。一般而言，算法中基本操作的频度是问题规模n（如算法所处理的矩阵的阶数，线性表的长度）的某个函数f(n)，算法的时间量度记作T(n)=O(f(n)，它表示随问题规模n的增大，算法的执行时间增长率与f(n)的增长率相同，称为算法的渐进时间复杂度（asymptotic time complexity），简称时间复杂度。同时，要全面地分析算法，需要分别考虑算法在最坏情况、最好情况以及平均情况下的时间代价。对于最坏情况下的时间复杂度，主要采用大写数学符号O表示法来描述。一般定义为：当且仅当存在正整数c和n0，使得T(n)c f(n)对所有的nn0成立，则称该算法的渐进时间复杂度为T(n)=O(f(n)。,例1-3 如何进行算法的时间复杂度分析,首先介绍计算增长率的加法规则和乘法规则。设T1(n)和T2(n)分别是程序段P1和P2的运行时间，且T1(n)=O(f(n)，T2(n)=O(g(n)，即T1(n)是f(n)的函数，T2(n)是g(n)的函数（O函数定义见后），则执行P1之后紧接着执行P2的运行时间为：T1(n)+T2(n)=O(maxf(n)，g(n)，称为加法规则；T1(n)T2(n)=Of(n)g(n)，称为乘积规则。一般来说，分析程序的时间复杂度是，先求出各模块（各语句）的运行时间，再求整个程序的运行时间，它可表示成唯一参数输入数据的规模n的函数。具体可遵循以下规则。每个赋值或读/写语句的运行时间通常是O(1)。如果赋值语句的右部为函数调用，则要考虑计算函数值所消耗的时间。序列语句的运行时间由加法规则确定。,例1-3 如何进行算法的时间复杂度分析,语句if B then S1 else S2的运行时间为条件B的测试时间（通常取O(1)）加上两个分支语句S1、S2运行时间的较大者。若无else S2，则只需加上S1的运行时间。循环语句的运行时间是循环体本身的运行时间和计算循环参数、测试循环终止条件及跳回循环开头所花的时间，后一部分通常取O(1)。遇到多层循环时，要由内层向外层逐层分析。在分析外层循环时间时，内层循环的运行时间应该是已知的，可把内循环看成是外循环体的一部分。若程序中只包含非递归过程，则从没有调用语句（对函数也认为是调用）的过程开始，计算所有这种过程的运行时间。然后考虑有调用语句的任一过程P，在P调用的全部过程的运行时间都算完之后，即可开始计算P的运行时间。若在程序中有递归过程，则可令每个递归过程对应于一个未知的时间开销函数T(n)，其中n是过程参数的长度。之后列出一个关于T的递归方程并求解之。,例1-4 分析算法时间复杂度,下面是一个nn阶矩阵A自乘得到B=AA的算法，分析其时间复杂度。时间复杂度T(n)=n+1+n(n+1)+nn+n2(n+1)+nnn=2n3+3n2+2n+1。当n时，T(n)n3，故算法时间复杂度的数量级为O(n3)。,例1-5 求带下划线语句的频度,已知算法如下，求带下划线语句的频度。在此程序段中，语句的频度不仅是n的函数，而且与x及数组A中各分量的值有关。在这种情况下，通常考虑最坏的情况。由于while循环执行的最大数为n1，因此下划线语句频度为n1。,例1-6 分析计算n！的递归函数fact(n)的时间复杂度,递归函数fact(n)的输入规模是n，设T(n)是fact(n)的时间开销函数。在上述算法中，if语句条件测试及语句return的运行时间是O(1)，递归调用fact(n1)的运行时间是T(n1)。假设两个整数相乘和赋值操作的运算时间是O(1)，故return fact(n1)*n的运行时间是O(1)+T(n1)。因此，对于常数C和D有T(n)=D，n1；T(n)=C+T(n1)，n1。现在来解这个递归方程。设n2，对上式中T(n1)进行展开有T(n1)=C+T(n2)，代入T(n)中，有T(n)=2C+T(n2)，再展开T(n2)得T(n)=3C+T(n3)。一般有T(n)=iC+T(ni)，ni。最后，当i=n1时，得T(n)=C(n1)+T(1)=C(n1)+D。当n时，T(n)n。,算法和算法分析,空间复杂度算法在执行时需要占用一定的存储空间，这些空间除了包括程序、输入数据、常数、变量所占的空间外，还包括算法对输入数据进行运算以及为实现运算所需信息的额外空间。额外空间与算法的质量密切相关，好的算法既节省时间又节省额外空间。类似于算法的时间复杂度，一般以空间复杂度（space complexity）作为算法所需存储空间的量度，记作S(n)=O(f(n)，其中n为问题的规模（或大小）。在大多数的算法设计中，时间效率和空间效率两者很难兼得，设计者往往需要根据具体的问题进行权衡，有时会用更多的存储空间来换取时间，有的时候又会用增加算法执行时间来减少所需的存储空间。,例1-7 如何进行算法的空间复杂度分析,对算法占用存储空间的分析类似于时间复杂度。估计渐近空间复杂度，称为空间复杂度。由于问题中原始数据所占用的空间与算法无关，故一般考虑空间复杂度时只估算算法中所需增添的辅助空间。例如，例1-5中除原始数据外，只用了两个变量x和i的辅助空间。因为与问题的规模n无关，所以空间复杂度S(n)=O(1)。在一般情况下，算法的时间和空间开销是一对矛盾。要想空间比较节约，往往时间消耗就大，反之亦然。具体在一个问题中到底注重哪一方面，这要看实际的需要和可能而定。在本书中，着重考虑时间因素，而假设内存足够大。因为在求解实际问题中，当输入量急剧增加时，如果没有高效率的算法，单纯依靠提高计算机的速度，有时是无法达到要求的。,例1-7 如何进行算法的空间复杂度分析,其中，O是数学符号，它的定义是，若f(n)是正整数n的一个函数，则T(n)=O(f(n)表示存在一个正的常数M，使得当nn0时都满足T(n)Mf(n)，即表明算法所需执行时间是f(n)的常数倍。如例1-6中，当n1时，T(n)3n，即n0=1，M=3，f(n)=n。,本章总结,学习要点本章主要介绍了：数据结构和抽象数据类型（ADT）等基本概念及术语定义；算法的描述方法与设计要求；从时间和空间角度，分析算法效率和存储空间需求的方法；算法时间复杂度及空间复杂度的表示等。主要学习要点如下：数据、数据元素、数据对象、数据结构等基本概念及术语的确切定义和相互关系；数据的逻辑结构与物理结构的基本组织形式和实现方式以及抽象数据类型（ADT）的概念；算法的重要特性；算法设计的基本要求；计算算法的语句频度与估算算法时间复杂度（数量级）和空间复杂度（数量级）的方法及表示方法。,本章总结,基本要求（1）掌握数据项、数据元素、原子元素、数据对象、数据结构之间的区别及关系。（2）掌握数据的逻辑结构与数据元素之间的逻辑关系和数据存储结构的含义。（3）理解逻辑结构的4种基本组织形式和存储结构的4种不同表示方法及其特点。（4）掌握算法分析的方法和时空复杂度的表示。（5）弄清算法的概念、分类、与程序的区别、描述方法和工具（C+语言）。（6）弄清算法与运算、运算的实现、操作的相互关系和区别。,本章总结,（7）掌握算法的时间复杂度和空间复杂度的含义及数量级的概念，计算方法和表示形式。（8）弄清最坏情况下算法时间复杂度和平均时间复杂度的定义、区别、估算方法。重点与难点重点：数据结构的概念、逻辑结构和存储结构的组织和表示形式，描述算法的C+语言。难点：最坏情况下算法的时间复杂度分析。,