JONY

线性表 线性表(linear list)是种非常简单的结构。一个线性表等价于一个集合与该集合所有元素的一个排序，可写成\([a,b,c,…]\)的形式，方括号中的内容既表示线性表中的全部元素，也表示这些元素的排序。对于线性表中任意前后相邻的\(x_i\)与\(x_{i+1}\)元素，通常称\(x_i\)的后继为\(x_{i+1}\)，\(x_{i+1}\)的前驱为\(x_i\)，首个元素的前驱为空，最后一个元素的后继为空。需注意到线性表本身是个逻辑概念，其不限制也不依赖于具体实现，就类似于集合这样的概念，在讨论算法时经常会遇到这种类型的概念。 在算法领域人们更关心线性表的实现，因为线性表本身十分简答。 实际的计算机硬件基本都采用相同的“内存模型”，其包括由确定的\(K\)个连续整数构成的\(K\)个内存地址，每个地址都存储相同规模的数据。读取内存的流程大致是先提供内存地址给内存，一段时间后内存返回该地址中的数据，写入内存的流程大致是同时提供地址和数据给内存，一段时间后内存完成写入。在这种“内存模型”下，线性表的实现方案通常是数组或链表，这两种方案都有各自的优缺点。当然如果不采用这种“内存模型”，也有一定的可能会用其他方案来实现线性表。… 阅读全文

