第5章计算机软件开发第9讲.ppt
《第5章计算机软件开发第9讲.ppt》由会员分享,可在线阅读,更多相关《第5章计算机软件开发第9讲.ppt(80页珍藏版)》请在三一文库上搜索。
1、10:38,1,第4章 计算机软件系统(回顾),4.1 软件概述 4.2 操作系统概述 4.3 操作系统的功能 4.4 常见操作系统 4.5 应用软件,10:38,2,第 5 章 计算机软件开发 (第8、9讲),讲授:黄瑞兴,10:38,3,第 5 章 计算机软件开发,5.1 算法与数据结构 5.2 程序设计的基本概念 5.3 结构化程序设计 5.4 面向对象程序设计 5.5 软件工程 5.6 数据库系统概述,10:38,4,5.1 算法与数据结构,算法与数据结构是计算机程序的两个最基本的概念。瑞士著名计算机科学家尼可莱沃思在1976年曾提出算法与数据结构二者的关系: 算法+数据结构=程序 准
2、确地说,一个程序规定了某个数据结构上的一个算法。,失算,起床,穿衣,冲凉,吃饭,上课,10:38,5,5.1.1 算法的基本概念,“算法(algorithms)”是什么? 韦氏新世界词典将“算法”定义为:解决某种问题的任何专门的方法。 如公元前300年欧几里得在其著作几何原本中关于求两个数的最大公约数的辗转相除法就是著名的欧几里德算法。,10:38,6,欧几里德算法,给定两个正整数m和n求它们的最大公因子(即能同时整除m 和n 的最大正整数)步骤: 以n除m并令所得余数为r,r必小于n; 若r=0算法结束,输出结果n ,否则继续步骤3; 将n置换为m,r置换为n并返回步骤1。 欧几里德算法既表
3、述了一个数的求解过程,同时又表述了一个判定过程。,10:38,7,汉诺塔问题,每次只能移动一个盘子 只能在三根柱子上移动,不能放在其他地方 移动时必须始终保持大盘在下,小盘在上 当这64个盘子全部移到第三根柱子上,世界末日就要到了。 汉诺塔问题只能用递归方法而不能用其他方法来求解。所谓递归就是将一个较大的问题归结为一个或多个比原问题简单,且在结构上与原问题相同的子问题的求解方法。,10:38,8,5.1.1 算法的基本概念,著名计算机科学家克努特把算法的性质归纳为 有穷性:算法必须在执行有限步之后结束。即必须在有限时间内完成。 确定性:算法中的每个步骤都必须有明确的定义,不允许存在多义性和模棱
4、两可。 能行性:算法中描述的每步操作都应是可执行的。例如,当B0时A/B 就无法执行,不符合能行性的要求。 输入:一个算法必须有0个(自动生成初始数据)或多个输入。 输出:一个算法必须产生一个或多个输出,10:38,9,自然语言是人们日常所用的语言,如英语、汉语等 优点:自然语言所描述的算法通俗易懂、灵活自由。 缺点:歧义性,容易导致算法执行的不确定性;串行性,一个算法中循环和分支较多时就很难清晰地表示出来;不便转换成用计算机程序设计语言表示。,5.1.2 算法的表示-自然语言,10:38,10,流程图是采用一些的图框符号来描述算法的逻辑结构,每个图框符号表示不同性质的操作。ANSI在上世纪6
5、0年代颁布流程图的标准,规定用来表示程序中各种操作的流程图符号。,5.1.2 算法的表示-流程图,起止框,输入/ 输出框,判断框,处理框,10:38,11,5.1.2 算法的表示,例3.2 求5! 步骤1: 令p1 步骤2: 令i2 步骤3: 使pXi,成绩依然存入p中,可表示为ppxi 步骤4: 使i的值加1,可表示为ii1 步骤5: 如果i5,则返回步骤3的位置,从步骤3开始再次执行本算法。 如果i5,则算法结束。,流程图,开始,i5,p 1,i2,p p x i,i i1,结束,F,T,10:38,12,伪代码是一种非正式的语言,它是用介于自然语言和计算机语言之间的文字和符号来描述算法
6、比真正的程序代码更简明,更贴近自然语言 书写方便、格式紧凑、易于理解,便于转化为计算机语言算法(即程序),5.1.2 算法的表示伪代码,10:38,13,5.1.2 算法的表示,用伪代码表示例3.2 求5!的算法 Begin 置 p的初值为1 置 i 的初值为2 while i 5 p p x i i i + 1 endwhile 打印p的值 End,10:38,14,5.1.3 数据结构的基本概念,数据:是描述客观事物的数字、字符及所有能输入到计算机中并被计算机程序处理的符号的集合。 数据元素:组成数据的基本单位称为数据元素。通常将数据元素作为一个整体进行处理。数据元素由若干个数据项组成,称
7、数据元素为记录。 数据项是数据的不可分割的最小单位。最简单的数据元素仅含有一个数据项。,10:38,15,5.1.3 数据结构的基本概念,数据结构:是指数据之间的相互关系,即数据的组织形式。 数据结构的研究内容: 程序设计中计算机所操作的对象及相互间的关系和运算,即数据的逻辑结构、存储结构以及数据结构的运算。 数据的逻辑结构是指数据元素之间的逻辑关系。逻辑结构有:线性结构、树形结构和图状结构(或称网状结构)。,10:38,16,5.1.3 数据结构的基本概念,数据的存储结构是指数据在存储器中的存储方式。 顺序存储结构借助元素在存储器中的相对位置来表示数据元素的逻辑关系 链式存储结构借助指针来表
8、示数据元素之间的逻辑关系,通常在数据元素上增加一个或多个指针类型的属性来实现这种表示方式。,10:38,17,数据结构的基本运算(操作), 建立数据结构 撤消数据结构 插入数据元素。在一个给定的数据结构中,在指定位置上增添一个新的元素。 删除数据元素。对一个给定的数据结构,删除某个指定节点。 更新数据元素。在一个给定的数据结构中,改变某个元素的值,它等于插入和删除两个操作的组合。,10:38,18,数据结构的基本运算(操作), 查找数据元素。在一个给定的数据结构中,找出满足指定条件的元素。 排序。对给定的数据结构中的所有的元素按照一定的条件将它们重新排列顺序 遍历。在一个给定的数据结构中,从第
9、一个结点开始,依次访问各个结点。每个结点只能被访问一次。 判定某个数据结构是否为空或是否已达到最大允许的容量。 统计数据元素的个数。,10:38,19,5.1.3 数据结构的基本概念,学习数据结构的目的,可简化算法,节省空间,提高效率,程序设计中选择适当的数据结构,10:38,20,5.1.4 线性表,定义:线性表的逻辑结构是n个数据元素的有限序列:(a 1 , a 2 , a 3 , , a n ) 逻辑结构特征:数据元素之间呈线性关系 第1个:无前驱,有1个后继; 最后一个:有1个前驱,无后继; 其它:有1个前驱,有1个后继。 存储结构,一类是顺序 (静态存储结构),另一类是链式 (动态存
10、储结构),除书上所列举的26个英文字母、0-9数字字符组成线性表。 还能举出其他的线性表吗?,10:38,21,5.1.4 线性表,顺序存储结构线性表的插入、删除过程,15,18,22,25,26,29,11,12,10:38,22,5.1.4 线性表,顺序存储结构线性表的插入、删除过程,15,18,22,25,26,29,11,12,20,10:38,23,5.1.4 线性表,顺序存储结构线性表的插入、删除过程,11,10:38,24,5.1.4 线性表,链式存储线性表的插入、删除,插入c,删除d,10:38,25,5.1.5 栈与队列,栈是限定仅在表尾进行插入和删除操作的线性表。因此,对栈
11、来说,表尾端有其特殊的含义,称为栈顶,相应的表头端称为栈底。不含元素的空表称为空栈 栈又称后进先出(Last In First Out)的线性表,简称LIFO。,10:38,26,5.1.5 栈与队列,栈的示意图,栈底,栈顶,进栈,出栈,a1,a2,an-1,an,10:38,27,5.1.5 栈与队列,栈顶指针和数据元素间的关系,A,B,C,D,E,10:38,28,5.1.5 栈与队列,栈的链式存储结构链栈示意图,栈顶指针,栈顶,栈底,10:38,29,5.1.5 栈与队列,队列是一种先进先出(First In First Out)的线性表,简称为FIFO。 队列只允许在表的一端进行插入操
12、作,而在表的另一端进行删除操作。 允许插入元素的表端称为队尾,允许删除元素的表端称为队头。 类似于日常生活中的排队,删除元素从队头进行、插入元素从队尾进行,最早进入队列的元素最早离开。,10:38,30,5.1.5 栈与队列,队列示意图,a1,a2,an,队头,队尾,入队列,出队列,10:38,31,5.1.6 树与图,树:非线性结构(有树和二叉树)。非空树有且仅有一个根结点。结点拥有子结点的个数称结点的度。,A,B,F,L,K,E,D,G,H,I,J,M,C,层次,1,2,3,4,ABC的度是多少?,10:38,32,5.1.6 树与图,图:数据元素之间的关系可以是任意的,1,3,2,1,4
13、,5,2,6,有向图,无向图,4,10:38,33,5.1.7 算法的设计,算法的设计目标 正确性:能无误地处理合法输入数据,得到满足要求的结果。 可读性:便于人们阅读和交流。 健壮性:对非法输入的数据能作出适当的反应和处理。 效率与存储量:衡量算法的执行时间及所需的最大存储空间。,10:38,34,5.1.7 算法的设计,算法设计的基本策略思想 分割求解法:把一个大问题划分为原问题的较小子问题,先求出各子问题的解答,然后把各子问题的解答合并成整个问题的解。 动态规划法:对所有的子问题都进行解答,每个子问题的解决依赖于一系列子问题的结果。如何找出后面的子问题,要依赖于前面一系列子问题的递推关系
14、式,这就是动态规划策略的核心。,10:38,35,5.1.7 算法的设计,算法设计的基本策略思想 子目标法(倒推法):从某个已知的特定解出发,反过来求这个解与已知条件之间存在的关系,以得到一般解的方法 图的搜索法:把问题的求解过程用图或树这种结构来描述。 回溯法:先试一试某一操作,如果以后发现这个操作不适合,则允许退回去,另选一个操作来进行。本质是一种搜索算法。,10:38,36,习题,(p69) 1. 什么是算法,算法应具备哪些特性,为什么? (p70) 3. 几种常用的算法表示方法是什么,各有什么特点? 10. 试比较线性表、栈和队列三种数据结构。 14. 好的算法应满足哪些主要的设计目标
15、?,10:38,37,5.2 程序设计的基本概念,什么是程序设计Programming? 程序设计是给出解决特定问题程序的过程,是指设计、编制、调试程序的方法和过程。是软件构造活动中的重要组成部分。程序设计往往以某种程序设计语言为工具,给出这种语言下的程序。 程序设计过程应当包括分析、设计、编码、测试、排错等不同阶段。专业的程序设计人员常被称为程序员。,10:38,38,5.2 程序设计的基本概念,5.2.1 程序设计语言的分类 机器语言(1GL) 优点:可以被计算机直接理解和执行,执行速度快,且占用内存少。 缺点:通用性差、程序可读性很差、不易于调试和维护。,10:38,39,5.2.1 程
16、序设计语言的分类,汇编语言(2GL) 用助记符表示机器指令操作码和地址码。助记符是一些有意义的英文单词的缩写和符号。如用ADD表示加法addition、用MOV表示数据的传送move等 优点:可用汇编语言写出语句少、质量高、执行速度快的程序 缺点:汇编语言仍是一种面向机器的语言,通用性差。,10:38,40,5.2.1 程序设计语言的分类,高级语言(3GL) 按照一定的“语法规则”构建程序。用英语单词表示的关键字和数学符号组成。简化开发应用程序的过程。高级语言是面向算法过程的语言。即不但要告诉计算机“做什么”,还要告诉计算机“怎么做” 优点:程序表达直观,可读性好,与具体机器无关,便于移植,通
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 计算机软件 开发
链接地址:https://www.31doc.com/p-2987444.html