72
Chapter2 AlgorithmAnalysis
(1) sum m = = 0;
for( i i = = 0; ; i i < n; ++i i )
++sum;
(2) sum m = = 0;
for( i i = = 0; ; i i < n; ++i i )
for( j = 0; j j < < n; ; ++j j )
++sum;
(3) sum m = = 0;
for( i i = = 0; ; i i < n; ++i i )
for( j = 0; j j < < n * n; ++j j )
++sum;
(4) sum m = = 0;
for( i i = = 0; ; i i < n; ++i i )
for( j = 0; j j < < i; ; ++j j )
++sum;
(5) sum m = = 0;
for( i i = = 0; ; i i < n; ++i i )
for( j = 0; j j < < i * i; ++j j )
for( k k = = 0; k < j; ++k k )
++sum;
(6) sum m = = 0;
for( i i = = 1; ; i i < n; ++i i )
for( j = 1; j j < < i * i; ++j j )
if( j j % i i == = 0 0 )
for( k = 0; k k < < j; ++k )
++sum;
2.8
SupposeyouneedtogeneratearandompermutationofthefirstNintegers.For
example,{4,3,1,5,2}and{3,1,4,2,5}arelegalpermutations,but{5,4,1,2,
1}isnot,becauseonenumber(1)isduplicatedandanother(3)ismissing.This
routineisoftenusedinsimulationofalgorithms.Weassumetheexistenceofa
randomnumbergenerator,
r
,withmethod
randInt(i,j)
,thatgeneratesintegers
between
i
and
j
withequalprobability.Herearethreealgorithms:
1. Fillthearray
a
from
a[0]
to
a[N-1]
asfollows:Tofill
a[i]
,generaterandom
numbersuntilyougetonethatisnotalreadyin
a[0]
,
a[1]
,...,
a[i-1]
.
2. Sameasalgorithm(1),butkeep p anextraarray called the
used
array.When
arandomnumber,
ran
,isfirstputinthearray
a
,set
used[ran] = true
.This
meansthatwhenfilling
a[i]
witharandomnumber,youcantestinonestep
toseewhethertherandomnumberhasbeenused,insteadofthe(possibly)
i
stepsinthefirstalgorithm.
3. Fillthearraysuchthat
a[i] = = i+1
.Then
for( i i = 1; i < < n; ; ++i )
swap( a[ i i ], a[ [ randInt( ( 0, i i ) ) ] );
a. Provethatallthreealgorithmsgenerateonlylegalpermutationsandthatall
permutationsareequallylikely.
How to change pdf to powerpoint on - C# Create PDF from PowerPoint Library to convert pptx, ppt to PDF in C#.net, ASP.NET MVC, WinForms, WPF
Online C# Tutorial for Creating PDF from Microsoft PowerPoint Presentation
add pdf to powerpoint presentation; convert pdf into ppt
How to change pdf to powerpoint on - VB.NET Create PDF from PowerPoint Library to convert pptx, ppt to PDF in vb.net, ASP.NET MVC, WinForms, WPF
VB.NET Tutorial for Export PDF file from Microsoft Office PowerPoint
convert pdf to powerpoint online for; how to change pdf to powerpoint on
Exercises
73
b.Giveasaccurate(Big-Oh)ananalysisasyoucanoftheexpectedrunningtimeof
eachalgorithm.
c. Write(separate)programstoexecuteeachalgorithm10times,togetagood
average.Runprogram(1)for= 250,500,1,000,2,000;program(2)for
= 25,000, , 50,000,100,000, 200,000, 400,000,800,000; and d program
(3) for = 100,000, , 200,000,400,000, 800,000, 1,600,000, 3,200,000,
6,400,000.
d.Compareyouranalysiswiththeactualrunningtimes.
e. Whatistheworst-caserunningtimeofeachalgorithm?
2.9
CompletethetableinFigure2.2withestimatesfortherunningtimesthatwere
toolongtosimulate.Interpolatetherunningtimesforthesealgorithmsandesti-
matethetimerequiredtocomputethemaximumsubsequencesumof1million
numbers.Whatassumptionshaveyoumade?
2.10 Determine,forthetypicalalgorithmsthatyouusetoperformcalculationsbyhand,
therunningtimetodothefollowing:
a. AddtwoN-digitintegers.
b.MultiplytwoN-digitintegers.
c. DividetwoN-digitintegers.
2.11 Analgorithmtakes0.5msforinputsize100.Howlongwillittakeforinputsize
500iftherunningtimeisthefollowing(assumelow-ordertermsarenegligible)?
a. linear
b.O(NlogN)
c. quadratic
d.cubic
2.12 Analgorithmtakes0.5msforinputsize100.Howlargeaproblemcanbesolvedin
1miniftherunningtimeisthefollowing(assumelow-ordertermsarenegligible)?
a. linear
b.O(NlogN)
c. quadratic
d.cubic
2.13 Howmuchtimeisrequiredtocomputef(x)=
N
i=0
a
i
x
i
:
a. Usingasimpleroutinetoperformexponentiation?
b.UsingtheroutineinSection2.4.4?
2.14 Consider the following algorithm(known as Horner’s rule) toevaluate f(x) =
N
i=0
a
i
x
i
:
poly = = 0;
for( i i = = n; i >= 0; --i )
poly = x * * poly y + a[i];
a. Showhowthestepsareperformedbythisalgorithmforx=3,f(x)=4x
4
+
8x
3
+x+2.
b.Explainwhythisalgorithmworks.
c. Whatistherunningtimeofthisalgorithm?
Online Convert PowerPoint to PDF file. Best free online export
Online Powerpoint to PDF Converter. Download Free Trial. Then just wait until the conversion from Powerpoint to PDF is complete and download the file.
convert pdf to ppt online; how to convert pdf to ppt using
RasterEdge XDoc.PowerPoint for .NET - SDK for PowerPoint Document
Able to view and edit PowerPoint rapidly. Convert. Convert PowerPoint to PDF. Convert PowerPoint to HTML5. Convert PowerPoint to Tiff. Convert PowerPoint to Jpeg
how to change pdf to powerpoint slides; how to change pdf to powerpoint
74
Chapter2 AlgorithmAnalysis
2.15 GiveanefficientalgorithmtodetermineifthereexistsanintegerisuchthatA
i
=i
inanarrayofintegersA
1
<A
2
<A
3
< ···< A
N
.Whatistherunningtimeof
youralgorithm?
2.16 Writeanalternative
gcd
algorithmbasedonthefollowingobservations(arrangeso
thata>b):
a. gcd(a,b)=2gcd(a/2,b/2)ifaandbarebotheven.
b.gcd(a,b)=gcd(a/2,b)ifaisevenandbisodd.
c. gcd(a,b)=gcd(a,b/2)ifaisoddandbiseven.
d.gcd(a,b)=gcd((a+b)/2,(ab)/2)ifaandbarebothodd.
2.17 Giveefficientalgorithms(alongwithrunningtimeanalyses)to
a. Findtheminimumsubsequencesum.
b.Findtheminimumpositivesubsequencesum.
c. Findthemaximumsubsequenceproduct.
2.18 Animportantprobleminnumericalanalysisistofindasolutiontotheequation
f(X)=0forsomearbitraryf.Ifthefunctioniscontinuousandhastwopointslow
andhighsuchthatf(low)andf(high)haveoppositesigns,thenarootmustexist
betweenlowandhighandcanbefoundbyabinarysearch.Writeafunctionthat
takesasparametersf,low,andhighandsolvesforazero.Whatmustyoudoto
ensuretermination?
2.19 Themaximumcontiguoussubsequencesumalgorithmsinthetextdonotgiveany
indicationoftheactualsequence.Modifythemsothattheyreturninasingleobject
thevalueofthemaximumsubsequenceandtheindicesoftheactualsequence.
2.20 a. Writeaprogramtodetermineifapositiveinteger,N,isprime.
b.IntermsofN,whatistheworst-caserunningtimeofyourprogram?(Youshould
beabletodothisinO(
N).)
c. LetBequalthenumberofbitsinthebinaryrepresentationofN.Whatisthe
valueofB?
d.IntermsofB,whatistheworst-caserunningtimeofyourprogram?
e. Compare e the running g times s to determine if a 20-bit number and d a a 40-bit
numberareprime.
f. IsitmorereasonabletogivetherunningtimeintermsofNorB?Why?
2.21 TheSieveofEratosthenesisamethodusedtocomputeallprimeslessthanN.We
beginbymakingatableofintegers2toN.Wefindthesmallestinteger,i,thatis
notcrossedout,printi,andcrossouti,2i,3i,....Wheni>
N,thealgorithm
terminates.Whatistherunningtimeofthisalgorithm?
2.22 ShowthatX
62
canbecomputedwithonlyeightmultiplications.
2.23 Writethefastexponentiationroutinewithoutrecursion.
2.24 Giveaprecisecountonthenumberofmultiplicationsusedbythefastexponenti-
ationroutine.(Hint:ConsiderthebinaryrepresentationofN.)
2.25 ProgramsAandBareanalyzedandfoundtohaveworst-caserunningtimesno
greaterthan150Nlog
2
NandN
2
,respectively.Answerthefollowingquestions,if
possible:
C# WinForms Viewer: Load, View, Convert, Annotate and Edit
to PDF; Convert PowerPoint to PDF; Convert Image to PDF; Convert Jpeg to PDF; Merge PDF Files; Split PDF Document; Remove Password from PDF; Change PDF Permission
convert pdf to powerpoint slide; embed pdf into powerpoint
How to C#: Overview of Using XDoc.PowerPoint
How to C#: Overview of Using XDoc.PowerPoint. Overview for How to Use XDoc.PowerPoint in C# .NET Programming Project. PowerPoint Conversion.
convert pdf slides to powerpoint online; pdf to powerpoint conversion
Exercises
75
a. Whichprogramhasthebetterguaranteeontherunningtimeforlargevaluesof
N(N>10,000)?
b.Whichprogramhasthebetterguaranteeontherunningtimeforsmallvaluesof
N(N<100)?
c. WhichprogramwillrunfasteronaverageforN=1,000?
d.Is itpossiblethat programwillrunfasterthanprogramAonallpossible
inputs?
2.26 Amajorityelementinanarray,A,ofsizeNisanelementthatappearsmorethan
N/2times(thus,thereisatmostone).Forexample,thearray
3,3,4,2,4,4,2,4,4
hasamajorityelement(4),whereasthearray
3,3,4,2,4,4,2,4
doesnot.Ifthereisnomajorityelement,yourprogramshouldindicatethis.Here
isasketchofanalgorithmtosolvetheproblem:
First,acandidatemajorityelementisfound(thisistheharderpart).Thiscandidateis
theonlyelementthatcouldpossiblybethemajorityelement.Thesecondstepdetermines
ifthiscandidateisactuallythemajority.Thisisjustasequentialsearchthroughthearray.
Tofindacandidateinthearray,A,formasecondarray,B.ThencompareA
1
andA
2
.
Iftheyareequal,addoneofthesetoB;otherwisedonothing.ThencompareA
3
andA
4
.
Againiftheyareequal,addoneofthesetoB;otherwisedonothing.Continueinthis
fashionuntiltheentirearrayisread.ThenrecursivelyfindacandidateforB;thisisthe
candidateforA(why?).
a. Howdoestherecursionterminate?
b.HowisthecasewhereNisoddhandled?
c. Whatistherunningtimeofthealgorithm?
d.Howcanweavoidusinganextraarray,B?
e. Writeaprogramtocomputethemajorityelement.
2.27 TheinputisanNbyNmatrixofnumbersthatisalreadyinmemory.Eachindivid-
ualrowisincreasingfromlefttoright.Eachindividualcolumnisincreasingfrom
toptobottom.GiveanO(N)worst-casealgorithmthatdecidesifanumberXisin
thematrix.
2.28 Designefficientalgorithmsthattakeanarrayofpositivenumbers
a
,anddetermine:
a. themaximumvalueof
a[j]+a[i]
,with
j
i
.
b.themaximumvalueof
a[j]-a[i]
,with
j
i
.
c. themaximumvalueof
a[j]
*
a[i]
,with
j
i
.
d.themaximumvalueof
a[j]/a[i]
,with
j
i
.
2.29
Whyisitimportanttoassumethatintegersinourcomputermodelhaveafixed
size?
2.30 Considerthewordpuzzleproblemonpage2.Supposewefixthesizeofthelongest
wordtobe10characters.
C# HTML5 Viewer: Load, View, Convert, Annotate and Edit PowerPoint
Such as load and view PowerPoint without Microsoft Office software installed, convert PowerPoint to PDF file, Tiff image and HTML file, as well as add
how to add pdf to powerpoint; convert pdf file to ppt online
VB.NET PowerPoint: Read, Edit and Process PPTX File
create image on desired PowerPoint slide, merge/split PowerPoint file, change the order of How to convert PowerPoint to PDF, render PowerPoint to SVG
pdf to ppt converter; how to change pdf file to powerpoint
76
Chapter2 AlgorithmAnalysis
a. IntermsofRandC,whicharethenumberofrowsandcolumnsinthepuzzle,
and W,which is the number of words, , what arethe running g times ofthe
algorithmsdescribedinChapter1?
b.Supposethewordlistispresorted.Showhowtousebinarysearchtoobtainan
algorithmwithsignificantlybetterrunningtime.
2.31 Supposethatline 15in thebinary search routinehad thestatement
low = mid
insteadof
low = = mid d + 1
.Wouldtheroutinestillwork?
2.32 Implementthebinarysearchsothatonlyonetwo-waycomparisonisperformedin
eachiteration.
2.33 Supposethatlines15and16inalgorithm3(Fig.2.7)arereplacedby
15
int maxLeftSum m = = maxSumRec( a, left, center - - 1 1 );
16
int maxRightSum m = maxSumRec( a, center, right );
Wouldtheroutinestillwork?
2.34 The inner r loop p of f the cubic maximum subsequence sum algorithm performs
N(N+1)(N+2)/6iterationsoftheinnermostcode.Thequadraticversionperforms
N(N+1)/2iterations.ThelinearversionperformsNiterations.Whatpatternis
evident?Canyougiveacombinatoricexplanationofthisphenomenon?
References
AnalysisoftherunningtimeofalgorithmswasfirstmadepopularbyKnuthinthethree-
partseries[5],[6],and[7].Analysisofthegcdalgorithmappearsin[6].Anotherearlytext
onthesubjectis[1].
Big-Oh,big-omega,big-theta,andlittle-ohnotationwereadvocatedbyKnuthin[8].
Thereisstillnouniformagreementonthematter,especiallywhenitcomestousing().
ManypeopleprefertouseO(),eventhoughitislessexpressive.Additionally,O()isstill
usedinsomecornerstoexpressalowerbound,when()iscalledfor.
Themaximumsubsequencesumproblemisfrom[3].Theseriesofbooks[2],[3],and
[4]showhowtooptimizeprogramsforspeed.
1.A.V.Aho,J.E.Hopcroft,andJ.D.Ullman,TheDesignandAnalysisofComputerAlgorithms,
Addison-Wesley,Reading,Mass.,1974.
2.J.L.Bentley,WritingEfficientPrograms,PrenticeHall,EnglewoodCliffs,N.J.,1982.
3.J.L.Bentley,ProgrammingPearls,Addison-Wesley,Reading,Mass.,1986.
4.J.L.Bentley,MoreProgrammingPearls,Addison-Wesley,Reading,Mass.,1988.
5.D. E. Knuth,TheArtofComputer Programming,Vol1:FundamentalAlgorithms,3ded.,
Addison-Wesley,Reading,Mass.,1997.
6.D.E.Knuth, TheArtofComputer Programming,Vol2:SeminumericalAlgorithms,3ded.,
Addison-Wesley,Reading,Mass.,1998.
7.D.E.Knuth,TheArtofComputerProgramming,Vol3:SortingandSearching,2ded.,Addison-
Wesley,Reading,Mass.,1998.
8.D.E.Knuth,“BigOmicronandBigOmegaandBigTheta,”ACMSIGACTNews,8(1976),
18–23.
VB.NET PDF Password Library: add, remove, edit PDF file password
Add password to PDF. Change PDF original password. Remove password from PDF. Set PDF security level. VB: Change and Update PDF Document Password.
pdf to ppt converter online for large; table from pdf to powerpoint
C# powerpoint - Convert PowerPoint to PDF in C#.NET
C# PowerPoint - Convert PowerPoint to PDF in C#.NET. Online C# Tutorial for Converting PowerPoint to PDF (.pdf) Document. PowerPoint to PDF Conversion Overview.
convert pdf to ppt; convert pdf pages to powerpoint slides
C H A P P T E R
3
Lists,Stacks,andQueues
Thischapterdiscussesthreeofthemostsimpleandbasicdatastructures.Virtuallyevery
significantprogramwilluseatleastoneofthesestructuresexplicitly,andastackisalways
implicitlyusedinaprogram,whetherornotyoudeclareone.Amongthehighlightsofthis
chapter,wewill...
IntroducetheconceptofAbstractDataTypes(ADTs).
Showhowtoefficientlyperformoperationsonlists.
IntroducethestackADTanditsuseinimplementingrecursion.
IntroducethequeueADTanditsuseinoperatingsystemsandalgorithmdesign.
Inthischapter,weprovidecodethatimplementsasignificantsubsetoftwolibrary
classes:
vector
and
list
.
3.1 AbstractDataTypes(ADTs)
Anabstractdatatype(ADT)isasetofobjectstogetherwithasetofoperations.Abstract
datatypesaremathematicalabstractions;nowhereinanADT’sdefinitionisthereanymen-
tionofhowthesetofoperationsisimplemented.Objectssuchaslists,sets,andgraphs,
alongwiththeiroperations,canbeviewedasADTs,justasintegers,reals,andbooleansare
datatypes.Integers,reals,andbooleanshaveoperationsassociatedwiththem,andsodo
ADTs.ForthesetADT,wemighthavesuchoperationsasadd,remove,size,andcontains.
Alternatively,wemightonlywantthetwooperationsunionandfind,whichwoulddefinea
differentADTontheset.
TheC
++
classallowsfortheimplementation ofADTs,with appropriatehiding of
implementationdetails.Thus,any otherpartoftheprogramthatneeds toperforman
operationontheADTcandosobycallingtheappropriatemethod.Ifforsomereason
implementationdetailsneedtobechanged,itshouldbeeasytodosobymerelychanging
theroutinesthatperformtheADToperations.Thischange,inaperfectworld,wouldbe
completelytransparenttotherestoftheprogram.
ThereisnoruletellinguswhichoperationsmustbesupportedforeachADT;thisis
adesigndecision.Errorhandlingandtiebreaking(whereappropriate)arealsogenerally
uptotheprogramdesigner.Thethreedatastructuresthatwewillstudyinthischapterare
primaryexamplesofADTs.Wewillseehoweachcanbeimplementedinseveralways,but
77
78
Chapter3 Lists,Stacks,andQueues
iftheyaredonecorrectly,theprogramsthatusethemwillnotnecessarilyneedtoknow
whichimplementationwasused.
3.2 TheListADT
WewilldealwithagenerallistoftheformA
0
,A
1
,A
2
,...,A
N−1
.Wesaythatthesizeof
thislistisN.Wewillcallthespeciallistofsize0anemptylist.
Foranylistexcepttheemptylist,wesaythatA
i
follows(orsucceeds)A
i−1
(<N)
andthatA
i−1
precedesA
i
(i>0).ThefirstelementofthelistisA
0
,andthelastelement
isA
N−1
.WewillnotdefinethepredecessorofA
0
orthesuccessorofA
N−1
.Theposition
ofelementA
i
inalistisi.Throughoutthisdiscussion,wewillassume,tosimplifymatters,
thattheelementsinthelistareintegers,butingeneral,arbitrarilycomplexelementsare
allowed(andeasilyhandledbyaclasstemplate).
Associatedwiththese“definitions”isasetofoperationsthatwewouldliketoperform
on theList ADT.Somepopularoperationsare
printList
and
makeEmpty
,whichdothe
obviousthings;
find
,whichreturnsthepositionofthefirstoccurrenceofanitem;
insert
and
remove
,whichgenerallyinsertandremovesomeelementfromsomepositioninthe
list;and
findKth
,whichreturnstheelementinsomeposition(specifiedasanargument).
Ifthelistis34,12,52,16,12,then
find(52)
mightreturn2;
insert(x,2)
mightmakethe
listinto34,12,
x
,52,16,12(ifweinsertintothepositiongiven);and
remove(52)
might
turnthatlistinto34,12,
x
,16,12.
Ofcourse,theinterpretationofwhatisappropriateforafunctionisentirelyupto
the programmer,as is the handling of special cases (for example,what does
find(1)
returnabove?).Wecouldalsoaddoperationssuchas
next
and
previous
,whichwould
takeaposition asargument andreturn thepositionofthesuccessorand predecessor,
respectively.
3.2.1 SimpleArrayImplementationofLists
Alltheseinstructionscanbeimplementedjustbyusinganarray.Althougharraysarecre-
atedwithafixedcapacity,the
vector
class,whichinternallystoresanarray,allowsthearray
togrowbydoublingitscapacitywhenneeded.Thissolvesthemostseriousproblemwith
usinganarray—namely,thathistorically,touseanarray,anestimateofthemaximumsize
ofthelistwasrequired.Thisestimateisnolongerneeded.
Anarrayimplementationallows
printList
tobecarriedoutinlineartime,andthe
findKth
operationtakesconstanttime,which isasgood as canbeexpected.However,
insertionanddeletionarepotentiallyexpensive,dependingonwheretheinsertionsand
deletionsoccur.Intheworstcase,insertingintoposition0(inotherwords,atthefront
ofthelist)requirespushingtheentirearraydownonespottomakeroom,anddeleting
thefirstelementrequiresshiftingalltheelementsinthelistuponespot,sotheworst
casefortheseoperationsisO(N).Onaverage,halfofthelistneedstobemovedforeither
operation,solineartimeisstillrequired.Ontheotherhand,ifalltheoperationsoccurat
thehighendofthelist,thennoelementsneedtobeshifted,andthenaddinganddeleting
takeO(1)time.
3.2 TheListADT
79
Therearemany situationswherethelist isbuiltup byinsertionsatthehigh end,
andthenonlyarrayaccesses(i.e.,
findKth
operations)occur.Insuchacase,thearrayis
asuitableimplementation.However,ifinsertionsanddeletionsoccurthroughoutthelist
and,inparticular,atthefrontofthelist,thenthearrayisnotagoodoption.Thenext
sectiondealswiththealternative:thelinkedlist.
3.2.2 SimpleLinkedLists
Inordertoavoidthelinearcostofinsertionanddeletion,weneedtoensurethatthelist
isnotstoredcontiguously,sinceotherwiseentirepartsofthelistwillneedtobemoved.
Figure3.1showsthegeneralideaofalinkedlist.
Thelinkedlistconsistsofaseries of nodes,which arenotnecessarily adjacent in
memory.Eachnodecontainstheelementandalinktoanodecontainingitssuccessor.We
callthisthe
next
link.Thelastcell’s
next
linkpointsto
nullptr
.
Toexecute
printList()
or
find(x)
,wemerelystartatthefirstnodein thelistand
thentraversethelistbyfollowingthe
next
links.Thisoperationisclearlylinear-time,as
inthearrayimplementation;although,theconstantislikelytobelargerthanifanarray
implementation wereused.The
findKth
operation isnolongerquiteasefficientasan
arrayimplementation;
findKth(i)
takesO(i)timeandworksbytraversingdownthelistin
theobviousmanner.Inpractice,thisboundispessimistic,becausefrequentlythecallsto
findKth
areinsortedorder(byi).Asanexample,
findKth(2)
,
findKth(3)
,
findKth(4)
,and
findKth(6)
canallbeexecutedinonescandownthelist.
The
remove
methodcanbeexecutedinone
next
pointerchange.Figure3.2showsthe
resultofdeletingthethirdelementintheoriginallist.
The
insert
methodrequiresobtaininganewnodefromthesystembyusinga
new
call
andthenexecutingtwo
next
pointermaneuvers.ThegeneralideaisshowninFigure3.3.
Thedashedlinerepresentstheoldpointer.
Aswecansee,inprinciple,ifweknowwhereachangeistobemade,insertingor
removinganitemfromalinkedlistdoesnotrequiremovinglotsofitems,andinstead
involvesonlyaconstantnumberofchangestonodelinks.
Thespecialcaseofaddingtothefrontorremovingthefirstitemisthusaconstant-
timeoperation,presumingofcoursethatalinktothefrontofthelinkedlistismaintained.
A
0
A
1
A
2
A
3
A
4
Figure3.1 Alinkedlist
A
0
A
1
A
2
A
3
A
4
Figure3.2 Deletionfromalinkedlist
80
Chapter3 Lists,Stacks,andQueues
A
0
A
1
A
2
A
3
A
4
X
Figure3.3 Insertionintoalinkedlist
first
last
a
b
c
d
Figure3.4 Adoublylinkedlist
Thespecialcaseofaddingattheend (i.e.,makingthenewitemthelastitem)canbe
constant-time,aslong as we maintain alink tothe last node. . Thus, atypicallinked
listkeepslinkstobothendsofthelist.Removingthelastitemistrickier,becausewe
havetofindthenext-to-lastitem,changeitsnextlinkto
nullptr
,andthenupdatethe
linkthat maintainsthe lastnode.In theclassic linked list,whereeach nodestoresa
linktoitsnextnode,havingalinktothelastnodeprovidesnoinformationaboutthe
next-to-lastnode.
Theobviousideaofmaintainingathirdlinktothenext-to-lastnodedoesn’twork,
becauseittoowouldneedtobeupdatedduringaremove.Instead,wehaveeverynode
maintainalinktoitspreviousnodeinthelist.ThisisshowninFigure3.4andisknown
asadoublylinkedlist.
3.3
vector
and
list
intheSTL
TheC
++
languageincludes,initslibrary,animplementationofcommondatastructures.
ThispartofthelanguageispopularlyknownastheStandardTemplateLibrary(STL).
TheListADTisoneofthedatastructuresimplementedintheSTL.Wewillseesome
othersin Chapters4and5.In general,thesedatastructuresarecalledcollectionsor
containers.
TherearetwopopularimplementationsoftheListADT.The
vector
providesagrow-
ablearrayimplementationoftheListADT.Theadvantageofusingthe
vector
isthatitis
indexableinconstanttime.Thedisadvantageisthatinsertionofnewitemsandremovalof
existingitemsisexpensive,unlessthechangesaremadeattheendofthe
vector
.The
list
providesadoublylinkedlistimplementationoftheListADT.Theadvantageofusingthe
3.3 vectorandlistintheSTL
81
list
isthatinsertionofnewitemsandremovalofexistingitemsischeap,providedthatthe
positionofthechangesisknown.Thedisadvantageisthatthe
list
isnoteasilyindexable.
Both
vector
and
list
areinefficientforsearches.Throughoutthisdiscussion,
list
refersto
thedoublylinkedlistintheSTL,whereaslist(typesetwithoutthemonospacefont)refers
tothemoregeneralListADT.
Both
vector
and
list
areclasstemplatesthatareinstantiatedwiththetypeofitems
thattheystore.Bothhaveseveralmethodsincommon.Thefirstthreemethodsshownare
actuallyavailableforalltheSTLcontainers:
int size( ( ) ) const
:returnsthenumberofelementsinthecontainer.
void clear( ( )
:removesallelementsfromthecontainer.
bool empty( ( ) ) const
: returns true ifthe container contains noelements, and d false
otherwise.
Both
vector
and
list
supportaddingandremovingfromtheendofthelistinconstant
time.Both
vector
and
list
supportaccessingthefrontiteminthelistinconstanttime.
Theoperationsare:
void push_back( const Object & & x x )
:adds
x
totheendofthelist.
void pop_back( ( )
:removestheobjectattheendofthelist.
const Object & & back( ( ) ) const
:returnstheobjectattheendofthelist(amutatorthat
returnsareferenceisalsoprovided).
const Object & & front( ( ) const
:returnstheobjectatthefrontofthelist(amutatorthat
returnsareferenceisalsoprovided).
Becauseadoublylinkedlistallowsefficientchangesatthefront,buta
vector
doesnot,
thefollowingtwomethodsareavailableonlyfor
list
:
void push_front( ( const Object t & x x )
:adds
x
tothefrontofthe
list
.
void pop_front( )
:removestheobjectatthefrontofthe
list
.
The
vector
hasitsownsetofmethodsthatarenotpartof
list
.Twomethodsallow
efficientindexing.Theothertwomethodsallowtheprogrammertoviewandchangethe
internalcapacity.Thesemethodsare:
Object & & operator[] ( ( int t idx x )
:returnstheobjectatindex
idx
inthe
vector
,withno
bounds-checking(anaccessorthatreturnsaconstantreferenceisalsoprovided).
Object & & at( ( int idx )
:returnstheobjectatindex
idx
inthe
vector
,withbounds-
checking(anaccessorthatreturnsaconstantreferenceisalsoprovided).
int capacity( ( ) const
:returnstheinternalcapacityofthe
vector
.(SeeSection3.4for
moredetails.)
void reserve( int newCapacity )
:setsthenewcapacity.Ifagoodestimateisavailable,
itcanbeusedtoavoidexpansionofthe
vector
.(SeeSection3.4formoredetails.)
Documents you may be interested
Documents you may be interested