《三元数组的转置算法.doc》由会员分享,可在线阅读,更多相关《三元数组的转置算法.doc(4页珍藏版)》请在金锄头文库上搜索。
1、/ matrix_reverse.cpp : Defines the entry point for the console application./普通转置算法/时间复杂度:O(t*m);t是非零元个数,m是列数。每转置一列需要扫描全部三元数组#include stdafx.h#include struct elementint value;int i,j;struct matrixint c,v,t;struct element *data;int main(int argc, char* argv) int m,n,t; int i,j,d; int index; matrix *mt
2、,*lm;/lm是转置后的矩阵 element *e; /原是矩阵的输入 printf(输入矩阵的行数,列数,非零元个数n); scanf(%d%d%d,&m,&n,&t); mt=new matrix; mt-c=m; mt-v=n; mt-t=t; mt-data=new elementt; printf(按行序输入矩阵的非零元,按三元组形式:行 列 数据n); index=0; do scanf(%d%d%d,&i,&j,&d); e=new element; e-i=i;e-j=j;e-value=d; mt-dataindex=*e; index+; while(indexdata=
3、new elementt; i=0;j=0;index=0; int k=0; lm-c=n;/行数和列数对掉,非零元总数不变 lm-v=m; lm-t=t; for(i=0;in;i+)/对所有三元组扫描 for(j=0;jdataj.j=i)/对每一列进行转置 /对此列上的元素对掉信息 lm-datak.i=mt-dataj.j; lm-datak.j=mt-dataj.i; lm-datak.value=mt-dataj.value; k+; else continue; index=0; printf(转置后的矩阵n); printf(行 列 值n); while(indexdatai
4、ndex.i,lm-dataindex.j,lm-dataindex.value); index+; return 0; 快速转置代码如下:/ quick_sparse.cpp : Defines the entry point for the console application./快速转置算法#include stdafx.h#include struct elementint value;int i,j;struct matrixint c,v,t;struct element *data;/每行第一个非零元位置数组position,每行非零元个数数组numberint *positi
5、on;int *number;int main(int argc, char* argv) int m,n,t; int i,j,d; int index; matrix *mt,*lm;/lm是转置后的矩阵 element *e; /原是矩阵的输入 printf(输入矩阵的行数,列数,非零元个数n); scanf(%d%d%d,&m,&n,&t); mt=new matrix; mt-c=m; mt-v=n; mt-t=t; mt-data=new elementt; position=new intm; number=new intm; printf(按行序输入矩阵的非零元,按三元组形式:
6、行 列 数据n); index=0; do scanf(%d%d%d,&i,&j,&d); e=new element; e-i=i;e-j=j;e-value=d; mt-dataindex=*e; index+; while(indexc=n; bm-v=m; bm-t=t; bm-data=new elementt; for(i=0;in;i+)numberi=0; for(i=0;idatai.j+; position0=0; for(i=1;in;i+) positioni=positioni-1+numberi-1; for(i=0;idatai.j;j=positionindex
7、;/原始数组第j列的第一个元素,当这一列再次有元素时,依次插入 bm-dataj.i=mt-datai.j; bm-dataj.j=mt-datai.i; bm-dataj.value=mt-datai.value; positionindex+;/此列下一个元素为上一个元素加1 /对矩阵快速转置 index=0; printf(n原三元组矩阵n); while(indexdataindex.i,mt-dataindex.j,mt-dataindex.value); index+; index=0; printf(n转置后的三元组矩阵n); while(indexdataindex.i,bm-dataindex.j,bm-dataindex.value); index+; return 0;