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

第11章 基本数据结构 栈 队列 结构体 链表 union结构体 数据结构应用实例 C语言程序设计 栈 队列 结构体 链表 union共同体 数据结构应用实例 01 02 04 05 03 目 录 CATALOUGUE 初心至善 匠心育人 理解栈 理解链表 理解队列 理解union共同体 学 习 目 标 LEARNING OBJECTIVES 初心至善 匠心育人 11.1 栈 11.1.1 定义栈 11.1.2 向栈中加入新元素 11.1.3 弹出栈中元素 11.1.4 查看栈顶元素 11.1.5 清空栈 11.1.6 打印栈中的元素 初心至善 匠心育人 在实际生活中会经常遇到一些“后进先出”的场景，例如，学习委员每周会收取同学们的作业本，先交的作业本放在最下面，最后交的作业本放在最上面，老师批改作业时，最先批改的是最上面的作业本，最后批改的是最下面的作业本，即后交的作业本先批改。在C语言中把满足“后进先出”原则的数据结构称为栈，如右图所示。 右图中，a1称为栈底元素，an称为栈顶元素，进栈的顺序为a1、a2、……、an，出栈的顺序为an、……、a2、a1，这些元素在存取的过程中遵循“后进先出”的原则。 11.1 栈 初心至善 匠心育人 在C语言中可以用数组来模拟栈。具体示例如下。 定义了两个全局变量bottom和top，分别存储栈底和栈顶的位置，栈底是固定不变的，栈顶随着进栈和出栈的操作而变化。在栈这一节中，约定top存储栈中即将加入的新元素的位置，即栈中已有元素的下标为0、1、2到top - 1。根据约定，当bottom和top的值都为0时，这个栈就是空的。 定义了宏STACK_SIZE，并将它的值设为1024。 定义了一个全局的整型数组stack，它的长度为STACK_SIZE。 11.1 栈 11.1.1 定义栈 初心至善 匠心育人 push函数实现了向栈中加入新元素的功能，其定义如下所示： 其中，参数element是要加入栈中的新元素。根据此前的约定，top存储的是新元素加入的位置，因此stack[top]用来保存要加入的值element。 新元素加入完毕后，栈的长度增加1，top的值也需要更新。top++使top的值加1，即表示接下来新元素要加入的位置。 11.1 栈 11.1.2 向栈中加入新元素 初心至善 匠心育人 pop函数实现了弹出栈顶元素的功能，其定义如下所示： pop函数不接受任何参数，它返回一个int类型的数据，即当前栈顶的元素。为了实现pop函数的功能，首先将top自减，此时top中存储的是栈中的最后一个元素的位置，随后将这个元素返回。注意pop函数调用之后栈的长度也减1，因此top自减之后恰好就是栈顶元素弹出栈之后新元素加入栈时的位置。 11.1 栈 11.1.3 弹出栈中元素 初心至善 匠心育人 有时程序只是想查看栈顶的元素，并根据查看的结果来决定是否需要将这个元素弹出栈。peek函数实现了这个功能，其定义如下所示： 由于top是栈顶下一个元素的位置，因此栈顶元素的下标是top - 1，peek函数返回这个下标对应的元素。请注意比较peek函数和pop函数的区别：两个函数的返回元素其实是一样的，但是pop函数在返回栈顶元素的同时还修改了top的值，而peek函数仅仅返回栈顶元素，栈顶的位置并没有被修改。 11.1 栈 11.1.4 查看栈顶元素 初心至善 匠心育人 由于一个栈为空的条件是top = bottom = 0，因此清空栈的操作非常简单，cleanStack函数定义如下所示： 注意到在栈中bottom的值自始至终为0，cleanStack函数实际上将top的值赋为0。另外，清空一个栈并没必要将栈中的所有元素都弹出栈或者将所有元素都设为0，只要将top指示栈底位置即可。 11.1 栈 11.1.5 清空栈 初心至善 匠心育人 为了更加方便直观地观察栈中行为，printStack函数用于打印栈中所有元素，其定义如下所示： 栈中的元素下标从bottom开始，到top-1结束，printStack函数利用一个for循环将栈中元素依次打印出来，以方便观察栈的当前状态。 11.1 栈 11.1.6 打印栈中元素 初心至善 匠心育人 11.2 队列 11.2.1 定义队列 11.2.2 进入队列 11.2.3 离开队列 11.2.5 打印队列中元素 11.2.4 清空队列 初心至善 匠心育人 生活中排队买火车票时，队伍前面的人先买票，买完票后就离开队伍，这就是队列的一个实例。队列与栈的“后进先出”原则正好相反，它满足“先进先出”的原则，即先进入队列的元素会先出队列，如图所示。 图中，在空队列中依次加入元素a1、a2、……、an，a1是队首元素，an是队尾元素，退出队列的次序只能是a1、a2