(第1版)数据结构实验指导

PAGE

11

3Projects

3.1Project1:PerformanceMeasurement

Givenalistoforderedintegers,numberedfrom0to–1,checkingtoseethatNisnotinthislistprovidesaworstcaseformanysearchalgorithms.

Considertwoalgorithms:oneiscalled“sequentialsearch”whichscansthroughthelistfromlefttoright;andtheotheris“binarysearch”whichisgivenonpage24(Figure2.9)ofyourtextbook.Yourtasksare:

Implementaniterativeversionandarecursiveversionofsequentialsearch;

Implementaniterativeversionofbinarysearch;

Analyzetheworstcasecomplexitiesoftheabovetwoversionsofsequentialsearchandthatofbinarysearch;

Measureandcomparetheworstcaseperformancesoftheabovethreefunctionsfor=100,500,1000,2000,4000,6000,8000,10000.

Tomeasuretheperformanceofafunction,wemayuseC’sstandardlibrarytime.hasthefollowing:

Note:Ifafunctionrunssoquicklythatittakeslessthanaticktofinish,wemayrepeatthefunctioncallsforKtimestoobtainatotalruntime(“TotalTime”),andthendividethetotaltimebytoobtainamoreaccurateduration(“Duration”)forasinglefunofthefunction.Therepetitionfactormustbylargeenoughsothatthenumberofelapsedticksisatleast10ifwewantanaccuracyofatleast10%.

Thetestresultsmustbelistedinthefollowingtable:

Theperformancesofthethreefunctionsmustbeplottedinthesame-run_timecoordinatesystemforillustration.

3.2Project2:ImplementationofLists,andPolynomial

Problems

1.Mergetwoorderedlistsintoanewlinkedlistinwhichthenodesarealsointhisorder.Iflengthsoforiginaltwolistsaremandn,thelengthofnewlinkedlistism+n.

Forexample:

Input:

5(lengthoflist1)

4

26465695

11(lengthoflist2)

15

17263046485658829095

Output:

41517263046485658829095

Demands:

(1).Youshouldusesinglelinkedlist(withaheader)tocreatethefunctionsMakeEmpty,IsEmpty,IsLast,Find,Delete,FindPrevious,Insert,DeleteList,Header,First,Advance,Retrieve(SeeP40,Figure3.6).

(2).Usingabovefunctionstosolvethisproblem.

(3).Thelinkedimplementationoflistshouldbewritteninseparatedfiles(.cppand.h)intheVC++workspace.Theirnamesshouldbelinkedlist.h,linkedlist.cpp,merge.cpp.

2.ThedeclarationsthatfollowgiveusthepolynomialADT.

StructurePolynomialis

Object:;asetoforderedpairsofwhereisthecoefficientandistheexponent.arenonnegativeintegers.

Operations:

Forallpoly,poly1,poly2∈Polynomial,coef∈Coefficients,expon∈Exponents

PolynomialZero()::=returnthepolynomial,P(x)=0

BooleanIsZero(poly)::=if(poly)returnFALSE;

elsereturnTRUE;

CoefficientCoef(poly,expon)::=if(expon∈poly)returnitscoeffient

elsereturnzero.

ExponentLead_Exp(poly)::=returnthelargestexponentinpoly.

PolynomialAttach(poly,coef,expon)::=if(expon∈poly)returnerror

elsereturnthepolynomialpolywiththeterm<coef,expon>inserted.

PolynomialRemove(poly,expon):=if(expon∈poly)returnthepolynomialpolywiththetermwhoseexponentisexpondeleted

elsereturnerror.

PolynomialSingleMult(poly,coef,expon):=returnthepolynomialpoly*coef*xexpon

PolynomialAdd(poly1,poly2):=returnthepolynomialpoly1+poly2.

PolynomialMult(poly1,poly2):=returnthepolynomialpoly1*poly2.

endPolynomial

Demands:

(1).YoushouldchooseasuitablerepresentationforPolynomial.

(2).YoushouldcreatethefunctionsZero,IsZero,Coef,Lead_Exp,Attach,Remove,SingleMult,Add,Mult,andtestthem.

(3).Ifand,writeafunctiontouseabovefunctionstocomputeand.

(4).Analyzeadvantagesofyourrepresentation.

(5).TheimplementationofpolynomialADTshouldbewritteninseparatedfiles(.cppand.h)intheVC++workspace.TheirnamesshouldbePolynomial.h,Polynomial.cpp,main.cpp.

Note:

Yourprogrammustreadfromafile“input.txt”andwritetoafile“output.txt”inthecurrentdirectory.

3.3Project3:ImplementationandApplicationsofStacks

Problems

1.WriteaConversionfunctiontoconverseanydecimaldatatobinaryversion.

Demands:

(1).ImplementStackADTusinglinkedlistrepresentation,whichmustatleasthasfivebasicoperations:Create,IsFull,Push,IsEmptyandPop.

