数据结构C语言版 稀疏矩阵的三元组顺序表存储表示和实现.docx

数据结构C语言版 稀疏矩阵的三元组顺序表存储表示和实现.docx

《数据结构C语言版 稀疏矩阵的三元组顺序表存储表示和实现.docx》由会员分享，可在线阅读，更多相关《数据结构C语言版 稀疏矩阵的三元组顺序表存储表示和实现.docx（9页珍藏版）》请在冰点文库上搜索。

typedefintElemType;

//稀疏矩阵的三元组顺序表存储表示

#defineMAXSIZE100//非零元个数的最大值

typedefstruct

{

inti,j;//行下标,列下标

ElemTypee;//非零元素值

}Triple;

typedefstruct

{

Tripledata[MAXSIZE+1];//非零元三元组表,data[0]未用

intmu,nu,tu;//矩阵的行数、列数和非零元个数

}TSMatrix;

//创建稀疏矩阵M

intCreateSMatrix（TSMatrix*M）

{

inti,m,n;

ElemTypee;

intk;

printf（"请输入矩阵的行数,列数,非零元素个数：

（逗号）\n"）;

scanf（"%d,%d,%d",&（*M）.mu,&（*M）.nu,&（*M）.tu）;

（*M）.data[0].i=0;//为以下比较顺序做准备

for（i=1;i<=（*M）.tu;i++）

{

do

{

printf（"请按行序顺序输入第%d个非零元素所在的行（1～%d）,"

"列（1～%d）,元素值：

（逗号）\n",i,（*M）.mu,（*M）.nu）;

scanf（"%d,%d,%d",&m,&n,&e）;

k=0;

//行或列超出范围

if（m<1||m>（*M）.mu||n<1||n>（*M）.nu）

k=1;

if（m<（*M）.data[i-1].i||m==（*M）.data[i-1].i

&&n<=（*M）.data[i-1].j）//行或列的顺序有错

k=1;

}while（k）;

（*M）.data[i].i=m;//行下标

（*M）.data[i].j=n;//列下标

（*M）.data[i].e=e;//该下标所对应的值

}

return1;

}

//销毁稀疏矩阵M，所有元素置空

voidDestroySMatrix（TSMatrix*M）

{

（*M）.mu=0;

（*M）.nu=0;

（*M）.tu=0;

}

//输出稀疏矩阵M

voidPrintSMatrix（TSMatrixM）

{

inti;

printf（"\n%d行%d列%d个非零元素。

\n",M.mu,M.nu,M.tu）;

printf（"%4s%4s%8s\n","行","列","元素值"）;

for（i=1;i<=M.tu;i++）

printf（"%4d%4d%8d\n",M.data[i].i,M.data[i].j,M.data[i].e）;

}

//由稀疏矩阵M复制得到T

intCopySMatrix（TSMatrixM,TSMatrix*T）

{

（*T）=M;

return1;

}

//AddSMatrix函数要用到

intcomp（intc1,intc2）

{

inti;

if（c1

i=1;

elseif（c1==c2）

i=0;

else

i=-1;

returni;

}

//求稀疏矩阵的和Q=M+N

intAddSMatrix（TSMatrixM,TSMatrixN,TSMatrix*Q）

{

Triple*Mp,*Me,*Np,*Ne,*Qh,*Qe;

if（M.mu!

=N.mu）

return0;

if（M.nu!

=N.nu）

return0;

（*Q）.mu=M.mu;

（*Q）.nu=M.nu;

Mp=&M.data[1];//Mp的初值指向矩阵M的非零元素首地址

Np=&N.data[1];//Np的初值指向矩阵N的非零元素首地址

Me=&M.data[M.tu];//Me指向矩阵M的非零元素尾地址

Ne=&N.data[N.tu];//Ne指向矩阵N的非零元素尾地址

Qh=Qe=（*Q）.data;//Qh、Qe的初值指向矩阵Q的非零元素首地址的前一地址

while（Mp<=Me&&Np<=Ne）

{

Qe++;

switch（comp（Mp->i,Np->i））

{

case1:

*Qe=*Mp;

Mp++;

break;

case0:

//M、N矩阵当前非零元素的行相等,继续比较列

switch（comp（Mp->j,Np->j））

{

case1:

*Qe=*Mp;

Mp++;

break;

case0:

*Qe=*Mp;

Qe->e+=Np->e;

if（!

Qe->e）//元素值为0，不存入压缩矩阵

Qe--;

Mp++;

Np++;

break;

case-1:

*Qe=*Np;

Np++;

}

break;

case-1:

*Qe=*Np;

Np++;

}

}

if（Mp>Me）//矩阵M的元素全部处理完毕

while（Np<=Ne）

{

Qe++;

*Qe=*Np;

Np++;

}

if（Np>Ne）//矩阵N的元素全部处理完毕

while（Mp<=Me）

{

Qe++;

*Qe=*Mp;

Mp++;

}

（*Q）.tu=Qe-Qh;//矩阵Q的非零元素个数

return1;

}

