arrays - home university of calgary阵列-家居卡尔加里大学

《arrays - home university of calgary阵列-家居卡尔加里大学》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、ARRAYSArraysareusuallyafeaturefoundinmanyprogramminglanguages.Thesearecombinationsofsimpletypesfoundinthelanguageandarecalledstructuredtypes.Theyarereallyaspecialtypeofdatastructurewhichhassomeabstractionsbuiltintothelanguagethatallowtheusertousethestructureeasily.ArraysarealsoanAbstractDataTypeandc

2、anbedefinedbytheprocesseswhichmakeupthestructure.Theseare:1.Create:Allocatethespacerequiredforstoringthearray.2.Insert:Insertvaluesintospecifiedelementsofthearray.3.Retrieve:Obtainvaluesforspecifiedelementsofthearray.Whenarraysarestored,theyaregenerallycontiguousinmemory,thatis,oneelementfollowsdire

3、ctlyaftertheotherinonelargeblockofmemory.Thesystemgenerallystoresthenameofthearray,thepointinmemorywherethearraybegins,thenumberofelementsinthearray,andthesizeofeachelement.Thesizeoftheelementisdeterminedbyanalyzingthetypeoftheelementwhichcanbequitesimpleorvaryincomplexity.Fromauser’spointofview,all

4、thatisrequiredistospecifythenameofthearrayandtheelementnumber.Elementsareusuallynumberedbeginningat0andaresaidtobezero-indexed.Thestructure’sdesignissuchthattheuserdoesnotneedtoknowhowtogettothelocationrequested,thisisdonebythesystem.MappingFunctionsOne-dimensionalarraysThemappingfunctionisusedbythe

5、systemtofindthebeginningofthespecifiedarrayelement.Supposethatwehaveanarrayof4elementscalled‘one’.WecanpicturethisasThesystemwillknowitsname,thebeginningpointinmemoryandthenumberofelements.However,findinganyelementwilldependonhowfaritmovesdownthischunkofmemory,sothesizeofeachelementmustbeknownandisd

6、eterminedbythetypedeclarationwhenthearrayisdeclared.Ifthearrayabovestorescharacters,then1byteisrequiredforeachelement.Ifweweretostorelongs,8byteswouldberequiredforeachelement.Inordertomakesurethesystemislookingatthebeginningofthebyterequested,itusesamappingfunction.Ingeneral,themappingfunctionwouldb

7、eposition=start+(sizeofelement*numberofelement)Thus,ifthearraycontainslongs,thenfindingthestartofelement#2wouldbePosition=start+(8*2)or16bytesbeyondthestartposition.Notethatthisisthebeginningofelement