数据结构05数组和广义表11.

《数据结构05数组和广义表11.》由会员分享，可在线阅读，更多相关《数据结构05数组和广义表11.（58页珍藏版）》请在金锄头文库上搜索。

1、*1 本章主要介绍本章主要介绍数组数组的概念及的概念及多维数组多维数组在计算机中的在计算机中的存放存放， 特殊矩阵的压缩存储及相应运算，广义表的概念和存储结构及特殊矩阵的压缩存储及相应运算，广义表的概念和存储结构及 其相关运算的实现。通过本章学习，要求掌握如下内容：其相关运算的实现。通过本章学习，要求掌握如下内容： 1 1多维数组的定义及在计算机中的存储表示；多维数组的定义及在计算机中的存储表示； 2 2对称矩阵、三角矩阵、对角矩阵等特殊矩阵在计算机中的对称矩阵、三角矩阵、对角矩阵等特殊矩阵在计算机中的 压缩存储表示及地址计算公式；压缩存储表示及地址计算公式； 3 3稀疏矩阵的三元组表示及转置

2、算法实现；稀疏矩阵的三元组表示及转置算法实现； 4 4稀疏矩阵的十字链表表示及相加算法实现；稀疏矩阵的十字链表表示及相加算法实现； 5 5广义表存储结构表示及基本运算。广义表存储结构表示及基本运算。 本章学习导读本章学习导读 *2 数组和广义表数组和广义表可看成是一种可看成是一种特殊的线性表，特殊的线性表，其特殊在于其特殊在于，表，表 中的数据元素本身也是一种线性表。中的数据元素本身也是一种线性表。 5 5.1 .1 .1 .1 数组的定义数组的定义 数组是大家都已经很熟悉的一种数据类型，几乎所有高级 语言程序设计中都设定了数组类型。 数组（Array）是由n(n1)个相同类型数据元素a0，a

3、l， ai，an-1构成的有限序列。n是数组的长度。其中数组中的数 据元素ai是一个数据结构，即ai可以是线性表中的一个元素，本 身也可以是一个线性表，而线性子表中的每一个数据元素还可以 再分解 。根据数组元素ai的组织形式不同，数组可以分为一 维数组、二维数组以及多维（n维）数组。 5 5.1 .1 数数 组组 *3 有时也把有时也把一维数组一维数组称为称为向量向量，二维数组二维数组称为称为矩阵矩阵。在二维。在二维 或多维数组中，每个数组元素都受到或多维数组中，每个数组元素都受到2 2个或个或n n个关系的约束。当个关系的约束。当 数组为数组为n n维时，其对应线性表中的每个元素又是一个线性

4、表。维时，其对应线性表中的每个元素又是一个线性表。 在每个关系中，每个元素都有一个在每个关系中，每个元素都有一个直接后继直接后继。因此，。因此，就其单个就其单个 关系而言，这关系而言，这n n个关系中的每一个仍然是一种线性关系。个关系中的每一个仍然是一种线性关系。 数组中数组中每个元素每个元素都是由都是由一个值一个值和和一组下标一组下标来确定的。同线来确定的。同线 性表一样，数组中的所有数据元素都必须属于同一数据类型。性表一样，数组中的所有数据元素都必须属于同一数据类型。 元素下标的个数被称为元素下标的个数被称为数组的维数数组的维数。显然，当维数为。显然，当维数为1 1时，数时，数 组就退化为

5、定长的线性表。组就退化为定长的线性表。 *4 1一维数组 一维数组可以看成是一个线性表或一个向量，它在计算机 内是存放在一块连续的存储单元中，适合于随机查找。 一维数组记为一维数组记为AnAn或或A=( aA=( a 0 0 ，a a l l ，a a i i ，a an-1 n-1) ) 一维数组中，一旦a0的存储地址、一个数据元素所占存储 单元数L确定，则ai的存储地址LOC(ai)就可求出： LOC(ai)=LOC(a0)+i*L (0in) 2二维数组 二维数组，又称矩阵(matrix)。二维数组中的每一个元素又 是一个定长的线性表（一维数组），都要受到两个关系即行关 系和列关系的约束

6、，也就是每个元素都同属于两个线性表。例 如，设A是一个有m行n列的二维数组，则A可以表示为： *5 可以看成由m个行向量组成的向量，也可以看由n个列向量 组成的向量。 数组中的每个元素由元素值aij及一组下标（i，j）来确 定。aij既属于第i行的行向量，又属于第j列的列向量。 其中，ai=( ai,0 ai,1 ai,n-1) (0in) 可以认为Am*n=A，A是这样的一维数组： A=( a0，al，ai，am-1) *6 显然，二维数组同样满足数组的定义。一个二维数组可以 看作是每个数据元素都是相同类型的一维数组。以此类推，任 何多维数组都可以看作一个线性表，这时线性表中的每个数据 元素

7、也是一个线性表。多维数组是特殊的线性表，是线性表的 推广。 数组的性质： (1) 数组中的数据元素数目固定。一旦定义了一个数组，其数 据元素数目不再有增减变化。它属于静态分配存储空间的数据 结构。 (2) 数组中的数据元素必须具有相同的数据类型。 (3) 数组中的每个数据元素都有一组唯一的下标值。 (4) 数组是一种随机存储结构。可随机存取数组中的任意数据 元素。 *7 对于多维数组，有两种存储方式：Am,n 以行序为主序的顺序存储； 数组元素按行向量排列，即第i+1个行向量紧接在第i个 行向量之后, 把所有数组元素顺序存放在一块连续的存 储单元中。 任一数据元素的存储地址可由公式算出： Lo

