(第1版)數(shù)據(jù)結(jié)構(gòu)實驗指導

3Projects

3.1Project1:PerformanceMeasurement

GivenalistoforderedNintegers,numberedfrom0toN–1,checkingtoseethatNis

notinthislistprovidesaworstcaseformanysearchalgorithms.

Considertwoalgorithms:oneiscalled“sequentialsearch”whichscansthroughthelist

fromlefttoright;andtheotheris“binarysearch”whichisgivenonpage24(Figure2.9)of

yourtextbook.Yourtasksare:

(1)Implementaniterativeversionandarecursiveversionofsequentialsearch;

(2)Implementaniterativeversionofbinarysearch;

(3)Analyzetheworstcasecomplexitiesoftheabovetwoversionsofsequentialsearch

andthatofbinarysearch;

(4)Measureandcomparetheworstcaseperformancesoftheabovethreefunctionsfor

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

Tomeasuretheperformanceofafunction,wemayuseC?sstandardlibrarytime.hasthe

following:

Note:Ifafunctionrunssoquicklythatittakeslessthanaticktofinish,wemayrepeatthe

functioncallsforKtimestoobtainatotalruntime(“TotalTime”),andthendividethetotaltime

byKtoobtainamoreaccurateduration(“Duration”)forasinglefunofthefunction.The

repetitionfactormustbylargeenoughsothatthenumberofelapsedticksisatleast10ifwe

wantanaccuracyofatleast10%.

Thetestresultsmustbelistedinthefollowingtable:

1

TheperformancesofthethreefunctionsmustbeplottedinthesameN-run_timecoordinate

systemforillustration.

2

3.2Project2:ImplementationofLists,andPolynomial

Problems

1.Mergetwoorderedlistsintoanewlinkedlistinwhichthenodesarealsoin

thisorder.Iflengthsoforiginaltwolistsaremandn,thelengthofnewlinked

listism+n.

Forexample:

Input:

5(lengthoflist1)

426465695

11(lengthoflist2)

1517263046485658829095

Output:

41517263046485658

829095

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)inthe

VC++workspace.Theirnamesshouldbelinkedlist.h,linkedlist.cpp,merge.cpp.

2.ThedeclarationsthatfollowgiveusthepolynomialADT.

StructurePolynomialis

e,awherea

Object:P(x)axe1axen;asetoforderedpairsof

is

1

n

i

i

i

thecoefficientande

istheexponent.arenonnegativeintegers.

e

i

i

Operations:

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

PolynomialZero()

::=returnthepolynomial,P(x)=0

::=if(poly)returnFALSE;

elsereturnTRUE;

BooleanIsZero(poly)

CoefficientCoef(poly,expon)

::=if(expon∈poly)returnitscoeffient

3

elsereturnzero.

ExponentLead_Exp(poly)

::=returnthelargestexponentinpoly.

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

elsereturnthepolynomialpolywiththeterm

<coef,expon>inserted.

PolynomialRemove(poly,expon)

:=if(expon∈poly)returnthepolynomialpolywith

thetermwhoseexponentisexpondeleted

elsereturnerror.

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

PolynomialAdd(poly1,poly2)

PolynomialMult(poly1,poly2)

endPolynomial

:=returnthepolynomialpoly1+poly2.

:=returnthepolynomialpoly1*poly2.

Demands:

(1).YoushouldchooseasuitablerepresentationforPolynomial.

(2).YoushouldcreatethefunctionsZero,IsZero,Coef,Lead_Exp,Attach,Remove,

SingleMult,Add,Mult,andtestthem.

(3).IfA(x)3x202x54andB(x)3x2x3x1,writeafunctiontouse

432

abovefunctionstocomputeC(x)A(x)B(x)andD(x)A(x)*B(x).

(4).Analyzeadvantagesofyourrepresentation.

(5).TheimplementationofpolynomialADTshouldbewritteninseparatedfiles(.cppand.h)

intheVC++workspace.TheirnamesshouldbePolynomial.h,Polynomial.cpp,

main.cpp.

Note:

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

currentdirectory.

4

