疎マトリクスの三元グループシーケンステーブル記憶構造の表示と実現
#define MAX_SIZE 100
struct Triple
{
int i, j;// ，
ElemType e;//
};
struct TSMatrix
{
Triple data[MAX_SIZE + 1];// ，data[0]
int mu, nu, tu;// ， ，
};
int comp(int c1, int c2){// c1 c2
if (c1 < c2)
return -1;
if (c1 == c2)
return 0;
return 1;
}
Status CreateSMatrix(TSMatrix &M){// M
int i;
Triple T;
Status k;
printf(" ， ， ：");
scanf("%d,%d,%d", &M.mu, &M.nu, &M.tu);
if (M.tu > MAX_SIZE)//
return ERROR;
M.data[0].i = 0;//
for (i = 1; i <= M.tu; i++)// M.tu
{
do{
printf(" %d （1~%d）， （1~%d）， ：", i, M.mu, M.nu);
scanf("%d,%d,%d", &T.i, &T.j, &T.e);
k = 0;//
if (T.i < 1 || T.i > M.mu || T.j < 1 || T.j > M.nu)//
k = 1;
if (T.i < M.data[i - 1].i || T.i == M.data[i - 1].i && T.j <= M.data[i - 1].j)
k = 1;//
} while (k);//
M.data[i] = T;// M
}
return OK;
}
Status AddSMatrix(TSMatrix M, TSMatrix N, TSMatrix &Q){// Q = M + N
int m = 1, n = 1, q = 0;
if (M.mu != N.mu || M.nu != N.nu)//M,N
return ERROR;
Q.mu = M.mu;// Q
Q.nu = M.nu;
while (m <= M.tu && n <= N.tu)// M N
{
switch (comp(M.data[m].i, N.data[n].i))//
{
case -1:Q.data[++q] = M.data[m++];// M ， M Q
break;
case 0:switch (comp(M.data[m].j, N.data[n].j))//M,N ，
{
case -1:Q.data[++q] = M.data[m++];// M ， M Q
break;
case 0:Q.data[++q] = M.data[m++];//M,N ， Q
Q.data[q].e += N.data[n++].e;
if (Q.data[q].e == 0)// 0，
q--;
break;
case 1:Q.data[++q] = N.data[n++];// N ， N Q
break;
}
break;
case 1:Q.data[++q] = N.data[n++];// N ， N Q
}
}// 2 1
while (m <= M.tu)// N ， M
Q.data[++q] = M.data[m++];
while (n <= N.tu)// M ， N
Q.data[++q] = N.data[n++];
if (q > MAX_SIZE)//
return ERROR;
Q.tu = q;// Q
return OK;
}
void TransposeSMatrix(TSMatrix M, TSMatrix &T){// M T
int p, col, q = 1;//q T ， 1
T.mu = M.nu;// T = M
T.nu = M.mu;// T = M
T.tu = M.tu;// T = M
if (T.tu)//
{
for (col = 1; col <= M.nu; ++col)// T 1
{
for (p= 1; p <= M.tu; ++p)// M
{
if (M.data[p].j == col)// = T
{
T.data[q].i = M.data[p].j;// M T
T.data[q].j = M.data[p].i;
T.data[q++].e = M.data[p].e;// T +1
}
}
}
}
}
Status MultSMatrix(TSMatrix M, TSMatrix N, TSMatrix &Q){// Q = M * N
int i, j, q, p;
ElemType Qs;// Q[i][j]
TSMatrix T;//N
if (M.nu != N.mu)// M N
return ERROR;
Q.mu = M.mu;//Q = M
Q.nu = N.nu;//Q = M
Q.tu = 0;//Q 0
TransposeSMatrix(N, T);//T N
for (i = 1; i <= Q.mu; i++)// M ， Q[i][]
{
q = 1;//q M 1
for (j = 0; j <= T.mu; j ++)// T （ N ）， Q[i][j]
{
Qs = 0;// Q[i][j] 0
p = 1;//p M 1
while (M.data[p].i < i)// p M i 1
p++;
while (T.data[q].i < j)// q T j （ N j ）
q++;
while (p <= M.tu && q <= T.tu && M.data[p].i == i && T.data[q].i == j)
{//[p] M i [q] T j （ N j ）
switch (comp(M.data[p].j, T.data[q].i))// M T （ N ）
{
case -1:p++;//M
break;
case 0:Qs += M.data[p++].e * T.data[q++].e;//M = T(N) （ ） ， Qs,p、q
break;
case 1:q++;//M >T(N) （ ） ，q
}
if (Qs)//Q[i][j] 0
{
if (++Q.tu > MAX_SIZE)//Q +1.
return ERROR;
Q.data[Q.tu].i = i;// Q[i][j] Q
Q.data[Q.tu].j = j;
Q.data[Q.tu].e = Qs;
}
}
}
}
return OK;
}
void DestroySMatrix(TSMatrix &M){// M
M.mu = M.nu = M.tu = 0;
}
void PrintSMatrix(TSMatrix M){// M
int i, j, k = 1;// ， 1
Triple * p = M.data + 1;//p M 1
for (i = 1; i <= M.mu; i++)// 1
{
for (j = 1; j <= M.nu; j++)// 1
{
if (k <= M.tu && p->i == i && p->j == i)//p ， p
{
printf("%3d", (p++)->e);// p ，p
k++;// +1
}
else//p
printf("%3d", 0);// 0
}
printf("
");
}
}
void CopySMatrix(TSMatrix M, TSMatrix &T){// M T
T = M;
}
Status SubtSMatrix(TSMatrix M, TSMatrix N, TSMatrix &Q){// Q = M - N
int i;
if (M.mu != N.nu || M.nu != N.nu)//M,N
return ERROR;
for (i = 1; i <= N.tu; ++i)// N ， -1
N.data[i].e *= -1;
AddSMatrix(M, N, Q);//Q = M + (- N)
return OK;
}
void FastTransposeSMatrix(TSMatrix M, TSMatrix &T){// M T
int p, q, col, *num, *cpot;
num = (int *)malloc((M.nu + 1) * sizeof(int));// M （T ） （[0] ）
cpot = (int *)malloc((M.nu + 1) * sizeof(int));// T （[0] ）
T.mu = M.nu;//T = M
T.nu = M.mu;//T = M
T.tu = M.tu;//T = M
if (T.tu)//T
{
for (col = 1; col <= M.nu; ++col)// M 1
num[col] = 0;// 0
for (p = 1; p <= M.tu; ++p)// M
++num[M.data[p].j];//
cpot[1] = 1;//T 1 1 T.data 1
for (col = 2; col <= M.nu; ++col)// M（T） 2 （ ） （ ）
cpot[col] = cpot[col - 1] + num[col - 1];// T col 1 T.data
for (p = 1; p <= M.tu; ++p)// M
{
col = M.data[p].j;// M col
q = cpot[col];//q M T
T.data[q].i = M.data[p].j;// M T
T.data[q].j = M.data[p].i;
T.data[q].e = M.data[p].e;
++cpot[col];//T col 1 T.data 1
}
}
free(num);// num cpot
free(cpot);
}