2013軟件工程數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)指導(dǎo)書

給大家的實(shí)驗(yàn)文檔中分為一下幾部分實(shí)驗(yàn)準(zhǔn)備：其中是C++的一些內(nèi)容，希望大家能借此好好復(fù)習(xí)C++。因?yàn)榇蠹椰F(xiàn)在使用的教材是C++版本的，所以，對(duì)于C++的一些基本語法，程序的編寫都需要有些了解c語言實(shí)驗(yàn)教案中是一些c語言的基礎(chǔ)知識(shí)，包括VC環(huán)境的使用和程序的調(diào)試，希望對(duì)c語言已經(jīng)忘記的同學(xué)好好看看復(fù)習(xí)一下。（程序的編寫調(diào)試是長年累月的過程，需要不斷的積累，寫得多了，程序調(diào)試的多了，自然就熟練了）對(duì)應(yīng)的flash課件：其中是一些實(shí)驗(yàn)的flash課件演示，給大家做一下參考實(shí)驗(yàn)指導(dǎo)書和實(shí)驗(yàn)教案大家在做每個(gè)實(shí)驗(yàn)前都需要看看。閱讀的時(shí)候，可以使用【視圖】|【文檔結(jié)構(gòu)圖】，可以比較自由跳到相應(yīng)位置總體實(shí)驗(yàn)難度比較大，時(shí)間緊，單靠實(shí)驗(yàn)課上的幾個(gè)學(xué)時(shí)，作為初學(xué)者是無法完成的，需要大家在課前課后盡自己最大的努力。實(shí)驗(yàn)一棧和隊(duì)列（2學(xué)時(shí)）實(shí)驗(yàn)二多項(xiàng)式加減法（2學(xué)時(shí)）實(shí)驗(yàn)三迷宮（4學(xué)時(shí)）實(shí)驗(yàn)四二叉樹（4學(xué)時(shí)）實(shí)驗(yàn)五圖（2學(xué)時(shí)）實(shí)驗(yàn)六歸并排序（2學(xué)時(shí)）ProgrammingProjectone:ApplicationofStack&Queue一、實(shí)驗(yàn)?zāi)康耐ㄟ^幾段代碼的編寫，熟悉棧和隊(duì)列二、實(shí)驗(yàn)內(nèi)容1、Reversingalist(必做，分3個(gè)小題目task1,task2,task3)2、Smallairportsimulation(選作)具體如下：Task1:Compileandrunthefollowingsampleapplicationofstackfromthetext.Youmayneedtomakechangestothecodeifnecessary.Writedownyourinputandoutput.//Section2.1:ReversingaList#include<stack>intmain()/*Pre:Theusersuppliesanintegernandndecimalnumbers.Post:Thenumbersareprintedinreverseorder.Uses:TheSTLclassstackanditsmethods*/{intn;doubleitem;stack<double>numbers;//declaresandinitializesastackofnumberscout<<"Typeinanintegernfollowedbyndecimalnumbers."<<endl<<"Thenumberswillbeprintedinreverseorder."<<endl;cin>>n;for(inti=0;i<n;iCC){cin>>item;numbers.push(item);}cout<<endl<<endl;while(!numbers.empty()){cout<<numbers.top()<<"";numbers.pop();}cout<<endl;}Task2:Assembletheappropriatedeclarationsfromthetextintothefilesstack.handstack.cpp.Makeanynecessarychangesasre-compilingtheaboveapplicationReversingaListbyreplacingtheuseofSTLclassstackwiththeuseofuserdefinedclassStack.//Section2.2:constintmaxstack=10;//smallvaluefortestingclassStack(public:Stack();boolempty()const;Error_codepop();Error_codetop(Stack_entry&item)const;Error_codepush(constStack_entry&item);private:intcount;Stack_entryentry[maxstack];};Error_codeStack::push(constStack_entry&item)/*Pre:None.Post:IftheStackisnotfull,itemisaddedtothetopoftheStack.IftheStackisfull,anError_codeofoverflowisreturnedandtheStackisleftunchanged.*/{Error_codeoutcome=success;if(count>=maxstack)outcome=overflow;elseentry[count++]=item;returnoutcome;}Error_codeStack::pop()/*Pre:None.Post:IftheStackisnotempty,thetopoftheStackisremoved.IftheStackisempty,anError_codeofunderflowisreturned.*/{Error_codeoutcome=success;if(count==0)outcome=underflow;else--count;returnoutcome;}Error_codeStack::top(Stack_entry&item)const/*Pre:None.Post:IftheStackisnotempty,thetopoftheStackisreturnedinitem.IftheStackisemptyanError_codeofunderflowisreturned.*/{Error_codeoutcome=success;if(count==0)outcome=underflow;elseitem=entry[count-1];returnoutcome;}boolStack::empty()const/*Pre:None.Post:IftheStackisempty,trueisreturned.Otherwisefalseisreturned.*/{booloutcome=true;if(count>0)outcome=false;returnoutcome;}Stack::Stack()/*Pre:None.Post:Thestackisinitializedtobeempty.*/{count=0;}Task3:Assumethefollowingdefinitionfileforanextendedstackdatastructure.classExtended_stack{public:Extended_stack();Error_codepop();Error_codepush(Stack_entryitem);Error_codetop(Stack_entry&item)const;boolempty()const;voidclear();//Resetthestacktobeempty.boolfull()const;//Ifthestackisfull,returntrue;size()const;//Returnthenumberofentriesinthestack.private:intcount;Stack_entryentry[maxstack];};Implementthefollowingmethods:(a)clear(b)full(c)sizeUsemethodsizeoftheclassExtended_stackinyourapplicationReversingaListtodisplaythenumberofdecimalnumbersyouimputed.Task4:Combineallthefunctionsandmethodsfortheairportsimulationintoacompleteprogram.Experimentwithseveralsamplerumsoftheairportsimulation,adjustingthevaluesfortheexpectednumbersofplanesreadytolandandtakeoff.Findapproximatevaluesfortheseexpectednumbersthatareaslargeaspossiblesubjecttotheconditionthatitisveryunlikelythataplanemustberefusedservice.Whathappenstothesevaluesifthemaximumsizeofthequeuesisincreasedordecreased?/*ProgramextractsfromChapter3of"DataStructuresandProgramDesigninC++"byRobertL.KruseandAlexanderJ.RybaCopyright(C)1999byPrentice-Hall,Inc.Allrightsreserved.Extractsfromthisfilemaybeusedintheconstructionofotherprograms,butthiscodewillnotcompileorexecuteasgivenhere.*///Section3.3:constintmaxqueue=10;//smallvaluefortestingclassQueue(public:Queue();boolempty()const;Error_codeserve();Error_codeappend(constQueue_entry&item);Error_coderetrieve(Queue_entry&item)const;protected:intcount;intfront,rear;Queue_entryentry[maxqueue];};Queue::Queue()/*Post:TheQueueisinitializedtobeempty.*/{count=0;rear=maxqueue-1;front=0;boolQueue::empty()const/*Post:ReturntrueiftheQueueisempty,otherwisereturnfalse.*/{returncount==0;}Error_codeQueue::append(constQueue_entry&item)/*Post:itemisaddedtotherearoftheQueue.IftheQueueisfullreturnanError_codeofoverflowandleavetheQueueunchanged.*/{if(count>=maxqueue)returnoverflow;count++;rear=((rear+1)==maxqueue)?0:(rear+1);entry[rear]=item;returnsuccess;}Error_codeQueue::serve()/*Post:ThefrontoftheQueueisremoved.IftheQueueisemptyreturnanError_codeofunderflow.*/{if(count<=0)returnunderflow;count--;front=((front+1)==maxqueue)?0:(front+1);returnsuccess;}Error_codeQueue::retrieve(Queue_entry&item)const/*Post:ThefrontoftheQueueretrievedtotheoutputparameteritem.IftheQueueisemptyreturnanError_codeofunderflow.*/{if(count<=0)returnunderflow;item=entry[front];returnsuccess;}intExtended_queue::size()const/*Post:ReturnthenumberofentriesintheExtended_queue.*/{returncount;}//Section3.5:intmain()//Airportsimulationprogram/*Pre:Theusermustsupplythenumberoftimeintervalsthesimulationistorun,theexpectednumberofplanesarriving,theexpectednumberofplanesdepartingpertimeinterval,andthemaximumallowedsizeforrunwayqueues.Post:Theprogramperformsarandomsimulationoftheairport,showingthestatusoftherunwayateachtimeinterval,andprintsoutasummaryofairportoperationattheconclusion.Uses:ClassesRunway,Plane,Randomandfunctionsrun_idle,initialize.*/{intend_time;//timetorunsimulationintqueue_limit;//sizeofRunwayqueuesintflight_number=0;doublearrival_rate,departure_rate;initialize(end_time,queue_limit,arrival_rate,departure_rate);Randomvariable;Runwaysmall_airport(queue_limit);for(intcurrent_time=0;current_time<end_time;current_time++){//loopovertimeintervalsintnumber_arrivals=variable.poisson(arrival_rate);//currentarrivalrequestsfor(inti=0;i<number_arrivals;i++){Planecurrent_plane(flight_number++,current_time,arriving);if(small_airport.can_land(current_plane)!=success)current_plane.refuse();}intnumber_departures=variable.poisson(departure_rate);//currentdeparturerequestsfor(intj=0;j<number_departures;j++)(Planecurrent_plane(flight_number++,current_time,departing);if(small_airport.can_depart(current_plane)!=success)current_plane.refuse();}Planemoving_plane;switch(small_airport.activity(current_time,moving_plane))(//LetatmostonePlaneontotheRunwayatcurrent_time.caseland:moving_plane.land(current_time);break;casetakeoff:moving_plane.fly(current_time);break;caseidle:run_idle(current_time);}}small_airport.shut_down(end_time);}enumRunway_activity{idle,land,takeoff};classRunway{public:Runway(intlimit);Error_codecan_land(constPlane¤t);Error_codecan_depart(constPlane¤t);Runway_activityactivity(inttime,Plane&moving);voidshut_down(inttime)const;private:Extended_queuelanding;Extended_queuetakeoff;intqueue_limit;intnum_land_requests;//numberofplanesaskingtolandintnum_takeoff_requests;intnum_landings;intnum_takeoffs;intnum_land_accepted;intintnum_takeoff_requests;intnum_landings;intnum_takeoffs;intnum_land_accepted;intnum_takeoff_accepted;intnum_land_refused;intnum_takeoff_refused;intland_wait;inttakeoff_wait;intidle_time;//numberofplanesthathavelanded//numberofplanesthathavetakenoff//numberofplanesqueuedtoland//numberofplanesqueuedtotakeoff//numberoflandingplanesrefused//numberofdepartingplanesrefused//totaltimeofplaneswaitingtoland//totaltimeofplaneswaitingtotakeoff//totaltimerunwayisidle};enumPlane_status{null,arriving,departing};classPlane{public:Plane();Plane(intflt,inttime,Plane_statusstatus);voidrefuse()const;voidland(inttime)const;voidfly(inttime)const;intstarted()const;private:intflt_num;intclock_start;Plane_statusstate;};voidinitialize(int&end_time,int&queue_limit,double&arrival_rate,double&departure_rate)/*Pre:Theuserspecifiesthenumberoftimeunitsinthesimulation,themaximalqueuesizespermitted,andtheexpectedarrivalanddepartureratesfortheairport.Post:Theprogramprintsinstructionsandinitializestheparametersend_time,queue_limit,arrival_rate,anddeparture_ratetothespecifiedvalues.Uses:utilityfunctionuser_says_yes*/cout<<"Thisprogramsimulatesanairportwithonlyonerunway."<<endl<<"Oneplanecanlandordepartineachunitoftime."<<endl;cout<<"Uptowhatnumberofplanescanbewaitingtoland"<<"ortakeoffatanytime?"<<flush;cin>>queue_limit;cout<<"Howmanyunitsoftimewillthesimulationrun?"<<flush;cin>>end_time;boolacceptable;do{cout<<"Expectednumberofarrivalsperunittime?"<<flush;cin>>arrival_rate;cout<<"Expectednumberofdeparturesperunittime?"<<flush;cin>>departure_rate;if(arrival_rate<0.0||departure_rate<0.0)cerr<<"Theseratesmustbenonnegative."<<endl;elseacceptable=true;if(acceptable&&arrival_rate+departure_rate>1.0)cerr<<"SafetyWarning:Thisairportwillbecomesaturated."<<endl;}while(!acceptable);}Runway::Runway(intlimit)/*Post:TheRunwaydatamembersareinitializedtorecordnopriorRunwayuseandtorecordthelimitonqueuesizes.*/{queue_limit=limit;num_land_requests=num_takeoff_requests=0;num_landings=num_takeoffs=0;num_land_refused=num_takeoff_refused=0;num_land_accepted=num_takeoff_accepted=0;land_wait=takeoff_wait=idle_time=0;}Error_codeRunway::can_land(constPlane¤t)/*Post:Ifpossible,thePlanecurrentisaddedtothelandingQueue;otherwise,anError_codeofoverflowisreturned.TheRunwaystatisticsareupdated.Uses:classExtended_queue.*/{Error_coderesult;if(landing.size()<queue_limit)result=landing.append(current);elseresult=fail;num_land_requests++;if(result!=success)num_land_refused++;elsenum_land_accepted++;returnresult;}Error_codeRunway::can_depart(constPlane¤t)/*Post:Ifpossible,thePlanecurrentisaddedtothetakeoffQueue;otherwise,anError_codeofoverflowisreturned.TheRunwaystatisticsareupdated.Uses:classExtended_queue.*/{Error_coderesult;if(takeoff.size()<queue_limit)result=takeoff.append(current);elseresult=fail;num_takeoff_requests++;if(result!=success)num_takeoff_refused++;elsenum_takeoff_accepted++;returnresult;}Runway_activityRunway::activity(inttime,Plane&moving)/*Post:IfthelandingQueuehasentries,itsfrontPlaneiscopiedtotheparametermovingandaresultlandisreturned.Otherwise,ifthetakeoffQueuehasentries,itsfrontPlaneiscopiedtotheparametermovingandaresulttakeoffisreturned.Otherwise,idleisreturned.Runwaystatisticsareupdated.Uses:classExtended_queue.*/{Runway_activityin_progress;if(!landing.empty()){landing.retrieve(moving);land_wait+=time-moving.started();num_landings++;in_progress=land;landing.serve();}elseif(!takeoff.empty()){takeoff.retrieve(moving);takeoff_wait+=time-moving.started();num_takeoffs++;in_progress=takeoff;takeoff.serve();}else{idle_time++;in_progress=idle;}returnin_progress;}Plane::Plane(intflt,inttime,Plane_statusstatus)/*Post:ThePlanedatamembersflt_num,clock_start,andstatearesettothevaluesoftheparametersflt,timeandstatus,respectively.*/{flt_num=flt;clock_start=time;state=status;cout<<"Planenumber"<<flt<<"readyto";if(status==arriving)cout<<"land."<<endl;elsecout<<"takeoff."<<endl;}Plane::Plane()/*Post:ThePlanedatamembersflt_num,clock_start,statearesettoillegaldefaultvalues.*/{flt_num=-1;clock_start=-1;state=null;}voidPlane::refuse()const/*Post:ProcessesaPlanewantingtouseRunway,whentheQueueisfull.*/{cout<<"Planenumber"<<flt_num;if(state==arriving)cout<<"directedtoanotherairport"<<endl;elsecout<<"toldtotrytotakeoffagainlater"<<endl;}voidPlane::land(inttime)const/*Post:ProcessesaPlanethatislandingatthespecifiedtime.*/{intwait=time-clock_start;cout<<time<<":Planenumber"<<flt_num<<"landedafter"<<wait<<"timeunit"<<((wait==1)?"":"s")<<"inthetakeoffqueue."<<endl;}voidPlane::fly(inttime)const/*Post:ProcessaPlanethatistakingoffatthespecifiedtime.*/{intwait=time-clock_start;cout<<time<<":Planenumber"<<flt_num<<"tookoffafter"<<wait<<"timeunit"<<((wait==1)?"":"s")<<"inthetakeoffqueue."<<endl;}intPlane::started()const/*Post:ReturnthetimethatthePlaneenteredtheairportsystem.*/{returnclock_start;}voidrun_idle(inttime)/*Post:Thespecifiedtimeisprintedwithamessagethattherunwayisidle.*/{cout<<time<<":Runwayisidle."<<endl;}voidRunway::shut_down(inttime)const/*Post:Runwayusagestatisticsaresummarizedandprinted.*/cout<<"Simulationhasconcludedafter"<<time<<"timeunits."<<endl<<"Totalnumberofplanesprocessed"<<(num_land_requests+num_takeoff_requests)<<endl<<"Totalnumberofplanesaskingtoland"<<num_land_requests<<endl<<"Totalnumberofplanesaskingtotakeoff"<<num_takeoff_requests<<endl<<"Totalnumberofplanesacceptedforlanding"<<num_land_accepted<<endl<<"Totalnumberofplanesacceptedfortakeoff"<<num_takeoff_accepted<<endl<<"Totalnumberofplanesrefusedforlanding"<<num_land_refused<<endl<<"Totalnumberofplanesrefusedfortakeoff"<<num_takeoff_refused<<endl<<"Totalnumberofplanesthatlanded"<<num_landings<<endl<<"Totalnumberofplanesthattookoff"<<num_takeoffs<<endl<<"Totalnumberofplanesleftinlandingqueue"<<landing.size()<<endl<<"Totalnumberofplanesleftintakeoffqueue"<<takeoff.size()<<endl;cout<<"Percentageoftimerunwayidle"<<100.0*((float)idle_time)/((float)time)<<"%"<<endl;cout<<"Averagewaitinlandingqueue"<<((float)land_wait)/((float)num_landings)<<"timeunits";cout<<endl<<"Averagewaitintakeoffqueue"<<((float)takeoff_wait)/((float)num_takeoffs)<<"timeunits"<<endl;cout<<"Averageobservedrateofplaneswantingtoland"<<((float)num_land_requests)/((float)time)<<"pertimeunit"<<endl;cout<<"Averageobservedrateofplaneswantingtotakeoff"<<((float)num_takeoff_requests)/((float)time)<<"pertimeunit"<<endl;3/*************************************************************************/ProgrammingProjecttwoPolynomialArithmetic一、實(shí)驗(yàn)?zāi)康倪M(jìn)一步熟悉數(shù)據(jù)結(jié)構(gòu)中的棧和隊(duì)列進(jìn)一步練習(xí)使用棧和隊(duì)列實(shí)現(xiàn)簡(jiǎn)單的算法二、實(shí)驗(yàn)內(nèi)容編寫程序?qū)崿F(xiàn)多項(xiàng)式的加減法，具體如下：Assemblethefunctionsdevelopedinsection4.5andthefunctionsget_command(),introduction()andinstructions()illustratedbelow,makethenecessarychangesinthecode,writethePolynomialmethodequals_differenceastoproduceaworkingskeletonforthecalculatorprogram,onethatwillread,write,add,andsubtractpolynomials.voidintroduction()/*PRE:None.POST:AnintroductiontotheprogramPolynomialCalculatorisprinted.*/{cout<<"PolynomialCalculatorProgram."<<endl<<"Thisprogramsimulatesapolynomialcalculatorthatworksona\n”<<"stackandalistofoperations.ItmodelsareversePolish\n"<<"calculatorwhereoperandsareenteredbeforetheoperators.An\n"<<"exampletoaddtwopolynomialsandprinttheansweris?P?Q+=.\n"<<"PandQaretheoperandstobeentered,+isadd,and=is\n"<<"printresult.Theresultisputontothecalculator'sstack.\n\n";}voidinstructions()/*PRE:None.POST:Printsouttheinstructionsandtheoperationsallowedonthecalculator.*/{cout<<"\nEnterastringofinstructionsinreversePolishform.\n"<<"Theallowableinstructionsare:\n\n"<<"?:Read+:Add=:Print-:Subtract\n"<<"*:Multiplyq:Quit/:Divideh:Help\n\n”;}charget_command()/*PRE:None.POST:Alegalcommandisreadfromtheuserandreturned.*/{charcommand,d;cout<<"Selectcommandandpress<Enter>:〃；while(1){do{cin.get(command);}while(command=='\n');do{cin.get(d);}while(d!='\n');command=tolower(command);if(command=='?'||command=='='||command=='+'||command=='-'||command=='h'||command=='*'||command=='/'||command=='q'||command=='p'||command=='h'){return(command);}cout<<"Pleaseenteravalidcommand:"<<endl;instructions();}}ProgrammingProjectthree-MazePathSearching一、實(shí)驗(yàn)?zāi)康耐ㄟ^設(shè)計(jì)走迷宮的算法，了解遞歸程序設(shè)計(jì)，使用非遞歸和遞歸方法分別完成走迷宮的算法二、PROBLEMDESCRIPTIONAmazeisarectangularspacewithanentranceattheupperleft-handcorner,anexitatthelowerright-handcorner,andsomeinternalwalls.Youralgorithmwillfindapaththroughagivenmazestartingfromtheentranceandfinishingattheexitthatdoesnotgothroughanywalls(apathmustgoaroundwalls).Youwillrepresentthemazebyatwodimensionalarray,MAZE[m][n],whereavalueof1impliesablockedpath,whilea0meansonecanwalkrightonthrough.Thesearchalgorithmwillstartatmaze[0][0]andfindapathtomaze[n][m].Youaretoimplementthealgorithmforfindingapaththrougharectangularmazebyusingastack.Ifapathisfound,thepositionsinthepathareprintedtostdoutwithasuccessmessage,otherwise,anerrormessageisprintedtothescreen.Yourprogramwillprintthepaths.Apathisrepresentedbyasequenceofmaze[i][j]coordinatesstartingwithmaze[0][0]andendingwithmaze[n][m].Apathcanmovefromonepositiontoanotheratanydirectionshorizontally,verticallyordiagonally.Fromaposition(i,j)inapath,thenextpositioninthepathcanbeanyoneof8contiguouspositionstotheright,lowerright,down,lowerleft,left,upperleft,up,orupperrightfrompositions(i,j).Youaretousethefollowingdataofthearrayofa10x10forthemaze:Enter->0111000000000100010001011001000100101100010010110011101010000010001011001000101101101010000000101100-->EXITThefollowingisaonepossiblepaththroughthismaze:Path:(maze[0][0],maze[1][0],maze[1][1],maze[1][2],maze[2][2],

