第5章计算机软件开发〔第8、9讲〕.pptVIP

第4章 计算机软件系统(回顾) 4.1 软件概述 4.2 操作系统概述 4.3 操作系统的功能 4.4 常见操作系统 4.5 应用软件 第 5 章 计算机软件开发 (第8、9讲) 讲授：黄瑞兴 第 5 章 计算机软件开发 5.1 算法与数据结构 5.2 程序设计的基本概念 5.3 结构化程序设计 5.4 面向对象程序设计 5.5 软件工程 5.6 数据库系统概述 5.1 算法与数据结构 算法与数据结构是计算机程序的两个最基本的概念。瑞士著名计算机科学家尼可莱沃思在1976年曾提出算法与数据结构二者的关系： 算法+数据结构=程序 准确地说，一个程序规定了某个数据结构上的一个算法。 5.1.1 算法的基本概念 “算法(algorithms)”是什么？ 韦氏新世界词典将“算法”定义为：解决某种问题的任何专门的方法。 如公元前300年欧几里得在其著作《几何原本》中关于求两个数的最大公约数的辗转相除法就是著名的欧几里德算法。 欧几里德算法 给定两个正整数m和n求它们的最大公因子(即能同时整除m 和n 的最大正整数)步骤： 以n除m并令所得余数为r，r必小于n； 若r=0算法结束，输出结果n ，否则继续步骤3； 将n置换为m，r置换为n并返回步骤1。 欧几里德算法既表述了一个数的求解过程，同时又表述了一个判定过程。 汉诺塔问题 每次只能移动一个盘子 只能在三根柱子上移动，不能放在其他地方 移动时必须始终保持大盘在下，小盘在上 当这64个盘子全部移到第三根柱子上，世界末日就要到了。 汉诺塔问题只能用递归方法而不能用其他方法来求解。所谓递归就是将一个较大的问题归结为一个或多个比原问题简单，且在结构上与原问题相同的子问题的求解方法。 5.1.1 算法的基本概念 著名计算机科学家克努特把算法的性质归纳为 有穷性：算法必须在执行有限步之后结束。即必须在有限时间内完成。 确定性：算法中的每个步骤都必须有明确的定义，不允许存在多义性和模棱两可。 能行性：算法中描述的每步操作都应是可执行的。例如，当B＝0时A/B 就无法执行，不符合能行性的要求。 输入：一个算法必须有0个(自动生成初始数据)或多个输入。 输出：一个算法必须产生一个或多个输出 5.1.2 算法的表示-自然语言 自然语言是人们日常所用的语言，如英语、汉语等 优点：自然语言所描述的算法通俗易懂、灵活自由。 缺点：①歧义性，容易导致算法执行的不确定性；②串行性，一个算法中循环和分支较多时就很难清晰地表示出来；③不便转换成用计算机程序设计语言表示。 5.1.2 算法的表示-流程图 流程图是采用一些的图框符号来描述算法的逻辑结构，每个图框符号表示不同性质的操作。ANSI在上世纪60年代颁布流程图的标准，规定用来表示程序中各种操作的流程图符号。 5.1.2 算法的表示 例3.2 求5! 步骤1: 令p＝1 步骤2: 令i＝2 步骤3: 使pXi，成绩依然存入p中，可表示为p←pxi 步骤4: 使i的值加1，可表示为i←i＋1 步骤5: 如果i≤5，则返回步骤3的位置，从步骤3开始再次执行本算法。 如果i5，则算法结束。 流程图 5.1.2 算法的表示－伪代码 伪代码是一种非正式的语言，它是用介于自然语言和计算机语言之间的文字和符号来描述算法 比真正的程序代码更简明，更贴近自然语言 书写方便、格式紧凑、易于理解，便于转化为计算机语言算法（即程序） 5.1.2 算法的表示 用伪代码表示例3.2 求5!的算法 Begin 置 p的初值为1 置 i 的初值为2 while i ≤5 p ← p x i i ← i + 1 endwhile 打印p的值 End 5.1.3 数据结构的基本概念 数据：是描述客观事物的数字、字符及所有能输入到计算机中并被计算机程序处理的符号的集合。 数据元素：组成数据的基本单位称为数据元素。通常将数据元素作为一个整体进行处理。数据元素由若干个数据项组成，称数据元素为记录。 数据项是数据的不可分割的最小单位。最简单的数据元素仅含有一个数据项。 5.1.3 数据结构的基本概念 数据结构：是指数据之间的相互关系，即数据的组织形式。 数据结构的研究内容： 程序设计中计算机所操作的对象及相互间的关系和运算，即数据的逻辑结构、存储结构以及数据结构的运算。 数据的逻辑结构是指数据元素之间的逻辑关系。逻辑结构有：线性结构、树形结构和图状结构（或称网状结构）。 5.1.3 数据结构的基本概念 数据的存储结构是指数据在存储器中的存储方式。 顺序存储结构借助元素在存储器中的相对位置来表示数据元素的逻辑关系 链式存储结构借助指针来表示数据元素之间的逻辑关系，通常在数据元素上增加一个或多个指针类型的属性来实现这种表示方式。 数据