数据结构C语言版稀疏矩阵的三元组顺序表存储表示和实现.docx
- 文档编号:10952303
- 上传时间:2023-05-28
- 格式:DOCX
- 页数:18
- 大小:19.87KB
数据结构C语言版稀疏矩阵的三元组顺序表存储表示和实现.docx
《数据结构C语言版稀疏矩阵的三元组顺序表存储表示和实现.docx》由会员分享,可在线阅读,更多相关《数据结构C语言版稀疏矩阵的三元组顺序表存储表示和实现.docx(18页珍藏版)》请在冰点文库上搜索。
数据结构C语言版稀疏矩阵的三元组顺序表存储表示和实现
typedefintElemType;
// 稀疏矩阵得三元组顺序表存储表示
#defineMAXSIZE100//非零元个数得最大值
typedef struct
{
inti,j;ﻩ//行下标,列下标
ﻩElemType e; // 非零元素值
}Triple;
typedefstruct
{
Tripledata[MAXSIZE+1]; //非零元三元组表,data[0]未用
ﻩintmu,nu,tu;ﻩﻩ// 矩阵得行数、列数与非零元个数
}TSMatrix;
// 创建稀疏矩阵M
intCreateSMatrix(TSMatrix *M)
{
ﻩinti,m,n;
ﻩElemType e;
ﻩ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
void PrintSMatrix(TSMatrix M)
{
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
int CopySMatrix(TSMatrixM,TSMatrix*T)
{
ﻩ(*T)=M;
ﻩreturn1;
}
//AddSMatrix函数要用到
intp(int c1,intc2)
{
ﻩinti;
ﻩif(c1<c2)
ﻩi=1;
else if(c1==c2)
ﻩi=0;
ﻩelse
ﻩﻩi=—1;
ﻩreturn i;
}
//求稀疏矩阵得与Q=M+N
intAddSMatrix(TSMatrixM,TSMatrixN,TSMatrix *Q)
{
ﻩTriple*Mp,*Me,*Np,*Ne,*Qh,*Qe;
if(M、mu!
=N、mu)
ﻩreturn 0;
ﻩ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(p(Mp->i,Np-〉i))
ﻩﻩ{
ﻩcase1:
ﻩ*Qe=*Mp;
ﻩMp++;
ﻩbreak;
ﻩcase0:
ﻩﻩ// M、N矩阵当前非零元素得行相等,继续比较列
ﻩﻩswitch(p(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、1 P99 //求稀疏矩阵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、2 P100 //快速求稀疏矩阵M得转置矩阵T。 int FastTransposeSMatrix(TSMatrix M,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; } int main() { ﻩ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个非零元素。 行列元素值 1 1 1 1 32 3 3 3 由矩阵A复制矩阵B: 3行3列3个非零元素. 行列 元素值 11 1 1 3 2 3 33 销毁矩阵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 21 2 3 1 3 矩阵C1(A+B): 3行3列6个非零元素。 行 列元素值 1 1 1 1 2 1 13 2 21 2 31 3 3 33 矩阵C2(A—B): 3行3列6个非零元素。 行列元素值 11 1 12 -1 1 3 2 21 —2 3 1 —3 33 3 矩阵C3(A得转置): 3行3列3个非零元素. 行列元素值 1 1 1 3 1 2 3 3 3 创建矩阵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个非零元素。 行列元素值 11 1 1 3 2 3 3 3 创建矩阵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个非零元素。 行 列元素值 13 1 22 2 矩阵C5(A*B): 3行3列1个非零元素. 行 列元素值 13 1 创建矩阵A: 请输入矩阵得行数,列数,非零元素个数: (逗号) 3,3,2 请按行序顺序输入第1个非零元素所在得行(1~3),列(1~3),元素值: (逗号) 1,2,2 请按行序顺序输入第2个非零元素所在得行(1~3),列(1~3),元素值: (逗号) 3,1,2 3行3列2个非零元素。 行列 元素值 1 2 2 31 2 矩阵B(A得快速转置): 3行3列2个非零元素。 行 列 元素值 13 2 21 2 请按任意键继续、、、 */
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 语言版 稀疏 矩阵 三元 顺序 存储 表示 实现