数据结构与算法3.1资料

Chapter3.1

StackandQueue数据结构与算法3全文共60页，当前为第1页。3.3TheStackADT3.3.1.StackModelAstackisalistinwhichinsertionsanddeletionstakeplaceatthesameend.Thisendiscalledthetop.Theotherendofthelistiscalledthebottom.ItisalsocalledaLIFO(last-in-first-out)list.数据结构与算法3全文共60页，当前为第2页。StackModeltopbottomA0An-1数据结构与算法3全文共60页，当前为第3页。StackModel

EtopDtopDCCBBBtopAbottomAbottomAbottom数据结构与算法3全文共60页，当前为第4页。StackModelAbstractDataTypeStack{

instanceslistofelements;oneendiscalledthebottom;theotheristhetop;

operations

Create():Createanemptystack;IsEmpty():Returntrueifstackisempty,returnfalseotherwiseIsFull():Returntrueifstackiffull,returnfalseotherwise;Top():returntopelementofthestack;Add(x):addelementxtothestack;Delete(x):Deletetopelementfromstackandputitinx;}

数据结构与算法3全文共60页，当前为第5页。3.3.2.ImplementationofStack1.LinkedListImplementationofStacks^topOfStackelementnext……whentopOfStack==nullisemptystack数据结构与算法3全文共60页，当前为第6页。LinkedListImplementationofStackspublicclassStackLi{publicStackLi(){topOfStack=null;}publicbooleanisFull(){returnfalse;}publicbooleanisEmpty(){returntopOfStack==null;}publicvoidmakeEmpty(){topOfStack=null;}publicvoidpush(objectx)publicobjecttop()publicvoidpop()throwsUnderflowpublicobjecttopAndPop()privateListNodetopOfStack;}

ClassskeletonforlinkedlistimplementationofthestackADT数据结构与算法3全文共60页，当前为第7页。LinkedListImplementationofStacksSomeRoutine:publicvoidpush(objectx){topOfStack=newListNode(x,topOfStack);}publicobjecttop(){if(isEmpty())returnnull;returntopOfStack.element;}数据结构与算法3全文共60页，当前为第8页。LinkedListImplementationofStackspublicvoidpop()throwsUnderflow{if(isEmpty())thrownewUnderflow();topOfStack=topOfStack.next;}publicobjecttopAndPop(){if(isEmpty())returnnull;objecttopItem=topOfstack.element;topOfStack=topOfStack.next;returntopItem;}

数据结构与算法3全文共60页，当前为第9页。

3.3.2.ImplementationofStack

2.ArrayImplementationofStacks

theArray

012

topOfStack

e1e2e3enwhentopOfStack==-1isemptystack数据结构与算法3全文共60页，当前为第10页。ArrayImplementationofStacks

