ch5数组和广义表(冲突STEVEN—PC2006—08—2517—10—14).pptVIP

第五章 数组和广义表;二、教学要求： 了解稀疏矩阵的三元组和十字链表存储结构和基本运算； 理解稀疏矩阵和特殊矩阵进行压缩存储的方法及下标变换； ????????理解广义表的基本概念，掌握广义表的特点及存储结构； 掌握数组的两种存储表示方法，特别是以行为主的存储结构中的地址计算方法； ;目 录;5.1 数组的定义和特点; 在C语言中，一个二维数组类型可以定义为其分量类型为一维数组类型的一维数组类型 typedef ElemType Array2[m][n]; 等价于 typedef ElemType Array1[n]; typedef Array1 Array2[m]; 如:Array2 A;//数组一旦被定义，它的维数和维界就不再改变。 二维的数组 = 定长的线性表 a11 a12 a13 ... a1n a21 a22 a23 ... a2n Amxn= ...... am1 am2 am3 ... amn Am*n= ((a11,a12,a13,...a1n),(a21,a22,a23,...a2n),...,(am1,am2,am3,...amn));数组的抽象数据类型;5.2 数组??顺序表示和实现;通常有两种顺序存储方式： 以行序为主序 以列序为主序; 无论规定行优先或列优先，只要知道以下三要素便可随时求出任一元素的地址（这样数组中的任一元素便可以随机存取！）：;数组的应用;5.3 矩阵的压缩存储;5.3.1 特殊矩阵 1.对称矩阵: aij = aji (1=i,j=n);对称矩阵顺序存储实例: 1 5 1 3 7 a00 5 0 8 0 0 a10 a 11 1 8 9 2 6 a20 a21 a23 3 0 2 5 1 ……………….. 7 0 6 1 3 an-1 0 a n-1 1 a n-1 2 …a n-1 n-1 在这个下三角矩阵中，元素总数为：n(n+1)/2 因此，我们可以按从上到下、从左到右访问对称矩阵A中的元素，若i≧j，则ai j在下三角形中。 ai j之前的i行一共有1+2+…+i=i(i-1)/2个元素，在第i行上， ai j之前恰有j-1个元素（即ai0,ai1,ai2,…,aij-1），因此有： k=i*(i-1)/2+j-1 ( 0≦kn(n+1)/2) 若ij，则aij是在上三角矩阵中。因为aij=aji，所以只要交换上述对应关系式中的i和j即可得到： k=j*(j-1)/2+i-1 ( 0≦ kn(n+1)/2 );2.下三角矩阵: 当ij时, aij = 0, (0=i,j=n-1);3.三对角矩阵: 当|i-j| 1时, aij = 0, (1=i,j=n);M由{(1,2,12), (1,3,9), (3,1,-3), (3,6,14), (4,3,24), (5,2,18), (6,1,15), (6,4,-7) } 和矩阵维数（6,7）唯一确定;稀疏矩阵的三元组线性表表示： 记录每个非零元素的行下标、列下标和元素值，这样稀疏矩阵中的每一个非零元素需要由一个三元组（i，j，ai，j）来唯一确定。记录稀疏矩阵中所有非零元素的三元组构成三元组线性表。;#define MAXSIZE 12500 //假设非零元个数的最大值 typedef struct{ int i,j; //非零元素行号/列号 ElemType e; //非零元素的值 }Triple; //三元组 typedef union{ Triple data[MAXSIZE+1]; //非零元三元组表,data[0]未用 int mu,nu,tu; //矩阵行数、列数、非零元个数 }TSMatrix;//稀疏矩阵类定义 ;稀疏矩阵转置算法思想;Status TransposeSMatrix(TSMatrix M, TSMatrix T){ T.mu=M.nu; T.nu=M.mu; T.tu=M.tu; //转置矩阵的列数,行数和非零元素个数 if (T.tu){ q=1; //矩阵T的指针 f