第13章 软件技术基础-vb.pptx

第13章 软件技术基础 13.1 算法与数据结构 13.1.1 算法 算法是解题方案的准确而完整的描述。算法可以用程序实现，但程序的编制不可能优于算法的设计，而且算法不等于程序，也不等于数学上的计算方法。 算法具有五个基本特征：可行性、确定性、有穷性、输入、输出。 算法由两个基本要素组成：一是对数据对象的运算和操作；二是算法的控制结构。算法的基本运算和操作包括四类：算术运算、逻辑运算、关系运算、数据传输；算法的基本控制结构有三种：顺序结构、选择结构、循环结构。 描述算法的工具有：传统的流程图、N-S结构化流程图、算法描述语言等。 算法设计的基本方法有：列举法、归纳法、递推法、递归法、减半递推技术、回溯法。 ; 评价一个算法的主要标准是：算法的效率和存储需求。算法的效率指的是时间复杂度，存储需求指的是空间复杂度。; 在同一个问题规模下，如果算法执行所需的基本运算次数取决于某一特定输入时，可以用如下两种方法来分析算法的工作量: （1）平均性态分析 所谓平均性态分析是指用各种特定输入下的基本运算次数的带权平均值来度量算法的工作量。 （2）最坏情况复杂性分析 所谓最坏情况复杂性分析是指在规模为n时，算法所执行的基本运算的最大次数。 ;2．算法的空间复杂度 算法的空间复杂度是指执行这个算法所需要的内存空间。一个算法所占用的存储空间包括算法程序所占的存储空间、输入的初始数据所占的存储空间以及算法执行过程中所需要的额外存储空间。 额外存储空间包括算法程序执行过程中的工作单元以及某些数据结构所需要的附加存储空间，如果额外空间量相对于问题规模来说是常数，则称该算法是原地(in place)工作的。 ;13.1.2 数据结构的基本概念 数据结构是指相互关联的数据元素的集合。结构是指数据元素之间的前后件关系，是数据元素之间的一个基本关系。数据结构讨论的主要内容有：（1）数据的逻辑结构；（2）数据的存储结构；（3）对数据结构的运算。 讨论数据结构的目的是为了提高数据处理的效率，主要包括：??1）提高数据处理的速度；（2）尽量节省数据处理过程中所占用的存储空间。 1．数据的逻辑结构 数据的逻辑结构是指反映数据元素之间逻辑关系的数据结构，其中数据元素之间的前后件关系是指它们的逻辑关系，而与它们在计算机中的存储位置无关。;2．数据的存储结构 数据的逻辑结构在计算机存储空间中的存放形式称为数据的存储结构，也称数据的物理结构。 3．数据结构的图形表示 数据集合中的每一个数据元素称为数据结点，简称结点，用中间标有元素值的方框表示，用一条有向线段表示前件结点指向后件结点，如图13-1所示。 ;;2．线性表的顺序存储结构 线性表的顺序存储结构也称为顺序表。具有如下两个基本特点： （1）在顺序表中，所有元素所占的存储空间是连续的。 （2）各数据元素在存储空间中是按逻辑顺序依次存放的，其前后件的两个元素在存储空间中是紧邻的，且前件元素一定存储在后件元素的前面。 在程序设计语言中，通常用一维数组来表示线性表的顺序存储空间，因为程序设计语言中的一维数组与计算机中实际的存储空间结构是类似的。一般来说，长度为n的线性表 （a1,a2,…,ai,…,an）; 在顺序表中，如果要在第i（1≤i≤n）个元素之前插入一个新元素，则原来第i个元素之后(包括第i个元素)的所有元素都必须往后移动一个位置。如果要删除第i（1≤i≤n）个元素，则原来第i个元素之后的所有元素都必须依次往前移动一个位置。 ;13.1.4 栈和队列 1．栈 栈是特殊的线性表，属于线性结构。栈允许插入与删除的一端称为栈顶，用Top指针指示，而不允许插入与删除的另一端称为栈底，用Bottom指针指示。 栈按照“先进后出”(First In Last Out，FILO)或“后进先出”(Last In First Out，LIFO)的原则组织数据，因此，栈也被称为“先进后出”表或“后进先出”表。栈具有记忆作用（栈顶指针以下的元素被记忆），在顺序存储结构下，栈的插入与删除运算都不需要移动表中其他数据元素，仅移动Top指针即可，栈顶指针动态反映了栈中元素的变化情况，如图13-3所示。与一般的线性表一样，在程序设计语言中，用一维数组作为栈的顺序存储空间。 在顺序存储结构下，栈的运算有如下三种： （1）入栈运算：在栈顶位置插入一个新元素。 （2）退栈运算：取出栈顶元素并赋给一个指定的变量。 （3）读栈顶元素：将栈顶元素赋给一个指定的变量。 ;2．队