数据结构入门----矩阵的两种转置运算

一. 实验要求 用三元组表压缩存储矩阵，实现创建矩阵、显示以及教材中介绍的两种转置算法。 二. 实验目的 通过该实验，理解矩阵压缩存储的概念、方法等相关知识，掌握用三元组表方式如何进行矩阵的压缩存储，并在此基础上进行转置操作，理解转置和快速转置两种矩阵转置算法的思想。 三. 设计思想 首先，构建稀疏矩阵的三元组顺序表存储单元。一个结点的定义：假设非零元个数的最大值为125000，定义非零元的行下标j，列下标k，元素值e；还有整个三元组表的定义：数据data（数据从data[1]开始存，data[0]未用），矩阵的行数mu，列数nu和非零元个数tu。然后写出函数word（）用于输出选项。 1.创建矩阵，首先从键盘输入要创建矩阵的行数mu列数nu非零元个数tu。检查非零元素个数是否小于等于行数乘列数：if(M.tu>M.mu*M.nu)；然后利用for循环循环输入第i个元素的行数row，列数col和元素值e。首先检查输入的行数或者列数是否大于创建矩阵的行数或列数if(row>M.mu||col>M.nu)；检查是否能控制输入的非零元素的下标是递增的：先判断行数j是否是递增的if(row<M.data[i-1].j&&i>1)，注意判断递增是在输入第二个元素开始；再判断如果行数j相同、列数k是否是递增的if(row==M.data[i-1].j&&i>1)｛if(col<M.data[i-1].k)｝；//检查是否能拦截元素重复输入：if((row==M.data[i-1].j)&&(col==M.data[i-1].k))。如果均满足条件，则进行赋值：M.data[i].j=row; M.data[i].k=col; M.data[i].e=e。 2.销毁矩阵，直接将创建矩阵的行数mu列数nu非零元个数tu均赋为0。即完成销毁矩阵。 3.输出矩阵M，首先定义一个二维数组a[100][100],然后先把数组要用的部分全部赋为0：for(i=1;i<=M.mu;i++){for(j=1;j<=M.nu;j++){a[i][j]=0; }}。再利用for循环把矩阵M的值赋给二维数组a：for(i=1;i<=M.tu;i++){a[M.data[i].j][M.data[i].k] =M.data[i].e;}。然后用for循环控制输出数组a的mu行nu列：for(i=1;i<=M.mu;i++){for(j=1;j<=M.nu;j++){cout<<a[i][j]<<" ";}cout<<endl; }。 4.转置矩阵，声明一个转置矩阵T，把M的行数mu列数nu非零元个数tu赋给T的列数nu行数mu非零元个数tu。再利用for循环对M进行转置：首先利用col来控制扫描矩阵M的三元表列序进行for循环，在循环中定义一个变量n是矩阵M中的结点编号，控制n<=M的非零元个数tu进行for循环，并定义每循环完一次col循环都赋n=1，再在循环中判断矩阵M的三元组表中底n个非零元元素的列下标k是否等于正在循环的矩阵M三元组表列序col，如果相等，则开始进行转置，把矩阵M的行下标j赋给矩阵T的列下标k，把矩阵M的列下表k赋给矩阵T的行下标j：for(int col=1;col<=M.nu;col++) {for(n=1;n<=M.tu;n++){if(M.data[n].k==col) {T.data[i].j=M.data[n].k; T.data[i].k=M.data[n].j; T.data[i].e=M.data[n].e; i++;}}}，即完成转置。 5.快速转置矩阵，声明一个转置矩阵T，把M的行数mu列数nu非零元个数tu赋给T的列数nu行数mu非零元个数tu。声明两个向量num和cpot，向量num[col]用于存放M中第col列中的非零元素个数，向量cpot[col]用于存放第col列的第一个非0元素的位置。先初始化M中各列的非零元素个数为0：for(col=1;col<=M.nu;col++){num[col] =0; }。再生成每列的非零元素个数向量num：for( i = 1; i <=M.tu; i ++) {col =M.data[ i ] .k ; num [col]++;}，再生成每列首元位置辅助向量表cpot：cpot[1] =1; for(col=2;col<=M.nu;col++) {cpot[col]=cpot[col-1]+num[col-1] ; }。定义两个变量p和q，p指向矩阵M的data域值，q指向矩阵T的data域值。在for循环中，控制p小于等于M的非零元个数tu，把矩阵M.data中的第p个数的列下表k赋给col，查辅助向量表得到q，即M中第p个数在转置矩阵T中的位置。然后把M中第p个元素的行下标j，列下标k和元素值e赋给T中第q个元素的列下标k，行下标j和元素值e。最后修改向量表中col所在列序的值加一，以供同一列的下一个非零元素定位用。for(p=1;p<=M.tu;p++){col=M.data[p].k; q=cpot[col];T.data[q].j=M.data[p].k;T.data[q].k=M.data[p].j;T.data[q].e=M.data[p].e;++cpot[col]; }。 四. 主要源代码

