第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.5线性链表
1．线性表的链式存储结构称为线性链表。
2．在链式存储结构中，每个数据结点由两部分组成：一部分存放数据元素的值，称为数据域；另一部分存放下一结点的存储地址，称为指针域。
3．在链式存储结构中，存储数据结构的存储空间可以不连续，各数据结点的存储顺序与数据元素的逻辑关系可以不一致，而数据元素之间的逻辑关系是由指针域来确定的。
4．线性链表的优点：在线性链表中插入或删除一个元素时，不需要移动元素的位置，只需改变指针的指向就行了。
5．循环链表的优点：只要指出表中任何一个结点的位置，就可以从它出发访问到表中其他所有的结点，而线性单链表做不到这一点。
1.6树与二叉树
1．树是一种简单的非线性结构。
2．树的基本术语：父结点；根结点；子结点；叶子结点；结点的度；树的度；树的深度
根结点在第1层。叶子结点没有子树。
3．二叉树：只有一个根结点，每一个结点最多有2颗子树，且分别叫做左子树和右子树。
4．二叉树的基本性质：
(1)在二叉树的第k层上，最多有2k-1（k>=1）个结点
(2)深度为m的二叉树最多有2m-1个结点
(3)度为0的结点（叶子结点）是比度为2的结点多一个
(4)具有n个结点的二叉树，其深度至少为[log2n]+1
当完全二叉树总结点n为偶数时，叶子节点的个数为：n/2
当完全二叉树总结点n为奇数时，叶子节点的个数为：(n+1)/2
5．二叉树的遍历：前序遍历（根-左-右）；中序遍历（左-根-右）；后序遍历（左-右-根）
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 结构化设计方法
