第一章 数据结构与算法

华信电脑培训中心内部资料第一章数据结构与算法第一节算法一、算法的基本概念所谓算法是指解题方案的准确而完整的描述。1、算法的基本特征:(1)可行性(2)确定性(3)有穷性(4)拥有足够的情报2、算法的基本要素(1)算法中对数据的运算和操作算术运算，逻辑运算，关系运算，数据传输(2)算法的控制结构：算法中各操作之间的执行顺序称为算法的控制结构。一个算法可以用顺序、选择、循环三种基本控制结构组合而成。2、算法设计的基本方法(1)列举法(2)归纳法(3)递推(4)递归(5)减半递推技术二、算法复杂度1、算法的时间复杂度：指执行算法所需要的计算工作量。用算法在执行过程中所需基本运算的次数来衡量算法的工作量。方法：平均性态，最坏情况复杂性2、算法的空间复杂度：指执行这个算法所需的内存空间。第二节数据结构的基本概念一、什么是数据结构数据结构是指相互有关联的数据元素的集合。如：(1)春、夏、秋、冬(2)父亲、儿子、女儿(1)数据元素有共同的特征(2)各个元素之间存在着某种关系(联系)。用前后件关系来描述。如：夏是秋的前件，秋是夏的后件。父亲是儿子和女儿的前件，儿子和女儿都是父亲的后件1、数据的逻辑结构数据结构是指带有结构的数据元素的集合。一个数据结构应包含以下两方面的信息：(1)表示数据元素的信息(2)表示各数据元素之间的前后件关系，前后件关系是逻辑关系，与它们在计算机中的存储位置无关。数据的逻辑结构反映数据元素之间的逻辑关系。2、数据的存储结构数据的逻辑结构在计算机中的存放形式称为数据的存储结构，也称数据的物理结构。采用不同的存储结构，数据处理的效率不同。一般情况下，数据的逻辑结构和存储结构是不同的。二、数据结构的图形表示每一个数据元素用中间标有元素值的方框表示，称为数据结点，简称结点。用一条有向线段从前件结点指向后件结点。在数据结构中，没有前件的结点称为根结点，没有后件的结点称为终端结点(也称为叶子结点)。其他结点一般称为内部结点。插入与删除是对数据结构的两种基本运算还有查找、分类、合并、分解、复制和修改等运算三、线性结构与非线性结构根据各数据元素之间前后件关系，将数据结构分为：线性结构与非线性结构线性结构满足以下两个条件：(1)有且只有一个根结点(2)每一个结点最多只有一个前件，也最多有一个后件线性结构又称为线性表。第三节线性表及其顺序存储结构一、线性表的基本概念线性表是由n个数据元素a1，a2,…an组成的一个有限序列，表中的每一个数据元素，除了第一个外，有且只有一个前件，除了最后一个外，有且只有一个后件。特征：(1)有且只有一个根结点a1，它无前件。(2)有且只有一个终端结点an，它无后件。(3)其它结点有且只有一个前件和一个后件。线性表中结点的个数n称为线性表的长度，n为0称为空表二、线性表的顺序存储结构线性表的顺序存储结构具有以下特点(1)线性表中所有元素所占的存储空间是连续的。(2)线性表各数据元素在存储空间中是按逻辑顺序依次存放的。三、线性表的插入运算要在第i个元素前插入一个新元素，要从最后一个元素开始，直到第n-i+1个元素依次向后移动一个位置,第i个位置就被空出，然后将新元素插入到第i项。四、线性表的删除运算要删除第i个元素，要从第i+1个元素开始，直到第n个元素之间共n-i个元素依次向前移动一个位置。第四节栈和队列一、栈及其基本运算栈是一种特殊的线性表。一端是封闭的，不允许进行插入与删除，另一端是开口的，允许进行插入与删除。如：子弹夹栈中的元素遵循“先进后出”或“后进先出”的原则二、队列及其基本运算队列是指允许在一端进行插入，而在另一端进行删除的线性表。允许插入的一端称为队尾，允许删除的一端称为排头(也称为队头)。遵循“先进先出”或“后进后出”的原则，体现了“先来先服务”的原则第五节线性链表一、线性表的缺点(1)插入与删除的效率低(2)线性表的存储空间不便于扩充(3)不便于对存储空间的动态分配二、线性链表的概念在链式存储方式中，要求每个结点由两部分组成：一部分用于存放数据元素值，称为数据域。另一部分用于存放指针，称为指针域。二、线性链表的概念线性表的链式存储结构称为线性链表。在线性链表中，各数据元素之间的前后件关系由各结点的指针域来表，指向第一个结点的指针HEAD称为头指针。第六节树与二叉树一、树的基本概念树是一种简单的非线性结构，所有元素之间的关系具有明显的层次特征。1、树的基本术语(1)每一个结点只有一个前件，称为该结点的父结点(2)没有前件的结点只有一个，称为根结点(3)每一个结点可以有多个后件，称为该结点的子结点(4)没有后件的结点称为叶子结点(5)每一个结点所拥有的后件个数称为该结点的度，叶子结点的度为0(6)所有结点中的最大的度称为树的度(7)树的最大层次称为树的深度(8)在树中，以某结点的一个子结点为根构成的树称为该结点的一棵子树。叶子结点没有子树。二、二叉树及其基本性质春夏秋冬父亲儿子女儿V(i)Next(i)数据域指针域数据1数据1数据1nullhead……1、什么是二叉树(1)非空二叉树只有一个根结点(2)每一个结点最多有两棵子树，称为左子树与右子树即每一个结点的度最大为22、二叉树的基本性质(1)在第k层上，最多有2k-1(k≥1)个结点(2)深度为m的二叉树最多有2m-1个结点(3)度为0的结点(即叶子结点)比度为2的结点多1个(4)具有n个结点的二叉树，其深度至少为[log2n]+1其中[log2n]表示的log2n整数部分。3、满二叉树与完全二叉树(1)满二叉树指，除最后一层外，每一层上的所有结点都有两个子结点。即每一层上的结点数均达到最大值。满二叉树的第k层上有有2k-1个结点深度为m的满二叉树有2m-1个结点(2)完全二叉树指，除最后一层外，每一层上的结点数均达到最大值。在最后一层上只缺少右边的若干结点。满二叉树是完全二叉树，但完全二叉树一般不是满二叉树三、二叉树的遍历(递归方法)(1)前序遍历(2)中序遍历(3)后序遍历第七节查找技术查找是指在一个给的数据结构中查找某个指定的元素。1、顺序查找顺序查找一般是指在线性表中查找指定的元素。过程：从线性表的第一个元素开始，依次将线性表中的元素与被查元素比较，若相等则表示找到(查找成功)。若线性表中的所有元素都与被查元素进行了比较但都不相等，则表示没有找到要找的元素(查找失败)。2、二分法查找二分法查找只适用于顺序存储的有序表。方法：设有序线性表的长度为n，被查元素为x(1)将x与线性表的中间项进行比较；(2)做中间项等于x，则说明查到，查找结束；(3)若x小于中间项，则线性表的前半部分以相同的方法继续进行查找。(4)若x大于中间项，则线性表的后半部分以相同的方法继续进行查找。第八节排序技术一、交换类排序法1、冒泡排序法2、快速排序法二、插入类排序法1、简单插入排序法2、希尔排序法三、选择类排序法思想：扫描整个线性表，从中选中最小的元素，将它交换到表的最前面；然后对剩下的子表采用同样的方法。1、简单选择排序法2、堆排序法以上各种查找方法中的一种的运算次数最大为n(n-1)/2次第二章程序设计基础第一节程序设计方法与风格一、程序设计方法(1)结构化程序设计方法(2)面向对象程序设计方法二、程序设计风格指编写程序时所表现出的特点、习惯和逻辑思路。程序设计的风格总体而言应该强调简单和清晰，程序必须是可以理解的。即：清晰第一、效率第二第二节结构化程序设计一、结构化程序设计的原则(1)自顶向下(2)逐步求精(3)模块化(4)限制使用goto语句二、结构化程序设计的基本结构与特点(1)顺序结构(2)选择结构(3)循环结构第三节面向对象程序设计一、对象是系统中用来描述客观事物的一个实体，它由一组表示静态特征的属性和它可执行的一组操作组成。如：一辆汽车是一个对象，它包含了汽车的属性(颜色，型号)及其操作(启动，刹车)。一个窗口是一个对象，它包含了窗口的属性(大小，颜色，位置)及其操作(打开，关系)特点：(1)分类性(2)多态性(3)封装性(4)模块独立性好二、类和实例:类是具有共同属性、共同方法的对象的集合。类是对象的抽象，而一个对象则是其对应类的一个实例。三、方法:对象所具有的操作。四、继承:是使用已有的类定义作为基础建立新类的定义技术。五、多态性:同样的消息被不同的对象接受时可导致完全不同的行动，该现象称为多态性。第三章软件工程基础第一节软件工程基本概念一、软件定义与软件特点软件是包括程序、数据及相关文档的完整集合。包括：(1)机器可执行的程序与数据。(2)机器不可执行的，与软件开发、运行、维护、使用等相关的文档。特点：(1)软件是一种逻辑实体，不是物理实体，具有抽象性。(2)软件的生产与硬件不同，没有明显的制作过程。一旦开发成功，可以大量拷贝。(3)软件在运行、使用期间不存在磨损与老化问题(4)软件的开发、运行对计算机系统有依赖性(5)软件复杂性高，成本昂贵二、软件危机与软件工程软件危机是泛指在计算机软件的开发和维护过程中所遇到的一系列严重问题。软件工程的核心思想是把软件产品看作一个工程产品来处理。以期达到工程项目的三个基本要素：进度、经费和质量目标。三、软件生命周期将软件产品从提出、实现、使用维护到停止使用退役的过程称为软件生命周期。(1)可行性研究与计划制定(2)需求分析(3)软件设计(4)软件实现(5)软件测试(6)运行与维护四、软件工程的目标在给定成本、进度的前提下，开发出具有有效性、可靠性、可理解性、可维护性、可适应性、可移植性和可互操作性且满足用户需求的产品。第二节结构化分析方法一、需求分析与需求分析方法1、需求分析：指用户对目标软件系统在功能、行为、性能、设计约束等方面的期望。需求分析的任务是发现需求、求精、建模和定义需求的过程。需求分析阶段的工作：(1)需求获取：确定对目标系统的各方面的需求(2)需求分析：对获取的需求进行分析与综合，最终给出系统的解决方案和目标系统的逻辑模型。(3)编写需求规格说明书(4)需求评审可行性研究初步项目计划需求分析概要设计详细设计实现调试使用维护退役定义阶段开发阶段维护阶段2、需求分析方法(1)结构化分析方法(2)面向对象的分析方法二、结构化分析方法1、结构化分析方法的定义结构化分析方法是结构化程序设计理论在软件需求分析阶段的运用。步骤如下：(1)通过对用户的调查，获得当前系统的具体模型(2)根据具体模型，抽象出当前系统的逻辑模型(3)根据计算机的特点，建立目标系统的逻辑模型(4)写出目标系统的软件需求规格说明书(5)评审直到确认完全符合用户对软件的需求2、结构化分析的常用工具(1)数据流程图(DFD—DataFlowDiagram)数据流程图是描述数据处理过程的工具，是需求理解的逻辑模型的图形表示。数据流程图中的主要图形元素与说明如下：加工(转换)：输入数据经加工变换产生输出数据流存储文件(数据源)源，潭：表示系统和环境的接口，属系统之外的实体建立数据流程图的步骤：(1)由外向里(2)自顶向下(3)逐层分解银行取款业务的数据流程图(2)数据字典(DD—DataDictionary)数据字典是对所有与系统相关的数据元素的一个有组织的列表，以及精确的、严格的定义。数据字典的作用是对DFD中出现的被命名的图形元素的确切解释。三、软件需求规格说明书1、作用：(1)便于用户、开发人员进行理解和交流(2)反映出用户问题的结构，可以作为软件开发工作的基础和依据(3)作为确认测试和验收的依据2、内容(1)概述(2)数据描述：数据流程图，数据字典，系统接口说明，内部接口(3)功能描述：功能，处理说明，设计的限制(4)性能描述：性能参数，测试种类，预期的软件响应，应考虑的特殊问题第三节结构化设计方法一、软件设计的概念1、从技术观点来看，软件设计包括：软件结构设计，数据设计，接口设计，过程设计。从工程管理角度来看，软件设计分两步：概要设计和详细设计。2、软件设计的基本原理(1)抽象(2)模块化(3)信息隐蔽(4)模块独立性内聚性：一个模块内各个元素间彼此紧密程度的度量耦合性：模块间互相连接的紧密程度的度量一般较