二级公共基础知识

1、一、算法的基本概念l算法是解题方案的准确而完整的描述，它不等于程序，也不等计算方法。l1算法的基本特征可行性(effectiveness)l 每一步要能实现l 执行的结果达到预期的目的确定性(definiteness)-非多义性有穷性(finiteness)拥有足够的情报-输入第二页，共64页。一、算法的基本概念l2算法的基本要素算法中对数据的运算和操作l 算术运算l 逻辑运算l 关系运算l 数据传输算法的控制结构顺序选择循环第三页，共64页。一、算法的基本概念l3算法设计基本方法列举法（工作量大 找规律 分类 优化）归纳法（列举少量 找出一般关系 可能是错的）递推（也是归纳 从初始条件逐次推

2、出中间结果或最后结果）递归（也是归纳 从算法本身到达递归边界）减半递推技术（分而治之 规模减半 重复减半）回溯法（试探 八皇后问题）第四页，共64页。一、算法的基本概念 算法的复杂度 1.时间复杂度 指执行算法所需要的计算工作量 算法工作量=f (n) n是问题的规模与下列因素无关：l书写算法的程序设计语言l编译产生的机器语言，代码质量l机器执行指令的速度第五页，共64页。l算法工作量的分析方法：l第一种情况：l在同一个问题规模下，算法执行所需的基本运算次数可能与输入有关（例如顺序查找），可以用两种方法分析算法工作量第六页，共64页。 (1)平均性态当问题规模一定时，如果算法执行所需的基本运算

3、次数取决于某一个特定的输入时，用此方法分析工作量 A(n) = pi 是某个元素(x)出现的概率 , ti 是在输入某个元素(x)时所执行的基本运算次数 n+1 i=1piti第七页，共64页。 (2)最坏情况复杂性是指当问题规模为n时，算法所执行的基本运算的最大次数 W(n)=max(ti) W(n)比A(n)更有实用价值第八页，共64页。l第二种情况：l算法的计算工作量也可能与输入无关（例如n阶矩阵相乘），在所有可能的输入下，算法所执行的基本运算次数是一定的，此时lA(n)=W(n)第九页，共64页。2.空间复杂度是指执行这个算法所需要的内存空间内存空间包括：1）算法程序占用空间2）输入的

4、初始数据占用空间3）算法执行中所需的额外空间第十页，共64页。二、数据结构的基本概念 数据结构研究三个问题:(1)逻辑结构:数据集合中各元素之间所固有的逻辑关系(2)存储结构:各数据元素在计算机中的存储关系(3)运算:对各种数据结构进行运算数据结构研究的目的:(1) 提高数据处理速度(2) 节省存储空间第十一页，共64页。1.什么是数据结构例如:无序表的顺序查找和有序表的对分查找第十二页，共64页。3516788543293321544616212933354346547885无序表:若查找的元素正好是第一个,次数少 若查找的元素是最后一个或查找的元素不在表中的情况, 无序表有序表则次数多第十

5、三页，共64页。(1)数据的逻辑结构 指数据元素的信息(即数据元素的集合,记为D)和各数据元素之间的前后件关系(记为R)。与它们在计算机中的存储位置无关. 记B为数据结构,则 B=( D , R )第十四页，共64页。例如:一年四季的数据结构表示为: B=( D , R ) D=春,夏,秋,冬 R= (春,夏) , (夏,秋) , (秋,冬) 用二元组表示数据元素之间的前后件关系第十五页，共64页。(2)数据的存储结构(物理结构) 是指数据的逻辑结构在计算机存储空间中的存放形式 注意:各数据在计算机中的存储位置关系与它们的逻辑关系不一定是相同的. 一种数据的逻辑结构根据需要可以表示成多种存储结

6、构，常用的存储结构有： 顺序 链接 索引 第十六页，共64页。2、数据结构的图形表示 例1:一年四季 春 夏 秋 冬 结点 例2:家庭成员 父亲 儿子 女儿 有向箭头 前件指向后件第十七页，共64页。例3:用图形表示数据结构B=(D,R) D=d1,d2,d3,d4,d5,d6,d7 R=(d1,d3),(d1,d7),(d2,d4),(d3,d6),(d4,d5) d1 d2 d3 d7 d4 d6 d5 根结点(无前件) 终端结点 (叶子结点 无后件) 内部结点第十八页，共64页。3.线性结构与非线性结构（1）线性结构:l有且只有一个根结点l每个结点最多有一个前件,也最多有一个后件注意注意