//求稀疏矩阵的差Q=M-N

intSubtSMatrix（TSMatrixM,TSMatrixN,TSMatrix*Q）

{

inti;

for（i=1;i<=N.tu;i++）

N.data[i].e*=-1;

AddSMatrix（M,N,Q）;

return1;

}

//求稀疏矩阵的乘积Q=M*N

intMultSMatrix（TSMatrixM,TSMatrixN,TSMatrix*Q）

{

inti,j,h=M.mu,l=N.nu,Qn=0;

//h,l分别为矩阵Q的行、列值,Qn为矩阵Q的非零元素个数，初值为0

ElemType*Qe;

if（M.nu!

=N.mu）

return0;

（*Q）.mu=M.mu;

（*Q）.nu=N.nu;

Qe=（ElemType*）malloc（h*l*sizeof（ElemType））;//Qe为矩阵Q的临时数组

//矩阵Q的第i行j列的元素值存于*（Qe+（i-1）*l+j-1）中，初值为0

for（i=0;i

*（Qe+i）=0;//赋初值0

for（i=1;i<=M.tu;i++）//矩阵元素相乘，结果累加到Qe

for（j=1;j<=N.tu;j++）

if（M.data[i].j==N.data[j].i）

*（Qe+（M.data[i].i-1）*l+N.data[j].j-1）+=

M.data[i].e*N.data[j].e;

for（i=1;i<=M.mu;i++）

for（j=1;j<=N.nu;j++）

if（*（Qe+（i-1）*l+j-1）!

=0）

{

Qn++;

（*Q）.data[Qn].e=*（Qe+（i-1）*l+j-1）;

（*Q）.data[Qn].i=i;

（*Q）.data[Qn].j=j;

}

free（Qe）;

（*Q）.tu=Qn;

return1;

}

//算法5.1P99

//求稀疏矩阵M的转置矩阵T。

intTransposeSMatrix（TSMatrixM,TSMatrix*T）

{

intp,q,col;

（*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;

}

}

return1;

}

//算法5.2P100

//快速求稀疏矩阵M的转置矩阵T。

intFastTransposeSMatrix（TSMatrixM,TSMatrix*T）