publicclassstackAr{publicStackAr()publicStackAr(intcapacity)publicbooleanisEmpty(){returntopOfStack==-1;}publicbooleanisFull(){returntopOfStack==theArray.length–1;}publicvoidmakeEmpty(){topOfStack=-1;}publicvoidpush(objectx)throwsoverflowpublicobjecttop()publicvoidpop()throwsUnderflowpublicobjecttopAndPop()privateobject[]theArray;privateinttopOfStack;

staticfinalintDEFAULT_CAPACITY=10;}Stackclassskeleton---arrayimplementation数据结构与算法3全文共60页，当前为第11页。ArrayImplementationofStacksSomeroutine:publicStackAr(){this(DEFAULT_CAPACITY);}publicStackAr(intcapacity){theArray=newobject[capacity];topOfStack=-1;}Stackconstruction---arrayimplementation数据结构与算法3全文共60页，当前为第12页。ArrayImplementationofStackspublicvoidpush(objectx)throwsOverflow{if(isfull())thrownewOverflow();theArray[++topOfStack]=x;}publicobjecttop(){if(isEmpty()returnnull;returntheArray[topOfStack];}数据结构与算法3全文共60页，当前为第13页。ArrayImplementationofStackspublicvoidpop()throwsUnderflow{if(isEmpty())thrownewUnderflow();theArray[topOfStack--]=null;}publicobjecttopAndPop(){if(isEmpty())returnnull;objecttopItem=top();theArray[topOfStack--]=null;reurntopItem;}数据结构与算法3全文共60页，当前为第14页。ArrayImplementationofStacksItiswastefulofspacewhenmultiplestacksaretocoexistWhenthere’sonlytwostacks,wecanmaintainspaceandtimeefficiencybypeggingthebottomofonestackatposition0andthebottomoftheotheratpositionMaxSize-1.Thetwostacksgrowtowardsthemiddleofthearray.数据结构与算法3全文共60页，当前为第15页。ArrayImplementationofStacks

0

MaxSize-1top1top2Stack1Stack2………Twostacksinanarray数据结构与算法3全文共60页，当前为第16页。3.3.3.Applications1.BalancingSymbols(ParenthesisMatching)2.ExpressionEvaluation数据结构与算法3全文共60页，当前为第17页。ParenthesisMatching

(a*(b+c)+d)(a+b))(

1234567891011

121314151617181920212223(d+(a+b)*c*(d+e)–f))(()48121611920位置不匹配

222321位置不匹配

数据结构与算法3全文共60页，当前为第18页。#include<iostream.h>#include<string.h>#include<stdio.h>#include“stack.h”constintMaxlength=100;//maxexpressionlengthvoidPrintMatchedPairs(char*expr){Stack<int>s(Maxlength);intj,length=strlen(expr);for(inti=l;i<=length;i++){if(expr[i-1]==‘(‘)s.Add(i);elseif(expr[i-1]==‘)’)try{s.Delete(j);cout<<j<<‘‘<<i<<endl;}catch(OutOfBounds){cout<<“Nomatchforrightparenthesis”<<“at“<<i<<endl;}}while(!s.IsEmpty()){s.Delete(j);cout<<“Nomatchforleftparenthesisat“<<j<<endl;}}数据结构与算法3全文共60页，当前为第19页。

voidstaticmain(void){charexpr[MaxLength];cout<<“typeanexpressionoflengthatmost”<<MaxLength<<endl;cin.getline(expr,MaxLength);cout<<“thepairsofmatchingparenthesesin“<<endl;puts(expr);cout<<“are”<<endl;printMatcnedPairs(expr);}O(n)

数据结构与算法3全文共60页，当前为第20页。2.ExpressionEvaluationcompiler:infixExpressionpostfixExpressionpostfixExpressionEvaluation

A*B-C*D#AB*CD*-#(A+B)*((C-D)*E+F)#AB+CD-E*F+*#

无括号；运算分量的次序不变；运算符的次序就是具体执行的次序。postfixExpressionEvaluationAB*CD*-#infixExpressionpostfixExpressionA*B-C*D#AB*CD*-#数据结构与算法3全文共60页，当前为第21页。postfixExpressionEvaluation

AB*CD*-#

开辟一个运算分量栈

1)遇分量进栈;

2)遇运算符:取栈顶两个分量进行运算,栈中退了两个分量,并将结果进栈.enumBoolean{False,True};#include<math.h>#include<stack.h>#include<iostream.h>classcalculator{public:calculator(intsz):s(sz){}

voidRun();voidclear();

private:

voidAddOperand(doublevalue);BooleanGet2Operands(double&left,double&right);

voidDoOperator(charop);

