数据结构实验(5).doc

计算机系数据结构实验报告（1）
姓名： 孟红波 学号： 6100410179 专业班级： 卓越101班

实验目的：
深入研究数组的存储表示和实现技术，着重掌握对稀疏矩阵的表示方法及其运算的实现。
问题描述：
稀疏矩阵是指那些多数元素为零的矩阵。利用‘稀疏’特点进行存储和计算可以大大节省存储空间，提高效率。通过对稀疏矩阵的存储表示，实现矩阵的基本操作。
实验要求：文法是一个四元

1、要求矩阵的输入形式采用三元组表示，以“带行逻辑链接信息”的三元组顺序表表示稀疏矩阵。
2、设计矩阵的逆置算法，实现矩阵的逆置。
3、实现两个稀疏矩阵的相加、相减和相乘等运算。
4、要求运算结果的矩阵则以通常的数组形式出现。

实验内容和过程：
实验步骤
1、 首先应输入矩阵的行数和列数、并判别给出的两个矩阵的行、列数对于所要求的运算是否相匹配；
2、 以三元组的形式输入矩阵；
3、 调用矩阵的逆置子函数、相加函数和相乘函数；
4、 分析输出结果，并进行总结。

输入数据：2 1 0
0 0 0
0 0 3
2 0 0
1 0 0
0 0 3
-1

2 1 0
0 0 0
0 0 3
0 0 0
0 0 0
0 0 2
+
=
2 1 0
0 0 0
0 0 5

2 1 0
0 0 3
0 0
0 0
0 2
*
=
0 0
0 6

实验程序：
#include <iostream>
#include <iomanip>
using namespace std;
const int MAXSIZE=100;
const int MAXROW=10;
typedef struct {
int i,j;
int e;
}Triple;
typedef struct {
Triple data[MAXSIZE+1];
int mu,nu,tu;
}TSMatrix;
typedef struct {
Triple data[MAXSIZE+2];
int rpos[MAXROW+1];
int mu,nu,tu;
}RLSMatrix;
template <class P>
bool InPutTSMatrix(P & T,int y){
cout<<"输入矩阵的行，列和非零元素个数:"<<endl;
cin>>T.mu>>T.nu>>T.tu;
cout<<"请输出非零元素的位置和
值:"<<endl;
int k=1;
for(;k<=T.tu;k++)
cin>>T.data[k].i>>T.data[k].j>>T.data[k].e;

return true;
}
template <class P>
bool OutPutSMatrix(P T){
int m,n,k=1;
for(m=0;m<T.mu;m++){
for(n=0;n<T.nu;n++){
if((T.data[k].i-1)==m&&(T.data[k].j-1)==n){
cout.width(4);
cout<<T.data[k++].e;}
else{
cout.width(4); cout<<"0"; }
}
cout<<endl;
}
return true;
}
bool TransposeSMatrix( ){
TSMatrix M,T; //定义预转置的矩阵
InPutTSMatrix(M, 0); //输入矩阵
int num[MAXROW+1];
int cpot[MAXROW+1]; // 构建辅助数组
int q,p,t;
T.tu=M.tu; T.mu=M.nu; T.nu=M.mu;
if(T.tu){
for(int col=1;col<=M.nu;col++) num[col]=0;
for(t=1;t<=M.tu;t++) ++num[M.data[t].j];
cpot[1]=1;
for(int i=2;i<=M.nu;i++) cpot[i]=cpot[i-1]+num[i-1]; // 求出每一列中非零元素在三元组中出现的位置
for(p=1;p<=M.tu;p++){
col=M.data[p].j; q=cpot[col];
T.data[q].i=col; T.data[q].j=M.data[p].i;
T.data[q].e=M.data[p].e; ++cpot[col];
}
}
cout<<"输入矩阵的转置矩阵为"<<endl;
OutPutSMatrix(T);
return true;
}

