数据结构实验(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
#include
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
bool InPutTSMatrix(P & T,int y){
cout<<"输入矩阵的行，列和非零元素个数:"<>T.mu>>T.nu>>T.tu;
cout<<"请输出非零元素的位置和
值:"<
for(;k<=T.tu;k++)
cin>>T.data[k].i>>T.data[k].j>>T.data[k].e;

return true;
}
template
bool OutPutSMatrix(P T){
int m,n,k=1;
for(m=0;mwidth(4); cout<<"0"; }
}
cout<ol]=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<<"输入矩阵的转置矩阵为"<
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.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<<"请输入矩阵的行，列，及非零元素个数"<>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<<"请按三元组的格式输入数组："<>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->jright);
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->idown);
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<e; p=p->right;
}
else

cout< 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->downNULL;
}
else{
p->down=hl[p->j]->down; hl[p->j]->down=p;
}
hl[p->j]=p;
pb=pb->right;
}
else
if((NULL!=pa)&&pa->jj){
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<<"请选择要进行的操作："<return 0;
}

实验结果：
矩阵的逆置

矩阵的加减法

矩阵的乘法

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

#include
void main(void){
const int SIZE=11;
int grid[SIZE][SIZE];
int gridT[SIZE][SIZE];
int i,j;
for(i=0;i
cin>>grid[i][j];
}
}

for(i=0;i