第五章 计算机软件技术基础

教学进度计算机科学与工程系第五章计算机软件技术基础硬件是计算机系统的基础，但没有软件的计算机是无法工作的。计算机能广泛地应用于各个领域完全是因为有了丰富的计算机软件。本章将学习计算机软件和计算机软件开发的相关知识，如什么是软件，程序设计语言的分类及构成、数据结构与算法、软件开发过程等。教学进度计算机科学与工程系5.1计算机软件系统5.1.1软件的概念与特点软件是由程序、数据及其相关文档三部分组成。①程序：按照事先设计的功能和性能要求执行的计算机指令序列。②数据：使程序能够正常操纵信息的数据结构。③文档：与程序开发、维护和使用有关的资料。教学进度计算机科学与工程系5.1计算机软件系统5.1.2软件的分类软件可以按功能、工作方式、服务对象进行划分，其中按软件功能可划分为：②支撑软件：又称为软件开发环境。是介于系统软件和应用软件之间的中间层软件，是支撑各种软件的开发与维护的软件。③应用软件：针对特定领域开发，为特定目的服务的软件。①系统软件：能与计算机硬件紧密配合，使计算机系统的各个部件、相关的软件和数据协调、高效工作。教学进度计算机科学与工程系5.1计算机软件系统计算机软件系统中所包括的各种软件之间的关系不是并列的，而是有一定的层次关系。5.1.3计算机软件的层次结构系统软件支撑软件应用软件教学进度计算机科学与工程系5.2程序设计语言简单讲，程序设计就是用计算机语言编写程序。程序=算法+数据结构编写计算机程序时使用的语言称为程序设计语言(ProgrammingLanguage)，程序设计语言分为机器语言、汇编语言和高级语言三种。对数据操作的步骤如何表示、组织和存储数据教学进度计算机科学与工程系5.2程序设计语言5.2.1机器语言机器语言是唯一能被计算机直接理解和执行的程序设计语言，属低级语言。机器语言的一条语句就是一条指令，机器指令的格式如下：操作码操作数例如：计算256+16结果的机器代码如下(以十六进制表示)：B80001；把256放入累加器AX051000；把16与AX中值相加，结果存入AX10111000000000010000010100001000教学进度计算机科学与工程系5.2程序设计语言5.2.2汇编语言为了解决机器语言难记忆、可读性差的缺点，人们把机器指令中的操作码和操作数用英文助记符来表示，这种助记符语言称为汇编语言，也属于低级语言。MOVAX，256；把256放入累加器AXADDAX，16；把16与AX中值相加，结果存入AX汇编语言编写的程序属于符号程序，计算机不能直接识别和执行，必须翻译成计算机能识别的机器指令后才能在计算机上执行，其翻译过程如下：教学进度计算机科学与工程系5.2程序设计语言5.2.3高级语言高级语言是一类程序设计语言的统称，它采用接近人类自然语言的表示方法，并遵循一定的语法规则来编写程序。实现求整数的绝对值的程序段：intintVar,result;scanf(“%d”,&intVar);if(intVar=0)result=intVar;elseresult=-1*intVar;printf(“%d的绝对值是：%d”,intVar,result);教学进度计算机科学与工程系5.2程序设计语言高级语言程序的翻译和执行过程如下：高级语言编写的程序也属于符号程序，不能直接在计算机上执行，必须通过程序的翻译才能执行，其翻译成指令代码的方法主要有编译和解释两种。教学进度计算机科学与工程系5.2程序设计语言教学进度计算机科学与工程系5.2程序设计语言5.2.4程序设计语言的构成程序设计语言的构成主要包括以下几个方面：(1)数据类型基本数据类型：是由程序设计语言内置的，其特点是不能再分解为其它的类型。在主流的程序设计语言中一般包括：整数类型、实数类型、字符类型、布尔类型等。构造数据类型：是由基本数据类型按照某种方式组合构成的。常见的构造数据类型有：数组类型、记录类型(结构体)等等。(2)运算符和表达式在程序设计中使用表达式可完成各种各样的运算。表达式通常包括：常量、变量、运算符和函数调用等。教学进度计算机科学与工程系5.2程序设计语言(3)语句程序是对计算机要执行的操作的描述，高级语言源程序的基本组成单位就是语句。语句按功能可以分为两类：①用于描述操作运算的语句，如赋值语句；②用于控制操作运算流程的语句，如分支控制语句。(4)控制结构①顺序结构，按照语句出现的先后顺序依次执行。②分支结构，根据给定条件判断，决定程序执行的顺序。③循环结构，循环(重复)是计算机解题的一个重要特征。教学进度计算机科学与工程系5.2程序设计语言(5)输入/输出高级程序设计语言中通常以函数或语句的形式提供输入输出操作。现代高级程序设计语言通常都提供通过窗口、文本框、按钮、组合框、图表等图形组件进行输入输出。(6)子程序子程序就是将需要重复使用的程序段或分解的子问题编写成一个独立的子程序，当程序中需要使用子程序时，再对其进行调用。子程序有两种：函数(Function)和过程(Procedure)，它们的主要区别是函数有返回值，而过程不能有返回值。教学进度计算机科学与工程系5.3数据结构5.3.1什么是数据数据是对客观事物的描述，对计算机来说，数字、字符、图形、色彩、声音等都是数据。数据元素是组成数据的基本单位。一个数据元素可以是一个单个数据也可以由若干个数据项组成，数据项是数据不可分割的最小单位。例：公司员工数据的存储(一个员工信息可以构造一个一维数组的数据结构)姓名性别出生日期职位工资张军男1975.5.6总经理2080.00李芳女1980.12.12项目经理1800.00王明男1979.4.19程序员1500.00刘杰男1974.6.23系统分析员1750.00数据项数据元素教学进度计算机科学与工程系5.3数据结构5.3.2数据结构研究的内容数据结构指的是数据间的相互关系。数据结构研究的内容包括:数据的逻辑结构、物理结构和数据结构运算。(1)数据的逻辑结构数据元素之间的逻辑上的相互关系称为数据的逻辑结构，它描述数据的组织形式。元素之间是一对一关系例如:公司员工数据表中每个成员关系元素之间是多对多关系例如:华农与周边地区的位置关系元素之间是一对多关系例如:一对夫妇和他们的全部子孙元素之间是松散关系例如:自然数的全体教学进度计算机科学与工程系5.3数据结构(2)数据的物理结构数据在计算机存储器中的存储方式，称为数据的物理结构或存储结构。它包括：①顺序存储方式，把逻辑上相邻的数据元素存储在物理上相邻的存储单元中。②链式存储方式，每个结点分为数据域和指针域两部分，数据域存储数据元素，指针域存储与该结点具有逻辑关系的结点的地址。③索引存储方式，数据元素存放在一个不连续存储区域里。再建一个附加的索引表，索引表中的第i项表示第i个元素的存储地址。④散列存储方式，数据元素均匀地分布在连续的存储区域里，用散列函数计算各结点的存储地址。教学进度计算机科学与工程系5.3数据结构例如:线性表是一种逻辑结构,若采用顺序存储方式，可称其为顺序表；若采用链式存储方法，可称其为链表；若采用散列存储方法，可称其为散列表。右图为某学生各科成绩表分别采用顺序和链式存储的情形。前者存储在一片连续空间，后者则存储在非连续空间。教学进度计算机科学与工程系5.3数据结构(3)数据结构的运算数据结构的运算是定义在数据逻辑结构上的操作，如插入、删除、查找、排序等。比如一张表格，可能需要进行查找、增加、修改、删除记录等，进行这样的操作已不是加减乘除这样一些算术运算，在数据结构中，运算常常涉及算法的问题。教学进度计算机科学与工程系5.3数据结构5.3.3常见数据结构介绍(了解)(1)数组数组属于线性数据结构，是在计算机内存中使用一组连续的存储单元保存数据类型相同的一组数据，这些数据拥有相同的变量名，称为数组名。教学进度计算机科学与工程系5.3数据结构(2)链表链表(LinkedList)是采用链式存储的线性表。线性链表的结点由数据域和指针域两个部分组成，数据域存储数据元素，指针域存储一个指向直接后继结点的指针。教学进度计算机科学与工程系5.3数据结构(3)二叉树二叉树是一种常用的非线性数据结构，其定义为：二叉树是一个结点的集合，该集合或者为空，或者满足下面两个条件：①有且仅有一个称为根的结点。②其它结点分为两个互不相交的集合T1、T2。T1和T2均为二叉树，并且在T1和T2之间存在顺序关系(T1在T2之前)，分别称为根的左子树和右子树。二叉树的5种基本形态教学进度计算机科学与工程系5.3数据结构二叉树的存储结构教学进度计算机科学与工程系5.3数据结构遍历二叉树遍历二叉树是非常重要的一种运算。“遍历”的含义是对结构中的每个数据都访问一次且仅访问一次。可以有三种访问路径：①前序遍历:访问根结点;前序遍历左子树;前序遍历右子树②中序遍历:中序遍历左子树;访问根结点;中序遍历右子树③后序遍历:后序遍历左子树;后序遍历右子树;访问根结点①前序遍历：ABDEFGC②中序遍历：DBFEGAC③后序遍历：DFGEBCA教学进度计算机科学与工程系5.4算法5.4.1算法的基本概念算法是指为解决给定问题而需实施的有穷操作步骤的描述。5.4.2算法的描述方法(1)用自然语言描述算法(2)用流程图描述算法(3)使用伪代码描述算法(4)用程序设计语言描述算法算法的描述方法有以下四种：教学进度计算机科学与工程系5.4算法5.4.3查找算法(了解)查找(Searching)也称检索，设表F中有n个结点，Ki是记录Ri的关键字，现给定关键字K，在F中寻找关键字与K相同的结点R的过程，叫做查找。(1)顺序查找顺序查找是线性表的最简单的查找算法。它是用给定的值与表中的每个结点的关键字逐个进行比较运算，若找到相等的关键字则查找成功，否则查找失败。顺序查找算法的优点是适用范围广，对线性表中结点逻辑次序无关，即不要求按关键字排序。对线性表的物理存储结构也没有要求，顺序存储与链式存储均可。教学进度计算机科学与工程系5.4算法(2)折半查找折半查找的基本思想是：先取表的中间位置的结点关键字与所给定的关键字进行比较，如果相等，则查找成功。如果给定值比该结点的关键字大，则所找结点在表的后半部分；否则所找结点在表的前半部分，然后再把选定的部分表的中间结点的关键字与给定关键字进行比较。如此反复进行，直到查找成功或者查找失败为止。教学进度计算机科学与工程系5.4算法例:教学进度计算机科学与工程系5.4算法5.4.4排序算法(了解)排序(Sort)是数据处理中的一种重要运算，它的功能是将一组数据元素(或记录)从任意序列排列成一个按关键字排序的序列。按照排序过程中涉及的存储器的不同将排序分为内部排序和外部排序两类，其中内部排序是指整个排序过程都在内存中进行的排序。教学进度计算机科学与工程系5.4算法(1)直接插入排序算法的基本思想如下：①开始时，把第一个记录看成是已经排好序的子序列，这时子序列中只有一个记录；②从第二个记录起到最后一个记录，依次将每个记录与前面子序列的记录按关键字比较，确定记录插入的位置；③将记录插入到子序列中，子序列记录个数加1，直至子序列长度与待排序列长度相等时结束。教学进度计算机科学与工程系5.4算法(1)直接插入排序教学进度计算机科学与工程系5.4算法5.4.4排序算法(了解)(2)冒泡排序冒泡排序的算法思想是：①将第n个记录的关键字与将第n-1个记录的关键字进行比较，若为逆序则将两个记录进行位置的交换，否则保持原来顺序；②将第n-1个记录的关键字与将第n-2个记录的关键字进行比较；③重复上述排序过程，直到全部关键字均比较一遍；④上面三步的比较交换过程称为第一趟排序，其结果是使关键字最小的记录被交换到了第1个记录的位置，完成一趟排序；⑤第二趟排序从第n个记录到第2个记录进行同样的操作，结果是使关键字次小的记录被交换到了第2个记录的位置；依次类推，第i趟排序是从第n个记录到第i个记录依次比较交换。教学进度计算机科学与工程系5.4算法(2)冒泡排序教学进度计算机科学与工程系5.5软件工程简介5.5