Data Structure(C++) Slides-ENG 数据结构课件Chapter-4-String-and-Array-English

2026DataStructuresChapter4StringandArrayIntroductionStringPatternMatchingMatrixContentsIntroduction4.1Chapter4StringandArray4.1IntroductiontoStringClanguagecharacterset→ClanguagesourceprogramEnglishletters→Englishwords→Englisharticles;Chinesecharacters+punctuation→articlesDNAbases={A(adenine),G(guanine),T(thymine),C(cytosine)}RNAbases={A(adenine),G(guanine),U(uracil),C(cytosine)}DataStructures4.1IntroductiontoStringCommoncharactersetsusedincomputersASCIIcodeStandardASCII:uses7binarybitstorepresentonecharacterandcanrepresent128characters.ExtendedASCII:uses8binarybitstorepresentonecharacterandcanrepresent256characters.ItissufficientforEnglishandsomespecialsymbols,butcannotmeetinternationalneeds.UnicodeUses16binarybitstorepresentonecharacterandcanrepresent2^16characters,i.e.,morethan65,000characters.Itcanrepresentallcharactersofalllanguagesintheworld.Forcompatibility,thefirst256charactersinUnicodeareexactlythesameasextendedASCII.Chapter4StringandArrayDataStructures4.1KeyTopicsofStringWhatisastring?Whatareitslogicalcharacteristics?Whatareitsoperationalcharacteristics?Howshouldstringsbestored?Patternmatching:BFalgorithmandKMPalgorithmChapter4StringandArrayDataStructures4.1DefinitionofString

Astringisafinitesequenceofzeroormorecharacters.Itisaspecialtypeoflinearlistandisalsocalledacharacterstring.Linearlist(list):afinitesequenceofdataelementsof

thesametype.String:afinitesequenceofzeroormorecharacters.Theelementtypeischaracter.Inthebasicoperationsofalinearlist,theoperationobjectismostlyanindividualelement;Inthebasicoperationsofastring,thewholestringisusuallytakenastheoperationobject.Chapter4StringandArrayDefinitionOperationsDataStructures4.1IntroductiontoArrayandMatrixBombermangame:Howcanwerepresentthegamemap?Howcanwerepresentthepositionsoftheplayer,bombs,andmonsters?Useatwo-dimensionalarrayormatrix.QQQQQQQQChapter4StringandArrayDataStructures4.1IntroductiontoArrayandMatrixHowcanweorganizepixelsonacomputermonitor,andhowcanwestoreQRcodesandimages?Useatwo-dimensionalarrayormatrix.Chapter4StringandArrayDataStructures4.1Innumericalanalysis,whensolvingsystemsoflinearequations,howcanwerepresenttheequationsandthesolutionprocess?Useatwo-dimensionalarrayormatrix.Chapter4StringandArrayIntroductiontoArrayandMatrixDataStructures4.1KeyTopicsofArrayandMatrixWhatisanarray?Whatareitslogicalcharacteristics?Whatareitsoperationalcharacteristics?Howshouldarraysbestored?CompressedstorageofspecialmatricesCompressedStorageofSparseMatrixChapter4StringandArrayDataStructures4.1DefinitionofArrayArray:anorderedcollectionofdataelementsofthesametype.Eachdataelementiscalledanarrayelement,orsimplyanelement.Eachelementisconstrainedbyn(n≥1)linearrelations,anditsordinalnumbersi1,i2,…,ininthenlinearrelationsarecalleditssubscripts.Suchanarrayiscalledann-dimensionalarray.

a11…a1n

…………am1…amnA=a21

a22…a2na12am2Chapter4StringandArrayAtwo-dimensionalarrayisalinearlistwhosedataelementsarelinearlists.DataStructures4.1SpecialMatrixandSparseMatrixSpecialmatrix:manyelementsinthematrixhavethesamevalue,andtheirdistributionfollowsacertainpattern.Mainformsincludesymmetricmatrices,triangularmatrices,anddiagonalmatrices;allaresquarematrices.

Basicstorageidea:allocateonlyonestorageunitformultipleelementswiththesame

value;guaranteerandomaccess,i.e.,addressinginO(1)time.Sparsematrix:thematrixcontainsmanyzeroelements,andthenumberofnonzeroelementsisfarsmallerthanthetotalnumberofmatrixelements.Thedistributionofnonzeroelementsisirregularandrandom.

