(5.1.1)--chapter5-1数组的定义与顺序存储.pdf

《(5.1.1)--chapter5-1数组的定义与顺序存储.pdf》由会员分享，可在线阅读，更多相关《(5.1.1)--chapter5-1数组的定义与顺序存储.pdf（12页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、 数据结构与算法Data Structures and Algorithms 数组的定义与顺序存储Definition of Array and Sequential StorageArray A is a finite sequence of n(n0)elements，denoted by A=(a1,an)l ai(1in)are all either atomic items ei (i.e.,specific value)with the same data type,or sub-arrays Bi with the same definition.lThe dimension o

2、f array A=(a1,an)is defined as：l n is the length of dimension 1 of array A;the length of ai equals to the length of dimension 2 of array A.l While defining an array,we need to give the length or range of each dimension of the array.Dim(A)=1 ai(1in)are all atomic itemsDim(ai)+1 ai(1in)are all sub-arr

3、ays Bi1Data StructuresData Structures1.Definition of arrayChapter 5 Arrays and generalized tablesl Defining an n-dimension array(n0)in C Lang.Let Li (1 i n)be any positive integern Syntax：ElemType arrayNameL1Ln;n Semantics：the length of dimension 1 is L1，and each element is a sub-array of L2*.*Ln.l

4、For example:a major has 50 courses in its program,and there are 100 students in each grade of the majorn Save the math scores of 100 students（100 atomic items）1-dimension array：int mathScore100 Length of the array：100 Element of the array：atomic item1.Definition of arrayin C LanguageChapter 5 Arrays

5、 and generalized tables2Data Structuresn Keep the 50 courses scores of all the students of a grade（50*100 atomic items）2-dimension array：int gradeScore50100 The length of array：The 1st dimension:50;The 2nd dimension:100.Element of the array：sub-array of length 100n Store all the students scores of 1

6、0 grades（10*50*100 atomic elements）3-dimension array:int allGradeScore1050100 Length of the array:The 1st dimension:10;The 2nd dimension:50;The 3nd dimension:100.Element of the array:2-dimension sub-array of the size 50*100.3l Defining an n-dimension array in Fortran.Let Li(1 i n)be any positive int

7、eger.n Syntax：ElemType array(L1,Ln);n Semantics：the length of dimension 1 is Ln，an each element is sub-array of L2*.*Ln;Data Structuresl For example：a major has 50 courses and each grade of the major has 100 students.To keep the 50 courses scores of all the 100 students of a grade:n 2-dimension arra

8、y：integer gradeScore(50,100)The length of the arrays：the lengths of dimension 1 and 2 are 100 and 50 respectively Element of the array：sub-array of length 50.n 2-dimension array：integer gradeScore(100,50)The length of the array：the lengths of dimension 1 and 2 are 50 and 100 respectively Element of

9、the array：sub-array of length 1001.Definition of arrayin Fortran LanguageChapter 5 Arrays and generalized tables4lKey problem：mapping the multi-dimension data space to linear memory space.lFor any array A=(a1,an)(n0)，the sequential storage scheme can be inductively defined as follows：n Recursion bas

10、is：ai is atomic item ein Recursion condition：ai is array Bie1eneiHigh addressB1BnBiHigh addressData Structures2.Sequential storage of arrayChapter 5 Arrays and generalized tables5mnmmnnnmAa.aa.a.aaa.aa2122221112112a.ma1aIn case of A being a matrix,the scheme is called row-first storage.lC Language：E

11、lemType Amn;a11a1na12am1amnam21ama In prog.Lang.C,Basic and Pascal，the elements of a matrix in memory are organized with the ascending order on low dimensional subscripts of the elements.Data StructuresData Structures2.Sequential storage of arraysHigh subscript firstHigh addressChapter 5 Arrays and

12、generalized tables6mnmmnnnmAa.aa.a.aaa.aa212222111211In case of A being a matrix,the scheme is called column-first storage.1(B2.)nlFortran：ElemType A(m,n);a11am1a21a1namna2n1mHigh address Fortran language takes the high dimensional subscript first storage.Data Structures2.Sequential storage of array

13、sHigh subscript firstChapter 5 Arrays and generalized tables7l The basic operations：n Initialization：InitArray(A,bound1,boundn)InitArray(A,low1,up1,lown,upn)n Destruction：Destroy(A)n Assignment：SetValue(A,e,index1,indexn)n Reading：GetValue(A,e,index1,indexn)l Operating characteristics：n Accessing an

14、 array is mainly on reading and writing；n Seldom on element inserting or deleting；n Supporting randomly access an element with its subscript(position indexes of each dimension).Data StructuresChapter 5 Arrays and generalized tables3.The basic operations on array8For array ，let the size of each atomi

15、c item be size，The function Loc to compute the location of element ai1,.,in is defined as：=Loc(A,1,1)+(ij-1)Lk)*sizenj=1nK=j+11.1n(a,.,a)NLLAa1,.,1.High addressai1,1,1,.,11a1iaLoc(A,i1,in)=Loc(A,1,1)ai1,1,1,.,LNai1,i2,1,.,1+(i1-1)L2LNsize+(i2-1)L3LNsize+(iN-1)size =Loc(A,0,0)C Lang.+(ij Lk)*sizenj=1

16、nK=j+1Data StructuresData Structures4.Randomly access an array-low dimensional subscript first storageChapter 5 Arrays and generalized tables9 Let A be a 2-dimension array with the size of 10*20，and each element occupies 2 bytes,and the address of element A1,1 be 100.If array A is saved with low sub

17、script first strategy,the address of element A6,10?A 6,10=100+(6-1)*20*2 +(10-1)*2 =318lExample of address calculationa1,1.a1,20a5,20a6,1.a6,10Data StructuresData StructuresHigh address4.Randomly access an array-low dimensional subscript first storageChapter 5 Arrays and generalized tables10 Exercis

18、e after class：Define the address computing function for arrays saved with the high subscript first storage strategy.l Features of multi-dimension array：Its elements are sub-arrays in a same definition；Its elements have the linear dependence relationship on the macro level.l Sequential storage scheme

19、：Designed according to the inductive definition of array；Realizes the mapping from multi-dimension relationship of arrays elements to the 1-dimension memory space；Supports randomly access any element directly.Data StructuresData Structures5.SummaryChapter 5 Arrays and generalized tables Thank you!D Da at ta a S St tr ru uc ct tu ur re es s