{

intp,q,t,col,*num,*cpot;

num=（int*）malloc（（M.nu+1）*sizeof（int））;//生成数组（[0]不用）

cpot=（int*）malloc（（M.nu+1）*sizeof（int））;//生成数组（[0]不用）

（*T）.mu=M.nu;

（*T）.nu=M.mu;

（*T）.tu=M.tu;

if（（*T）.tu）

{

for（col=1;col<=M.nu;++col）

num[col]=0;//设初值

for（t=1;t<=M.tu;++t）//求M中每一列含非零元素个数

++num[M.data[t].j];

cpot[1]=1;

//求第col列中第一个非零元在（*T）.data中的序号

for（col=2;col<=M.nu;++col）

cpot[col]=cpot[col-1]+num[col-1];

for（p=1;p<=M.tu;++p）

{

col=M.data[p].j;

q=cpot[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;

++cpot[col];

}

}

free（num）;

free（cpot）;

return1;

}

intmain（）

{

TSMatrixA,B,C;

printf（"创建矩阵A:

"）;

CreateSMatrix（&A）;

PrintSMatrix（A）;

printf（"由矩阵A复制矩阵B:

"）;

CopySMatrix（A,&B）;

PrintSMatrix（B）;

DestroySMatrix（&B）;

printf（"销毁矩阵B后:

\n"）;

PrintSMatrix（B）;

printf（"重创矩阵B:

（注意与矩阵A的行、列数相同，这样方便后面的测试"

"行、列分别为%d,%d）\n",A.mu,A.nu）;

CreateSMatrix（&B）;

PrintSMatrix（B）;

printf（"矩阵C1（A+B）:

"）;

AddSMatrix（A,B,&C）;

PrintSMatrix（C）;

DestroySMatrix（&C）;

printf（"矩阵C2（A-B）:

"）;

SubtSMatrix（A,B,&C）;

PrintSMatrix（C）;

DestroySMatrix（&C）;

printf（"矩阵C3（A的转置）:

"）;

TransposeSMatrix（A,&C）;

PrintSMatrix（C）;

DestroySMatrix（&A）;

DestroySMatrix（&B）;

DestroySMatrix（&C）;

printf（"创建矩阵A2:

"）;

CreateSMatrix（&A）;

PrintSMatrix（A）;

printf（"创建矩阵B3:

（行数应与矩阵A2的列数相同=%d）\n",A.nu）;

CreateSMatrix（&B）;

PrintSMatrix（B）;

printf（"矩阵C5（A*B）:

"）;

MultSMatrix（A,B,&C）;

PrintSMatrix（C）;

DestroySMatrix（&A）;

DestroySMatrix（&B）;

DestroySMatrix（&C）;

printf（"创建矩阵A:

"）;

CreateSMatrix（&A）;

PrintSMatrix（A）;

FastTransposeSMatrix（A,&B）;

printf（"矩阵B（A的快速转置）:

"）;

PrintSMatrix（B）;

DestroySMatrix（&A）;

DestroySMatrix（&B）;

system（"pause"）;

return0;

}

/*

输出效果：

创建矩阵A:

请输入矩阵的行数,列数,非零元素个数：

（逗号）

3,3,3

请按行序顺序输入第1个非零元素所在的行（1～3）,列（1～3）,元素值：

（逗号）

1,1,1

请按行序顺序输入第2个非零元素所在的行（1～3）,列（1～3）,元素值：

（逗号）

1,3,2

请按行序顺序输入第3个非零元素所在的行（1～3）,列（1～3）,元素值：

（逗号）

3,3,3

3行3列3个非零元素。

行列元素值

111

132

333

由矩阵A复制矩阵B:

3行3列3个非零元素。

行列元素值

111

132

333

销毁矩阵B后:

0行0列0个非零元素。

行列元素值

重创矩阵B:

（注意与矩阵A的行、列数相同，这样方便后面的测试行、列分别为3,3）

请输入矩阵的行数,列数,非零元素个数：

（逗号）

3,3,3

请按行序顺序输入第1个非零元素所在的行（1～3）,列（1～3）,元素值：

（逗号）

1,2,1

请按行序顺序输入第2个非零元素所在的行（1～3）,列（1～3）,元素值：

（逗号）

2,1,2

请按行序顺序输入第3个非零元素所在的行（1～3）,列（1～3）,元素值：

（逗号）

3,1,3

3行3列3个非零元素。

行列元素值

121

212

313

矩阵C1（A+B）:

3行3列6个非零元素。

行列元素值

111

121

132

212

313

333

矩阵C2（A-B）:

3行3列6个非零元素。

行列元素值

111

12-1

132

21-2

31-3

333

矩阵C3（A的转置）:

3行3列3个非零元素。

行列元素值

111

312

333

创建矩阵A2:

请输入矩阵的行数,列数,非零元素个数：

（逗号）

3,3,3

请按行序顺序输入第1个非零元素所在的行（1～3）,列（1～3）,元素值：

（逗号）

1,1,1

请按行序顺序输入第2个非零元素所在的行（1～3）,列（1～3）,元素值：

（逗号）

1,3,2

请按行序顺序输入第3个非零元素所在的行（1～3）,列（1～3）,元素值：

（逗号）

3,3,3

3行3列3个非零元素。

行列元素值

111

132

333

创建矩阵B3:

（行数应与矩阵A2的列数相同=3）

请输入矩阵的行数,列数,非零元素个数：

（逗号）

3,3,2

请按行序顺序输入第1个非零元素所在的行（1～3）,列（1～3）,元素值：

（逗号）

1,3,1

请按行序顺序输入第2个非零元素所在的行（1～3）,列（1～3）,元素值：

（逗号）

2,2,2

3行3列2个非零元素。

行列元素值

131

222

矩阵C5（A*B）:

3行3列1个非零元素。

行列元素值

131

创建矩阵A:

请输入矩阵的行数,列数,非零元素个数：

（逗号）

3,3,2

请按行序顺序输入第1个非零元素所在的行（1～3）,列（1～3）,元素值：

（逗号）

1,2,2

请按行序顺序输入第2个非零元素所在的行（1～3）,列（1～3）,元素值：

（逗号）

3,1,2

3行3列2个非零元素。

行列元素值

122

312

矩阵B（A的快速转置）:

3行3列2个非零元素。

行列元素值

132

212

请按任意键继续...

*/