Basicstorageidea:donotallocatestoragespaceforzeroelements.Themainpurposeofcompressedstorageistosavestoragespace.Chapter4StringandArrayDataStructuresStringandItsStorageStructure4.2

Astringisafinitesequenceofzeroormorecharacters.Itisaspecialtypeoflinearlistandisalsocalledacharacterstring.Stringlength:thenumberofcharacterscontainedinastring,whichmaybe0;Non-nullstring:astringwhoselengthisnot0,usuallywrittenasS="s1

s2……sn"

Here,Sisthestringname;thedoublequotationmarksaredelimiters;

thecharacters

insidethemarethestringvalue;andsi（1≤i≤n）isanarbitrarycharacter.Nullstring:astringoflength0,writtenas"".4.2DefinitionofStringChapter4StringandArrayDataStructures4.2AbstractDataTypeofStringADTStringDatamodelDataelementsconsistofcharacters;adjacentelementshavepredecessorandsuccessorrelationships.OperationsstrAssign:stringassignmentstrLength:obtainstringlengthstrCpy:stringcopystrCat:stringconcatenationstrSub:obtainsubstringstrCmp:stringcomparisonstrIndex:substringpositioning,patternmatchingstrInsert:stringinsertionstrDelete:stringdeletionendADTAbstractdatatype=logicalstructure+basicoperationsLogicalstructure=setofdataelements+relationshipsamongdataelementsChapter4StringandArrayDataStructures4.2AbstractDataTypeofStringstrCmpstringcomparison:comparisonisperformedbycomparingthecharacters(ASCIIcodes)thatmakeupthestrings.GiventwostringsX="x1x2…xn"andY="y1y2…ym":1.X=Yifandonlyifn=mandx1=y1，…，xn=ym;2.X<Yifoneofthefollowingconditionsholds:(1)n＜mandxi=yi（1≤i≤n）；(2)thereexistsk≤min(m,n)，suchthatxi=yi(1≤i≤k-1)andxk＜yk.3.Inallothercases,X>Y.Chapter4StringandArrayExample1：S1="ab12cd"，S2="ab12"Example2：S1="ab12cd"，S3="ab13"S2<S1S1<S3

DataStructures4.2ComparisonBetweenStringandLinearListDefinitions

L=(a1,a2,…,ai,…,an)

S="

s1

s2……sn"String:afinitesequenceofzeroormorecharacters.Theelementtypeischaracter.NameDelimiterChapter4StringandArrayDefinitionRepresentationLinearlist(list):afinitesequenceofdataelementsofthe sametype.DataStructures4.2Inthebasicoperationsofalinearlist,theoperationobjectismostlyan“individualelement”;Inthebasicoperationsofastring,the“wholestring”isusuallytakenastheoperationobject.ComparisonBetweenStringandLinearListDefinitionsBasic

operations：Chapter4StringandArrayDataStructures4.2StorageStructureofStringLogically,astringisaspecialformoflinearlist;thedifferenceisthatitsdataelementsarerestrictedtocharacters.Therefore,storagemethodsforlinearlists,suchassequentiallistsandlinkedlists,cantheoreticallystorestrings.However,theapplicationscenariosandbasicoperationsofstringsdiffergreatlyfromthoseoflinearlists.Asaresult,stringstoragecannotsimplycopy

linear-liststoragemethods;ithasitsowncharacteristics.Therearetwostoragemethodsforstrings:SequentialstorageBlock-linkedstorageChapter4StringandArrayDataStructures4.2SequentialStorageStructureofStringSequentialstorageofastringstoresthecontentsofthestringinacontiguousstoragespace.Twomainproblemsneedtobesolved:Howtorecordthefirstaddressofthestoragespace?Howtorecordthestringlength?Method1:usecell0ofthearraytostorethestringlength,andusecell1asthefirstaddressofthestoragespace.Chapter4StringandArray01234567……MAX-1

7

abcdefgFreeWhatistheproblem?DataStructures4.2Method2:followingthesequential-listapproach,setanindependentlengthvariable.Chapter4StringandArray0123456……Max-1

abcdefgFree7

SequentialStorageStructureofStringSequentialstorageofastringstoresthecontentsofthestringinacontiguousstoragespace.Twomainproblemsneedtobesolved:Howtorecordthefirstaddressofthestoragespace?Howtorecordthestringlength?DataStructures4.2Method3:storeaspecialcharacterthatneverappearsinthestringattheendofthestringastheterminalcharacter,indicatingtheendofthestring.CommonmethodChapter4StringandArraySequentialstorageofastringstoresthecontentsofthestringinacontiguousstoragespace.Twomainproblemsneedtobesolved:Howtorecordthefirstaddressofthestoragespace?Howtorecordthestringlength?SequentialStorageStructureofString01234567……Max-1

