数据结构第3章_第1页
数据结构第3章_第2页
数据结构第3章_第3页
数据结构第3章_第4页
数据结构第3章_第5页
已阅读5页,还剩65页未读 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

数据结构A·第3章第3章堆栈和队列

引言堆栈和队列也是最常见的数据结构,在算法设计中经常使用,它们在逻辑上同线性表一样,都是线性结构,差别在于:线性表可以在表的任意位置插入和删除元素,而堆栈和队列只能在表的端点插入和删除元素。第3章堆栈和队列内容提要

1、定义堆栈与队列抽象数据类型

2、讨论堆栈与队列的顺序表示方法

3、讨论堆栈与队列的链接表示方法

4、以表达式计算为例讨论堆栈的应用

5、介绍递归的概念和递归算法3.1堆栈a0a1…ai…an-1入栈出栈bottomtop

图3-1栈的示意图堆栈(简称栈)的示意图S=(a0,a1,…,an-1)课堂提要第3章堆栈和队列3.1堆栈3.2队列3.3表达式的计算3.4递归3.1堆栈3.1.1堆栈抽象数据类型

堆栈是后进先出(LastInFirstOut——LIFO)的动态线性数据结构。

1.堆栈的定义堆栈工作的演示ACB3.1堆栈3.1.1堆栈抽象数据类型

同时,堆栈也是是后进先出(LastInFirstOut——LIFO)的动态线性数据结构。

1.堆栈的定义ACB堆栈工作的演示3.1堆栈3.1.1堆栈抽象数据类型

ADTStack{数据:0个或多个元素的线性序列(a0,a1,...,an-1),其最大允许长度为MaxStackSize。其插入和删除运算都限制在同一端进行,并遵循LIFO原则。运算:Create():建立一个空栈。

Destroy():撤消一个栈。

IsEmpty():若栈空,则返回true;否则返回false。

IsFull():若栈满,则返回true;否则返回false。

Top(x):返回栈顶元素。若操作成功,则返回true;否则返回false。

Push(x):在栈顶插入元素x。

Pop():从栈中删除栈顶元素。

Clear():清除堆栈中全部元素。}

2.栈的抽象数据类型3.1堆栈3.1.1堆栈抽象数据类型

3.栈的C++模板抽象类程序3-1堆栈的C++类#include<iostream.h>template<classT>classStack{public:virtualboolIsEmpty()const=0;virtualboolIsFull()const=0;virtualboolTop(T&x)const=0;virtualboolPush(Tx)=0;virtualboolPop()=0;virtualvoidClear()=0;};3.1堆栈3.1.2栈的顺序表示

1.栈的顺序表示法an-1a1a0topn-110栈s图3-2顺序栈maxTop………一维数组s存储栈中元素,maxTop+1为最大允许容量,top指示栈顶,top==-1表示空栈,top==maxTop表示栈满。

S=(a0,a1,…,an-1)3.1堆栈3.1.2栈的顺序表示

2.顺序栈类template<classT>classSeqStack:publicStack<T>{public:SeqStack(intmSize);~SeqStack(){delete[]s;}boolIsEmpty()const{return(top==-1);}boolIsFull()const{return(top==MaxTop);}boolTop(T&x)const;boolPush(Tx);boolPop();voidClear(){top=-1;}private:inttop;//总是指向栈顶元素

intmaxTop;T*s;}an-1a1a0topn-110栈s图3-2顺序栈maxTop………3.1堆栈3.1.2栈的顺序表示

3.动态一维数组描述顺序栈类an-1a1a0topn-110栈s图3-2顺序栈maxTop………template<classT>classSeqStack:publicStack<T>{public:……private:intmaxTop;inttop;T*s;}3.1堆栈3.1.2栈的顺序表示

3.动态一维数组描述顺序栈类an-1a1a0topn-110栈s图3-2顺序栈maxTop………构造函数template<classT>SeqStack<T>::SeqStack(intmSize){maxTop=mSize-1;s=newT[mSize];top=-1;}析构函数SeqStack<T>::~SeqStack(intMaxSize){delete[]s;}3.1堆栈3.1.2栈的顺序表示

4.在顺序存储表示下实现栈上定义的操作an-1a1a0topn-110栈s图3-2顺序栈maxTop………(1)取栈顶元素template<classT>boolSeqStack<T>::Top(T&x)const{if(IsEmpty()){//空栈处理

cout<<"Empty"<<endl;returnfalse;}x=s[top];returntrue;}3.1堆栈3.1.2栈的顺序表示

