数据结构及软件工程简介.doc

数据结构和软件工程简介
数据结构的基本概念
§ 数据是描述客观事物并能为计算机加工处理的符号的集合。数据元素是数据的基本单位，即数据集合中的个体。有些情况下也把数据元素称为结点、记录等。一个数据元素可由一个或多个数据项组成。数据项是有独立含义的数据最小单位，有时也把数据项称为域、字段等。
§ 数据结构（Data Structure）是指数据元素的组织形式和相互关系。数据结构一般包括以下三方面的内容。
1、数据的逻辑结构
§ 数据的逻辑结构从逻辑上抽象地反映数据元素间的结构关系，它与数据在计算机中的存储表示方式无关。因此，数据的逻辑结构可以看作是从具体问题抽象出来的数学模型。
§ 数据的逻辑结构有两大类：
§ 线性结构——线性结构的逻辑特征是：有且仅有一个始端结点和一个终端结点，并且除两个端点结点外的所有结点都有且仅有一个前趋结点和一个后继结点。线性表、堆栈、队列、数组、串等都是线性结构。
§ 非线性结构——非线性结构的逻辑特征是：一个结点可以有多个前趋结点和后继结点。如树形结构、图等
2、数据的物理结构
§ 数据的物理结构是逻辑结构在计算机存储器里的映像，也称为存储结构。
§ 数据的存储结构可用以下四种基本存储方法体现：
§ 顺序存储方法——把逻辑上相邻的结点存储在物理位置上相邻的存储单元里，结点之间的逻辑关系由存储单元的邻接关系来体现。由此得到的存储结构称为顺序存储结构。
§ 链式存储方法——不要求逻辑上相邻的结点在物理位置上也相邻，结点之间的逻辑关系是由附加的指针字段表示的。由此得到的存储结构称为链式存储结构。
§ 索引存储方法——在存储结点信息的同时，还建立附加的索引表，索引表中的每一项称为索引项。索引项由关键字和地址组成，关键字是能惟一标识一个结点的那些数据项，而地址一般是指示结点所在存储位置的记录号。
§ 散列存储方法——根据结点的关键字直接计算出该结点的存储地址。
§ 用不同的存储方法对同一种逻辑结构进行存储映像，可以得到不同的存储结构。四种基本的存储方法也可以组合起来对数据逻辑结构进行存储映像。
3、数据的运算
§ 数据的运算是指对数据施加的操作。它是定义在数据的逻辑结构上的，但运算的具体实现要在物理结构上进行。数据的每种逻辑结构都有一个运算的集合，常用的运算有检索、插入、删除、更新、排序等

线性表：
1．顺序表
§ 当线性表采用顺序存储结构时称之为顺序表。在顺序表中，数据元素按逻辑次序依次放在一组地址连续的存储单元里。由于逻辑上相邻的元素存放在内存的相邻单元里，所以顺序表的逻辑关系蕴含在存储单元的邻接关系中。在高级语言中，可以直接用数组实现。
2. 单链表
§ 采用链式存储结构的链表是用一组任意的存储单元来存放线性表的数据元素，这组存储单元既可以是连续的，也可以是不连续的，甚至可以是零星分布在内存中的任何位置上，从而可以大大提高存储器的使用效率。
§ 在线性链表中，每个元素结点除存储自身的信息外，还要用指针域额外存储一个指向其直接后继的信息（即后继的存储位置：地址）。
3. 栈与队列
栈与队列是两种特殊的线性表。即它们的逻辑结构与线性表相同，只是其插入、删除运算仅限制在线性表的一端或两端进行。

（1）栈
§ 栈是仅限于在表的一端进行插入和删除运算的线性表，通常称插入、删除的这一端为栈顶，另一端称为栈底。当表中没有元素时称为空栈。
§ 栈的特点是：后进先出（LIFO——Last In，First Out）。
§ 如：入栈顺序为 1，2，3，4，5，出栈为 5，4，3，2，1。
（2）队列
§ 队列是一种操作受限的线性表，它只允许在线性表的一端进行数据元素的插入操作，而在另一端才能进行数据元素的删除操作。其中，允许插入的一端称为队尾，允许删除的另一端称为队头。
§ · 特点：先进先出（FIFO——First In，First Out）。
树
1．树结构
树是一个或多个结点元素组成的有限集合T，且满足条件如下：
§ 树结构的重要术语与概念：
① 叶子——没有后继结点的结点称为叶子（或终端结点）。
② 分支结点——非叶子结点称为分支结点。
③ 结点的度——一个结点的子树数目就称为该结点的度。
④ 树的度——树中各结点的度的最大值称为该树的度。
⑤ 子结点——某结点子树的根称为该结点的子结点。
⑥ 父结点——相对于某结点的子树的根，称为该结点的子树的父结点。
⑦ 兄弟——具有同一父结点的子结点称为兄弟。
⑧ 结点的层次——根结点的层次数是1，其他任何结点的层数等于它的父结点的层数加1。
⑨ 树的深度——一棵树中，结点的最大层次数就是树的深度。
2．二叉树
二叉树结构也是非线性结构中重要的一类，它是有序树，不是树的特殊结构。在二叉树中，每个结点最多只有两棵子树，一个是左子树，一个是右子树。
满二叉树和完全二叉树是两种特殊形式的二叉树。一棵深度为k且有2k-1个结点的二叉树称为满二叉树。满二叉树的特点是每一层上的结点数都达到最大值，2k-1个结点是深度为k的二叉树所能具有的最大结点个数。
§ 性质1 ——在二叉树的第i层上至多有2i-1个结点( i>0 )。
§ 性质2 ——深度为k的二叉树至多有2k-1个结点(k＞0)。

