第11章程序设计基础

返回习题要点重点目的11.1程序设计概述11.2软件工程11.3算法11.4数据结构11.5思考题与习题第11章程序设计基础返回习题要点重点目的通过本章的教学，使学生理解软件开发的整体流程，了解数据结构的意义。基本要求及教学目的返回习题要点重点目的教学要点本门课程的学习方法、指定本课程的课外阅读书籍及阅读成果的表现形式、考核方法，1学时；程序的思想、数据结构、算法2学时。返回习题要点重点目的重点及难点重点：软件设计的总体流程、数据结构及算法的理解。难点：编写程序，设计算法。返回习题要点重点目的11.1程序设计概述11.1.1程序设计语言的分类按照语言级别可以分为低级语言和高级语言。按照用户的要求有过程式语言和非过程式语言之分。按照应用范围，有通用语言与专用语言之分按照使用方式，有交互式语言和非交互式语言之分。按照成分性质，有顺序语言、并发语言和分布语言之分。返回习题要点重点目的11.1.2程序设计的基本过程程序设计包括分析问题、画出程序的基本轮廓和实现该程序这三个基本步骤。1．分析问题3．实现程序2．形成程序的基本轮廓返回习题要点重点目的11.2软件工程软件工程是一门研究用工程化方法构建和维护有效的、实用的和高质量的软件的学科。它涉及到程序设计语言、数据库、软件开发工具、系统平台、标准、设计模式等方面。返回习题要点重点目的11.2.1软件工程的基本概念1．软件软件是计算机系统必不可少的组成部分，是程序、数据和相关文档的集合。其中程序是软件开发人员根据用户需求开发的、用程序设计语言描述的、适合计算机执行的指令序列；数据是使程序正常操纵信息的数据结构；文档是与程序开发、维护和使用相关的各种图文资料。返回习题要点重点目的2．软件危机随着计算机应用的日益普及，软件需求量急剧增大在软件发展的初期许多程序员没有接受过正规的教育，他们边学习边开发；在组织方面，解决问题的方法就是增加更多的程序员到项目中去。结果，软件通常时难以按时交付，程序也不能像用户期望的那样工作，程序很少能适应变化的环境，而且在软件交付给用户之后又会发现很多错误。更严重的是，许多程序的个体化特征使得它们最终成为不可维护的软件，这就是“软件危机”。返回习题要点重点目的3．软件工程为了更有效地开发和维护软件，逐渐形成了一门新的工程学科，即计算机软件工程学，简称为软件工程。返回习题要点重点目的11.2.2软件开发方法软件工程中的开发方法主要有3种：面向过程的方法面向对象的方法面向数据的方法返回习题要点重点目的1．面向过程的方法面向过程的方法又称为结构化方法。它包括面向过程需求分析、面向过程设计、面向过程编程、面向过程测试、面向过程维护和面向过程管理，习惯上称为结构化分析、结构化设计、结构化编程、结构化测试和结构化维护。返回习题要点重点目的2．面向对象的方法面向对象的方法包括面向对象需求分析、面向对象设计、面向对象编程、面向对象测试、面向对象维护和面向对象管理。返回习题要点重点目的3．面向数据的方法面向数据的方法也称为面向元数据的方法。元数据是关于数据的数据，组织数据的数据。如数据库概念设计中的实体名和属性名、数据库物理设计中的表名和字段名就是元数据。而一个具体的特定的实例就不是元数据，而叫做对象或记录，是被元数据组织或统帅的数据。返回习题要点重点目的11.2.3软件生命周期1．软件生命周期软件生命周期是指软件产品从提出开始直到停止使用的全过程。概括地讲，软件生命周期是由软件定义、软件开发和软件维护3个时期组成，每个时期又进一步划分成若干个阶段。返回习题要点重点目的2．软件生命周期模型软件生命周期模型表达的是软件生命周期内各种活动如何组织，以及各个阶段应该如何衔接，它给出的是直观的图示表达。目前，提出的软件生命周期模型主要有瀑布模型、螺旋模型、原型模型、喷泉模型和职能模型等。返回习题要点重点目的11.2.4软件测试软件测试和软件质量是密不可分的。测试是手段，质量是目的，因此软件分析与测试已成为现代软件工程学研究和应用的热点。软件测试是软件质量保证的关键，是对计划、设计和编码的最终检查，是发现软件中错误和缺陷的主要手段。一般情况下，软件测试过程与整个软件开发过程基本上是平行进行的。返回习题要点重点目的1．软件测试的目的2．软件测试的原则3．软件测试的方法4．软件测试过程返回习题要点重点目的11.2.5软件维护软件维护是指在软件已经交付使用之后（即运行维护阶段），为了改正错误或满足新的需要而修改软件的过程。它是软件开发周期的最后一个阶段，处于系统投入生产性运行之后的时期。返回习题要点重点目的11.2.6软件开发工具与软件开发环境1．软件开发工具软件开发工具是一种软件，是辅助和支持其他软件研制和维护工作的工具。现代软件工程方法能得以实施，重要的保证是软件开发工具和环境的保证，使软件在效率和质量等方面得到了改善。2．软件开发环境软件开发环境（SDE）又称为集成式项目支撑环境（IPSE），是一组相关的软件工具的集合，将它们组织在一起，可以支持某种软件开发方法。返回习题要点重点目的11.3算法11.3.1算法的概念算法是对解决某一特定问题的操作步骤地具体描述，或者说算法是解决一个问题而采取的方法和步骤。如上网的过程是：打开浏览器的窗口、输入网址、在网页上操作、关闭网页，这就是“上网算法”。返回习题要点重点目的11.3.2算法的特征一个好的算法应该具有以下几个特性：1．正确性2．可读性3．准确性4．高效率和低存储量返回习题要点重点目的11.3.2算法的特征一个好的算法应该具有以下几个特性：1．正确性2．可读性3．准确性4．高效率和低存储量返回习题要点重点目的11.3.3算法的表示1．自然语言2．传统流程图3．N-S图4．伪代码5．计算机语言返回习题要点重点目的11.3.4算法设计的基本方法1．列举法2．归纳法3．递推法4．递归法5．回溯法返回习题要点重点目的11.3.5算法的复杂度算法的优劣与它的复杂度有关，而算法的复杂度是算法效率的度量，是评价算法优劣的重要依据。一个算法的复杂度的高低体现在运行该算法所需要的计算机资源的多少上面，算法所需的资源越多，其复杂度就越高；相反，算法所需的资源越低，其复杂性就越低。返回习题要点重点目的1．时间复杂度一个算法的运行时间不是固定的，而是受到了多种因素的影响，比如使用的语言不同、使用不同的编译程序、运行环境的不同等。2．空间复杂度算法的空间复杂度，主要是考虑算法所占有系统资源的情况。返回习题要点重点目的11.4数据结构数据结构主要研究的问题是：（1）数据集合中各数据元素之间所固有的逻辑关系，即数据的逻辑结构。（2）在对数据进行处理时，各数据元素在计算机中的存储关系，即数据的存储结构。（3）对各种数据结构进行的运算。返回习题要点重点目的11.4.1数据结构的概念1．数据（Data）2．数据元素（DataElement）3．数据对象（DataObject）4．数据类型（DataType）5．数据结构（DataStructure）返回习题要点重点目的11.4.2线性表数据结构分为线性结构和非线性结构。在线性结构中有且仅有一个无前驱的结点和一个无后继的结点，并且所有结点都最多只有一个前驱和一个后继。典型的线性结构有线性表、顺序表。返回习题要点重点目的1．线性表的定义2．线性表的顺序存储表示3．线性表的运算4．线性表的链式存储表示返回习题要点重点目的11.4.3栈和队列1．栈（Stack）栈是一种特殊的线性表，这种线性表上的插入和删除运算限定在表的一端进行2．队列（Queue）队列是只允许在一端进行插入元素，而在另外一端进行删除元素的线性表。返回习题要点重点目的11.4.4树和二叉树树型结构是一类重要的非线性数据结构。其中以树和二叉树最为常用，直观看来，树是以分支关系定义的层次结构。返回习题要点重点目的1．树（Tree）树是n（n≥0）个结点组成的有限集。在任意一棵非空树中：（1）有且仅有一个特定的结点称为根结点；（2）当n1时，其余结点可分为m（m0）个互不相交的有限集T1，T2，…，Tm，其中每一个集合本身又是一棵树，并且称为根的子树（SubTree）。返回习题要点重点目的2．二叉树（BinaryTree）二叉树是另一种树型结构，它的特点是每个结点至多只有两棵子树（即二叉树中不存在度大于2的结点），并且，二叉树的子树有左右之分，其次序不能任意颠倒。返回习题要点重点目的11.4.5图图（Graph）：由两个集合V(G)和E(G)所组成，记做G=(V,E)，其中V(G)是图中顶点的非空有限集合，E(G)是边的有限集合。返回习题要点重点目的11.4.6排序与查找方法1．查找查找是根据给定的某个值，在查找表中确定一个其关键字等于给定值的记录或数据元素。2．排序排序是计算机进行数据处理的一个重要操作，它的功能是将一个无序的数据序列排列成一个递增或递减的有序序列。返回习题要点重点目的习题及思考题1.栈和队列有何异同？2.什么是完全二叉树？3.为什么要进行软件测试？常用的软件测试方法有哪些？