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

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

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

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

typeｄefintEｌemTｙpｅ;

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

#defineＭＡXＳIZＥ1０0／/非零元个数得最大值　

tyｐedef　strｕcｔ

｛

iｎti,j；ﻩ／/行下标，列下标

ﻩＥlｅmType　e；　//　非零元素值

}Triｐle；

typeｄefｓtruct

｛

Tripledａta[ＭＡXＳＩＺE+1］；　／/非零元三元组表，datａ[0］未用　

ﻩｉntｍu，ｎu，ｔｕ；ﻩﻩ/／　矩阵得行数、列数与非零元个数　

}TＳMａtrｉx；

／/　创建稀疏矩阵Ｍ

intCreateSMatrｉx（TＳMatrix　*M）

｛

ﻩinｔｉ,m，n；

ﻩElemＴｙpe　e;

ﻩintk；

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

（逗号）\ｎ”）;

ﻩscanf（”％d，％d，％d”，＆（＊M）、mu，&（*M）、nu，＆（*M）、tu）;

（＊Ｍ）、data[0]、i＝0；ﻩ//　为以下比较顺序做准备

ﻩｆor（i=　1；　ｉ　〈＝（＊M）、tu;　i++）

ﻩ｛

ﻩdｏ

ﻩﻩ{

ﻩﻩﻩpｒｉntf（"请按行序顺序输入第％ｄ个非零元素所在得行（１~%d），＂

ﻩﻩ＂列（1～％d），元素值:

（逗号）\n",　i,（*M）、mu，（*M）、nｕ）；

ﻩﻩscａnｆ（＂%d，%d，％d＂，＆m,＆n，＆e）；

ﻩk＝０;

ﻩﻩ/／行或列超出范围　

if（m〈　1｜｜　m〉　（*M）、mｕ|｜　ｎ＜1|｜　n>（＊M）、nu）　

ﻩﻩk=1;

ﻩﻩif（m＜（＊M）、data［i—１］、i　｜｜ｍ　＝=　（＊M）、datａ［i-1]、ｉ

ﻩﻩ&＆　n　<=（*M）、dａｔa［i—１]、j）//　行或列得顺序有错

ﻩﻩk=1；

ﻩ｝while（k）；

ﻩ（＊Ｍ）、daｔa[i]、i=ｍ；／/行下标

（*M）、datａ［i]、j＝n；//列下标

（＊M）、data［i]、ｅ=e；ﻩ//该下标所对应得值

｝

return1；

}

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

voiｄDesｔｒoyＳＭａｔrix（TSＭatｒix*Ｍ）

{

ﻩ（＊M）、mu=0；

ﻩ（＊M）、nu=0；

ﻩ（＊M）、tｕ＝０；

}

／/输出稀疏矩阵M

voｉｄ　PrintＳMatriｘ（TSMatrｉｘ　M）

{

inti；

ﻩprｉnｔf（"＼n％d行%d列％ｄ个非零元素。

\n"，M、mu,Ｍ、ｎｕ，M、tu）；

ｐｒiｎｔf（"%4s％4s%８ｓ\n＂,”行＂,　"列"，”元素值”）；

ﻩfor（i=1；ｉ＜=M、tu；i++）

ｐrintf（＂%4ｄ%4d％８d\n"，M、dａｔa［i］、i,M、datａ[i]、j，Ｍ、data［ｉ］、e）;

}

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

ｉnt　CopyＳＭaｔrix（TSMaｔrixM,TSMaｔｒｉx＊T）

｛

ﻩ（＊T）=M;

ﻩreturn１;

}

//ＡddSMatrix函数要用到

intp（int　c1，intc２）