(2).BuildanewprojecttoimplementtheConversionfunction.Theinputandoutputshouldbeaccordingtothefollowingformat:

Pleaseinputthedecimalnumber:15

Thecorrespondingbinaryversionis:1111

Pleaseinputthedecimalnumber:-1

Bye!

2.Writeaprogramtojudgewhetherabracketsequence(maybehasotherletters)is“matching”.The“matching”meansthatiftherehasa‘(‘inaexpressionandtheremusthasa‘)’init.Iftheinputsequenceis“matching”,thenoutput‘ok’,otherwiseoutput‘ERROR’.

Demands

(1).ImplementStackusingarrayrepresentation,whichmustatleasthasfivebasicoperations:Create,IsFull,Push,IsEmptyandPop.

(2).BuildanewprojecttoimplementthebracketMatchingfunction.Theinputandoutputshouldbeaccordingtothefollowingformat:

Pleaseinputtheexpression:a*(b+c)

ThebracketoftheexpressionismatchingOK!

Pleaseinputtheexpression:a*(b+c))

ThebracketoftheexpressionismatchingERROR!

Pleaseinputtheexpression:(a*(b+c)

ThebracketoftheexpressionismatchingERROR!

Note

ThetwoimplementationofStackshouldbewritteninseparatedfiles(.cppand.h)intheVC++workspace.Theirfilesshouldbenameddifferently,suchaslinkedStack.h,linkedStack.cpp,SqStack.h,SqStack.cpp.

3.4Project4:BinaryTreeTraversals

1.Problem

Createbinarytreeasfollow(Figure-1)incomputer,writeoutthefunctionsofinorder,preorder,postorderandlevelorder,andusethemtotraversalthebinarytree.Andcomputetheleafnumberandheightofthebinarytree.

Hint:Youmaychoosesuitablerepresentation,suchaslinkedrepresentationisoftenused.

Figure-1abinarytree

2.Stepsandrestrictconditions

Step1.

Writethefunctionofcreatetocreateatreebyinputdata.

Step

2.

Writerecursiveversionfunctionsofinorder,preorderandpostordertotraversalthetree.

Step

3.

SelectasuitablerepresentationtoimplementstackADT,whichmustatleasthasfivebasicoperations:Create,IsFull,Push,IsEmptyandPop.Theelementtypeinthestackispointerofnode.

Step

4.

ImplementQueueADTrepresentedbycircularqueue,whichhassevenbasicoperations:CreateQueue,IsEmpty,DisposeQueue,MakeEmpty,EnQueue,Front,DeQueue.Theelementtypeinthequeueispointerofnode.

Step

5.

Writeaniterativeversionofinorder,thenameisiter_inorder()toinordertraversaltree.

Step

6.

Writeafunctionforlevelordertraversalofbinarytree,thenameislevel_order.

Step7.Writeafunctiontocomputetheleafnumberofthebinarytree,thenameisleaf.

Step8.Writeafunctiontocomputetheheightofthebinarytree,thenameisheight.

3.5Project5:JumpingtheQueue:anACMProblem

ThebeginningofawinterbreaknearSpringFestivalisalwaysthebeginningofapeakperiodoftransportation.Ifyouhaveevertriedtogetatrainticketatthattime,youmusthavewitnessedtheendlessqueuesinfrontofeveryticketboxwindow.Ifaguyhasseenhisfriendinaqueue,thenitisverymuchlikelythatthisluckyguymightgostraighttohisfriendandaskforafavor.Thisiscalled"jumpingthequeue".Itisunfairtotherestofthepeopleintheline,but,itislife.Yourtaskistowriteaprogramthatsimulatessuchaqueuewithpeoplejumpingineverynowandthen,assumethat,ifoneinthequeuehasseveralfriendsaskingforfavors,hewouldarrangetheirrequestsinaqueueofhisown.

InputSpecification:

Yourprogrammustreadtestcasesfromafile“input.txt”.Theinputfilewillcontainoneormoretestcases.Eachtestcasebeginswiththenumberofgroupsn(1<=n<=100).Thenngroupdescriptionsfollow,eachoneconsistingofthenumberoffriendsbelongingtothegroupandthosepeople'sdistinctnames.Agroupisafriendgroup.Peopleinonegrouparefriendwitheachother.Anameisastringofupto4characterschosenfrom{A,B,...,Z,a,b,...,z}.Agroupmayconsistofupto1000friends.Youmayassumethatthereisnoonebelongtotwodifferentgroups.

Finally,alistofcommandsfollows.Therearethreedifferentkindsofcommands:

ENQUEUEX-Mr.orMs.Xgoesintothequeue

DEQUEUE-thefirstpersongetstheticketandleavethequeue

STOP-endoftestcase

Theinputwillbeterminatedbyavalueof0forn.

OutputSpecification:

Outputallresultstoafile“output.txt”.Foreachtestcase,firstprintalinesaying"Scenario#k",wherekisthenumberofthetestcase.Then,foreachDEQUEUEcommand,printthepersonwhojustgetsaticketonasingleline.Printablanklinebetweentwotestcases,butnoextralineattheendofoutput.

SampleInput:

2

3AnnBobJoe

3ZoeJimFat

ENQUEUEAnn

ENQUEUEZoe

ENQUEUEBob

ENQUEUEJim

ENQUEUEJoe

ENQUEUEFat

DEQUEUE

DEQUEUE

DEQUEUE

DEQUEUE

DEQUEUE

DEQUEUE

STOP

2

5AnnyJackJeanBillJane

6EvaMikeRonSonyGeoZoro

ENQUEUEAnny

ENQUEUEEva

ENQUEUEJack

ENQUEUEJean

ENQUEUEBill

ENQUEUEJane

DEQUEUE

DEQUEUE

ENQUEUEMike

ENQUEUERon

DEQUEUE

DEQUEUE

DEQUEUE

DEQUEUE

STOP

0

SampleOutput:

Scenario#1

Ann

Bob

Joe

Zoe

Jim

Fat

Scenario#2

Anny

Jack

Jean

Bill

Jane

Eva

3.6Project6:PerformancesMeasurementofSortingAlgorithms

1.Problems

(1).SortthelistbyInsertionSort,ShellSort,QuickSort,MergeSortandHeapSort,respectively.Andoutputeverypassresultofthem.

Input:(alist)

265371611159154819

Output:theeverypassresultofthem.

Notes:youshouldprinttheoriginallist,everypassresultandthelastresults.

(2).MeasureperformancesofInsertionSort,ShellSort,QuickSort,MergeSortandHeapSortforrandomdata.

2.Stepsandrestrictconditions

(1).ImplementfunctionsofInsertionSort,ShellSort,QuickSort,MergeSortandHeapSort.

(2).OutputeverypassresultofinputlistL={265371611159154819}byexecutethesefunctions.

(3).Analyzetheworstcasecomplexitiesofallabovealgorithms;

(4).Measureperformancesoftheabovefunctionsfor=100,500,1000,2000,4000,5000,10000,20000.

Youmayuserandomlibraryfunctiontocreatethetestingdatafirstly.Second,sortitusingabovealgorithmsalternately.Finally,measuretheirperformances.

Togeneratealistrandomdata,wemayuseC’sstandardlibrarystdlib.hasthefollowing:

3.7Project7:TraversalsandApplicationsofGraph

1.Problem

Givenadirectedgraph(seeFigure2),usetheadjacencylistmethodtorepresentit,andoutputthesequenceofvertexnamesgettingfromDepth-FirstSearchandBreadth-FirstSearch.AndGivenasourcev0,Determineashortestpathtoeachv∈V(G)\{v0}andoutputthem.

2.InputandOutputDemand

Input:thenumberofvertex,thenumberofedge,alledges(Vi,Vj)anditsweightinagraph.

Output:

(1).printthegraph.

(2).printthesequenceofvertexnamesgettingfromDepth-FirstSearch.

(3).printthesequenceofvertexnamesgettingfromBreadth-FirstSearch.

Forexample(SeeFigure1):

Input:

611//indicatethegraphincludingsixvertexesandelevenedges.

0150//indicateanedgefromV0toV1.

0210

0445

1215

1410

2020

2315

3120

3435

4330

533

Figure2

Output:

0：124

1：24

2：03

3：14

4：3

5：3

ThesequenceofvertexnamesgettingfromDepth-FirstSearch(from‘V1’):

V1V2V0V4V3V5

ThesequenceofvertexnamesgettingfromBreadth-FirstSearch(from‘V1’):

V1V2V4V0V3V5

Shortestpathsfromv0toeachvertexare

V0toV145

V0toV210

V0toV325

V0toV445

V0toV51000

(“1000”meansnopath.)

3.Stepsandrestrictconditions:

Step1.ImplementDepth-FirstSearchAlgorithm;

Step2.ImplementQueueADTrepresentedbycircularqueue,whichhassevenbasicoperations:CreateQueue,IsEmpty,DisposeQueue,MakeEmpty,EnQueue,Front,DeQueue.Theelementtypeispointerofnode;

Step3.ImplementBreadth-FirstSearchAlgorithm;

Step4.Writeafunctiontodetermineashortestpathfromvitoeachv∈V(G)\{vi}.

Note:

Yourprogrammustreadfromafile“input.txt”andwritetoafile“output.txt”inthecurrentdirectory.

4MinimumRequirementsonWritingaProjectReport

TitleofProject

Class

GroupID

DateofCompletion

mm-dd-yy

1.Introduction

Problemdescriptionand(ifany)backgroundofthealogithms.

2.AlgorithmSpecification

Description(pseudo-codepreferred)ofallthealgorithmsinvolvedforsolvingtheproblem,includingspecificationsofmaindatastructures.

3.TestingResults

Tableoftestcases.Eachtestcaseusual