《级公共基础》ppt课件

《《级公共基础》ppt课件》由会员分享，可在线阅读，更多相关《《级公共基础》ppt课件（36页珍藏版）》请在金锄头文库上搜索。

1、二级公共基础（30）,第一章 数据结构与算法,一、概述 1、基本概念及术语 1)数据结构:反映数据元素之间关系的数据元素集合的表示。 2)数据 :描述事物的符号记录；是信息的载体。3） 数据元素 ：数据的基本单位（元组、记录、结点、顶点） 4）数据项：是具有独立含义的最小单位，不能分割；（属性、字段） 2.数据结构（研究三方面的内容） (1)数据的逻辑结构 :反映数据元素之间的所固有的逻辑关系（是在现实世界中的描述）; (2)数据的存储结构 :数据的逻辑结构在计算机中的存储关系（反映在JSJ世界中）; (3)对数据结构的加工运算 ; 注意：1)数据的逻辑结构与存储结构、计算机无关； 2)数据的

2、逻辑结构分为线性结构(线性表、栈、队列)与非线性结构（树、图）； 3.数据的存储结构:数据的逻辑结构在计算机中的存储关系. (1)顺序存储结构: 逻辑上相邻的结点，物理上仍相邻，结点之间的关系由存储单元的 连接关系体现的; (例如：数组 采用此种存储结构) 特点：存储密度大、空间的利用率高； 支持直接访问，知一地址能访问所有元素； 插入、删除时可能引起大量结点的移动 (2)链式存储结构： 至少含有一个指针（地址）域，用指针体现数据元素之间的逻辑关系 特点: 存储密度小、空间的利用率低； 不支持直接访问； 插入、删除时不移动结点 （链式存储不仅存储数据元素而且还存储地址） (3)散列存储 (4)

3、索引存储,4.算法及其特点 1）定义：解决问题准确而又完整性的描述； 2）特点： 确定性（无二义性）、可行性、有穷性（在有限的时间内完成）、拥有足够的情报 3）算法设计方法： 列举法 、 归纳法 、递推 、递归 、减半递推技术 、 回溯法 5. 算法的时间复杂度和空间复杂度 最坏时间复杂度及平均时间复杂度 算法的时间复杂度: 执行算法所需要的计算工作量。（执行算法的次数） 与使用的计算机、程序设计语言及程序编程者无关，但与问题规模有关； 算法的工作量= f (n) n 为问题的规模 算法的空间复杂度: 执行这个算法所需要的内存空间。,二、线性表 1.线性表的逻辑结构 1）定义： n个元素（结点

4、）的有穷序列；n称表长。 2）特点： 除表头无直接前驱，表尾无直接后继，其余的结点有且仅有一个前驱（前件），一个后继（后件); 【表头没前驱，表尾没有后继】 2.线性表分类 1）顺序表 顺序存储结构的线性表。 是一种随机存取结构 Loc(ai)=Loc(a1)+(i-1)*k 计算第i个位置的存储地址： ADR(ai)=ADR（a1）+ (i-1)*k 第i个位置之前插入时: 移动n - i+1个结点 平均移动n/2个结点 量级(n) 删除第i个位置时: 移动n - i个 平均移动(n-1)/2个结点 量级O(n) 2）链表 （运算的实现容易、空表与非空表处理一致） 链式存储结构的线性表。 (

5、1)单链表 设头结点 （查找效率低） (2)循环链表 设尾结点 (3)双向循环链表 从任一结点可迅速确定前趋和后继 (查找效率高，但存储利用率低）,补充 循环链表的四个优点: 1)在循环链表中增加一个表头结点，使得循环链表对空表与非空表的操作实现了统一； 2）循环链表中最后一个结点的指针域不是为空，而是指向表头结点； 3）判断循环链表是否为空的办法不是看表头指针为空，而是看表头结点的后续结点是否还是表头结点； 4）在循环链表中，从任意一个结点都可以访问到表中其他所有的结点。,三.栈与队列 (运算受限【插入与删除】的线性表) 1.栈 (后进先出的线性表) （1）特点： 1)LIFO （FILO）

