数据结构 第五章 数组

《数据结构 第五章 数组》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、数据结构5数组15数组和广义表主要内容数组的基本概念数组的存储结构矩阵的压缩存储特殊矩阵稀疏矩阵25数组和广义表数组的基本概念数组的定义数组是下标与值组成的偶对的有穷集合。数组的基本操作给定一组下标，存取或修改相应元素的值。给定一组下标，检索相应的数组元素。对数组元素进行排序。对数组的操作是基于下标进行的35数组和广义表数组的存储结构一维数组A[1:n]A[1..n]=(a1,a2,a3,…,an-1,an)一维数组的特点给定一组下标，存取或修改相应元素的值。除了第一个元素外，其他每个元素有且仅有一个直接前驱。除了最后那个元素外，其他每个元素有

2、且仅有一个直接后继元素。一维数组的存储LOC(ai)=LOC(a1)+(i-1)k典型的线性结构a1a2a3a4a5…an-1anLOC(a1)45数组和广义表数组的存储结构二维数组A[1:m,1:n]二维数组在内存中的存放二维数组的“二维”是逻辑上的内存永远是线性编址0,00,10,20,31,01,11,21,32,02,12,22,33,03,13,23,34,04,14,24,30,00,10,20,31,01,11,21,32,02,1...内存中的存放方式9*2字节55数组和广义表数组的存储结构LOC(aij)=LOC(a11)+

3、(i-1)nk+(j-1)k=LOC(a11)+[(i-1)n+(j-1)]k若已知每个元素占k个存储单元，并且知道第一个元素的存储地址LOC(a11)，则二维数组的存储行序为主序分配方式特点前一行最后一个元素的存储位置与后一行的第一个元素的存储位置相邻。65数组和广义表数组的存储结构特点前一列最后一个元素的存储位置与后一列的第一个元素的存储位置相邻。二维数组的存储列序为主序分配方式LOC(aij)=LOC(a11)+(j-1)mk+(i-1)k=LOC(a11)+[(j-1)m+(i-1)]k若已知每个元素占k个存储单元，

4、并且知道第一个元素的存储地址LOC(a11)，则75数组和广义表问题：数组与线性表的区别与联系相同之处：都是由若干个相同数据类型的数据元素a0,…,an-1构成的有限序列。不同之处：(1)数组要求其元素占用一块地址连续的内存单元空间，而线性表无此要求；(2)线性表的元素是逻辑意义上不可再分的元素，而数组中的每个元素还可以是一个数组；(3)数组的操作主要是向某个下标的数组元素中存放数据和取读取某个下标中的数组元素，这与线性表的插入和删除操作不同。85数组和广义表0,0,00,1,00,2,00,3,01,0,01,1,01,2,01,3,02,0

5、,02,1,02,2,02,3,03,0,03,1,03,2,03,3,04,0,04,1,04,2,04,3,0yxz0,0,10,0,20,1,10,1,20,2,10,2,20,3,10,3,21,3,22,3,23,3,24,3,2N维数组三维数组Amnp，即m×n×p数组，对于数组元素aijk其物理地址为：LOC(aijk)=LOC(a111)+((i-1)*n*p+(j-1)*p+k-1)*l推广到一般的三维数组：A[c1..d1][c2..d2][c3..d3]，则aijk的物理地址为：LOC(i,j,k)=LOC(ac1c2c3

6、)+((i-c1)*(d2-c2+1)*(d3-c3+1)+(j-c2)*(d3-c3+1)+(k-c3))*l95数组和广义表魔术方阵往一个n为奇数的n×n的魔术方阵中填入1到n2的整数，能使其各列、各行及对角线之和皆相等。规则：首先将1填入最上列的中间格，然后往左上方走，(1)以1的级数增加其值，并将此值填入空格；(2)若方格已填满，则在原地的下一方格填上数字，并继续做；(3)若超出方阵，则往下到最底层或往右到最右方，看两者哪一个有方格，即将数字填入此方格；(4)若两者皆无方格，则在原地的下一方格填上数字。105数组和广义表3阶魔方115数

7、组和广义表5阶魔方形成的步骤A、将1填入此方阵最上列的中间方格，如图1所示。图1插入1后的魔术方阵图图2插入2后的魔术方阵图B、在A的基础上往左上方走，由于超出方阵，依据规则(3)发现往下的最底层有空格，因此将2填上，如图2所示。125数组和广义表5阶魔方形成的步骤C、承B往左上方，依据规则(1)将3填上，然后再往左上方，此时，超出方阵，依据规则(3)将4填入最右方的方格，如图3所示。图3插入3后的魔术方阵图图4插入4后的魔术方阵图D、承C往左上方，依据规则(1)将5填上，再往左上方时，此处方格已有数字，依据规则(2)往5的下方填，如图4所示。

8、135数组和广义表5阶魔方形成的步骤E、依此类推，依据上述4个规则继续填，填到15的结果如图5所示。图5插入15后的魔术方阵图图6插入16后的魔术方阵