栈(Stack)栈这种结构强调的是栈运算，实现了如下3种运算的结构就是栈： 1) \(push(x)\)：存入\(x\)元素(也称为压栈)； 2) \(pop()\)：删除最后一次存入的元素并返回该元素(也称为弹栈)； 3) \(top()\)：返回最后一次存入的元素(也称为栈顶，所以写作top)； 直观上栈像狭长的储物箱，只有一面开口，只能看到最顶上的物品，取最里面的物品时要自顶向下的先拿出所有其他物品。这3种运算使栈中的元素在逻辑上也蕴含着前驱后继关系，所以栈也是线性表。但栈不必像数组和链表那样，必须提供查看任意元素、在任意元素间插入、删除任意元素等各种运算，所以直观上栈并不像一张“表”，而像是有3个运算的“黑箱”，所以栈也被称为操作受限的线性表。当然如果在链表或数组的基础上实现栈运算的话，那也可以作为栈。栈作为后进先出(LIFO,… 阅读全文

直接寻址表(Direct Address Table)数组是把所有元素按顺序存储在连续内存地址中的，如果单个元素需要的内存地址数越多，数组整体需要的内存地址数就要成倍增长。显然同样大小的连续内存比不连续内存更“稀缺”，因为即使有足够的内存，也不代表有足够的连续内存。那么为更合理的使用内存，在元素数量多且单个元素很大的场景下就不应直接使用大数组存储，而是应该考虑使用链表，但如果对按索引访问的性能有高的要求，就需要结合数组和链表的特点构造一种新的称为直接寻址表的结构。直接寻址表本身是个数组，但元素不存入数组，而是存入不连续的其他内存区域，数组中存储的是元素的内存地址。 直接寻址表的各个位置称为槽(slot)，其允许索引不连续(索引1有元素、索引2没元素、索引3又有元素……)，所以把索引改称为关键字(key)。当元素不大时，也允许不存地址，而是依然存元素本身。所以数组可看作直接寻址表的特例，很多时候甚至不区分这两个概念，因为直接寻址表仅多了1次按地址找元素的步骤，和数组的代价是没有区别的。直接寻址表还有些其他好处，数组创建时必须确定每个元素占用的固定大小。直接寻址表就自由的多，由于其存储的只是地址，所以元素的大小可以不同。事实上很多程序语言中“基于数组”的数据类型更接近直接寻址表而不是数组，比如Python的list。… 阅读全文

摊还分析(Amortized Analysis) 通常算法分析的“目标问题”都是给定1个规模为\(n\)的数据结构和1个算法，分析该算法关于\(n\)的代价并表示为\(O(f(n))\)。如果在此基础上继续分析“在该数据结构连续执行\(k\)次该算法”的问题，用乘法可得\(O(kf(N))\)，其中\(N\)是\(k\)次中最大的\(n\)。由于\(O\)是上界所以该结论完全正确，但可能不够“精确”(离确界不够近)。因为没考虑到每次算法执行后，数据结构本身的变化。如果考虑到，则可能得到小于\(O(kf(N))\)的界，并且其更能反映出该场景下的真实代价。 举例说明上述观点，假设有个“包含\(popAll\)运算”的栈，其除了能\(O(1)\)完成\(push,pop,top\)，还支持\(popAll\)运算，其实现是“循环\(pop\)直到栈顶为空”，如果\(popAll\)执行前栈中有\(n\)个元素，\(popAll\)的代价就是\(O(n)\)。然后带入场景“这个栈是某算法的一部分，该算法会多次调用这个栈的\(push,pop,popAll\)，由于这个算法很复杂，不能确定每次都调用什么运算，也不能确定每次调用前栈的元素数。只知道算法开始时栈是空的”。由于不知道元素数，\(popAll\)的\(O(n)\)代价就不精确了，但我们很想衡量这个栈在该算法中的性能表现，所以构造下面这个需要做算法分析的“目标问题”：… 阅读全文

反转数组 该问题是“给定一个数组，将其元素按从右到左重新排列，比如输入\([1,2,3]\)，应该得到\([3,2,1]\)。要求在原数组上反转，且只能占用常数额外空间”。这个问题可通过以中心为对称轴，从最外层开始反转，比如\([1,2,3,4,5]\)，会先变成\([5,2,3,4,1]\)，然后变成\([5,4,3,2,1]\)，两轮即可完成。然后考虑问题的边界，当数组有奇数个元素，两索引最后会在中心元素处相遇，当数组有偶数个元素，两索引最后会出现右边小于左边的情况。所以当右边的索引小于等于左边的索引时就意味着算法结束。该算法的时间复杂度是\(O(n)\)，其中\(n\)为数组中元素的个数。具体程序实现如下。 Python def reverse(arr): i, j = 0, len(arr) - 1 while… 阅读全文

反转链表该问题是“给定链表(表头节点)，将链表逆序，要求原地完成(由原节点构成)且只占常数额外空间”。先考虑递归程序，思路是递归进入到链表尾，然后在每次递归退出时，让外层递归把当前节点原后继的\(next\)反过来指向当前节点。需注意最后一次递归结束后，其当前节点的\(next\)没有发生变化，所以要特别的将其指向空，那为了方便干脆在每轮递归结束前都加一步把当前节点的\(next\)指向空。然后是如何记录新表头，上述递归没有用到函数返回值，可以一层层返回新表头。 Python def f(node): if not node.next: return node newHead = f(node.next) node.next.next = node node.next = None return newHead 1234567 def… 阅读全文

栈的最小值 该问题是“实现一个空栈存储数值，其支持一般的\(push,pop\)，以及用于求当前栈中最小值的\(min\)运算，要求3个运算的时间复杂度都是\(O(1)\)”。问题要求找最小值的代价是\(O(1)\)，那只能在\(push,pop\)的过程中用额外空间维护一些关于最小值的信息。假设栈只有\(push\)运算，那只需1个额外变量就能记录栈中的最小值，但当存在\(pop\)运算时，如果最小值元素被\(pop\)了，那就只能遍历寻找新的最小值，代价就不再是\(O(1)\)。这里就需要注意到栈的一个性质，即“每次\(pop\)后栈会回到最后一次\(push\)前的状态”。这说明如果用一个结构顺序记录每次\(push\)后的“历史最小值”，那么\(pop\)后的最小值就是这个结构中的倒数第2条记录，然而倒数第一条记录因为\(pop\)结束已经没意义了，应从中删除，这又说明这个结构也很适合用栈实现。… 阅读全文

两个栈实现队列 该问题是“有2个空栈\(s_1,s_2\)，出入栈运算都是\(O(1)\)代价的，要求用这2个栈实现一个队列，出入队运算都是\(O(1)\)摊还代价的”。用2个栈实现队列的思路很简单，把一组元素入栈\(s_1\)再出栈入栈到\(s_2\)就能把\(s_1\)的栈底变成\(s_2\)的栈顶，进而就能实现队头的出队。这里具体来看如何实现，首先对于入队运算，直接入栈\(s_1\)即可，对于出队运算，当\(s_2\)为空时把\(s_1\)的元素全部出栈并依次入栈\(s_2\)，最后弹出\(s_2\)的栈顶作为队头出队。当\(s_2\)非空，直接弹出\(s_2\)的栈顶作为队头出队即可。 上述过程中，每个元素的入队都是1次\(s_1\)的入栈，出队都是3次的\(s_1\)出栈、\(s_2\)入栈、\(s_2\)出栈操作。对于\(2n\)次队列操作，最好的情况是发生\(2n\)次入队操作，最坏的情况是发生\(n\)次入队、\(n\)次出队，对于最坏的情况，也仅意味着发生了\(4n\)次栈操作。所以此时的总代价是\(O(n)\)，每次操作的摊还代价是\(O(1)\)。下面是具体程序实现。… 阅读全文