课程资源数据结构与算法

TheStackStackAstackisalistinwhichinsertionsanddeletionstake ceatthesameend.Thisendiscalledthetop.Theotherendofthelistiscalledthebottom.ItisalsocalledaLIFO(last-in-first-out)Stack

StackB

E🡨top

Stacklistofelements;oneendiscalledthebottom;theotheristhetop;Create():CreateanemptyIsEmpty():Returntrueifstackisempty,returnfalseotherwiseIsFull():Returntrueifstackiffull,returnfalseotherwise;Top():returntopelementofthestack;Add(x):addelementxtotheDelete(x):Deletetopelementfromstackandputitin}ImplementationofLinkedListImplementationof

^^whentopOfStack==nullisemptyLinkedListImplementationofpublicclass publicStackLi(){topOfStack=null;}publicbooleanisFull(){returnfalse;publicbooleanisEmpty(){returntopOfStack==null;publicvoidmakeEmpty(){topOfStack=null;publicvoidpush(objectx)publicobjecttop()publicvoidpop()throwsUnderflowpublicobjecttopAndPop()privateListNode}ClassskeletonforlinkedlistimplementationofthestackLinkedListImplementationofSomepublicvoidpush(objectx{topOfStack=newListNode(x,topOfStack}publicobjecttop({if(isEmpty())returnnull;return}LinkedListImplementationofpublicvoidpop()throws{if(isEmpty()thrownewUnderflow();topOfStack=topOfStack.next;}publicobjecttopAndPop({if(isEmpty())returnnull;objecttopItem=topOfstack.element;topOfStack=topOfStack.next;returntopItem;}3.3.2.ImplementationofArrayImplementationofwhentopOfStack==-1isemptyArrayImplementationofpublicclass publicStackAr(publicStackAr(intcapacitypublicbooleanisEmpty(){returntopOfStack==-1;publicbooleanisFull(){returntopOfStack==theArray.length–1;}publicvoidmakeEmpty(){topOfStack=-1;}publicvoidpush(objectx)throwspublicobjecttop(publicvoidpop()throwsUnderflowpublicobjecttopAndPop()privateobject[]theArray;privateinttopOfStack;staticfinalintDEFAULT_CAPACITY=}Stackclassskeleton---arrayArrayImplementationofSomepublicStackAr( this(DEFAULT_CAPACITY}publicStackAr(intcapacity theArray=newobject[capacity];topOfStack=-1;}ArrayImplementationofpublicvoidpush(objectx)throws if(isfull())thrownewOverflow();theArray[++topOfStack]=x;}publicobjecttop( if(isEmpty()returnnull;returntheArray[topOfStack}ArrayImplementationofpublicvoidpop()throws if(isEmpty()thrownewUnderflow();theArray[topOfStack--]=null;}publicobjecttopAndPop( if(isEmpty())returnnull;objecttopItem=top();theArray[topOfStack--]=null;reurntopItem;}ArrayImplementationofItiswastefulofspacewhenmultiplestacksaretoWhenthere‟sonlytwostacks,wecanmaintainspaceandtimeefficiencybypegging thebottomofonestackatposition0andthebottomoftheotheratpositionMaxSize-1.Thetwostacksgrowtowardsthemiddleofthearray.ArrayImplementationof MaxSize- TwostacksinanBalancingSymbols(ParenthesisExpression1234567891011121314151617(d+(a+b)*c*(d+e)–f))(( 位置不匹21位置不匹#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; if(expr[i-1]==„(„)s.Add(i);elseif(expr[i-1]==„)‟)try{s.Delete(j); catch(OutOfBounds){cout<<“Nomatchforright<<“at“<<i<<}while(!s.IsEmpty cout<<“Nomatchforleftparenthesisat<<j<<voidstatic charcout<<“typeanexpressionoflengthatcout<<“thepairsofmatchingparenthesesin}ExpressioninfixExpression postfixExpressionEvaluation

无括号；运算分量的次序不变；运算符的次序就是具体执行的次序postfixExpressionEvaluationinfix

postfixExpressionAB*CD*-开辟一个遇分量进栈:enumBoolean{False,True};#include<stack.h>classcalculator{calculator(intsz):s(sz){voidRun( voidclear(voidAddOperand(doublevalue)BooleanGet2Operands(double&left,double&right)voidDoOperator(charop);stack<double>s;}{}double{ifright=s.Pop();ifleft=s.Pop();return}voidcalculator::DoOperator(char{doubleleft,right;Booleanresult;result=Get2Operands(left,right);if(result=Switch{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(}voidCalculator::Run{charch; while(cin>>ch, ch!=„#„){switchDoOperator(ch);break;default:cin.cin>>newoperand;}}}void }voidmain(){CalculatorCALC(10);}infix postfixA+B*C#--------→遇运算分量(操作数)直接遇运算符：比较当前运算符与栈顶运算符的优先级.若当前运算符的优先级<=栈顶运算符的优先级,则不断取出运算符栈顶输出;否则进栈.因此一开始栈中要放一个优先级最低的运算符,假设为“#”A+B+C；A*B-C(A+B)*(C-D)#------→AB+CD-3）遇‘（:压栈每个运算符有双重优先级遇‘）’:不断退栈输出，直到遇到#’:infix postfixvoidpostfix(expression{Stack<char>s;charch,y;s.MakeEmpty();s.Pushwhile(cin.get(ch),ch!= if(isdigit(ch))cout<<elseif(ch==for(y=s.Pop();y!=„(„;y=s.Pop())cout<<y{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;}Chapter 允许连续三次进行退栈工作，则不可能得到的出栈序列是（） 5.中缀表达式 对后缀表达式求值,合为一趟来做。.TheQueueAqueueisalinearlistinwhichadditionsanddeletions ceatdifferentends.Itisalsocalledafirst-in-first-outTheendatwhichnewelementsareaddediscalledtherear.TheendfromwhicholdelementsaredeletediscalledtheQueueSamplefront front

Delete AddQueueDataType{orderedlistofelements;oneendiscalledthefront;theotheristherear;Create():CreateanemptyIsEmpty():Returntrueifqueueisempty,returnfalseotherwise;IsFull():returntrueifqueueisfull,returnfalseotherwise;First():returnfirstelementofthequeue;Last():returnlastelementofthequeue;Add(x):addelementxtothequeue;Delete(x):deletefrontelementfromthequeueandputitin}ArrayImplementationof ABABCX

n-thequeuesize:anemptyqueuehascurrentSize==anfullqueuehascurrentSize==3.4.2.ArrayImplementationofToaddanback=back+1;theArray[back]=x;Todeleteanelement:twomethods: shiftthequeueoneposition 3.4.2.ArrayImplementationoffront front ABC… ABC…BC…BCD…3.4.2.ArrayImplementationof …ABCDE3.4.2.ArrayImplementationofCBACDBAtouseacirculararraytorepresentCBACDBA

3.4.2.ArrayImplementationof

CDCDB

3.4.2.ArrayImplementationofHowimplementationacircularWhenfrontorbackreachstheArray.length-1,reset0 back=(back+1)%theArray.lengthfront=(front+1)%theArray.length3.4.2.ArrayImplementationofPublicclass publicQueueAr(publicQueueAr(intcapacitypublicbooleanisEmpty(){returncurrentsize==0;publicbooleanisfull(){returncurrentSize==theArray.length;publicvoidmakeEmpty(publicObjectgetfront(publicvoidenqueue(Objectx)throwOverflowprivateintincrement(intx)privateObjectdequeue(privateObject[]theArray;privateintcurrentSize;privateintfront;privateintstaticfinalintDEFAULT_CAPACITY=}3.4.2.ArrayImplementationofpublicQueueAr( this(DEFAULT_CAPACITY}publicQueueAr(intcapacity theArray=newObject[capacity];makeEmpty();}publicvoidmakeEmpty( currentSize=0;front=0;back=-}3.4.2.ArrayImplementationofpublicvoidenqueue(objectx)throw if(isFull()thrownewOverflow();back=increment(back);theArray[back]=x;}privateintincrement(intx if(++x==theArray.length)x=0;return}3.4.2.ArrayImplementationofpublicObjectdequeue( if(isEmpty()returnnull;currentSize--ObjectfromtItem=theArray[fronttheArray[front]=null;front=increment(front);returnfrontItem;}3.4.3LinkedRepresentationofLinked^data^ 3.4.3LinkedRepresentationofClassdefinitionforalinked te<classT>class{boolIsFull()const;TTLast()const;LinkedQueue<T>&Add(constT&x);LinkedQueue<T>&Delete(T&x); 3.4.3LinkedRepresentationof te<classT>{{deletefront;}}3.4.3LinkedRepresentationof te<classLinkedQueue<T>&LinkedQueue<T>::Add(const Node<T>*p=newp.p.if(front)back.link=p;elsefront=p;return*this;}LinkedRepresentationof {if(IsEmpty())throwOutOfBounds();x=front.data;front=front.link;deletep;return}Printthecoefficientsofthebinomialexpansion(a+b)i,i=1,2,3,…,n 15 Printthecoefficientsofthebinomial#include<stdio.h>#include<iostream.h>#include“queue.h”voidYANGHUI(intn){Queue<int>q;ints=0;

q.makeEmpty(for(inti=1;{cout<<for(int intt=q.Dequeue();if(j!=i+2)cout<<s<<„}}}Printthecoefficientsofthebinomialpublicclass publicstaticvoidmain(Stringargs[] intn=intmat[][]=newint[n][];inti,j;for(i=0;i<n;

//申请第一维 mat[i]=newint //申请第二维 空间，每次长度不mat[i][0]=1; mat[i][i]=1;for(j=1;j<i;j++)}for(i=0;i<mat.length; for(j=0;j<n-i;j++)System.out.print(“ for(j=0;j<mat[i].length;j++) “+mat[i][j]);System.out.println();}WireababA7*7 Awirebetweenaand2)Wire3312 2 b 468578678abDistance Wire步骤搜索过先从位置a(3,2)开始把a可到达的相邻方格都表为1(表示与a相距为1).注意:具体实现时,将a位置置为2,其它相邻方格为a位置的值+1然后把标记为1的方格可到达的相邻方格都标记为2(表示与a相距为这里需要什么数据结构本例中,当到达b时,b上的表记为9(实现时为9+2=11)构造a---→b的路径 从b回溯到a这里需要什么数据结构

首先移动到比b的编号小1的相接着再从当前位置继续移动到比当前标号小1的相邻位置上重复这一过程,直至到达2)WireboolFindPath(Positionstart,Positionfinish,int&PathLen,Position*&{if((start.row==finish.row)&&(start.col=={PathLen=0;returntrue;}for(inti=0;i<=m+1;i++){grid[0][i]=grid[m+1][i]=grid[i][0]=grid[i][m+1]=Positionoffset[0].row=0;offset[0].col=offset[1].row=1;offset[1].col=offset[2].row=0;offset[2].col=-offset[3].row=-1;offset[3].col=0;intNumOfNbrs=4;Positionhere,here.row= here.col= grid[start.row][start.col]=2)Wiredo{//labelneighborsofherefor(inti=0;i<NumOfNbrs;{nbr.row=here.row+offset[i].row;nbr.col=here.col