第6章
数据结构基础
第6章
数据结构基础
62链表63二叉树64图
【教学内容相关章节】61栈和队列【教学目标】（1）熟练掌握栈和队列及其实现；（2）了解双向链表及其实现；（3）掌握对比测试的方法；（4）掌握随机数据生成方法；（5）掌握完全二叉树的数组实现；（6）了解动态内存分配和释放方法及其注意事项；（7）掌握二叉树的链式表示法；（8）掌握二叉树的先序、后序和中序遍历和层次遍历；（9）掌握图的DFS及连通块计数；（10）掌握图的BFS及最短路的输出；（11）掌握拓扑排序算法；（12）掌握欧拉回路算法。【教学要求】掌握栈和队列及其实现；掌握对比测试的方法；掌握随机数据生成方法；掌握完全二叉树的数组实现和链式表示法；掌握二叉树的先序、后序和中序遍历和层次遍历；掌握图的DFS和BFS遍历；掌握拓扑排序算法；掌握欧拉回路算法。【教学内容提要】本章介绍基础数据结构，包括线性表、二叉树和图。有两种特殊的线性表：栈和队列。对于树型结构主要讨论二叉树，还有二叉树的先序、中序和后序的遍历方式。对于图主要讨论图的DFS和BFS的遍历方法。这些内容是很多高级内容的基础。如果数据基础没有打好，很难设计正确、高效的算法。【教学重点、难点】教学重点：（1）掌握栈和队列及其实现；（2）掌握对比测试的方法；
第159页
f第6章
数据结构基础
（3）掌握随机数据生成方法；（4）掌握完全二叉树的数组实现和链式表示法；（5）掌握二叉树的先序、后序和中序遍历和层次遍历；（6）掌握图的DFS和BFS遍历；（7）掌握拓扑排序算法和欧拉回路算法。教学难点：（1）掌握完全二叉树的数组实现和链式表示法；（2）掌握二叉树的先序、后序和中序遍历和层次遍历；（3）掌握图的DFS和BFS遍历；（4）掌握拓扑排序算法和欧拉回路算法。【课时安排（共9学时）】61栈和队列62链表63二叉树64图
第160页
f第6章
数据结构基础
61
栈和队列
线性表是“所有元素排成一行”的数据结构。除了第一个元素之外，所有元素都有
一个“前一个元素”；除了最后一个元素外，所有元素都有“后一个元素”。线性结构是重要的算法和数据结构的基础。下面介绍两种特殊的线性表：栈和队列。
611
卡片游戏
桌上有叠牌，从第一张牌（即位于顶面的牌）开始从上往下依次编号为1～
。当至少还剩两张牌时进行以下操作：把第一张牌扔掉，然后把新的第一张放一整叠牌的最后。输入
，输出每次扔掉的牌，以及最后剩下的牌。样例输入：7样例输出：1r