數據結構與算法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+*#

無括號；運算分量的次序不變；運算符的次序就是具體執(zhí)行的次序。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)迂運算符：比較當前運算符與棧頂運算符的優(yōu)先級.若當前運算符的優(yōu)先級<=棧頂運算符的優(yōu)先級,則不斷取出運算符棧頂輸出,否則進棧.因此一開始棧中要放一個優(yōu)先級最低的運算符,假設為“#”，例子：A+B+C；A*B-C

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

3）迂‘（’:每個運算符有雙重優(yōu)先級.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年全國統(tǒng)考題1、若元素a,b,c,d,e,f依次進棧，允許進棧、退棧操作交替進行。但不允許連續(xù)三次進行退棧工作，則不可能得到的出棧序列是（

）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).這里需要什么數據結構?*標記過程繼續(xù)進行下去,直至到達b或找不到可到達的相鄰方格為止.本例中,當到達b時,

b上的表記為9(實現時為9+2=11)

2.構造a---b的路徑.從b回溯到a

.這里需要什么數據結構?

*從b出發(fā),并將b的位置保存在path中.首先移動到比b的編號小1的相鄰位置上(5,6)*接著再從當前位置繼續(xù)移動到比當前標號小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