第四章 数组、串和广义表

1.三元组表表示法3
（1）建立稀疏矩阵的三元组表2 算法分析： 建立并输出稀疏矩阵的三元组表，首先要给出三元组表的类型定义，然 后编写建立函数和输出函数，最后在主程序中调用，见算法4-1。程序 第00-16行为建立函数，程序先定义了三元组变量M，再通过键盘输入 稀疏矩阵的信息：行数、列数、非零元个数，由程序第04-09行完成。 程序第10行的for语句循环M.tu次，输入每个非零元的信息，填入到相 应的三元组的对应域中，即完成三元组表的建立。 输出函数（程序第17-24行）则按每行输出一个三元组的形式输出三元 组的信息。 主程序（程序第25-30行）通过调用建立函数和输出函数完成三元组表 的建立于输出。
8 a32
a03 a13 a23 a33
9 a33
4.1.3 特殊矩阵压缩存储
1.对称矩阵2
对称矩阵中任意元素与其对应的一维数组下标k的计算公式：
(i+1)*i/2+j k= (j+1)*j/2+i
(i>=j) (i<j)
4.1.3 特殊矩阵压缩存储2
2.三角矩阵
n阶方阵，沿主对角线以上的元素全为零。 上三角矩阵、下三角矩阵
三元组表中（程序第13-15行）。这样就将M中的第i列的非零元
转置到了T中的第i行，并且能保证T的三元组表是按行序存放。
算法4-2 稀疏矩阵的转置算法
00 SMatrix TransMatrix(SMatrix M) /* 稀疏矩阵M的转置算法 */ 01 { 02 SMatrix T; 03 int i,j,k; 04 T.mu=M.nu; /* 稀疏矩阵M的列数作为T的行数 */ 05 T.nu=M.mu; /* 稀疏矩阵M的行数作为T的列数 */ 06 T.tu=M.tu; /* 稀疏矩阵M的非零元个数作为T的非零元个数 */ 07 if(T.tu>0) 08 { 09 k=0; 10 for(i=0;i<M.nu;i++) /* M有nu列，要扫描nu趟 */ 11 for(j=0;j<M.tu;j++) /* 对M中的每个三元组扫描 */ 12 if(M.data[j].col==i) 13 { 14 T.data[k].row=M.data[j].col; 15 T.data[k].col=M.data[j].row; 16 T.data[k].value=M.data[j].value; 17 k++; 18 } 19 } 20 return T; 21 }
1.三元组表表示法4
（2）稀疏矩阵的转置 第一种方法：
假设稀疏矩阵M有n列，转置后的稀疏矩阵为T。需要对M的 三元组表进行n趟扫描，第i（0≤i≤n-1）趟扫描将M中所有col值 为i的三元组存放到T的三元组表中，具体方法是：取出该三元组， 交换row值和col值，连同value值，作为新的三元组存放到T的
算法4-3 稀疏矩阵的快速转置算法1
00 SMatrix FastTransMatrix(SMatrix M) /* 稀疏矩阵M的快速转置算法 */ 01 { 02 SMatrix T; 03 int rowsize[MAXSIZE]; 04 int rowstart[MAXSIZE]; 05 int i,j,k; 06 T.mu=M.nu; /* 稀疏矩阵M的列数作为T的行数 */ 07 T.nu=M.mu; /* 稀疏矩阵M的行数作为T的列数 */ 08 T.tu=M.tu; /* 稀疏矩阵M的非零元个数作为T的非零元个数 */ 09 if(T.tu>0) 10 { 11 for(j=0;j<M.nu;j++) /* 设rowsize的初值全为0 */ 12 rowsize[j]=0; 13 for(i=0;i<M.tu;i++) /* 求M中每一列非零元素个数 */ 14 { 15 j=M.data[i].col; 16 rowsize[j]=rowsize[j]+1; 17 } 18 printf("\nrowsize[]:"); 19 for(i=0;i<M.nu;i++) /* 打印输出rowsize变量 */ 20 printf("%d ",rowsize[i]); 21 printf("\n");
a 02 a12 a 22
a 03 a13 a 23
4.1.2 矩阵的顺序表示与实现
行序优先存储：
a00 a01 a02 a03 a10 a11 a12 a13 a20 a21 a22 a23
Loc(aij) = Loc(a00) +（i*n+j）* length
列序优先存储：
称为三元组。
下标 0
row 0 0 1 2 3 4
col 1 5 0 4 2 4
value 5 7 8 -9 12 4ຫໍສະໝຸດ rowcolvalue
1 2 3 4 5
1.三元组表表示法2
用C语言定义三元组表的结构类型如下： 00 01 02 03 04 05 06 07 08 09 10 11 typedef int DataType; /* 假设稀疏矩阵的元素类型为整型 */ #define MAXSIZE 100 /* 非零元个数的最大值 */ typedef struct /* 定义三元组结点类型 */ { int row,col; /* 非零元所在的行下标,列下标 */ DataType value; /* 非零元素值 */ }Triple; typedef struct /* 定义三元组表结构类型SMatrix */ { Triple data[MAXSIZE+1]; /* 非零元组成的三元组表 */ int mu,nu,tu; /* 稀疏矩阵的行数、列数和非零元个数 */ }SMatrix;
7 a23
0 0 a 23 a33
8 a32 9 a33
a22
4.1.3 特殊矩阵压缩存储3
3.对角矩阵2
按行序压缩存储三对角矩阵，元素下标（i，j）与对应的一维
数组下标k映射公式为：
k=3*i-1+(j-i+1)=2*i+j
4.1.4 稀疏矩阵压缩存储
稀疏矩阵是指矩阵中的非零元很少，大部分是零元素，且
第四章 数组、串和广义表
学习要点：
数组（二维数组）基本概念与存储方式，基于某些特殊矩阵
的典型算法。
串的基本概念和基本操作，串的存储方式和典型算法。 广义表基本概念和相关概念，广义表的存储与基本操作实现。
§4.1 数组
数组（array）表示n（n>1）个具有相
同数据类型的数据元素的有序集合。
1.三元组表表示法3
（1）建立稀疏矩阵的三元组表1 算法4-1 建立并输出稀疏矩阵的三元组表 00 SMatrix CreateSMatrix() /* 创建稀疏矩阵M */ 01 { 02 SMatrix M; 03 int i; 04 printf("\n请输入矩阵的行数："); 05 scanf("%d",&M.mu); 06 printf("\n请输入矩阵的列数："); 07 scanf("%d",&M.nu); 08 printf("\n请输入矩阵的非零元素个数："); 09 scanf("%d",&M.tu); 10 for(i = 0; i < M.tu; i++) 11 { 12 printf("请按行序顺序输入第%d个非零元素所在的行(0～%d)," "列(0～%d),元素值：(逗号分隔)\n", i,M.mu-1,M.nu-1); 13 scanf("%d,%d,%d",&M.data[i].row,&M.data[i].col,&M.data[i].value); 14 } 15 return M; 16 }
4.1.1二维数组
数组中数据元素由一个数据值和一个（组）下标确定。下
标是数组中元素相互区分的标识。使用一个下标区分其中
元素的数组称为一维数组。使用两个以上下标的数组称为 多维数组。常用的多维数组是二维数组，通常称为矩阵。
A3*4的阵列形式表示：
a 00 a 10 a 20
a 01 a11 a 21
a00 a10 a20 a01 a11 a21 a02 a12 a22 a03 a13 a23
Loc(aij) = Loc(a00) +（j*m+i）* length
4.1.3 特殊矩阵压缩存储
1.对称矩阵
n阶方阵，沿主对角线对称位置上的元素相等，即aij=aji。 主对角线：由元素aii组成的数列
8 a32
0 0 0 a33
9 a33
4.1.3 特殊矩阵压缩存储2
2.三角矩阵2
按行序压缩存储下三角矩阵，元素下标（i，j）与对应的一维数组下
标k映射公式为：
k=(i+1)*i/2+j
(i>=j)
4.1.3 特殊矩阵压缩存储3
3.对角矩阵
n阶方阵，沿主对角线上下若干对角线上有非零元素，其他全为零。 带宽：主对角线上下各d条对角线上有非零元，则共有2d+1条对角线
a 00 a 如右图为3对角矩阵。 10 按行序压缩存储3对角矩阵，映射到一维 0 数组中去，其对应的一维数组下标如下图 0
所示：
下标 k： aij： 0 a00 1 a01 2 a10 3 a11 4 a12 5 a21 6
有非零元，称为带宽。