数据结构课设报告—稀疏矩阵转置和乘法

数据结构课程设计,稀疏矩阵转置和乘法

燕山大学

课 程 设 计 说 明 书

题目：稀疏矩阵的转置和乘法

学院（系）： 理学院 年级专业： 12级信息一班、二班 学 号： 120108010002 学生姓名： 吴中原 学 号： 120108010004 学生姓名： 黄志豪 学 号： 120108010050 学生姓名： 李红旭

指导教师： 教师职称：

数据结构课程设计,稀疏矩阵转置和乘法

燕山大学课程设计（论文）任务书

院（系）： 理学院 基层教学单位：

说明：此表一式四份，学生、指导教师、基层教学单位、系部各一份。

年 月 日

数据结构课程设计,稀疏矩阵转置和乘法

燕山大学课程设计评审意见表

数据结构课程设计,稀疏矩阵转置和乘法

一：课设内容

建立稀疏矩阵的三元组顺序表，实现稀疏矩阵的转置。->建立行逻辑链接顺序表，实现稀疏矩阵乘法。 二：课设步骤

小组讨论—>查阅资料—>编写代码—>完成设计报告—>制作PPT—>准备答辩 三：算法思想 转置算法一

基本思想：在A的三元组顺序表a.data中依次找第1列、第2列、…, 直到最后一列的三元组，并将找到的每个三元组的行、列交换后顺序存储到B的三元组顺序表b.data中。 转置算法二

基本思想：顺序取，直接存。

即在a.data中依次取三元组，交换其行号和列号放到b.data中适当位置。

乘法基本思想：修改前述的稀疏矩阵的结构定义，增加一个数据成员rpos，指示各行第一个非零元的位置，其值在稀疏矩阵的初始化函数中确定。 四：程序代码与结果显示 稀疏矩阵转置： #include<iostream> using namespace std;

//——三元组顺序表的类型定义——// #define MAXSIZE 12500 typedef struct {

int row,col; int item; }Triple; typedef struct {

Triple *data;//data[0]不用

int mu,nu,tu;//分别表示行数、列数和非零元素个数 }thMatrix;

//——初始化三元组表——// void initMatrix_Th(thMatrix &M) {

M.data=new Triple[MAXSIZE+1]; M.mu=0; M.nu=0; M.tu=0; }

//——转置三元组表——//

//一般方法，算法时间复杂度较高

void transMatrix_1(thMatrix M,thMatrix &T)

数据结构课程设计,稀疏矩阵转置和乘法

