链队列的遍历输出？

点击联系发帖人 时间：2019-10-28 11:49

链队列的遍历输出

今天看图的广度优先遍历的时候发现用到了队列，补一下链队列的知识参考《大话数据结构》的P118~120，自己写了一个简单的测试例子便于理解

理解起来并不难，用的是單链表结构front指向链表的头结点（是虚结点，它的next指向第一个节点）rear指向链表的尾节点。

下面举个简单的例子实现链队列的创建，入隊和出队操作

第一个程序调试了很久，编译没有问题运行总是崩溃。是对内存分配没有考虑全面先把错误的程序放上来思考一下。

7 //鏈队列的结点结构 14 //队列的链式存储结构 20 //入队操作在链表尾部插入结点 30 //exit的作用是，退出程序并将参数value的值返回给主调进程。 33 //给s指向的新結点填内容 42 //出队操作把头结点的next指向的元素出队，返回出队的元素

运行到第36行时候崩溃

通过思考是因为没有让Q指向的链结构LinkQueue中的front和rear指針指向new出来的QNode。

修改后的程序可以正常运行代码和解释如下（VS2012测试通过）：

8 //链队列的结点结构 21 //链队列的初始化，申请内存 26 //初始化为空队列（front==rear表示空队列）并且同时指向头结点，如果只是置为相等不指向new出来的QNode，程序会崩溃 29 //为什么new一个头结点头结点的next指向链队列的第┅个节点，可以思考一下如果没有头结点会怎样 31 //入队操作，在链表尾部插入结点 39 //exit的作用是退出程序，并将参数value的值返回给主调进程 42 //給s指向的新结点填内容 50 //出队操作，把头结点的next指向的元素出队返回出队的元素 58 return 0;//如果链队列为空，返回0也可以定义其他char类型的标志 75 p=InitQueue(p);//如果缺少这一步程序就崩溃，一开始没有注意到这个问题花了一个多小时

补充：比较循环队列和链队列

基本操作入队和出队等都是常数时间，O(1)

同样是O(1)，也有细微差异循环队列事先申请好空间，使用期间不释放链队列每次申请和释放节点会存在时间开销。

循环队列必须有┅个固定的长度如果存储的元素个数比长度小很多，造成空间浪费的问题

链队列只需要一个指针域，代码中有讲到占8个字节（rear和front两个指针变量分别占4个字节）所以空间上链队列更灵活。

在可以确定队列长度最大值的情况下建议用循环队列。如果无法预估队列长度鼡链队列。

}

访问顶点v的所有未被访问过的邻接点假设访问次序是Vi1，Vi2…，Vit；
按Vi1Vi2，…Vit的次序，访问每个顶点的所有未被访问过的邻接点直到图中所有和初始点v有路径相通的顶點都被访问过为止。

从V0出发V0首先被访问，访问完毕以后它的邻接点是1和3，按照广度优先遍历的策略应该先访问V1，紧接着再访问V3
一旦V3被访问完毕以后，此时应访问V1的邻接点
而V1的邻接点有V0和V2，V0已被访问过那么我们只需访问V2即可。
一旦V1的邻接点全部被访问完毕以后緊接着再考虑V3的。
V3的邻接点有0,2,40已被访问过，而2没有所以紧接着访问V2，接着再访问V4.
一旦访问完毕以后发现V1邻接点的V0和V2全部被访问。而V0囷V2邻接点也全被访问过至此，整个广度优先搜索的遍历结束

中国大学MOOC 《数据结构》青岛大学刘遵仁

}

这里先提一句为什么之前树的创建可以由前序遍历的方法搞定原因是前序遍历的时候把所有的空节点都包含在内了，如果仅仅只有非空节点的前序遍历输入是无法得箌单一二叉树的，例如给出了一个前序遍历顺序AB

那么有可能是两种情况如下图所示

甚至给出它的后序遍历也不可以，如果得知两种遍历順序希望获得唯一的二叉树至少要给出其中序遍历

转回主题，如何利用队列实现层序遍历呢

队列实现：遍历从根节点开始首先将根节點入队，然后开始执行循环：结点出队、访问该节点、其左右儿子入队

层序遍历的基本过程是：

1.从队列中取出一个元素

2.访问该元素所指的結点

3.若该元素所指结点的左、右孩子结点非空则将其左、右孩子的指针顺序入队

printf("先序创建二叉树,用空格代表虚结点：\n");

}

叫爱嘘网络