资源描述：
《第4章-多维数组和广义表.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第4章多维数组和广义表4.1多维数组4.2数组的存储结构4.3矩阵的压缩存储特殊矩阵和特殊矩阵4.4广义表的基本概念线性表——具有相同类型的数据元素的有限序列。限制插入、删除位置线性表——具有相同类型的数据元素的有限序列。限制元素类型为字符栈——仅在表尾进行插入和删除操作的线性表。队列——在一端进行插入操作，而另一端进行删除操作的线性表。串——零个或多个字符组成的有限序列。特殊线性表线性表——具有相同类型的数据元素的有限序列。将元素的类型进行扩充广义线性表（多维）数组——线性表中的数据元素可以是线
2、性表，但所有元素的类型相同。广义表——线性表中的数据元素可以是线性表，且元素的类型可以不相同。4.1多维数组多维数组可看成线性表的推广。一维数组：就是线性表；二维数组：每个元素为一维数组的线性表，这个元素可以是行向量，也可以是列向量。三维数组：每个元素为二维数组的线性表。n维数组：每个元素为n−1维数组的线性表。非线性：元素受多个线性关系（如行、列）的约束，可多个前驱和后继。元素类型相同，元素个数和元素间关系在数组建立后一般不能改变。constintm=10;constintn=5;typedef
3、intR[n];Rx[m];intx[m][n];constintm=10;constintn=5;typedefintA[m][n];Ax;基本运算——读和写：（1）读：给定一组下标，读出相应的元素。（2）写：给定一组下标，修改相应的元素。存取和修改操作本质上只对应一种操作——寻址4.2数组的存储结构A[0..n]：LOC(i)=LOC(0)+i×cA[1..n]：LOC(i)=LOC(1)+(i−1)×c没有插入和删除运算，采用顺序存储方式一、一维数组：设一维数组的下标的范围为闭区间［s，t］
4、，每个数组元素占用c个存储单元，则其任一元素ai的存储地址可由下式确定：Loc(ai)＝Loc(as)＋(i－s)×ccasai-1ai……atas+1……Loc(ai)4.2数组的存储结构非线性结构，但内存单元是一维的线性结构，在进行顺序存储时，需要将多维关系映射为一维的线性关系。二、二维数组：常用的映射方法有两种：按行优先：先行后列，先存储行号较小的元素，行号相同者先存储列号较小的元素。按列优先：先列后行，先存储列号较小的元素，列号相同者先存储行号较小的元素。二维数组内存二维结构一维结构行优先
5、：按行排列，如PASCAL、C，对A[1..m][1..n]:a11,a12,…,a1n,a21,a22,…a2n,……,am1,am2,…,amn对A[s..t][q..r]:h=(i−s)×(r−q+1)+(j−q+1)LOC(i,j)=LOC(s,q)+(h−1)×c=LOC(s,q)+[(i−s)×(r−q+1)+(j−q)]×c对A[1..m][1..n]:LOC(i,j)=LOC(1,1)+[(i−1)×n+(j−1)]×c对A[0..m-1][0..n-1]，即C数组A[m][n]:
6、LOC(i,j)=LOC(0,0)+[i×n+j]×c列优先：按列排列，如FORTRAN，对A[1..m][1..n]a11,a21,…,am1,a12,a22,…am2,……,an1,an2,…,anm提问：列优先时，元素相对位置如何计算？行优先：对每一个左下标，逐个变动其右边的下标（右下标先动），或说，先排最右的下标，从右到左，最后排最左下标。列优先：对每一个右下标，逐个变动其左边的下标（左下标先动），或说，先排最左的下标，从左向右，最后排最右下标。如三维数组A[2..3,0..1,1..3]
7、，按行存储：a201,a202,a203,a211,a212,a213,a301,a302,a303,a311,a312,a313三维数组A[1..m,1..n,1..p]，按行存储：LOC(i,j,k)=LOC(1,1,1)+[(i−1)×n×p+(j−1)×p+(k−1)]×c不论是按行存储还是按列存储，数组元素的地址都是其下标的线性函数，任一元素都可在相同的（逻辑）时间内存取，故数组是一种随机存取结构。三、多维数组：m页,每页n行p列四维：A[1..m,1..n,1..p,1..q]？数组A
8、[0..4,-1..-3,5..7]中含有元素的个数（）。A.55B.45C.36D.16设二维数组A[1..m，1..n]（即m行n列）按行存储在数组B[1..m*n]中，则二维数组元素A[i，j]在一维数组B中的下标为()。A.（i-1）*n+jB.（i-1）*n+j-1C.i*（j-1）D.j*m+i-1BA二维数组A的元素都是6个字符组成的串，行下标i的范围从0到8，列下标j的范圈从1到10。从供选择的答案中选出应填入下列关于数组存储叙述中（）内的正确答案。（1）存放A至少
