计算机科学导论第6章程序设计与算法分析.ppt

第六章 程序设计与算法分析,本章要点,初步了解程序设计的基础知识掌握结构化程序设计和面向对象程序设计的基本方法掌握数据结构中的基本数据类型及其实现掌握程序设计算法的基本思想及几种经典的算法,6.1.1 程序的概念,程序就是能够实现特定功能的一组指令序列的集合。程序设计是程序员编写一系列可存储的指令以指示计算机完成某些工作的过程。这些指令用程序设计语言写成。程序设计语言是一组专门设计的用来生成一系列可被计算机处理和执行的指令的符号集合。程序设计人员用程序设计语言写成的指令称作代码。,6.1 程序设计基础,6.1.2 计算机程序设计语言,分类：低级语言、高级语言。1）低级语言包括两种类型：机器语言和汇编语言。2）高级语言又称为程序设计语言或算法语言。,低级语言的特点,都与特定的计算机硬件系统紧密相关，来自于特定系统的指令系统，可移植性差；专业知识要求高，要求对计算机硬件的结构和工作原理非常熟悉；每条指令的功能很单一，程序员编制源程序时指令比较繁琐；由于直接针对特定硬件编程，所以，最终的可执行程序代码精炼，而且执行效率非常高。,两者主要的区别在于：机器语言无需翻译或编译，CPU能够直接识别和执行。而汇编语言必须经过汇编才能得到目标程序。,高级语言的产生,所谓高级语言是一种由表达各种意义的“词”和“公式”，按照一定的“语法规则”来编写程序的语言，又称为程序设计语言或算法语言。,高级语言的常见类型,(1)BASIC语言(2)FORTRAN语言(3)COBOL语言(4)PASCAL语言(5)C语言(6)C+语言(7)其他高级语言基于视窗类操作系统的，如Visual Basic、Visual C+、Delphi、Power Builder、Java等等。,高级语言的特点,优点：语句的功能强，源程序比较短，容易学习，使用方便，通用性较强，便于推广和交流。缺点：编译程序比汇编程序复杂，而且编译出来的目标程序往往效率不高，目标程序的长度比有经验的程序员所编的同样功能的汇编语言程序要长半以上，运行时间也要长一些。,6.1.3 高级语言的基本内容1高级语言的基本符号,高级语言都是由所谓的基本符号组成的。基本符号可以分为单字符和多字符两种情况。单字符基本符号由单个字符组成，在高级语言中通常都有下列几种单字符基本符号：(1)字母大写英文字母AZ，小写英文字母az，共52个符号。(2)数字09，共10个数字符号。,(3)特殊字符(加)，(减)，*(乘)，/(除)，(乘方)，(等号)，(左括号)，)(右括号)，(大于)，(小于)，(逗号)，(空格)等。在高级语言中的多字符基本符号由两个或两个以上的字符组成，例如GoTo(转移)、(小于或等于)、AND(与)等等。,2高级语言的基本元素,基本元素由基本符号组成，可分为数、逻辑值、名字、标号和字符串等五大类。(1)数它由09共10个基本数字和其他一些符号(如小数点“.”、正负号“、”及指数符号“E”等所构成。(2)逻辑值由真(True)和假(False)两个值表示。,(3)名字由字符组成，一般约定名字的开头是字母或者下划线，其后可为字母或数字，如XYZ、A123、_C等。名字可用来定义常量、变量、函数、过程或子程序的，也被用来定义成某些东西，故也称为标识符。在高级语言中，一般还规定了组成名字的字符的长度，即字符个数。(4)标号是在高级语言中的程序语句前所加的一个名字，主要用来指示程序可能的转移方向。,(5)字符串由一串字符所组成。在不同的高级语言中，字符串中的多个字符放在一对单引号或双引号中。,3基本的数据类型,基本的数据类型通常包括整数数据类型、实数数据类型和字符数据类型等。变量必须先定义，然后才能使用，这是条基本原则。变量实质上代表了一个特定大小的内存单元空间。,4结构数据类型,(1)数组类型数组是若干个相同类型的数据的集合。(2)用户自定义的结构体类型结构体是隶属于同一个事物的多个不同类型的数据的集合，用来表示具有若干个属性的一个事物。,5运算符与表达式,表达式是由基本符号、基本元素和各种数据通过各种运算符连接而成的。高级语言中的运算符大致包括以下几个方面：(1)逻辑运算：与、或、非、异或。(2)算术运算：加、减、乘、除、取模。(3)数据比较：大于、小于、等于、不等于。,(4)数据传送；输入、输出、赋值。(5)算术表达式：该表达式的运算结果是数，它非常近似于日常的数学公式。(6)关系运算表达式：该表达式的运算结果是逻辑值，常用的运算符包含(大于)、(小于)、(等于)、(小于等于)、(大于等于)、不等于。(7)字符串表达式：该表达式的运算结果是字符串。,6语句,语句是构成高级语言源程序的基本单位，是由基本元素、运算符、表达式等组成。,10高级语言程序的运行,使用高级语言编制程序的一般过程可以归纳为以下几个步骤：(1)使用文本编辑工具，逐条编写源程序的语句。存储源程序文件时文件的后缀名与所用的高级语言有关。(2)编译源程序文件，生成目标文件，文件后缀名通常为obj。(3)链接目标文件，生成可执行文件，文件后缀名通常为exe。(4)在计算机上执行可执行程序文件，进步调试和维护。,6.2.1 结构化程序设计方法,采用自顶向下、逐步求精的设计方法和单入口单出口的控制结构。,1.结构化程序设计思想,结构化程序设计的原则是：(1)使用顺序、选择、循环3种基本控制结构表示程序逻辑。(2)程序语句组织成容易识别的语句模块，每个模块都是单入口、单出口。(3)严格控制GOTO语句的使用。,(a)顺序结构(b)选择结构(c)while循环(d)do-while循环,2模块,一个复杂的问题可以划分为多个简单问题的组合。在自顶向下、逐步细化的过程中，把复杂问题分解成一个个简单问题的最基本方法就是模块化。模块化便于问题的分析，模块体现了信息隐藏的概念。模块常用子程序加以实现。,1面向对象的思想,OO(Object Oriented，面向对象)的程序设计把客观事物看作具有属性和行为的对象，通过抽象找出同一类对象的共同属性(静态特征)和行为(动态特征)，形成类。,6.2.2 面向对象的程序设计方法,2对象和类,对象 是基本的实体，既包括数据（属性），也包括作用于数据之上的操作（方法或函数）。类 定义了一组大体上相似的对象。一个类所包含的方法和数据描述一组对象的共同行为和属性。对象则是类的具体化，是类的实例。,3抽象,抽象 是对具体事物(即对象)进行概括，即忽略事物的非本质特征，只注意那些与当前目标有关的本质特征，从而抽象出一类对象的共性并加以描述。,4封装性,封装的两个含义：第一是，将抽象得到的数据成员和代码成员相结合，形成一个不可分割的整体，即对象，这种数据及行为的有机结合也就是封装。第二个含义称为信息隐蔽，即尽可能隐蔽对象的内部细节。,5继承性,继承性 是父类和子类之间共享数据和方法的机制。原有的类称为基类或父类，产生的新类称为派生类。,6多态性,多态性 在收到外部消息时，对象通常要予以响应。不同的对象收到同一消息可能产生完全不同的结果。,1数据、数据类型,数据 是对客观事物的符号表示。数据类型 是指具有相同取值范围和可以实施同种操作的数据的集合的总称。,6.3.1 基本概念,6.3 数据结构,2数据元素、数据项、数据对象,能够独立并完整地描述客观世界实体的基本数据单元称为数据元素，它是组成数据的基本单位。数据项是组成数据元素的不可分割的最小单位。最简单的数据元素就是由一个数据项构成的。同类数据元素的集合称为数据对象。,3数据结构,数据结构 是指数据元素之间的相互关系的集合，包括了数据的逻辑结构、物理结构以及数据的运算。,数据的逻辑结构 数据的逻辑结构是指数据元素之间的逻辑关系。数据之间可以根据不同的关系组成不同的数据结构。(2)数据的物理结构 数据的物理结构是指逻辑结构在计算机存储器中的表示。数据的物理结构不仅要存储数据本身，还要存储表示数据间的逻辑关系。,顺序结构 把所有元素存放在一片连续的存储单元中，逻辑上相邻的元素存储在物理位置相邻的存储单元中，由此得到的存储表示称为顺序存储结构。顺序存储结构常借助于程序设计语言中的数组来实现。优点是使用方法简单，缺点是必须预先分析出所需定义数组的大小。,链表结构 对逻辑上相邻的元素不要求其物理位置相邻，元素间的逻辑关系通过附设的指针域来实现，由此得到的存储表示称为链式存储结构。链式存储结构通常借助于程序设计语言中的指针来实现。,索引结构 针对每个数据结构建立一张所谓的索引表，每个数据元素占用表中的一项，每个表项包含一个能够惟一识别一个元素的关键字和用以指示该元素的地址指针。散列结构 通过构造相应的散列函数，由散列函数的值来确定元素存放的地址。,(3)数据运算 数据操作的集合。常见的数据操作有数据的插入、删除、查找、遍历等。数据操作通常由计算机程序加以实现，通常也叫算法实现。,6.3.2 线性表,1定义 线性表是由有限个相同的数据元素构成的序列，元素之间是一对一的线性关系，除了第一个元素只有直接后继、最后一个元素只有直接前驱外，其余数据元素都有一个直接前驱和一个直接后继，如图。,2运算和实现 线性表通常采用顺序和链表两种物理实现。对于经常变化的表，通常采取链表结构。,插入 在保持原有的存储结构的前提下，根据插入要求，在适当的位置插入一个元素。插入操作要求线性表要有足够的存放新元素的空间，如果空间不足，插入操作无法进行，线性表会溢出。删除 在线性表中，找到满足条件的数据元素，并删除。如果线性表为空，删除就会失败。,查询 在线性表中，按照查询条件，定位数据元素的过程就是查询。查询的条件一般根据数据元素中的关键字进行。实际上，数据的插入和删除都需要首先定位数据元素。对于空的线性表是无法查询的。遍历 是指按照某种方式，逐一访问线性表中的每一个数据元素，并执行相同处理的操作。这里的处理可以是读、写、或查询等。,6.3.3 栈,1定义 对于由N个数据元素构成的一个线性序列，如果只允许在其固定的一端位置插入和删除一个数据元素，那么这种逻辑结构的数据结构称为堆栈或栈(stack)。允许插入或删除的这一端称为栈项，另一个固定端称为栈底。当表中没有元素时称为空栈。,2运算和实现,栈的基本运算主要有：入栈、出栈和判断。入栈 入栈也叫压栈，是在栈顶添加新元素的操作，新的元素入栈后成为新的栈顶元素。出栈 出栈也叫退栈或弹栈，是将栈顶元素从栈中退出并传递给用户程序的操作,判断 判断操作用来检查栈内数据是否为空，返回结果是一个逻辑值：真或假。如果栈顶和栈底重合，说明堆栈为空。,6.3.4 队列,1定义 对于由N个数据元素构成的一个线性序列，如果在其固定的一端只允许插入数据元素，且在另一端只允许删除数据元素，则这种逻辑结构的数据结构称为队列(queue)。把允许插入的一端叫队尾(rear)，把只允许删除的一端叫队首(front)。,2运算,队列的基本运算主要有：入队、出队和判断。入队 入队是在队列中插入一个新数据元素的过程，插入在队尾进行，新的元素成为队尾，。出队 出队是在队列中删除一个数据元素的过程，删除在队首进行并把出来的数据传递给用户程序。,判断：判断操作用来检查队列是否为空，返回结果是一个逻辑值：真或假，如图。,6.3.5 树,1定义 树形数据结构中，每个数据元素称为是一个节点，除了一个惟一的所谓根节点外，其他每个节点都有且只有一个父节点，每个元素可以有多个子节点。树主要用在大型、动态列表的搜索，人工智能系统和编码算法等问题中。,2运算,树常见的基本运算有：插入、删除和遍历。插入 在树中合适的位置，添加一个节点，通常插入新的节点后，仍然应该保持该树本身所具有的性质。删除 在树中找到满足条件的节点并删除。通常删除节点后，也要保持该树本身所具有的性质。遍历 按照某种顺序或规则，对树中的每个节点逐一进行访问的过程。,3实现,6.3.6 图,1定义 在图形结构中，每个数据元素称为一个顶点，任意两个顶点之间都可能相关，这种相关性用一条边来表示，顶点之间的邻接关系可以是任意的。图可以用来描述计算机网络的拓扑结构，以及图论中获得最小生成树。除此以外，图在自然科学、社会科学和人文科学等许多领域也都有着非常广泛的应用。,2运算,常见的基本运算有：添加顶点、删除顶点、添加边、删除边和遍历图。添加顶点 在图中添加新的顶点，新添加的顶点通常是孤立的节点，还没有边连接。删除顶点 在图中去掉一个顶点，显然，在去掉一个顶点的同时还应该删除与该顶点所连接的边。,添加边 根据指定的顶点，添加相应的边。删除边 根据指定的顶点，删除相应的边。遍历图 按照一定的规则，对图中的每个数据顶点逐一进行访问。,3实现,图通常用数组和链表两种结构加以实现。对于各个顶点和顶点之间的关系分别采用邻接矩阵和邻接列表来进行描述。,6.4.1 概述,1算法的定义 准确地说，“算法(Algorithm)是一组明确的、可以执行的步骤的有序集合，它在有限的时间内终止并产生结果”。,6.4 算法分析基础,2算法的特性,(1)有穷性(可终止性)一个算法必须在有限个操作步骤内以及合理的时间内执行完成。(2)确定性 算法中的每一个操作步骤都必须有明确的含义，不允许存在二义性。(3)有效性(可执行性)算法中描述的操作步骤都是可执行的，并能最终得到确定的结果。(4)输入及输出 一个算法应该有零个或多个输入数据、有1个或多个输出数据。,3算法的描述,(1)自然语言表示 自然语言就是人们日常使用的语言，可以是中文、英文等。,(2)流程图表示 流程图是用规定的一组图形符号、流程线和文字说明来表示算法的一种表示方法。(3)伪码 伪码用一种介于自然语言与计算机语言之间的文字和符号来描述算法。比计算机语言形式灵活，格式紧凑，没有严格的语法。(4)程序设计语言形式 算法也可以用某种具体的计算机程序设计语言来表示，如，C、C+、Java等都可以用来描述算法。,例如，求两个数的较大者。用伪代码描述算法如下：Input:two number s:a,b1.if(the first number a is greater than or equal to the second number b)then 1.1 return a else 1.2 return bend if end,6.4.2 常用算法介绍,1递归算法 如果一个过程直接或间接地调用它本身，则称该过程是递归的。,2迭代算法 所谓迭代是指重复执行一组指令或操作步骤，在每次执行这组指令时，都从原来的解值的基础上推出一个新的解值。新的解值比原来的解值更加接近真实的解。这个过程不断重复，直到计算得到的解与真实解的误差满足实际要求。迭代常常用于科学计算领域对某些无法直接求解的数值问题。,3穷举算法 亦称枚举法，该算法首先根据问题的部分条件确定问题解的大致范围，然后在此范围内对所有可能的情况逐一进行验证，直到全部情况验证完毕。,4贪婪算法 贪婪算法通常具有贪婪选择性和最优子结构性。贪婪选择性指的是所求解问题的整体最优解可以通过一系列局部最优的选择，即贪婪选择来达到。最优子结构性指的是一个问题的最优解往往包含着它的子问题的最优解。,6.4.3 算法的评价,对于一个算法的评价，通常要从正确性、可理解性、健壮性、时间复杂性及空间复杂性等多个方面加以衡量。,1算法的时间复杂度,时间复杂度(Time complexity)是度量时间复杂性、即算法的时间效率的指标。时间复杂度是与求解问题规模、算法输入相关的函数，该函数表示算法运行所花费的时间。为了简化问题，通常，用算法运行某段核心代码的次数来代替准确的执行时间，记为T(n)，其中，n代表求解问题的规模，一般是指待处理的数据量的大小。,2算法的空间复杂度,算法的空间复杂度(Space complexity)用来度量算法的空间复杂性、即执行算法的程序在计算机中运行时所占用空间的大小。简单讲，空间复杂度也是与求解问题规模、算法输入相关的函数。记为S(n)，其中n代表求解问题的规模。,6.4.4 NP问题,NP(Non-deterministic Polynomial)问题，是非确定型多项式问题。所谓的非确定型，简单讲就是指算法无法直接计算出结果，只能通过进行一些有选择的“猜算”来得到结果。,6.6 本章小结,本章从程序设计的基础开始介绍，阐述了结构化程序设计和面向对象程序设计，并对这两种方法进行了比较。在数据结构中，介绍了常用的数据结构，如线性表、栈、队列、树、图等。在算法分析中，讲述了设计算法的思想，评价算法优劣的标准。,