《《计算机导论》-柳青-电子教案 第8章 计算机软件》由会员分享，可在线阅读，更多相关《《计算机导论》-柳青-电子教案 第8章 计算机软件（38页珍藏版）》请在金锄头文库上搜索。
1、8.1计算机软件的概念 8.2算法与数据结构 8.3程序设计,第8章 计算机软件,8.1计算机软件的概念,任务1 初步认识计算机软件,任务描述 本任务学习软件、程序、文档资料等概念。 相关知识与技能,计算机系统主要由软件和硬件两大部分组成。硬件是计算机系统的机器部分，即中央处理机、存储器及各种外围设备的总称。软件则是为使计算机高效地工作所配置的各种程序及相关的文档资料的总称。程序是经过组织的计算机指令序列，指令是组成计算机程序的基本单位。文档资料包括：软件开发过程中的需求分析、方案设计、编程方法等的文档及使用说明书、用户手册、维护手册等。,8.2算法与数据结构,任务2 算法及其描述 任务描述
2、本任务通过案例学习算法的概念及算法的描述。 案例8-1 求计算1+2+3+4+5的算法。 相关知识与技能 做任何事情都要有一个步骤，广义地讲，为解决一个问题而采取的方法和步骤，就称为“算法”。 算法有两大类别： 数值计算：求方程的根、求函数的定积分等。 非数值计算：查找、排序、图书检索、人事管理、文字处理等。 算法的设计师在设计一个算法后，不能只是自己明白，应该准确清楚地将自己设计的解题步骤记录下来，或提供交流，或编写程序供计算机执行。,步骤1：先计算1+2，得到3 步骤2：将步骤1得到的结果加上3，得到6 步骤3：将步骤2得到的结果加上4，得到10 步骤4：将步骤3得到的结果加上5，得到15
3、，计算结果为15,按照同样的思路可写出计算1+2+.100的步骤，可知是非常繁琐的。,方法与步骤,知识拓展 瑞士著名计算机科学家尼克莱沃思（Niklaus Wirth）早在1976年提出了这样一个公式： 算法数据结构程序 1974年，图灵奖的获得者、著名计算机科学家、算法大师克努特（Donald E。 Knuth）说：“计算机科学是算法的学习”。 可见，算法是计算机科学中非常重要的概念，是计算机学科的核心内容，在程序编制、软件开发，乃至整个计算机科学中都占有重要地位。,所谓算法（Algorithm），是对特定问题求解步骤的一种描述，是指令的有限序列。描述算法需要一种语言，可以是自然语言、数学语
4、言或者是计算机语言。 一个算法一般具有下列5个重要特性： 输入：一个算法应该有一个或多个输入。 有穷性：一个算法必须在执行有穷步骤之后正常结束，而不能形成无限循环。 确定性：算法中的每一条指令都必须有确切的含义，不能有二义性。 可行性：算法中的每一条指令都必须是切实可行的，即原则上可以通过已经实现的基本运算执行有限次来实现。 输出：一个算法应该有0个或多个输出，这些输出是与输入有某种特定关系的量。,任务3 用程序设计语言描述算法,任务描述 本任务通过案例进一步学习算法的概念，理解用程序设计语言（C语言）进行算法描述的方法。,案例8-2 用程序设计语言（C语言）描述计算1+2+100的算法。 相
5、关知识与技能 求解1+2+100的过程如图8-1所示，可得出以下规律：,1+2=3,3+3=6,6+4=10,10+5=15,.,4851+99=4950,4950+100=5050,重复地进行相加运算 本次的和作为下一次相加运算的被加数 加数有规律地变化着,规律,图8-1 1+2+100 运算过程,用C语言对算法描述如下： main() int x, y; x = 1; y=2; while(y=100) x = x + y; y=y+1; printf(“%d”, x); ,方法与步骤,任务4 用伪代码描述算法 任务描述 本任务通过案例进一步学习算法的概念，理解用伪代码进行算法描述的方法。
6、 案例8-3 用伪代码语言描述求1+2+100的算法。 相关知识与技能 伪代码是用文字（数字、字母）和符号来描述算法的，用伪代码描述的算法结构清晰，格式紧凑，简单易懂。它为程序员提供了以特定编程语言编写指令的模板。伪代码表明了程序细节，在伪代码阶段检测并修复错误是简单。在校验并接受伪代码之后，就可以把伪代码表示的指令转换成高级编程语言。,方法与步骤 用伪代码对算法描述如下： begin y 2 x 1 while(y=100) x x+y y y+1 print x end,任务5 用流程图描述算法 任务描述 本任务通过案例进一步学习算法的概念，理解用流程图进行算法描述的方法。 案例8-4 用
7、流程图描述求1+2+100的算法。 相关知识与技能,用流程图表示算法,ANSI规定的一些常用的流程图符号,1+2=3,3+3=6,6+4=10,10+5=15,.,4851+99=4950,4950+100=5050,0+1=1,令s表示被加数（初始值为0），令I表示加数（初始值为1） 进行100次加法后结束，或者当加数大于100时结束 S中存放计算结果,重复地进行相加运算 本次的和作为下一次相加运算的被加数 加数有规律地变化着,计算1+2+.+100,下面的算法中S表示被加数，也表示累加和，I表示加数 步骤1：S 0; I 1 步骤2：若I小于等于100，则转向步骤3；否则，转向步骤6； 步
8、骤3： S S + I; 步骤4： I I + 1; 步骤5：转向步骤2； 步骤6：S的值就是计算结果，算法结束。,推广该算法，即修改算法中步骤2的100为n，可得到计算1+2+.+n的算法。,计算1+2+.+100的算法,方法与步骤 用流程图对算法描述如图8-2所示。,图8-2 求1+2+100算法的流程图,算法思想：例如，计算1+2+.+100时先计算1100, 2+99, ., 49+52, 50+51, 然后用10150即可得到运算结果。类推，要计算1+2+.+n，只要知道有多少个n+1，就可以得到计算结果。,步骤1：S n+1 步骤2：若n是偶数，则 S (S n) 2; 否则， S
9、 S ( n-1) 2 + (n + 1) 2 步骤3：S的值就是计算结果，算法结束。,同一个问题可用不同的方法解决，即用不同算法解决同一个问题。 因此，就存在一个算法的比较(分析)和选择问题，比较的依据是算法的效率。,计算1+2+.+n的另一种算法,任务6 初步认识数据结构 任务描述 本任务了解数据结构的基本概念和常用的几种数据结构，如线性表、数组、树和二叉树以及图等。 相关知识与技能,数据结构（Data Structure）是计算机专业的一门重要专业基础课，主要研究三部分内容：数据的逻辑结构、数据的存储结构以及对各种结构进行的运算。,1. 顺序存储结构 在程序设计中，由若干个数据元素组成的
10、线性结构称为线性表。线性表是最简单和最常用的数据结构。 例如，考虑一副扑克牌中相同花色的13张红桃，为了要在程序中引用每一张红桃，可以建立13个变量Card1,Card2,Card13。每一张牌有确定的值，如“红桃2”、“红桃9”等。,图 8-3 线性结构：一维数组,2. 链式存储结构,每个结点除包含一个数据域外，还包含一个指针域，用以存放下一个结点的指针，这样的链表称为单链表。图8-4是一个具有附加头结点的单链表，指针变量h中存放的是附加头结点的指针，附加头结点只用来存放第一个具有数据的结点的指针，而第一个结点的指针域存放第二个结点的指针，如此下去，最后一个结点的指针域要置空（NULL），以
11、表示它位于链表的尾部。,图 8-4 单链表的结构,图 8-6 单链表的删除操作,图 8-5 单链表的插入操作,3. 栈与队列 对于一般的线性表，可以在任何位置上插入元素，也可以删除任何位置上的元素。如果限定插入和删除都只能在线性表的一端进行，这样的线性表称为栈；如果限定插入在线性表的一端，删除在另一端，这样的线性表称为队列。 栈是一个按“后进先出”（last in first out）方式工作的数据列表。表中允许进行插入、删除操作的一端称作栈顶；另一端称作栈底。栈顶的位置是动态的，对栈顶当前位置的标记称为栈顶指针。当栈中没有数据元素时，称为空栈。栈的插入操作通常称为进栈或入栈；栈的删除操作则称
12、为退栈或出栈。,图8-7是一个栈的动态示意图，图中箭头代表当前栈顶的指针位置，用top表示。,图8-7 栈的动态示意图,队列与栈非常相似，队列按“先进先出”（first in first out）方式工作。插入元素的那一端称为队尾，删除操作的那一端称为队头。队列的插入操作通常称为进队列或入队列；队列的删除操作称为退队列或出队列。,图8-8 队列的动态示意图,4. 树和二叉树 树（tree）是数据结构中的一种非线性结构。树在我们周围随处可见。这里讨论的树结构形同大自然中的树，也有树根、树叶和树枝。不同之处是：前者树根在上，后者树根在下。,图8-9 树结构示意图,如果树结构每个结点的孩子结点个数最
13、多为2个，这种树就是二叉树，如图8-10所示。,图8-10 二叉树,图8-11 图8-9树对应的二叉树,8.3 程序设计,任务7 初步认识程序设计 任务描述 本任务学习程序及计算机程序的基本概念。 相关知识与技能,本书中所说的程序指的是计算机程序，它实际上表示的是一种处理事务的时间顺序和处理步骤。由于组成计算机程序的基本单位是指令，因此，计算机程序就是按照工作步骤事先编排好的、具有特殊功能的指令序列。 一个程序具有一个单一的、不可分的结构，它规定了某个数据结构上的一个算法。于是有以下公式： 算法+数据结构=程序,任务8 常见程序设计语言 任务描述 本任务了解一些常见的程序设计语言的特点。 相关
14、知识与技能 1. 面向机器语言,机器语言：机器语言是计算机的第一代语言。,例如，用机器语言写的某一段程序为： 0000 0110 0000 0011 0011 1110 0000 0100 0000 其中，每一条机器指令都是用二进制代码表示的。 以上由“0”、“1”组成的三条指令对Z80机器而言就是完成3加4的运算。,汇编语言 汇编语言是计算机的第二代语言。,例如，把上述用机器语言书写的三条指令用汇编语言来表示，即成为： LD B, 03 LD A, 04 ADD A, B 从英文字母的含义可知，第一条指令是把3送到寄存器B中（LD是load的缩写）。同理，第二条是把4送到寄存器A中，第三条则
15、是把B中的数加到A中去。,2. 面向过程语言,FORTRAN语言（公式翻译语言）,ALGOL 60（算法语言）,COBOL（用于事务处理的通用语言）,BASIC（初学者通用符号指令码）,PL/1（程序设计语言1）,Ada语言, PASCAL语言,C语言,3. 面向对象语言,C+程序设计语言 Visual Basic程序设计语言,4. 网络编程语言 网络编程语言是计算机的第五代语言。进入20世纪90年代，网络技术得到了飞速发展，尤其进到21世纪后，Internet得到了更为广泛的应用。 Java语言（Java language）是一种简捷的、面向对象的、用于网络环境的程序设计语言，由SUN公司（
16、汉语简称“太阳公司”）于1995年5月正式对外发布。,任务9 面向过程程序设计 任务描述 本任务通过案例学习简单的面向过程程序设计。 案例8-5 用C语言编写程序：输入一个年份，判断该年份是否是润年。 相关知识与技能,单分支选择语句格式： If(条件表达式) 语句块 语句功能：当条件为True（真）时，执行后面的语句块。 方法与步骤,两分支选择结构语句格式： If(条件表达式) 语句块1 else 语句块2,本案例可采用选择结构来实现。单分支选择结构有两种语句格式：,C语言的历史背景,C语言是AT&T贝尔实验室的Dennis Ritchie和Ken Thompson 在B语言的基础上开发出来的(1972 or 1973) UNIX操作系统是用C语言编写
