|
第一章 数据结构与算法 §1.1 算法 1. 算法的定义：是指解题方案的准确而完整的描述。（算法不等于程序，程序的设计不可能优于算法的设计） 2. 算法的基本特征：可行性、确定性、有穷性、足够的情报。 3. 算法的基本要素： ① 对数据对象的运算和操作： 算术运算、逻辑运算、关系运算、数据传输。 ② 算法的控制结构： a.算法中各操作之间的执行顺序； b.描述算法的工具通常有传统流程图、N-S结构化流程图、算法描述语言等； c.一个算法一般可以用顺序、选择（分支）、循环（重复）三种基本结构组合而成。 4. 算法的时间和空间复杂度： ① 时间复杂度：是指执行算法所需要的计算工作量，可以用算法所执行的基本运算次数度量。 ② 空间复杂度：是指执行算法所需要的内存空间。包括算法程序、输入的初始数据以及算法执行过程中需要的额外空间。 ③ 算法的时间复杂度和算法的空间复杂度相互独立。 §1.2 数据结构的基本概念 1. 数据：需要处理的数据元素的集合，一般来说，这些数据元素，具有某个共同的特征。 a.数据元素是数据的基本单位，即数据集合中的个体。 b.有时一个数据元素可有若干数据项组成。数据项是数据的最小单位。 2. 结构：是集合中各个数据元素之间存在的某种关系（或联系）。 3. 数据结构：是指相互有关联的数据元素的集合。 4. 数据结构的分类： ① 逻辑结构：线性结构（线性表、栈、队列）；非线性结构（树、图）。 ② 存储结构：顺序存储；链式存储。 ③ 运算：插入、删除、查找、排序。 5. 逻辑结构：反应数据元素间的逻辑关系（即前后件关系）的数据结构。 ① 线性结构（线性表）：（举例：春→夏→秋→冬） a.有且只有一个根节点，它无前件； b.每一个节点最多有一个前件，也最多有一个后件。 ② 非线性结构： a.不满足以上两个条件的数据结构就称为非线性结构； b.非线性结构主要是指树形结构和网状结构。 6. 存储结构：又称为数据的物理结构，是数据的逻辑结构在计算机存储空间中的存放方式 ① 顺序存储结构：主要用于线性的数据结构，它把逻辑上相邻的数据元素存储在物理上相邻的存储单元里。 ② 链式存储结构：每一个结点至少包含一个指针域，用指针的指向来体现数据元素之间在逻辑上的联系。  a.一种逻辑结构可以有多种存储结构 b.不同的存储结构其数据处理的效率不同 §1.3 线性表及其顺序存储结构 1. 线性表： 线性表是n（n≥0）个数据元素构成的有限序列，表中除第一个元素外的每一个元素，有且只有一个前件，除最后一个元素外，有且只有一个后件。 举例：英文字母表、地理学中的四向、表格 2. 线性表的顺序存储结构： ① 通常，线性表可以采用顺序存储和链式存储，但一般使用顺序存储结构。线性表的顺序存储又叫做顺序表（顺序分配）。 ② 特点： a.线性表中所有元素所占的存储空间是连续的； b.线性表中数据元素在存储空间中是按逻辑顺序依次存放的； c.可以随机访问数据元素； d.做插入、删除时需移动大量元素，因此线性表不便于插入和删除元素。 §1.4 栈和队列 1. 栈：栈是限定在一端进行插入和删除的线性表。 特点：★ ① 栈是只能在栈顶进行插入和删除； ② 栈的修改原则是“先进后出”或“后进先出”； ③ 栈底指针boottom，栈顶指针top，入栈，栈满，出栈； ④ 栈底指针不变，栈中元素随栈顶指针的变化而动态变化； ⑤ 栈具有记忆功能； ⑥ 栈支持子程序调用。 2. 队列：队列是指允许在一端进行插入，而在另一端进行删除的线性表。 特点： ① 队列只允许在队尾进行插入，而在队头进行删除； ② 队列的修改原则是“先进先出”或“后进后出”； ③ 队头指针front，队尾指针rear，入队，出队； ④ 队列中元素随队头指针和队尾指针的变化而动态变化。 3. 循环队列：是讲队列存储空间的最后一个位置绕道第一个位置，形成逻辑上的环状空间 rear＞front：s=rear-front rear＜front：s=容量+rear-front rear=front：s=1或者s=0 §1.5 线性链表 1. 线性链表： ① 线性表可以采用顺序存储和链式存储。线性表的顺序存储叫做顺序表，线性表的链式存储结构叫做线性链表。 ② 特点： a.各数据结点的存储空间可以不连续； b.各数据元素的存储顺序和逻辑循序可以不一致； c.线性表的链式存储所占存储空间大于顺序存储结构； d.查找结点时链式储存要比顺序存储慢； e.链式存储插入删除元素比顺序存储灵活。 ③ 线性链表的操作：在线性链表中进行插入与删除，不需要移动链表中的元素。 2. 线性表： ① 线性表顺序存储结构； ② 线性表链式存储结构（还包括双向链表、循环链表）。★ §1.6 树与二叉树（★） 1. 树： ① 是n（n>0）个元素的有限集合。它有且仅有一个称为根的元素；其余元素是互不相交的子树。 ② 常用术语： a.父结点、子结点； b.根结点、叶子结点； c.结点的度、树的度（所有结点中最大的度称为树的度）； d.树的深度； e.子树（以某个结点的一个子结点为根构成的树称为该结点的一颗子树）。 2. 二叉树： ① 是一个有限的结点集合，该集合或者为空，或者有一个根结点及其两颗互不相交的左右二叉子树所组成。 ② 特点： a.非空二叉树只有一个根结点； b.每一个结点最多有两颗子树，且分别称为该结点的左子树与右子树。  ③ 五种基本形态： a.空二叉树； b.只有一个结点的二叉树； c.只有左子树的二叉树； d.只有右子树的二叉树； e.左右子树双全的二叉树。  3. 特殊二叉树： ① 满二叉树：除最后一层外，每一层上的结点数均达到最大值。 ② 完全二叉树：除最后一层外，每一层上的结点数均达到最大值，在最后一层上只缺右边的若干结点。  满二叉树是完全二叉树，但是完全二叉树不一定是满二叉树。 4. 二叉树特点：★ 非空二叉树只有一个根结点，每个结点最多有两颗子树，分别称为左子树和右子树 ① 在二叉树的第K层上，最多有2k-1个结点； ② 深度为m的二叉树最多有2m-1个结点； ③ 度为0的结点（叶子结点）总比度为2的结点多一个； ④ 有n个结点的二叉树深度至少为[log2n]+1。 5. 二叉树的遍历： ① 前序遍历：ABDGECF 访问根结点、前序遍历左子树、前序遍历右子树（根左右） ② 中序遍历：DGBEAFC 中序遍历左子树、访问根结点、中序遍历右子树（左根右） ③ 后序遍历：GDEBFCA 后序遍历左子树、后序遍历右子树、访问根结点（左右根）  §1.7 查找技术 1. 顺序查找：对于长度为n的线性表，平均要进行n/2次比较，在最坏的情况下进行n次比较。 顺序查找适用于无序表或链式线性表（不管无序还是有序）（适用于所有的线性表） 2. 二分查找：适用于顺序存储的有序表，对长度为n的线性表，在最坏的情况下进行次比较。 注意：即使是有序线性表，如果采用链式存储结构，也只能用顺序查找。 §1.8 排序技术 1. 排序：  2. 快速排序： 基本思想：在要排序的序列中找一个数作为基准数（通常为第一个数）； 通过交换将这个序列中所有比基准数大的数放在右边，比基准数小的数放在左边； 以基准数为分割线分为两个子表，对两个子表重复上述步骤。 第一章总结：  第二章 程序设计基础 §2.1程序设计方法与风格 1. 良好的程序设计风格：清晰第一，效率第二 2. 如何形成良好的程序设计风格： ① 源程序内部文档化； ② 数据说明； ③ 语句的结构； ④ 输入和输出 3. 源程序内部文档化： ① 选择标识符的名字； ② 注释（序言性和功能性注释）：序言性注释一般位于模块的首部，用于说明模块的相关信息（标题、功能的说明、主要的算法、模块接口、开发历史、程序设计者、复审者和复审日期）；功能性注释位于源程序模块内部。 ③ 程序的视觉组织。 §2.2结构化程序设计 1. 结构化程序设计原则：（★） ① 自顶向下：先考虑总体，后考虑细节；先考虑全局目标，后考虑局部目标 ② 逐步求精：对复杂问题，先设计一个目标作为过渡，然后逐步细化 ③ 模块化：把程序要解决的总目标分解为一个一个的模块 ④ 限用goto：限制使用goto语句，程序的质量与goto语句数量成反比 2. 结构化程序的基本结构： 结构化程序设计常采用顺序、选择（分支）和循环三种基本结构 3. 程序设计语言的基本成分：数据成分、运算成分、控制成分和传输成分。 §2.3面向对象的程序设计 1. 几个术语： ① 对象：在现实世界中，每个实体都是对象（例如大学生、汽车、电视机、空调等）； ② 属性：用于描述对象的状态； ③ 方法：用于描述对象的行为； ④ 类：类是一组具有相同属性和相同操作的对象的集合 （基于同一类产生的对象可以分别设置各自的属性） 2. 对象的基本特点： ① 标识唯一性：对象可由内在本质来区分。而不是通过描述来区分。 ② 分类性：可以将具有相同属性和操作的对象抽象成类。 ③ 多态性：同一操作可以是不同对象的行为。 ④ 封装性：从外面看不到对象的内部，只能看到对象的外部特征。 ⑤ 模块独立性好：对象是面向对象的软件的基本模块，内聚性强。 3. 继承：使用已有的类建立新类的定义技术。能直接获得已有的性质，不必重复定义他们。 4. 消息：是一个实例与另一个实例之间传递的信息。对象间的通信靠消息传递。 组成：①接收消息的对象的名称；②消息标识符，也称消息名；③零个或多个参数。 5. 多态性：是指同样的消息被不同的对象接受时可导致完全不同的行动的现象。 第三章 软件工程基础 §3.1软件工程基本概念 1. 软件：是由程序、数据及其相关文档构成的集合。 2. 软件的分类： ① 系统软件：操作系统、编译程序、汇编程序、网络软件、数据库管理系统； ② 应用软件：事务处理软件、工程与科学计算软件、实时处理软件、人工智能软件； ③ 支撑软件（工具软件）：需求分析工具、编译工具软件、测试工具软件、维护工具软件。 3. 软件危机：需求增长、开发难控、质量难保、难以维护、提高成本、生产率低。 4. 软件工程： ① 定义：应用于计算机软件的定义、开发和维护的一整套方法、工具、文档、实践标准和工序。 ② 其目的是提高软件生产率、提高软件质量、降低软件成本。 ③ 其核心思想是把软件当作一个工程产品来处理。 5. 软件工程三要素： ① 方法：是完成软件工程项目的技术手段； ② 工具：支持软件的开发、管理和文档生成； ③ 过程：支持软件发开的各环节的控制和管理。 6. 软件生命周期： ① 定义：将软件产品产品能够提出、实现、使用维护到停止使用退役的过程称为软件生命周期。 ② 分为软件定义、软件开发及软件运行维护3个时期。维护是持续时间最长，花费代价最大的一个时期。 ③ 软件工程学的一个目的就是提高软件的可维护性，降低维护代价。 7. 3个时期共有8个阶段： ① 软件定义：问题定义可行性研究、需求分析； ② 软件开发：概要设计、详细设计、实现、测试； ③ 软件运行维护：使用、维护。 8. 需求分析：（★） ① 确定系统的逻辑模型。参加人员有用户、项目负责人和系统分析员。 ② 其工作：需求获取、需求分析、编写需求规格说明书、需求评审。 ③ 产生文档：为需求规格说明书。 ④ 需求规格说明书的作用： a.便于用户、开发人员进行理解交流； b.反映用户问题的结构，可以作为软件开发工作的继承和依据； c.作为确认测试和验收的依据。 9. 需求规格说明书（SRS）：需求分析阶段产生的主要文档是“软件需求规格说明书”。 特点： ① 正确性：体现待开发系统的真是要求； ② 无歧义性：对每个需求只有一种解释； ③ 完整性：包括全部有意义的需求； ④ 可验证性：每个需求都是可验证的； ⑤ 一致性：各个需求的描述不矛盾； ⑥ 可理解性：需求说明书必须简明易懂； ⑦ 可修改性：结构风格在改变时，是易于实现的； ⑧ 可追踪性：每个需求的来源和流向是清晰的。 §3.2结构化分析方法 1. 结构化分析方法： ① 需求分析方法有：结构化需求分析方法和面向对象的需求方法 ② 结构化分析方法：使用数据流图（DFD）、数据字典（DD）、判定表和判定树等工具，来建立系统的逻辑模型。 2. 数据流图（DFD）： ① 数据流图的图形元素 〇 加工：输入数据经加工变换产生输出； → 数据流：沿箭头方向传递数据的通道； ＝ 存储文件（数据源）：存放各种数据的文件； □ 源（潭）：系统和环境的接口。  ② 数据字典（DD）是对数据流图中所有元素定义的集合，是结构化分析的核心。 §3.3结构化设计方法 1. 软件分析是确定系统的逻辑模型，软件设计是确定系统的物理模型。 2. 软件设计的划分： ① 从工程管理角度划分：概要设计、详细设计。 ② 按技术观点划分：结构设计、数据设计、接口设计、过程设计。 3. 软件设计基本原理： ① 抽象：在软件设计中，可以定出多个抽象级别，抽象层次从概要设计到详细设计逐步降低。 ② 模块化：把一个待开发的软件分解成若干小的简单的部分，自顶向下逐层把软件换分成若干模块。 ③ 信息隐蔽：一个模块内的信息，对于不需要这些信息的其他模块来说不能访问。 ④ 模块独立性：每个模块只完成独立的子功能，并且与其他模块的联系少且接口简单。模块的独立程度是评价设计好坏的重要度量标准。（高内聚，低耦合） 4. 软件模块独立性： ① 内聚性：指一个模块内部各个元素件彼此结合的紧密程度（高内聚）。 ② 耦合性：指模块间相互连接的紧密程度（低耦合）。非直接耦合、数据耦合、标记耦合、控制耦合、外部耦合、公共耦合、内容耦合。（★） 5. 概要设计： ① 概要设计的任务： a.设计软件系统结构； b.数据结构及数据库设计； c.编写概要设计文档； d.概要设计文档评审。 ② 概要设计的工具是程序结构图（SC）。 6. 程序结构图（SC）：   7. 详细设计： ① 详细设计的任务：确立每个模块的实现算法和局部数据结构，用适当方法标识算法和数据结构的细节。 ② 详细设计的常用工具： a.图形工具：程序流程图、N-S图、PAD、HIPO b.表格工具：判定表 c.语言工具：PDL（伪码） 8. 程序流程图：基本图符： ① 控制流：表示为→或↓ ② 加工步骤：表示为□ ③ 逻辑条件：表示为◇ §3.4软件测试 1. 软件测试： ① 软件测试的目的是发现程序中的错误。 ② 软件测试的准则： a.所有测试都应追溯到用户需求； b.在测试之前制定测试计划，并严格执行； c.充分注意测试中的群集现象； d.避免由程序的编写者测试自己的程序； e.不可能进行穷举测试； f.妥善保存测试分析报告，为维护提供方便。 2. 静态测试和动态测试： ① 静态测试：不实际运行软件，通过人发挥思维优势发现程序的错误。 ② 动态测试：基于计算机的测试，是为了发现错误而执行程序的过程。 3. 白盒测试和黑盒测试： ① 白盒测试：把测试对象看作一个打开的盒子，利用程序内部的逻辑结构，对程序所有逻辑路径进行测试。（针对程序的内部逻辑结构） a.逻辑覆盖测试； b.基本路径测试。 ② 黑盒测试：完全不考虑程序内部的逻辑结构，只检查程序是否能接收输入数据而产生正确的输出信息。（针对程序的外部功能） a.等价类划分法； b.边界值分析法； c.错误推测法。 4. 软件测试步骤：（顺序不可换） ① 单元测试：是对软件设计的最小单位——模块进行测试，目的是发现各模块内部的错误。 ② 集成测试：是把模块按照设计要求组装起来的同时进行测试，目的是发现与接口有关的错误。 ③ 确认测试：是验证软件功能和性能是否满足各种要求，以及软件配置是否完全、正确。 ④ 系统测试：是将软件作为一个元素，与计算机系统其他元素组合在一起，进行集成测试。 §3.5程序的调试 1. 程序调试： ① 对程序进行了成功的测试之后将进入程序调试，通常称为Debug（排错），主要在开发阶段进行。 ② 程序调试的主要任务是诊断和改正程序的错误。 ③ 基本步骤： a.错误定位； b．修改设计和代码，以排除错误； c.进行回归测试，防止引进新的错误。 ④ 软件调试方法：强行排除法、回溯法、原因排除法。 第三章总结：  第四章 数据库设计基础 §4.1数据库系统的基本概念 1. 数据（data）：描述事物的符号纪录称为数据。 ① 实际上就是描述事物的符号纪录； ② 软件中的数据一定是有结构的，有型和值两个概念。 2. 数据库（DB）：是指长期存储在计算机内的，有组织的，可共享的数据集合。 数据库中的数据具有两大特点：“集成”“共享”。（★） 3. 数据库管理系统（DBMS）：数据库管理系统是数据库系统的核心。（系统软件） 语言： ① 数据定义语言DDL： a.数据模式定义； b.数据存取的物理构建。 ② 数据操纵语言DML： a.数据操纵，包括查询与增、删、改等操作。 ③ 数据控制语言DCL： a.数据的安全性的定义域检查； b.并发控制与故障恢复； c.数据的完整性。 4. 数据库管理员（DBA）：主要工作： ① 数据库设计； ② 数据库维护； ③ 改善系统性能，提高系统效率。 5. 数据库系统（DBS）：组成： ① 数据库（数据）——集成，共享。 ② 数据库管理系统DBMS（软件）——定义，构建，操纵，检查，控制，服务。DDL,DML,DCL. ③ 数据库管理员DBA（人员）——设计，维护，改善性能，提高效率。 ④ 软件平台——操作系统，开发工具，接口软件。 ⑤ 硬件平台——计算机，网络。 6. 数据库应用系统（DBAS）： 数据库应用系统包括：数据库系统、应用软件以及应用界面。 7. 数据管理三个阶段：人工管理、文件系统、数据库系统。 数据库技术的根本目标是：解决数据共享问题。 8. 数据库系统特点：集成性，高共享低冗余，独立性，统一管理控制。 9. 三级模式和两级映射： 两级映射保证了数据库中数据具有较高的逻辑独立性和物理独立性。 §4.2数据模型 1. 数据模型： ① 三要素：数据结构、数据操作和数据约束 ② 分类：按不同的应用层次分为： a.概念数据模型（概念模型）：E-R模型 b.逻辑数据模型（数据模型）：层次模型、网状模型、关系模型、面向对象模型 c.物理数据模型（物理模型） 2. E-R模型：（实体联系模型） 联系：一对一，一对多（学生与宿舍），多对多（学生与课程） 3. 数据模型分类： ① 层次模型：树； ② 网状模型：无向图； ③ 关系模型：二维表。 4. 关系模型：采用二维表来表示，简称表，每一个二维表称为一个关系。 ① 属性：二维表中的一列称为属性； ② 元祖：二维表中的一行称为元祖。（分量不可再分） ③ 关系操纵：查询、增加、删除和修改。 ④ 关系中的数据约束： a.实体完整性约束； b.参照完整性约束； c.束和用户定义的完整性约束。 §4.3关系代数 1. 关系代数： ① 关系模型的基本操作：插入、删除、修改、查询。 查询运算： a.投影运算；（投影列） b.选择运算；（选择行） c.笛卡尔积运算（连接运算）（T=R×S） ② 关系代数中的扩充运算： 交运算、除运算、连接与自然连接运算。 并（T=R+S）、差（T=R-S）、交、除（T=R÷S）、自然连接 小技巧：两个表为投影或选择，三个表为其他；属性列增加为自然连接，ST属性列相加等于R为除。 §4.4数据库设计与管理 1. 数据库设计概述：设计一个能满足用户要求，性能良好的数据库。 ① 基本任务： 根据用户对象的信息需求、处理需求和数据库的支持环境设计出数据模式。 ② 两种方法： a.以信息需求为主，兼顾处理需求（面向数据的方法）。 b.已处理需求为主，兼顾信息需求（面向过程的方法）。 c.面向数据的设计方法已成为主流方法。 2. 数据库设计的步骤：数据库设计目前一般采用生命周期法，分若干阶段： ① 需求分析阶段：建立数据字典； ② 概念设计阶段：设计E-R图； ③ 逻辑设计阶段：把E-R图转换为关系模式。实体与联系表示成关系，E-R图中属性转换成关系的属性； ④ 物理设计阶段； ⑤ 编码阶段； ⑥ 测试阶段； ⑦ 运行阶段； ⑧ 进一步修改阶段。 在数据库设计中采用前四个阶段，并且重点以数据结构与模型的设计为主线。 3. 数据库管理： ① 数据库的建立； ② 数据库的调整； ③ 数据库的重组； ④ 数据库安全性控制与完整性控制； ⑤ 数据库的故障恢复； ⑥ 数据库监控。 ★有需要PDF/Word版本的笔记私聊我发，无偿，希望大家都能过★ |
|
|
来自： 昵称63837301 > 《文件夹1》