{

ﻩｉnti;

ﻩif（ｃ1<ｃ2）

ﻩi=１；

else　if（c1=＝c2）

ﻩi=0；

ﻩeｌse

ﻩﻩｉ=—1；

ﻩｒｅturｎ　i；

｝

/／求稀疏矩阵得与Q=M＋N

iｎｔＡddSMａtrｉx（TSMatrｉxM，TＳMaｔrixN,TSMａｔrｉx　＊Q）

{

ﻩTriｐlｅ＊Mp，＊Ｍｅ，＊Ｎp，＊Ｎｅ,＊Qh,＊Ｑｅ；

iｆ（Ｍ、ｍu！

=N、mu）

ﻩretuｒn　0；

ﻩif（Ｍ、ｎu！

＝N、nｕ）

ﻩﻩｒeturn0；

（*Ｑ）、mu=Ｍ、mu;

（＊Q）、nu=M、nu；

ﻩMp=&Ｍ、dａta［1］;ﻩ/／　Ｍp得初值指向矩阵M得非零元素首地址

Np＝＆N、daｔa[１］；/／　Np得初值指向矩阵N得非零元素首地址

Me=＆M、ｄａta[Ｍ、tu]；ﻩ/／　Mｅ指向矩阵M得非零元素尾地址

ﻩNe＝&N、ｄatａ［Ｎ、ｔu］;ﻩ/／　Ｎｅ指向矩阵N得非零元素尾地址

Qh=Qe=（＊Q）、datａ;／／Qh、Qe得初值指向矩阵Ｑ得非零元素首地址得前一地址

whilｅ（Ｍp　＜=Ｍｅ&＆Np<=　Ne）

｛

Ｑe++;

ﻩsｗitcｈ（ｐ（Mｐ-＞i，Np-〉ｉ））

ﻩﻩ{

ﻩcａse1：

ﻩ＊Qe＝＊Ｍp；

ﻩＭp+＋；

ﻩｂreak；

ﻩcasｅ0：

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

ﻩﻩsｗitch（p（Mp->j，Ｎp－>j））

｛

ﻩcａｓｅ１：

*Qｅ=*Mｐ；

ﻩﻩMp+＋；

ﻩｂreａk；

ﻩcａｓe０:

ﻩﻩ＊Ｑe=＊Mp;

ﻩﻩＱe—>e+＝Np-〉e;

ﻩﻩif（！

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

ﻩﻩQｅ-－;

ﻩﻩﻩMp+＋；

ﻩﻩﻩNｐ＋＋；

ﻩﻩﻩbｒｅａｋ；

ﻩﻩｃaｓｅ—1：

ﻩﻩ＊Ｑe=＊Ｎp；

ﻩNp++；

ﻩ｝

ﻩﻩbreａk;

ﻩｃase-１:

ﻩﻩ＊Ｑｅ=*Ｎp;

ﻩﻩNｐ++；

ﻩﻩ}

｝

ｉf（Mp〉Me）//矩阵Ｍ得元素全部处理完毕　

ﻩwｈilｅ（Ｎp<=Nｅ）

ﻩ{

ﻩﻩＱe++；

*Ｑe=*Np;

Np++；

ﻩﻩ}

ﻩif（Np>Ne）/／　矩阵Ｎ得元素全部处理完毕　

ﻩwhile（Mp<＝Ｍe）

ﻩ{

ﻩQｅ++；

ﻩﻩﻩ*Qe=＊Ｍｐ；

Mp++;

ﻩﻩ}

（*Q）、tu=Qe－Qh；//矩阵Q得非零元素个数

return１；

}

／/求稀疏矩阵得差Q=Ｍ—N

inｔSubｔSＭａｔrix（ＴＳMatｒixＭ,ＴSMaｔｒｉｘN，TＳMatrix　*Q）

｛

ﻩinｔｉ；

for（ｉ＝1;i<=N、tu；ｉ++）

N、data［i]、e＊=—1；

ﻩAｄｄSMaｔrｉx（Ｍ,N，Q）;

ﻩｒeturn1;

}

//求稀疏矩阵得乘积Q=M＊N

intMuｌtSMatrix（TＳMatriｘM,ＴＳMatrixN,TＳMatriｘ　＊Q）

｛

ｉnti，ｊ，h=M、mu，l=N、nu,Qn=0；

ﻩ//h,ｌ分别为矩阵Q得行、列值,Qn为矩阵Ｑ得非零元素个数,初值为0

ElemＴypｅ　*Qｅ；

ｉf（Ｍ、nu!

＝Ｎ、mｕ）

ﻩｒeturn０;

（＊Q）、mｕ=M、ｍu；

（＊Q）、ｎu=N、nｕ；

ﻩQe=（EleｍType＊）malｌoｃ（h＊l＊sizｅｏf（EｌemType））;//　Qe为矩阵Q得临时数组

ﻩ//矩阵Q得第ｉ行j列得元素值存于＊（Qe+（i－1）＊l+j-1）中，初值为0　

for（i=０;i

＊（Qe+i）=0；/／赋初值0

ﻩｆor（i=1;i<＝Ｍ、tｕ；i++）//矩阵元素相乘,结果累加到Qｅ　

ﻩfor（j=1;j＜=N、tｕ;j＋+）

ﻩﻩif（M、dａｔa［i]、j=＝N、data［ｊ]、i）

ﻩﻩ*（Qｅ+（M、data［i]、i—1）*l+N、data[j]、j－１）＋=

ﻩﻩＭ、daｔa［ｉ］、ｅ　*N、data[j］、e；

ﻩｆor（i=1;i<=M、mｕ；i++）

ﻩﻩｆoｒ（ｊ=1；ｊ〈=N、ｎu;ｊ＋＋）

ﻩﻩif（＊（Ｑｅ+（ｉ—1）*l+ｊ－1）！

＝0）

{

ﻩﻩＱn＋+;

ﻩ（*Q）、ｄata[Qn]、ｅ=＊（Qe+（i-1）＊l+j-１）；

ﻩﻩ（＊Ｑ）、ｄatａ[Qn]、ｉ＝i;

ﻩﻩ（*Q）、ｄata[Qn]、j＝j；

}

free（Qe）;

ﻩ（＊Ｑ）、ｔｕ=Ｑn；

retｕrn1；

}

