《数据结构C语言版-稀疏矩阵的三元组顺序表存储表示和实现.doc》由会员分享，可在线阅读，更多相关《数据结构C语言版-稀疏矩阵的三元组顺序表存储表示和实现.doc（11页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、typedef int ElemType；/ 稀疏矩阵的三元组顺序表存储表示 #define MAXSIZE 100 / 非零元个数的最大值 typedef structint i，j；/ 行下标，列下标 ElemType e； / 非零元素值 Triple;typedef structTriple dataMAXSIZE+1； / 非零元三元组表，data0未用 int mu，nu，tu；/ 矩阵的行数、列数和非零元个数 TSMatrix；/ 创建稀疏矩阵Mint CreateSMatrix（TSMatrix M)int i，m,n;ElemType e;int k;printf（”请输入矩
2、阵的行数，列数，非零元素个数：（逗号)n”)；scanf(”%d，d,%d”,(M).mu，（*M）。nu,&（M）.tu)；（M）。data0。i=0；/ 为以下比较顺序做准备 for（i = 1； i = (M）。tu； i+）doprintf（”请按行序顺序输入第%d个非零元素所在的行(1d)，列(1d）,元素值:（逗号）n， i，（*M）.mu,（M)。nu)；scanf(”d,%d，d，&m,n，&e)；k=0;/ 行或列超出范围 if(m （M)。mu n 1 | n （M)。nu) k=1；if(m (M）.datai1.i m = (M)。datai1。i n = (M).da
3、tai-1。j） / 行或列的顺序有错 k=1;while（k)；(M）。datai.i = m；/行下标(M）.datai.j = n；/列下标（*M）.datai.e = e；/该下标所对应的值return 1；/ 销毁稀疏矩阵M,所有元素置空void DestroySMatrix（TSMatrix M) （*M).mu=0；(*M）。nu=0；(M）。tu=0；/ 输出稀疏矩阵Mvoid PrintSMatrix(TSMatrix M）int i；printf(nd行%d列%d个非零元素。n”，M.mu，M.nu，M.tu)；printf（”4s%4s%8sn”， ”行”， ”列”， 元
4、素值）;for（i=1；i=M。tu；i+）printf（”4d%4d8dn”，M.datai.i,M.datai。j,M。datai。e);/ 由稀疏矩阵M复制得到Tint CopySMatrix（TSMatrix M，TSMatrix *T) (*T）=M;return 1；/ AddSMatrix函数要用到int comp（int c1,int c2） int i；if（c1c2）i=1；else if(c1=c2)i=0；elsei=-1;return i；/ 求稀疏矩阵的和Q=M+Nint AddSMatrix（TSMatrix M，TSMatrix N,TSMatrix Q） Tr
5、iple Mp，*Me，*Np，Ne，Qh,Qe；if（M.mu！=N.mu)return 0；if（M.nu！=N。nu)return 0；（Q）.mu=M。mu;（*Q）。nu=M。nu；Mp=M.data1;/ Mp的初值指向矩阵M的非零元素首地址 Np=N。data1;/ Np的初值指向矩阵N的非零元素首地址 Me=M.dataM。tu；/ Me指向矩阵M的非零元素尾地址 Ne=&N.dataN.tu；/ Ne指向矩阵N的非零元素尾地址 Qh=Qe=（Q)。data；/ Qh、Qe的初值指向矩阵Q的非零元素首地址的前一地址 while(Mp = Me Np j)） case 1： *Q
6、e=*Mp；Mp+；break;case 0： Qe=*Mp;Qee+=Npe;if（!Qe-e) / 元素值为0，不存入压缩矩阵 Qe-；Mp+;Np+；break;case -1： Qe=*Np；Np+;break;case -1： *Qe=*Np；Np+;if（MpMe） / 矩阵M的元素全部处理完毕 while（Np=Ne）Qe+；Qe=*Np；Np+;if（NpNe) / 矩阵N的元素全部处理完毕 while（Mp=Me）Qe+;*Qe=*Mp；Mp+;（Q).tu=QeQh； / 矩阵Q的非零元素个数 return 1;/ 求稀疏矩阵的差Q=MNint SubtSMatrix（TS
7、Matrix M，TSMatrix N,TSMatrix *Q) int i;for(i=1;i=N。tu；i+）N。datai.e=1；AddSMatrix（M,N,Q）；return 1；/ 求稀疏矩阵的乘积Q=M*Nint MultSMatrix（TSMatrix M,TSMatrix N,TSMatrix *Q） int i,j，h=M.mu，l=N。nu,Qn=0；/ h，l分别为矩阵Q的行、列值，Qn为矩阵Q的非零元素个数,初值为0 ElemType *Qe；if（M.nu！=N。mu)return 0；（*Q)。mu=M。mu；（*Q）.nu=N。nu；Qe=(ElemType
8、）malloc(hlsizeof（ElemType）)； / Qe为矩阵Q的临时数组 / 矩阵Q的第i行j列的元素值存于（Qe+（i1）*l+j-1)中，初值为0 for(i=0；ihl；i+）（Qe+i）=0; / 赋初值0 for(i=1;i=M。tu；i+) / 矩阵元素相乘,结果累加到Qe for(j=1；j=N。tu；j+)if（M。datai.j=N。dataj。i）*（Qe+（M。datai.i-1)l+N.dataj.j1） +=M。datai.e N。dataj.e；for(i=1；i=M。mu；i+）for(j=1；j=N.nu;j+)if（Qe+（i1)l+j1）!=0)
9、Qn+；(Q）。dataQn。e=*（Qe+（i1）*l+j-1)；（Q）。dataQn。i=i；（*Q).dataQn。j=j;free（Qe）;(Q）。tu=Qn；return 1；/ 算法5。1 P99/ 求稀疏矩阵M的转置矩阵T。int TransposeSMatrix（TSMatrix M，TSMatrix *T)int p，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.datap。j=col）
10、(T）。dataq。i=M.datap.j;（*T).dataq。j=M。datap.i；(*T）。dataq.e=M。datap.e；+q；return 1;/ 算法5.2 P100/ 快速求稀疏矩阵M的转置矩阵T。int FastTransposeSMatrix(TSMatrix M,TSMatrix *T) int p，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.
11、mu；(T).tu=M.tu;if（(T）。tu）for（col=1;col=M。nu；+col）numcol=0； / 设初值 for（t=1；t=M。tu；+t） / 求M中每一列含非零元素个数 +numM。datat。j;cpot1=1；/ 求第col列中第一个非零元在（*T)。data中的序号for（col=2;col=M。nu；+col） cpotcol=cpotcol1+numcol-1；for(p=1;p=M。tu；+p）col=M。datap。j;q=cpotcol；（T).dataq.i=M.datap.j；（T)。dataq。j=M.datap.i；（T）.dataq。e=
12、M。datap。e；+cpotcol;free（num）;free（cpot）；return 1；int main()TSMatrix A，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）;Creat
13、eSMatrix(B）;PrintSMatrix（B）;printf（”矩阵C1(A+B)： ）；AddSMatrix（A,B,&C）;PrintSMatrix(C）；DestroySMatrix(C）;printf（”矩阵C2（AB）： ”）；SubtSMatrix（A,B，C）;PrintSMatrix（C）；DestroySMatrix（C)；printf（矩阵C3(A的转置): ”）；TransposeSMatrix（A，C）;PrintSMatrix（C);DestroySMatrix(A);DestroySMatrix(B）；DestroySMatrix（C）;printf(创建矩
14、阵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,
15、&B);printf(矩阵B（A的快速转置）: ）;PrintSMatrix(B)；DestroySMatrix（&A)；DestroySMatrix(&B)；system（”pause）;return 0；/输出效果:创建矩阵A: 请输入矩阵的行数,列数,非零元素个数:(逗号)3,3,3请按行序顺序输入第1个非零元素所在的行(13），列(13），元素值:（逗号)1，1，1请按行序顺序输入第2个非零元素所在的行(13），列（13），元素值：（逗号）1,3，2请按行序顺序输入第3个非零元素所在的行(13）,列（13)，元素值：（逗号）3,3，33行3列3个非零元素。 行 列 元素值 1 1 1
16、1 3 2 3 3 3由矩阵A复制矩阵B:3行3列3个非零元素。 行 列 元素值 1 1 1 1 3 2 3 3 3销毁矩阵B后：0行0列0个非零元素。 行 列 元素值重创矩阵B：（注意与矩阵A的行、列数相同，这样方便后面的测试行、列分别为3,3)请输入矩阵的行数，列数,非零元素个数：(逗号）3，3，3请按行序顺序输入第1个非零元素所在的行（13），列(13),元素值:(逗号）1，2，1请按行序顺序输入第2个非零元素所在的行(13）,列(13），元素值:(逗号）2，1，2请按行序顺序输入第3个非零元素所在的行(13),列（13)，元素值：(逗号)3,1,33行3列3个非零元素。 行 列 元素值
17、 1 2 1 2 1 2 3 1 3矩阵C1(A+B）:3行3列6个非零元素. 行 列 元素值 1 1 1 1 2 1 1 3 2 2 1 2 3 1 3 3 3 3矩阵C2（A-B）：3行3列6个非零元素。 行 列 元素值 1 1 1 1 2 1 1 3 2 2 1 -2 3 1 3 3 3 3矩阵C3（A的转置）：3行3列3个非零元素。 行 列 元素值 1 1 1 3 1 2 3 3 3创建矩阵A2： 请输入矩阵的行数，列数，非零元素个数:（逗号)3,3,3请按行序顺序输入第1个非零元素所在的行（13)，列（13),元素值：（逗号）1,1，1请按行序顺序输入第2个非零元素所在的行（13），
18、列（13），元素值：（逗号）1，3，2请按行序顺序输入第3个非零元素所在的行(13),列（13），元素值：（逗号）3，3,33行3列3个非零元素。 行 列 元素值 1 1 1 1 3 2 3 3 3创建矩阵B3：(行数应与矩阵A2的列数相同=3)请输入矩阵的行数，列数，非零元素个数：（逗号）3，3,2请按行序顺序输入第1个非零元素所在的行(13），列(13），元素值：（逗号)1,3,1请按行序顺序输入第2个非零元素所在的行(13）,列(13），元素值：（逗号）2，2,23行3列2个非零元素。 行 列 元素值 1 3 1 2 2 2矩阵C5（A*B）：3行3列1个非零元素。 行 列 元素值 1 3 1创建矩阵A: 请输入矩阵的行数，列数，非零元素个数:(逗号)3,3，2请按行序顺序输入第1个非零元素所在的行（13），列（13),元素值：（逗号）1，2,2请按行序顺序输入第2个非零元素所在的行（13)，列(13），元素值:（逗号）3，1，23行3列2个非零元素. 行 列 元素值 1 2 2 3 1 2矩阵B（A的快速转置）：3行3列2个非零元素。 行 列 元素值 1 3 2 2 1 2请按任意键继续. 。 ./