7、:在一个线性结构中插入或删除任何一个结点后还应该是线性结构在一个线性结构中插入或删除任何一个结点后还应该是线性结构如: A B C D将A删除就不满足了第十九页，共64页。(2) 非线性结构：不是线性结构就是非线性结构例如：家庭成员关系 对非线性结构的存储与处理比线性结构复杂得多第二十页，共64页。三、线性表及其顺序存储结构1、线性表的基本概念 例如：一个N维向量、英文字母表、一年中的四季，一个一维数组等都是线性表，其中的每一个值都是线性表的一个数据元素（结点）。此时的数据元素是一个简单项。 又如：一个学生表也是线性表，其中的每条记录就是线性表的一个数据元素（结点）。此时的数据元素是一个复杂项

8、。第二十一页，共64页。2、线性表的顺序存储结构 两个基本特点: （1）线性表中所有元素所占存储空间是连续的 （2）线性表中所有元素在存储空间中是按逻辑顺序依次存放的第二十二页，共64页。2、线性表的顺序存储结构 线性表中每一个数据元素的存储地址ADR(ai)由该元素在线性表中的位置序号i唯一确定 ADR(ai)=ADR(a1)+(i-1)k k表示每个元素占用的字节数第二十三页，共64页。3、顺序表的插入运算（元素后移、上溢）291856633524314712345678910872918566335243147123456789101429871856633524314712345678

9、910如再插入，将上溢如再插入，将上溢1234567第二十四页，共64页。思考：在末尾插入一个元素，在表头插入一个元素，在表中 i 位置处插入一个元素，表中其他元素移动情况。第二十五页，共64页。结论：在线性表的存储情况下，要插入一个元素，效率低；特别是在大表中，消耗的时间更多。第二十六页，共64页。4、顺序表的删除运算2918566335243147123456789101856633524314712345678910185663352447123456789101256734第二十七页，共64页。思考：在末尾删除一个元素，在表头删除一个元素，在表中 i 位置处删除一个元素，表中其他元素移

10、动情况。第二十八页，共64页。结论：在线性表的存储情况下，要删除一个元素，效率低；特别是在大表中，消耗的时间更多。故：线性表在顺序存储结构下的插入与删除运算，比较适合小线性表或者其中元素不常变动的线性表。第二十九页，共64页。四、栈和队列1、栈（stack）及其基本运算 它是限定在一端进行插入与删除的线性表此端称为栈顶，用指针top来指示；另一端不允许做任何操作，称为栈底，用指针bottom来指示。 所谓“先进后出”表或者“后进先出”表。 插入一个元素称为入栈，删除一个元素成为退栈。第三十页，共64页。栈示意图ana2a1入栈退栈栈顶 top栈底bottom第三十一页，共64页。2、队列（qu

11、eue）及其运算 它是在一端（队尾）插入，用尾指针rear指示；另一端（队头）删除，用头指针front指示的线性表。 所谓“先进先出”表或者“后进后出”表 往队列的队尾插入一个元素称为入队运算，从队列的队头删除一个元素称为退队运算。第三十二页，共64页。队列示意图ABCDEFfrontrear退队入队第三十三页，共64页。五、线性链表 一个存储单元对应一个数据结点，这个存储单元称为存储结点，简称结点。 1、线性链表 线性表的链式存储结构称为线性链表数据域指针域存储序号12Im线性链表的存储空间第三十四页，共64页。数据域指针域V（i）NEXT(i)存储序号i线性链表的一个存储结点数据1数据2数

