欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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

程序员文章站 2024-02-02 18:27:52
...

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;