stack<double>s;}数据结构与算法3全文共60页，当前为第22页。voidcalculator::AddOperand(doublevalue){s.Push(value);}Booleancalculator::Get2Operands(double&left,double&right){if(s.IsEmpty()){cerr<<“MissingOperand!”<<endl;returnfalse;}right=s.Pop();if(s.IsEmpty()){cerr<<“MissingOperand!”<<endl;returnfalse;}left=s.Pop();returntrue;}数据结构与算法3全文共60页，当前为第23页。voidcalculator::DoOperator(charop){doubleleft,right;Booleanresult;result=Get2Operands(left,right);if(result==true)

Switch(op){case‘+’:s.Push(left+right);break;

case‘-’:s.Push(left-right);break;

case‘*’:s.Push(left*right);break;case‘/’:if(right==0.0){cerr<<“divideby0!”<<endl;s.Clear();}eless.Push(left/right);break;case‘^’:s.Push(power(left,right));break;}

elses.Clear();}数据结构与算法3全文共60页，当前为第24页。voidCalculator::Run(){charch;doublenewoperand;while(cin>>ch,ch!=‘#‘){switch(ch){case‘+’:case‘-’:case‘*’:case‘/’:case‘^’:DoOperator(ch);break;default:cin.Putback(ch);cin>>newoperand;AddOperand(newoperand);break;}}}数据结构与算法3全文共60页，当前为第25页。voidCalculator::clear(){s.MakeEmpty();}#include<Calculator.h>voidmain(){CalculatorCALC(10);CALC.Run();}数据结构与算法3全文共60页，当前为第26页。infixExpressionpostfixExpression

A+B*C#--------ABC*+#

1)迂运算分量输出

2)迂运算符：比较当前运算符与栈顶运算符的优先级.若当前运算符的优先级<=栈顶运算符的优先级,则不断取出运算符栈顶输出,否则进栈.因此一开始栈中要放一个优先级最低的运算符,假设为“#”，例子：A+B+C；A*B-C

(A+B)*(C-D)#------AB+CD-*#

3）迂‘（’:每个运算符有双重优先级.4）迂‘）’:5）迂‘#’:数据结构与算法3全文共60页，当前为第27页。infixExpressionpostfixExpression

voidpostfix(expressione){Stack<char>s;charch,y;s.MakeEmpty();s.Push(‘#’);

while(cin.get(ch),ch!=‘#’){if(isdigit(ch))cout<<ch;

elseif(ch==‘)’)

for(y=s.Pop();y!=‘(‘;y=s.Pop())cout<<y;

else

{for(y=s.Pop();isp(y)>icp(ch);y=s.Pop()) cout<<y;s.Push(y);s.Push(ch);}}

while(!s.IsEmpty()){y=s.Pop();cout<<y;}}

如果合为一步怎么做？实习题。数据结构与算法3全文共60页，当前为第28页。

Chapter3----stack2010年全国统考题1、若元素a,b,c,d,e,f依次进栈，允许进栈、退栈操作交替进行。但不允许连续三次进行退栈工作，则不可能得到的出栈序列是（

）A：dcebfa

B：cbdaef

C：bcaefd

D：afedcb

实习题：

5.中缀表达式后缀表达式对后缀表达式求值,合为一趟来做。数据结构与算法3全文共60页，当前为第29页。3.4.TheQueueADT

Aqueueisalinearlistinwhichadditionsanddeletionstakeplaceatdifferentends.Itisalsocalledafirst-in-first-outlist.Theendatwhichnewelementsareaddediscalledtherear.Theendfromwhicholdelementsaredeletediscalledthefront.数据结构与算法3全文共60页，当前为第30页。3.4.1.QueueModel

Samplequeues

frontrearfrontrearfrontrearABCBCBCD

DeleteA

AddD数据结构与算法3全文共60页，当前为第31页。QueueModel

AbstractDataTypeQueue

{

instancesorderedlistofelements;oneendiscalledthefront;theotheristherear;operationsCreate():Createanemptyqueue;IsEmpty():Returntrueifqueueisempty,returnfalseotherwise;IsFull():returntrueifqueueisfull,returnfalseotherwise;First():returnfirstelementofthequeue;Last():returnlastelementofthequeue;Add(x):addelementxtothequeue;Delete(x):deletefrontelementfromthequeueandputitinx;}

数据结构与算法3全文共60页，当前为第32页。3.4.2.ArrayImplementationofQueue

ABC……theArray:front

back012n-1

XcurrentSizethequeuesize:currentSize;anemptyqueuehascurrentSize==0;anfullqueuehascurrentSize==theArray.length;数据结构与算法3全文共60页，当前为第33页。3.4.2.ArrayImplementationofQueue

Toaddanelement:back=back+1;theArray[back]=x;

Todeleteanelement:twomethods:1)front=front+1;O(1)2)shiftthequeueonepositionleft. O(n)数据结构与算法3全文共60页，当前为第34页。3.4.2.ArrayImplementationofQueue