8、c(a i,j)=loc(a 0,0)+(i*n+j)*L 以列序为主序的顺序存储 在以列序为主序的存储方式中，数组元素按列向量排列 ，即第j+1个列向量紧接在第j个列向量之后, 把所有数组 元素顺序存放在一块连续的存储单元中。 任一数据元素的存储地址可由公式算出 Loc(a i,j)=loc(a 0,0)+(j*m+i)*L *8 推广到一般 设二维数组行下界为c1,行上界为d1,列下界为c2，列上界为 d2,即数组Ac1d1,c2d2. -则以行序为主序的求元素地址公式可以为： Loc(a i,j)=loc(a c1,c2)+(i-c1)*(d2-c2+1)+(j-c2)*L 则以列序为主

9、序的求元素地址公式可以为： Loc(a i,j)=loc(a c1,c2)+(j-c1)*(d1-c1+1)+(i-c1)*L *9 5.1.2 5.1.2 数组的数组的基本操作基本操作 数组一旦被定义，它的维数和维界就不再改变。因此，除 了结构的初始化和销毁之外，数组的基本操作一般不会含有元 素的插入或删除等操作,数组只有访问数组元素和修改元素值 的操作。 (1) 取值操作：给定一组下标，读其对应的数据元素。 (2) 赋值操作：给定一组下标，存储或修改与其相对应的 数据元素。 我们着重研究二维和三维数组，因为它们的应用是广泛的 ，尤其是二维数组。 *10 5.1.3 5.1.3 数组的数组的

10、存储结构存储结构 通常，数组在内存中被映象为向量，即用向量作为数组的 一种存储结构，这是因为内存的地址空间是一维的，数组的行 列固定后，通过一个映象函数，则可根据数组元素的下标得到 它的存储地址。 对于一维数组按下标顺序分配即可。 对多维数组分配时，要把它的元素映象存储在一维存储器 中，一般有两种存储方式：一是以行为主序（或先行后列）的 顺序存放，如BASIC、PASCAL、COBOL、C等程序设计语言中用 的是以行为主的顺序分配，即一行分配完了接着分配下一行。 另一种是以列为主序（先列后行）的顺序存放，如FORTRAN语 言中，用的是以列为主序的分配顺序，即一列一列地分配。 *11 以行为主

11、序的分配规律是：最右边的下标先变化 ，即最右下标从小到大，循环一遍后，右边第二个 下标再变，从右向左，最后是左下标。 以列为主序的分配规律恰好相反：最左边的下标 先变化，即最左下标从小到大，循环一遍后，左边 第二个下标再变，从左向右，最后是右下标。 *12 例如一个23的二维数组，逻辑结构可以用左图表示。 以行为主序的内存映象如右图（a）所示。 分配顺序为：a11 ，a12 ，a13 ，a21 ，a22 ，a23 ；以列为主序的分配顺序为： a11 ，a21 ，a12 ，a22 ，a13 ，a23 ；它的内存映象如右图（ b）所示。 *13 设有mn二维数组Amn，下面我们看按元素的下标求其地

12、 址的计算： 以“行为主序”的分配为例：设数组的基址为LOC(a11)，每 个数组元素占据l个地址单元，那么aij 的物理地址可用一线 性寻址函数计算： LOC(aij) = LOC(a11) + ( (i-1)*n + j-1 ) * l 在C语言中，数组中每一维的下界定义为0，则： LOC(aij) = LOC(a00) + ( i*n + j ) * l 推广到一般的二维数组：Ac1.d1 c2.d2，则aij的物理地 址计算函数为： LOC(aij)=LOC(a c1 c2)+( (i- c1) *( d2 - c2 + 1)+ (j- c2) )*l *14 同理对于三维数组Amnp

13、，即mnp数组，对于数组元素 aijk其物理地址为： LOC(aijk)=LOC(a111)+( ( i-1) *n*p+ (j-1)*p +k-1)*l 推广到一般的三维数组：Ac1.d1 c2.d2 c3.d3，则aijk 的物理地址为： LOC(i,j)=LOC(a c1 c2 c3)+( (i- c1) *( d2 - c2 + 1)* (d3- c3 + 1)+ (j- c2) *( d3- c3 + 1)+(k- c3)*l *15 三维数组的逻辑结构和以行为主序的分配示意图如图所示。 *16 (2)由于C语言采用行序为主序的存储方式，有： LOC(a2,3)=LOC(a0,0)+

14、(i*n+j)*k =1000+(2*4+3)*4 =1044 【例1】在C语言中，对于给定的二维数组float a34，计算： (1) 数组a中的数组元素数目； (2) 若数组a的起始地址为1000，且每个数组元素长度为32位(即 4个字节)，数组元素a23的内存地址。 【解】(1)由于C语言中数组的行、列下标值的下界均为0，该数 组行上界为3-1=2，列上界为4-1=3，所以该数组的元素数目共有 3*4=12个。 *17 【例2】有m名学生，每人考n门功课，试写出求任一学生总分数和 任一课程总分数的数据结构和算法。 【解】把学生的考试成绩存放在m行n列的二维数组中，则第 i(0im)行第j

15、(0jn)列中存放了第i个学生的第j门课程考试成 绩。即数据结构为： #define M 10 /假设为10人 #define N 3 /假设为3 int scoreMN; /学生成绩二维数组 求第i名学生总分数的算法为： int student_sum(int scoreMN,int i) int j,sum=0; for(j=0;jN;j+) sum=sum+scoreij; return(sum); *18 求第j门课程总分数的算法为： int course_sum(int scoreMN,int j) int i,sum=0; for(i=0;iM;i+) sum=sum+scoreij; return(sum); *19 矩阵是数值计算程序设计中经常用到的数学模型，它是由 m 行和 n 列的数值构成（当m=n 时称为方阵）。在高级级程序设设 计语计语 言中，通常用二维数组二维数组表示矩阵