第1章数据结构与算法1.1算法1算法的概念：是指解题方案的准确而完整的描述2算法的基本特征：可行性、确定性、有穷性(有限的时间)、拥有足够的情报3算法的复杂度：时间复杂度和空间复杂度(1)时间复杂度：算法所需要的计算工作量（算法所执行的基本运算次数）(2)空间复杂度：执行这个算法所需要的内存空间1.2数据结构的基本概念1数据结构研究的三个问题(1)逻辑结构：指反应数据元素之间逻辑关系的数据结构(2)存储结构（物理结构）：数据的逻辑结构在计算机存储空间中的存放形式。(3)对各种数据结构进行的运算2数据结构定义：是指带有结构的数据元素的集合。所谓结构就是指数据元素之间的前后件关系。在数据结构中，没有前件的结点称为根结点，没有后件的结点为终端结点（也叫叶子结点）。3空的数据结构：一个元素都没有的数据结构。4数据结构的种类：线性结构与非线性结构。 线性结构：有且只有一个根结点，每一个结点最多有一个前件，也最多有一个后件。 非线性结构：如果一个数据结构不是线性结构，则称之为非线性结构。1.3线性表及其顺序存储1线性表是最简单、最常用的一种线性结构。2非空线性表的结构特征：(1)有且只有一个根结点，无前件(2)有且只有一个终端（叶子）结点，无后件 (3)除根结点与终端结点外，其他所有结点有且只有一个前件，也有且只有一个后件。在线性表中结点的个数n称为线性表的长度，当n=0时，称为空表。3线性表顺序存储结构的基本特点：(1)所有元素所占的存储空间是连续的(2)各元素在存储空间中是按逻辑顺序依次存放的4在长度为n的顺序存储的线性表中，当在任何位置上插入或删除一个元素概率都相等时，插入或删除一个元素所需移动元素的平均个数是为n/2。1.4栈和队列1栈：限定在一端进行插入与删除的线性表。2栈的结构特点： 先进后出 或 后进先出3栈的基本运算：入栈运算、退栈运算、读栈顶元素(1)上溢：当栈空间已满，不能再入栈时，称为“上溢”。(2)下溢：当栈空间已空，不能再出栈时，称为“下溢”。4队列：允许在一端进行插入、而在另一端进行删除的线性表5队列的结构特点： 先进先出 或 后进后出6循环队列：将队列存储空间的最后一个位置绕到第一个位置，形成逻辑上的环状空间。7循环队列中元素个数：(分两种情况) (1)队尾指针队头指针： 元素个数 = 队尾指针 - 队头指针 (2)队尾指针=1）个结点(2)深度为m的二叉树最多有2m-1个结点(3)度为0的结点（叶子结点）是比度为2的结点多一个(4)具有n个结点的二叉树，其深度至少为log2n+1 当完全二叉树总结点n为偶数时，叶子节点的个数为：n/2 当完全二叉树总结点n为奇数时，叶子节点的个数为：(n+1)/25二叉树的遍历：前序遍历（根-左-右）；中序遍历（左-根-右）；后序遍历（左-右-根）1.7查找技术1顺序查找： 最坏情况下，需比较n次。2二分法查找：最坏情况下，需比较loag2n次。1.8排序技术1交换类排序：（1）冒泡排序法：n(n-1)/2（最坏情况下）（2）快速排序法：n(n-1)/2（最坏情况下） O(nlog2n)（平均情况下）2插入类排序：（1）简单插入排序法：n(n-1)/2（最坏情况下） （2）希尔排序法：O(n1. 5)（最坏情况下）3选择类排序：（1）简单选择法：n(n-1)/2（最坏情况下）（2）堆排序法： O(nlog2n) （最坏情况下）第2章程序设计基础 1程序设计风格：清晰第一，效率第二2注释一般分为：序言性注释和功能性注释3结构化程序设计的原则：自顶向下，逐步求精，模块化，限制使用 goto 语句4结构化程序的基本结构：顺序结构、选择结构、重复结构（循环结构）5对象：客观世界中的任何实体。类是具有共同属性、共同方法的对象的集合。对象是类的一个实例。类是对象的抽象。6对象特点：标识唯一性、分类性、多态性、封装性、模块独立性好8消息：是对象与对象之间传递的信息。9在面向对象方法中，类之间共享属性和操作的机制称为：继承10继承性的优点：相似的对象可以共享程序的代码和数据结构,从而大大减少了程序中的冗余信息,提高软件的可重用性,便于软件修改维护第3章软件工程基础3.1 软件工程的基本概念1软件：包括程序、数据及相关文档的完整集合。2软件按功能分为：应用软件、系统软件、支撑软件（或工具软件）。3软件危机：是泛指在计算机软件的开发和维护过程中所遇到的一系列严重问题。4软件工程概念的出现源自软件危机5软件工程3要素：方法，工具，过程（支持软件开发的各个环节的控制、管理）。6软件生命周期：将软件产品从提出、实现、使用维护到停止使用退役的过程。7软件工程的理论和技术性研究：软件开发技术和软件工程管理。8软件工程原则：抽象、信息隐蔽、模块化、局部化、确定性、一致性、完备性、可验证性3.2 结构化分析方法1需求分析的任务：发现需求、求精、建模和定义需求的过程。需求分析的目的是确定系统的功能。2结构化需求分析的常用工具(1)数据流图（DFD）：加工（转换）数据流存储文件（数据源）源，潭(2)数据字典（DD）：结构化需求分析方法的核心。3、软件的需求分析阶段的工作，可以概括为四个方面：需求获取、需求分析、编写需求规格说明书和需求评审。4软件需求规格说明书：是需求分析阶段的最后成果，是软件开发中的重要文档之一。5软件需求规格说明书的作用： (1)便于用户、开发人员进行理解和交流 (2)反映出用户问题的结构，可以作为软件开发工作的基础和依据。 (3)作为确认测试和验收的依据。6软件需求规格说明书的特点：正确性、无歧义性（最重要）、完整性、可验证性、一致性、可理解性、可修改性、可追踪性3.3 结构化设计方法1软件设计从技术观点看，软件设计包括软件结构设计、数据设计、接口设计、过程设计。 (1)结构设计：定义软件系统各主要部件之间的关系。 (2)数据设计：将分析时创建的模型转化为数据结构的定义。 (3)接口设计：描述软件内部、软件和协作系统之间以及软件与人之间如何通信。 (4)过程设计：把系统结构部件转换成软件的过程性描述。2软件设计从工程管理角度看，软件设计分两步完成：概要设计和详细设计3软件设计的基本原理抽象、模块化 、信息隐蔽、模块独立性4衡量软件独立性依据：耦合性（是模块间互相连接的紧密程度的度量）内聚性（是一个模块内部各个元素间彼此结合的紧密程度的度量）5耦合性包括：内容耦合、公共耦合、外部耦合、控制耦合、标记耦合、数据耦合、非直接耦合。6优秀的软件设计应做到“高内聚，低耦合”。7与结构化需求分析方法对应的是结构化设计方法。8常用的软件结构设计工具是结构图（程序结构图）。其中箭头表示模块间的调用关系。9典型的数据流类型有两种：变换型和事务型。10结构化详细设计工具：(1)程序流程图：表示控制流；矩形表示加工步骤；菱形表示逻辑条件。 (2)N-S图：为了避免流程图在描述程序逻辑时的随意性和灵活性，提出了用方框图来代替传统的程序流程图，通常也称为N-S图。3.4软件测试1软件测试的目的：检验它是否满足规定的需求可是弄清预期结果与实际结果之间的差别，是为了发现错误而执行程序的过程。2测试要以查找错误为中心，而不是为了演示软件的正确功能。3软件测试的准则：(1)所有测试都应追溯到需求(2)严格执行测试计划，排除测试的随意性(3)充分注意测试中的群集现象:为了提高测试效率，测试人员应该集中对付那些错误群集的程序。(4)程序员应避免检查自己的程序(5)穷举测试不可能：测试只能证明程序中有错误，不能证明程序中没有错误(6)妥善保存测试计划、测试用例、出错统计和最终分析报告，为维护提供方便4软件测试的方法： (1)按是否需要执行被测软件划分：静态测试：包括代码检查、静态结构分析、代码质量度量等。动态测试：是为了发现错误而执行程序的过程。测试用例由测试输入数据和之与对应的预期输出结果两部分组成。 (2)按功能划分：白盒测试：保证所侧模块中每一独立路径至少执行一次（穷举路径测试） 黑盒测试：完全不考虑程序内部的逻辑结构和内部特性，只依据程序的需求和功能规格说明，检查程序的功能是否符合它的功能说明。黑盒测试方法包括：等价类划分法、边界值分析法、错误推测法、因果图等。5软件测试的实施：软件测试是保证软件质量的重要手段，目的是使软件测试工作系统化。 软件测试的过程： (1) 单元测试：目的是发现各模块内部可能存在的各种错误。 (2) 集成测试：是测试和组装软件的过程。(3) 确认测试：验证软件的功能和性能及其他特性是否满足了需求规格说明中确定的各种需求。(4) 系统测试：6程序的调试的任务：诊断和改正程序中的错误（主要在开发阶段）。软件测试是尽可能多地发现软件中的错误。第4章数据库设计基础4.1数据库系统的基本概念1数据库技术的基本目标是解决数据共享问题。2数据：是描述事物的符号记录。3数据库(DB)：是结构化的相关数据集合，是多种应用数据的集成，并可被多个应用程序共享。4数据库管理系统(DBMS)：是一种系统软件，是数据库系统的核心，位于用户和操作系统（OS）之间。5数据语言： (1)数据定义语言（DDL）：负责数据的模式定义与数据的物理存取构建。(2)数据操纵语言（DML）：负责数据的操作，包括查询及增、删、改等操作。(3)数据控制语言（DCL）：负责数据完整性、安全性的定义与检查以及并发控制、故障恢复等功能。6数据库管理员（DBA）：主要工作包括数据库设计、数据库维护、改善系统性能，提高系统效率。7数据库系统（DBS）由五部分组成：数据库、数据库管理系统、数据库管理员、硬件平台、软件平台。 数据库系统包括数据库和数据库管理系统。 （即DBS包括DB和DBMS）8数据管理发展三个阶段：人工管理阶段、文件系统阶段、数据库系统阶段。 在数据管理技术的发展过程中，可实现数据共享的是：数据库系统系统