资源描述：
《数据结构（C语言描述） 马秋菊 第4章数组》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、4.1数组（重点）4.2特殊矩阵的压缩存储4.3广义表小结第4章数组、特殊矩阵和广义表2021/8/15第页本章学习目标掌握多维数组的概念以及在计算机中的存储表示；掌握对称矩阵、三角矩阵、对角矩阵的压缩存储表示及地址运算公式；稀疏矩阵在计算机中的存储表示及基本运算的实现；广义表的逻辑结构和基本运算。2021/8/15第页4.1数组4.1.1数组的基本概念数组作为一种数据结构其特点是结构中的元素本身可以是具有某种结构的数据，但属于同一数据类型，比如：一维数组可以看作一个线性表，二维数组可以看作“数据元素是一维数组”的一维数组，三维数组可以看
2、作“数据元素是二维数组”的一维数组，依此类推。数组的定义：数组（array）是由下标（index）和值（value）组成的序对集合。在C语言中，一维数组定义为：ElemTypearrayname[MAXSIZE];2021/8/15第页下图一个m行n列的二维数组。它可以看成是由行向量组成的向量，也可以看成是由列向量组成的向量。在数组中通常做下面两种操作：(1)取值操作：给定一组下标，读其对应的数据元素。(2)赋值操作：给定一组下标，存储或修改与其相对应的数据元素。a00a01…a0,n-1a10a11…a1,n-1………aij………am-
3、1,0am-1,1…am-1,n-1A=m行n列的二维数组与线性表的区别：在数组中不能进行插入、删除数据元素的操作。2021/8/15第页4.1.2数组的存储结构一维数组在计算机内是存放在一组连续的存储单元中。因此，数组中任一元素A[i]的存储位置可用下列公式计算：LOC（A[i]）=LOC（A[0]）+(i)×L其中L是每个数据元素所占存储单元的个数。对于一维数组按下标顺序分配即可。a00a01…a0,n-1a10a11…a1,n-1………aij………am-1,0am-1,1…am-1,n-1A=m行n列的二维数组二维数组的存储器，一般
4、有两种存储方式：一是以行为主序的顺序存放，如BASIC、C等程序设计语言，即一行分配完了接着分配下一行。2021/8/15第页C语言中，数组就是按行优先顺序存储的。如，一个2×3的二维数组A2×3，以行为主序的分配顺序为：a00，a01，a02，a10，a11，a12。以列为主序分配顺序为：a00,a10,a01,a11,a02,a12a00a01a02a10a11a12A2×3=2×3的二维数组a00a01a02a10a11a12a00a10a01a11a02a12以行为主序以列为主序2021/8/15第页在C语言中，二维数组定义为：E
5、lemTypearrayname[m][n];数组中任一元素A[i][j]的存储位置可用下列公式计算：LOC(A[i][j])=LOC(A[0][0])+(i×n+j)×L这是因为数组元素A[i][j]的前面有i行，每一行的元素个数为n，在第i行中A[i][j]的前面还有j个数组元素。L仍然是每个数据元素所占存储单元的个数。例如2×3二维数组：LOC(a12)=LOC(a00)+[(1)*3+2]*La00a01a02a10a11a12A=2021/8/15第页【例4-1】选择题。设二维数组M的每个数据元素占6个存储单元，行下标i的范围从
6、0到8，列下标j的范围从1到10，则存放M至少需要(Ⅰ)个字节；若M按行优先方式存储，元素M[8][5]的起始地址与当M按列优先方式存储时的(Ⅱ)元素的起始地址一致。(Ⅰ)A.90B.180C.240D.540(Ⅱ)A.M[8][5]B.M[3][10]C.M[5][8]D.M[0][9](1)二维数组M共有(8-0+1)×(10-1+1)=90个数据元素，所以共占90×6=540个字节，即(Ⅰ)选D.(2)M[8][5]的存储位置为：LOC(M[8][5])=LOC(M[0][1])+504在(Ⅱ)中只有B.有表达是：LOC(M[3][
7、10])=LOC(M[0][1])+504,因此(Ⅱ)选B.2021/8/15第页在科学与工程计算问题中，矩阵中非零元素呈某种规律分布或者矩阵中出现大量的零元素的情况，比如常见的一些特殊矩阵，如三角矩阵、对称矩阵、带状矩阵、稀疏矩阵等。4.2.1对称矩阵4.2特殊矩阵的压缩存储在一个n阶方阵中，对称矩阵的特点是：若数据元素满足下列性质：36285198603６ 8 96 ２5 88 5 169 8 6 0A=A[i][j]=A[j][i]（0≤i,j≤n-1）2021/8/15第页A[i][j]和SA[k]之间对应关系:若i≥j，则A[i
8、][j]在下三角矩阵中，A[i][j]之前的i行一共有1+2+…+i=i×(i+1)/2个元素，在第i行上，A[i][j]之前有j个元素，因此有：k=i×(i+1)/2+j若i
