第11章 基本数据结构-【千锋教育】C语言程序设计（微课）同步教案

千锋教育 《C语言程序设计》 教学设计 课程名称： C语言程序设计教程 授课年级： 授课学期： 教师姓名： 2017年09月01日 课程名称 第11章 基本数据类型 计划学时 7学时 内容分析 本章主要介绍一些基本的数据结构，如栈、队列和链表，另外介绍一下union共同体的概念。 教学目标 与 教学要求 理解栈、队列、链表、union共同体，熟练掌握结构体 教学重点 栈、队列、结构体、链表 教学难点 结构体、链表 教学方式 课堂讲解及ppt演示 教 学 过 程 第一课时 （栈） 栈 在实际生活中会经常遇到一些“后进先出”的场景，例如，学习委员每周会收取同学们的作业本，先交的作业本放在最下面，最后交的作业本放在最上面，老师批改作业时，最先批改的是最上面的作业本，最后批改的是最下面的作业本，即后交的作业本先批改。在C语言中把满足“后进先出”原则的数据结构称为栈，如图11.1所示。 图11.1 栈示意图 图11.1中，a1称为栈底元素，an称为栈顶元素，进栈的顺序为a1、a2、……、an，出栈的顺序为an、……、a2、a1，这些元素在存取的过程中遵循“后进先出”的原则。 · 向栈中加入新元素 push函数实现了向栈中加入新元素的功能，其定义如下所示： void push(int element) { stack[top] = element; top++; } 其中，参数element是要加入栈中的新元素。根据此前的约定，top存储的是新元素加入的位置，因此stack[top]用来保存要加入的值element。 新元素加入完毕后，栈的长度增加1，top的值也需要更新。top++使top的值加1，即表示接下来新元素要加入的位置。 · 弹出栈中元素 pop函数实现了弹出栈顶元素的功能，其定义如下所示： int pop() { top--; return stack[top]; } pop函数不接受任何参数，它返回一个int类型的数据，即当前栈顶的元素。为了实现pop函数的功能，首先将top自减，此时top中存储的是栈中的最后一个元素的位置，随后将这个元素返回。注意pop函数调用之后栈的长度也减1，因此top自减之后恰好就是栈顶元素弹出栈之后新元素加入栈时的位置。 · 查看栈顶元素 有时程序只是想查看栈顶的元素，并根据查看的结果来决定是否需要将这个元素弹出栈。peek函数实现了这个功能，其定义如下所示： int peek() { return stack[top - 1]; } 由于top是栈顶下一个元素的位置，因此栈顶元素的下标是top - 1，peek函数返回这个下标对应的元素。请注意比较peek函数和pop函数的区别：两个函数的返回元素其实是一样的，但是pop函数在返回栈顶元素的同时还修改了top的值，而peek函数仅仅返回栈顶元素，栈顶的位置并没有被修改。 · 清空栈 由于一个栈为空的条件是top = bottom = 0，因此清空栈的操作非常简单，cleanStack函数定义如下所示： void cleanStack() { top = bottom; } 注意到在栈中bottom的值自始至终为0，cleanStack函数实际上将top的值赋为0。另外，清空一个栈并没必要将栈中的所有元素都弹出栈或者将所有元素都设为0，只要将top指示栈底位置即可。 · 打印栈中的元素 为了更加方便直观地观察栈中行为，printStack函数用于打印栈中所有元素，其定义如下所示： void printStack() { int i; printf("打印栈中元素："); for (i = bottom; i < top; i++) { printf("%d ", stack[i]); } printf(" "); } 栈中的元素下标从bottom开始，到top-1结束，printStack函数利用一个for循环将栈中元素依次打印出来，以方便观察栈的当前状态。 第二课时 （队列） 队列 生活中排队买火车票时，队伍前面的人先买票，买完票后就离开队伍，这就是队列的一个实例。队列与栈的“后进先出”原则正好相反，它满足“先进先出”的原则，即先进入队列的元素会先出队列，如图11.2所示。 图11.2 队列示意图 图11.2中，在空队列中依次加入元素a1、a2、……、an，a1是队首元素，an是队尾元素，退出队列的次序只能是a1、a2、……、an，这些元素在存取的过程中遵循“先