第4章软件技术基础1.ppt
《第4章软件技术基础1.ppt》由会员分享,可在线阅读,更多相关《第4章软件技术基础1.ppt(87页珍藏版)》请在三一文库上搜索。
1、第四章 软件技术基础,一.程序的概念,程序就是一系列的操作步骤,计算机程序就是由人事先规定的计算机完成某项工作的操作步骤。每一步骤的具体内容由计算机能够理解的指令来描述,这些指令告诉计算机“做什么”和“怎样做”。,二.程序设计语言的概念,编写计算机程序所使用的语言称为程序设计语言。,第一步把8转成二进制:,三 计算机语言发展过程,机器语言,汇编语言,高级语言,用机器语言完成一个加法运算,8+4,1000,再补满八位00001000,第二步把4转成二进制:,100,再补满八位00000100,第三步用指令10110000把00001000送入累加器AL中,第四步用指令10110000把00000
2、100送入累加器AL中,第五步用指令00000100把00001000与00000100相加,第六步用指令11110100终止操作,最早的计算机语言,它是用二进制代码来编写程序,其编写的程序计算机能直接识别,且速度快。,1.机器语言,10110000 00001000 10110000 00000100 00001000 00000100 00000100 11110100,8+4的机器程序为:,如果要算1+2+3+4+5+6+100?,机器语言书写困难、记忆复杂,一般很难掌握。,程序为:,8+4,MOV AL,8,MOV AL,4,HLT,用命令MOV把4送到累加器AL中,用命令ADD把8与
3、4相加,用命令MOV把8送到累加器AL中,ADD 8,4,语言汇编语言完成一个加法运算,MOV AL,8 MOV AL,4 ADD 8,4 HLT,源程序,目标程序,可执行程序,翻译,连接,计算机不能识别,2.汇编语言,由于机器语言的缺陷,人们开始用助记符编写程序,用一些符号代替机器指令所产生的语言称为汇编语言。,3. 高级语言,为了克服机器语言和汇编语言的缺陷,使普通人都能使用计算机语言来编写程序,人们开始研究一种既接近自然语言又简单易懂的语言。经过长时间的实践,产生了我们今天的高级语言。,汇编语言虽然采用了助记符来编写程序,比机器语言简单,但是仍属于低级语言,它与计算机的体系结构有关,在编
4、写程序前要花费相当多的时间和精力去熟悉机器的结构。因此工作量大、繁琐,而且程序可移植性差。,Basic、VB、 C、C+、VC、VP,用高级语言C语言完成一个加法运算,8+4,int s; s=8+4;,计算机也不能识别高级语言,必须转换成二进制,有两种方式:,解释方式和编译方式,解释方式:是解释一条执行一条,不产生目标程序。,源程序,可执行程序,解释程序,编译方式:是整个程序都转换二进制,连接成可执行文件.,源程序,目标程序,可执行程序,编译程序,连接程序,BASIC,java等为解释型语言,C,FORTRAN,PASCAL 等为编译型语言,这种语言最接近自然语言又简单易懂的语言,语言简洁、
5、紧凑、使用方便、灵活,(2)可移植性好,生成代码质量高,程序运行效率高,(3)有丰富运算符和数据结构。,C语言是一种面向过程的编程语言,具有高级语言的一切功能,又有低级语言的一些功能,因此它既可以用来编写系统软件,也可以用来编写应用软件。 c语言与其它语言相比具有如下特点:,1 C语言,四、高级语言分类,高级语言分3类:,(1)面向过程,(2)面向问题,(3)面向对象,五、常用的高级语言分类,面向对象的C+语言。它是在C语言的基础上增加了面向对象的内容。C+的学习比C语言更为困难。从目前的发展看,C+的应用更为普及。,2 C+语言,PASCAL语言是一种面向过程的良好结构化特性的高级语言,它是
6、在软件危机的70年代所创造的一种完全符合结构化原则,有着严格的语法规则的高级语言。该语言在语言教学中有着良好的声誉,但在实际使用中,利用该语言开发软件并不多。所以许多人认为PASCAL 只是一种教学语言。,3 PASCAL语言,4 FORTRAN 语言,FORTRAN是最早出现的高级语言之一。它是针对科学计算而设计的一种高级语言(早期计算机的主要任务就是进行科学计算),到目前为止,FORTRAN仍主要是用于科学计算。 C语言出现后,有人给FORTRAN语言判了死刑,但事实上,在科学计算上,尤其是在大规模科学计算上,FORTRAN仍是首选的高级语言。FORTRAN 自身也在发展,目前,FORTR
7、AN已发展到90和95版本。 微机上的FORTRAN编译器也有多种,在国内最流行的是VISUAL FORTRAN 5.0及更高的版本。此外还有其它的编译器如NDP FORTRAN等,只是在国内不大流行。,5 VISUAL BASIC,是由微软公司开发的,支持WINDOWS平台下开发的BASIC语言。它支持面向对象的开发,是目前WINDOWS平台下流行的开发工具之一。,7 其它语言,一般来说,每一种高级语言或开发工具都有它的使用范围,到目前为止,还没有一种语言能包打天下。,6 java语言,是由sum公司开发的,面向对象的网络编程语言,是目前跨平台下最流行的网络开发工具之一。,5 VISUAL
8、foxpro,支持WINDOWS平台下开发的数据库存语言。它支持面向对象的开发,是目前WINDOWS平台下流行的开发数据库工具之一。,8 程序设计的基本过程,确定解决方案,分析问题,设计算法,编写程序,调试程序,整理文档,修改程序,4.1 算法语言简介,算法是指解决某一特定问题的具体步骤的描述,是指令的有限序列。,解决刻问题的算法为:,例1. 已知圆的半径为R(R是一个可变的量),求圆的面积和周长?,第一步:输入半经给r,第二步:计算面积存入s中,即s=3.14*r2,第三步:计算周长存入l中,即l=2*3.14*r,第四步:输出计算结果s与l的值,求园面积、周长的步骤就是一个算法,例2 求1
9、+2+3+4+5n表达式的值(假设n=100),算法为:,分析:设和为s,则其通项为s=s+n,第五步:若n的值小于100,重复三、四步,第六步:输出结果,求数字累加的步骤就是一个算法,(4)输出:要求算法有一个或多个输出,1. 算法的基本牲,(5)可行性:算法描述的操作都是可以通过已经实现的基本运算,通过执行有限次来实现的。,(1)确定性:是指算法中的每一步都必须是有明确的定义,不允许有模棱两可的解释和多义性。,(2)有穷性:是指必须能在执行有限步骤之后终止。,(3)输入:要求算法有零个或多个输入,例 下列对算法特性描述正错误的是(2005年9月),A.算法中的每一步都必须是有明确的定义,不
10、允许有多义性,B.算法有一定要有输出,C.算法一定要有输入,D.算法描述的操作都是可以通过执行有限次来实现的,(4)效率与存储量需求:效率指的是算法执行的时间;存储量需求指算法执行过程中所需要的最大存储空间,即:要有较优时间效与空间效率。,2. 评价一个好的算法有以下几个标准:,(1)正确性:算法应满足具体问题的需求。,(2)可读性:算法应该以有利于阅读者对程序的理解。,(3)健状性:算法应具有容错处理。当输入非法数据时,算法应对其作出反应,而不是产年莫名其妙的输出结果。,3. 算法效率的度量,(1)时间复杂度:是指算法基本运算的次数(不是执行时间),用来衡量算法执行的时间效率。,(2)空间复
11、杂度:执行这个算法所需要的内存空间。包括程序所占的空间、输入的初始数据所占的空间、运算时所需的空间。,例1. 算法的时间复杂度是指(2005年4月考题) A)执行算法程序所需要的时间 B)算法程序的长度 C)算法执行过程中所需要的基本运算次数 D)算法程序中的指令条数,例2.算法的空间复杂度是指(2005年9月考题) A)算法程序的长度 B)算法程序中的指令条数 C)算法程序所占的存储空间 D)算法执行过程中所需要的存储空间,例1 将两个变量x=3,y=5的值交换,其算法为:(首先引入中间变量z),第一步:输入3给x,输入5给y,第二步:将x的值存入中间变量z中:x z,第三步:将y的值存入x
12、中:y x,第四步:把中间变量z的值存入y中:z y,4 算法的表示,(1) 自然语言表示:,用人们通使用的语言来表示。,(2)用流程图形来表示算法,流程图:是一种表示算法的图形工具,用来助人们设计程序。,流程图的类型,1.ANSI流程图 2.N-S流程图 3.PAD图 4.HIPO图,起止框,处理框,判断框,输入输出框,连结点,流向线,ANSI流程图简介,例2 用流程图将两个变量x=3,y=5的值交换。,算法的控制结构可分为顺序、选择、循环三种基本结构。,4.结构化程序算法的控制结构,用流程图表示为:,当型循环,直到型循环,注:任何一个结构化程序都可以由这3种基本结构来完成。已经证明:这3种
13、基本结构所构成的程序可以处理任何复杂的问题。,例 结构化程序设计的3种基本结构是(2005年4月考题) A)顺序、选择、重复 B)递归、嵌套、调用 C)过程、子过程、主程序 D)顺序、转移、调用,例3 输入两个数x,y;输出最大的数,算法为:,第二步:对x,y进行比较,第三步:输出最大的数,no,yes,P136页 例4 输入三个数x,y,z;输出最大的数,例5 求1x2x3x4x5n表达式的值(假设n=100),算法为:,分析:设和为s,则其通项为s=sxn,第五步:若n的值小于100,重复三、四步,第六步:输出结果,no,yes,计算机解题的过程实际上是实施某种算法,称计算机算法。 (1)
14、列举法 列举法是指根据提出的问题,列举所有可能的情况进行处理。 (2)归纳法 通过列举少量的特殊情况,经过分析,找出一般关系 (3)递推 从已知的初始条件出发,逐次推出所要求的各中间结果和最后结果 (4)递归 将一个复杂的问题归结为若干个较简单的问题,直到最简单问题解决 (5)减半递推技术 就是对问题分而治之。,5. 算法设计的基本方法,数据结构是一门研究非数值计算的程序设计问 题中计算机的操作对象以及它们之间的关系和 操作等等的学科。,4.4.1 数据结构定义,4.4 数据结构简介,4.4.2 基本概念和术语,数据所有能输入到计算机中去的描述客观事物的符号。 数据项有独立含义的数据最小单位,
15、也称域。 数据元素数据的基本单位,也称节点或记录,可以包括一个或几个数据项。,学生信息表,举例,以上是用线性表的形式来表示数据,数据结构是反映数据元素间关系的集合的表示,以上是通过树形结构来表示数据,如何来让计算机表示其关系?(设计算法),如何来让计算机存储这些关系的数据?(编程实现算法),如何来让计算机对其进行运算?,(1)集合数据元素间除“同属于一个集合”外,无其它关系,(1)数据的逻辑结构(数据元素之间的逻辑关系) (2)数据的存储结构(逻辑结构在计算机内部的实现) (3)对各种数据结构进行的运算(增加、删除、修改等),数据结构主要研究三个方面的问题:,根据数据元素间关系的基本特性,数据
16、的逻辑结构有四种基本结构,4.4.3 数据结构主要研究问题,如:坐在同一个电影 院里素不相识的观众,如:装在同一袋子里有大米,(2)线性结构该结构的数据元素之间存在着一个对一的关系,如线性表。,线性结构特点:在数据元素的非空有限集中 *存在唯一的一个被称作“第一个”的数据元素 *存在唯一的一个被称作“最后一个”的数据元素 *除第一个外,集合中的每个元素均只有一个前驱 *除最后一个外,集合中的每个元素均只有一个后继,例 英文字母表(A,B,C,Z)是一线性结构,叫线性表,几种常用特殊的线性表,栈:栈是限定在一端进行插入与删除的线性表。,栈顶指针top,指向实际栈顶 后的空位置,初值为0,进栈,A
17、,出栈,栈满,B,C,D,E,F,设数组维数为M top=0,栈空,此时出栈,则下溢(underflow) top=M,栈满,此时入栈,则上溢(overflow),栈空,栈的特点:先进后出,后进选出。,A)在栈中只能插入元素而不能删除元素 B)在栈中只能删除元素而不能插入元素 C)栈是特殊的线性表,只能在一端插入或删除元素 D)栈是特殊的线性表,只能在一端插入元素,而在另一端 删除元素,例1 下列关于栈的描述正确的是(2005年9月),例2: 栈底至栈顶依次存放元素A、B、C、D、E,在第五个元素E入栈前,栈中元素可以出栈,则出栈序列可能是_。 ABCED B. DBCEA C. CDABE
18、D. DCBEA,对列:是指允许在一端进行插入、而在另一端进行删除的线性表。,front,rear,队空,把a1,a2,a3,a4,a5,a6,a7,a8,a9放入队列,a1,a2,a3,a4,a5,a6,a7,a8,a9,入队,出队,队列的特点:“先进先出,后进后出”的原则,队列在两端进行操作,一端插入,一端删除,例1 栈和队列的共同点是( ) A)都是先进先出 B)都是后进先出 C)只允许在端点处插入和删除元素 D)没有共同点,例2 一个队列的入队序列是1,2,3,4,则队列的输出序列是 A)4,3,2,1 B)1,2,3,4 C)1,4,3,2 D)3,2,4,1,(3)树形结构(层次结
19、构)一个对多个,数据元素间存在着一对多或多对一的关系,每个元素若有直接前驱元素,只能有一个,但可以有多个直接后继元素。,特点: 树中至少有一个结点根 树中各子树是互不相交的集合,根,子树,一、树基本术语,结点表示树中的元素,包括数据项及若干指向其子树的分支 结点的度结点拥有的子树数 叶子度为0的结点 孩子结点子树的根称为该结点的孩子 双亲孩子结点的上层结点叫该结点的双亲 兄弟同一双亲的孩子 树的度-一棵树中最大的结点度数 结点的层次从根结点算起,根为第一层,它的孩子为第二层 树的高度树中结点的最大层次数 森林m(m0)棵互不相交的树的集合,结点A的度:3 结点B的度:2 结点M的度:0,叶子:
20、K,L,F,G,M,I,J,结点A的孩子:B,C,D 结点B的孩子:E,F,结点I的双亲:D 结点L的双亲:E,结点B,C,D为兄弟 结点K,L为兄弟,树的度:3,结点A的层次:1 结点M的层次:4,树的深度:4,结点F,G为堂兄弟 结点A是结点F,G的祖先,结点B的孩子:,结点F的双亲:,树的高度,结点K的层次,树的度,叶子:,结点A的度:,互为兄弟的结点:,2,E,I,J,K,H,D,E,C,B,C,D,E,F,H,I,J,2,4,4,下列关于树的概念错误的是( )(2004年) A一棵树中只有一个无前驱的结点 B一棵树的度为树中各个结点的度数之和 C一棵树中,每个结点的度数之和等于结点总
21、数减1 D一棵树中每个结点的度数之和与边的条数相等,一、树基本术语,结点表示树中的元素,包括数据项及若干指向其子树的分支 结点的度结点拥有的子树数 叶子度为0的结点 孩子结点子树的根称为该结点的孩子 双亲孩子结点的上层结点叫该结点的双亲 兄弟同一双亲的孩子 树的度-一棵树中最大的结点度数 结点的层次从根结点算起,根为第一层,它的孩子为第二层 树的高度树中结点的最大层次数 森林m(m0)棵互不相交的树的集合,二、 二叉树,特点:每个结点至多有二棵子树(即不存在度大于2的结点) 二叉树的子树有左、右之分,且其次序不能任意颠倒 基本形态,定义:二叉树是n(n0)个结点的有限集,它或为空树(n=0),
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 软件技术 基础
链接地址:https://www.31doc.com/p-2256643.html