frontbackfrontbackfrontbackABC…BC…BCD…数据结构与算法3全文共60页，当前为第35页。3.4.2.ArrayImplementationofQueue

…ABCDEFrontbackFreespace数据结构与算法3全文共60页，当前为第36页。3.4.2.ArrayImplementationofQueue

touseacirculararraytorepresentaqueue

backCBAfrontbackCBAfrontD

Addtion数据结构与算法3全文共60页，当前为第37页。3.4.2.ArrayImplementationofQueue

deletionCBAfront

DbackdeletionCBfrontbackD数据结构与算法3全文共60页，当前为第38页。3.4.2.ArrayImplementationofQueueHowimplementationacirculararray:WhenfrontorbackreachstheArray.length-1,reset02)back=(back+1)%theArray.lengthfront=(front+1)%theArray.length数据结构与算法3全文共60页，当前为第39页。3.4.2.ArrayImplementationofQueuePublicclassQueueAr{publicQueueAr()publicQueueAr(intcapacity)publicbooleanisEmpty(){returncurrentsize==0;}publicbooleanisfull(){returncurrentSize==theArray.length;}publicvoidmakeEmpty()

publicObjectgetfront()publicvoidenqueue(Objectx)throwOverflowprivateintincrement(intx)

privateObjectdequeue()privateObject[]theArray;privateintcurrentSize;privateintfront;privateintback;staticfinalintDEFAULT_CAPACITY=10;}数据结构与算法3全文共60页，当前为第40页。3.4.2.ArrayImplementationofQueue

publicQueueAr(){this(DEFAULT_CAPACITY);

}publicQueueAr(intcapacity){theArray=newObject[capacity];makeEmpty();}publicvoidmakeEmpty(){currentSize=0;front=0;back=-1;}

数据结构与算法3全文共60页，当前为第41页。3.4.2.ArrayImplementationofQueuepublicvoidenqueue(objectx)throwOverflow{if(isFull())thrownewOverflow();back=increment(back);theArray[back]=x;currentSize++;}privateintincrement(intx){if(++x==theArray.length)x=0;returnx;}

数据结构与算法3全文共60页，当前为第42页。3.4.2.ArrayImplementationofQueuepublicObjectdequeue(){if(isEmpty())returnnull;currentSize--;ObjectfromtItem=theArray[front];theArray[front]=null;front=increment(front);returnfrontItem;}

数据结构与算法3全文共60页，当前为第43页。3.4.3LinkedRepresentationofqueue

Linkedqueues

datalink……^frontbacka1a2

an数据结构与算法3全文共60页，当前为第44页。3.4.3LinkedRepresentationofqueue

Classdefinitionforalinkedqueuetemplate<classT>classLinkedQueue{public:LinkedQueue(){front=back=0;}~LinkedQueue();boolIsEmpty()const{return((front)?false:true);}boolIsFull()const;TFirst()const;TLast()const;LinkedQueue<T>&Add(constT&x);LinkedQueue<T>&Delete(T&x);privarte:Node<T>*front;Node<T>*back;};数据结构与算法3全文共60页，当前为第45页。3.4.3LinkedRepresentationofqueue1)destructortemplate<classT>LinkedQueue<T>::~LinkedQueue(){Node<T>*next;while(front){next=front.link;deletefront;front=next;}}数据结构与算法3全文共60页，当前为第46页。3.4.3LinkedRepresentationofqueue2)Add(x)

template<classT>LinkedQueue<T>&LinkedQueue<T>::Add(constT&x){Node<T>*p=newNode<T>;p.data=x;p.link=0;

if(front)back.link=p;elsefront=p;back=p;return*this;}数据结构与算法3全文共60页，当前为第47页。3.4.3LinkedRepresentationofqueue3)Delete(x)