12、据nNullhead线性链表的逻辑结构第三十五页，共64页。例：设线性表为（a1,a2,a3,a4,a5）,存储空间有10个存储结点，则存储情况如图：a29a11a410a35a50123456789103head物理状态图a1head线性链表的逻辑状态图a2a3a4a50319510第三十六页，共64页。以上是线性单链表，特点是： 每个结点只有一个指针域，由它只能找到后件结点，而不能找到前件结点。为弥补此缺点，每个结点设两个指针，即左指针（Llink）用来指向其前件；右指针(Rlink)用来指向其后件。此线性链表称为双向链表，其逻辑状态如图：0DRLDRLD0head域中值为0，表示为空Nu

13、ll,即不指向任何结点第三十七页，共64页。2、带链的栈AnAn-1A10TopAnAn-1A10TopAn+1AnAn-1A10Top入栈操作退栈操作第三十八页，共64页。3、带链的队列A1A2An0frontA1A2AnAn+10A1A2An0rearfrontrearrearfront入队操作退队操作第三十九页，共64页。六、树与二叉树1、树的基本概念 树（tree）是一种非线性结构。RKPQDBENOTCHXYSWZAMFGL根结点根结点叶子结点叶子结点根结点、父结点、子结点、叶子结点结点的度、树的度（后件个数）树的深度（层次个数）子树重要概念第四十页，共64页。2、二叉树及其基本性质

14、l 特点： （1）非空的二叉树只有一个根结点 （2）每个结点最多有两棵子树，且分别称为该结点的左子树与右子树；没有左右子树的结点就是叶子结点 RKDENOTBB只有根结点的二叉树第四十一页，共64页。二叉树的基本性质 性质1 ：在二叉树的第K层上，最多有2k-1(k=1)个结点。 性质2：深度为m的二叉树最多有2m-1个结点。 （等比数列求和： S=a1(1-qn) /(1-q) ） 性质3：在任意一棵二叉树中，（出）度为0的结点（即叶子结点）总是比（出）度为2的结点多一个。 （所有的出度=所有入度+1） 性质4：具有n个结点的二叉树，其深度至少为log2n+1,其中 log2n 表示取 lo

15、g2n 的整数部分。 （由性质2得出）第四十二页，共64页。满二叉树与完全二叉树 （1）满二叉树 即除最后一层外，每一层上的所有结点都有两个子结点。也就是说，每一层上的结点数都达到最大值。(即：除叶子结点外的所有结点均有两个子结点)满二叉树非满第四十三页，共64页。（2）完全二叉树 即除最后一层外，每一层上的结点数都达到最大值；在最后一层上只缺少右边的若干结点。 两者关系： 满二叉树也是完全二叉树，反之则不一定。第四十四页，共64页。完全二叉树的基本性质 性质5 ：具有n个结点的完全二叉树的深度为log2n+1 （由性质4得出） 性质6 ：设完全二叉树共有n个结点。如果从根结点开始，按层序（每

16、层从左到右）用自然数1，2，3，n给结点进行编号，则对编号为k（k=1,2,3,n）的结点有以下结论： （1）若k=1 ,则该结点为根结点，它没有父结点；若k1,则该结点的父结点编号为 int ( k / 2 ) （2）若2k=n,则编号为k的结点的左子结点编号为2k;否则该结点无左子结点（显然也没有右子结点） （3）若2k+1=n,则编号为k的结点的右子结点 第四十五页，共64页。3、二叉树的存储结构FCEDHGPAB4F6C90E2A08D0130H010P05G110B0BT二叉树二叉链表的逻辑状态iL(i)V(i)R(i)LchildRchildValue二叉树存储结点结构第四十六页，

17、共64页。10P020A0346F9513G162C87811D090E510110B012130H0BT二叉链表的物理状态第四十七页，共64页。4、二叉树的遍历 （1）前序遍历（DLR） 根左右 （2）中序遍历（LDR） 左根右 （3）后序遍历（LRD） 左右根第四十八页，共64页。例如：表达式（a+b）* d / 2 用下列逻辑结构，采用前序遍历就可以实现(a*b/d2+)第四十九页，共64页。七、查找技术1、顺序查找 从第一个元素开始，依次比较，若相等，则表示找到。 这对于大表来说，效率较低。在最坏的情况下，顺序查找需要比较 n 次。2、二分法查找 此方法只适用于顺序存储的有序表。 效率