bool Count(RLSMatrix &T)
{
int num[MAXROW+1];
for(int col=1;col<=T.mu;col++) num[col]=0;
for(col=1;col<=T.tu;col++) ++num[T.data[col].i];
T.rpos[1]=1;
for(int i=2;i<=T.mu;i++) T.rpos[i]=T.rpos[i-1]+num[i-1];
return true;
}
bool MultSMatrix ( ){
RLSMatrix M,N,Q;
InPutTSMatrix(M,1);
InPutTSMatrix(N,1);
Count(M); Count(N);
if(M.nu!=N.mu) return false;
Q.mu=M.mu; Q.nu=N.nu; Q.tu=0; // Q初始化
int ctemp[MAXROW+1];
int arow,tp,p,brow,t,q,ccol;
if(M.tu*N.tu){
for( arow=1;arow<=M.mu;arow++){
///memset(ctemp,0,N.nu);
for(int x=1;x<=N.nu;x++)
ctemp[x]=0;
Q.rpos[arow]=Q.tu+1;
if(arow<M.mu) tp=M.rpos[arow+1];
else tp=M.tu+1;
for(p=M.rpos[arow];p<tp;p++){

brow=M.data[p].j;
if(brow<N.mu) t=N.rpos[brow+1];
else t=N.tu+1;
for(q=N.rpos[brow];q<t;q++){
ccol=N.data[q].j;
ctemp[ccol] += M.data[p].e*N.data[q].e;
}
}
for(ccol=1;ccol<=Q.nu;ccol++)
if(ctemp[ccol]){
if(++Q.tu>MAXSIZE) return false;
Q.data[Q.tu].e=ctemp[ccol];
Q.data[Q.tu].i=arow;
Q.data[Q.tu].j=ccol;
}
}
}
OutPutSMatrix(Q);
return true;
}
typedef struct OLNode{
int i,j;
int e;
struct OLNode *right,*down;
}OLNode,*OLink;
typedef struct{
OLink *rhead,*chead;
int mu,nu,tu;
}CrossList;
bool CreateSMatrix_OL(CrossList & M){
int x,y,m;
cout<<"请输入矩阵的行，列，及非零元素个数"<<endl;
cin>>M.mu>>M.nu>>M.tu;
if(!(M.rhead=(OLink*)malloc((M.mu+1)*sizeof(OLink)))) exit(0);
if(!(M.chead=(OLink*)malloc((M.nu+1)*sizeof(OLink)))) exit(0);
for(x=0;x<=M.mu;x++)
M.rhead[x]=NULL; /
for(x=0;x<=M.nu;x++)
M.chead[x]=NULL;
cout<<"请按三元组的格式输入数组："<<endl;
for(int i=1;i<=M.tu;i++){
cin>>x>>y>>m;
OLink p,q;
if(!(p=(OLink)malloc(sizeof(OLNode)))) exit(0);
p->i=x; p->j=y; p->e=m;
if(M.rhead[x]==NULL||M.rhead[x]->j>y){
p->right=M.rhead[x]; M.rhead[x]=p;
}
else{
for(q=M.rhead[x];(q->right)&&(q->right->j<y);q=q->right);
p->right=q->right; q->right=p; // 完成行插入
}
if(M.chead[y]==NULL||M.chead[y]->i>x){
p->down=M.chead[y]; M.chead[y]=p;
}
else{
for(q=M.chead[y];(q->down)&&(q->down->i<x);q=q->down);
p->down=q->down; q->down=p; // 完成列插入

}
}
return true;
}
bool OutPutSMatrix_OL(CrossList T){
for(int i=1;i<=T.mu;i++){
OLink p=T.rhead[i];
for(int j=1;j<=T.nu;j++){
if((p)&&(j==p->j)){
cout<<setw(3)<<p->e; p=p->right;
}
else
cout<<setw(3)<<"0";
}
cout<<endl;
}
return true;
}
bool AddSMatrix(){
CrossList M,N;
CreateSMatrix_OL(M);
CreateSMatrix_OL(N);
cout<<"输入的两矩阵的和矩阵为："<<endl;
OLink pa,pb,pre ,hl[MAXROW+1]; /
for(int x=1;x<=M.nu;x++) hl[x]=M.chead[x];
for(int k=1;k<=M.mu;k++){
pa=M.rhead[k]; pb=N.rhead[k]; pre=NULL;
while(pb){
OLink p;
if(!(p=(OLink)malloc(sizeof(OLNode)))) exit(0);
p->e=pb->e; p->i=pb->i; p->j=pb->j;
if(NULL==pa||pa->j>pb->j){
if(NULL==pre)
M.rhead[p->i]=p;
else
pre->right=p;
p->right=pa; pre=p;
if(NULL==M.chead[p->j]){
M.chead[p->j]=p; p->down=NULL;
}
else{
p->down=hl[p->j]->down; hl[p->j]->down=p;
}
hl[p->j]=p;
pb=pb->right;
}
else
if((NULL!=pa)&&pa->j<pb->j){
pre=pa; pa=pa->right;
}
else
if(pa->j==pb->j){
pa->e += pb->e;
if(!pa->e){
if(NULL==pre)
M.rhead[pa->i]=pa->right;

else
pre->right=pa->right;
p=pa; pa=pa->right;
if(M.chead[p->j]==p) M.chead[p->j]=hl[p->j]=p->down;
else
hl[p->j]->down=p->down;
free(p); pb=pb->right;
}
else{
pa=pa->right; pb=pb->right;
}
}
}
}
OutPutSMatrix_OL(M);
return true;
}
int main(){
cout.fill(' ');
// system("color 0C");
cout.fill(' ');
cout<<"请选择要进行的操作："<<endl;
cout<<"1:矩阵的转置"<<endl;
cout<<"2:矩阵的加法或减法"<<endl;
cout<<"3:矩阵的乘法"<<endl;
cout<<"4:退出程序"<<endl;
char c=getchar();
if(c=='1')
TransposeSMatrix( );
else
if(c=='2')
AddSMatrix();
else
if(c=='3')
MultSMatrix (); /
else
exit(0); //退出
return 0;
}

实验结果：
矩阵的逆置

矩阵的加减法

矩阵的乘法

思考题
1、 如何提高矩阵转置算法效率？

#include <iostream.h>
void main(void){
const int SIZE=11;
int grid[SIZE][SIZE];
int gridT[SIZE][SIZE];
int i,j;
for(i=0;i<SIZE;i++){
for(j=0;j<SIZE;j++){
cout<<"Input the Value of "<<i<<" , "<<j<<endl;
cin>>grid[i][j];
}
}

for(i=0;i<SIZE;i++){
for(j=0;j<SIZE;j++){
gridT[i][j]=grid[j][i];
}
}
cout<<"原始矩阵"<<endl;
for(i=0;i<SIZE;i++){
for(j=0;j<SIZE;j++){
cout<<grid[i][j]<<" ";
}
cout<<endl;
}

cout<<"转置矩阵"<<endl;
for(i=0;i<SIZE;i++){
for(j=0;j<SIZE;j++){
cout<<gridT[i][j]<<" ";
}
cout<<endl;
}

}

2、 如果用十字链表方式表示稀疏矩阵的话，如何来实现矩阵的相加操作呢？

总结和感想：
通过实验，我数组的存储表示和实现技术，对矩阵的逆置、矩阵的加减运算和乘除运算有更深的了解，能熟练运用矩阵进行相关的操作。