4.在顺序存储表示下实现栈上定义的操作an-1a1a0topn-110栈s图3-2顺序栈maxTop………(2)进栈(压入)template<classT>boolSeqStack<T>::Push(T&x){if(IsFull()){//溢出处理

cout<<"Overflow"<<endl;returnfalse;}s[++top]=x;returntrue;}3.1堆栈3.1.2栈的顺序表示

4.在顺序存储表示下实现栈上定义的操作an-1a1a0topn-110栈s图3-2顺序栈maxTop………(3)出栈(弹出)template<classT>boolSeqStack<T>::Pop(){if(IsEmpty()){//空栈处理

cout<<"Underflow"<<endl;returnfalse;}top--;returntrue;}3.1堆栈3.1.3栈的链接表示

1.栈的链接表示法(链式栈)链式栈的定义和操作的实现类似于单链表。an-1a0…top∧图3-3链式栈

an-2an-3不带表头结点的单链表课堂提要第3章堆栈和队列3.1堆栈

3.1.1栈抽象数据类型

3.1.2栈的顺序表示

3.1.3栈的链接表示3.2队列3.3表达式的计算3.4递归3.1堆栈3.1.3栈的链接表示

2.在链接表示下实现栈上定义的操作an-1a0…top∧图3-3链式栈

an-2an-3入栈操作push(Tx)Node<T>*q=newNode<T>;q->element=x;q->link=top;top=q;3.1堆栈3.1.3栈的链接表示

2.在链接表示下实现栈上定义的操作an-1a0…top∧图3-3链式栈

an-2an-3出栈操作Pop()Node<T>*q=top;top=top->link;deleteq;3.2队列3.1.3栈的链接表示课堂提要第3章堆栈和队列3.1堆栈3.2队列

3.2.1队列抽象数据类型

3.2.2队列的顺序表示

3.2.3队列的链接表示3.3表达式的计算3.4递归队列的示意图

Q=(a0,a1,…,an-1)a0a1…an-1frontrear入队出队3.2队列3.2.1队列抽象数据类型

1.队列的定义队列是限定在表的一端插入,在表的另一端删除的线性数据结构。若队列中无元素,则为空队列队尾——允许插入元素的一端队头——允许删除元素的另一端Q=(a0,a1,…,an-1)课堂提要第3章堆栈和队列3.1堆栈3.2队列

3.2.1队列抽象数据类型

3.2.2队列的顺序表示

3.2.3队列的链接表示3.3表达式的计算3.4递归3.2队列3.2.1队列抽象数据类型

1.队列的定义a0a1…an-1frontrear入队出队若给定队列Q=(a0,a1,…,an-1),则称a0是队头元素,an-1是队尾元素。元素a0,…,an-1依次入队,出队的顺序与入队相同,a0出队后,a1才能出队,因此又称队列为先进先出(FirstInFirstOut——FIFO)的动态线性数据结构。3.2队列3.2.1队列抽象数据类型

1.队列的定义ACBrearfront队列工作的演示(入队)3.2队列3.2.1队列抽象数据类型

1.队列的定义rearfront队列工作的演示(出队)ACB3.2队列3.2.1队列抽象数据类型

2.队列的抽象数据类型ADTQueue{

数据:0个或多个元素的线性序列(a0,a1,…,an-1),其最大长度为MaxQueueSize。它插入在一端进行,而删除在另一端进行,并遵循FIFO原则。运算:Create():建立一个空队列。

Destroy():撤消一个队列。

IsEmpty():若队列空,则返回true;否则返回false。

IsFull():若队列满,则返回true;否则返回false。

Front(x):在x中返回队头元素。操作成功返回true;否则返回false。

EnQueue(x):在队尾插入元素x。操作成功返回true;否则返回false。

DeQueue():从队列中删除队头元素。操作成功返回true;否则返回falseClear():清除队列中全部元素。}3.2队列3.2.1队列抽象数据类型

3.队列的C++模板抽象类template<classT>classQueue{public:Queue(){};~Queue(){}; virtualboolEnQueue(constTx)=0;virtualboolDeQueue()=0;virtualboolFront(T&x)=0; virtualboolIsEmpty()const=0; virtualboolIsFull()const=0;virtualvoidClear()=0; };3.2队列3.2.2队列的顺序表示

1.队列的顺序表示法课堂提要第3章堆栈和队列3.1堆栈3.2队列

3.2.1队列抽象数据类型

3.2.2队列的顺序表示

3.2.3队列的链接表示3.3表达式的计算3.4递归01234=maxSize-1(a)空队列fr

图中f为front,r为rear3.2队列3.2.2队列的顺序表示

