本文部分内容参考的博客。

• Python中提供了list容器，可以当作数组使用。但列表中的元素可以是任何对象，因此列表中保存的是对象的指针，这样一来，为了保存一个简单的列表[1,2,3]。就需要三个指针和三个整数对象。对于数值运算来说，这种结构显然不够高效。
• Python虽然也提供了array模块，但其只支持一维数组，不支持多维数组，也没有各种运算函数。因而不适合数值运算。
• NumPy的出现弥补了这些不足。

（——摘自张若愚的《Python科学计算》）

• 一维数组打印成行，二维数组打印成矩阵，三维数组打印成矩阵列表

——《数据结构题集》-严蔚敏.吴伟民版

      本习题文档的存放目录：数据结构\▼配套习题解析\▼03 栈和队列

      文档中源码的存放目录：数据结构\▼配套习题解析\▼03 栈和队列\▼习题测试文档-03

3.1?若按教科书3.1.1节中图3.1(b)所示铁道进行车厢调度（注意：两侧铁道均为单向行驶道），则请回答：

(1) 如果进站的车厢序列为123，则可能得到的出站车厢序列是什么？

(2) 如果进站的车厢序列为123456，则能否得到435612和135426的出站序列，并请说明为什么不能得到或者如何得到（即写出以‘S’表示进栈和以‘X’表示出栈的栈操作序列）。

3.2?简述栈和线性表的差别。

3.3?写出下列程序段的输出结果（栈的元素类型SElemType为char）。

3.4?简述以下算法的功能（栈的元素类型SElemType为int）。

3.5?假设以S和X分别表示入栈和出栈的操作，则初态和终态均为空栈的入栈和出栈的操作序列可以表示为仅由S和X组成的序列。称可以操作的序列为合法序列（例如，SXSX为合法序列，SXXS为非法序列）。试给出区分给定序列为合法序列或非法序列的一般准则，并证明：两个不同的合法（栈操作）序列（对同一输入序列）不可能得到相同的输出元素（注意：在此指的是元素实体，而不是值）序列。

试证明：若借助栈由输入序列12…n得到的输出序列为p1p2…pn(它是输入序列的一个排列)，则在输出序列中不可能出现这样的情形：存在着i<j<k使p_j<p_k<p_i。

3.7?按照四则运算加、减、乘、除和幂运算(↑)优先关系的惯例，并仿照教科书3.2节例3-2的格式，画出对下列算术表达式求值时操作数栈和运算符栈的变化过程：

3.8?试推导求解n阶梵塔问题至少要执行的move操作的次数。

3.9?试将下列递推过程改写为递归过程。

3.10?试将下列递归过程改写为非递归过程。

3.11?简述队列和堆栈这两种数据类型的相同点和差异处。

3.12?写出以下程序段的输出结果（队列中的元素类型QElemType为char）。

3.13?简述以下算法的功能（栈和队列的元素类型均为int）。

3.14?若以1234作为双端队列的输入序列，试分别求出满足以下条件的输出序列：

    (1) 能由输入受限的双端队列得到，但不能由输出受限的双端队列得到的输出序列。

    (2) 能由输出受限的双端队列得到，但不能由输入受限的双端队列得到的输出序列。

    (3) 既不能由输入受限的双端队列得到，也不能由输出受限的双端队列得到的输出序列。

3.15?假设以顺序存储结构实现一个双向栈，即在一维数组的存储空间中存在着两个栈，它们的栈底分别设在数组的两个端点。试编写实现这个双向栈tws的三个操作：初始化inistack(tws)、入栈push(tws,i,x)和出栈pop(tws,i)的算法，其中i为0或1，用以分别指示设在数组两端的两个栈，并讨论按过程(正/误状态变量可设为变参)或函数设计这些操作算法各有什么有缺点。

3.16?假设如题3.1所属火车调度站的入口处有n节硬席或软席车厢（分别以H和S表示）等待调度，试编写算法，输出对这n节车厢进行调度的操作（即入栈或出栈操作）序列，以使所有的软席车厢都被调整到硬席车厢之前。

3.17?试写一个算法，识别一次读入的一个以@为结束符的字符序列是否为形如‘序列1&序列2’模式的字符序列。其中序列1和序列2中都不含字符‘&’，且序列2是序列1的逆序列。例如，‘a+b&b+a’是属该模式的字符序列，而‘1+3&3-1’则不是。

3.18?试写一个判别表达式中开、闭括号是否配对出现的算法。

3.19?假设一个算数表达式中可以包含三种符号：圆括号“(”和“)”、方括号“[”和“]”和花括号“{”和“}”，且这三种括号可按任意的次序嵌套使用（如：…[…{…}…[…]…]…[…]…(…)…）。编写判别给定表达式中所含括号是否正确配对出现的算法（已知表达式已存入数据元素为字符的顺序表中）。

1…n)表示一个图像区域，g[i,j]表示该区域中点(i,j)所具颜色，其值为从0到k的整数。编写算法置换点(i₀,j₀)所在区域的颜色。约定和(i₀,j₀)同色的上、下、左、右的邻接点为同色区域的点。

3.21?假设表达式有单字母变量（下面算法中将改为只有一位的数字）和双目四则运算符构成。试写一个算法，将一个通常书写形式且书写正确的表达式转换为逆波兰表达式。

3.22?如题3.21的假设条件，试写一个算法，对以逆波兰式表示的表达式求值。

