文档介绍：,这种算法称为计算机算法。:可行性,确定性,有穷性,拥有足够的情报。:算法中对数据的运算和操作、算法的控制结构。:列举法、归纳法、递推、递归、减半递推技术、回溯法。:正确性、可读性、健壮性、:::反映数据元素之间的关系的数据元素集合的表示。数据的逻辑结构包括集合、线形结构、树形结构和图形结构四种。:数据的逻辑结构在计算机存储空间种的存放形式称为数据的存储结构。常用的存储结构有顺序、链接、索引等存储结构。:在数据结构中,没有前件的结点称为根结点;没有后件的结点成为终端结点。插入和删除是对数据结构的两种基本运算。还有查找、分类、合并、分解、复制和修改等。,一般将数据结构分为两大类型:线性结构和非线性结构。线性结构:非空数据结构满足:有且只有一个根结点;每个结点最多有一个前件,最多只有一个后件。非线性结构:如果一个数据结构不是线性结构,称之为非线性结构。常见的线性结构:线性表、栈、(A1,A2,A3??)。表中的每一个数据元素,除了第一个以外,有且只有一个前件。除了最后一个以外有且只有一个后件。即线性表是一个空表,或可以表示为(a1,a2,??an),其中ai(I=1,2,??n)是属于数据对象的元素,通常也称其为线性表中的一个结点。非空线性表有如下一些特征:(1)有且只有一个根结点a1,它无前件;(2)有且只有一个终端结点an,它无后件;(3)除根结点与终端结点外,其他所有结点有且只有一个前件,也有且只有一个后件。线性表中结点的个数n称为线性表的长度。当n=0时称为空表。。线性表的顺序存储结构具备如下两个基本特征:;。即线性表逻辑上相邻、物理也相邻,则已知第一个元素首地址和每个元素所占字节数,则可求出任一个元素首地址。假设线性表的每个元素需占用K个存储单元,并以所占的第一个单元的存储地址作为数据元素的存储位置。则线性表中第i+1个数据元素的存储位置LOC(ai+1)和第i个数据元素的存储位置LOC(ai)之间满足下列关系:LOC(ai+1)=LOC(ai)+KLOC(ai)=LOC(a1)+(i-1)*K????①其中,LOC(a1)是线性表的第一个数据元素a1的存储位置,通常称做线性表的起始位置或基地址。因为在顺序存储结构中,每个数据元素地址可以通过公式①计算得到,所以线性表的顺序存储结构是随机存取的存储结构。在线性表的顺序存储结构下,可以对线性表做以下运算:插入、删除、查找、排序、分解、合并、复制、,插入一个新结点x,使长度为n的线性表(a1,a2?ai?an)变成长度为n+1的线性表(a1,a2?x,ai?an).该算法的时间主要花费在循环的结点后移语句上,执行次数是n-I+1。当I=n+1,最好情况,时间复杂度o(1)当I=1,最坏情况,时间复杂度o(n)算法的平均时间复杂度为o(n),删除一个新结点x,使长度为n的线性表(a1,a2?ai?an)变成长度为n-1的线性表(a1,a2?ai-1,ai+1?an).当I=n,时间复杂度o(1),当I=1,时间复杂度o(n),平均时间复杂度为o(n)?栈实际上也是一个线性表,只不过是一种特殊的线性表。栈是只能在表的一端进行插入和删除运算的线性表,通常称插入、删除这一端为栈顶(TOP),另一端为栈底(BOTTOM)。当表中没有元素时称为空栈。栈顶元素总是后被插入的元素,从而也是最先被删除的元素;栈底元素总是最先被插入的元素,从而也是最后才能被删除的元素。假设栈S=(a1,a2,a3,??an),则a1称为栈底元素,an称为栈顶元素。栈中元素按a1,a2,a3??an的次序进栈,退栈的第一个元素应该是栈顶元素。即后进先出。(1:M)作为栈的顺序存储空间。M为栈的最大容量。栈的基本运算有三种:入栈、退栈与读栈顶元素。入栈运算:在栈顶位置插入一个新元素