《数据结构与C++算法设计案例教程 教学课件 ppt 作者 赖俊峰 模块四》由会员分享，可在线阅读，更多相关《数据结构与C++算法设计案例教程 教学课件 ppt 作者 赖俊峰 模块四（27页珍藏版）》请在金锄头文库上搜索。
1、模块四 栈和队列,本模块要点: 1、理解栈的定义和特点。 2、掌握入栈、出栈、判断栈空、栈满的算法。 3、理解队列的定义和特点。 4、掌握入队、出队、判断队空、队满的算法。 5、循环队列的定义和操作,任务一 栈的概念和基本操作 子任务1 栈的概念,栈（stack）是限制在一端进行插入和删除的线性表。允许进行插入、删除操作的这一端称为栈顶；另一端不作任何操作，称为栈底，。如果没有一个元素则称为空栈。 如图所示的栈中有a1、a2、a3、a4这四个元素。在建立这个栈时，它们进栈的顺序是a1、a2、a3、a4；当需要出栈时，则只能按照a1、a2、a3、a4的顺序进行出栈，所以栈被称为“后进先出”的线性
2、表（Last In First Out），简称 LIFO表。,栈基本操作,（1）创建栈：StaCreat() 初始条件：栈不存在 操作结果：构造了一个空栈。 （2）删除一个栈：StaDestroy() 初始条件：栈存在 操作结果：把整个栈删除。 （3）显示栈顶元素GetTop() 初始条件：栈不为空 操作结果：现实栈顶元素的值。 （4）入栈操作： Push(StackElem e) 初始条件：栈s已存在 操作结果：在栈s的顶部插入一个新元素x，x成为新的栈顶元素。栈发生变化。,（5）出栈操作：Pop(); 初始条件：栈s存在且非空 操作结果：栈s的顶部元素从栈中删除，栈中少了一个元素。栈发生变
3、化。 （6）显示栈中元素个数：StaLength() 初始条件：栈已存在 操作结果：显示栈中元素个数,并提示还可以有几个元素入栈。 （7）判断栈是否为空：StaEmpty() 初始条件：栈已存在 操作结果：若栈为空栈，并输出结果 （8）判断栈是否为满：StackFull() 初始条件：栈已存在 操作结果：若栈中元素的个数已经达到最大值，并输出结果。,class StackElem private: char Name10; /学生姓名 double Score; /学生成绩 StackElem* Next; /指向下一元素的指针 public: StackElem(); /构造函数 Stack
4、Elem(); /析构函数 void SEdisplay(); /显示本元素的内容 StackElem* GetStackElem(); /取指向下一元素的指针 ;,class StackOperation/声明栈操作类 private: int StackMax; /设置栈的最大长度, StackElem* Top;/指向栈顶元素 StackElem* Base;/指向栈底元素 public: StackOperation();/构造函数 StackOperation();/析构函数 void StaCreat(); /创建栈, void StaDestroy();/删除一个栈 void G
5、etTop(); /显示栈顶元素 void Pop();/弹出栈顶元素 void Push(StackElem e);/元素e入栈, void StaLength();/显示栈中元素个数, void StaEmpty();/判断栈是否为空, int StackFull();/判断栈是否为满 ;,子任务2 栈的主要操作,栈中的数据元素用一个预设的足够长度的一维链表来实现，栈底位置可以设置在链表的一个端点，而栈顶则是另一端，它可以随着插入和删除而变化，我们用用top 指针来指向栈顶。定义一个指向顺序栈的指针： StackElem* Top; 通常0下标端设为栈底，这样空栈时栈顶指针top=-1;
6、入栈时，栈顶指针加，即top+； 出栈时，栈顶指针减1，即top-。栈操作的示意图如图4-2所示。,void StackOperation:Push(StackElem e) /元素e入栈,需要根据栈的最大长度判断是否可以入栈 StackElem* p; p=new StackElem;/生成新结点 if(Top=NULL) /如果栈为空,则入栈元素为栈的首元素. strcpy(p-Name,e.Name); /将要入栈的元素姓名复制给新结点 p-Score=e.Score;/将要入栈的元素成绩复制给新结点 p-Next=NULL; Top=p; /将新元素设为栈顶元素 Base=p; /同时
7、将新结点设为栈底元素,即新元素既为栈顶元素,有为栈底元素 else /如果栈不为空 strcpy(p-Name,e.Name); /将要入栈的元素姓名复制给新结点 p-Score=e.Score; /将要入栈的元素成绩复制给新结点 p-Next=Top; /将新结点设置为栈顶元素 Top=p; ,void StackOperation:Pop()/弹出栈顶元素 StackElem* p; if(Top=NULL) coutNext; /栈顶指针指向下一结点 delete p; /释放p结点 cout“已弹出栈顶元素!“endl; ,知识扩展,void StackOperation:StaEmp
8、ty()/判断栈是否为空,显示结果 if(Top=NULL) cout“此栈为空!“endl; else cout“此栈不空!“endl; coutendl; void StackOperation:StaEmpty() /判断栈是否为空,显示结果 int StackOperation:StackFull() /判断栈是否为满,子任务3 栈的应用,问题：这是实验心理学中的一个经典问题，心理学家把一只老鼠从一个无顶盖的大盒子的入口处赶进迷宫。迷宫中设置很多隔壁，对前进方向形成了多处障碍，心理学家在迷宫的唯一出口处放置了一块奶酪，吸引老鼠在迷宫中寻找通路以到达出口。 求解思想：回溯法是一种不断试探
9、且及时纠正错误的搜索方法。下面的求解过程采用回溯法。从入口出发，按某一方向向前探索，若能走通（未走过的），即某处可以到达，则到达新点，否则试探下一方向 ; 若所有的方向均没有通路，则沿原路返回前一点，换下一个方向再继续试探，直到所有可能的通路都探索到，或找到一条通路，或无路可走又返回到入口点。,任务二 队列的概念和操作 子任务1 队列的概念,队列的主要特性是“先进先出”。它有一端只能进行插入操作，另一端只能进行删除操作。最先进入队列的元素一定最先出队列，最后进入队列的元素一定放在队尾。 我们把这种“先进先出”(FIFO-First In First Out) 的数据结构：即插入在表一端进行，而
10、删除在表的另一端进行的数据结构称为队列，把允许插入的一端叫队尾(rear) ，把允许删除的一端叫队头(front)。如图4-3所示是一个有4个元素的队列。如果它们入队的顺序为a1、a2、a3、a4那么它们出队时的顺序是a1、a2、a3、a4 。,a1、a2、a3、a4,队列的基本操作,（1）创建队列,建立一个QueueElem的对象为首元素： QueCreat()： 初始条件：队列不存在。 操作结果：构造了一个有一个元素的队列。 （2）删除一个队列：QueueDestroy() 初始条件：队列存在。 操作结果：把队列中的所有元素删除。 （3）入队操作：QueAdd(QueueElem e) 初
11、始条件：队列不为空。 操作结果：向队尾插入元素e。,（4）出队操作QueueSub() 初始条件：队列已经存在。 操作结果：让队列头部的元素出队列。 （5）显示队列中元素的个数：QueueLength() 初始条件：队列已经存在且非空。 操作结果：显示对中元素的个数,提示还有几个元素可以入队。 （6）判断队列是否为满：QueueFull() 初始条件：队列已经存在 操作结果：如果队列没有满则返回“1”，说明还有元素可以入队。如果队列满则返回“0”，不能再有元素入队了。,class QueueElem /定义队列元素类 public: char Name10; /学生姓名 int Grade;
12、/学生年级QueueElem* Next; /指向下一元素的指针 void QEdisplay(); /显示本元素的内容 ;,class QueueOperation/定义队列操作类对象 private: int QueueMax; /设置队列的最大长度,默认值为10 QueueElem* front; /指向队头元素 QueueElem* rear; /指向队尾元素 public: QueueOperation(); /构造函数 QueueOperation(); /析构函数 void QueCreat(); /创建队列,建立一个QueueElem的对象为首元素 void QueueDest
13、roy(); /删除一个队列 void QueAdd(QueueElem e); /入队操作,在队首加入一个QueueElem的对象 void QueueSub();/出队操作,在队尾删除一个元素 void QueueLength(); /显示对中元素的个数,显示还有几个元素可以入队 int QueueFull(); /判断队列是否为满 ;,子任务2 队列的操作,队列中最重要的操作是入队与出队，在不考虑溢出的情况下，入队操作队尾指针加1，指向新位置后，元素入队。出队操作队头要求队头指针加1，表明队头元素出队。情况如下图：,void QueueOperation:QueAdd(QueueElem
14、 e) /入队操作,在队首加入一个QueueElem的对象 QueueElem *p; /生成新节点 p=new QueueElem; /给新结点开辟空间 if(front=NULL) /空队列时,新结点成为队列的第一个结点,既是队头又是队尾 strcpy(p-Name,e.Name); /将新元素的内容复制给新结点 p-Grade=e.Grade; p-Next=NULL; front=rear=p; /如果队列为空,将新结点置为既是队首结点又是队尾结点 else/如果队列不空 strcpy(p-Name,e.Name); /将新元素的内容复制给新结点 p-Grade=e.Grade; p-
15、Next=NULL; rear-Next=p; /则设置为队尾结点 rear=p; ,void QueueOperation:QueueSub() /出队操作,在队头删除一个元素(重要) QueueElem *p; if(front=NULL) coutNext; /将首结点指向下一结点 delete p; /将队首节点删除 if(front=NULL) rear=NULL; /出队后队列已空 cout“队头元素已出队!“endl; ,知识扩展,void QueueOperation:QueueLength() /显示对中元素的个数,显示还有几个元素可以入队 QueueElem *p; int len=0; /len计算队列中元素的个数 p=front; /将p指向队首 while(p!=NULL) /当p不为空时 len+; p=p-Next; cout“队列中有“len“个元素“endl; /显示队列中元素的个数 cout“还可以有“QueueMax-len“个元素可以入队“endlendl; /显示还可以有多少元素入队 ,int QueueOperation:QueueFull() QueueElem *p; int len=0; /len计算队列中元素的个数 p
