计算机软件技术基础.ppt

计算机软件技术基础 第一章软件工程第二章数据结构第三章操作系统第四章数据库技术第五章面向对象程序设计第六章计算机网络第七章网页设计综合练习题 第一章软件工程 本章简单介绍软件工程的形成和发展 重点介绍软件开发的不同方法和软件测试策略与方法 最后就软件开发环境和软件重用技术作一简要介绍 1 1概述软件工程的提出源于20世记60年代末期出现的 软件危机 并在较短的时间内发展成一个完整的学科方向 30多年来 在理论研究和工程实践两个方面作了大量的工作 1 1 1软件工程的形成与发展1 软件发展的三个阶段软件开发方法从机器语言编程到软件工程方法 经历了三个阶段 1 程序设计时期 1946年到60年代中期 生产方式是手工生产 个体劳动 只有程序 无软件的概念 2 软件时期 60年代中期至70年代中期 程序不再是硬件的附属 有软件的概念 作坊式的生产方式已难满足软件生产的质量和数量上的要求 出现了 软件危机 3 软件工程时期 70年代至今 1968年 1969年北大西洋公约组织成员国的软件工件者召开了两个研讨会 提出了 软件工程 这一述语 根本目的在于克服 软件危机 中所遇到的困难问题 从此进入软件工程时代 2 软件危机 1 软件危机的主要表现 软件开发成本和进度的估计常常很不准确 用户往往对已完成的软件不满意 3 软件的质量常被怀疑 4 软件极难维护 5 缺乏良好的软件文档 6 软件开发生产率提高的速度远远跟不上计算机应用迅速普及深入的趋势 2 软件危机的产生原因一般以为 软件危机的发生与软件产品的特征和软件产品开发与维护的方法不正确有关 其一 软件是逻辑的系统部件而不是物理的系统部件 以程序和文档形式存在 具有无形性 其二 软件规模越来越大 功能越来越强 导致软件结构非常复杂 3 解决软件危机的途径方法是要充分吸取和借鉴人类长期以来从事各种工程项目所积累的行之有效的原理 概念 技术和方法 并应用于软件开发的实践中 将软件开发变成一种组织良好 管理严密 各类人员协同完成的工程项目 3 软件工程1983年IEEE定义为 软件工程是开发 运行 维护和修复软件的系统方法 软件工程学的多个分支 1 软件工程方法学方法学是研究软件构造技术的学问 一个软件从定义 开发到维护 都需要有适当的方法 2 软件工程环境对最终用户而言 环境就是他们运行程序所使用的计算机系统 对于应用软件开发人员 环境是开发活动的舞台 软件工具是环境中最活跃的成分 所谓工具 在这里泛指一切帮助开发软件的软件 在软件开发的各个方面都研制了许多有效的工具 集成化工具的自动切换 可以明显提高软件的生产率 3 软件工程管理软件工程管理的目的 是为了按照软件的预算和进度完成项目计划 实现预期的经济和社会效益 1 1 2软件工程范型1 传统的软件工程范型 瀑布模型瀑布模型是1976年由B W Boehm提出的 是基于软件生存周期的一种范型 它将软件生存周期分为定义 开发 维护三个阶段 每个阶段又分为若干个子阶段 各子阶段的工作顺序展开 如自上而下的瀑布 见后图 定义阶段 分析用户需求 问题定义 收集 分析 理解 确定用户的要求 可行性研究 确定对问题是否有可行的解决办法 需求分析 确定用户对软件系统的全部需求 开发阶段 设计 设计软件系统的模块层次结构 数据库结构 模块控制流程等 编程 将每个模块的控制流程纺出相应的程序 测试 检查并排除软件中的错误 提高软件的可靠性 维护阶段 运行与维护 维护软件系统的正常运行 各个阶段确均有相应的文档 问题定义 或行性研究 需求分析 设计 编程 测试 运行与维护 目标与范围说明 可行性论证报告 需求说明书 设计文档 程序 测试报告 维护报告 定义阶段 开发阶段 维护阶段 传统的软件工程范型 瀑布模型 1 2软件开发方法两种不同的开发方法 结构化开发方法和面向对象的开发方法 1 2 1结构化开发方法一 结构化分析1 结构化分析方法 亦称SA StructuredAnalysis 方法 1 SA方法的特点 核心思想 自顶向下和逐步求精 基本手段 分解和抽象 分解 把大问题分割成若干小问题 然后分别解决 抽象 略去细节 先考虑问题最本质的属性 使用了描述需求说明书的几个规范工具 即数据流图 数据词典 小说明 加工逻辑的描述 等 使文档规范化 2 数据流图 DataFlowDiagram 简称DFD图 SA方法采用 分解 的方法来描述一个复杂的系统 数据流图是描述系统中数据流程的图形工具 它标识了一个系统的逻辑输入和逻辑输出以及把逻辑输入转换为逻辑输出所需要的加工处理 1 数据流图的基本符号 1 数据流 2 加工 3 数据存储 4 数据源点或终点 画各层数据流图应注意的问题 1 父图和子图平衡 2 子图的编号 3 数据守恒 3 数据词典 DataDictionary 简称DD 对数据流图中包含的所有元素的定义的集合构成了数据字典 数据词典中有四种类型的条目 数据流 文件 数据项和加工 1 数据流条目数据流条目给出某个数据流的定义 它通常是列出该数据流的各组成数据项 如 课程 课程名 教员 教材 课程表课程表 星期几 第几节 教室 2 文件条目文件条目给出某个文件的定义 订单文件 订单编号 顾客名称 产品名称 订货数量 交货日期 3 数据项条目数据项条目给出某个数据单项的定义 学号编号 1 9999 4 加工条目加工条目又称小说明 小说明中应精确地描述用户要求某个加工做什么 2 结构化设计结构化设计方法 亦称SD StructuredDesign 方法 是一种面向数据流的设计方法 目的在于确定软件的结构 1 SD方法的基本思想其基本思想是 根据SA方法中的数据流图建立一个良好的模块结构图 例如SC图或软件层次方框图 运用模块化的设计原理控制系统的复杂性 即设计出模块相对独立的 模块结构图深度 宽度都适当的 单入口单出口的 单一功能的模块结构的软件结构图或软件层次方框图 此方法提供了描述软件系统的工具 提出了评价模块结构图质量的标准 即模块之间的联系越松散越好 而模块内各成分之间的联系越紧凑越好 2 SD方法的设计原理1 模块化 模块化就是把系统划分为若干个模块 从而获得满足问题需要的一个解的过程 2 模块的独立性 模块独立性有两个定性的度量标准 即内聚和耦合 耦合有六种 从小到大如下 两个模块完全独立 没有任何联系 数据耦合 即两个模块只通过数据进行交换 状态耦合 即两个模块之间通过控制状态进行传递 环境耦合 即两个模块之间通过公共环境进行数据存取 公共块耦合 即多个模块引用一个全程数据区 内容耦合 即一个模块使用保存在另一模块内部的数据或控制信息 或转移进入另一个模块中间时 或一个模块有多个入口时 由此看出模块间耦合性越小越好 内聚有六种 从小到大如下 偶然内聚 即一个模块由多任务组成 这些任务之间关系松散或根本没联系 逻辑内聚 即一个模块完成的任务在逻辑上相同或相似 时间内聚 即一个模块所包含的任务必须在同一时间内执行 通信内聚 即一个模块内所有处理元素集中于相同的数据结构 顺序内聚 即一个模块中所有处理元素都是为完成同一功能而且必须顺序执行 功能内聚 一个模块所有处理都完成一个而且仅完成一个功能 内聚性给出模块的内在联系 因此内聚性越大越好 3 模块的设计准则 通过模块的分解和合并 提高模块的独立性 模块调用个数最好不要超过五个 降低模块接口的复杂性 一个模块的所有下属模块应该包括该模块受某一判定影响的所有模块的集合 模块应设计成单入口和单出口 模块的大小要适中 一般在50句左右 3 数据流图的类型数据流图通常分为两大类型 转换处理型和事务处理型 转换处理型 由于大多数数据流图都可看成是对输入数据进行转换而得到输出数据的处理 因此可把这类处理抽象为转换处理型 转换处理过程大致分为输入数据 变换数据和输出数据三步 它包含的数据流有输入流 转换流 输出流三个部分 在输入流中 信息由外部形式转换为内部形式的结果 在输出流中 信息由内部形式的结果转换为外部形式数据流出系统 转换处理型的数据流图 事务处理型 另一类数据流图可看成是对一个数据流经过某种加工后 按加工的结果选择一个输出数据流继续执行的处理 这种类型的处理可以抽象为事务处理型 在事务处理中 输入数据流称为事务流 加工称为事务中心 若干平行数据流称为事务路径 当事务流中的事务送到事务中心后 事务中心分析每一事务 根据事务处理的特点和性质选择一个事务路径继续进行处理 4 SD方法的设计过程使用SD方法的基础是数据流图 正如前面所述 几乎所有软件在分析阶段都可以表示为数据流图 所以SD方法基本上可适用于任何软件的开发工作 用SD方法进行总体设计的过程大致如下 1 研究 分析和审查数据流图 从软件的需求说明书弄清楚数据流加工的过程 2 根据数据流图确定数据流图的类型 3 从数据流图导出系统的初始软件结构图 4 改进初始软件结构图 直到符合要求为止 5 复查 5 软件结构的描述方式在SD方法中 软件结构用一种结构图来描述 它是设计说明书的一部分 结构图描述了软件模块结构 并反映了模块和模块间联系等特性 3 详细设计和编码 1 详细设计的任务为软件结构图中的每一个模块确定采用的算法和块内数据结构 用某种选定的表达工具给出清晰的描述 2 详细设计的描述工具 程序流程图也称为程序框图 独立于任何一种程序设计语言 比较直观 清晰 易于掌握 任何复杂的程序流程图都可以由以下不同类型的基本结构组合或嵌套而成 顺序结构选择结构 IF THEN ELSE 多分支选择结构 CASE 先判定循环结构 WHILE 后判定循环结构 UNTIL 2 方框图 N S图 图形描述工具 限制了随意的控制转移 顺序结构选择结构多分支选择结构 先判定型循环结构后判定型循环结构 3 结构化编码方法 对源程序的编码要求 最基本要求是源程序的正确性 同时还要考虑其可读性 可理解性 可测试性和可维护性 写程序的风格 一个好的源程序意味着源程序代码逻辑简明清晰 易读易懂 编码原则 程序内部文档应选取含义鲜明的名字 注解正确 程序清单层次清晰 布局合理 数据说明和次序应该标准化 个别复杂的数据结构应加注释 每个语句应该简单直接 不能为提高效率而使程序变得过份复杂 对输入数据应进行合法性检查 对输出数据要加输出数据的标志 在程序编码阶段以不影响程序的清晰度和可读性为前提 尽可能提高效率 1 2 2面向对象开发方法面向对象技术是一种非常实用而强有力的软件开发方法 面向对象软件开发方法又称OOSD Object OrientedSoftwareDevelopment OOSD包括面向对象分析 OOA 面向对象设计 OOD 和面向对象程序设计 OOP 三个方面 其中OOP是基础 OOA和OOD是应用OOP的机制 面向对象方法和技术是自80年代以来逐渐形成的一种分析问题和解决问题的新方法 其基本出发点就是尽可能按照人类认识世界的方法和思维方式来分析和解决问题 客观世界是由许多具体的事物或事件 抽象的概念和规则等组成的 因此 我们将要加以研究的事 物 概念都称为对象 面向对象的方法正是以对象作为最基本的元素 以对象作为分析问题 解决问题的核心 1 面向对象分析 OOA 把对象作为现实世界的抽象表示 然后定义对象的属性和专门操纵那些属性的服务 属性和服务被看成对象的特征 具有相同的属性和服务抽象的一系列对象组成类 因此在面向对象模型中 它可以包含若干类 并且它对应于模型的不同层次 因此这些类有一定的层次关系和属性继承关系 面向对象分析由五个主要步骤构成 1 标识对象 2 标识对象属性 3 定义对象的服务 4 识别对象所属的类 5 定义主题 2 面向对象的设计 OOD OOA是一个分类活动 而OOD模型由主体部件 用户界面部件 任务管理部件和数据管理部件四部分构成 每个部件又由主题词 对象及类 结构 属性和外部服务五层组成 它们分别对应OOA中的五个活动 定义主题词 标识对象 标识类 标识对象的属性和标识对象的服务 其中主体部件是整个设计的主体 它包括完成目标软件系统主要功能的所有对象 用户界面部件给出人机交互需要的对象 任务管理部件提供协调和管理目标软件各个任务的对象 数据管理部件定义专用对象 要将目标软件系统中依赖于开发平台的数据存取操作与其他功能分开 以提高对象独立性 概括地说 OOD方法是以OOA模型为基础 不断填入和扩展有关软件设计的信息 3 面向对象编程完成OOD以后 将开始进入编程阶段 目前主要选取面向对象语言 如C 基于对象的语言 如Ada 过程式语言 如C语言 1 3软件测试与质量保证1 3 1软件测试原则1 基本概念软件测试定义 软件测试是为了发现错误而执行程序的过程 软件测试分为 单元测试和综合测试 软件测试在软件生存周期中横跨了两个阶段 通常在编写出第一个模块之后就对它做必要的测试 称作单元测试 编码与单元测试属于软件生存周期中的同一阶段 在结束这个阶段之后 对软件系统还要进行各种综合测试 这是软件生存周期的另一个独立的阶段 即测试阶段 2 目标和原则软件测试的目标可以归纳为以下几点 1 测试是为了发现软件中的错误而去运行软件的过程 2 好的测试方案是尽可能地发现至今尚未发现的错误的测试方案 3 成功的测试则是发现出至今未发现的错误的测试 1 3 2软件测试策略与技术1 软件测试策略测试过程是按单元测试 组装测试 确认测试和系统测试四个步骤进行的 1 单元测试 模块测试 目的是发现模块的子程序或过程的实际功能与该模块的功能和接口描述是否相符 以及是否有编码错误存在 单元测试的主要内容有 模块接口测试 局部数据结构测试 重要路径测试 出错处理能力测试 边界条件测试 2 组装测试 集成测试或联合测试 它的测试目的是为了发现程序结构的错误 组装测试过程中的模块组织方式有非渐增式和渐增式两种 非渐增式组装测试 又称一次性组装方式或整体拼装 测试方式是先对每个模块分别进行测试 然后再把所以模块组装在一起整体测试 其优点是对各模块的测试可以并行进行 有利于充分利用人力 加快测试速度 其缺点是由于程序中不可避免的地存在涉及模块间接口 全局数据结构等方面的问题 所以一次试运行成功的可能性不大 结果是发现有错误 但却找不到错误的产生原因 渐增式组装测试这种方式是对一个个模块进行模块调试 然后将这些模块逐步组装成较大的系统 在组装过程中 每连接一个模块便进行一次测试 直到把所有模块集成为一个整体并进行测试 则软件的组装测试完成 在渐增测试过程中 将模块结合起来的策略有两种 自底向上测试和自顶向下测试 自底向上测试 从程序模块结构的最低层模块进行组装和测试 因为模块是自底向上进行组装的 对给定层次的模块的下层模块处理功能总可以得到 所以这种测试策略不必设计桩模块 存根模块 但要设计驱动模块 自顶向下测试 将模块按系统程序结构 沿控制层次自顶向下进行组装 由主控模块开始 按照程序的层次结构向下移动 逐渐把各个模块组装起来 3 确认测试 有效性测试 又称有效性测试 组装测试结束后 得到的是一个完整的软件系统 这时需要进行最后的测试 即有效性测试 有效性测试阶段主要进行的测试有 有效性测试 黑盒测试 软件配置复查 测试和 测试以及验收测试 4 系统测试系统测试是指将经过测试后的软件系统与计算机硬件 外设 其他支持软件以及其他系统元素一起进行测试 测试内容主要有 功能测试 吞吐量测试 可用性测试 保密性测试 安装测试 可恢复性测试 资料测试和程序测试 2 常用的测试方法常用的测试方法有黑盒测试和白盒测试两种 1 白盒测试白盒测试又称结构测试或逻辑驱动测试 所谓 白盒 是指将对象看作一个打开的盒子 测试人员可利用程序内部的逻辑结构及有关的信息来设计或选择测试用例 白盒测试主要考虑的是测试用例对程序内部逻辑的覆盖程度 而不考虑程序的功能 测试用例对程序的覆盖程序从低到高分别为 语句覆盖 判定覆盖 条件覆盖 判定 条件覆盖 条件组合覆盖 需要说明的是 上述各种覆盖准则的侧重点不同 覆盖程度也不同 但它们共同的是 任何一种覆盖都不能做到完全测试 2 黑盒测试黑盒测试又称功能测试或数据驱动测试 在这种测试方法中 程序对测试者是完全透明的 测试者不考虑程序的内部结构和特性 就好像把程序看作一个不能打开的盒子 只根据程序的需求规格说明中的程序功能或程序的外部特性来设计测试用例 黑盒测试的方法包括 等价分类法 边缘值分析法 因果图法和错误推测法 测试方法还有回归测试 强度测试等等 每一种测试方法都各有所长 在实际测试中应综合使用 一般来讲 通常用黑盒法设计基本的测试方案 再利用白盒法做必要的补充 1 3 3软件质量保证1 评审与测试评审和测试都是质量保证的重要活动 验证 我们制造产品的步骤正确吗 确认 我们制造的是正确的产品吗 2 程序正确性证明程序正确性证明就是要通过数学的方法 证明程序具有某些需要的性质 通过多年的研究 现已提出了一些有用的方法和技术 其中包括输入 输出断言法 最弱前置条件法 结构归纳法纪等几种常用的方法 如果说程序测试是为了证明程序有错 则程序正确性的证明正好相反 是为了证明程序能够完成某些预定的功能 现有的证明程序正确性的技术与工具包括已研制出来的程序正确性自动证明器 仅适用于很小的程序 要解决大程序的正确性证明 还需要进行大量的工作 1 4软件重用重用 Reuse 是软件过程的一部分 为了快速做出复杂的应用 重用是一条捷径 此外 重用也是当今软件系统的重要特征 重用指在一个软件项目中直接使用以前项目中的产物 而非重用某些工具 也就是把以前做过的东西纳入到新项目中 1 重用过程面向对象的语言本身就提供了重用机制 如封装 继承 模板等 技术上可以制成可重用构件 不仅封装数据还封装行为 成为独立的可重用对象 这样可以大幅度提高开发效率 重用的真正价值在于方案 决策的重用 利用集成技术将构件按可重用模式装入可重用框架 相当于建筑中的梁 柱组成的房梁 构成一组装式软件过程 从代码重用到构件重用到设计重用到过程重用 域工程 从初创到成长到成就到实用 现代的软件平台 或多或少都提供了重用机制 2 支持重用的环境从过程重用的观点 以下10种软件过程产物均可以重用 项目计划 费用估算 体系结构 需求模型和规格说明 设计 源代码 各种文档 人机界面 测试用例 数据这些产物作为重用件要作分类 标记 作为对象构件放入构件库 在当今CIS分布系统上 构件库是一个数据库服务器 它提供访问服务 重用环境还必须提供集成工具 使重用的构件能集成到新项目中 3 构件与构件重用构件 是可重用的 具有独立性的软件单元 是用来构造其他软件的部件 构件具有以下特点 1 构件是具有独立性的 被封装好的 具有描述能力的软件单元 2 构件本身不是一个完整的应用程序 3 构件都有被定义好的接口 只巴能通过这些接口来操纵构件 4 构件之间可以交互 5 构件可以被扩展 构件的可继承性使构件能够被扩充和修改 目前有两个方面的技术 一种是可视化构件 另一种是分布式对象构件 1 5软件开发环境软件开发由来已久 一台宿主机 一个编译 或汇编 程序 加上编辑 链接 装入等少量实用程序 就构成了早期软件开发的舞台 从这个意义上讲 在软件工程兴起之前就有了软件开发环境 在70年代和80年代初期 开发环境常被称为 软件工程环境 简称SEE或SE2 或 程序设计支撑环境 计算机辅助软件工程 简称CASE 是今天对开发环境最流行的称呼 成为描述软件开发环境与工具的最通用的名称 另一个常见的名称 工作台 workshop 1976年 ICSE第二届会议在一篇文章中发表了一个基于UNIX操作系统的程序设计支撑环境 称之为 UNIX程序员工作台 UNIXprogrammer sworkbench 简写为UNIX PWB 这是国际上出现的第一个有影响的软件开发环境 自此之后 工作台也常被用作开发环境的同义词 2 集成化工具开发软件用到两类工具 一类工具是画或写在纸上的 包括在不同阶段使用的各种图形与语言 另一类则是用来 开发软件的软件 又称为 软件工具 或CASE工具 这里讨论的是后一类工具 早期的环境只配置用于编码阶段的工具 也称为 低层 CASE工具 今天在软件分析和总体设计等阶段也有了许多支持开发的工具 即 高层 CASE工具 70年代出现了 工具箱 能部分地实现从一个工具到另一个工具的切换 今天 高 低层CASE工具由一组专用程序和一个用来支持工具间数据交换的环境信息库构成的支持下 共同构成了具有统一的用户界面 并能自动实现工具切换的 集成工具 对软件开发的自动化提供了有力的支持 CASE环境还可能包括另两个层次 一个是环境体系结构 用于区分开发环境为单机环境或网络环境 另一个是可移植性服务程序 它介于集成工具与宿主机之间 使集成后的CASE工具不需要作重大的修改即可与环境的软 硬件平台适应 小结软件工程是从工程角度来研究软件开发的方法和技术 它是在克服软件危机的过程中产生而发展起来的 软件工程学是自软件工程出现以后形成的一门新兴学科 它包括的主要内容有 软件工程方法学 软件工程环境和软件工程管理等多个分支 一个软件从用户提出开发要求 到废弃不用为止的全过程 称为软件的生存周期 软件的生存周期划分为若干个阶段 如 需求定义 软件设计 编程 测试 运行维护等 每个阶段有相对独立的任务 需求分析最常用的方法是结构化分析方法 SA方法 SA方法适于分析大型数据处理系统 使用的主要工具有数据流图和数据词典 数据流图以图形形式表示软件信息流向和信息加工 而数据词典对这些信息和加工进行更详细的描述 SA方法简单实用 易于理解 使用广泛 软件设计可分为总体设计和详细设计 总体设计通常使用结构化设计方法 详细设计是根据结构化程序设计原则进行的 只使用顺序 分支 重复三种结构来设计模块的控制流程 使用的表示工具有程序流程图 方框图 PAD图 伪码 PDL语言 等 软件编程的任务是将软件详细设计的结果转换成某种程序设计语言编写的源程序 面向对象的方法是在结构化程序设计的基础上 进一步力图用更自然的方法反映客观世界 在面向对象的系统中 将数据和使用该数据的一组基本操作或过程封装在一起 用 对象 这个概念来完整地反映客观事物的静态属性和动态属性 面向对象 的基本思想就是把要构造的系统表示为对象的集合 软件测试是为了发现错误而执行程序的过程 软件测试的目的是要暴露软件系统中的隐含错误 然后通过软件测试找出错误的原因和位置并加以改正 在软件开发中 测试是保证软件正确性的最后一个阶段 测试需要制定测试计划 设计测试用例 然后实施测试 测试后进行分析评价 测试结束后 要给出测试报告 软件测试方式分为 人工测试 动态测试和自动测试三种 测试过程按单元测试 组装测试 确认测试和系统测试四个步骤 常用的测试方法有黑盒测试和白盒测试两种 对于不同的测试方法 需要设计不同的测试用例 阶段评审与测试 软件配置管理是保证软件质量的重要环节 软件质量保证计划是确保上述环节实施的关键 软件重用和CASE集成环境是当今软件工程技术重要的两个方面 重用技术已从代码重用发展到域工程 是大规模生产软件的希望 集成技术在对象包装下 当今分布式应用系统上已可实现数据集成 控制集成 表示集成 第二章数据结构概述 随着计算机应用领域的不断扩大 非数值数据的处理变得尤为重要 这些数据的元素之间在多是相互有关的 因此 讨论数据元素之间的逻辑关系 数据元素在计算机中的存储方式及在数据元素集合上设立的运算如何实现 这是研究数据处理的基础 本章在介绍数据结构的有关概念后 着重讨论线性结构 树型结构和图形结构等三类数据结构 最后介绍数据结构中两种特别重要的运算 查找和排序 对数据结构的基本操作 本章采用C语言描述 2 1概述2 2线性表2 3树型结构2 4图2 5查找2 6排序小结 2 1概述计算机早期运算 原始数据和结果数据不多 重点在于算法 计算机应用的发展 逐渐变成对数据进行非数值型的加工处理为主 特点是数据量大 而计算的工作量可能很小 数据结构的提出 数据结构是为研究和解决诸如数据的分类与查找 情报检索 数据库 企业管理 系统工程 图形识别 人工智能以及日常生活等各领域的非数值问题而提出的理论与方法 即如何合理的组织数据 以提高算法的效率 重要性 对实现系统软件 如操作系统 编译程序和数据库管理系统等均有十分重要的意义 2 1 1数据结构的概念数据 描述客观事物的的信息 数 字符 符号等 的集合 是程序处理的对象 数据元素 是数据集合中的个体 是构成数据对象的基本单位 可由若干个数据项组成 数据项 是数据的最小单位 一组数据元素具有某种结构形式 数据结构 就是描述一组数据元素及元素间的相互关系的 数据结构描述了一组性质相同的数据元素及元素间的相互关系 用集合论给出的数据结构的定义为 数据结构S是一个二元组 S D R 其中 D是一个数据元素的非空的有限集合 R是定义在D上的关系的非空的有限集合数据结构概念一般包括三个方面的内容 数据元素之间的逻辑关系 数据元素在计算机中的存储方式以及在这些数据元素上定义的运算的集合 2 1 2数据的逻辑结构数据的逻辑结构有时可直接称为数据结构 数据的逻辑结构的三种基本类型 线性表 树和图 分别属于两大类 一 线性结构 线性表 各数据元素之间的逻辑关系可以用一个线性序列简单地表示出来 线性表是典型的线性结构 它的数据元素只按先后次序联接 有栈 队列 字串 数组和文件 二 非线性结构 树 图 不满足线性结构特点的数据结构称为非线性结构 树 图等是非线性结构 树中的数据元素是分层次的纵向联接 图中的数据元素则有各种各样复杂联接 其它种类的数据结构由这三种基本结构派生的 2 1 3数据的物理结构数据的逻辑结构在计算机存储设备中的映象称为数据的存储结构 亦称为物理结构 同一个逻辑结构可以有不同的存储结构 最常用的二种方式是 顺序存储结构和链接存储结构 大多数据结构的存储表示都采用其中的一种方式或两种方式的结合 1 顺序存储结构数据结构的数据元素按某种顺序存放在存储器的连续单元中 即将逻辑上相邻的数据元素存储在物理上相邻的存储单元中 而数据元素之间的关系由存储单元的邻接关系唯一确定 若数据元素存放在以起始地址S开始的连续存储单元中 则第i个元素的存储地址 LOC i LOC 1 i 1 l S i 1 l 假定每个元素所占的存储空间是相同的 长度均为l 数据的这种顺序存储结构叫做向量 以V表示 向量V的分量V i 是数据结构的第i个元素在存储器中的映像 顺序存储的主要特点是 1 结点中只有自身信息域 没有连接信息域 因此存储密度大 存储空间利用率高 2 可以通过计算直接确定数据结构中第i个结点的存储地址L 即可以对记录直接进行存取 3 插入 删除运算会引起大量结点的移动 4 要求存储在一片连续的地址中 这种存储方式主要用于线性的数据结构 2 链接存储结构存储数据结构的存储空间可以不连续 而数据元素之间的关系是由指针来确定的 主要特点是 1 结点由两类域组成 数据域和指针域 2 逻辑上相邻的结点物理上不必邻接 既可实现线性数据结构 又可用于表示非线性数据结构 3 插入 删除操作灵活方便 不必移动结点 只要改变结点中的指针值即可 2 1 4数据结构的运算对一些典型数据结构中的结点进行操作处理 1 插入 在数据结构中的指定位置上插入新的数据元素 2 删除 根据一定的条件 将某个结点从数据结构中删除 3 更新 更新数据结构中某个指定结点的值 4 检索 在给定的数据结构中 找出满足一定条件的结点来 条件可以是某个或几个数据项的值 5 排序 根据某一给定的条件 将数据结构中所有的结点重新排列顺序等 从操作的特性来看 所有这些运算的操作可以分为二类 一类是加工型操作 操作改变了存储结构的值 如插入 删除 更新等 另一类是引用操作 操作只是查询或求得结点的值 如检索等 2 2线性表 最简单 最常用的一种数据结构2 2 1线性表线性是指表中的每个元素呈线性关系 即除第一个外 都有一个直接前趋 predecessor 同时除最后一个元素外 都仅有一个直接后继 successor 1 线性表的逻辑结构线性表L用符号表示为 L a1 a2 a3 ai an 线性表也可以正式定义为 若数据结构L D R 是一个线性表 则 D是包括a1 a2 a3 an等元素的集合 R中只包含一个关系 即R ai 1 ai D 2 i n 关系给出了元素的一种先后次序 a1称为表的线性起始结点 an为表的终结点 2 线性表的存储结构存储结构 顺序存储结构和链接存储结构 具有顺序存储结构的线性表称为顺序表 即用一组地址连续的存储单元依次存储线性表中的每个数据元素 具有链接存储结构的线性表称为线性链表 链式存储结构是用一组任意的存储单元来存储线性表中数据元素的 这组存储单元可以是连续的 也可以是不连续的 通常亦称为链表 常用的链表有单链表 循环链表和双向链表 3 线性表的基本运算常用的操作有 插入 删除 修改 读值 检索和排序等 线性表还可以进行一些更为复杂的操作 如将两个或两个以上的具有相同数据对象的线性表合并成一个线性表 将一个线性表拆成若干个线性表 复制一个线性表等等 这些较为复杂的操作都可以利用上述几种常用的操作来实现 1 顺序表的操作顺序表在各种高级语言里经常用一维数组实现 defineMAXSIZE100 数组中元素个数的最大值intlist MAXSIZE n n为线性表中当前的结点数 插入运算插入运算是在线性表的第i个元素和第i 1个元素之间插入一个一个新元素x 为了实现这个操作 必须把第i 1个元素到第n个元素依次向后移位一个位置 以便把第i 1个存储位置让出来 存储新元素X 假定已有一个数组 其值是由小到大排列的 现插入一个新的结点p0 要求插入后仍能保持由小到大的顺序 defineN20inta N main inti data n 10 for i 0 i0 i if a i 1 data a i a i 1 else a i data break if i 0 a 0 data 当i 0时 新结点x插在a1之前 这时需移动线性表中的所有元素 当i n 1时 新结点x插入在an 1之后 这时不需移动线性表中的元素 在具有n个结点的线性表中 插入一个新结点时 其执行时间主要化费在移动结点的循环上 移动结点的平均次数为 删除运算线性表的删除运算是指将线性表中第i个数据元素除掉 即把长度为n的线性表 a1 a2 ai 1 ai ai 1 an 中的ai除去 变成长度为n 1的线性表 a1 a2 ai 1 ai 1 an 这只需将第i 1数据元素到n数据元素依次向前移动一个位置即可 设线性表用一维数组a N 存放 则在长度为n的线性表中删除值为data元素 函数如下 intdelete inta intn intdata inti j k 0 for i 0 i n i if a i data for j i j n 1 j a j a j 1 数据元素依次向前移动 a n 1 0 n k 1 break if k 0 printf Nothiselement return n head an 0 a0 a1 a2 2 线性链表的操作单链表结点一般用结构体说明如下 structnode intdata structnode next 单链表的插入假定已有一个链表的表头为h 其data域的值是由小到大排列的 现插入一个新的结点p0 要求插入后仍能保持由小到大的顺序 考虑 1 链表h若为空 则将p0的next值为NULL 并将h指向p0 2 链表h不是空表 则首先确定p0的插入位置 则分三种情况 p0插在第一个结点之前 将p0的next指向h的第一个结点 然后将h指向p0 p0插在链表中间 若在ai 1和ai之间插入 可将p0的next指向ai ai 1的next指向p0 p0插在链表的末尾 将最后一个结点的next指向p0 而使p0的next置为NULL p2 p1 p0 structnode insert structnode h structnode p0 structnode p1 h p2 if h NULL h p0 p0 next NULL else while p0 data p1 data 单链表的删除在已给定的链表h中 删除data值为m的结点 1 链表h是否指向空表 如果是空表 则报告空表信息 2 若h不为空 一直查到表尾还找不到该结点 则在此链表中无此结点 查找到该结点 若该结点在头部 则h指向该结点的下一个结点 若该结点在中部 则前趋结点的指针指向后趋结点 若该结点在尾部 则前趋结点的指针为NULL p2 p1 structnode del structnode h intm structnode p1 p2 if h NULL printf nThisnull n return h p1 h while p1 data m 实例 单链表的建立 打印和插入 defineNULL0 defineLENsizeof structnode include stdio h structnode intdata structnode next structnode create 建立链表 structnode h NULL p q intx for printf Inputdata scanf d structnode insert structnode h structnode p0 structnode p1 h p2 if h NULL h p0 p0 next NULL else while p0 data p1 data 二 循环链表 1 循环链表的最后一个结点的指针域不为NULL 而是指向头结点 整个链表形成一个环 2 在循环链表中设置一个表头结点 使空表与非空表的运算统一起来 a 非空表 b 空表图2 2 5带表头结点的循环链表 1 插入算法 在头指针为h的循环链表中元素b的结点前插入新元素a structnode inscst structnode h intb inta structnode q p q structnode malloc LEN q data a p h while p next h h p q b a 2 删除算法 在头指针为h的循环链表中删除元素为b的结点delcst structnode h intb structnode p q p h while p next h b p q 三 多项式相加A x 3x14 2x8 1B x 8x14 3x10 10 x6C x A x B x 设pa pb指针 1 若指针相等 则系数相加 c x 中建项 系数为0 不建 2 若pa exp pb exp复抄pa所指项 反之 复抄pb所指项 1 3 14 2 8 1 0 ah 1 8 14 3 10 10 6 bh cof exp ch 1 14 11 3 10 2 8 10 6 1 0 pa pb pc structnode1 addpoly structnode1 ah structnode1 bh structnode1 pa pb pc ch pp intx e ch structnode1 malloc LEN ch exp 1 ch next ch pc ch 建立新表头结点 pa ah next pb bh next while pa exp 1 pb exp 1 if pa exp pb exp x pa cof pb cof e pa exp 系数相加 pa pa next pb pb next 修改指针 elseif pa exp pb exp x pa cof e pa exp 复抄A x pa pa next else x pb cof e pb exp 复抄B x pb pb next if x 0 形成新结点链入C x pp structnode1 malloc LEN pp cof x pp exp e pp next ch pc next pp pc pp return ch 多重链表 每个结点均有两个或两个以上指针的链表 双重链表设两个指针域 一个指向后继结点 另一个指向前趋结点 structnode intdata structnode prio structnode next 图2 2 6带表头结点的双向循环链表 a 插入运算在已由小到大排列的带表头结点的双向循环链表h中 插入一个新的结点p0插入后 要求仍保持由小到大的排列次序 structnode insert2 structnode h structnode p0 structnode p1p1 h next while p0 data p1 data p0 p1 h b 删除操作在已给定的头结点h的双向链表中 删除一个data值为m的结点 structnode data structnode h intm structnode p1 p1 h next while p1 data m h m p1 2 2 2栈栈是限定在一端进行插入与删除的线性表 允许插入和删除的一端称为栈顶 而不允许插入和删除的另一端称为栈底 例如 给定栈 a0 a1 an 1 称a0为栈底元素 an 1为栈顶元素 栈是一种后进先出 LIFO LastInFirstOut 或先进后出 FILO 的线性表 在栈中 元素的插入称为进栈 元素的删除称为出栈 1 顺序存储的栈顺序栈 利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素 同时设指针top指示栈顶元素的当前位置 假设用一维数组s max 表示栈 指针top指向栈顶元素 s 0 为最早进入栈的元素 s top 为最迟进入栈的元素 当top max 1时 为满栈 初始化top 1注 top max为全局变量 1 进栈push ints intx if top max 1 printf Stackoverflow n 上溢 elses top x 2 出栈intpop ints inty 1 if top 1 printf Stackunderflow n 下溢 elsey s top return y 图2 2 8数据元素和栈顶指针之间的对应关系 假设有两个栈 我们让它们共享一数组s m 因为栈底位置是不变动的 所以可将两个栈底分别设在数组空间的两端 然后各自向中间伸展 如下图所示 显然 仅当两个栈顶相遇时才可能发生上溢 由于两个栈之间可以做到互补余缺 使得每个栈实际可利用的最大空间大于m 2 2 链存储的栈当栈的最大容量事先不能估计时 也可采用链式存储结构的栈 称为链栈 一个链栈由它的栈顶指针top唯一确定 如图2 11所示 这里栈空的判别条件是top是否为NULL 而栈满将不会发生 除非计算机的全部可利用空间都被占满 对一个元素多变的栈来说 链式存储结构似乎更适宜 栈链的运算实现也比较简单 3 栈的应用 1 子程序的调用和返回 当多个过程构成嵌套调用时 按照后调用先返回的原则 通过栈来实现 2 表达式求值栈的另一个重要的应用是在编译中用来求表达式的值 任何一个表达式由三部分组成 操作数 运算符和界限符 其中 操作数可以是常量或标识符 表示常量或变量 运算符有算术运算符 关系运算符 逻辑运算符等 在这里 我们只讨论算术运算符 算术运算符的规则 界限运算符有左 右括号 左括号运算级最高 右括号运算级最低 及表达式结束符 号的运算级最低 要正确解释表达式 必须先了解算术四则运算的规则 即 先乘除 后加减 从左计算到右 先括号内 后括号外为实现算符优先法必须使用两个工作栈 一个数栈 opnd 一个运算符栈 optr 系统自左至右扫描表达式 遇到操作数 则送入数栈 遇到运算符 则把它的优先度与当前运算符栈顶运算符的优先度比较 若大于栈顶优先符的优先度 则入栈 否则退栈 并以这个退栈运算符和从数栈顶上退出的两个操作数形成一条机器指令 这样 一边形成相应的机器指令 直到扫描到结束符 所有的栈空为止 计算表达式运算符 X A B C D E F G优先数 43322 A B C D OptrOpnd a 进栈后 A B T1 b T1 C D A T2 c T2 B T1 A T2 d 弹出左括号 T3 e T3 A T2 T3 E F G f 进栈后 T3 E T4 g T4 F G T3 T5 h T5 E T4 T6 i T6 T3 T5 求表达式3 7 2 的值 optropnd输入字符主要操作1 3 7 2 push opnd 3 2 3 7 2 push optr 3 3 7 2 push optr 4 37 2 push opnd 7 5 37 2 push optr 6 372 push opnd 2 7 372 operate 7 2 8 35 pop optr 一对 出栈9 35 operate 3 5 10 15 return 2 2 3队列队列 Queue 也是操作受限的线性表 队列是一种先进先出 FIFO 的线性表 a1 a2 an 允许在表的一端进行插入 而在表的另一端进行删除 允许插入的一端叫做队尾 rear 允许删除的一端则称队头 front 若限制插入和删除能在表的两端进行 称此队列为 双向队 若限制插入在表的一端进行 而限制删除在表的另一端进行 称此队列为 单向队 允许插入的一端称为队尾 允许删除的一端称为队首 队列是一种先进先出 FIFO 的线性表 队列的基本运算有以下四种 获得队列的队首结点之值 gethead q x 读取q队列的队头元素于变量x中 队列不变 队列q中插入一个结点 进队 add q x 在队尾插入一个元素x 队列q中删除一个结点 出队 del q 删除队头元素 判队列q是否为空 empty q 1 顺序存储的队设置二个指针front 队头 和rear 队尾 存在 假溢出 现象 解决方法 采用循环队列 反转技术 假设存储空间为数组q m 把队列数组的元素q 0 和q m 1 连接起来 形成一个环形的表 初始值front rear 0 1 进队rear rear 1 m q rear x 出队front front 1 m y q front 0 1 m 1 front rear a1 a2 a3 a4 2 环形队列的队空和队满都有rear front专门设立一个标志符少用一个元素空间 用 rear 1 m front作为队满的判别条件 循环队列中入队和出队操作的具体算法intfront rear m 全局变量 addque intq intx 进队算法 rear rear 1 m if rear front printf Queenoverflow n elseq rear x delque intq 出队算法 inty 1 if front rear printf Queenundelflow n else front front 1 m y q front return y 2 链接存储的队采用链式存储结构的队列称为链队列 一个链队列需要队头和队尾的两个指针才能唯一确定 b 链式存储的队列 1 进队算法注 front rear是全局变量add intx structnode q q structnode malloc LEN q data x q next NULL if front NULL front q rear q else rear next q rear q 2 出队算法注 front rear是全局变量del structnode q inty 1 if front NULL printf Queennderflow n else q front y q data front q next free q return y 3 队列的应用分时操作系统中 多个用户程序排成队列 分时地循环使用CPU和主存 缓冲技术 系统为了解决高速的主机和低速的输入输出设备之间的矛盾 在主存中开辟缓冲区 主机将要输入或输出的信息先送至缓冲区 然后输入或输出设备从缓冲区中按队列的先进先出原则依次取出数据 在这种情况下 主机不必等待外部设备操作完就可以继续做其它的工作 通常 缓冲区的结构为一个循环队列 2 2 4串串 String 也是一种特殊的线性表 即当线性表中的元素为字符时的情形 串定义 由零个或多个字符组成的有限序列 称为串 一般记为 s a1a2 an n 0 线性表上的操作通常是对其中的单个元素进行的 如插入一个元素 删除一个元素等 对于串 经常要对其连续的字符组进行操作 如从正文中取一个单词 替换一个单词等 串的基本运算有 求串s的长度的函数len s 求串s的第m位置开始且长度为n的子串的函数sub s m n 求子串t在主串s中的位置的函数index s t 串v的值替换所有在串s中出现的子串t的值的函数rep s t v 及将串s2的值紧接着放在串s1的值的末尾 联接成一个新串的函数concat s1 s2 等 1 串的顺序存储用一组地址连续的存储单元来存放字符串的值 为了唯一确定串 需要设置两个变量 一个是指向串第一个字符位置的指针sp 一个是指示串长度的整型变量sl 可以将串的长度和串值一起存于内存 也可以用一个特定字符作为串结束标志和串值一起存放 这样就不需要设置sl了 C语言就是用NULL 0 作为串结束标志的 不同的字符所占据的内存空间都是一个字节computer 0ll 1l 2 l 8图2 2 14顺序存储r的串 2 串的链式存储链表存储串值时 由于串中每个数据元素是一个字符 因而存在一个结点大小的选择问题 即结点中是存放一个字符 还是存放多个字符 结点大小的选择直接影响对串和处理效率 结点越小 串处理越方便 但所占内存也随之扩大 反之 结点越大 串处理越不方便 但可以节省内存 串的基本运算一 求串的长度main longle longlen char chars 30 scanf s s le len s printf len s d n le longlen chars longi 0 while s i 0 i returni 二 求子串sub s m n 求串s的第m位置开始且长度为n的子串 三 求子串t在主串s中的位置index s t 从主串S的第一个字符起和模式t的另一个字符比较 若相等 则继续逐个比较后继字符 如果全部相等 则匹配成功 返回子串的位置 否则从S的第二个字符起重新开始新的比较 直至某一步匹配成功或S结束 无法再进行比较为止 此时返回 1作为匹配失败的标志 index chars chart inti 0 j 0 while s i 0 四 字符串置换rep s t v 以串v的值替换所有在串s中出现的子串t的值 五 字符串连接char concat char s1 char s2 char p p s1 while p p while p s2 return s1 六 字符串比较intcmp chars1 chars2 inti 0 r while s1 i s2 i 以下是C语言提供的一些有关字符串的库函数 unsignedstrlen char str 字符串长度函数 char strcat char str1 char str2 连接函数 char strcpy char str1 char str2 拷贝函数 2 3树形结构树形结构是结点之间有分支 层次关系的结构 是一种重要的非线性结构 树型结构在客观世界中广泛存在 如人类的族谱和各种社会组织机构都可以用 树 来表示 2 3 1树的定义及其基本概念树可以定义如下 1 有且仅有一个称为根的结点 2 除根结点之外的结点可分为m m 0 个互不相交的有限集T1 T2 Tm 其中每一个集合本身又是一棵树 并且称为根的子树 这是一个递归的定义 即在树的定义中又用到树本身这个术语 树的基本概念树的根结点 是树中一个特定的结点 它是没有前趋的结点 结点的度 树中每个结点拥有的子树的数目 度为0的结点为终端结点或叶子 度