数组·稀疏矩阵的三种表示方法

1.数组的基本操作：

InitArray(&A,n,bound1,…,boundn) //构建n维数组A,构建成功则返回OK
DestroyArray(&A) //销毁数组
Value(A,&e,index1…,indexn); //将指定下标的元素赋给e,并返回OK 
Assign(&A,e,index1…,indexn); //将e赋给指定下标的元素，并返回OK 

2.稀疏矩阵的存储方式
①三元组

typedef struct{
	int i,j;//非零元的行下表和列下表 
	ElemType e;//存储元素e 
}Triple; //三元组的类型

typedef struct{
	Triple data[MAXSIZE+1];
	int mu,nu,tu;//矩阵的行数、列数和非零元个数 
}TSMtrix; //稀疏矩阵类型 

eg:求转置矩阵

Status TransopseSMatix(TSMatrix M,TSMatrix &T){
	T.mu=M.nu;T.nu=M.mu;T.tu=M.tu;
	if(T.tu){
		q=1;
		for(col=1;col<=M.nu;++col)
		for(p=1;p<=M.tu;++p)
		if(M.data[p].j==col){
			T.data[q].i=M.data[p].j;T.data[q].j=M.data[p].i;
			T.data[q].e=M.data[p].e;++q;
		}//if
	}//if 
}//TransposeSMatix 

②行逻辑联接的线性表

typedef struct{
	Triple data[MAXSIZE+1];
	int rpos[MAXRC+1];//各行第一个非零元的位置表
	int mu,nu,tu;//矩阵的行数、列数和非零元个数 
}RLSMatrix;

eg:矩阵相乘

Status MultSMatrix(RLSMatrix M,RLSMatrix N,RLSMatrix &Q){ //Q=M*N
	if(M.nu!=N.mu) return (ERROR);
	Q.mu=M.mu;Q.nu=N.nu;Q.tu=0;//Q初始化
	if(M.tu*N.tu) {//M、N为非零矩阵
	for(arow=1;arow<=M.mu;++arow){//处理M的每一行
	ctemp[]=0;//当前行各元素累加器清零
	Q.rpos[arow]=Q.tu+1;//每行第一个非零元素的位置（因为矩阵是一维数组存储结构，想象着横着一个长条条）
	if(arow<M.mu) tp=M.rops[arow+1];//下一行的第一个非零元 
	else  {tp=M.tu+1;}
	for(p=M.rops[arow];p<tp;++p){//对于每行第一个非零元
	brow=M.data[p].j;//该元在M中的列号，即对应N中的行号
	if(brow<N.mu) t=N.rops[brow+1];
	else {t=N.tu+1;}
	for(q=N.rops[brow];q<t;q++){
		ccol=N.data[q].j;//所得乘积元素在Q中的列号
		ctemp+=M.data[p].e*N.data[q].e; 
	}//for q
	}//for p 求得Q中第crow(=arow)行的非零元 
	for(cool=1;cool<Q.nu;++cool){ //压缩储存该行非零元 
		if(ctemp[cool]){
			if(++Q.tu>MAXSIZE) return (ERROR);
			Q.data[Q.tu]=(arow,ccol,ctep[cool]);
		}//if
	}//for cool 
	}//for arow 
	}//if
	return OK;
}//MultMatrix

③十字链表
稀疏矩阵的存储方式（只存储非零元素）中，前两种的顺序存储适合存储的结构不发生增缩的操作（eg：矩阵相乘、矩阵转置）；当结点被删除或者被添加（eg：矩阵相加时 2+（-2）=0删除结点），则应使用脸是储存；
十字链表中的结点中不仅有行号、列号、元素值，还有指向下一行的、下一列的非零元的两个指针。

typedef struct OLNode{
	int i,j;//非零元的行、列下标
	ElemType e;
	struct OLNode *right,*down;//该非零元所在行和列的非零后继结点 
}OLNode,*OLink;

typedef struct{
	OLink *rhead,*chead;//行和列链表头指针向量基址由CreateSMatrix分配
	int mu,nu,tu;//稀疏矩阵的行数、列数和非零元个数 
}CrossList;