template<classT>LinkedQueue<T>&LinkedQueue<T>::Delete(T&x){if(IsEmpty())throwOutOfBounds();x=front.data;

Node<T>*p=front;front=front.link;deletep;return*this;}数据结构与算法3全文共60页，当前为第48页。3.4.4Application1)Printthecoefficientsofthebinomialexpansion(a+b)i,i=1,2,3,…,n11121133114641151010511615201561数据结构与算法3全文共60页，当前为第49页。Printthecoefficientsofthebinomialexpansion#include<stdio.h>#include<iostream.h>#include“queue.h”voidYANGHUI(intn){Queue<int>q;q.makeEmpty();q.Enqueue(1);q.Enqueue(1);

ints=0;

for(inti=1;i<=n;i++){cout<<

endl;

for(intk=1;k<=10-i;k++)cout<<‘‘;q.Enqueue(0);for(intj=1;j<=i+2;j++){intt=q.Dequeue();q.Enqueue(s+t);s=t;

if(j!=i+2)cout<<s<<‘‘;}}}数据结构与算法3全文共60页，当前为第50页。Printthecoefficientsofthebinomialexpansion用可变长度的二维数组来实现：publicclassYanghui{publicstaticvoidmain(Stringargs[]){intn=10;intmat[][]=newint[n][];//申请第一维的存储空间

inti,j;for(i=0;i<n;i++){mat[i]=newint[i+1];//申请第二维的存储空间，每次长度不同

mat[i][0]=1;mat[i][i]=1;for(j=1;j<i;j++)mat[i][j]=mat[i-1][j-1]+mat[i-1][j];}for(i=0;i<mat.length;i++){for(j=0;j<n-i;j++)System.out.print(““);for(j=0;j<mat[i].length;j++)System.out.print(““+mat[i][j]);System.out.println();}}}数据结构与算法3全文共60页，当前为第51页。2)WireRouting

abA7*7gradAwirebetweenaandb数据结构与算法3全文共60页，当前为第52页。2)WireRouting

ab3221112212b23485678678aDistancelabelingWirepath数据结构与算法3全文共60页，当前为第53页。步骤:

1.搜索过程*先从位置a(3,2)开始,把a可到达的相邻方格都表为1(表示与a相距为1).注意:具体实现时,将a位置置为2,其它相邻方格为a位置的值+1*然后把标记为1的方格可到达的相邻方格都标记为2(表示与a相距为2).这里需要什么数据结构?*标记过程继续进行下去,直至到达b或找不到可到达的相邻方格为止.本例中,当到达b时,

b上的表记为9(实现时为9+2=11)

2.构造a---b的路径.从b回溯到a

.这里需要什么数据结构?

*从b出发,并将b的位置保存在path中.首先移动到比b的编号小1的相邻位置上(5,6)*接着再从当前位置继续移动到比当前标号小1的相邻位置上.*重复这一过程,直至到达a.数据结构与算法3全文共60页，当前为第54页。2)WireRouting

boolFindPath(Positionstart,Positionfinish,int&PathLen,Position*&path){if((start.row==finish.row)&&(start.col==finish.col)){PathLen=0;returntrue;}for(inti=0;i<=m+1;i++){grid[0][i]=grid[m+1][i]=1;grid[i][0]=grid[i][m+1]=1;}Positionoffset[4];offset[0].row=0;offset[0].col=1;offset[1].row=1;offset[1].col=0;offset[2].row=0;offset[2].col=-1;offset[3].row=-1;offset[3].col=0;intNumOfNbrs=4;Positionhere,nbr;here.row=start.row;here.col=start.col;grid[start.row][start.col]=2;数据结构与算法3全文共60页，当前为第55页。2)WireRouting

LinkedQueue<Position>Q;do{//labelneighborsofherefor(inti=0;i<NumOfNbrs;i++){nbr.row=here.row+offset[i].row;nbr.col=here.col+offset[i].col;if(grid[nbr.row][nbr.col]==0){grid[nbr.row][nbr.col]=grid[here.row][here.col