认识数据结构与算法

数据结构课程说明•《数据结构》是计算机程序设计的重要理论基础，是计算机类专业的一门实践性很强的专业技术基础课。•本课程的主要任务是使学生较全面地理解算法和数据结构的概念，了解与它们有关的基本问题，并学会在解决问题、设计程序的过程中正确地分析处理这些问题。学习情境1认识数据结构与算法学习情境1认识数据结构与算法•教学提示：本章主要介绍数据结构的概念及有关术语，为后续章节做好铺垫。•教学目标：通过本章的学习，使读者能掌握数据结构的概念和有关的术语。学习情境1认识数据结构与算法•任务一初识数据结构和算法•任务二数据结构•任务三算法1.1任务一初识数据结构和算法子任务1什么是数据结构和算法•数据结构：是一门研究非数值计算的程序设计问题中计算机的操作对象（数据元素）以及它们之间的关系和运算等的学科。•这门学科主要是研究各种结构、定义在各种结构上的操作和这些操作在计算机中的实现方法。•数据结构研究实际问题中元素之间的逻辑关系、元素及其关系在计算机中的表示和相关的操作。数据结构是一门综合性的专业基础课，它涉及到计算机硬件的研究范围和软件的研究范围(存储装置和存取方法等)。1.1任务一初识数据结构和算法子任务1什么是数据结构和算法•算法：是一系列解决问题的清晰指令，算法代表着用系统的方法描述解决问题的策略机制。•一个算法的优劣可以用空间复杂度和时间复杂度以及稳定性来衡量。1.1任务一初识数据结构和算法子任务2数据结构和算法的重要性•数据的组织结构：•数据的逻辑结构•数据的存储结构•数据结构与算法的关系•数据结构的算法的重要基础•数据结构与算法是程序设计的基础子任务3数据结构与算法课程数学代数系统编译理论存储装置硬件(计算机系统设计)算子关系数据类型数据表示法数据的操作数据结构数据存取机器组织文件系统数据组织信息检索软件(计算机程序设计)1.用计算机如何解决问题：(1)从具体问题中抽象出一个适当的数学模型。即从具体问题中找出操作对象之间含有的关系，然后用数学语言加以描述。(2)设计一个适合该数学模型的算法。(3)编写程序。(4)进行测试、调整、修改，直至解决问题。1.2任务二数据结构子任务1数据处理1.2任务二数据结构•数据(Data)：数据是计算机表示客观事物的符号。在计算机科学中，所有能输入到计算机中并被计算机程序处理的符号统称为数据。它是计算机程序加工的“原料”。例如，一个用某种程序语言编写的源程序、一篇文章、一张地图、一幅照片、一首歌曲等等，都属于计算机能处理的数据。因此，对计算机科学而言，数据的含义极为广泛；图象、声音等也都可以通过编码而归之于数据的范畴。子任务1数据处理2.数据相关术语：•数据元素：数据元素是数据的基本单位。数据的范围非常广泛，数据元素也是可大可小的。在计算机程序中通常作为一个整体进行考虑和处理。有时，一个数据元素可由若干个数据项组成。例如，一本书的书目信息为一个数据元素，而书目信息中的每一项(如书名、作者名)是数据项。•数据项：数据项是组成数据元素的最小单位——字段、域，是对数据属性的描述。•关键字：关键字是指能识别一个或多个数据元素的数据项。若能唯一识别，则称为主关键字，否则称为次关键字。•数据对象：数据对象是性质相同的数据元素组成的集合，是数据的一个子集。•数据处理：数据处理是指对数据进行查找、插入、删除、合并、排序、统计以及简单计算等操作的过程。•数据类型数据类型是指程序设计语言中各变量可取的数据种类。数据类型是高级程序设计语言中的一个基本概念，它和数据结构的概念密切相关。•数据的组织结构：数据的组织结构分别为逻辑结构、存储结构和数据的运算。数据结构是彼此具有一定关系的数据元素的集合。这些关系反映了客观世界事物之间的联系。这种数据元素之间的相互关系称为结构。由于客观事物存在着各种不同的联系形式，因此在计算机内反映数据的关系时，可以用结构来描述这些关系。1.2任务二数据结构子任务2数据结构的分类•数据的逻辑结构：集合：这个结构中的数据元素之间同属于一个集合，除这一关系外没有其他关系。线性结构：这个结构中数据元素存在着由依次排列的先后次序决定的关系。树形结构：这个结构中数据元素之间存在着层次关系。图形结构：这个结构中数据元素之间相互连接成网状。图1四种基本逻辑结构数据结构是一个二元组：DS=（D，R）D——数据对象R——D上关系的集合例：设有一数据结构（D，R），其中D={a，b，c，d，e}，R={a,b，b,c，c,d，d,e}，则其逻辑结构可描述如下：a→b→c→d→e•数据的存储结构：数据结构在计算机中的表示称为数据的物理结构，又称为存储结构。存储结构是指在计算机中存储数据和逻辑结构。同一种逻辑结构可以使用不同的物理结构来实现。数据元素之间的关系在计算机中有两种基本的存储结构：顺序存储结构和链式存储结构。存储结构的内容：存储结点、存储逻辑结构、附加设施存储方式：顺序存储、链接存储、索引存储、散列存储数据的运算：运算可以分为下列两种基本类型：(1)加工型运算：运算后改变了原结构中数据元素的个数或数据元素的内容。(2)引用型运算：运算不改变结构中数据元素的个数和元素的内容，只从结构中提取某些信息作为运算的结果。基本运算主要包括下列几种：插入运算：属于加工型运算，在原结构的指定位置上增添新的数据元素。删除运算：属于加工型运算，将原结构中的某个指定的数据元素删除。查找运算：属于引用型运算，从结构中找出满足条件的数据元素的位置。读取运算：属于引用型运算，使用结构中满足条件的数据元素的内容。更新运算：属于加工型运算，更换结构中某个数据元素的内容。1.2任务二数据结构子任务3常用的数据结构a0a1…ai…anABC进栈出栈数组栈：后进先出队列：先进先出ABC出队进队链表树图a0a1an^…ABDEFGCHIABCDE1.3任务三算法子任务1认识算法1.算法的历史：2.算法分类：3.经典算法与箸作:•输入有0个或多个输入•输出有一个或多个输出(处理结果)•确定性每步定义都是确切、无歧义的•有穷性算法应在执行有穷步后结束•可行性算法原则上能够精确地运行，即算法中描述的操作都是可以通过已经实现的基本运算执行有限次来实现。子任务2算法的重要特征数据结构+算法=程序算法的设计目标◎正确性——合理的数据输入下，在有限的运行时间内得出正确的结果。◎健壮性——对不合理的数据输入的反应和处理能力。◎可读性——供人们阅读的方便程度。◎高效性——算法的效率主要从时间和空间两个方面考虑。解决一个问题的算法如果使用时间少和占用空间少，则是算法高效率的体现。。算法的时间复杂度◎算法运行时间大致等于计算机执行一个简单操作的时间与算法所包含简单操作次数之积。◎算法包含的简单操作次数的多少叫做时间复杂度。◎若解决一个问题的规模为n，则T(n)＝O(f(n))。研究算法的效率称为算法复杂度的分析(简称算法分析)。简单地说，一个算法所进行的计算次数的多少称为时间复杂度，一个算法所需要辅助存储空间的多少称为空间复杂度。子任务3算法分析算法分析中绝对的量不能反映时间复杂度，使用一个函数T(n)表示一个算法的复杂度。一个算法所解决问题的规模n增大时，时间的增长率越小，时间复杂度越好，反之时间复杂度越坏。也就是说，时间复杂度是n的一个函数。从好到坏表示时间复杂度的函数依次是：常量阶O(1)；对数阶O(logn)；线性阶O(n)；平方阶O(n2)；多项式阶O(nk)；指数阶O(2n)等。算法的时间复杂度计算运行时间要遵循下面的法则。1.法则1——赋值语句的运行时间：12.法则2——for循环的运行时间：循环次数3.法则3——嵌套for循环的运行时间从里面到外面分析这些循环。每一层循环的运行时间等于该层的for循环语句的运行时间乘以该层循环内所有的for循环的运行时间。4.法则4——顺序语句的运行时间将各个语句的运行时间求和即可，总的运行时间为其中的最大值。5.法则5——IF/ELSE语句的运行时间6.法则6——递归函数的复杂度分析算法复杂度，举例：①{x++;s=x+2;}时间复杂度为O(1)②for(k=1;k=n;k++)s=k+2时间复杂度为O(n)③for(k=1;k=n;k++)for(j=1;j=n;j++)s=k+j；时间复杂度为O(n2)空间复杂性（SpaceComplexity）◎算法运行中占用空间包括算法本身占用，输入输出数据占用和运行中的临时占用。◎同一个问题，算法不同，运行中的临时空间不同，即空间复杂性不同。◎SC只考虑在运行中为局部变量分配的存贮空间的大小，一般也以数量级表示。S(n)=O(f(n))常见函数的增长率子任务4算法设计方法•递推法•递归•穷举搜索法•贪婪法•分治法•动态规划法•迭代法子任务5递归算法及案例•案例1：阶乘比较非递归算法和递归算法•案例2：汉诺塔本章小结•(1)数据结构研究的三方面内容是数据的逻辑结构、数据的存储结构和对数据的运算。数据的逻辑结构可分为集合、线性、树和图四种基本结构。数据的存储结构有顺序、链式、索引和散列四种存储结构。•(2)算法是对特定问题求解步骤的一种描述，是指令的有限序列。算法具有有穷性、确定性、可行性、输入、输出特性。•(3)一个好的算法应该达到正确性、可读性、健壮性、高效性和低存储量等目标。•(4)算法的效率通常用时间复杂度和空间复杂度来评价，应该掌握其基本分析方法。一般只要大致计算出相应的数量级即可。一个算法的时间和空间复杂度越好，则算法的效率就越高。(1)逻辑结构是_____________关系的整体。A.数据元素之间逻辑B.数据项之间逻辑C.数据类型之间D.存储结构之间(2)数据结构有_____________种基本逻辑结构。A.1B.2C.3D.4(3)下列四种基本的逻辑结构中，数据元素之间关系最弱的是_______。A.集合B.线性结构C.树形结构D.图状结构(4)下列时间复杂度中最坏的是_____________。A.O(1)B.O(n)C.O(log2n)D.O(n2)(5)下列算法的时间复杂度是_____________。for(i=0;in;i++)for(j=0;jn;j++)c[i][j]=i+j;A.O(1)B.O(n)C.O(log2n)D.O(n2)(6)下列算法的时间复杂度是_____________。for(i=0;in;i++)c[i][i]=i+i;A.O(1)B.O(n)C.O(log2n)D.O(n2)