图结构
图是一种重要的、比树更复杂的非线性数据结构。

软件工程的基本概念
1．软件
§ 软件是程序的完善和发展，是经过严格的正确性检验和实际试用，并具有相对稳定的文本和完整的文档资料的程序。这些文档资料包括功能说明、算法说明、结构说明、使用说明和维护说明等。
§ 定的文本和完整的文档资料的程序。这些文档资料包括功能说明、算法说明、结构说明、使用说明和维护说明等。
2．软件危机
§ 由于软件本身是一个逻辑实体，而非一个物理实体，因此软件是非实物性与不可见的。而软件开发本身又是一个“思考”的过程，很难进行管理。开发人员以“手工作坊”的开发方式来开发软件，完全是按照各自的爱好和习惯进行的，没有统一的标准和规范可以遵循。因而，在软件的开发过程中，人们遇到了许多困难。有的软件开发彻底失败了，有的软件虽然开发出来了，但运行的结果极不理想。这些软件有的因无法维护而不能满足用户的新要求，最终失败了；有的虽然完成了，但比原计划推迟了好几年，而且成本上大大超出了预算。
§ 软件开发的高成本与软件产品的低质量之间的尖锐矛盾，终于导致了软件危机的发生。
§ 为摆脱软件危机，首次提出了“软件工程”的概念，认为计算机软件的开发，也应像工程设计一样，进行规范性的开发，走“工程化”的道路。以按照预期进度和经费完成软件生产计划。提高软件生产效率和可靠性。“软件工程”出现以后，人们围绕着实现软件优质高产的目标进行了大量的理论研究和实践，逐渐形成了“软件工程学”这一新型学科。
1、软件生存周期
§ 一个软件从用户提出开发、使用要求到废弃不用为止的全过程，称为软件生存周期，又称软件生命周期。
§ 软件生命周期由软件定义、软件开发、软件维护三个时期组成。每个时期又分为若干个阶段。
2、软件定义
§ 软件定义，又称为系统分析。这个时期的任务，是确定软件开发的总目标，确定软件开发工程的可行性，确定实现工程目标应该采用的策略和必须完成的功能，估计完成该项工程需要的资源和成本，制定出工程进度表。
§ 软件定义，可进一步划分为三个阶段，即问题定义、可行性研究和需求分析。
3、软件开发
§ 软件开发，是实现前一个时期定义的软件。它包含四个阶段：总体设计、详细设计、编码、测试。
① 总体设计的目标是采用结构化分析的成果，由数据模型、功能模型、行为模型描述的软件需求，按一定的设计方法，完成数据设计、体系结构设计、接口设计和过程设计。
§ 总体设计应遵循的一条主要原则就是程序模块化的原则。总体设计的结果通常以层次图或结构图来表示。
§ 采用传统软件工程学中的结构化设计技术或面向数据流的系统化的设计方法来完成。总体设计阶段的表示工具有层次图、HIPO图等。
② 详细设计阶段的方法：
§ 结构化程序设计技术。如果一个程序的代码仅仅通过顺序、选择和循环这三种控制结构进行连接，并且每个代码块只有一个入口和出口，则称此程序为结构化的。主要工具有：程序流程图（程序框图）、方框图：（N-S图）、问题分析题（PAD图）、伪码语言（PDL语言）等。
§ 面向数据结构的设计方法，适用于信息具有清楚的层次结构的应用系统开发。
§ 面向对象的程序设计方法：OOP (Object Oriented Programming)。
4、软件测试
§ 测试的定义：为了发现程序中的错误而执行程序的过程。
§ 测试的目的：尽可能揭露和发现程序中隐藏的错误，好的测试方案是极可能发现尚未发现的错误的测试方案。
5、软件维护
§ 软件维护的任务，是使软件能够持久地满足用户的需求。具体地说，当软件在使用过程中发现错误，应能及时地改正；当用户在使用过程中提出新要求，应能按要求进行更新；当系统环境改变，应能对软件进行修正，以适应新的环境。

3