C语言程序设计基础电子教案 第6章 数据结构

第6章数据结构教案教学任务理解数据结构在程序设计中的作用。栈、队列和二叉树的概念。栈的顺序存储结构和链式存储结构。队列的顺序存储结构和链式存储结构。二叉树的顺序存储结构和链式存储结构。授课课时总时长：学时包括：课堂讲授学时；实训学习学时一、教学分析教学重点栈、队列及二叉树等常用的数据结构的特点教学难点握栈、队列及二叉树等常用的数据结构的基本操作教学方法讲授法+导例教学二、教学基本内容一、栈栈是一种特殊形式的线性表，它的数据元素以及数据元素之间的逻辑关系与线性表相同。栈只能在栈顶进行插入和删除操作，具有后进先出的特性，因此也称为后进先出的线性表，简称LIFO表。一维数组用来存储具有相同类型的数据，类似于数学中的向量。向一个栈中插入数据元素的操作称为进栈、入栈或压栈，它把新元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除数据元素的操作称作出栈或退栈，它把栈顶元素删除，使其相邻的元素成为新的栈顶元素。当栈中不包含数据元素时，称为空栈，如下图所示。2．栈的基本操作（1）置空栈：初始化栈，即构造一个空栈，使栈顶top值为-1。（2）进栈：从栈顶压入一个数据元素，该元素作为新的栈顶元素，即栈中增加一个元素。（3）退栈：将栈顶元素从栈中弹出，即删除当前栈顶元素，使其相邻的元素成为新的栈顶元素。（4）取栈顶元素：取栈顶元素的值，与退栈不同，栈顶元素不变。（5）判断空栈：若栈非空返回1，否则返回0。根据存储结构的不同，栈可以分为顺序栈和链栈。顺序栈使用数组作为底层数据结构，因此在栈顶进行插入和删除操作可以通过下标直接访问。对于需要频繁访问栈顶元素的操作，可以提高数据访问的效率。链栈对于内存的管理更加灵活，可以动态地分配内存，更适合用于需要频繁调整大小的应用场景。二、队列队列也是一种运算受限的线性表。队列只能在表的一端进行插入，在表的另一端进行删除操作，具有先进先出的特性。队列也称为先进先出（firstinfirstout）的线性表，简称FIFO表。允许插入数据的一端称为队尾（rear）；相对的，允许删除数据的一端称为队头（front）。向一个队列中插入数据元素的操作称为入队，它把新元素放到队尾元素的后面，使之成为新的队尾元素；从一个队列中删除数据元素的操作称作出队，它把队头元素删除，使其相邻的元素成为新的队头元素。当队列中不包含数据元素时，称为空队。队列的基本操作如下：（1）置空队列：初始化操作。构造一个空队列，即队列中不含任何数据元素。（2）入队：将一个新数据元素插入队列的队尾，即队列中增加了一个元素。（3）出队：队头元素出队，即删除当前队列的队头元素，使其相邻的元素成为新的队头。（4）取队头元素：取队列中的队头元素的值，与出队操作不同，该操作队头元素不变。（5）判断空队：若队列空，返回0；否则，返回1。三、二叉树树状结构是一种重要的非线性数据结构，它是数据元素（称为结点）按分支关系组织起来的结构。它的每一个结点都可以有不止一个直接后继，除根结点外的所有结点都有且只有一个直接前驱。二叉树是每个结点最多有两个子树的有序树，通常子树被称作“左子树”和“右子树”。相比一般的树而言，二叉树的结构更加规范和确切，且一般的树可以转化成二叉树。二叉树的存储结构如下：顺序存储结构。二叉树的顺序存储结构就是用一组地址连续的存储单元（如一维数组）来存放一棵二叉树的所有结点，此结构简单，且操作方便。但对于一般的二叉树，不宜直接采用顺序存储结构。需要将其转化成完全二叉树，之后按层次编号，使编号为i的结点存入一维数组第i个单元中，从而实现一般二叉树的顺序存储。链式存储结构。二叉树的链式存储结构是指用一个链表来存储一棵二叉树，最常用的链式存储结构是二叉链表，每个结点由一个数据和分别指向其左、右子树的两个分支构成，则二叉链表存储结构中的结点包括3个域：数据域、左指针域和右指针域。从根结点开始，通过指针域，将各个结点连结成一个整体结构，指向根结点的指针可表示整个二叉链表，代表这棵二叉树。二叉树的基本操作：（1）二叉树的建立。算法：将给定的二叉树扩充为完全二叉树，依次输入结点值（包括虚结点），生成二叉链表的结点，按层次将各个结点链接到其双亲结点的相应指针域，直至输入结束。二叉树的遍历。所谓二叉树的遍历，就是对二叉树中的所有结点进行访问，且只访问一遍。任意一棵二叉树由根、左子树和右子树三部分组成，左、右子树可为空。由此，二叉树的遍历包括访问根结点、遍历左子树和遍历右子树。遍历子树是递归过程，直至所遍历的二叉树为空。根据遍历的顺序不同，二叉树的遍历方式分为3种：先序遍历、中序遍历和后序遍历。四、数据结构与程序设计著名的瑞士计算机科学家N·Wirth教授曾提出：程序设计=算法+数据结构。这个典经的公式表明一个程序设计应该包括数据结构和算法两方面的内容。数据结构是对数据的描述，即数据的组织形式，用于体现数据之间的关系。而算法是对操作的描述，即操作步骤，是用来解决“做什么”和“怎么做”的问题。数据结构指的是数据之间的相互关系，即数据的组织形式，它一般包括以下三方面内容：（1）数据元素之间的逻辑关系，称为数据的逻辑结构。（2）数据元素及其关系在计算机存储器内的表示，称为数据的存储结构。（3）数据的运算，即对数据的操作。在解决具体问题时，首先要分析数据的特性和数据之间的关系，选取一种恰当的组织形式来体现数据之间的内在联系。随后，