稀疏矩阵的三种表示方法·转置矩阵·矩阵相乘·十字链表表示法·数组的基本操作

怼烎@ 2023-07-13 04:25 21阅读 0赞

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;