计算之魂在线阅读(计算之魂作者吴军)

本文节选自《计算之魂》电子版：

/第2章/逆向思考一一从递推到递归/计算机科学中所说的队列和我们生活中相应的概念是一致的。比如要对一段视频进行处理，我们需要把它变成一帧帧的图像，然后按照时间顺序一个个送入程序中，按照先来后到的顺序逐一处理。处理后，再合并、拼接成完整的视频。由于在视频文件中，后一帧的内容和前一帧有相关性，因此先后的顺序必须保持原样，不能随意变动，这就需要有一个先来先服务、先进先出的机制。在计算机中实现队列这种数据结构，通常采一个数组〔或者其他的线性列表)和两个指针。第一个指针指向当前队列中最前面一个数据的位置，因此也被称为头指针;第二个措针指向队列中最后一个数据的位置，也被称为进来，它被放到队列的最后，当然尾指针就要相应地往的数据离开队列后，相应的头指针也要往后挪一个位置，队列中间位置的数据既不能被访问，也不会被处理。队列的数据结构可以大致定义如下:StructoOueue{尾指针。当一个新的数据后挪一个位置;当队列最前面array_of_any_kind_of_data//任意数据类型的数组风3intstart_pointer;//头指针4intend_Poi

计算之魂这本书怎么样

nter;//尾指针这}图2.12示意了元素进出队列后头、尾指针的变化。头指针尾指针mm一LETT|5头指针尾指针加入1、7、7之后人|人|头指针尾指针取出5、2之后刘贡o|1二图2.12”一个典型的队列，以及元素进出队列后头、旦指针的变化085/计算之魂//利用队列这种数据结构，就可以很容易地实现“一排一排地”横向扫描遍历二叉树的算法了。这种算法是前面提到的广度优先算法，它的伪代码如下(在算法中我们用到一个队列queue):1BreadthFirstTraverseTree(BinaryTreetree){2if(tree=NIL)return;i//如果树为室，不做任何操作，直接返匠3，//在队列中加人一个新的数据，相应尾指针的调整是自动进行的4“将根节点送到队列sueue中;5。while(队列queue不为空)6可89取出队列sueue中的头一个数据noede(即二叉树的某个节点)，if(noqe.1left_subtree!=NIL){//node的左子树不是空树将node.1Lleft_subtree放进队列queue:;】10if(

如何评价计算之魂的书

node.right_subtree!=NIL){//node的右子树不是空树记将node,.right_subtree放进队列gueue:;I2}13本寺如果我们用这个算法遍历图2.8所示的二叉树，一开始会先将根节点1放入队列中，然后在取出根节点时，会放入它的两个子节点2和3;接下来会取出节点2处理，同时将节点4和5放在节点3的后面。这时节点3在队列的最前面，等处理节点3时，会将节点6放在队列的最后，即节点5的后面。处理节点4和5时，由于它们的子节点均为空，因此不会有新的节点加入队列中。等处理节点6时，节点7会放到队列中。最后，在处理节点7之后，不会再有节点进入队列，队列为空，整个算法结束。按照上述节点进入队列和被处理的次序，我们就完成了广度优先遍历整棵二叉树的过程。队列这种数据结构和本章重点介绍的递归无关，但是和堆栈形成对比，它们可以放在一起学习理解，因此我们在介绍堆栈时，顺便介绍了队列。除了用于实现递归的问题，堆栈的另一大应用场景是实现程序中不同功能模块的相互调用。今天几乎所有的计算机程序都是由一个个功能模块(通常被称为函数或者086

计算之魂笔记

综上：计算之魂作者吴军值得推荐阅读