1.队列的顺序表示法

从(d)可以看到,当再有元素需要入队时将产生“溢出”,然而队列中尚有三个空元素单元,我们称这种现象为“假溢出”。指针f指向队首元素的前一个位置,指针r指向队尾元素50403020(b)元素20,30,40,50入队01234=maxSize-1fr50(c)元素20,30,40依次出队01234=maxSize-1fr50(d)元素60入队01234=maxSize-1fr603.2队列3.2.2队列的顺序表示

2.循环队列表示法

把数组从逻辑上看成是一个头尾相连的环。(a)空队列满队列front==rear实际仍有一个元素的空间未使用0fr12340f123420304050r3.2队列3.2.2队列的顺序表示

2.循环队列表示法注意r值的变化:

4+1=>00f123420304050r(b)元素20,30,40,50入队列(c)元素20,30,40出队列0f123450r(d)元素60,70入队列0f123450r60703.2队列3.2.2队列的顺序表示

2.循环队列表示法

实现循环队列操作:

(1)为使入队和出队实现循环,可以利用取余运算符%。

(2)队头指针进一:

front=(front+1)%maxSize;

(3)队尾指针进一:

rear=(rear+1)%maxSize;

(4)空队列:当front==rear时为空队列,

(5)满队列:当(rear+1)%maxSize==front时为满队列。满队列时实际仍有一个元素的空间未使用。3.2队列3.2.2队列的顺序表示

3.顺序队列类template<classT>classSeqQueue:publicQueue<T>{public:SeqQueue(intmSize);~SeqQueue(){delete[]q;}

boolIsEmpty()const;

boolIsFull()const;

boolFront(T&x)const;boolEnQueue(Tx);boolDeQueue();voidClear(){front=rear=0;}private:intfront,rear;intmaxSize;T*q;};0fr12343.2队列3.2.2队列的顺序表示

4.动态一维数组描述顺序队列类template<classT>classSeqQueue:publicQueue<T>{public:……

private:intfront,rear;intmaxSize;T*q;}01…n-1…maxSize-1frontrearq……3.2队列3.2.2队列的顺序表示

4.动态一维数组描述顺序队列类01…n-1…maxSize-1frontrearq……构造函数template<classT>SeqQueue<T>::SeqQueue(intmSize){//生成一个空队列

maxSize=mSize;q=newT[maxSize];front=rear=0;}析构函数~SeqQueue(){delete[]q;}3.2队列3.2.2队列的顺序表示

5.在顺序存储表示下实现队列定义的操作template<classT>boolSeqQueue<T>::IsEmpty()const{returnfront==rear;}template<classT>boolSeqQueue<T>::IsFull()const{return(rear+1)%maxSize==front;}(1)判空(2)判满3.2队列3.2.2队列的顺序表示

5.在顺序存储表示下实现队列定义的操作template<classT>boolSeqQueue<T>::Front(T&x){if(IsEmpty()){cout<<"empty"<<endl;returnfalse;}x=q[(front+1)%maxSize];returntrue;}(3)取队列元素0f123420304050r3.2队列3.2.2队列的顺序表示

5.在顺序存储表示下实现队列定义的操作template<classT>boolSeqQueue<T>::EnQueue(Tx){if(IsFull()){cout<<"Full"<<endl;returnfalse;}q[(rear=(rear+1)%maxSize)]=x;returntrue;}(4)进队列(插入)0f123420304050r元素50入队列0f1234203040r3.2队列3.2.2队列的顺序表示

5.在顺序存储表示下实现队列定义的操作template<classT>boolSeqQueue<T>::DeQueue(){if(IsEmpty()){cout<<"Underflow"<<endl;returnfalse;}front=(front+1)%maxSize;returntrue;}(5)出队列(删除)0f123420304050r0f123450r

元素20,30,40出队列3.2队列3.2.3队列的链接表示队列的链接表示法(链式队列)链式队列的定义和操作的实现类似于单链表。课堂提要第3章堆栈和队列3.1堆栈3.2队列

3.2.1队列抽象数据类型

3.2.2队列的顺序表示

3.2.3队列的链接表示3.3表达式的计算3.4递归不带表头结点的单链表a0an-1…front∧图3-3链式队列

a1a2rear3.2队列3.2.3队列的链接表示队列的链接表示法(链式队列)a0an-1…front∧图3-3链式队列

a1a2rear入队列EnQueue(Tx)Node<T>*q=newNode<T>;q->element=x;q->link=NULL;rear->link=q;rear=q;出队列DeQueue()Node<T>*q=front;front=front->link;delq;3.3堆栈的应用—表达式计算3.3.1表达式课堂提要第3章堆栈和队列3.1堆栈3.2队列3.3表达式的计算