abcdefg\0FreeDataStructures4.2Block-LinkedStorageStructureofStringAlinkedlistcanbeusedtostoreastring.Becauseeachdataelementofastringisonecharacter,thedatafieldofeachnodestores1character,whilethepointerfieldusuallytakes4bytes,resultinginlowstoragedensity.Exampleofstoringastringwithalinkedlist:storageof"shujujiegou"Storagedensity

=StoragespacefordataelementsActuallyallocatedstoragespaceChapter4StringandArrayDataStructures4.2Eachlinked-listnodestoresmultiplecharacters,givinghigherstoragedensity.Improvementoflinked-liststringstorage—block-linkedstorage:storageof"shujujiegou"Characteristicsofblock-linkedstorage:thedatafieldofeachnodeusesacontiguoussegmentofstorageunitstostoremultipledataelements,showingthecharacteristicsofsequentialstoragewithinablock;addressesofdifferentnodesneednotbecontiguous,andpointersindicatepredecessor-successorrelationships,showingthecharacteristicsoflinkedstoragebetweenblocks.Chapter4StringandArrayBlock-LinkedStorageStructureofStringDataStructuresPatternMatchingofString4.34.3BasicConceptsofPatternMatchingApplicationsofpatternmatching:patternmatchingisanimportantstringoperationwithwideapplications.Forexample,intext-editingprograms,weoftenneedtolocateaspecificwordinatext.Itisalsoimportantinemailfiltering,anti-virussoftware,compilationsystems,searchengines,andotherapplications.Patternmatching:giventhemainstringS=“s1s2…sn”andthesubstringT=“t1t2…tm”，theprocessoffindingTinSiscalledpatternmatching,alsocalledsubstringpositioning.Ifthematchsucceeds,returnthepositionofTinS;ifthematchfails,return-1.Inpatternmatching,Sisalsocalledthetargetstring,andTiscalledthepatternstring.Pattern-matchingalgorithms:BFalgorithmandKMPalgorithmChapter4StringandArrayDataStructures4.3BasicIdeaoftheBFAlgorithmBasicidea:ComparethefirstcharacterofthemainstringSwiththefirstcharacterofthesubstringT.Iftheyareequal,continuecomparingthesubsequentcharacters;ifallcharactersinTarecompared,thismatchingattemptsucceeds.Otherwise,comparethesecondcharacterofSwiththefirstcharacterofT.Iftheyareequal,continuecomparingsubsequentcharactersuntilallcharactersinThavebeencompared,indicatingasuccessfulattempt.Repeatthisprocess.IfallcharactersinShavebeencompared,thematchfails.BruteForcealgorithm：characterizedbybrute-forcematching.Chapter4StringandArrayDataStructures4.3ProcessoftheBFAlgorithmComparethefirstcharacterofthemainstringSwiththefirstcharacterofthesubstringT.Iftheyareequal,continuecomparingthesubsequentcharacters;ifallcharactersinThavebeencompared,thismatchingattemptsucceeds.Chapter4StringandArrayMatchsuccessfulDataStructures4.3ComparethefirstcharacterofthemainstringSwiththefirstcharacterofthesubstringT.Iftheyareequal,continuecomparingthesubsequentcharacters;ifallcharactersinThavebeencompared,thismatchingattemptsucceeds.Otherwise,comparethesecondcharacterofSwiththefirstcharacterofT.Iftheyareequal,continuecomparingthesubsequentcharacters;ifallcharactersinThavebeencompared,thismatchingattemptsucceeds.Repeatthisprocess.IfallcharactersinShavebeencompared,thematchfails.Chapter4StringandArrayProcessoftheBFAlgorithmMatchsuccessfulDataStructures4.3Chapter4StringandArrayProcessoftheBFAlgorithmMatchfailedComparethefirstcharacterofthemainstringSwiththefirstcharacterofthesubstringT.Iftheyareequal,continuecomparingthesubsequentcharacters;ifallcharactersinThavebeencompared,thismatchingattemptsucceeds.Otherwise,comparethesecondcharacterofSwiththefirstcharacterofT.Iftheyareequal,continuecomparingthesubsequentcharacters;ifallcharactersinThavebeencompared,thismatchingattemptsucceeds.Repeatthisprocess.IfallcharactersinShavebeencompared,thematchfails.DataStructures4.3

