内容提要
? 2.1 数组的定义
? 2.2 数组的顺序表示与实现
? 2.3 距阵的压缩存储
2.1 数组
? 数组：相同类型数据的有序集合。是数据结构中最
基本的结构类型
? 数组的操作：
通过给定下标取出相应元素的值
通过给定下标修改相应元素的值
数组只有顺序存储结构，多维数组实际
上也是按照一维数组存放的
二维数组 a[N][M]中每个单元占有 L个字节，那么 a[i][j]
的存储位置：
Loc(aij)=Loc(a00)+(i*M+j)*L
三维数组 a[P][N][M]中每单元占 L个字节，那么 a[i][j][k]
的存储位置：
Loc(aijk)=Loc(a000)+(i*N*M+j*M+k)*L
n维数组的
a[k1][k2]..[kn]
的存储位置
如何求？
2.2 数组的顺序表示与实现
? 数组的顺序表示
//---------数组的顺序存储表示 -----------
#include <stdarg.h> // 标准头文件,提供宏 va_start,va_arg
// 和 va_end，用于存取变长参数表
#define MAX_ARRAY_DIM 8 // 假设数组维数的最大值为 8
typedefstruct {
ElemType *base; // 数组元素基址，由 InitArray分配
int dim; // 数组维数
int *bounds; // 数组维界基址，由 InitArray分配
int *constants; // 数组映象函数常量基址，
// 由 InitArray分配
}Array;
? 数组的顺序实现（见书 P93）
2.3 距阵的压缩存储
利用数组压缩存储矩阵
可以压缩存储的矩阵有两种：
1、特殊矩阵
(1)三角矩阵
(2)对称矩阵
(3)带状矩阵
2、稀疏矩阵
N?M个单元中，只有 T个非
零元素，当 T/(N ? M)<=0.05时，
就是稀疏矩阵。
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
a00
a10 a11 C
a20 a21 a22
a30 a31 a32 a33
下三角矩阵
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
a00 a10 a20 a30
a10 a11 a21 a31
a20 a21 a22 a32
a30 a31 a32 a33
对称矩阵
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
a00 a01
a10 a11 a12
a21 a22 a23
a32 a33
带状矩阵
距阵的压缩存储 (cont’d)
(1)三角矩阵的压缩存储
只需要将矩阵中的三角区域的数据按照顺序存放
到一维数组中即可，关键的问题是确定矩阵的两个
下标 [i][j]与一维数组的下标 [k]的对应关系：
以上三角矩阵为例,A[i][j](j>=i)前面的元素个数
是：
N+N-1+N-2+…+N -i+1=i*(2N-i+1)/2
在本行前面有 j-i个元素，因此，在一维数组中，
A[i][j]的位置,k= i*(2N-i+1)/2+j-i
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
a00 a01 a02 a03
a11 a12 a13
a22 a23
a33
a00 a01 a02 a03 a11 a12 a13 a22 a23 a33
距阵的压缩存储 (cont’d)
(2)对称矩阵的压缩存储
可以采用三角矩阵的方式
(3)带状矩阵的压缩存储
只需将非零元素存放在一维数组中，矩阵
下标 [i][j]与一维数组下标 k的对应关系：
k=i*3-1+j-(i-1)=2*i+j
a00 a01 a10 a11 a12 a21 a22 a23 a32 a33
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
a00 a01
a10 a11 a12
a21 a22 a23
a32 a33
带状矩阵
距阵的压缩存储 (cont’d)
(4)稀疏矩阵的压缩存储
① 顺序存储, 三元组的顺序表
三元组＝ (行,列,值 )
数据类型定义：
#define N 500
typedef struct
{ int i,j; //行列下标
Elemtype e; //非零值
}Triple;
typedef struct {
Triple data[N];
int mu,nu,tu; //矩阵的行数、列数和非零值的个数
}Matrix;
三元组数组存放的稀疏矩阵转置算法
转置操作,即将 A[i][j]改成 A[j][i],将 N?M矩阵
改成 M ? N矩阵。
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
0 12 9 0 0 0 0
0 0 0 0 0 0 0
-3 0 0 0 0 14 0
0 0 24 0 0 0 0
0 18 0 0 0 0 0
15 0 0 -7 0 0 0 ?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
0 0 -3 0 0 15
12 0 0 0 18 0
9 0 0 24 0 0
0 0 0 0 0 -7
0 0 0 0 0 0
0 14 0 0 0 0
0 0 0 0 0 0
距阵的压缩存储 (cont’d)
三元组数组存放的稀疏矩阵转置算法
算法思想,
(1)扫描整个三元组数组，将每个三元组的 i和 j
互换。
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
0 12 9 0 0 0 0
0 0 0 0 0 0 0
-3 0 0 0 0 14 0
0 0 24 0 0 0 0
0 18 0 0 0 0 0
15 0 0 -7 0 0 0
0,1,12
0,2,9
2,0,-3
2,5,14
3,2,24
4,1,18
5,0,15
5,3,-7
1,0,12
2,0,9
0,2,-3
5,2,14
2,3,24
1,4,18
0,5,15
3,5,-7
距阵的压缩存储 (cont’d)
算法思想,
(2) 原来的三元组数组是按照行序存放的,ij互
换后也要调整称为行序存放的方式。这需要事
先指导转置后每行非零元素的个数，也就是原
矩阵每列非零元素的个数。通过单独扫描一次
整个三元组数组，就可以计算得到这些数据。
有了这些数据，就可以确定转置后的矩阵的每
行的非零元素在数组中的位置。
三元组数组存放的稀疏矩阵转置算法
0,1,12
0,2,9
2,0,-3
2,5,14
3,2,24
4,1,18
5,0,15
5,3,-7
num[i] 2 2 2 1 0 1 0
rpos[i] 0 2 4 6 7 7 8
0 1 2 3 4 5 6
距阵的压缩存储 (cont’d)
三元组数组存放的稀疏矩阵转置算法
#define N 50 //行数和列数的最大值
void transmatrix(MATRIX M,MATRIX *T)
{ int num[N]={0},rpos[N],p,q,col;
//计算转置后矩阵的各行的非零元素的个数
for(p=0;p<M.tu;p++)num[M.data[p].j]++;
rpos[0]=0; //开始计算各行非零元素在数组中的起始位置
for(col=1;col<M.nu;col++)
rpos[col]=rpos[col-1]+num[col-1];
T->mu=M.nu; T->nu=M.mu; T->tu=M.tu;
for(p=0;p<M.tu;p++)
{ col=M.data[p].j;
q=rpos[col]; //q成为该单元在转置矩阵数组中的下标
T->data[q].i=M.data[p].j; //开始转置行列号
T->data[q].j=M.data[p].i;
T->data[q].e=M.data[p].e; //复制非零元素的值
rpos[col]++; /*修正改行非零元素在三元数组中
下标，为存放下一个改行的非零元
素作准备 */
}//for
}
距阵的压缩存储 (cont’d)
(4)稀疏矩阵的压缩存储
② 十字链表, 三元组的双链表，结点不但包含三元组，而
且还包含两个指针，一个称为行链指针，指向下一个同行的非
零元素；另一个称为列链指针，指向下一个同列的非零元素。
同一个结点，同时链到行链和列链上。
0 0 30
1
2
0 1 2 3
1 1 -1
2 0 2
0 3 5
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
3 0 0 5
0 -1 0 0
2 0 0 0
rhead
chead
距阵的压缩存储 (cont’d)
(4) 稀疏矩阵的压缩存储
十字链表的数据类型定义,
typedef struct olnode {
int i,j; // 该非零元的行和列下标
int e;
struct olnode *right,*down; // 该非零元所在行表
和列表的后继链域
}Olnode,*Olnodeptr;
typedef struct {
Olnodeptr *rhead,*chead; // 行和列链表头指针向量基
址由 CreateSMatrix分配
int mu,nu,tu; //稀疏距镇的行数、列数和非零元个数
}Crosslist;
十字链表的创建算法
void createSMatrix(Crosslist *M)
{int m,n,t,i,j,e; Olnodeptr p,q;
printf("请输入矩阵的行数、列数和非零元总数 \n");
scanf("%d%d%d",&m,&n,&t);
M?mu=m; M?nu=n; M?tu=t;
//开始为行链和列链的头指针分配空间
M?rhead=(Olnodeptr)malloc(m,sizeof(Olnodeptr));
M?chead=(Olnodeptr)malloc(n,sizeof(Olnodeptr));
for(i=0;i<m;i++)M?rhead[i]=NULL;
for(i=0;i<n;i++)M?chead[i]=NULL;
scanf("%d%d%d",&i,&j,&e); //没有处理非法数据
while(i!=-1) //如果 i是－ 1，表示输入结束
{p=(Olnodeptr)malloc(sizeof(Olnode));
p?i=i; p?j=j; p?e=e;
十字链表的创建算法
//下面将 p按序插入行链
if(M?rhead[i]==NULL) //行链空，直接插入
{M?rhead[i]=p;p?right=NULL;}
else
{if(j<M?rhead[i]?j)
{p?right=M?rhead[i]; M?rhead[i]=p;}
else
{for(q=M?rhead[i];q?right&&q?right?j<j;q=q?right);
p?right=q?right; q?right=p; //插到 q的后面
} //else 寻找插入位置
} //else 行链不空
十字链表的创建算法
//下面将 p按序插入列链
if(M?chead[j]==NULL) //列链空，直接插入
{M?chead[j]=p;p?down=NULL;}
else
{if(i<M?chead[j]?i)
{p?down=M?chead[j]; M?chead[j]=p;}
else
{for(q=M?chead[j];q?down&&q?down?i<i;
q=q?down);
p?down=q?down; q?down=p; //插到 q的后面
}//else 寻找插入位置
}//else 列链不空
}//while
}
,数据结构,
数组