3.3Project3:ImplementationandApplicationsofStacks

Problems

1.WriteaConversionfunctiontoconverseanydecimaldatatobinaryversion.

Demands:

(1).ImplementStackADTusinglinkedlistrepresentation,whichmustatleasthasfivebasic

operations:Create,IsFull,Push,IsEmptyandPop.

(2).BuildanewprojecttoimplementtheConversionfunction.Theinputandoutputshouldbe

accordingtothefollowingformat:

Pleaseinputthedecimalnumber:15

Thecorrespondingbinaryversionis:1111

Pleaseinputthedecimalnumber:-1

Bye!

2.Writeaprogramtojudgewhetherabracketsequence(maybehasother

letters)is“matching”.The“matching”meansthatiftherehasa?(?ina

expressionandtheremusthasa?)?init.Iftheinputsequenceis“matching”,

thenoutput?ok?,otherwiseoutputE?RROR?.

Demands

(1).ImplementStackusingarrayrepresentation,whichmustatleasthasfivebasicoperations:

Create,IsFull,Push,IsEmptyandPop.

(2).BuildanewprojecttoimplementthebracketMatchingfunction.Theinputandoutput

shouldbeaccordingtothefollowingformat:

Pleaseinputtheexpression:a*(b+c)

ThebracketoftheexpressionismatchingOK!

Pleaseinputtheexpression:a*(b+c))

ThebracketoftheexpressionismatchingERROR!

