语句的频度课件.ppt

1,第1章 绪 论,1.1 什么是数据结构 1.2 基本概念和术语 1.3 数据抽象和抽象数据类型1.4 算法描述与分析 小结 习题一,2,教学安排,课时：2学时难点：时间的渐进复杂度（语句频度）计算重点：数据结构基本概念、算法分析教学方法：多媒体教学，通过大量实例讲解基本的概念和语法习题：见课件后习题,3,1.1 什么是数据结构,数据结构的重要性：（1）考研的必考科目，很多大的软件公司面试必考内容。（2）专业基础课（学位课程），有承上启下的作用。先修课程：计算机基础、C语言程序设计、离散数学 后继课程：操作系统（队列、存储管理表、目录树）数据库原理（线性表、多链表、索引树）编译原理（栈、哈希表、语法树）人工智能（广义表、集合、搜索树、有向图）,4,1.1 什么是数据结构,在各种高级语言程序设计的基本训练中，解决某一实际问题的步骤一般是：分析实际问题；确定数学模型；编写程序；反复调试程序直至得到正确结果。所谓数学模型一般指具体的代数方程等。然而，有些实际问题无法用数学方程表示。现在来分析几个这方面的典型实例，它们的主要特点是处理数据信息的存储与检索等，而不是单纯的数值计算。例如：图书档案类问题、棋类对奕问题、交通或通信网问题。,5,表1.1 学 籍 表,首先分析图书目录卡或学籍档案类问题。设一个班级有30个学生，这个班级的学籍表如表1.1所示。,1.1 什么是数据结构,6,我们可以把每个学生的信息看成一个记录，表中的每个记录又由7个数据项组成。该学籍表由30个记录组成，记录之间是一种顺序关系。这种表通常称为线性表，数据之间的逻辑结构称为线性结构，其主要操作有检索、查找、插入或删除等。对于这些运算，显然是由计算机来完成，这就要设计相应的插入、删除和修改的算法。也就是说，数据结构还需要给出每种结构类型所定义的各种运算的算法。通过以上讨论，我们可以直观地认为：数据结构是研究程序设计中计算机操作的对象以及它们之间的关系和运算的一门学科。,1.1 什么是数据结构,7,1数据 数据是描述客观事物的数值、字符以及能输人机器且能被处理的各种字符的集合，即数据就是计算机化的信息。换句话说，数据就是对客观事物采用计算机能够识别、存储及处理的形式所进行的描述。在计算机科学中，数据的含义非常广泛，我们把一切能够输入到计算机中并 被计算机程序处理的信息，包括文字、表格、图像等，统称为数据。例如，一个学生成绩管理程序所要处理的数据，如表1.1所示。,1.2 基本概念和常用术语,8,表1.1 学生成绩表,1.2 基本概念和常用术语,9,2数据元素 数据元素也叫结点，它是组成数据的基本单位，是一个数据整体中相对独立的单元。例如，在表1.1所示的学生成绩中，为了便于处理，把其中的每一行（代表一个学生成绩）作为一个基本单位来考虑，故该数据由五个结点构成。一般情况下，一个结点还可以分割成若干具有不同属性的字段(也叫数据项)。例如，在表1.1所示的表格数据中，每个结点都由学号、姓名、数据结构、大学物理、高等数学和平均成绩六个字段构成。字段是构成数据的最小单位。,1.2 基本概念和常用术语,10,3数据对象 在数据结构中，将性质相同的数据元素的集合称之为数据对象，它是数据的一个子集。上例：一个班级的学生成绩表可以看作一个数据对象。4数据结构 数据结构由某一数据元素集合及该集合中所有数据元素之间的关系组成。具体来说，数据结构包含三个方面的内容，即数据的逻辑结构、数据的存储结构和对数据所施加的操作。,1.2 基本概念和常用术语,11,根据数据结构中数据元素之间的结构关系的不同特征，通常将数据结构分为如下四种基本结构：（1）集合结构（set）：数据元素的有限集合。数据元素之间除了“属于同一个集合”的关系之外没有其他关系。元素顺序是随意的。（2）线性结构（linear）或称序列（sequence）结构：数据元素的有序集合。数据元素之间形成一对一的关系。（3）树形结构（tree）：树是层次结构，树中数据元素之间存在一对多的关系。（4）图形结构（graph）：图中数据元素之间的关系是多对多的。,1.2 基本概念和常用术语,12,1.2 基本概念和常用术语,13,5逻辑结构 结点和结点之间的逻辑关系称为数据的逻辑结构。数据结构从逻辑结构划分为:（1）线性结构。元素之间为一对一的线性关系，第一个元素无直接前驱，最后一个元素无直接后继，其余元素都有一个直接前驱和直接后继。见图1.1中的(b)。（2）非线性结构。元素之间为一对多或多对多的非线性关系，每个元素有多个直接前驱或多个直接后继。见图1.1中的（c）和（d）（3）集合结构。元素之间无任何关系，元素的排列无任何顺序。见图1.1中（a）。,1.2 基本概念和常用术语,14,6存储结构 数据的逻辑结构是独立于计算机的，它与数据在计算机中的存储无关，要对数据进行处理，就必须将数据存储在计算机中。数据在计算机中的存储方式称为数据的存储结构。数据的存储结构主要有4种。（1）顺序存储（2）链式存储（3）索引存储（4）散列存储,1.2 基本概念和常用术语,15,7数据处理 数据处理是指对数据进行查找、插入、删除、合并、排序、统计以及简单计算等操作的过程。8数据类型 数据类型是指程序设计语言中各变量可取的数据种类，它是高级程序设计语言中的一个基本概念，和数据结构的概念密切相关。8算法 简单地说，算法就是解决特定问题的方法。特定问题可以是数值的，也可以是非数值的。解决数值问题的算法叫做数值算法。数据处理方面的算法都属于非数值算法。,1.2 基本概念和常用术语,16,1.3.1 数据抽象 抽象（abstraction）可以被理解为一种机制，其实质是抽取共同的和实质的东西，忽略非本质的细节。抽象可以使我们的求解问题过程以自顶向下的方式分步进行:首先考虑问题的最主要方面，然后再逐步细化，进一步考虑问题的某些细节，并最终实现之。数据的抽象经历了三个发展阶段：第一个发展阶段是从无类型的二进制数到基本数据类型的产生。第二个发展阶段是从基本数据类型到用户自定义类型的产生。第三个发展阶段是从用户自定义类型到抽象数据类型的出现。,1.3 数据抽象和抽象数据类型,17,1.3.2 抽象数据类型 抽象数据类型(Abstract Data Type，简称ADT)是指一个数学模型以及定义在该模型上的一组操作。抽象数据类型的定义仅取决于它的一组逻辑特性，而与其在计算机内部如何表示和实现无关，即不论其内部结构如何变化，只要它的数学特性不变，都不影响其外部的使用。,1.3 数据抽象和抽象数据类型,18,1.3.3 抽象数据类型描述和实现 抽象数据类型形式化定义可以用以下三元组表示 ADT（D，S，P）其中，D是数据对象，S是D上的关系集，P是对D的基本操作集。抽象数据类型描述的一般形式如下：ADT 抽象数据类型名称 数据对象：数据关系：操作集合：操作名1：操作名n：ADT抽象数据类型名称,1.3 数据抽象和抽象数据类型,19,1.4.1 算法及其性能标准 算法具有五个基本特征：有穷性，算法的执行必须在有限步内结束。确定性，算法的每一个步骤必须是确定的无二义性的。输入，算法可以有0个或多个输入。输出，算法一定有输出结果 可行性，算法中的运算都必须是可以实现的。,1.4 算法和算法分析,20,衡量一个算法的性能，主要有以下几个标准:正确性（corectness）:算法的执行结果应当满足预先规定的功能和性能要求。简明性（siplcty）:一个算法应当思路清晰、层次分明、简单明了、易读易懂。健壮性（robustness）:当输入不合法数据时，应能做适当处理，不至于引起严重后果。效率（efecency）:有效使用存储空间，井有高的时间效率。,1.4 算法和算法分析,21,1.4.2 算法时间复杂度和渐近时间复杂度 衡量算法的二种方法：事前分析、事后测试 如何估算算法的时间效率？和算法执行时间相关的因素如下：（1）算法所用的“策略”。（2）算法所解决问题的“规模”。（3）编程所用的“语言”。（4）“编译”的质量。（5）执行算法的计算机的“速度”。*后三条受到计算机硬件和软件的制约，“估算”只需考虑前两条。,1.4 算法和算法分析,22,1.4.2 算法时间复杂度和渐近时间复杂度 定义：如果一个问题的规模是n，解这一问题的某一算法所需要的时间为T(n)，它是n的某一函数T(n)称为这一算法的“算法时间复杂性”。一个算法的“运行工作量”通常是随问题规模的增长而增长，因此比较不同算法的优劣主要应该以其“增长的趋势”为准则。假如，随着问题规模n的增长，算法执行时间的增长率和f(n)的增长率相同，则可记作：称T(n)为算法的(渐近)时间复杂度。换句话说，当输入量n逐渐加大时，时间复杂性的极限情形称为算法的“渐近时间复杂性”。,1.4 算法和算法分析,23,在实际研究中，我们使用语句频度的数量级来衡量一个算法的时间复杂度。语句的频度（frequency count）指的是该语句重复执行的次数，下面举一个例子介绍时间复杂度的估算方法。例1 二层for循环的时间复杂度 sum=0；for(i=1;i=n;i+)for(j=1;j=n;j+)sum+；解：语句1的频度是1 语句2的频度是n1 语句3的频度是n(n+1)语句4的频度是n2 该程序的时间复杂度T(n)=2n2+2n+2=O(n2),1.4 算法和算法分析,24,又如下列三个程序段：(a)x=x+1;(b)for(i=1;i=n;i+)x=x+1;(c)for(j=1;j=n;j+)for(k=1;k=n;k+)x=x+1;现把它们看成三个简单的算法，在三个算法中语句x=x+1的频度分别为1；n；n2；,1.4 算法和算法分析,那么算法(a)，(b)，(c)的时间复杂度分别记作：T(n)=O(1)；T(n)=O(n)；T(n)=O(n2)。,25,1.4 算法和算法分析,算法描述如下：void simsort(arr a,int n)/*n和数组a的数据由主调函数提供*/for(i=0;in-1;i+)for(j=i+1;jn;j+)if(ai.data aj.data)m=ai;ai=aj;aj=m;for(i=0;in;i+)printf(n%8d%8d%10d,i,ai.num,ai.data);,26,现在来分析上述算法的时间复杂度。算法中有一个二重循环，if语句频度为,即：n2/2+n/2。现在试着忽略低次幂项n/2，只剩n2/2。然后再忽略n2/2项的常数系数1/2，本项的数量级就为n2。而算法中输出语句的频度为n，数量级显然为n。该算法的时间复杂度以最大语句频度if语句的频度n2来估算，即不考虑算法中其他语句频度，则记作：T(n)=O(n2),1.4 算法和算法分析,27,由上述各个例题可见，随着问题规模n的增大，其时间消耗T(n)也在增大。通常将这些时间复杂度分别称为常量阶O(1)，线性阶O(n)和平方阶O(n2)，算法还可能呈现的时间复杂度有指数阶和对数阶O(lbn)（log2n）等。研究算法的时间复杂度，目的是研究随着问题规模n的逐渐增大，时间消耗的增长趋势(很快、缓慢、很少)。不同数量级时间复杂度的性状如图1.3所示。,1.4 算法和算法分析,28,图1.3 各种数量级的时间复杂度,1.4 算法和算法分析,29,从图1.3中可见，随着问题规模的增大，其时间消耗也在增大，但它们的增长趋势明显不同。假设对同一个问题的解决，设计两种不同的算法A和B，算法A的时间复杂度为O(n2)，算法B的时间复杂度为O(lbn)。随着问题规模n的增大，算法A所消耗时间将会迅速增大，而算法B所消耗时间的增大趋向平缓，即增长比较慢。显然，在问题的规模n很大时算法B运行效率高，可以认为算法B优于算法A。,1.4 算法和算法分析,30,1.4.3 算法的空间复杂度 一个程序的空间复杂度(space complexity)是程序运行从开始到结束所需的存储量。程序运行所需的存储空间包括两部分：（1）固定部分(fxed space requirement)：它主要包括程序代码、常量、简单变量、定长成分的结构变量所占的空间。（2）可变部分(varible space requirement)：包括数据元素所占的空间，以及算法执行所需的额外空间，如递归栈所用的空间。,1.4 算法和算法分析,31,数据结构应讨论数据的逻辑结构、存储结构以及在数据结构上定义的一组运算和实现这些运算的算法。数据结构上的运算是在逻辑结构上定义的，而只有当存储结构确定后才能给出其实现的算法。本章介绍的使用抽象数据类型描述数据结构的方式将贯穿全书。一个数据结构的ADT描述是用户使用数据结构的规范，它应严格定义，它的实现与使用分离，实行封装和信息隐蔽。数据结构的实现必须严格符合其ADT规范，这是程序设计的基本原则之一。本章最后介绍的算法效率和算法分析的基本方法将在以后各章中用以分析算法的时间和空间效率。,小 结,32,1.简述下列术语的含义:数据、数据元素、逻辑结构、存储结构、线性数据结构和非线性数据结构。2.什么是数据结构?有关数据结构的讨论应包括哪些方面?3.什么是算法？算法的主要特点是什么？4.如何评价一个算法？5.什么是算法的时间复杂度和空间复杂度？6.确定下列各程序划线语旬的执行次数，计算它们的渐近时间复杂度。,习 题 一,33,（1）i=l;k=O;do k=k+l0*i;i+;wh1e(i=(y+l)*(y+1)y+;,习 题 一,