第01讲公共基础知识.ppt

第一讲,公共基础知识,2,内容提要,教学重点及难点重点：基本概念难点：数据结构,1.1、数据结构与算法算法；数据结构1.2、程序设计基础程序设计方法和风格；结构化程序设计；面向对象程序设计1.3、软件工程基础软件工程基本概念；结构化分析方法；结构化设计方法；软件测试；程序调试,3,1.1.1.1 算法（P1）,1、算法定义：指解题方案的准确而完善的描述。2、算法的基本特征：可行性；确定性；有穷性；拥有足够的情报。3、算法的基本要素：运算算术、逻辑和关系运算和操作数据传输：输入和输出；控制结构顺序、选择和循环结构。4、算法的基本方法：列举法、归纳法、递推法、减半递推法、回溯法。5、算法的复杂度：时间复杂度（执行算法所需要的计算工作量平均|最坏）；空间复杂度（执行该算法所需要的内存空间算法程序空间+数据空间+执行空间）常见时间复杂度（按递增排列）有常数级O(1)、对数级O（log2n）、线性级O（n）、线性对数级O（nlog2n）、平方级O（n2）、指数级O（2n）。,4,1.1.1.2 基本算法（P8）,1、查找算法：顺序查找：适用无序表或链表。二分查找：适用有序表。2、排序算法：交换排序：冒泡法、快速排序法。插入排序：简单插入排序法、希尔排序法。选择排序：简单选择排序法、堆排序法。,5,1.1.1.2 基本算法_查找算法,查找算法：查找算法是指在某种数据结构中找出满足条件的数据结点，若找到满足条件的结点，则查找成功，否则查找失败。顺序查找：又称为线性查找。它从线性表的一端开始，顺序查找线性表，依次将查找到的结点与给定值K相比较，若查找到的结点关键字与给定的K值相等，则查找成功，若查找到线性表的末端，仍未找到关键字等于K的结点，则查找失败。适用无序表或链表。二分查找：又称为折半查找。它要求线性表中的结点必须按关键字排序。它首先将要查找的K值与线性表中间位置的结点关键字比较，若相等，则查找成功，否则，再根据K值与中间结点关键字大小，确定下一步查找哪个子表。适用有序表。,6,1.1.1.2 基本算法_交换排序算法,排序算法：排序就是把一组无序的记录按其关键字的某种次序排列起来，使其具有一定的顺序，便于进行数据查找。交换排序：两两比较待排序记录的关键字，发现两个记录的与规定的次序相反时即进行交换，起到没有反序的记录为止。冒泡法：对无序数据列从最下面的记录开始，对每两个相邻的记录关键字进行比较，便关键字最小或最大的记录如气泡一样逐渐往上“漂浮”直到“水面”，接着再找第二个直到所有记录都有序为止。对于长度为n的线性表，最坏情况下需要比较n(n-1)/2次。快速排序法：由冒泡法改进而来。在待排序的n个记录中任取一个记录（通常是第一个记录），把该记录放入最后的位置，数据序列被此记录分为两个部分，所有关键字比该记录关键字小的结点放在该结点之前，比它大的放在它之后，然后再重复以上操作，直到所有记录有序为止。对于长度为n的线性表，最坏情况下需要比较n(n-1)/2次。,7,1.1.1.2 基本算法_插入排序算法,排序算法：排序就是把一组无序的记录按其关键字的某种次序排列起来，使其具有一定的顺序，便于进行数据查找。插入排序：每一次循环将一个待排序的记录，按其关键字大小插入到已经排序记录的适当位置，直到全部记录插入完成为止。简单插入排序法：又称直接插入排序。假设记录存放在r1,n之中，r1,j-1上已排好序的记录，ri-1,n是没有排序的记录，插入排序把未的排序记录中的ri插入到r1,j-1之中，使 r1,i成为有序，直到r1,n全部有序。对于长度为n的线性表，最坏情况下需要比较n(n-1)/2次。希尔排序法：把记录按下标的一定增量分组，对每组记录进行直接插入排序，随着增量逐渐减小，所分成的组包含的记录越来越多，到增量的值减小到1时，整个数据合成一组有序的记录。对于长度为n的线性表，最坏情况下需要比较O(n1.5)次。,8,1.1.1.2 基本算法_选择排序算法,排序算法：排序就是把一组无序的记录按其关键字的某种次序排列起来，使其具有一定的顺序，便于进行数据查找。选择排序：每一次循环，从待排序的记录中选出关键字最小的记录，顺序放在已排好的记录的最后，直到全部记录排序完毕。简单选择排序法：又称直接选择排序。每一次排序在n-i+1（i=1，2，n-1）个记录中选取关键字最小的记录，并和第i个记录进行交换。对于长度为n的线性表，最坏情况下需要比较n(n-1)/2次。堆排序法：将顺序表中存储的数据看成是一棵完全二叉树,利用完全二叉树中双亲结点和小孩结点之间的内存关系来选择关键字最小的记录进行排序。对于长度为n的线性表，最坏情况下需要比较O(nlog2n)次。,9,1.1.2.1 数据结构定义,1、数据结构定义：指同一类数据元素中各数据元素之间存在的关系。数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间关系和操作的学科。2、数据结构研究的主要内容：数据的逻辑结构：数据集合中各数据元素之间所固有的逻辑关系；数据的存储结构：数据处理时，各数据元素在计算机中的存储关系；对各种数据结构进行运算。3、数据结构研究的目的：提高数据处理的效率（提高数据处理速度；节省数据处理过程中占用计算机存储空间）,10,1.1.2.2 数据结构概念,1、数据处理：对数据集合中的各元素以各种方式进行运算。2、数据元素：数据处理中，每一个需要处理的对象均可抽象为数据元素。3、数据结构：反映数据元素之间数据元素集合的表示。数据的逻辑结构：数据与数据间关系B=（D，R）。数据的逻辑结构分为线性结构（如顺序表、链表）和非线性结构（如树和图形结构）。数据的存储结构：数据在计算机存储空间中的存放形式。常用的数据存储结构有顺序、链接|式、索引、散列等。数据结构的图形表示:,11,1.1.2.3 数据结构,1、线性表（P2）：定义；特征；存储结构；主要操作插入、删除、查找、排序、分解、合并、复制、逆转；线性表适用场合。2、栈（P4）：定义；存储结构；栈运算。3、队列（P5）：定义；存储结构；运算。4、线性链表（P5）：定义；存储结构；运算。5、树与二叉树（P6）：定义；存储结构；运算。二叉树遍历（前序遍历根-左右、中序遍历左-根-右、后序遍历左-右-根,12,树的基本概念,父结点：在树结构中每一个结点只有一个前驱，称为父结点。根结点：在树结构中没有前驱的结点称为根结点。子结点：在树结构中每一个结点可以有多个后继，它们都称为该结点的子结点。叶子结点：没有后继的结点称为叶子结点或叶子。结点的度：一个结点所拥有的后继的个数称该结点的度。树的度：在树中所有结点中最大的度称为树的度。树的深度：树的最大层次称为树的深度（高度）。子树：在树中以某个结点的一个子结点为根结点的树称为该结点的一棵子树。,13,二叉树及基本性质,二叉树的二个特点：非空与二叉树只有一个根结点，每个结点最多有两棵子树。满二叉树：除最后一层外，每一层上所有结点都有两个子结点（即每层上结点数都达到最大值或者说每个结点的度为2）。完全二叉树：除最后一层外，每一层上所有结点数都达到最大值，在最后一层上只缺少右边的若干个结点。完全二叉树的特点：叶子结点只出现在最下层或次下层，且最下层的叶子集中在树的左部。,14,二叉树及基本性质,性质1：在树的第K层上最多有2k1个结点。性质2：深度为m的二叉树最多有2m1个结点。性质3：在任意一棵二叉树中度为0的结点（即叶子）总是比度为2的结点多一个。性质4：具有n个结点的二叉树其深度至少为log2n+1。性质5：满二叉树的第k层上有2k1个结点，且其深度为m的满二叉树有2m1个结点。性质6：具有n个结点的完全二叉树其深度为log2n+1。性质7：设完全二叉树具有n个结点。如果从根结点开始，按层序（每层从左至右）用自然数1，2，n给结点进行编号，由对于编号为k的结点有以下结论：若k=1，则该结点为根结点，它没有父结点；若k1，则该结点的父结点编号为INT（k/2）。若2kn，则编号为k的结点的左子结点编号为2k，否则该结点无左子结点（当然也没有右子结点）。若2k+1n，则编号为k的结点的右子结点编号为2k+1，否则该结点没有右子结点。,15,二叉树的遍历,二叉树的遍历用到了递归的思想，主要有三种方式前序遍历（DLR）：先访问根结点，后前序遍历左子树，再前序遍历右子树。中序遍历（LDR）：先中序遍历左子树，后访问根结点，再中序遍历右子树。后序遍历（LRD）：先后序遍历左子树，后后序遍历右子树，再访问根结点。,16,1.1.2.3 数据结构,例：已知二叉树后序遍历序列是dabec，中序遍历序列是debac，它的前序遍历序列是A）acbed B）decab C）deabc D）cedba,17,1.2、程序设计基础,1.2.1 程序设计方法和风格1.2.2 结构化程序设计1.2.3 面向对象程序设计,18,1.2.1、程序设计方法和风格（P19）,1、程序设计定义：指对问题进行分析，建立数学模型，组织数据和算法，编写程序，调试程序的过程。2、程序设计方法发展的两个阶段：结构化程序设计；面向对象程序设计。3、影响良好程序设计风格的因素：源程序的文档结构组织（符号命令、注释、视觉组织缩进、空格和空行）；数据说明（数据和变量命名规则、文字说明复杂数据结构）；语句结构原则；输入和输出界面原则要求（P21）。,程序清晰第一，效率第二。,19,1.2.2、结构化程序设计（P22）,1、结构化程序设计的原则：自顶向下；逐步求精；模块化；限制使用GOTO语句。2、结构化程序设计的基本结构和特点：结构（顺序、选择、循环）；特点（易于理解、使用和维护；提高编程效率，降低开发成本）。3、结构化程序设计原则和方法的应用注意：（参见P22）。,20,1.2.3、面向对象程序设计（P22）,1、面向对象程序设计的本质：模仿人类在现实生活中常用思维来认识、理解和描述客观事物，并将其应用于计算机程序设计中。2、面向对象程序设计的优点：接近人类习惯思维方法；稳定性；可重用性好；易于开发大型软件产品；可维护性好。3、面向对象程序设计的基本概念：对象的定义：对象是对问题域某个实体的抽象；对象的属性；对象的方法；对象的特征（封装性、继承性、多态性）。4、类和实例：类是具有共同属性、共同方法的对象的集合，对象是类的实例。5、消息：对象之间的相互作用是通过消息传递。,21,1.3、软件工程基础,1.3.1 软件工程基本概念1.3.2 结构化分析方法1.3.3 结构化设计方法1.3.4 软件测试1.3.5 程序调试,22,1.3.1、软件工程基本概念（P27）,1、软件定义：软件是与计算机操作相关的计算机程序、规程、规则，以及可能有的文件、文档和数据。2、软件三要素：程序、数据和文档。3、软件的特点：（6点）4、软件分类：应用软件、系统软件和支撑软件。5、软件危机：（含义、主要表现5点、产生原因）6、软件生命周期：定义、开发和维护,23,1.3.1、软件工程基本概念（P28）,7、软件工程的定义：是应用于计算机软件的定义、开发和维护的一整套方法、工具、文档、实施标准和工序。8、软件工程的三要素：方法（完成项目的技术手段）、工具（开发、管理和文档生成的工具）、过程（开发环节的控制和管理）9、软件工程过程：定义（将输入转化为输出的一组相关的资源和活动）、过程的基本活动（软件规格说明、软件开发、软件确认、软件演进升级）10、软件工程的目标（P28）11、软件工程原则（P29）12、软件开发工具和开发环境（P29）13、软件工程的理论和技术研究内容（P29）,24,1.3.2、结构化分析方法1（P29）,1、需求分析：指用户对目标软件系统在功能、行为、性能、设计约束方面的期望。2、结构化分析方法：是结构化程序设计理论在软件需求分析的应用。它是基于功能分解的分析方法，其目的是帮助用户弄清对软件的需求。结构化分析最终结果是产生软件需求说明书。3、结构化设计方法(P30)软件设计是将软件需求转换为软件的表示过程。软件设计的重要性：软件开发的基础。软件设计的内容：结构设计、数据设计、接口设计、过程设计。软件设计的原则：抽象、模块化（独立模块、高内聚，低耦合）、信息隐蔽,25,1.3.2、结构化分析方法2（P31）,4、结构化设计内容：概要设计：将需求分析阶段的系统层次结构进一步分解成模块和模块的层次结构。概要设计的基本任务：设计软件体系结构、确定数据结构及数据库设计、编写概要设计文档、进行概要设计评审。详细设计：详细设计的任务：为软件结构图中的每一个模块确定实现的算法和局部数据结构，用某种选定的工具表达算法和数据结构的细节。过程设计的任务：对每个模块规定的功能及算法设计给出描述。过程设计的工具：（P29）HIPO图(Hierarchy Plus Input/Processing/Output)“层次图加输入/处理/输出图”,26,1.3.4、软件测试（P32）,1、软件测试定义和目的：为发现错误而执行程序的过程。它涵盖整个软件开发过程，目的是保证软件开发的质量。2、软件测试准则：3、软件测试技术与方法 按是否要执行被测试软件分为：静态测试和动态测试。按软件功能测试分为：白盒测试和黑盒测试。4、软件测试的实施需求测试。单元测试集成测试确认测试系统测试,27,1.3.5、程序调试（P33）,1、程序调试的任务：诊断和改正程序中的错误。主要在开发阶段。(注意与软件测试的区别)2、程序调试的基本步骤：错误定位；修改设计和代码，排除错误；进行回归测试，防止新错误。3、程序调试的原则：4、程序调试方法：（P33）强行排错法；回溯法；原因排除法。,