si

……MainstringSPatternT

tjji…BacktrackiBacktrackj1.SettheinitialcomparisonsubscriptsiandjinstringsSandT;2.LoopuntilallcharactersofSorThavebeencompared.2.1IfS[i]equalsT[j],continuetocomparethenextcharactersofSandT;2.2Otherwise,backtrackiandjtoprepareforthenextcomparisonattempt;3.IfallcharactersinThavebeencompared,returnthestartingsubscriptofthematch;otherwise,return0.Assumethatthestartingsubscriptofthestringis0.Chapter4StringandArrayProcessoftheBFAlgorithmDataStructures4.3si

……MainstringSPatternTji…

tj1.SettheinitialcomparisonsubscriptsiandjinstringsSandT;2.LoopuntilallcharactersofSorThavebeencompared.2.1IfS[i]equalsT[j],continuetocomparethenextcharactersofSandT;2.2Otherwise,backtrackiandjtoprepareforthenextcomparisonattempt;3.IfallcharactersinThavebeencompared,returnthestartingsubscriptofthematch;otherwise,return0.Whereshoulditbacktrack?jbacktracksto0ibacktrackstothestartingpositionofthepreviousattemptplus1Assumethatthestartingsubscriptofthestringis0.Chapter4StringandArrayProcessoftheBFAlgorithmDataStructures4.3BFAlgorithmChapter4StringandArray//Assumethatthestartingsubscriptofthestringis0.DataStructures4.3PerformanceAnalysisoftheBFAlgorithmLetthelengthofstringSbenandthelengthofstringTbem.Whenthematchsucceeds,considerthebestandworstcases:Bestcase:allunsuccessfulmatchingattemptsfailatthefirstcharacterofT.Supposethesuccessfulmatchoccursatsi.Chapter4StringandArrayDataStructures4.3PerformanceAnalysisoftheBFAlgorithmLetthelengthofstringSbenandthelengthofstringTbem.Whenthematchsucceeds,considerthebestandworstcases:Worstcase:allunsuccessfulmatchingattemptsfailatthelastcharacterofT.Example:S=“aaaaaaaaaaaaaaaaaaaaaaba” T=“aaaaab”Supposethesuccessfulmatchoccursatsi.Inthei-1unsuccessfulattempts,(i-1)×mcomparisonsaremade.Inthei-thsuccessfulattempt,mcomparisonsaremade.Therefore,thetotalnumberofcomparisonsisi×m,soChapter4StringandArrayDataStructures4.3ImprovementoftheBFAlgorithmWhyistheBFalgorithmslow?Eachunsuccessfulmatchingattemptinvolvesextensivebacktrackingandfailstomakeuseoftheresultsofpreviouspartialmatches.Patternmatching—KMPalgorithmAcommonlyusedimprovementoftheBFalgorithmBasicidea:themainstringdoesnotbacktrack,andeachcharacterinitismatchedonlyonce.Implementationidea:byanalyzingthepatternstring(substring),aftersiandtjfailtomatch,pointeridoesnotbacktrack.Instead,patternstringTslidesrighttoapositionksothattkalignswithsiandmatchingcontinues.Keyquestion:howtodeterminepositionk,i.e.,thenewstartingpointforcomparison.Difficulty:Chapter4StringandArrayWhyistheBFalgorithminefficient?DataStructures4.3KMPAlgorithmAttempt

1Attempt2i=2，j=2mismatch;Chapter4StringandArray

DataStructures4.3KMPAlgorithmAttempt2Attempt

3Chapter4StringandArrayThemainstringdoesnotneedtobacktrack.Compares6witht1DataStructures4.3KMPAlgorithmConclusion:SomematchingprocessesoftheBFalgorithmcanbeomitted;eitheranentireattemptoronlysomematchingstepsmaybeomitted.Allmatchingprocessesthatrequireitobacktrackcanbeomitted.idoesnotneedtobacktrack;weonlyneedtoslidethepatterntothenewcomparisonstartingpointk.Thesethreepointsarebasedonfullyusingpartiallymatchedresultsaftereachunsuccessfulattempt,andtheydependonlyonthepatternstringT,notdirectlyonthemainstring.Chapter4StringandArrayDataStructures4.3KMPAlgorithmTwobasiccharacteristicswhenthepatternslidesrightaftereachmismatch1.Assumethatthepatternslidestothek-thcharacter,thenT0～Tk-1