6、 2) 只允许在一端（栈顶）插入与删除； 3）具有记忆功能 (2)基本操作 ：入栈 、出（退）栈 、取栈顶元素、判栈空（入栈判满、出栈判空） (3) 分类：顺序栈和链栈 (4)应用：栈是内存的一片区域；函数调用（子程序调用）； 计算机中断过程 注：若入栈的顺序A 、B 、C ，问有几种出栈可能？ 熟练出栈的顺序，准确判断哪些能出栈哪些不能出栈.,2.队列( 一端插入，另一端删除) 先进先出的线性表 (1）特点： 1)FIFO (LILO) 2)插入、删除时指针均向后移（向右） 3)有”假溢出”现象 (2)基本操作: 入队 、出队（退队） (3)分类: 顺序队列和链式队列 (4)有假溢出现象 循

7、环队列,四、树 1.定义：若干个结点的有序集（Tree）. 当T为空时，称为空树（T=）；要么满足： 1)有且仅有一个结点为根结点；（位于第一层） 2）其余的若干个结点为互不相交的子集，每个子结点为子树。(子树：树中以某结点的一个子结点为根构成的树。) 2.术语及基本概念 层：（深度或高度） 、度：包括树度和结点度 、 根结点 ：无前件的结点； 子结点：某结点的的后件 ； 叶子结点：（0 度结点） 、父结点：只有一个前件 3.二叉树 （1）定义：除第一层、最后一层外，其余的结点有且仅有一个前件、有一个或两个后件的树； (2) 五种基本形态： o 注意：二叉树有 无数种！,（3）满二叉树与完全二

8、叉树 满二叉树： 除最后一层外，每一层上的结点数均达到最大值（2）。 完全二叉树：除最后一层外，每一层上的结点数均达到最大值（2），在最后一层上只缺少右边若干个结点。（在最后一层上，自右向左缺少） （4）二叉树性质 性质1 在二叉树第K 层上，最多有 2 k-1 (K=1)个结点； 性质2 深度为m的二叉树，最多有 2 m -1(m=0)个结点； 性质3 在任意二叉树中，度为0的结点（叶子结点）总比度为2的结点多一个； n0 = n2 + 1 性质4 具有n个结点的二叉树中，其深度至少为log2n +1 ； log2n 表示它的整数部分 补充： 性质： 设完全二叉树有 n个结点，如果从根结点开

9、始，按层次（从左至右），用自然数1，2，3，4n 给结点进行编号，则对于编号为k （k=1,2,3,4n ）的结点，有一下结论： 1）若k=1时，则该结点为根结点，它没有父节点；若k1时，则该结点的父节点编号为 int(k/2) ,即父节点数为 int(k/2); 2)若2k=n ，则编号为k的左子树编号为 2k ; 3)若2K+1=n ,则编号为k的右子树编号为 2k+1 注意： 若完全二叉树有 50个结点，问有多少个叶子结点？ （n/2）n 为偶数 n 为奇数， 则 叶子结点为 (n+1)/2,(5)二叉树遍历 ：不重复的访问树中所有结点。（采用了递归思想） 前序遍历：(DLR) 根左右

10、中序遍历：(LDR) 左根右 后序遍历：(LRD) 左右根 注意：由遍历方式画树，必须给出“中序遍历”； 前序：ABDECF 中序 ：DBEACF 后序：？ 前序：abdgcefh 中序 ：dgbaechf 后序：？ 中序：TZBACYXP 后序：ZBTYCPXA 前序：？,五、查找与排序 1.查找 (1)顺序查找 ： 适应无序表或采用链式存储的表 对于长度为n 的线性表，平均要进行n/2次；最坏情况下比较n次; (2) 二分查找（折半查找） 条件：顺序存储的有序表 在长度为n 的有序表中进行二分查找，次数为 log2n 2.排序 分类： 内排序 和外排序 (根据排序的元素是否完全占有内存)

11、稳定排序和不稳定排序 （根据排序时对于相同元素是否移动位置） 3.常见的排序（三大类） 最坏时间复杂度 交换类排序 冒泡排序 n(n-1)/2 或 O（n2） 快速排序 n(n-1)/2 插入类排序 直接插入排序 n(n-1)/2 希尔排序 O（n1.5） 选择类排序 直接选择排序 n(n-1)/2 堆排序 O（nlog2n） 归并排序 将已经排好的几个表合并成一个表。 O（nlog2n） 注意：最简单的交换类排序是 冒泡排序； 冒泡、快速、直接插入、直接选择 的最坏时间复杂度均为 n(n-1)/2,第二章 软件工程及程序设计,一、软件 （1）定义：与计算机中相关的程序、数据和说明文档的集合。