18、比顺序查找高。对于长度为n的有序线性表，在最坏的情况下，二分法只需要比较 log2n 次，而顺序查找需要比较 n 次。第五十页，共64页。八、排序技术1、交换类排序（1）冒泡排序（相邻元素比较） 假设线性表的长度为 n，在最坏情况下，需要比较的次数为 n(n-1)/2（2）快速排序法（选取元素，不断分割）2、插入类排序（1）简单插入排序法（提取元素，插入有序表） 将无序序列中的各元素（先保存到一个变量T中）依次插入到已经有序的线性表。每一次比较后最多移掉一个逆序。因此其效率与冒泡法相同，在最坏情况下，需要比较的次数为n(n-1)/2第五十一页，共64页。（2）希尔排序法（先分割成子序列，再插入

19、排序） 将相隔某个增量h的元素构成一个子序列。在排序的过程中，逐次减小这个增量，最后当h减到1时，进行一次插入排序，排序完成。 增量一般取 ht = n / 2k ( k = 1 , 2 , , log2n ) 其中n为待排序序列的长度。 希尔排序对于每个子表仍然是插入排序，但是，在子表中每进行一次比较就有可能移去整个线性表中的多个逆序，从而改善了排序性能。其效率与所选取的增量序列有关，如果选取上述增量，则在最坏情况下，需要比较次数为O（n1.5）第五十二页，共64页。3、选择类排序（1）简单选择类排序（选择，交换） 扫描整个线性表，选取最小元素，交换到表的最前面；对剩下的子表采用同样的方法，

20、直到子表是空为止。 最坏情况下，比较次数 n (n-1) / 2（2）堆排序第五十三页，共64页。一、软件的生命周期 指软件产品从提出、实现、使用维护到停止使用退役的过程。 第五十四页，共64页。可行性研究需求分析概要设计详细设计实现测试使用维护退役定义阶段开发阶段维护阶段第五十五页，共64页。二、结构化分析方法1、需求分析2、分析工具 a.数据流图（DFD） b. 数据字典（DD） c.判定树 d.判定表3、软件需求规格说明书（SRS）加工（转换）数据流存储文件（数据源）源，潭（系统之外的实体）第五十六页，共64页。三、结构化设计方法1、软件设计的基本原理（1）抽象（2）模块化（3）信息隐蔽

21、（4）模块独立性 a.内聚性：是一个模块内部各个元素间彼此结合的紧密程度。 一个模块的内聚性越强，那么其独立性就越强。 b.耦合性：是模块间互相连接的紧密程度。 一个模块与其他模块的耦合性越强,则其独立性越弱。 内聚与耦合的关系：内聚性越强那么耦合性就越弱。应该做到高内聚，低耦合。第五十七页，共64页。2、概要设计 （1） 基本任务： 设计软件的系统结构 数据结构及数据库设计 编写概要设计文档 概要设计文档评审 （2）设计工具 a.结构图 b.数据流图（变换型、事务型） （3）设计准则 （P66）第五十八页，共64页。3、详细设计（1） 基本任务： a.为软件结构中的每一个模块确定实现算法和局

22、部数据结构。 b.用某种选定的表达工具表示算法和数据结构的细节。 （2）设计工具 a.图形工具：程序流程图PFD，N-S，PAD，HIPO PAD:问题分析图 b.表格工具：判定表 c.语言工具：PDL（伪码） 第五十九页，共64页。HIPO图(hierarchy plus input-process-output)是IBM公司于70年代中期在层次结构图(structure chart)的基础上推出的一种描述系统结构和模块内部处理功能的工具(技术)。HIPO图由层次结构图和IPO图两部分构成,前者描述了整个系统的设计结构以及各类模块之间的关系,后者描述了某个特定模块内部的处理过程和输入/输出关系。 HIP0图一般由一张总的层次化模块结构图和若干张具体模块内部展开的IPO图组成,如图3.13和图3.14所示。 图3.13是一张有关修改库存文件部分内容模块的层次模块结构图。图3.14是图3.13中若干张模块展开图(IPO图)中的一