3.3.1表达式

3.3.2后缀表达式求值

3.3.3中缀表达式转换为后缀表达式3.4递归

表达式:表达式习惯的书写形式是一个双目运算符位于两个操作数之间,如a+b;还有单目运算符,如I++和-a。条件运算符是C/C++语言中惟一的三目运算符。

中缀表达式:操作符在两个操作数之间的表达式,如:a/(b-c)+d*e

前缀表达式:操作符放在两个操作数之前的表达式,如:+/a-bc*de

后缀表达式:操作符放在两个操作数之后的表达式(逆波兰表达式)如:abc-/de*+3.3堆栈的应用—表达式计算逆波兰式(ReversePolishnotation,RPN)

J.Lukasiewicz

19293.3堆栈的应用—表达式计算3.3.1表达式表3-1C++中部分操作符的优先级操作符优先级-,!7*,/,%6+,-5<,<=,>,>=4==,!=3&&2||1

有括号时先计算括号号中的表达式;高优先级先计算同级操作符计算:从左到右,或从右到左3.3堆栈的应用—表达式计算3.3.2后缀表达式求值比较中缀表达式及其对应的后缀表达式的例子表3.2中缀表达式和后缀表达式中缀表达式后缀表达式a*b+cab*c+a*b/cab*c/a*b*c*d*e*fab*c*d*e*f*a+(b*c+d)/eabc*d+e/+a*((b+c)/(d-e)-f)abc+de-/f-*a/(b-c)+d*eabc-/de*+课堂提要第3章堆栈和队列3.1堆栈3.2队列3.3表达式的计算

3.3.1表达式

3.3.2后缀表达式求值

3.3.3中缀表达式转换为后缀表达式3.4递归3.3堆栈的应用—表达式计算3.3.2后缀表达式求值后缀表达式求值优点:1)无界限符;2)求值时无需考虑操作符的优先级。因此用后缀表达式求值计算简便,在编译程序中常用。利用栈很容易计算后缀表达式的值。为了方便算法的实现,在后缀表达式的后面,通常会加上1个后缀表达式的结束符“#”。3.3堆栈的应用—表达式计算3.3.2后缀表达式求值后缀表达式求值算法:

(1)从左往右顺序扫描后缀表达式;(2)遇到操作数就进栈;(3)遇到操作符就从栈中弹出两个操作数,执行该操作符规定的运算;并将结果进栈;(4)重复上述操作,直到表达式结束。弹出栈顶元素即为结果。

3.3堆栈的应用—表达式计算3.3.2后缀表达式求值642-/32*+#栈操作遇到结束符,弹出栈顶元素9即为结果#96、3出栈,计算3+6,结果9进栈+632、3出栈,计算3*2,结果6进栈*2332进栈2333进栈332、6出栈,计算6/2,结果3进栈/262、4出栈,计算4-2,结果2进栈-2462进栈264

6扫描项表3.3后缀表达式的计算6进栈64进栈43.3堆栈的应用—表达式计算3.3.2后缀表达式求值642-/32*+#6-24/32*+#642=22利用栈计算后缀表达式值的演示3.3堆栈的应用—表达式计算3.3.2后缀表达式求值利用栈计算后缀表达式值的演示233642-/32*+#6-24/32*+#=3263.3堆栈的应用—表达式计算3.3.2后缀表达式求值利用栈计算后缀表达式值的演示33642-/32*+#6-24/32*+#=2663.3堆栈的应用—表达式计算3.3.2后缀表达式求值利用栈计算后缀表达式值的演示63=642-/32*+#6-24/32*+#9=9==>6/(4-2)+3*26

4

2

-

/

3

2

*

+=93.3堆栈的应用—表达式计算3.3.2后缀表达式求值在Linux系统中有后缀表达式计算器。$>dc43+p73.3堆栈的应用—表达式计算3.3.2后缀表达式求值举例:模拟一个简单的计算器假设该计算器可以接收后缀表达式,但只进行+、-、*、/和^运算。为实现计算器,定义一个计算器类。程序3.5计算器类#include”SeqStack.h”#include<math.h>classCalculator{public:Calculator(intmaxSize):s(maxSize){};//构造函数

voidRun();voidClear(s.Clear();)private:SeqStack<double>s;//私有数据成员是一个栈,用于存放操作数

voidPushOperand(double);//操作数进栈

boolGetOperands(double&,double&);//两个操作数出栈

