重庆大学数据结构ppt11_Array

DataStructureDataStructureCollegeofComputerScience,CQUArraysDataStructureDataStructureArrays_01Arrays_01OutlineArrayADTArrayADTMatrixSymmetricMatrix（对称矩阵）TriangularMatrix（三角矩阵）SymmetricBandMatrix（对角矩阵）SparseMatrix（稀疏矩阵）Representation，Transpose（转置）DataStructureDataStructureArrays_01Arrays_01ArraysArray:asetofpairs(indexandvalue)datastructure:Foreachindex,thereisavalueassociatedwiththatindex.representation(possible):implementedbyusingconsecutivememory.DataStructureDataStructureArrays_01Arrays_01TheArrayADTObjects:Asetofpairsindex,valuewhereforeachvalueofindexthereisavaluefromthesetitem.Indexisafiniteorderedsetofoneormoredimensions,forexample,{0,…,n-1}foronedimension,{(0,0),(0,1),(0,2),(1,0),(1,1),(1,2),(2,0),(2,1),(2,2)}fortwodimensions,etc.Methods:forallAArray,iindex,xitem,j,sizeintegerArrayCreate(j,list)//returnanarrayofjdimensionswherelistisaj-tuplewhose//kthelementisthesizeofthekthdimension.//Itemsareundefined.DataStructureDataStructureArrays_01Arrays_01TheArrayADT(cont’d)ItemRetrieve(A,i)//if(iindex)returntheitemassociatedwithindex//valueiinarrayAelsereturnerrorArrayStore(A,i,x)//if(iinindex)returnanarraythatisidenticalto//arrayAexceptthenewpairi,xhasbeeninserted//elsereturnerror5DataStructureDataStructureArrays_01Arrays_01MatricesTwo-dimensionalarraysareaparticularlycommonrepresentationformatrices.Amatrix,alsoreferredtoasageneralmatrix,isanmbynorderedcollectionofnumbers.Itisrepresentedsymbolicallyas:wherethematrixisnamedAandhasmrowsandncolumns.AndaijistheelementinithrowandjthcolumnofmatrixA.DataStructureDataStructureArrays_01Arrays_01Matrices(cont’d)Amatrixappearsastwo-dimensional,butphysicallyitisstoredinalinearfashion.Howtorepresentthistwo-dimensionalarray？123A=456789DataStructureDataStructureArrays_01Arrays_01MatricesRepresentCommonwaystoindexintomulti-dimensionalarraysinclude:Row-majororder:Theelementsofeachrowarestoredinorder.Column-majororder:Theelementsofeachcolumnarestoredinorder.123456789147258369DataStructureDataStructureArrays_01Arrays_01MatricesRepresent(cont’d)XXXXXXXXXXXXCol0Col1Col2Colu2-1Row0Row1Rowu1-1u2elementsu2elementsRow0Row1Rowu1-1Rowii*u2elementRow-majororder:DataStructureDataStructureArrays_01Arrays_01MatricesRepresent(cont’d)So,inordertomaplogicalviewtophysicalstructure,weneedindexingformula.Row-majororder:AssumethatthebaseaddressisatM,theaddressofaijwillbeobtainedasAddress(aij)=M+i*n+jColumn-majororder:ConsideringthebaseaddressatM,theformulawillstandasAddress(aij)=M+j*n+iDataStructureDataStructureArrays_01Arrays_01SymmetricMatrixThematrixAissymmetricifithasthepropertyAequaltoAT,whichmeans:Ithasthesamenumberofrowsasithascolumns;thatis,ithasnrowsandncolumns.Thevalueofeveryelementaijononesideofthemaindiagonalequalsitsmirrorimageajiontheotherside:aij=aji.DataStructureDataStructureArrays_01Arrays_01SymmetricMatrix(cont’d)Thefollowingmatrixillustratesasymmetricmatrixofordern;thatis,ithasnrowsandncolumns.Thesubscriptsoneachsideofthediagonalappearthesametoshowwhichelementsareequal.aij=aji11121110122221201112111010020100AnnnnnnnnaaaaaaaaaaaaaaaaDataStructureDataStructureArrays_01Arrays_01SymmetricMatrix(cont’d)Whenasymmetricmatrixisstoredincompressedstoragemode,thelowertriangular（下三角）partofthesymmetricmatrixisstored,includingthediagonal,inaone-dimensionalarray.Thelowertrianglecanbepackedbyroworcolumns.Thematrixispackedsequentiallyrowbyrow(columnbycolumn)inn(n+1)/2elementsofaone-dimensionalarray.Whenthematrixispackedsequentiallyrowbyrow,tocalculatethelocationkofelementaijofmatrixAinanarray,usethefollowingformula:k=(i+1)*i/2+ji=j,lowertriangularpartk=(j+1)*j/2+iij,uppertriangularpartDataStructureDataStructureArrays_01Arrays_01TriangularMatrixAmatrixoftheformiscalledatriangularmatrix.DataStructureDataStructureArrays_01Arrays_01TriangularMatrix(cont’d)Therearetwotypesoftriangularmatrices:uppertriangularmatrixandlowertriangularmatrix.Triangularmatriceshavethesamenumberofrowsastheyhavecolumns;thatis,theyhavenrowsandncolumns.AmatrixUisanuppertriangularmatrixifitsnonzeroelementsarefoundonlyintheuppertriangleofthematrix,includingthemaindiagonal;thatis:uijequalto0（orconstantC）ifigreaterthanjAmatrixLisanlowertriangularmatrixifitsnonzeroelementsarefoundonlyinthelowertriangleofthematrix,includingthemaindiagonal;thatis:lijequalto0（orconstantC）ifilessthanjDataStructureDataStructureArrays_01Arrays_01TriangularMatrix(cont’d)Thefollowingmatrices,UandL,illustrateupperandlowertriangularmatricesofordern,respectively:DataStructureDataStructureArrays_01Arrays_01TriangularMatrix(cont’d)Whenalower-triangularmatrixisstoredinlower-triangular-packedstoragemode,thelowertriangleofthematrixisstored,includingthediagonal,inaone-dimensionalarray.Thelowertriangleispackedbyroworbycolumns.Theelementsarepackedsequentially,rowbyrow(columnbycolumn),inn(n+1)/2elementsofaone-dimensionalarray.Tocalculatethelocationofeachelementofthetriangularmatrixinthearray,usethetechniquedescribedinSymmetricMatrix.Whenanupper-triangularmatrixisstoredinupper-triangular-pa