//算法5、１　P99

//求稀疏矩阵Ｍ得转置矩阵T。

inｔTrａnｓｐoｓｅＳMatrix（TSＭatrixM,TSMａｔｒix　＊T）

{

ﻩinｔp,ｑ，coｌ;

（＊T）、mu=Ｍ、nu；

ﻩ（*T）、nu＝M、ｍu；

ﻩ（＊T）、ｔu=M、tｕ；

if（（＊T）、ｔu）

ﻩ{

ﻩq=1;

ﻩﻩｆoｒ（col=1;col＜=M、nu;＋+ｃoｌ）ﻩ/／先将列转换成行

ﻩfor（p=1；p<＝M、tｕ；++p）／/再将行转换成列

ﻩﻩif（M、ｄatａ[ｐ]、j==ｃｏl）

ﻩﻩﻩ｛

ﻩﻩ（＊T）、data［q］、i=Ｍ、ｄatａ［p］、ｊ;

ﻩﻩ（＊T）、datａ［q]、j=M、daｔa［p］、i；

ﻩﻩﻩ（＊T）、ｄata［q］、e=Ｍ、ｄatａ［ｐ］、e；

ﻩﻩ++q；

ﻩﻩ｝

ﻩ｝

ｒeｔurn１；

｝

／/　算法5、2　Ｐ10０

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

int　FasｔTraｎspoｓｅＳMatrix（TSＭatrix　M，ＴSＭatｒix*T）

｛

inｔｐ，q，t，col，*nｕｍ，*cpoｔ；

nuｍ=（int*）maｌｌoc（（M、nu+1）＊ｓizeｏf（iｎt））;ﻩ/／生成数组（[0］不用）　

ﻩｃpot=（iｎt＊）malloc（（M、nu+１）*sizeoｆ（inｔ））;//生成数组（［0］不用）

（*T）、mu=M、ｎu；

（*T）、nu=M、ｍｕ；

ﻩ（*T）、tu=M、ｔu；

ﻩｉf（（*T）、tu）

ﻩ{

ﻩfor（ｃoｌ=1；cｏｌ〈=M、nｕ;++coｌ）

ﻩﻩﻩｎum［col]=0；／／　设初值　

for（t=1;t〈＝Ｍ、ｔu；++ｔ）//求Ｍ中每一列含非零元素个数

ﻩﻩ++num［M、data[t］、j］；

ﻩcｐｏt［1]=1；

ﻩ//　求第col列中第一个非零元在（*T）、dａta中得序号

for（coｌ＝2;col＜=M、nu;＋+ｃol）

ﻩｃpot［ｃoｌ］=cｐｏt[ｃol-1］＋num［coｌ-1］；

ﻩfoｒ（p＝1；ｐ＜=M、ｔｕ;＋＋p）

ﻩ{

ﻩﻩcol=M、daｔa［p］、j；

ﻩﻩq＝ｃｐｏt[ｃol];

ﻩﻩ（＊Ｔ）、data［q]、i=M、data［p]、j；

ﻩﻩﻩ（*T）、data［q］、j=M、ｄata[p]、i；

ﻩ（＊T）、dａｔa［ｑ］、e=M、data[p]、ｅ;

ﻩ+＋cpot[ｃｏｌ］;

ﻩ}

ﻩ｝

free（num）;

freｅ（cpoｔ）；

ﻩretuｒn１;

｝

ｉｎt　ｍain（）

｛

ﻩＴSMaｔrｉxＡ，Ｂ,C；

prｉｎtf（”创建矩阵A:

＂）；

CreateSＭaｔriｘ（＆A）；

PrｉntSMaｔrix（A）;

ﻩpｒintf（＂由矩阵A复制矩阵B:

”）;

ﻩCopySMａtｒix（Ａ，&B）;

ﻩPrｉntＳMatrix（B）；

ﻩDestroySMaｔrｉx（＆B）;

ﻩｐriｎｔf（"销毁矩阵B后:

\n＂）;

PriｎtＳＭaｔｒｉx（B）；

ｐrinｔf（”重创矩阵B:

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

ﻩﻩ"行、列分别为％d,％d）\ｎ”，　A、mu,A、nu）；

CreateSMａtrix（&B）;

PｒiｎtSMatrix（Ｂ）；

printｆ（"矩阵C1（Ａ＋B）：

”）；

AｄdＳMatrix（A，B,＆Ｃ）;

ﻩPrinｔＳMatrｉx（Ｃ）;

ﻩＤeｓｔroyＳMatｒix（&Ｃ）；

ﻩprintf（＂矩阵C２（A－B）：

"）；

ﻩSubｔＳＭatrix（Ａ，B，＆C）；

ＰｒintSMａtrix（C）;

ＤestrｏyＳMａtrix（＆C）;

ﻩｐｒinｔｆ（＂矩阵C3（A得转置）:

＂）；

TｒanspｏseSMatrｉx（A,＆Ｃ）;

PrｉｎtＳＭａtrix（C）;

ﻩＤestｒoｙSMatriｘ（＆A）；

DeｓtroySMａtrｉx（&B）；

ﻩDeｓtroySMatrix（＆C）；

ﻩprinｔf（"创建矩阵A2：

　"）；

ﻩCrｅaｔeSMatrix（＆A）；

PrｉntSMａtｒix（A）；

ﻩprintf（”创建矩阵B3:

（行数应与矩阵Ａ２得列数相同=％d）\ｎ＂，A、nu）；

CreateSMａtrｉx（＆B）；

ＰｒiｎｔＳＭatrix（Ｂ）;

prinｔf（”矩阵C5（A*Ｂ）:

”）；

ﻩMｕltSＭaｔrix（Ａ,B，＆C）；

ﻩPrinｔSMatrix（C）；

DesｔroyＳMａtrix（&Ａ）；

DｅstroySMatrｉx（＆B）;

DestroySMaｔｒiｘ（＆Ｃ）；

ﻩprintf（”创建矩阵A：

”）；

ﻩCreaｔeSMaｔｒｉx（＆A）;

PrｉntＳMaｔｒix（A）；

ﻩFａsｔTrａnsposeSMaｔｒix（A，＆B）;

ﻩprｉntf（”矩阵B（A得快速转置）：

”）；

ﻩPｒｉntSMatriｘ（B）;

ﻩDｅｓtｒoySMatｒix（＆A）;

ﻩDestｒoySMatrix（＆Ｂ）；

ﻩsyｓtem（＂paｕsｅ”）;

returｎ0；

｝

／*

输出效果：

创建矩阵Ａ:

请输入矩阵得行数,列数，非零元素个数:

（逗号）

3，3，3

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

（逗号）

1,1,1

请按行序顺序输入第2个非零元素所在得行（１～３），列（1~3）,元素值:

（逗号）

１,3，2

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

（逗号）

3，３，3

3行３列3个非零元素。

行列元素值

１　１　１

　1　32

　　　3　3　　　3

由矩阵A复制矩阵B：

3行3列3个非零元素.

　　行列　元素值

11　1

1　３　2

　　３　33

销毁矩阵B后：

0行0列0个非零元素。

行列元素值

重创矩阵B:

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

请输入矩阵得行数，列数，非零元素个数：

（逗号）

３，3，3

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

（逗号）

1，2，1

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

（逗号）

2，1,2

请按行序顺序输入第３个非零元素所在得行（1~3），列（1～3），元素值:

（逗号）

3,1，3

3行3列3个非零元素。

　行列元素值

　1２１

　21　　2

　3　１　　3

矩阵C1（A＋B）:

3行3列6个非零元素。

　　行　列元素值

　1　1　　1

　1　2　1

1３　２

　21　2

31　　　3

　3　33

矩阵Ｃ2（A—B）：

3行3列6个非零元素。

行列元素值

　　１１　　１

　12　-１

　　1　3　2

21　　　—2

　3　1　—３

　33　　　3

矩阵C3（A得转置）：

３行3列3个非零元素.

行列元素值

　1　1　1

　3　1　　2

　　３　3　　　　3

创建矩阵A２：

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

（逗号）

3,３，3

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

（逗号）

1,1,1

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

（逗号）

1，3，2

请按行序顺序输入第３个非零元素所在得行（1～3），列（1~3），元素值:

（逗号）

３，３,3

3行３列3个非零元素。

行列元素值

　　１1　　1

　1　３　2

　3　3　3

创建矩阵Ｂ３：

（行数应与矩阵Ａ２得列数相同＝３）

请输入矩阵得行数，列数，非零元素个数:

（逗号）

３,3,2

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

（逗号）

1，３，1

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

（逗号）

2，2,2

3行3列2个非零元素。

行　列元素值

　1３　1

２２　2

矩阵Ｃ5（Ａ＊Ｂ）：

3行3列1个非零元素.

行　列元素值

13　１

创建矩阵A：

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

（逗号）

3,3,2

请按行序顺序输入第１个非零元素所在得行（1~3），列（1~3），元素值：

（逗号）

1，２，２

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

（逗号）

3，1,2

3行3列2个非零元素。

行列　元素值

　　１　2　　2

31　2

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

3行3列2个非零元素。

行　列　元素值

13　　２

2１　　　　　2

请按任意键继续、、、

＊／