＝Si-k

～

Si-1Chapter4StringandArrayComparesiwitht2t0andt1arethesameassi-2andsi-1DataStructures4.3KMPAlgorithmTwobasiccharacteristicswhenthepatternslidesrightaftereachmismatchAssumethatthepatternslidestothek-thcharacter,thenT0～Tk-1

＝Si-k

～

Si-1.Also,Tj-k

～Tj-1

＝Si-k

～

Si-1.Combining1and2gives:T0～Tk-1

=Tj-k

～Tj-1

Chapter4StringandArrayDataStructuresSincetjandsidonotmatch,

​tj-1isthesameassi-1​tj-2​isalsothesameassi-24.3KMPAlgorithmWhatdoesT[0]~T[k-1]=T[j-k]~T[j-1]indicate?khasafunctionalrelationshipwithj,denotedasnext(j).Fromthecurrentmismatchpositionj,theslidingpositionk,i.e.,thenewstartingpointforcomparison,canbecalculated.TheslidingpositionkisrelatedonlytothepatternstringT.Moverightfromposition0

forkpositionsMoveleftfrompositionj-1forkpositionsWhatisthephysicalmeaningofT[0]~T[k-1]=T[j-k]~T[j-1]?Howfarshouldthepatternslideright,i.e.,whatisnext(j)?Toavoidmissingmatches,slideaslittleaspossible;therefore,kshouldbeaslargeaspossible.Chapter4StringandArrayDataStructuresmax{k|1≤k＜j

andT[0]…T[k-1]=T[j-k]…T[j-1]}4.3ProcessoftheKMPAlgorithmnext[j]=-1whenj=0Whenj=0,next[j]=-1;Thismeansjremainsunchanged,whileimovesonepositionbackwardandiscomparedwithtj.Theslidingpositionkcanbecalculatedbythefollowingformula:max{k|1≤k<jandT0…Tk-1=Tj-k-…Tj-1}Whenj>1,next[j]isthemaximumlengthofthesubstringwiththesameprefixandsuffixinthesubstringofthepatternfromposition0toj-1.Whenthereisnosubstringwiththesameprefixandsuffix,next[j]is0,andcomparisonstartsfromthebeginningofthepattern.Chapter4StringandArrayDataStructures0otherwiseSok=2Themaximumlengthis2.4.3ProcessoftheKMPAlgorithmChapter4StringandArrayDataStructures

PatternT：abaabcac

Mismatchj：01234567 k=next[j]:Whenj=0,next[j]＝Whenj=1,next[j]＝Whenj=2,next[j]＝Whenj=3,next[j]＝Whenj=4,next[j]＝Whenj=5,next[j]＝Whenj=6,next[j]＝Whenj=7,next[j]＝//For'a':nocommonprefix/suffix.//For'ab':nocommonprefix/suffix.//For'aba':longestcommonprefix/suffixno4.3ProcessoftheKMPAlgorithmExampleoftheKMPalgorithmGiven:

S="ababcabaabcaabaababcaab"T="abaababc"

Findnext[j]ofpatternTandwriteordrawtheKMPmatchingprocess.Chapter4StringandArrayDataStructures

PatternT：abaababcMismatchj：01234567

k=next[j]:nono4.3ProcessoftheKMPAlgorithmKMPalgorithmexampleChapter4StringandArrayDataStructuresS="ababcabaabcaabaababcaab"T="abaababc"next[j]="-10011232"Attempt1:4.3ProcessoftheKMPAlgorithmChapter4StringandArrayDataStructuresKMPalgorithmexampleS="ababcabaabcaabaababcaab"T="abaababc"next[j]="-10011232"Attempt2:4.3ProcessoftheKMPAlgorithmChapter4StringandArrayDataStructuresKMPalgorithmexampleS="ababcabaabcaabaababcaab"T="abaababc"next[j]="-10011232"Attempt3:4.3ProcessoftheKMPAlgorithmChapter4StringandArrayDataStructuresKMPalgorithmexampleS="ababcabaabcaabaababcaab"T="abaababc"next[j]="-10011232"Attempt4:4.3ProcessoftheKMPAlgorithmChapter4StringandArrayDataStructuresKMPalgorithmexampleS="ababcabaabcaabaababcaab"T="abaababc"next[j]="-10011232"Attempt5:4.3ProcessoftheKMPAlgorithmChapter4StringandArrayDataStructuresKMPalgorithmexampleS="ababcabaabcaabaababcaab"T="abaababc"next[j]="-10011232"Attempt6:4.3ProcessoftheKMPAlgorithmChapter4StringandArrayDataStructuresKMPalgorithmexampleS="ababcabaabcaabaababcaab"T="abaababc"next[j]="-10011232"Attempt7:4.3ProcessoftheKMPAlgorithmChapter4StringandArrayDataStructuresKMPalgorithmexampleS="ababcabaabcaabaababcaab"T="abaababc"next[j]="-10011232"Attempt8:Ifamatchisfound,returnthestartingposition.Arrayindex:i-jLinearlistposition:i−j+14.3KMPAlgorithmAtmismatchpositionj=5,therearetwokvaluessatisfyingT[0]~T[k-1]=T[j-k]~T[j-1]:k=1andk=3.Theycorrespondtoslidingthepatternstringsothatits1stor3rdcharacterbeginsmatchingthemainstringatpositioni.Itcanbeseenthatwhenk=1,thepatternslides4positionstotherightandskipsoverthesubstringposition,causinganerror.Therefore,kmusttakethemaximumvaluesothattheslidingdistanceisassmallaspossible.abababaa

