二级教程公共基础

第1章数据结构与算法1.1算法1.1.1算法的基本概念算法:是指解题方案的准确而完整的描述。1．算法的基本特征：可行性、确定性、有穷性、拥有足够的信息。2．算法的基本要素：对数据对象的运算和操作：算术运算逻辑运算关系运算数据传输算法的控制结构：顺序结构、选择结构、循环结构3．算法的基本方法：列举法归纳法递推法递归法减半递推技术1.1.2算法复杂度1.算法的时间复杂度：用算法在执行过程中所需基本运算的执行次数来度量算法的工作量算法的工作量=f(n)其中n是问题的规模算法的平均性态(AverageBehavior)A(n)=Dnxxtxp)()(最坏情况复杂性(Worst-CaseComplexity)W(n)=)}({maxxtnDx2.算法的空间复杂度：一般是指执行这个算法所需要的内存空间1.2数据结构的基本概念：数据结构主要研究数据的逻辑结构、数据的存储结构、对各种数据结构的运算。1.2.1什么是数据结构1．数据的逻辑结构：一个数据结构应包含以下两方面的信息：表示数据元素的信息表示各数据元素之间的前后件的关系线性结构、树形结构、图形结构、集合2．数据的存储结构：顺序结构、链接结构、索引结构1.2.2数据结构的图形表示：数据结点(简称结点)用方框表示，有向线表示前后关系。1.2.3线性结构与非线性结构线性结构：二个条件：有且只有一个根结点；每一个结点最多有一个前件，也最多有一个后件。非线性结构：结点之间的关系较复杂，前件和后件的个数多于一个。1.3线性表及其顺序存储结构1.3.1线性表的基本概念(LinearList)一组数据元素，例矩阵，每个元素的类型一致。数据元素可以是简单项，也可以由若干项数据组成。非空线性表有如下一些结构特征：有且只有一个根结点a1，它无前件；有且只有一个终端结点an，它无后件；除根结点和终端结点外，其他所有结点有且只有一个前件，也有且只有一个后件。表中结点的个数称为表的长度。当n=0时，称为空表。1.3.2线性表的顺序存储结构线性表的顺序存储结构具有以下两个基本特点：1．表中所有元素所占的存储空间是连续的。2．线性表中各数据元素在存储空间中是按逻辑依次存放的。在线性表的顺序存储结构下，主要的运算有以下几种：线性表的插入线性表的删除线性表的查找线性表的排序线性表的分解线性表的合并线性表的复制线性表的逆转1.3.3顺序表的插入运算：寻找插入位置，后移，插入。1.3.4顺序表的删除运算：寻找删除位置，前移。1.4栈与队列1.4.1栈及其基本运算1.什么是栈？栈(stack)是限定在一端进行插入与删除的线性表2.栈的顺序存储及其运算栈顶(top指针指向栈顶)，栈底(bottom指针指向栈底元素)入栈：指针进1，元素插入指针所指向的单元。退栈：栈顶的元素赋给一个指定的变量，栈顶指针退1。读栈顶元素：栈顶的元素赋给一个指定的变量，栈顶指针不变。1.4.2队列及其基本运算1.什么是队列：队列(queue)是指允许在一端进行插入、而在另一端进行删除的线性表。尾指针(rear)指向队尾元素，头指针(front)指向排头元素的前一个位置。2.循环队列及其运算在循环队列中，尾指针(rear)指向队尾元素，头指针(front)指向排头元素的前一个位置。循环队列的初始状态为空，即rear=front=m入队：队尾指针进一，当队尾指针rear=m+1时，则置rear=1退队：队头指针退一，当队头指针front=m+1时，则置front=1在循环队列中，当front=rear时，不能确定是队列满还是队列空。在实际使用循环队列时，为了能区分队列满还是队列空，，通常还需增加一个s,s值的定义如下：S=表示队列非空表示队列空10由此得出：队列空的条件为s=0队列满的条件为s=0且front=rear(1)入队运算：先要判断一个队列是否为满，若不满，则进行入队操作。(2)退队运算：先要判断一个队列是否为空，若不空，则进行退队操作1.5线性链表1.5.1线性链表的基本概念顺序存储结构的缺点：插入、删除需移动数据元素存储空间分配不灵活多个线性表同时共享存储空间不好同时分配1．线性链表：线性表的链式存储结构。存储结点的概念：数据元素的值，数据元素的之间前后件关系HEADV(i)NEXT(i)2.带链的栈：入栈和退栈3.带链的队列：入列和出列1.5.2线性链表的基本运算：在线性链表中包含指定元素的结点之前插入一个新元素在线性链表中删除包含指定元素的结点将两个线性链表按要求全成一个线性链表将一个线性链表按要求进行分解逆转线性链表复制线性链表线性链表的排序线性链表的查找1.5.3循环链表的基本运算：循环链表与线性链表相比具有以下两个特点：增加了表头结点，最后一个结点的指针域空表和非空表的表现形式1.6树与二叉树1.6.1树的基本概念在树结构中，每一个结点只有一个前件，称为父结点。可以有多个后件，称为该结点的子结点。度：结点的后件的个数。层的概念：根结点为第一层树的最大层次称为树的深度。子树：以某结点的一个子结点为根构成的树称为该结点的一棵子树。叶子结点：没有子树用树来表示算术表达式的原则如下：(1)表达式中的每一个运算符在树中对应一个运算符结点。(2)运算符的每一个运算对象在树中为该运算符结点的子树(在树中的顺序为从左到右)。(3)运算对象中的单变量均为叶子结点树在计算机中通常用多重链表表示，但指针域不好处理。1.6.2二叉树及其基本性质1．什么是二叉树二叉树具有以下两个特点：非空二叉树只有一个根结点。每个结点最多有二棵子树，且分别称为该结点的左子树和右子树二叉树的五种形态2．二叉树的基本性质：(1)在二叉树的第k层上，最多有2k-1(k=1)个结点。(2)深度为m的二叉树最多有2m-1个结点。(3)n0=n2+1(4)具有n个结束的二叉树，其深度至少为[log2n]+13．满二叉树与完全二叉树完全二叉树：除最后一层外，每一层上的结点数均达到最大值；在最后一层上只缺少右边的若干结点。深度为[log2n]+1;从根结点开始可以按序编号。1.6.3二叉树的存储结构采用链式存储结构：一个数据域(value)，二个指针域(Lchild,Rchild)1.7.4二叉树的遍历：前序遍历：访问根结点前序遍历左子树前序遍历右子树中序遍历：中序遍历左子树访问根结点前序遍历右子树后序遍历：后序遍历左子树后序遍历右子树访问根结点1.7查找技术1.7.1顺序查找：最好情况，最坏情况，平均情况大致要比较一半线性表为无序表，不管是顺序存储结构还是链式存储结构，只能采用顺序查找。线性表为有序表，好果采用链式存储结构只能用顺序查找。1.7.2二分法查找：只适用于顺序存储的有序表。1.8排序技术1.8.1交换类排序法：冒泡排序，快速排序法1.8.2插入类排序法：简单插入排序法，希尔排序1.8.3选择类排序法：简单选择排序法，堆排序第2章程序设计基础2.1程序设计方法与风格程序设计方法主要经过了结构化程序设计和面向对象的程序设计阶段。程序设计风格主要是清晰第一，效率第二。要注重和考虑下述一些因素。1)源程序文档化：符号名的命名；程序注释；视觉组织2)数据说明的方法：数据说明的次序规范化说明语句中变量安排有序化使用注释来说明复杂数据的结构3)语句的结构：在一行内只写一条语句程序编写应优先考虑清晰性除非对效率有特殊要求，程序编写要做到清晰第一，效率第二首先要保证程序正确，然后才要求提高速度避免使用临时变量而使程序可读性下降避免不必要的转移尽可能使用库函数避免采用复杂的条件语句尽量减少使用“否定”条件的条件语句数据结构钉有利于程序的简化要模块化，使模块功能尽量单一化利用信息隐蔽，确保每一模块的独立性从数据出发去构造程序不要修补不好的程序，要重新编写4)输入和输出输入和输出信息是用户直接关心的，输入和输出方式和格式应尽可能方便用户的使用，因为系统能否被用户接受，往往取决于输入和输出的格式。无论是批处理的输入和输出方式，还是交互式的输入和输出方式。2.2结构化程序设计2.2.1结构化程序设计的原则：自顶向下，逐步求精，模块化，限制goto语句。2.2.2结构化程序设计的基本结构与特点：顺序结构、选择结构、重复结构(循环结构)2.2.3结构化程序设计原则和方法的应用在结构化程序设计的具体实施中，要注意把握如下要素：1)使用程序设计语言中的、选择、循环等有限的控制结构表示程序的控制逻辑；2)选用的控制结构只准许有一个入口和一个出口3)程序语句组成容易识别的块，每块只有一个入口和一个出口；4)复杂的结构应该用嵌套的基本控制结构进行组合嵌套来实现5)语言中所没有的控制结构，应该采用前后一致的方法来模拟；6)严格控制GOTO语句的使用。2.3面向对象的程序设计2.3.1关于面向对象方法主要优点：与人类习惯的思维方法一致稳定性好可重用性好易于开发大型软件产品可维护性好：用面向对象的方法开发的软件稳定性比较好用面向对象的方法开发的软件比较容易修改用面向对象的方法开发的软件比较容易理解易于测试和调试2.3.2面向对象方法的基本概念1.对象：标识惟一性、分类性、多态性、封装性、模块独立性好2.类3.消息：接受消息的对象的名称消息标识符(也称为消息的名称)零个或多个参数4．继承：单继承和多重继承5．多态性第3章软件工程基础3.1软件工程基本概念3.1.1软件定义与软件特点软件的定义：国标(GB)中对计算机软件的定义为：与计算机操作有关的计算机程序、规程、规则，以及可能有的文件、文档及数据。软件的组成：软件有两部分组成，一是机器可执行的程序和数据，二是机器不可执行的，与软件开发、运行、维护、使用有关的文档。软件的种类及区分：应用软件、系统软件、支撑软件(工具软件)。软件特点：1.软件是一种逻辑实体，而不是物理实体2.软件的生产与硬件不同，没有明显的制作过程3.软件在运行、使用期间不存在磨损与老化问题4.软件的开发、运行对计算机系统具有依赖性5.软件复杂性高，成本昂贵6.软件开发涉及诸多的社会因素3.1.2软件危机与软件工程软件危机主要表现：1.软件需求的增长得不到满足2.软件开发成本和进度无法控制3.软件质量难以保证4.软件不可维护或维护程度非常低5.软件的成本不断提高6.软件开发生产率的提高赶不上硬件的发展和需求的增长软件工程的定义：国标(GB)中指出，软件工程是应用于计算机软件的定义、开发和维护的一整套方法、工具、文档、实践标准和工序软件工程包括3个要素：方法、工具和过程方法是完成软件工程项目的技术手段工具支持软件的开发、管理、文档生成过程支持软件开发的各个环节的控制、管理软件工程的核心思想：是把软件产品看作是一个工程产品来处理。把需求计划、可行性研究、工程审核、质量监督等工程化的概念引入到软件生产中，以期达到工程项目的三个基本要素：进度、经费和质量的目标。3.1.3软件工程过程与软件生命周期1.软件工程过程：ISO9000定义：软件工程过程是把输入转化为输出的一组彼此相关的资源和活动。定义支持了软件工程过程的两方面内涵其一，软件工程过程是指为获得软件产品，在软件工具的支持下由软件工程师完成的的一系列软件工程活动。基于这个方面，软件工程过程通常包含4种基本活动：P(Plan)—软件规格说明D(Do)—软件开发C(Check)—软件确认A(Action)—软件演进其二，从软件开发的观点看它就是使用适当的资源(包括人员、硬软件工具、时间等)，为开发软件进行的一组开发活动，在过程结束时将输入(用户要求)转化为输出(软件产品)。2.软件生命周期:从提出、实现、使用维护到停止使用退役的过程。一般包括可行性研究与需求分析、设计、实现、测试、交付使用以及维护等活动3.1.4软件工程的目标与原则1.软件工程目标：在给定成本、进度的前提下，开发出具有有效性、可靠性、可理解性、可维护性、可重用性、可适应性、可移植性、可追踪性和可互操作性且满足用户需求的产品。基于以上目标，软件工程的理论和技术性研究的内容主要包括：软件开发技术和软件工程管理。软件开发技术包括：软件开发方法学、开发过程、开发工具和软件工程