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

第六章程序设计与算法分析本章要点◆初步了解程序设计的根底知识◆掌握结构化程序设计和面向对象程序设计的根本方法◆掌握数据结构中的根本数据类型及其实现◆掌握程序设计算法的根本思想及几种经典的算法6.1.1程序的概念程序就是能够实现特定功能的一组指令序列的集合。程序设计是程序员编写一系列可存储的指令以指示计算机完成某些工作的过程。这些指令用程序设计语言写成。程序设计语言是一组专门设计的用来生成一系列可被计算机处理和执行的指令的符号集合。程序设计人员用程序设计语言写成的指令称作代码。6.1程序设计根底6.1.2计算机程序设计语言分类：低级语言、高级语言。1〕低级语言包括两种类型：机器语言和汇编语言。2〕高级语言又称为程序设计语言或算法语言。低级语言的特点①都与特定的计算机硬件系统紧密相关，来自于特定系统的指令系统，可移植性差；②专业知识要求高，要求对计算机硬件的结构和工作原理非常熟悉；③每条指令的功能很单一，程序员编制源程序时指令比较繁琐；④由于直接针对特定硬件编程，所以，最终的可执行程序代码精炼，而且执行效率非常高。两者主要的区别在于：机器语言无需翻译或编译，CPU能够直接识别和执行。而汇编语言必须经过汇编才能得到目标程序。高级语言的产生所谓高级语言是一种由表达各种意义的“词〞和“公式〞，按照一定的“语法规那么〞来编写程序的语言，又称为程序设计语言或算法语言。高级语言的常见类型(1)BASIC语言(2)FORTRAN语言(3)COBOL语言(4)PASCAL语言(5)C语言(6)C++语言(7)其他高级语言基于视窗类操作系统的，如VisualBasic、VisualC++、Delphi、PowerBuilder、Java等等。高级语言的特点优点：语句的功能强，源程序比较短，容易学习，使用方便，通用性较强，便于推广和交流。缺点：编译程序比汇编程序复杂，而且编译出来的目标程序往往效率不高，目标程序的长度比有经验的程序员所编的同样功能的汇编语言程序要长—半以上，运行时间也要长一些。6.1.3高级语言的根本内容

1．高级语言的根本符号高级语言都是由所谓的根本符号组成的。根本符号可以分为单字符和多字符两种情况。单字符根本符号由单个字符组成，在高级语言中通常都有以下几种单字符根本符号：(1)字母大写英文字母A～Z，小写英文字母a～z，共52个符号。(2)数字0～9，共10个数字符号。(3)特殊字符＋(加)，－(减)，*(乘)，/(除)，∧(乘方)，＝(等号)，((左括号)，)(右括号)，＞(大于)，＜(小于)，，(逗号)，(空格)等。在高级语言中的多字符根本符号由两个或两个以上的字符组成，例如GoTo(转移)、＜＝(小于或等于)、AND(与)等等。2．高级语言的根本元素根本元素由根本符号组成，可分为数、逻辑值、名字、标号和字符串等五大类。(1)数它由0～9共10个根本数字和其他一些符号(如小数点“.〞、正负号“＋、－〞及指数符号“E〞等所构成。(2)逻辑值由真(True)和假(False)两个值表示。(3)名字由字符组成，一般约定名字的开头是字母或者下划线，其后可为字母或数字，如XYZ、A123、_C等。名字可用来定义常量、变量、函数、过程或子程序的，也被用来定义成某些东西，故也称为标识符。在高级语言中，一般还规定了组成名字的字符的长度，即字符个数。(4)标号是在高级语言中的程序语句前所加的一个名字，主要用来指示程序可能的转移方向。(5)字符串由一串字符所组成。在不同的高级语言中，字符串中的多个字符放在一对单引号或双引号中。3．根本的数据类型根本的数据类型通常包括整数数据类型、实数数据类型和字符数据类型等。变量必须先定义，然后才能使用，这是—条根本原那么。变量实质上代表了一个特定大小的内存单元空间。4．结构数据类型(1)数组类型数组是假设干个相同类型的数据的集合。(2)用户自定义的结构体类型结构体是隶属于同一个事物的多个不同类型的数据的集合，用来表示具有假设干个属性的一个事物。5．运算符与表达式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(ObjectOriented，面向对象)的程序设计把客观事物看作具有属性和行为的对象，通过抽象找出同一类对象的共同属性(静态特征)和行为(动态特征)，形成类。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:twonumbers:a,b1. if(thefirstnumberaisgreaterthanorequaltothesecondnumberb)then1.1returnaelse1.2returnbendifend6.4.2常用算法介绍1．递归算法如果一个过程直接或间接地调用它本身，那么称该过程是递归的。2．迭代算法所谓迭代是指重复执行一组指令或操作步骤，在每次执行这组指令时，都从原来的解值的根底上推出一个新的解值。新的解值比原来的解值更加接近真实的解。这个过程不断重复，直到计算得到的解与真实解的误差满足实际要求。迭代常常用于科学计算领域对某些无法直接求解的数值问题。3．穷举算法亦称枚