baijababa

aabababaa

baijababa

aabababaa

baijababa

aSuccess!Whenk=1Whenk=3Canthelongestsubstringwiththesameprefixandsuffixoverlap?Chapter4StringandArrayDataStructures4.3ProcessoftheKMPAlgorithm1.SettheinitialcomparisonsubscriptsiandjinstringsSandT;2.LoopuntilallcharactersofSorThavebeencompared.2.1IfS[i]=T[j],continuetocomparethenextcharactersofSandT;otherwise2.2Slidejtothenext[j]position,i.e.,j=next[j];2.3Ifj=-1,incrementbothiandjby1toprepareforthenextcomparisonattempt;3.IfallcharactersinThavebeencompared,returnthestartingsubscriptofthematch;otherwise,return0.Chapter4StringandArrayDataStructures4.3KMPAlgorithmAlgorithmforfindingthenextfunctionvaluesofpatternstringTStudentsareencouragedtoimplementitthemselves;itisquitedifficult.Page101providesonesampleimplementation.Summary:TheKMPalgorithmisoneofthemostdifficultalgorithmstounderstandinthiscourse.Ascomputerscienceprofessionals,youareexpectedtomasteritscoreidea.FurtherimprovementsoftheKMPalgorithmstillexist,andyoumaystudythemindependently.Somegraduateentranceexamsincludethistopic.Chapter4StringandArrayDataStructuresCompressedStorageofMatrix4.44.4GeneralizedLinearListLinearlist:afinitesequenceofdataelementsofthesametype.ExtendtheelementtypeGeneralizedlinearlist(Multidimensional)array:thedataelementsinalinearlistcanthemselvesbelinearlists,butallelementsareofthesametype.Generalizedlist:thedataelementsinalinearlistcanthemselvesbelinearlists,andtheelementtypesmaybedifferent.Chapter4StringandArrayDataStructures4.4MultidimensionalArrayStorageandAddressingDefinitionofarray:Anarrayisanorderedcollectionofdataelementsofthesametype.Eachdataelementiscalledanarrayelement,orsimplyanelement.Inann-dimensionalarray,eachelementisconstrainedbyn(n≥1)linearrelations.Theordinalnumbersi1、i2、…、inofanelementinthesenrelationsarecalleditssubscripts.Characteristicsofarrays:Elementsthemselvesmayhaveacertainstructureandbelongtothesamedatatype;Anarrayisadatacollectionwithafixedformatandafixednumberofelements.Chapter4StringandArrayDataStructures4.4ExampleofMultidimensionalArraya11a12…a1na21

a22…a2n…………am1am2…amnA=Elementa22isconstrainedbytwolinearrelations.Intherowdirection,ithasrowpredecessora21androwsuccessora23.Inthecolumndirection,ithascolumnpredecessora12andcolumnsuccessora32.Atwo-dimensionalarrayisalinearlistwhosedataelementsarelinearlists.MultidimensionalArrayStorageandAddressingChapter4StringandArrayDataStructures

A=(A1，A2，……，An)

where：

Ai=(a1i，a2i，……，ami)(1≤i≤n)4.4BasicOperationsofArrayIsitmeaningfultoinsertordeleteanelementinanarray?a11a12…a1na21a22…a2n…………am1am2…amnA=Insertelementx

intorow1,column2ofthearray.xa11a12…a1na21a22…a2n……