12、 （2）三要素：程序 、数据 、文档 （3）特点： 是逻辑实体，具有抽象性；没有明显的制造过程；软件在运行、使用期间不存在磨损、老化问题； 软件的开发、运行对计算机系统具有依赖性；软件的复杂性高，成本昂贵；软件开发涉及社会诸多的因素 （4）分类：系统软件 支撑软件（工具软件） 用来协调用户开发软件的工具性软件 应用软件 (5)软件危机 （20世纪60年代） 1) 定义：在计算机软件的开发、维护中所遇到的一系列严重问题。 2）表现：软件需求增长得不到满足；软件开发的成本和进度无法控制；软件质量难以保证，软件不可维护或维护程度非常低；软件的成本不断提高；软件开发生产率的提高跟不上硬件的发展和应用需

13、求的增长！,3)原因：客观上说由于软件日益深入社会生活的各个层面，对软件需求的增长速度大大超过了技术进步所能带来的软件生产率的提高。 如：软件生产困难、繁琐；软件管理困难；软件生产力低，生产方式落后；生产具有风险，价格昂贵。,二、软件工程 （为了摆脱软件危机，提出了软件工程的概念） 1.定义：运用计算机科学、数学、管理科学等原理，开发软件的工程。 2.核心思想：把软件当作一个工程产品来处理。 3.性质：一门综合性学科。 4.目标：在给定成本、进度的前提下，开发出具有时效性、可靠性、可理解性、可维护性、可重用性、可适应性、可移植性、可追踪性和可互作性且满足用户需求的产品。 5.内容： 软件开发技

14、术 ：软件开发方法学、开发过程、开发工具、软件工程环境 软件工程管理 ：软件管理学 、软件工程经济学、软件心理学等 6.软件工程原则：抽象、信息隐蔽、模块化、局部化、确定性、一致性、完备性和可追踪性 7. 软件工程三要是： 工具、方法 、过程 工具：支持软件开发、管理、文档生成； 方法：完成软件工程项目的技术手段； 过程：支持软件开发的各个环节的控制、管理 8. 软件开发工具： CASE,三、软件工程过程： 1. 定义：软件工程过程是把输入转化成输出的一组相关的资源和活动。 2.内涵：获得软件产品，在软件工具支持下由软件工程师完成的一系列软件过程活动。 3. 4项基本活动： 软件规格说明（pl

15、an） 、软件开发(Do) 、软件确认(check) 、软件演进(action) 规定软件的功能及其运行时的限制； 产生满足规格谁明的软件 ； 能够满足客户提出的要求； 为满足客户的变更要求，软件必须在使用过程中演进 四、软件生命周期 1.定义: 软件产品从提出、实现、使用维护到停止使用退役的全过程。 2. 三个时期（三大阶段） 软件定义阶段：问题定义、可行性研究和需求分析3个阶段 软件开发阶段：包括概要设计、详细设计 实现（编码）和测试4个阶段； 软件维护阶段：即运行、维护阶段,五、软件生命周期模型 瀑布模型 ：针对目的比较明确、清晰的软件；而目的不确切的开发 出不能满足需求的软件。 增量模型 ：让用户参与到软件开发过程中来，保证软件的质量，是优秀的一种模型 螺旋模型 喷泉模型 进化模型 智能模型,六、三个时期（三大阶段）的8个阶段 1.问题定义 : 确定需求解决的问题是什么? 2.可行性分析阶段： 技术可行性 、经济可行性 、社会可行性 3.需求分析阶段 （1）目的：用户对目标软件系统在功能、行为、性能、设计约束等方面的期望。 （2）工作：需求获取、需求分析、编写需求规格说明书和需求评审 （3）常见方法：结构化分析方法 和 面向对象分析方法 结构化分析方法：面向数据流（SA） 、面向数据结构的Jackson方法（JSD） 面向数据结构的结