次课-链栈的实现、队列及基本操作.ppt

《次课-链栈的实现、队列及基本操作.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、首页学到现在，有什么体会？教学主题链栈的实现、队列及基本操作教学目标通过本次课的学习，使学生掌握链栈的实现方法、队列的概念及存储方式、顺序队列的实现。教学重点１．队列的顺序存储方式　２．顺序队列的基本操作教学难点链栈操作的实现教案主要内容栈栈的回顾链栈的实现队列队列的概念队列的基本操作队列的存储顺序队列的实现栈的概念和特点什么是栈？栈是一种特殊的线性表，它只在线性表的一端进行插入和删除操作。栈中允许插入、删除的这一端称为栈顶，另一个固定端称为栈底。当表中没有元素时称为空栈。栈的特点“先进后出”（

2、FirstInLastOut）或“后进先出”（LastInFirstOut）栈的存储回顾：前面介绍的线性表是采用什么方式存储数据的？栈与前面介绍过的线性表一样，也可以采用顺序存储结构（数组）或者链式存储结构（链表）。顺序栈链栈（单链表）栈的表示可以用一个栈顶指针（top）来指示栈顶元素存放的位置，用一个栈底指针（bottom）来指示栈底元素的存放位置。由于栈底位置相对不变，通常不用bottom。链栈的示意图返回链栈的实现【例】先建栈，然后输入一个整型元素后入栈，显示栈的内容。接下来进行出栈操作，再

3、显示栈的内容。最后销毁栈。数据结构描述链栈的类型描述如下：structstack_node{Elemtypedata;structstack_node*next;}；定义一个指向链栈的栈顶指针：structstack_node*top;源程序运行程序(11_1)看源程序(11_1)建栈分析对于链栈，建栈就是将链表初始化为空表。源程序structstack_node*init_linkstack(){returnNULL;}入栈流程图源程序思考：对于链栈，会不会出现栈满的情况？运行程序(11_1)看

4、源程序(11_1)出栈流程图源程序运行程序(11_1)看源程序(11_1)显示栈流程图源程序运行程序(11_1)看源程序(11_1)销毁栈分析只要释放链表中所有结点空间即可。流程图源程序运行程序(11_1)看源程序(11_1)返回引例在日常生活中，有一些这样的例子。例1：在食堂排队买饭，排在队首的买完后走掉，新来的排在队尾。例2：在车站排队买票、在银行排队存取款、在商店排队购物等。请问：上面的例子中有什么共同的特点？新进来的，先出去。队列的概念和特点什么是队列？队列是一种特殊的线性表，它在线性表的

5、一端进行插入操作，在另一端进行删除操作。队列中允许插入的一端称为队尾，允许删除的一端称为队头（首）。当表中没有元素时称为空队列。队列的特点“先进先出”（FirstInFirstOut）返回队列的基本操作队列主要有建队、入队、出队和销毁队列四个基本操作。建队：向操作系统申请分配存储单元，用来存储队列元素，同时初始化队列指针。入队：在队尾插入元素。出队：在队首删除元素。销毁队列：把存储单元归还给操作系统。为了实时了解队列的情况，还需要有输出队列这样的操作。输出队列：显示队列的内容。返回队列的存储回顾：

6、前面介绍的线性表和栈是采用什么方式存储数据的？队列与它们一样，也可以采用顺序存储结构（数组）或者链式存储结构（链表）。顺序队列链队列（单链表）队列的表示可以用一个头指针（front）来指示队首元素存放的位置，用一个尾指针（rear）来指示队尾元素的存放位置。队列的示意图入队的顺序依次为：a1、a2、a3、a4、a5出队的顺序依然是：a1、a2、a3、a4、a5返回顺序队列的实现【例】先建队列，然后输入一个整型元素后入队，显示队列的内容。接下来出队，再显示队列的内容。最后销毁队列。数据结构描述1）顺

7、序队列就是用数组来存储。顺序队列包括数据区、队首指针、队尾指针三个部分。2）顺序队列的类型描述如下：#defineMAXSIZE200structsequeue{Elemtypedata[MAXSIZE];/*数据区*/intrear,front;/*队头队尾指针*/};3）定义一个指向顺序队列的指针：structsequeue*q;运行程序(11_2)看源程序(11_2)建队列流程图源程序运行程序(11_2)看源程序(11_2)入队操作流程图源程序intin_sequeue(structsequ

8、eue*q,Elemtypex){q->data[q->rear]=x;q->rear=q->rear+1;return1;}思考：如果不断入队，会出现什么情况？(11_3)上溢出判断队列是否满的子函数源程序/*********************************************************//*函数名：full_sequeue*//*函数功能：判断队列是否满*//*入口参数：q——队列*//*返回值：队列满，返回1，否则返回0*//********