中小企业网站制作软件,网站怎么做支付宝接口,英文网站推广,app开发公司成员文章目录408 第一章 数据结构数据是客观事物的符号表示#xff0c;是对现实世界的事物采用计算机能够识别#xff0c;存储和处理的形式进行描述的符号的集合。 数据元素是数据的基本单位。一个数据元素由若干个数据项组成。数据项又成为简单数据项及复合数据项两种。简单数据…
文章目录 408 第一章 数据结构数据是客观事物的符号表示是对现实世界的事物采用计算机能够识别存储和处理的形式进行描述的符号的集合。 数据元素是数据的基本单位。一个数据元素由若干个数据项组成。数据项又成为简单数据项及复合数据项两种。简单数据项不能再分割复合数据项由若干个数据项组成。 类型是一组值的集合 抽象数据类型ADT用一种类型和定义再该类型上的一组操作来定义。 数据结构是抽象数据类型的实现可以使用二元组表示 数据结构D,R 其中D是数据对象即数据元素的有限集R是该数据对象种所有数据元素之间的关系有限集。 数据元素及数据元素之间的逻辑关系称为数据的逻辑结构数据元素及数据元素之间的关系在计算机中的存储表示称为数据的存储结构或物理结构。 数据的逻辑结构分为4类集合线性结构树结构和图结构。 线性结构中每个元素最多只有一个前驱和一个后继。线性表是典型的线性结构。 树结构和图结构都属于非线性结构其中每个元素都可能有多个前驱和多个后继。 如果结构中每个元素最多只有一个前驱而可能有多个后继且有一个元素没有前驱则为树结构。 如果结构中每个元素都可能有多个前驱及多个后继则为图结构。 数据的基本存储结构有四种顺序存储链式存储索引存储及散列存储。 顺序存储方式通常采用数组实现也称为静态存储。链式存储方式通常采用指针实现也称为动态存储。 问题是一个需要完成的任务即一组输入就有一组相应的输出。 算法是指解决问题的一种方法或者一个过程。一个问题可以用多种算法来解决一种给定的算法解决一个特定的问题。算法应具备有输入有输出确定性有穷性及可执行性。 一个计算机程序是使用某种程序设计语言对一种算法的具体实现。 1.1线性表 线性表是最简单的一种线性结构有很广泛的应用同时也是其他非线性结构的基础。线性表中各元素的类型是一致的。 由任意元素组成的表称为广义表广义表是对线性表的扩展。线性表是大纲中数据结构部分的重要内容对广义表不做要求。 要深入理解线性表的概念了解线性表基本操作中各参数的含义正确给出操作的结果。能正确实现基于线性表应用的程序。 1.1.1线性表的定义和基础操作 1.线性表的定义 线性表是最常用且最基本的一种数据结构是由称为元素的数据项组成的一种有限且有序的序列。表中元素可以是任意类型。由n,(n≥0)个元素组成的线性表记为a0,a1,…an-1 其中a0称为表头an-1称为表尾。元素的个数n称为表长。n0时称为空表记为。 线性表各元素的位置是确定的。线性表中常使用整数表示各元素的位置表头a0的位置为0a1的位置为1一般地ai的位置为i。 元素ai-1(1≤i≤n-1)称为ai的直接前驱简称为前驱ai称为ai-1的直接后继简称为后继。除a0外每个元素有且仅有一个前驱除an-1外每个元素有且仅有一个后继。 线性表中各元素可以是可比类型的也可以是不可比类型的。如果是可比类型的其“大小”可以任意即可以有序也可以无序。大小有序的线性表称为有序表。 2.线性表的基本操作 线性表的基础操作包括 创建一个空表Create():返回一个空的线性表L。 在表的指定位置插入一个元素Insert(L,i,e):在表L的位置I插入元素e。 删除表中指定位置的元素Delete(L,i):删除表L中位置I的元素。 访问表中指定位置的元素GetElem(L,i):返回表L中位置i的元素。 判定表空IsEmpth(L):如果表为空返回真否则返回假。 判定表满IsFull(L):如果表已满返回真否则返回假。 求表长Length(L):返回表中元素的个数。 求表中指定元素的直接前驱Prev(L,e):返回表L中元素e的直接前驱。 求表中指定元素的直接后继Next(L,e):返回表L中元素e的直接后继。 1.1.2线性表的实现 1.线性表可以采用不同的存储结构保存主要存储结构有两种数组及链表。 2.采用数据保存的线性表称为顺序表这种存储结构称为顺序存储结构或静态存储结构。 采用指针方式保存的线性表称为链表相应的存储结构称为链式存储结构或者动态存储结构。 集合两种存储结构的特点将线性表以动态存储的策略保存在数组中得到静态链表。 1.顺序存储 顺序存储方式下线性表采用一维数组保存采用数组保存的线性表称为顺序表。线性表中各元素依次保存在数组各存储单元中表中逻辑上相邻的两个元素其实际的存储位置也相邻。 若线性表每个元素占用L个存储单元线性表中元素a的存储地址表示为Loc(ai),则有下列关系 LOC(ai) LOC(a0)i*l 只要确定了顺序表存储的其实位置数组首址根据上式可以立即得到线性表中任一元素的存储位置。由于数组能够按照下表直接当问元素所以顺序表可实现随机存取。 根据已知条件计算顺序表中某个元素的实际存储地址是考试中中常见的题型。 设顺序表元素类型表示为ElemType 使用C语言定义的顺序表如下 typedef struct{ElemType* listArray; //指向ElemType类型数组的指针int length; //数组长度int listSize; //数组最大容量
}SeqList;数组一经分配其大小不可改变数组空间大小由listSize表示顺序表中当前元素个数保存在length中。 顺序表保存在数组中数组的特点要求数据必须保存在一段连续的地基空间内。在顺序表中插入删除元素时不可避免地要进行或多或少的元素移动。在顺序表中插入一个新元素删除指定位置元素时最优时间复杂度均为O1最差时间复杂度和平均时间复杂度均为On.所列的其他基本操作的时间复杂度均为O1。由此可见插入删除操作的开销较大。 2.链式存储 线性表中的各元素也可以不必保存在一段连续的地址空间中而是放在任意的存储单元内。为了能方便找到这些存储单元采用指针结构将这些存储单元串在一起形成链表。这种存储方式称为链表存储采用链式存储结构的线性表称为链表。这样的表示法也称为动态表示 链表由一系列的节点构成每个节点包括数据域和指针域其中数据中保存线性表的一个数据元素的信息指针域中保存指向该数据元素后继结点的指针信息表尾结点的指针域中保存NuLL表示表的结束。指针也称为连链表的名称由此得来。 每个结点中除数据域外只包含一个指针域这样的链表称为单链表。单链表中各元素的位置仍然用整数表示通常使用一个指针称为表头指针指向表头元素结点使用另外一个指针称为当前工作指针来指示操作位置如图1-1所示为一个单链表指针head指向表头元素指针P指向操作位置。表尾结点的指针域保存Null,使用^表示。 为了操作上的方便常常在单链表的表头添加一个空结点称为表头结点得到带表头的单链表 在单链表中当前工作指针确定后插入删除操作的时间复杂度均为O1但访问表中元素的效率较低时间复杂度为On。寻找表中元素的前后操作很好实现但寻找元素的前驱式需要从表头向后遍历时间复杂度为On。 双向链表中寻找前驱后继操作的时间复杂度都为O1。 3.线性表的应用 1多项式操作 多项式是数学上经常用到的概念。设有n次一元多项式如下 Pn(X) p0 p1X p2x2 ***** pnXn 最先想到的是采用顺序表来保存多项式分配含n1个元素的数组数组元素的类型依多项式系数的类型而定。在这种存储方式下很容易实现多项式的加法和剑法操作 但当多项式中为零的系数很多时顺序表存储方式的弱点显现。考虑一个仅有三个非零系数的2015次的一元多项式 Sx2-7x158.4X2015 可以采用链表的方式保存。链表中仅需保存多项式中由非零系数没有规律所以还必须保存该项对应的指数。非零系数与指数构成一个二元组多项式中多有的非零系数用一系列的二元组来表示。用系数指数的序列可以唯一地确定一个多项式。 有了这样的定义后多项式的操作可以归结为单链表的操作。 2freelist(空闲块)管理 当链表中频繁赠删结点时很大程度上会影响到运行效率。一是申请释放空间都会进行系统调用二是可能会产生大量的碎块不方便以后的再分配。 可以在程序中额外建立一个freelist链表与程序中正常使用的链表L类型一致。当L中删除一个结点Node时将Node链到freelist中而当L需要一个新结点是若freelist不空则将freelist中的结点转移到L中仅当freelist中已没有结点时才真正向系统申请一个新空间。freelist的插入与删除都在表头进行时间复杂度都是O1的。freelist只是临时管理程序中用到的空间空间中的数据没有意义各块的次序不重要这个表不需要表头结点。它的实现方式与链栈是类似的。 3静态链表 可以在数组中保存一个链表这样的链表称为静态链表-----》 datalink6184205010335011781590124.线性表两种实现方式的比较 线性表的两种实现各有特色。 顺序表的缺点是大小不能改变。如果不能预知表中元素的最多个数则分配数组空间时就很盲目。数组空间一经分配不论表中元素的实际个数有多少空间全部占用。另外当有元素的插入及删除时除在顺序表尾进行操作已外其他位置的操作都会带来元素的移动系统开销较大。但它的优点是能够实现随机访问数组空间全部用来存放数据没有指针开销。 链表的特点与顺序表不同。它的空间可以随时按需申请空间大小随元素个数的多少而改变元素多则占空间大元素少则占空间少。但每个元素都配有指针开销所以并不是申请的全部空间均用于保存数据。若当前工作指针已指向操作位置时元素插入及删除的时间复杂度均为O(1),且不需要数据元素的移动。有些应用中移动数据元素的开销较大链表就是个很好的选择。但链表只能实现顺序访问时间复杂度为On.。 表1-2列出了在顺序表及单链表实现方式下几种比较典型操作的对比。 表1-2线性表两种实现方式下若干典型操作的比较 操作/应用单链表顺序表说明在尾端添加或删除元素O(n)O(1)对单链表必须遍历整个表。对顺序表只需赋值在头部插入或删除元素O(1)O(n)对顺序表必须将每个元素向后移动一个位置以将第一个位置腾空。单链表只需调整指针对关键字进行线性查找O(n)O(n)最坏情况下必须查找整个单链表或顺序表在有序表的当前位置插入元素a找到插入位置b插入元素O(n)O(1)Olog2nO(n)在单链表中插入只需要指针调整。对于顺序表二分查找找到插入位置然后可能会移动n个元素来腾空单元从表中删除某个值的所有出现O(n)O(n)对于单链表重复进行找到值并调整指针一直到表尾。对于顺序表若找到一次值就调整一次元素则需要On2;若找到值后调整元素的同时也进行判断则是On的
1.2栈队列和数组 栈队列都是线性表并且是操作受限的线性表。所谓操作受阻是指插入删除操作的位置不再是线性表中任何合理的地方而是只局限于线性表的两端。其中栈只允许在表的一端操作表的另一端及中间位置是不可见的。队列允许在表的两端分别进行操作中间位置也是不可见的。数组即是一种数据类型也是一种存储结构。数组本身也属于线性表的范畴。1.2.1栈和队列的基本概念 1.栈的基本概念栈是一种受限的线性表只允许咋线性表的一端进行插入和删除操作。惊醒操作的一端称为栈顶另一端称为栈底。插入操作称为入栈push,删除操作称为出栈pop。入栈和出栈都是O(1)操作。栈的处理方式为后进先出Last In,First OutLIFO.- 栈中没有元素时称为空栈。当栈不空时允许出栈操作当栈不满时允许入栈操作。最后入栈的元素是栈顶元素其所处位置是栈顶一般地使用一个变量标记栈顶位置通常记为top。- 栈的特点是先进后出也可以说是先进后出。不能简单地理解为先入栈的元素一定后出栈后入栈的元素一定先出栈例如给定入栈序列1.2.3.4.5即可以得到5.4.3.2.1的出栈序列也可以得到1.2.3.4.5的出栈序列甚至是3.2.1.4.5这样的出栈顺序。元素1比元素5先入栈1即可以先于5出栈也可以在5之后出栈。- 那么如何正确理解后进先出特点呢这是同时在栈中的元素之间具有的特性。对于栈中的两个元素ai与aj,如果ai先于aj入栈则ai一定先于aj出栈。因为入栈与出栈操作是随机的只要栈不空即可出栈栈不满即可入栈。若元素ai刚入栈后就出栈在ai之后入栈的元素aj都在ai出栈后出栈ai与a不同时在栈中他们之间就不具备后进先出的特点了。2.队列的基本概念队列也是一种受限的线性表它允许在线性表的一端惊醒插入而在另一端进行删除。插入操作称为入栈允许入栈的一端称为对位。删除草错称为出队允许出队的一端称为队头。队列中没有元素时称为空队列。当队列不空时允许出队操作证等待出队的元素是队头元素使用front标记队头位置当队列不满时允许入队操作刚入队的元素是队尾元素使用rear标记队尾元素后的一个空位置。都列中出队次序与入队次序永远保持一致先入队的元素一定先出队。队列的处理方式是先进先出First In, First Out FiFO。
3.双端队列
双端队列结合了栈与队列的特性在线性表的两端均可以插入及删除。双端队列可以是对底栈即两个栈的栈底连在一起。两端分别是两个栈的栈顶且两个栈底互同。双端队列中从一端入队的元素即允许在本端出队也允许在另一端出队。
1.2.2栈和队列的顺序存储结构
1.栈的顺序存储结构
使用数组保存的栈称为顺序栈
在顺序栈中入栈及出栈均不需要移动元素操作的时间复杂度都是O1的。
2.队列的顺序存储结构
采用数组作为队列的存储结构时为避免入队出队时带来的元素移动需要采用循环存储方式。 若队列保存在一堆数组A[0],A[1],‘’‘’,A[n-1]中数组首位相接将A[0]看作是A[n-1]的后续即在逻辑上将一堆数组看作是一个环。这样的队列称为循环队列“循环”意味着队列采用一个“环”状结构保存。当访问到达数组尾时再重新从数组头开始访问元素 数组空间可以重复利用。实际生活中跑到的利用就是一种“循环”方式下入队操作和出队操作均不导致元素的移动故操作的时间复杂度都是O(1)的。
1.2.3 栈和队列的链式存储结构
顺序表有两个不足之处第一元素插入和删除时都可能导致数组中元素移动。因为栈的队列知允许在线性表的断点处进行插入和删除所以避免了数据的移动第二顺序表的大小受数组空间的限制。 这个问题在顺序栈及循环队列中仍存在。一旦数组分配了空间栈及队列的最大容量就确定下来。同时保存在栈及队列中的元素个数不能超过数组大小的限制。
当不能预知同时保护在栈或队列中的元素个数时通常使用链式存储结构。
1.栈的链式存储结构
使用链式保存的栈称为链式栈。栈顶指针top也是表头指针入栈和出栈均操作在表头位置所以时间复杂度都是O(1)的。 链式栈实际上是链表的一个简化版本。
2.队列的链式存储结构
使用链表保存的队列称为链式队列。队列的操作位置在其两端队头指针front指向队头元素队尾指针rear指向队尾元素入队和出队时通过两个指针可快速找到操作位置故入队操作和出队操作的时间复杂也是O(1)的。
链式队列实际上是带头尾指针的链表的一个简化版本。
1.2.4 栈和队列的应用
栈的应用非常广泛例如使用键盘输入时调用回退键在程序中调用其他方法中缀表达式转变为后缀表达式后缀表达式的计算表达式中括号的匹配检查迷宫程序的实现树的遍历图的深度优化搜索等。
1.表达式中括号的匹配检查
编译程序计算程序中表达式的结果时要先检查表达式的正确性其中的一项是检查括号匹配的正确性。一对括号的左半部分称为开括号右半部分称为闭括号若开括号与闭括号的个数相等且嵌套正确表示括号匹配正确否则匹配错误。检查过程中使用栈来保存开括号从左至右依次扫描表达式中的括号ch,并进行判断 若ch是开括号ch入栈 若ch是闭括号则于栈顶符号比较若属于同一类例如栈顶是‘{’且ch‘}’则出栈本对括号匹配成功继续读入下一符号否则报告错误 当ch是表达式结束符时若栈为空表达式括号匹配正确否则匹配错误 若ch是其他符号忽略。 对 栈的访问过程中需要判断栈是否为空或已满。当需要与栈顶符号进行比较而栈为空时表明在开括号出现之前先遇到了闭括号表达式中括号匹配不正确当表达式结束而栈不为空时表示开括号数多于闭括号数表达式中括号匹配不正确若栈顶符号与当前读入的符号不是同一类时表示括号的嵌套关系不正确等。
2.计算后缀表达式
日常书写习惯中算术表达式常写为中缀infix形式即二元运算符放在它的两个操作数中间例如45,这样的表达式称为中缀表达式。计算中缀表达式时要依赖优先级规则来判定操作执行的次序程序处理复杂。将二元运算符放到两个操作数后面的形式称为后缀postfix形式相应地表达式称为后缀表达式。例如45对应的后缀表达式为4 5 。后缀表达式中不需要使用括号。
一般来讲后缀表达式的计算逻辑闭中缀表达式的计算逻辑要容易些因为不必考虑优先级规则及括号的情况。 表达式中运算的出现次序足以判断其计算次序因此程序设计语言编译器及实时环境在其内部设计时常使用后缀表达式计算过程中使用栈来保存中间结果及最终结果。
计算后缀表达式的算法如下自左至右扫描表达式依次识别每个符号ch(运算符或操作数)。如果ch是操作数将ch压入栈中;如果ch是运算符则依次弹出栈顶的两个元素弹出的第一个元素作为第二操作数弹出的第二个元素作为第一操作数执行ch表示的操作并把计算结果再压入栈中。当到达表达式的结尾时栈中唯一的元素就是表达式的结果。任何时候如果想从栈中弹出两个元素而栈中不足两个元素时表明后缀表达式是不正确的具体来说是运算数的个数不足。同样地如果到达表达式的结尾但是栈中还能一个以上的元素时表达式也是不正确的具体来说运算符的个数不足。
3.二叉树的层序遍历
二叉树的层序遍历过程中使用队列保护当前正遍历的层及其下一层的相关结点。
4.对顶栈
可以使用一个一堆数组来同时存储两个栈数组两端分别是两个栈的栈底每个站从各自的栈底中间延申。这样的两个栈称为对顶栈数组元素的个数取两个栈中同时保存元素的最大值。在对顶栈中进行插入。删除操作时两个栈顶的变化方向是相反的并且判断栈满的方式也与普通的顺序栈不同当公用空间没有时两个栈均满。
5.双端队列
扩展队列的定义减少其操作限制允许在队列的两端都可进行入队及出队操作这样的队列称为双端队列。实际上双端队列可以看成是一对对底栈。
若一端允许进行入队及出队操作另一端仅允许出队操作这样的队列称为输入受限的双端队列类似地若一端允许惊醒入队及出队操作另一端仅允许入队操作这样的队列称为输出受限的双端队列。
1.2.5特殊矩阵的压缩存储
n.阶矩阵采用二维数组存储。C及C语言中采用行主序的方式保存数组元素。 二维数组也以线性方式保存在一段连续空间中即先依次保存矩阵的第一行元素再依次保存矩阵的第二行元素以此类推直到保存矩阵的第n行元素。
1.对称矩阵的压缩存储
对于n阶对称矩阵其元素以对角线为界对称相等因此n2个元素仅需要n(n2)/2个存储单元。
2.三角矩阵的压缩存储
另一端仅允许出队操作这样的队列称为输入受限的双端队列类似地若一端允许惊醒入队及出队操作另一端仅允许入队操作这样的队列称为输出受限的双端队列。
1.2.5特殊矩阵的压缩存储
n.阶矩阵采用二维数组存储。C及C语言中采用行主序的方式保存数组元素。 二维数组也以线性方式保存在一段连续空间中即先依次保存矩阵的第一行元素再依次保存矩阵的第二行元素以此类推直到保存矩阵的第n行元素。
1.对称矩阵的压缩存储
对于n阶对称矩阵其元素以对角线为界对称相等因此n2个元素仅需要n(n2)/2个存储单元。
2.三角矩阵的压缩存储