Enter->X11100X---X---X0X---X---X100X1X001X11X---X1X001X---X1X11X0010X1X11X0111X1X1X---X0001X---X---X1X110010001X110110101X--X--X000010110X-->EXITmaze[3][2],maze[6][4],maze[2][5],maze[0][8],maze[5][8],maze[8][8],maze[3][3],maze[6][5],maze[2][6],maze[1][8],maze[5][7],maze[8][9],maze[4][3],maze[5][5],maze[3][2],maze[6][4],maze[2][5],maze[0][8],maze[5][8],maze[8][8],maze[3][3],maze[6][5],maze[2][6],maze[1][8],maze[5][7],maze[8][9],maze[4][3],maze[5][5],maze[1][6],maze[2][8],maze[6][7],maze[9][9])maze[5][3],maze[4][5],maze[0][6],maze[3][8],maze[7][7],maze[6][3],maze[3][5],maze[0][7],maze[4][8],maze[8][7],Youwillprintthemaze,using'0'toindicatednon-wallpositionsand,1,toindicatewallpositionsinthemaze.Yourprogramwillsearchforapathfromthemazeentrancepointtotheexitpointinthemaze.Thepathsearchingalgorithmwillterminateeitherwhenitfindsapaththroughthemazeorwhenitdeterminesthatthereisnopaththroughthemaze.Yourprogramwilleitherprintanerrormessage(ifthereisnopaththroughthemaze)orwillprint:Thepathasalistof(i,j)positionsstartingattheentrancepointandendingatthemazeexitpointThelengthofthepathThemazewiththepathcoordinatesindicatedby'X'characters.Yourprogramwillsearchforapathfromthemazeentrancepointtotheexitpointinthemaze,andprintthepathoranerrormessageindicatingtheresultsofthesearchasinstep(3)above.ThePathFindingAlgorithmYoushouldimplementthefollowingalgorithmforfindingapath(thedetailsareleftforyoutofillin):Setlisttothemazeentrancecoordinatesanddirectionup;Whilelistisnotemptydo{(i,j,mov)<-coordinatesanddirectionfromfrontoflist;whiletherearemoremovesdo{if(g,h)=(m,n)thensuccess;ifMAZE(g,h)=0andMARK(g,h)=0//themoveislegalandwehaven’tbeenherebeforethen{[MARK(g,h)<-1;add(i,j,mov)tofrontoflist;(i,j,mov)<-(g,h,null)}}}printnopathhasbeenfoundDataStructuresArrayMAZE[m][n]holdsthemaze.ArrayMARK[m][n]iszeroinspot(i,j)ifMAZE(i,j)hasnotyetbeenreached.MOVE[7][1]isatableusedtochangecoordinates(i,j)tooneofthepossibledirections.Usestacktoholdthecurrentpath.HANDINFilesinyourprojectshouldinclude:Allprojectfilesnecessaryforcompilingyourcode(includeanyoftheclassesthatthatyouuseinyoursolution).AMakefileforbuildingyourcodeAREADMEfilewith:Thenamesofthetwosearchmethodsinyourimplementation.Thebig-Ocomplexityofeachsearchshowinghowyoucomputedit.Path(MAZE,MARK,m,n,MOVE,STACK)//AbinarymatrixMAZE(0:m+1,0:n+1)holdsthemaze.STACK(mn,2)recordsthepath//{MARK(1,1)=1;STACK.push((1,1,1));WhilenotSTACK.empty(){(i,j,mov)=STACK.top();STACK.pop();Whilemov!=8{g=i+MOVE(mo