데이터 구조 - 희소 행렬 - 정적 분배 의 삼원 조 순서 저장
8885 단어 데이터 구조
압축 저장 의 개념 에 따라 희소 행렬 의 비 0 원 만 저장 합 니 다.따라서 0 원 이 아 닌 값 을 저장 하 는 것 외 에 줄 과 열 에 있 는 위치 (i, j) 를 동시에 몇 번 더 해 야 합 니 다.반대로
하나의 3 원 그룹 (i, j, aij) 은 행렬 A 의 0 원 이 아 닌 것 을 유일 하 게 확정 했다.따라서 희소 행렬 은 0 원 이 아 닌 3 원 조 와 그 행렬 수 에서 유일 하 게 확정 할 수 있다.
우선 보조 매크로 의 정의 입 니 다.
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define OVERFLOW -1
#define UNDERFLOW -2
#define MAXSIZE 12500 // 12500
#define MAXMN 12500// 12500희소 행렬 의 3 원 그룹 순서 표 저장 표시:
//
typedef struct{
int i,j; // 0
ElemType e;// 0
}Triple;//
typedef struct{
Triple data[MAXSIZE+1]; // ，data[0]
int rpos[MAXMN+1]; // 0
int mu,nu,tu;//
}RLSMatrix;// 희소 행렬 만 들 기 M.
Status CreateSMatrix(RLSMatrix &M){
// M
int i,j,a,flag=0;
M.tu=0;
scanf("%d %d",&M.mu,&M.nu);
if(M.mu<1||M.nu<1)
return ERROR;
for(i=1;i<=M.mu;i++){
M.rpos[i]=0;
for(j=1;j<=M.nu;j++){
scanf("%d",&a);
if(a!=0) {
M.tu++; //
if(!flag) {//flag==0 M.rpos flag 1
M.rpos[i]=M.tu;
flag=1;
}
M.data[M.tu].i=i;
M.data[M.tu].j=j;
M.data[M.tu].e=a;
}
}
flag=0;// flag 0
}
return OK;
}희소 행렬 제거 M.
Status DestroySMatrix(RLSMatrix &M){
// M
M.mu=0;
M.nu=0;
M.tu=0;
return OK;
}출력 희소 행렬 M.
void PrintRLSMatrix(RLSMatrix &M){
// M
int i,j,k=1;
if(!M.mu||!M.nu||!M.tu)
printf("
");
else{
for(i=1;i<=M.mu;i++){
for(j=1;j<=M.nu;j++){
if(M.data[k].i==i&&M.data[k].j==j) //
printf("%3d",M.data[k++].e);
else
printf(" 0");// 0
}
printf("
");
}
}
printf("
");
}희소 행렬 M 에서 T 를 복사 합 니 다.
Status CopySMatrix(RLSMatrix M,RLSMatrix &T){
// M T
T=M;
return OK;
}희소 행렬 Q = M + N.
Status AddSMatrix(RLSMatrix M,RLSMatrix N,RLSMatrix &Q){
// Q=M+N
if(M.mu!=N.mu||M.nu!=N.nu) //M N
return ERROR;
int i,j,k1=1,k2=1;//k1 M k2 N
Q.tu=0;
Q.mu=M.mu;
Q.nu=N.nu;
for(i=1;i<=M.mu;i++)
for(j=1;j<=M.nu;j++){
if(M.data[k1].i==i&&M.data[k1].j==j){// M
if(N.data[k2].i==i&&N.data[k2].j==j){// N
if(M.data[k1].e+N.data[k2].e){ // 0 Q.data
Q.tu++;
Q.data[Q.tu].i=i;
Q.data[Q.tu].j=j;
Q.data[Q.tu].e=M.data[k1].e+N.data[k2].e;
}
k1++; //
k2++;
}
else { //N 0
Q.tu++;
Q.data[Q.tu].i=i;
Q.data[Q.tu].j=j;
Q.data[Q.tu].e=M.data[k1++].e; //M Q,data
}
}
else if(N.data[k2].i==i&&N.data[k2].j==j){// N M 0
Q.tu++;
Q.data[Q.tu].i=i;
Q.data[Q.tu].j=j;
Q.data[Q.tu].e=N.data[k2++].e; //N Q,data
}
}
return OK;
}희소 행렬 의 차 를 구하 다 Q = M - N.
Status SubtMatrix(RLSMatrix M,RLSMatrix N,RLSMatrix &Q){
// Q=M-N
if(M.mu!=N.mu||M.nu!=N.nu)//
return ERROR;
int i,j,k1=1,k2=1;//k1 M k2 N
Q.tu=0;
Q.mu=M.mu;
Q.nu=N.nu;
for(i=1;i<=M.mu;i++)
for(j=1;j<=M.nu;j++){
if(M.data[k1].i==i&&M.data[k1].j==j){ // M
if(N.data[k2].i==i&&N.data[k2].j==j){// N
if(M.data[k1].e-N.data[k2].e){// 0 Q.data
Q.tu++;
Q.data[Q.tu].i=i;
Q.data[Q.tu].j=j;
Q.data[Q.tu].e=M.data[k1].e-N.data[k2].e;
}
k1++;//
k2++;
}
else{//N 0
Q.tu++;
Q.data[Q.tu].i=i;
Q.data[Q.tu].j=j;
Q.data[Q.tu].e=M.data[k1++].e; //M Q,data
}
}
else if(N.data[k2].i==i&&N.data[k2].j==j){// N M 0
Q.tu++;
Q.data[Q.tu].i=i;//N Q,data
Q.data[Q.tu].j=j;
Q.data[Q.tu].e=N.data[k2++].e*-1;
}
}
return OK;
}희소 행렬 의 전환 행렬 T 를 구하 십시오.
열 번호 col 은 1 에서 M. tu 로 M. data 를 스 캔 합 니 다. 모든 요 소 는 열 번호 가 j 와 같은 3 원 그룹 에 대해 줄 표 지 를 교환 한 후 T. data 에 순서대로 넣 습 니 다.
Status TransposeSMatrix(RLSMatrix M,RLSMatrix &T)
{
/* T
col 1 M.tu M.data j
， T.data */
T.mu=M.nu;
T.nu=M.mu;
T.tu=M.tu;
if(T.tu)//
{
int j,k=1,q=1;//q
for(j=1;j<=M.nu;j++)
for(k=1;k<=M.tu;k++)
if(M.data[k].j==j){// j M T.data i，j
T.data[q].e=M.data[k].e;
T.data[q].i=M.data[k].j;
T.data[q].j=M.data[k].i;
q++;
}
}
return OK;
}복잡 도 O (M. nu * M. tu) 는 희소 할 때 알고리즘 이 더욱 효과 적 입 니 다. 그렇지 않 으 면 최 악의 O (M. nu ^ 2 * M. mu) 입 니 다.
관건 적 인 이 유 는 여러 번 의 순서 표를 반복 해 야 하기 때 문 입 니 다. 먼저 한 번 옮 겨 다 니 며 A 의 요소 가 B 에 있어 야 할 위 치 를 구하 고 그 다음 에 바로 넣 을 수 있 습 니까?
희소 행렬 의 전환 행렬 T:
M 의 각 열의 0 이 아 닌 요소 의 개 수 를 배열 num M 의 첫 번 째 col 열 에 계산 하 는 첫 번 째 요 소 를 T 의 위치 cpot [col] 만족 cpot [col] = cpot [col - 1] + num [col - 1] cpot [1] = 1 로 확인 합 니 다. M 을 p 로 옮 겨 다 니 며 col 로 표 시 된 요 소 를 처음 만 났 습 니 다.
Status FastTransposeSMatrix(RLSMatrix M,RLSMatrix &T)
{
/* T
M num
M col T cpot[col] cpot[col]=cpot[col-1]+num[col-1] cpot[1]=1
p M col T cpot[col] cpot[col] clo cpot[col]*/
T.mu=M.nu;
T.nu=M.mu;
T.tu=M.tu;
if(T.tu){//
int col,t,q;//col t
int * num=(int *)malloc((M.nu+1)*sizeof(int));//0
if(!num) //
exit(OVERFLOW);
for(col=1;col<=M.nu;col++)
num[col]=0; //num 0
for(t=1;t<=M.tu;t++)
num[M.data[t].j]++;
int * cpot=(int *)malloc((M.nu+1)*sizeof(int));
if(!cpot)//
exit(OVERFLOW);
cpot[1]=1;//M 1 T
for(col=2;col<=M.nu;col++)
cpot[col]=cpot[col-1]+num[col-1];
for(t=1;t<=M.tu;t++) {
col=M.data[t].j;//
q=cpot[col];//
T.data[q].e=M.data[t].e;
T.data[q].j=M.data[t].i;
T.data[q].i=M.data[t].j;
cpot[col]++;//
}
free(num);//
free(cpot);
num=NULL;
cpot=NULL;
}
return OK;
}복잡 도: O (M. nu + M. tu) 공간 이 num [M. nu + 1] 많아 졌 습 니 다. cpot[M.nu+1] ,O(M.nu)
아래 에 표 시 된 요소 의 지정 값 을 지정 합 니 다:
ElemType Value(RLSMatrix M,int r,int c){
//
int k=M.rpos[r]; //r
while(M.data[k].j희소 행렬 곱 하기 Q = M * N 을 구하 세 요.
M 의 현재 줄 을 옮 겨 다 니 는 것 은 0 원 M. data [rpos [Mrow] 가 아 닙 니 다. rpos [Mrow + 1] - 1], j 열 을 옮 겨 다 니 는 N. data [rpos [j].. rpos [j + 1] - 1], 좌 표를 [j] [col] 로 설정 하여 M. data [Mrow] [j] * N. data [j] [col] 를 Qtemp [col] 로 누적 합 니 다.
Status MultSMatrix(RLSMatrix M,RLSMatrix N,RLSMatrix &Q){
// Q=M*N
if(M.nu!=N.mu) //M N
return ERROR;
Q.mu=M.mu;//Q
Q.nu=N.nu;
Q.tu=0;
int *ctrmp=(int *)malloc((N.nu+1)*sizeof(int));
if(!ctrmp) //
exit(OVERFLOW);
if(M.tu*N.tu!=0) {//Q
int arow,blow,tp,p,t,q,i,ccol,j;
for(arow=1;arow<=M.mu;arow++){//
for(i=1;i<=N.nu;i++)
ctrmp[i]=0;//Q
Q.rpos[arow]=Q.tu+1; //Q rpos
for(j=arow;jMAXSIZE)
return ERROR; //
Q.data[Q.tu].e=ctrmp[ccol];
Q.data[Q.tu].i=arow;
Q.data[Q.tu].j=ccol;
}
}//for arow
}//if
return OK;
} 이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
정수 반전Udemy 에서 공부 한 것을 중얼거린다 Chapter3【Integer Reversal】 (예) 문자열로 숫자를 반전 (toString, split, reverse, join) 인수의 수치 (n)가 0보다 위 또는 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
