搜索
第一章算法和数据结构一、算法的概念算法的定义算法是指解决方案的准确而完整的描述，是一系列解决问题的清晰指令。算法≠程序。算法的5大特征1.至少1个输出：任何算法，必须有输出结果。2.至少0个输入，足够的情报：对于复杂算法，情报越充足，效果越好。3.有穷性：算法能在有限的执行步骤内、有限的时间内执行结束。4.可行性：算法的每一个步骤都必须能够翻译成计算机可执行的基本操作。5.确定性：算法的每一个步骤都必须描述准确，没有歧义。算法的复杂度【时间复杂度】以基本操作次数的数量级计数，不以秒计数。常见复杂度（越小越快）：O(1)O(logn)O(n)O(nlogn)O(n^2)O(2^n)O(n!)【空间复杂度】算法执行过程中的空间开销。【二者关系】虽然算法中常常会以牺牲空间的方式来换取时间效率，但一般认为二者没有必然关系。二、数据结构的概念数据结构的定义数据结构是指计算机组织、存储数据的方式。数据结构可分为逻辑结构和存储结构。其中：1.逻辑结构又分为线性结构和非线性结构。2.存储结构又分为顺序存储结构和链式存储结构逻辑结构逻辑结构不关心数据如何存储，只关心数据的组织方式。逻辑结构可分为线性结构和非线性结构。典型线性结构：栈、队列典型非线性结构：树（二叉树）、网状图存储结构存储结构不关心数据如何组织，只关心数据的存储方式。存储结构又分为顺序存储结构和链式存储结构。【顺序存储结构】1.所有元素在内存中按顺序排列2.查找、修改比较不方便3.插入、删除比较方便【链式存储结构】1.所有元素在内存中随机分布2.插入、删除比较不方便3.查找、修改比较方便4.由于要存储下一元素的地址，所以需要更多的存储空间【二者关系】二者没有必然关系。三、栈基本概念1.栈属于逻辑结构的概念，属于线性结构。2.栈既可以用顺序存储结构实现，也可以用链式存储结构实现。3.栈的特点是先进后出（FILO）。4.进出过程中，栈底指针不变，栈顶指针移动。计算规则视栈顶和栈底指针的指向规则而定。一般的，栈底指向首元素的前一位置（比如0），栈顶指针指向尾元素（比如5），即栈中1、2、3、4、5各存储了一个数据。此时：栈中元素个数=栈顶指针-栈底指针（比如5-0=5）四、队列基本概念1.队列属于逻辑结构的概念，属于线性结构。2.队列既可以用顺序存储结构实现，也可以用链式存储结构实现。3.队列的特点是先进先出（FIFO）。4.队头负责出队，队尾负责入队。循环队列循环队列是专门针对顺序存储结构空间固定的特点而设计的，所以一般认为循环队列是顺序存储结构。其核心原理是：当队尾到达队列最大位置、而队头不在最小位置时如果继续入队，则队尾移至队列最小位置，从头开始移动，形成循环。出队时同理。计算规则视栈顶和栈底指针的指向规则而定。一般的，队头指向首元素的前一位置，队尾指针指向尾元素。假设队列容量为20：1.若队尾队头（比如队尾为7，队头为2）：队列元素个数=队尾指针-队头指针（7-2=5）2.若队头队尾（比如队尾为2，队头为7）：队列元素个数=队尾指针-队头指针+队列容量（2-7+20=15）其中，第二种情况只有循环队列中才会出现。五、二叉树的计算基本概念1.一个二叉树只有一个根节点。2.在二叉树中，任何一个节点最多只能有2个子节点。3.一个节点有几个子节点，则度为几。度为0的节点称为叶子节点。常用公式1.第n层的节点数最多为2^(n-1)个。2.层数为n的二叉树，总节点数最多为2^n-1个。3.叶子节点数=度为2的节点数+14.二叉树节点总数=度为2的节点数+度为1的节点数+叶子节点数六、二叉树的遍历遍历规则先序遍历：父节点、左子树、右子树中序遍历：左子树、父节点、右子树后序遍历：左子树、右子树、父节点其中左右子树按此规则继续拆分，拆分过程中也按其对应规则遍历，直到不能再拆分为止。七、查找算法顺序查找其算法复杂度为O(n)，长度为n的线性表，最多需要n次才能找到指定元素。顺序查找最大/最小值长度为n的线性表，所有元素随机排列，最多需要n-1次才能找到最大/最小值。二分查找其算法复杂度为O(logn)，长度为n的线性表，最多需要logn次就能找到指定元素。二分查找使用条件1.使用顺序存储结构（如数组）。2.所有元素按序排列。八、排序算法按原理分类交换类：冒泡排序、快速排序选择类：简单选择排序、堆排序插入类：简单插入排序、希尔排序按稳定性分类稳定：冒泡排序、简单插入排序……不稳定（快选希堆）：快速排序、简单选择排序、希尔排序、堆排序按算法复杂度O(n^2)：冒泡排序、简单选择排序、简单插入排序O(nlogn)：快速排序、堆排序、希尔排序在一般情况下，快速排序是已知常用算法中效率最高的。在最坏情况下，快速排序的算法复杂度是O(n^)2。第二章软件工程一、需求分析基本概念可行性研究主要考虑：经济、技术、法律。需求分析阶段最重要的文档：《软件需求规格说明书》。《软件需求规格说明书》的任务是统一认识，所以必须追求准确，消灭歧义。数据流图（DFD）箭头：数据流圆形、椭圆形：数据的加工方框：系统和环境的接口半开口的方框、双杠：数据的存储文件数据字典1.是数据流图的重要补充2.应该包含数据流图中提到的所有数据二、软件设计概要设计耦合性：模块之间的关联程度内聚性：模块内部的关联程度设计原则：高内聚低耦合软件系统结构图：深度、宽度、扇入、扇出。详细设计【程序流程图】箭头：控制流矩形：执行步骤菱形：逻辑条件【N-S图】【PAD图】三、结构化程序设计基本原则自顶向下、逐步求精、模块化使用3种基本控制结构，限制goto语句的使用3种控制结构顺序结构、选择结构、循环结构四、面向对象程序设计基本概念对象是类的实例。类由两个部分组成：属性、方法。由同一个类定义的对象，拥有相同的属性和方法类的特征封装型、继承性、多态性五、测试与调试基本概念测试：发现错误调试：诊断并改正错误注意：没有一种方法可以保证软件没有错误黑盒和白盒【黑盒】根据软件的外部功能设计测试用例例如：等价类划分、边界值分析、错误推测法【白盒】根据软件的内部逻辑设计测试用例例如：基本路径覆盖测试、逻辑条件覆盖测试测试流程单元测试：对单一模块进行测试集成测试：对模块间的协作进行测试确认测试：对《软件需求规格说明书》的需求进行逐一确认系统测试：对安全、性能等系统指标进行测试回归测试：对调试后的代码重新进行测试第三章数据库系统一、数据库系统的概念基本概念数据（Data）：信息的载体。包括类型和值两个属性。数据库（DB）：依照某种数据模型将数据组织并存放起来的集合。数据库管理系统（DBMS）：系统软件，是数据库系统的核心，为数据库提供底层服务。数据库管理系统（DBAS）：基于数据库管理系统设计的应用软件，面向普通用户使用。数据库管理员（DBA）：负责数据库设计、维护、性能、安全等工作的高科技人才。数据库系统（DBS）：包括以上所有概念，再加上其他相关软硬件环境的总和。数据语言数据定义语言：表的建立、修改和删除数据操纵语言：表中数据的增加、删除、修改和查询数据控制语言：负责表中的安全性和完整性的设置发展阶段人工管理阶段-文件管理阶段-数据库管理阶段数据库管理阶段主要解决的问题：数据共享。独立性逻辑独立性：逻辑结构修改时，应用程序不需要修改。物理独立性：物理结构修改时，应用程序不需要修改。三级模式概念模式（逻辑模式）：数据库逻辑结构的全局描述外模式（子模式）：用户能看到的数据库逻辑结构和描述内模式（物理模式）：数据库的物理存储结构和存取方法二、E-R模型基本概念E(Entity)：实体R(RelationShip)：联系一对一：学生和学号、中国公民和身份证、考生和准考证号……一对多：班长和班级、宿舍和学生……多对多：学生和课程、老师和课程……图示实体：矩形联系：菱形属性：椭圆形三、关系模型基本概念层次模型：用“树”的方式组织数据网状模型：用“图”的方式组织数据关系模型：用“二维表”的方式组织数据【关系模型】属性、元组【关系数据库】字段、记录元组的分量是关系模型中的最小不可再分单位数据完整性候选键（候选关键字）：可以标识记录唯一性的几个字段。主键（主关键字）：可以标识记录唯一性的一个字段。一个表只能有一个主关键字。外键（外部关键字）：如果当前表中某字段是其他表的主键，则称此字段为外键。实体完整性：主键和候选键不能为空。参照完整性：对一对多关系中父表和子表之间关系的制约。自定义完整性：其他设置。如域完整性，就是对字段取值范围进行设置。四、关系代数基本概念【交】计算前提：两个关系的属性完全相同属性规则：属性保持不变。元组规则：对两个关系中的元组求交集。【并】计算前提：两个关系的属性完全相同属性规则：属性保持不变。元组规则：对两个关系中的元组求并集。【差】R-S=T计算前提：两个关系的属性完全相同属性规则：属性保持不变。元组规则：表示取R中存在且S中不存在的元组形成结果T。【笛卡儿积】RxS=T计算前提：对属性无要求属性规则：对两个关系的属性求并集。元组规则：对两个关系的元组做全排列。【除】R/S=T计算前提：S的属性应是R的子集属性规则：取R中存在的属性而S中不存在的属性作为结果T的属性，即对属性做差运算。元组规则：在R中选择与各属性值完全相等的元组，将其对T中的属性做投影基本概念【选择】规则：按照指定规则，对元组进行筛选，属性不变。【投影】规则：按照指定规则，对属性进行筛选，元组不变。【连接】前提：两个关系中有一个公共属性规则：先做笛卡儿积，然后根据连接条件对结果做选择。连接条件根据公共属性设计。【自然连接】RxS=T前提：两个关系中有一个公共属性规则：1.做笛卡儿积，2.将公共属性值相等的记录留下，3.将两个公共属性合并为一个五、数据库的设计生命周期【需求分析】数据流图、数据字典、需求规格说明书【概念设计】设计E-R模型【逻辑设计】将E-R模型转换为数据模型（主要是关系模型）【物理设计】将关系模型转换为关系数据库