#include "iostream" using namespace std; #define MAXSIZE 12500 int checkStatus=0; typedef struct { int elem_row,elem_colunm; int elem; }Triple; typedef struct { Triple data[MAXSIZE+1]; int row_count,column_count,nonzero_elem; }TSMatrix; void selectFunc(int _select); void CreatSMatrix(TSMatrix &M); void DestroySMatrix(TSMatrix &M); void PrintSMatrix(TSMatrix &M); void TransposeSMatrix(TSMatrix &M); void FastTransposeSMatrix(TSMatrix &M); static TSMatrix M; void main() { cout<<"***************************************************"<<endl; cout<<"***************** 1.创建矩阵 *****************"<<endl; cout<<"***************** 2.销毁矩阵 *****************"<<endl; cout<<"***************** 3.输出矩阵 *****************"<<endl; cout<<"***************** 4.转置矩阵 *****************"<<endl; cout<<"***************** 5.快速转置矩阵 *****************"<<endl; cout<<"***************** 6.退出 *****************"<<endl; cout<<"***************************************************"<<endl; int _select; while(1) { cout<<"请输入功能前面的数字代号："; cin>>_select; if(!cin || _select==0 || _select>6) { cout<<"您输入的选项有误，请重新输入！"<<endl; cout<<endl; cin.clear(); cin.sync(); continue; } else { if(_select==6) { exit(1); } else { selectFunc(_select); } } cout<<endl; } system("pause"); } void selectFunc(int _select) { switch(_select) { case 1: { CreatSMatrix(M); checkStatus=1; break; } case 2: { if(checkStatus==1) { DestroySMatrix(M); checkStatus=0; } else { checkStatus=0; cout<<"尚未初始化矩阵，请先初始化!"<<endl; } break; } case 3: { if(checkStatus==1) { PrintSMatrix(M); } else { checkStatus=0; cout<<"尚未初始化矩阵，请先初始化!"<<endl; } break; } case 4: { if(checkStatus==1) { TransposeSMatrix(M); } else { checkStatus=0; cout<<"尚未初始化矩阵，请先初始化!"<<endl; } break; } case 5: { if(checkStatus==1) { FastTransposeSMatrix(M); } else { checkStatus=0; cout<<"尚未初始化矩阵，请先初始化!"<<endl; } break; } default: { cout<<"输入不合法，请重新输入！"<<endl; break; } } } void CreatSMatrix(TSMatrix &M) { int row,col,elem; cout<<"请输入要创建矩阵的行数，列数、非零元个数："<<endl; cin>>M.row_count; cin>>M.column_count; cin>>M.nonzero_elem; if(M.nonzero_elem>M.row_count*M.column_count || M.row_count<0 || M.column_count<0 || M.nonzero_elem<0) { cout<<"非零元素个数大于行数乘列数，输入错误！"<<endl; } else { for(int after=1;after<=M.nonzero_elem;after++) { cout<<"请输入第"<<after<<"个元素的行，列，数值："<<endl; cin>>row; cin>>col; cin>>elem; if(row>M.row_count || col>M.column_count || row<1 || col<1) { cout<<"输入有误！"<<endl; after--; } if(row<M.data[after-1].elem_row && after>1) { cout<<"请从小到大（行数）输入元素！"<<endl; after--; continue; } if(row==M.data[after-1].elem_row && after>1) { if(col<M.data[after-1].elem_colunm) { cout<<"请按照列数从小到大输入元素！"<<endl; after--; continue; } if(col>M.data[after-1].elem_colunm) { M.data[after].elem_row=row; M.data[after].elem_colunm=col; M.data[after].elem=elem; } } if((row==M.data[after-1].elem_row) && (col==M.data[after-1].elem_colunm)) { cout<<"请勿重复输入元素！"<<endl; after--; continue; } else { M.data[after].elem_row=row; M.data[after].elem_colunm=col; M.data[after].elem=elem; } } cout<<"创建矩阵成功！"<<endl; } } void DestroySMatrix(TSMatrix &M) { M.row_count=0; M.column_count=0; M.nonzero_elem=0; cout<<"销毁矩阵成功！"<<endl; } void PrintSMatrix(TSMatrix &M) { int a[100][100]; int i,j; for(i=1;i<=M.row_count;i++) { for(j=1;j<=M.column_count;j++) { a[i][j]=0; } } for(i=1;i<=M.nonzero_elem;i++) { a[M.data[i].elem_row][M.data[i].elem_colunm]=M.data[i].elem; } for(i=1;i<=M.row_count;i++) { for(j=1;j<=M.column_count;j++) { cout<<a[i][j]<<" "; } cout<<endl; } } void TransposeSMatrix(TSMatrix &M) { TSMatrix T; T.row_count=M.column_count; T.column_count=M.row_count; T.nonzero_elem=M.nonzero_elem; int before=1; int after=1; for(int col=1;col<=M.column_count;col++) { for(before=1;before<=M.nonzero_elem;before++) { if(M.data[before].elem_colunm==col) { T.data[after].elem_row=M.data[before].elem_colunm; T.data[after].elem_colunm=M.data[before].elem_row; T.data[after].elem=M.data[before].elem; after++; } } } cout<<"转置矩阵成功！"<<endl; PrintSMatrix(T); } void FastTransposeSMatrix(TSMatrix &M) { TSMatrix T; T.row_count=M.column_count; T.column_count=M.row_count; T.nonzero_elem=M.nonzero_elem; int p,q,col,*num,*cpot; num=(int *)malloc((M.column_count+1)*sizeof(int)); cpot=(int *)malloc((M.column_count+1)*sizeof(int)); if(T.nonzero_elem) { for(col=1;col<=M.column_count;col++) { num[col]=0; } for(int after=1;after<=M.nonzero_elem;after ++) { col=M.data[after].elem_colunm; num [col]++ ; } cpot[1] =1; for(col=2;col<=M.column_count;col++) { cpot[col]=cpot[col-1]+num[col-1]; } for(p=1;p<=M.nonzero_elem;p++) { col=M.data[p]. elem_colunm; q=cpot[col]; T.data[q].elem_row=M.data[p].elem_colunm; T.data[q].elem_colunm=M.data[p].elem_row; T.data[q].elem=M.data[p].elem; cpot[col]++; } } cout<<"快速转置矩阵成功！"<<endl; PrintSMatrix(T); }

五. 调试与测试数据