第三章 数据结构及软件工程2

13.3.3数据结构（DataStructures）数据结构：研究程序设计中计算机操作对象以及它们之间关系和运算的一个专门学科。研究数据结构一般包括三个方面的内容：数据的逻辑结构数据的存储结构在数据上定义的运算的集合2数据结构的产生（1）数据是对客观事物的符号表示。在计算机科学中其含义是指所有能够输入到计算机中并被计算机程序处理的符号集合。例如：数字、字母、汉字、图形、图像、声音都称为数据。（2）数据元素是数据集合中的一个实体，是计算机程序中加工处理的基本单位。数据结构中涉及到的基本概念数据元素按其组成可分为简单型数据元素和复杂型数据元素。简单型数据元素由一个数据项组成，所谓数据项就是数据中不可再分割的最小单位；复杂型数据元素由多个数据项组成，它通常携带着一个概念的多方面信息。数据元素具有广泛的含义。一般来说，现实世界中客观存在的一切个体都可以是数据元素。例如，描述一年四季的季节名，可以作为季节的数据元素；表示数值的各个数：11，34，25，67，99，可以作为数值的数据元素；在数据处理领域中，通常把数据元素之间这种固有的关系简单地用前后件关系（或者直接前驱与直接后继关系）来描述。4数据的逻辑结构数据元素之间的逻辑关系，与数据在计算机内部如何存储无关，独立于计算机，有以下几种结构：线性结构：数据元素之间存在线性关系，即最多只有一个前导和后继元素；树形结构：数据元素之间呈层次关系，即最多有一个前导和多个后继元素；图状结构：数据元素之间的关系为多对多的关系。5集合线性树图数据的逻辑结构6数据的存储结构数据元素在计算机中的存储方式，分为：顺序存储结构链式存储结构数据域指针域索引存储结构散列存储结构7数据的存储结构数据的存储结构实质上是它的逻辑结构在计算机存储器上的实现。为全面地反映一个数据元素的逻辑结构，它在存储器中的映象应包括两方面的内容：数据元素自身值数据元素之间关系链接表是以指针方式表示的“线性表结构”学号、姓名……学号、姓名……学号、姓名……∧infolinkinfolinkinfolink第1个学生第2个学生第n个学生学生表的链接结构……8对各种数据逻辑结构有相应的各类运算，每种逻辑结构都有一个运算的集合，常用的运算有：检索、插入、删除、更新、排序等。实质上，数据的运算定义在数据逻辑结构上，而其运算的具体实现要在存储结构上进行。运算的定义直接依赖于逻辑结构，但运算的实现必依赖于存贮结构。数据的运算93.4软件工程基础1、软件工程概述2、软件工程研究内容3、软件开发模型软件生存周期软件开发模型：瀑布模型、增量模型、螺旋模型和软件重用模型4、软件开发过程101软件工程概述由于硬件技术的进步，计算机得到了广泛应用。因而出现了一些复杂的、大型的软件开发项目，虽然技术不断发展，但始终不能满足软件发展的要求，从而形成了“软件危机”。软件危机：是指在计算机软件的开发和维护过程中所遇到的一系列严重问题。几乎所有软件都不同程度地存在这些问题。111软件工程概述从微观上看，特征表现：在开发过程没有规范化和系统化、开发计划，不能按期完成、经费超支导致成本过高，甚至工程最终失败。从宏观及整个社会对软件的需求来看，实质是软件产品的供应赶不上硬件的发展和用户需求的增长。原因：开发靠手工，没有统一、公认的方法论规范指导。负责开发管理的中高级人员，对产业规律性和质量度量研究不透彻，不能及时解决实际出现的问题。12解决危机的方法：–提出结构程序设计方法–提出用工程方法开发软件–从理论上探讨程序正确性和软件可靠性问题。目前，软件开发工程化成为提高软件开发效率的唯一的方法。1软件工程概述132软件工程研究内容软件工程是计算机领域的一个较大的研究方向，其内容十分丰富，包括：理论、结构、方法、工具、环境、管理、经济、规范等软件工程软件开发技术软件工程管理软件开发方法软件开发工具软件开发环境软件开发管理软件心理学软件工程经济学143软件开发模型1、软件生存周期定义：由软件定义、软件开发和运行维护三个时期组成，每个时期又可进一步划分成若干个阶段。软件定义时期的工作：问题定义，弄清用户要计算机解决的问题是什么。可行性研究，为前一阶段提出的问题寻求一种或数种在技术上可行、且在经济上有较高效益的解决方案。15软件开发时期的五个阶段：需求分析：弄清用户对软件系统的全部需求，主要是确定目标系统必须具备哪些功能。总体设计：设计软件的结构，即确定程序由哪些模块组成以及模块间的关系。详细设计：针对单个模块的设计。编码：按照选定的语言，把模块的过程性描述翻译为源程序。测试：通过各种类型的测试使软件达到预定的要求3软件开发模型163、软件开发模型（1）瀑布模型将软件生存周期的各项活动规定为依照固定顺序连接的若干阶段工作，形如瀑布流水，最终得到软件产品。系统规划系统分析系统设计系统实施系统维护瀑布模型方法17（2）增量模型先开发一个“原型”软件，完成主要功能，征求用户意见，再逐步完善，最终获得满意的软件产品。特点：具有较大的灵活性，应用范围：适合于软件需求不明确、设计方案有一定风险的软件项目。系统定义及用户需求分析原型设计编码测试原型完善原型产品系统的设计实现18（3）螺旋模型结合瀑布模型与增量模型，并加入风险分析。模型沿螺线旋转，在笛卡尔坐标的四个象限上分别表达了四个方面的活动，即：制定计划：确定软件目标，选定实施方案，弄清项目开发的限制条件；风险分析：分析方案，考虑如何识别和消除风险；实施工程：实施软件开发客户评估：评价开发工作，提出修正建议。沿螺线自内向外每旋转一圈便开发出更为完善的一个新的软件版本。1920（4）软件重用模型特点：开发具有各种一般性功能的软件模块，将它们组成软件重用库。通常对于一个具体的软件开发会存在若干方法的组合与交叉，也可使用新的开发模型与方式。214软件开发过程在软件计划确定后，目前通常采用结构化方法的软件开发过程或面向对象方法的软件开发过程。软件测试软件计划后面向对象分析面向对象设计面向对象编程软件计划后结构化分析结构化设计结构化程序设计软件测试22特点：采用自顶向下、逐步求精的方式来进行程序设计，以模块化设计为中心，将待开发的软件系统划分为若干个相对独立的模块。模块间工作明确，相互独立。优点：一定程度上解决了软件的可靠性、可生产性和可维护性等方面的问题，部分缓解了软件危机。缺点：对大型软件的开发，在稳定性、可修改性、可维护性等方面仍然存在许多问题A、结构化程序设计23起源于面向对象程序设计语言（ObjectOrientedProgramLanguage，简称OOPL）。特点：将现实世界中的问题从组成结构上自然分解成一个个对象，用对象及对象之间的联系建立起问题域的模型。优点：对现实世界的描述更加直接并且更符合人类的思维方式。B、面向对象方法程序设计方法