{

initMatrix_Th(T); T.mu=M.nu; T.nu=M.mu; T.tu=M.tu; if(T.tu) { int p=1;//用来指M中的元素 int q=1;//用来指T中的元素 int col;//用来遍历列中的元素 for(col=1;col<=M.nu;col++) { for(p;p<=M.tu;p++) { if(M.data[p].col==col) { T.data[q].row=M.data[p].col; T.data[q].col=M.data[p].row; T.data[q].item=M.data[p].item; q++; } } } } }

//——改进的方法—快速转置——//

void transMatrix_2(thMatrix M,thMatrix &T) { initMatrix_Th(T); T.mu=M.nu; T.nu=M.mu; T.tu=M.tu; int i,j,p,q; int num[100]; int cpot[100]; if(T.tu) { for(i=1;i<=M.nu;i++) num[i]=0;//M中每一列的非零元素个数初始化为0 for(i=1;i<=M.tu;i++) ++num[M.data[i].col];//M中每一列的非零元素个数存储到一个数组中

数据结构课程设计,稀疏矩阵转置和乘法

cpot[1]=1; for(i=2;i<=M.nu;i++) cpot[i]=cpot[i-1]+num[i-1];//每一列第一个非零元素的位置 for(p=1;p<=M.tu;p++) { j=M.data[p].col;

q=cpot[j];//确定第j列第一个非零元素的位置 T.data[q].row=M.data[p].col; T.data[q].col=M.data[p].row; T.data[q].item=M.data[p].item; ++cpot[j];//指向下一个位置 } } }

//——创建一个三元组表——// //——按行优先存储——// int creatMatrix(thMatrix &M) { initMatrix_Th(M); int i;

cout<<"输入稀疏矩阵的行数、列数以及非零元的个数:"<<endl; cin>>M.mu>>M.nu>>M.tu; if(M.tu==0)

cout<<"按行序输入"<<M.tu<<"个非零元素的三元组:"<<endl; for(i=1;i<=M.tu;i++) { cout<<"输入第"<<i<<"个非零元素的行号、列号和元素值:"<<endl; cin>>M.data[i].row>>M.data[i].col>>M.data[i].item; } return 0; }

//——输出一个三元组表——// void outputMatrix(thMatrix M) { int i;

cout<<M.mu<<" "<<M.nu<<" "<<M.tu<<endl; cout<<endl;

for(i=1;i<=M.tu;i++) { cout<<M.data[i].row<<" "<<M.data[i].col<<" "<<M.data[i].item<<endl; }

数据结构课程设计,稀疏矩阵转置和乘法

}

int main() { thMatrix M; thMatrix T; creatMatrix(M); cout<<"原始矩阵M为:"<<endl; outputMatrix(M); transMatrix_2(M,T);

cout<<"转置矩阵T为:"<<endl; outputMatrix(T); return 0;

}

数据结构课程设计,稀疏矩阵转置和乘法

稀疏矩阵乘法： #include<iostream> using namespace std;

//——三元组顺序表的类型定义——// #define OK 1 #define ERROR 0

#define OVERFLOW 0 #define MAXSIZE 100 typedef int Status; typedef struct { int row,col; int e; }Triple;

#define MAXMN 500 //假设矩阵行数和列数的最大值为500 typedef struct{ Triple data[MAXSIZE+1];//非零元三元组表，data[0]未用 int rpos[MAXMN + 1];//指示各行第一个非零元的位置

int mu,nu,tu; //矩阵的行数、列数和非零元个数 }RLSMatrix; //行逻辑链接顺序表类型

Status MultSMatrix(RLSMatrix A,RLSMatrix B,RLSMatrix &C){ int ctemp[100]; int arow,p,brow,t,q,ccol,tp; if(A.nu!=B.mu)return ERROR; C.mu=A.mu;C.nu=B.nu;C.tu=0; if(A.tu*B.tu!=0){ //C是非零矩阵 for(arow=1;arow<=A.mu;++arow){ for(int i=0;i<=B.nu;i++) ctemp[i]=0; //当前行各元素累加器清零 C.rpos[arow]=C.tu+1; if(arow<A.mu)tp=A.rpos[arow+1]; else{tp=A.tu+1;} for(p=A.rpos[arow];p<A.rpos[arow+1];++p){//对当前行中每一个非零元 brow=A.data[p].col; //找到对应元在B中的行号 if(brow<B.mu)t=B.rpos[brow+1]; else{t=B.tu+1;} for(q=B.rpos[brow];q<t;++q){ ccol=B.data[q].col; //乘积元素在C中列号 ctemp[ccol]+=A.data[p].e*B.data[q].e; } //for q } //for p:求得C中第crow(=arow)行的非零元

数据结构课程设计,稀疏矩阵转置和乘法

for(ccol=1;ccol<=C.nu;++ccol) //压缩存储该行非零元 if(ctemp[ccol]){ if(++C.tu>MAXSIZE) return ERROR; else{ C.data[C.mu].row=arow; C.data[C.nu].col=ccol; C.data[C.tu].e=ctemp[ccol];} } } } return OK; }

//——按行优先存储——//

int creatRLSMatrix(RLSMatrix &M) { int i;

cout<<"输入稀疏矩阵的行数、列数以及非零元的个数:"<<endl; cin>>M.mu>>M.nu>>M.tu; if(M.tu!=0)

cout<<"按行序输入"<<M.tu<<"个非零元素的三元组:"<<endl; for(i=1;i<=M.tu;i++) { cout<<"输入第"<<i<<"个非零元素的行号、列号和元素值:"<<endl; cin>>M.data[i].row>>M.data[i].col>>M.data[i].e; } return 0; }

//——输出一个三元组表——//

void outputRLSMatrix(RLSMatrix M) { int i;

cout<<M.mu<<" "<<M.nu<<" "<<M.tu<<endl; cout<<endl;

for(i=1;i<=M.tu;i++) { cout<<M.data[i].row<<" "<<M.data[i].col<<" "<<M.data[i].e<<endl; } }

int main() { RLSMatrix A;

数据结构课程设计,稀疏矩阵转置和乘法

RLSMatrix B; RLSMatrix C;

creatRLSMatrix(A); cout<<"原始矩阵A为:"<<endl; outputRLSMatrix(A); creatRLSMatrix(B); cout<<"原始矩阵B为:"<<endl; outputRLSMatrix(B); MultSMatrix(A,B,C); cout<<"乘积矩阵C为:"<<endl; outputRLSMatrix(C); return 0;

}

数据结构课程设计,稀疏矩阵转置和乘法

五：成员分工

六：收获体会

通过这次课程设计，我们更深层的体会到了数据结构的用处，特别是在现实生活中的用处；更加牢固地掌握了关于数组、三元组以及稀疏矩阵的数据结构知识，并且能够熟练的运用到实际当中；同时，我们也增强了我们三个人彼此的了解，以及之间的熟悉程度、默契程度，我们同心协力，不留余力的一起完成任务。在这次课设中，组员之间互帮互助，像组长吴中原，基础比较好，所以他就担任了绝大部分编程任务并且悉心给组员讲清每一步过程，让其他两个组员都有了深切的认识和了解。当然我们两个用心学习，尽力把这次课设做好。

总之，通过这次课程设计，我们对数据结构的有关知识掌握更加的全面和牢固，我相信通过这次课程设计会让我们变得更好，对知识的了解也会进一步加深。

本文来源：https://www.bwwdw.com/article/2if1.html