数据结构：第五章：多维数组、稀疏矩阵和广义表.pptVIP

2003年12月1日软件需求工程第五章：多维数组、稀疏矩阵和广义表5.1多维数组5.2稀疏矩阵5.3广义表5.4小结5.1多维数组数组是有序并具有相同类型数据的集合数组中每一个元素都属于同一个数据类型用一个统一的数组名来标识这一组数据用下标来唯一标识数组中的元素序号数组有一维数组、二维数组和多维数组在一维数组中，组成数组的所有元素都是同一类型的简单变量，如果数组中的所有元素又都是一维数组，则称其为二维数组。以此类推可得多维数组的概念。数组的基本操作：初始化：生成一个新的数组存储：对给定下标的数组元素进行赋值检索：查找给定下标的数组元素的值。5.1多维数组二维数组多维数组5.1.1二维数组学生成绩单学生成绩可以用a[4]、b[4]、…组成，而这些数组又都有相同的数据类型数据的个数也相同5.1.1二维数组二维数组定义的一般形式为： 数据类型数组名[常量表达式1][常量表达式2];其中数据类型和数组名与一维数组的定义相同常量表达式1和常量表达式2分别表示二维数组的行、列的大小初始化同一维数组的初始化方法相同二维数组初始化时还可以采用分行赋值法。如： inta[3][4]={1,2,3,4,5,6,7,8,9,10,11,12};或： inta[3][4]={{1,2,3,4},{5,6,7,8},{9,10,11,12}};要对某个元素进行操作需提供两个下标值5.1.1二维数组二维数组是一个特殊的一维数组数组中，每个元素也是一个一维数组5.1.1二维数组采用顺序存储方法来表示数组，元素的个数及元素之间的次序关系不会变化，一般不做插入和删除操作。在C语言中，二维数组在内存中的存储顺序是先行（第一维）后列（第二维）a[5][6]在内存中的存放形式为：5.1.2多维数组多维数组定义格式如下： 数据类型数组名[常量表达式1][常量表达式2]...[常量表达式n]常量表达式m（m=1,2,...n）表示数组的多个下标长度在多维数组中，它的每一个元素也都具有相同的数据类型。多维数组是数组的数组在存储时，多维数组按维数由大至小的顺序，逐个元素连续存储。多维数组的数组名同样是该数组的第一个元素在内存中的起始地址。例如，定义三维数组如下： inta[10][10][10];如果每个整型数据在内存中占用4个字节那么该数组就需要10×10×10×4即4000字节的内存空间5.2稀疏矩阵稀疏矩阵：矩阵阶数很高，非零元素个数很少，零元素很多。例如：稀疏矩阵的存储稀疏矩阵的转置运算5.2.1稀疏矩阵的存储常用的稀疏矩阵的存储方法有：三元组顺序表行逻辑链接的顺序表十字链表。5.2.1稀疏矩阵的存储三元组顺序表矩阵的每个元素都可以用形如（i,j,value）这样的三元组来表示i,j分别表示行号和列号，value表示矩阵元素的值整个稀疏矩阵中表示非零元素的三元组按顺序（行优先）排列起来，再加上一个表示矩阵行数r、列数c和非零元素个数t的三元组（r,c,t）,就得到了一个唯一确定稀疏矩阵的三元组顺序表。例如图5-3中的稀疏矩阵的三元组顺序表如下： （（1，4，5），（2，3，3），（3，5，6），（4，1，2），（4，3，4），（5，6，7），（5，6，6））5.2.1稀疏矩阵的存储三元组顺序表三元组的定义如下：三元组顺序表的定义如下：5.2.1稀疏矩阵的存储三元组顺序表稀疏矩阵而言，三元组顺序表存储方法可节省大量存储空间5.2.1稀疏矩阵的存储十字链表每个非零元素用一个结点来表示，结点的结构是一个五元组（i,j,value,right,down）i,j是非零元素的行列号，value是非零元素的值,right是一个指向矩阵的同一行中下一个非零元素的指针,down是一个指向矩阵的同一列中下一个非零元素的指针；如图5-5所示：便于稀疏矩阵非零元素的插入与删除，较适用于稀疏矩阵的加法等运算。5.2.1稀疏矩阵的存储十字链表5.2.2稀疏矩阵的转置运算稀疏矩阵的转置运算对于一个r×c的矩阵A，其转置矩阵B是一个c×r的矩阵，且B[i][j]=A[j][i]，1≤i≤c,1≤j≤r。稀疏矩阵的转置矩阵示例：5.2.2稀疏矩阵的转置运算用三元组顺序表表示的稀疏矩阵的转置运算求矩阵A的转置矩阵B，就是将矩阵的行列数值进行互换，将A的三元组表中的每个三元组中的i和j的值互换，就得到了B的三元组表。但此时B的三元组表中三元组之间的顺序仍是按A中的行主序排