计算机软件基础(自考本科栈、队列)研究PPT课件

计算机软件基础，第2部分数据结构基础，第9章堆栈，队列和数组，第1部分堆栈，(第1部分)堆栈概念，第1部分。堆栈：后进先出线性表，缩写为后进先出表。顶端：执行插入和删除操作的堆栈末端(即改变末端)。底部：堆栈的固定端。栈的存储结构：顺序存储和链式存储。a，B，C，D，E，底部，堆栈外，a，a，B，C，D，E，堆栈容量：一个堆栈可以容纳的元素数，1。堆栈)，3。顺序堆栈的类型，#definem100/将堆栈的最大容量定义为100 structseqstack data type datam；/堆栈最多可容纳m个元素inttop/指向堆栈顶部的指针；1.堆栈。4.顺序堆栈推送的基本操作，1。堆栈。5.顺序堆拉的基本操作，1。堆栈。3.链式堆栈。1.形式。Ls，A，b，x，非空堆栈，堆栈顶部元素，堆栈底部元素，Ls，空堆栈，链堆栈：没有标题节点的单个链表(堆栈顶部指针直接指向堆栈顶部元素)。一，堆栈，三，链堆栈，二，类型定义，结构节点 datatypedatastructnode * next*Ls。(1)堆叠，(3)链式堆叠，(3)堆叠操作，(1)链式堆叠，(3)堆叠操作，(4)堆叠取出操作，(1)铁路调度系统，示例9-1:三列列车A、B和C一列一列堆叠。有多少种堆叠顺序，它们是什么？(4)使用堆栈，例9-2有a，b，c，d，e，f六列一个接一个的堆栈，我们可以得到如下的堆栈顺序：(1)CBE fa(2)CDF aeb，1，stack，(2)算术表达式求值，对于算术表达式求值，主要解决算术运算符的优先级问题，有以下规则：首先，乘法和除法运算，然后是加减运算(乘法和除法的优先级大于加减运算)；对于具有相同优先级的运算符，从左到右进行计算。要更改优先级，请使用括号。对于带括号的表达式，首先计算括号内的内容，然后计算括号外的内容。在计算表达式的过程中，应该保存操作数和运算符。在这种情况下，可以定义两个堆栈，一个用于保存操作数，另一个用于保存运算符。(4)栈的使用，(1)栈，例9-3已知x=9 4*6/8-5，试写栈的表达式求值过程，(4)栈的使用，例9-4分析以下程序，写操作结果，解释其功能。void f(intn) if(n1) f(n/2)；printf(,n%2)；，main() f(26)；(1)堆栈，示例9-5使用堆栈来反转单个链表。(4)堆栈、空隙、标题的使用；p=下一个标题；同时(p！=空推送(s，p-数据)；p=p-next p=head-next；同时(！空的(s) p-数据=pop(s)；p=p-下一个；表格：队列为空，进入队列，a，b，c注：进入队列时，头指针保持固定，尾指针向后移动。表格：队列已满，在队列之外，a，b，c，d，e，f，a，b，c，d，e，e，f。注意：当队列之外时，尾部指针保持固定，头部指针向后移动。(2)队列，(2)顺序队列，(2)类型定义：# definem 100 structseqq data type datam；intfrontintrear sq(2)队列，(3)序列队列的基本操作-排队，(2)队列，(4)序列队列的基本操作-出列，(2)队列，(3)循环队列，(1)序列队列的假满：当r=m-1，f不等于-1时，序列队列发生假满。例如：f，r，2，queue，3，circular queue，2，circular queue:通过连接顺序队列的头部和尾部而形成的循环队列称为循环队列，如图所示：0，1，2，3，4，5，6，7，8，9，a，b，c，f，r，以及，描述：(1)传入队列和传出队列都以逆时针方向前进；(2)牺牲f所指的空间。(2)队列(3)循环队列(3)循环队列的几个关键点：(1)循环队列为空的条件：front=原因；(2)全循环队列的条件：前=(后1)% m；(3)当循环队列满时，元素数为m-1；(4)通常，循环队列中的元素数量是(原因前端m)% m；a，b，x，非空，第一个元素节点，最后一个元素节点，空，2。特点：前、前、头节点，(1)是单链表；(2)它是一个队列，入口在R后面，出口在头节点后面；(2)队列，(5)队列应用，(3)循环队列的几个关键点：(1)循环队列为空的条件：front=原因；(2)全循环队列的条件：前=(后1)% m；(3)当循环队列满时，元素数为m-1；(4)通常，循环队列中的元素数量是(原因前端m)% m；(2)队列(3)循环队列(3)循环队列的几个关键点：(1)循环队列为空的条件：front=原因；(2)全循环队列的条件：前=(后1)% m；(3)当循环队列满时，元素数为m-1；(4)通常，循环队列中的元素数量是(原因前端m)% m；(1)二维数组的运算，(2)二维数组的存储结构，(1)基于行的序列的存储方法，(2)基于列的序列的存储方法，(2)二维数组的元素地址的计算，如例9-6所示，数组A108是已知的，每个元素占用4个字节，数组的第一个地址是1000，试着分别找到基于行的序列和基于列的序列，元素A5的地址例如9-7，二维阵列910是已知的。让我们问一下哪一个元素A85按行存储相同的地址，哪一个元素按列存储相同的地址。(1)基本概念，1。特殊矩阵，2。矩阵的压缩存储不会将空间分配给零个元素，并且只有一个空间分配给相同的元素。矩阵压缩存储要解决的问题是有n阶特殊矩阵a，非零元素按行顺序存储在一维数组b中。如果Aij=Bk1) I和j已知，则计算k。2)给定K，求I和J。(2)特殊矩阵，1.3对角矩阵，1)已知I，J，求K。K=3i-1J-I 1=2i J知道K，求I，j. I=(k1)/3 j=k-2i三对角矩阵压缩存储至少需要3n-2个存储空间。四、特殊矩阵的压缩存储，(二)特殊矩阵，1。三对角矩阵，例9-8如果已知B0的存储地址是1000，每个元素占用3个字节，那么B中三个对角矩阵A压缩存储元素A5，4的地址是多少？k=2i j=2*5 4=14，4，特殊矩阵的压缩存储，(2)特殊矩阵，2。三角矩阵，1)已知的I，j，求k，(2)特殊矩阵，(2)三角矩阵，(1)已知的I，j，k，上三角矩阵，4，特殊矩阵的压缩存储，(2)特殊矩阵，2。三角形矩阵，从，k=19。示例9-9通过按压三角形阵列，对称阵列A被压缩并存储到从B开始的一维阵列中0。众所周知，0的第一个地址是1000，每个元素占用4个字节。矩阵A4、5和5的存储地址是什么？(无线电1，2009.4)当按照1、2、3、4和5的顺序堆叠时，不可能的堆叠顺序是()。A1，2，3，4，5B2，3，4，5，1C5，4，3，2，1D5，4，1，2，3，2。(无线电2010.4)如果堆栈入口数据元素序列是A、B、C、D，那么不可能的堆栈出口序列是()。Aa，b，c，dBc，b，a，dCd，c，b，aDd，b，c，a，历年真题，3。(2009.4填空)在有m个节点的循环队列中，头指针在前，尾指针在后。判断循环队列已满的条件。实现递归算法所需的数据结构是。如果循环队列使用数组数据m来存储元素值，并且前后分别用作头指针和尾指针，则判断循环队列为空的条件是。有了知识，一个人将拥有各种各样的分析能力和辨别是非的能力。因此，我们应该努力