3.23?如题3.21的假设条件，试写一个算法，判断给定的非空后缀表达式是否为正确的逆波兰表达式，如果是，则将它转化为波兰式。

3.24?试编写如下定义的递归函数的递归算法，并根据算法画出求g(5,2)时栈的变化过程。

3.25?试写出求递归函数F(n)的递归算法，并消除递归：

3.26?求解平方根√A的迭代函数定义如下： 

其中，p是A的近似平方根，e是结果允许误差。试写出相应的递归算法，并消除递归。

(1) 写出递归算法；

(2) 写出非递归算法；

(3) 根据非递归算法，画出求akm(2,1)时栈的变化过程。

3.28?假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾元素结点（注意不设头指针），试编写相应的队列初始化、入队列和出队列的算法。

3.29?如果希望循环队列中的元素都能得到利用，则需设置一个标志域tag，并以tag的值为0和1来区分，尾指针和头指针值相同时的队列状态是“空”还是“满”。试编写与此结构相应的入队列和出队列的算法，并从时间和空间角度讨论设标志和不设标志这两种方法的使用范围（如当循环队列容量较小而队列中每个元素占的空间较多时，哪一种方法较好）。

3.30?假设将循环队列定义为：以域变量rear和length分别指示循环队列中队尾元素的位置和内含元素的个数。试给出此循环队列的队满条件，并写出相应的入队列和出队列的算法（在出队列的算法中要返回队头元素）。

3.32?试利用循环队列编写求k阶菲波那契序列中前n+1项的算法，要求满足f_n≤max而f_n+1≥max，其中max为某个约定的常数。（注意：本题所用循环队列的容量仅为k，则在算法执行结束时，留在循环队列中的元素应是所求k阶菲波那契序列中的最后k项）

3.31?假设称正读和反读都相同的字符序列为“回文”，例如，‘abba’和‘abcba’是回文，‘abcde’和‘ababab’则不是回文。试写一个算法判别读入的一个以‘@’为结束符的字符序列是否是“回文”。

3.33?在顺序存储结构上实现输出受限的双端循环队列的入列和出列（只允许队头出列）算法。设每个元素表示一个待处理的作业，元素值表示作业的预计时间。入队列采取简化的短作业优先原则，若一个新提交的作业的预计执行时间小于队头和队尾作业的平均时间，则插入在队头，否则插入在队尾。

3.34?假设在如教科书3.4.1节中图3.9所示的铁道转轨网的输入端有n节车厢：硬座、硬卧和软卧（分别以P，H和S表示）等待调度，要求这三种车厢在输出端铁道上的排列次序为：硬座（P）在前，软卧（S）在中，硬卧（H）在后。试利用输出受限（只允许队头出列）的双端队列对这n节车厢进行调度，编写算法输出调度的操作序列：分别以字符‘E’和‘D’表示对双端队列的头端进行入队列和出队列的操作；以字符A表示对双端队列的尾端进行入队列的操作。

数学上，一个m×n的矩阵是一个由m行n列元素排列成的矩形阵列。矩阵里的元素可以是数字、符号或数学式。以下是一个由6个数字元素构成的2行3列的矩阵：

计算机科学中，三维动画制作也需要用到矩阵。矩阵的运算是数值分析领域的重要问题。将矩阵分解为简单矩阵的组合可以在理论和实际应用上简化矩阵的运算。对一些应用广泛而形式特殊的矩阵，例如稀疏矩阵和准对角矩阵，有特定的快速运算算法。

在数值分析中，稀疏矩阵（Sparse matrix），是其元素大部分为零的矩阵。反之，如果大部分元素都非零，则这个矩阵是稠密的。在科学与工程领域中求解线性模型时经常出现大型的稀疏矩阵。

在使用计算机存储和操作稀疏矩阵时，经常需要修改标准算法以利用矩阵的稀疏结构。由于其自身的稀疏特性，通过压缩可以大大节省稀疏矩阵的内存代价。更为重要的是，由于过大的尺寸，标准的算法经常无法操作这些稀疏矩阵。

稀疏矩阵主要用两种数据结构来表示，三元组和十字链表。

在学习线性代数的时候，经常用到矩阵。在C语言中，表示矩阵的最直观形式就是二维数组。然而在实际应用中，很多高阶矩阵中的非零元素非常少，这个时候如果继续使用二维数组存储，那么就会浪费很多存储空间。
在数据结构中，我们用三元组存储稀疏矩阵。三元组定义为(i,v,j)，这三个值一次表示矩阵的行、列、值。

定义三元组（行，列，值）

定义稀疏矩阵（三元组数组，行最大值，列最大值，有效值个数）

矩阵的转置（实际就是将三元组的行值和列值进行交换）

十字链表（Orthogonal List)是有向图的另一种链式存储结构。该结构可以看成是将有向图的邻接表和逆邻接表结合起来得到的。用十字链表来存储有向图，可以达到高效的存取效果。

定于一个简单布尔型（毕竟C语言:-(）

定义节点（一个值和两个指针域）

定义稀疏矩阵（最大行值，最大列值，两个头指针，一个代表行链表，一个代表列链表）

找到节点所在行位置和列位置

将节点分别插入行链表和列链表

插入节点（把前面几个小功能汇集在一块）

显示稀疏矩阵（按列显示）

最后还是销毁 O(∩_∩)O哈哈~