Pleaseinputtheexpression:(a*(b+c)

ThebracketoftheexpressionismatchingERROR!

5

Note

ThetwoimplementationofStackshouldbewritteninseparatedfiles(.cppand.h)inthe

VC++workspace.Theirfilesshouldbenameddifferently,suchaslinkedStack.h,

linkedStack.cpp,SqStack.h,SqStack.cpp.

6

3.4Project4:BinaryTreeTraversals

1.Problem

Createbinarytreeasfollow(Figure-1)incomputer,writeoutthefunctionsofinorder,

preorder,postorderandlevelorder,andusethemtotraversalthebinarytree.Andcomputethe

leafnumberandheightofthebinarytree.

Hint:Youmaychoosesuitablerepresentation,suchaslinkedrepresentationisoftenused.

Figure-1abinarytree

2.Stepsandrestrictconditions

Step1.Writethefunctionofcreatetocreateatreebyinputdata.

Step2.Writerecursiveversionfunctionsofinorder,preorderandpostordertotraversalthe

tree.

Step3.SelectasuitablerepresentationtoimplementstackADT,whichmustatleasthasfive

basicoperations:Create,IsFull,Push,IsEmptyandPop.Theelementtypeinthe

stackispointerofnode.

Step4.ImplementQueueADTrepresentedbycircularqueue,whichhassevenbasic

operations:CreateQueue,IsEmpty,DisposeQueue,MakeEmpty,EnQueue,Front,

DeQueue.Theelementtypeinthequeueispointerofnode.

Step5.Writeaniterativeversionofinorder,thenameisiter_inorder()toinordertraversaltree.

Step6.Writeafunctionforlevelordertraversalofbinarytree,thenameislevel_order.

Step7.Writeafunctiontocomputetheleafnumberofthebinarytree,thenameisleaf.

Step8.Writeafunctiontocomputetheheightofthebinarytree,thenameisheight.

7

3.5Project5:JumpingtheQueue:anACMProblem

ThebeginningofawinterbreaknearSpringFestivalisalwaysthebeginning

ofapeakperiodoftransportation.Ifyouhaveevertriedtogetatrainticketatthat

time,youmusthavewitnessedtheendlessqueuesinfrontofeveryticketbox

window.Ifaguyhasseenhisfriendinaqueue,thenitisverymuchlikelythatthis

luckyguymightgostraighttohisfriendandaskforafavor.Thisiscalled"jumping

thequeue".Itisunfairtotherestofthepeopleintheline,but,itislife.Yourtaskis

towriteaprogramthatsimulatessuchaqueuewithpeoplejumpingineverynow

andthen,assumethat,ifoneinthequeuehasseveralfriendsaskingforfavors,he

wouldarrangetheirrequestsinaqueueofhisown.

InputSpecification:

Yourprogrammustreadtestcasesfromafile“input.txt”.Theinputfilewill

containoneormoretestcases.Eachtestcasebeginswiththenumberofgroupsn

(1<=n<=100).Thenngroupdescriptionsfollow,eachoneconsistingofthe

numberoffriendsbelongingtothegroupandthosepeople'sdistinctnames.Agroup

isafriendgroup.Peopleinonegrouparefriendwitheachother.Anameisastring

ofupto4characterschosenfrom{A,B,...,Z,a,b,...,z}.Agroupmayconsistof

upto1000friends.Youmayassumethatthereisnoonebelongtotwodifferent

groups.

Finally,alistofcommandsfollows.Therearethreedifferentkindsof

commands:

ENQUEUEX-Mr.orMs.Xgoesintothequeue

DEQUEUE-thefirstpersongetstheticketandleavethequeue

STOP-endoftestcase

Theinputwillbeterminatedbyavalueof0forn.

OutputSpecification:

Outputallresultstoafile“output.txt”.Foreachtestcase,firstprintaline

saying"Scenario#k",wherekisthenumberofthetestcase.Then,foreach

DEQUEUEcommand,printthepersonwhojustgetsaticketonasingleline.Print

ablanklinebetweentwotestcases,butnoextralineattheendofoutput.

SampleInput:

2

3AnnBobJoe

3ZoeJimFat

ENQUEUEAnn

ENQUEUEZoe

ENQUEUEBob

ENQUEUEJim

ENQUEUEJoe

8

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

9

3.6Project6:PerformancesMeasurementofSortingAlgorithms

1.Problems

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

respectively.Andoutputeverypassresultofthem.

Input:(alist)

265371611159154819

Output:theeverypassresultofthem.

Notes:youshouldprinttheoriginallist,everypassresultandthelastresults.

(2).MeasureperformancesofInsertionSort,ShellSort,QuickSort,MergeSort

andHeapSortforrandomdata.

2.Stepsandrestrictconditions

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

(2).OutputeverypassresultofinputlistL={265371611159154819}by

executethesefunctions.

(3).Analyzetheworstcasecomplexitiesofallabovealgorithms;

(4).MeasureperformancesoftheabovefunctionsforN=100,500,1000,2000,4000,5000,

10000,20000.

Youmayuserandomlibraryfunctiontocreatethetestingdatafirstly.Second,sortitusing

abovealgorithmsalternately.Finally,measuretheirperformances.

Togeneratealistrandomdata,wemayuseC?sstandardlibrarystdlib.hasthefollowing:

3.7Project7:TraversalsandApplicationsofGraph

1.Problem

Givenadirectedgraph(seeFigure2),usetheadjacencylistmethodtorepresentit,and

outputthesequenceofvertexnamesgettingfromDepth-FirstSearchandBreadth-First

Search.AndGivenasourcev0,Determineashortestpathtoeachv∈V(G)\{v0}andoutput

them.

2.InputandOutputDemand

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

Output:

(1).printthegraph.

(2).printthesequenceofvertexnamesgettingfromDepth-FirstSearch.

(3).printthesequenceofvertexnamesgettingfromBreadth-FirstSearch.

Forexample(SeeFigure1):

Input:

611

//indicatethegraphincludingsixvertexesandelevenedges.

//indicateanedgefromV0toV1.

0150

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?):

11

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.The

elementtypeispointerofnode;

Step3.ImplementBreadth-FirstSearchAlgorithm;

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

Note:

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

currentdirectory.

12

4MinimumRequirementsonWritingaProjectReport

TitleofProject

Class

GroupID

DateofCompletionmm-dd-yy

1.Introduction

Problemdescriptionand(ifany)backgroundofthealogithms.

2.AlgorithmSpecification

Description(pseudo-codepreferred)ofallthealgorithmsinvolvedforsolvingtheproblem,

includingspecificationsofmaindatastructures.

3.TestingResults

Tableoftestcases.Eachtestcaseusuallyconsistsofabriefdescriptionoft