voidDoOperator(char);//操作符进行处理(遇到操作符时调用)};3.3堆栈的应用—表达式计算3.3.2后缀表达式求值举例:模拟一个简单的计算器成员函数的实现:voidCalculator::PushOperand(doubleop){s.Push(op);//操作数进栈}BOOLCalculator::GetOperands(double&op1,double&op2){//两个操作数出栈

if(!s.Top(op1)){ cerr<<"Missingoperand!"<<endl;returnfalse;}s.Pop();if(!s.Top(op2)){ cerr<<"Missingoperand!"<<endl;returnfalse;}s.Pop();returntrue;}3.3堆栈的应用—表达式计算3.3.2后缀表达式求值举例:模拟一个简单的计算器voidCalculator::DoOperator(charoper)//遇到操作符时调用{boolresult;doubleoper1,oper2;result=GetOperands(oper1,oper2);//从栈中弹出2个操作数3.3堆栈的应用—表达式计算3.3.2后缀表达式求值举例:模拟一个简单的计算器if(result)//执行操作符oper指定的运算

switch(oper)//根据操作符做相应的运算,先出栈的操作数oper1{//放在操作符的右边,后出栈的oper2放在左边

case'+':s.Push(oper2+oper1);break;case'-':s.Push(oper2-oper1);break;case'*':s.Push(oper2*oper1);break;case'/':if(fabs(oper1)<1e-6){//如果分母为0,则做出错处理

cerr<<"Divideby0!"<<endl; Clear();} elses.Push(oper2/oper1);break;case'^':s.Push(pow(oper2,oper1));break;}elseClear();}3.3堆栈的应用—表达式计算3.3.2后缀表达式求值举例:模拟一个简单的计算器voidCalculator::Run(){charc;doublenewop;while(cin>>c,c!='#'){//从输入流试读入一个字符,遇结束符结束

switch(c){//读入的字符做如下处理

case'+':case'-':case'*':case'/':case'^':DoOperator(c);break;//是操作符则进行相应的计算

default:cin.putback(c);//如不是操作符,则将试读入的字符放回输入流

cin>>newop;//读入一个操作数

PushOperand(newop);break;//操作数进栈

}}if(s.Top(newop))cout<<newop<<endl;//取栈顶元素,得结果输出}3.3堆栈的应用—表达式计算3.3.2后缀表达式求值举例:模拟一个简单的计算器计算器类的应用程序:#include“calculator.h”constintSIZE=20;voidmain(){CalculatorCal(SIZE);Cal.Run();}输入:642-/32*+#结果:93.3堆栈的应用—表达式计算3.3.3中缀表达式转换为后缀表达式注意:只考虑左结合的双目运算。每个表达式以“#”号作为其结束标记。输入中缀表达式由运算符、操作数、园括弧和‘#’四种不同类型的项组成的序列输出后缀表达式课堂提要第3章堆栈和队列3.1堆栈3.2队列3.3表达式的计算

3.3.1表达式

3.3.2后缀表达式求值

3.3.3中缀表达式转换为后缀表达式3.4递归3.3堆栈的应用—表达式计算3.3.3中缀表达式转换为后缀表达式栈内优先级isp(in-stackpriority)栈外优先级icp(incomingpriority)对未进栈的左括号赋以最高优先级,对已进栈的左括号赋以最低优先级。假定表达式的语法正确性检查已在表达式转换之前完成。3.3堆栈的应用—表达式计算3.3.3中缀表达式转换为后缀表达式转换步骤:(1)从左到右扫描中缀表达式,遇到#转(6);否则继续;(2)遇到操作数直接输出;(不进栈)(3)遇到“)”,则连续出栈输出,直到遇到“(”为止(注意:“(”出栈但不输出);(4)若是其它操作符,则与栈顶的操作符比较优先级;若小于栈顶操作符的栈内优先级,则连续出栈输出,直到大于等于栈顶操作符的栈内优先级结束,该操作符进栈;(5)转(1)继续;(6)输出栈中剩余操作符(#除外)。3.3堆栈的应用—表达式计算3.3.3中缀表达式转换为后缀表达式a(/中缀表达式:a/(b-c)+d*e后缀表达式:abc-/de*+bc-)d+*e#3.3堆栈的应用—表达式计算3.3.3中缀表达式转换为后缀表达式中缀表达式:a/(b-c)+d*e后缀表达式:abc-/de*+a(/bc-d+*e#3.3堆栈的应用—表达式计算3.3.3中缀表达式转换为后缀表达式中缀表达式:a/(b-c

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论