当前位置:首页 >> 理学 >>

数据结构课程设计之稀疏矩阵实现与应用1


数据结构课程设计报告
题目:十字链表成为存储结构,实现稀疏矩阵的求和运算 学生姓名:张旋 班级:软件三班 学号:201213040304 指导教师: 吴小平

一、需求分析
1.问题描述:
要求:十字链表下的稀疏矩阵的加、转、乘的实现。

2.基本功能
实现十字链表下的转置,乘法,加法运算。

3.输入输出
(1)设计函数建立稀疏矩阵,初始化值。 (2)设计函数输出稀疏矩阵的值。 (3)构造函数进行两个稀疏矩阵相加,输出最终的稀疏矩阵。 (4)构造函数进行两个稀疏矩阵的相乘,输出最终的稀疏矩阵。 (5)构造函数进行稀疏矩阵的转置,并输出结果。 (6)退出系统。

二、 概要设计
1.设计思路:
本实验要求在三元组,十字链表下实现稀疏矩阵的加、转、乘。首先要进行矩阵的初 始化操作,定义三元组和十字链表的元素对象。写出转置,加法,乘法的操作函数。通过主 函数调用实现在一个程序下进行矩阵的运算操作。

2.数据结构设计:
抽象数据类型稀疏矩阵的定义如下: ADT SparseMatrix{ 数据对象:D={aij | i=1,2,…,m; j=1,2,..,n; aij∈Elemset, m和n分别称为矩阵的行数和列数。} 数据关系:R={Row,Col} Row={<ai,j , ai,j+1> | 1<=i<=m, 1<=j<=n-1} Col= {<ai,j , ai+1,j> | 1<=i<=m-1, 1<=j<=n} 基本操作: CreateSMatrix(&M); 操作结果:创建稀疏矩阵M。 DestroySMatrix(&M); 初始条件:稀疏矩阵M存在。 操作结果:销毁稀疏矩阵M。 PrintSMatrix(M); 初始条件:稀疏矩阵M存在。 操作结果:输出稀疏矩阵M。 AddSMatrix(M,N,&Q); 初始条件:稀疏矩阵M与N的行数和列数对应相等 操作结果:求稀疏矩阵的和 Q=M+N。 MultSMatrix(M,N,&Q); 初始条件:稀疏矩阵M的列数等于N的行数。 操作结果:求稀疏矩阵乘积Q=M*N。 TransposeSMatrix(M,&T); 初始条件:稀疏矩阵M存在。 操作结果:求稀疏矩阵M的转置矩阵T。 }ADT SparseMatrix

3.软件结构设计:

(1)主程序模块: Void main(){ 初始化; do { 接受命令; 处理命令; }while( “命令”=“退出” ) ; } (2)稀疏矩阵模块 { 实现矩阵的相加 bool AddSMatrix(); 实现矩阵的相乘 bool MultSMatrix(); 实验矩阵的转置 bool TransposeSMatrix(); } (3)十字链表模块 { 创建十字链表 bool CreateSMatrix_OL(CrossList & M); 输出十字链表 bool OutPutSMatrix_OL(CrossList T); } (4) 主程序模块

稀疏矩阵模块

十字链表模块

三、 详细设计
1. 定义程序中所有用到的数据及其数据结构,及其基本操作的实现;
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; // 定义带链接信息的三元组对象 typedef struct OLNode { // 定义十字链表元素 int i, j; int e; struct OLNode *right, *down; // 该非零元所在行表和列表的后继元素 } OLNode, *OLink; // 定义十字链表元素 typedef struct { // 定义十字链表对象结构体 OLink *rhead, *chead; int mu, nu, tu; // 系数矩阵的行数,列数,和非零元素个数 } CrossList; // 定义十字链表对象结构体

2.主函数
int main() { int t; cout.fill('*'); cout << setw(80) << '*'; cout.fill(' '); cout << setw(50) << "***欢迎使用矩阵运算程序***" << endl; //输出头菜单 cout.fill('*'); cout << setw(80) << '*'; cout.fill(' '); cout << " 请选择要进行的操作:" << endl; cout << " 1:矩阵的转置。" << endl; cout << " 2:矩阵的加法。" << endl; cout << " 3:矩阵的乘法。" << endl; cout << " 4:退出程序。" << endl; while(t) { cout<<"请输入您要进行的操作:"<<endl; cin>>t; switch(t) { case 1: TransposeSMatrix(); //调用矩阵转置函数 break; case 2: AddSMatrix(); //调用矩阵相加函数 break; case 3: MultSMatrix(); //调用矩阵相乘函数 break;

case 4: t=0; break; } } return 0; }

矩阵的转置函数
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++) { int col = M.data[p].j; q = cpot[col]; T.data[q].i = M.data[p].j; 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 row = 1; row <= T.mu; row++) num[row] = 0; for (int 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); cout << "输入的两矩阵的乘矩阵为:" << endl; 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) // Q是非零矩阵 { 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; // 当前行的首个非零元素在三元组中的位置 为此行前所有非零元素+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; // 在N中找到i值也操作元素的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++) // 对已经求出的累加器中的值 压缩到Q中 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; }

矩阵的加法函数
bool AddSMatrix() //矩阵的加法 { CrossList M, N; // 创建两个十字链表对象,并初始化 CreateSMatrix_OL(M); CreateSMatrix_OL(N); cout << "输入的两矩阵的和矩阵为:" << endl; OLink pa, pb, pre, hl[MAXROW + 1]; //定义辅助指针,pa,pb分别为M,N当前比较 的元素,pre为pa的前驱元素 for (int x = 1; x <= M.nu; x++) hl[x] = M.chead[x]; for (int k = 1; k <= M.mu; k++) // 对M的每一行进行操作 { pa = M.rhead[k]; pb = N.rhead[k]; pre = NULL; while (pb) // 把N中此行的每个元素取出 { OLink p; if (!(p = (OLink) malloc(sizeof (OLNode)))) exit(0); // 开辟新节 点,存储N中取出的元素 p->e = pb->e; p->i = pb->i; p->j = pb->j; if (NULL == pa || pa->j > pb->j) // 当M此行已经检查完或者pb因该放 在pa前面 {

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) // 如果此时的pb元素因该放 在pa后面,则取以后的pa再来比较 { pre = pa; pa = pa->right; } else if (pa->j == pb->j) // 如果pa,pb位于同一个位置上,则将值相加 { pa->e += pb->e; if (!pa->e) { // 如果相加后的和为0,则删除此节点,同时改变此元素坐在行,列的 前驱元素的相应值 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; }

创建十字链表
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; // 初始化各行,列头指针,分别为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; }

3.主要函数的程序流程图,实现设计中主程序和其他子模块的算法,以流程 图的形式表示。

矩阵的相加流程图

矩阵的相乘流程图

开始

开始

CrossList M, N; CreateSMatrix_OL(M); CreateSMatrix_OL(N);

RLSMatrix M, N, Q; InPutTSMatrix(M, 1); InPutTSMatrix(N, 1);

对应位置相加

int ctemp[MAXROW + 1]; int arow, tp, p, brow, t, q, ccol;

输出结果

Q.mu = M.mu; Q.nu = N.nu; Q.tu = 0;

结束

实现矩阵的相乘

结束

矩阵转置的流程图
开始

主函数流程图
开始

TSMatrix M, T; InPutTSMatrix(M,0);

输出界面

int num[MAXROW + 1]; int cpot[MAXROW + 1];

int i;

T.tu = M.tu; T.mu = M.nu; T.nu = M.mu;

输入i

i T.tu 是 实现转置 否 TransposeSMatrix(); AddSMatrix(); MultSMatrix();

OutPutSMatrix(T) 结束 结束

4. 画出函数之间的调用关系图。
Main

AddSMatrix

TransposeSMatrix

MultSMatrix

CreateSMatrix_OL OutPutSMatrix_OL

InPutTSMatrix

OutPutSMatrix

InPutTSMatrix

四、 调试分析
1.实际完成的情况说明(完成的功能,支持的数据类型等);
完成了稀疏矩阵的建立,初始化及输出值的操作。 实现三元组,十字链表下的稀疏矩阵的加法,乘法以及转置运算。

2.程序的性能分析,包括时空分析;
能应对一般小的错误输入,如果复杂则自动退出程序

3.上机过程中出现的问题及其解决方案; 1.起始有错误,设定的变量名相同。经检查,改正。
2.一些逻辑错误。经讨论改正。运行出现部分语法错误修正

4.程序中可以改进的地方说明;
程序在运行中一旦出现矩阵数据格式错误如输入汉字, 则程序自动退出。 需要重新启动。 更新程序对更多错误输入情况的分析能力。

5.程序中可以扩充的功能及设计实现假想。
对退出操作的扩充 在主菜单下,用户输入4回车选择退出程序是,询问是否真的退出系统,如果是,则即退 出系统,否则显示??continue??并且返回主菜单。为了方便由于误按导致程序退出。 在退出时可以增加一段感谢使用本程序的结束语。

五、测试结果
系统运行主界面

输入需要执行的操作1矩阵的转置

输入需要执行的操作2矩阵的加法

输入需要执行的操作3矩阵的乘法

输入错误操作时需要重新选择

退出操作

六、用户手册
1.本程序执行文件为:crosslist.exe 2.进入本系统之后,随即显示系统主菜单界面。用户可在该界面下输入各子菜单前对应的 数字并按回车,执行相应子菜单命令

3.执行操作时,按要求输入数字。彼此之间用空格隔开。 4.执行加法运算时,输入的两个矩阵的行必须相同,列数也必须相同。这是基本的矩阵运 算常识。 5.执行乘法运算时,第一个矩阵的行数和第二个矩阵的列数相同。 6.当输入错误时请尝试退出程序重新运行。请尽量遵守矩阵运算的规则输入有效的运算。

七、体会与自我评价
我选的上机题目是实现三元组,十字链表下的转置,乘法,加法运算。 对这个题目,我觉得有点难,因为我们数据结构这一部分并没有讲,可是选题必 须是每人选择一个不许选重。有点无奈吧,当作是考验了。各种资料收集,各种 代码整合。各种错误。虽然上机的时间只有短短两个星期,但从中学到了不少知 识。数据结构可以说是计算机里一门基础课程,对于以后的学习尤为重要。所以 我们一定要把基础学扎实, 这两周的上机帮我们重新巩固基础知识,提高了我们 专业的动手实践能力。 在实践的过程中我们应当有良好的规划,每天完成一小部分。尽量减少操 作的盲目性,提高我们学习的效率。有个总体的大纲来逐步实现。我也曾经犯过 这种错误。每个函数都做出来部分。结果都没做完。所以计划很重要 在实验中我们要培养自己独立的思考能力和解决问题的能力。 培养这种能 力主要看我们对待这次实验的态度。 我们要把它当作以后工作时接的项目一样认 真对待。 积极的朝着更好地一面发展不断的完善程序。不能马马虎虎随便应付一 下。 通过这次实验我也认识到了数据结构这门课程的重要性,以及 C 语言功能 的强大。它可以令计算机执行各种你想要的操作。当然前提是你的技术水平。使 我深刻的认识到要学好数据结构这门课程,为了以后打好坚实的基础。提高自己 的动手实践能力,把所学的理论知识和实践相结合。就像古人云,纸上得来终觉 浅,得知此事要躬行。为了以后的计算机道路。不断的提高自身的专业素养。奋 斗。 也希望在今后的学习生活中向老师学到更多的知识。不断的充实自己。努 力改正自己的坏毛病,做个奋发向上的大学生。

源代码:
#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; // 定义带链接信息的三元组对象 typedef struct OLNode { // 定义十字链表元素 int i, j; int e; struct OLNode *right, *down; // 该非零元所在行表和列表的后继元素 } OLNode, *OLink; // 定义十字链表元素 typedef struct { // 定义十字链表对象结构体 OLink *rhead, *chead; int mu, nu, tu; // 系数矩阵的行数,列数,和非零元素个数 } CrossList; // 定义十字链表对象结构体 template <class P> bool InPutTSMatrix(P & T, int y) { //输入矩阵,按三元组格式输入 cout << "输入矩阵的行,列和非零元素个数:" << endl; cin >> T.mu >> T.nu >> T.tu; cout << "请输出非零元素的位置和值:" << endl; for (int k = 1; 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++) { int col = M.data[p].j; q = cpot[col]; T.data[q].i = M.data[p].j; 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 row = 1; row <= T.mu; row++) num[row] = 0; for (int 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); cout << "输入的两矩阵的乘矩阵为:" << endl; 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) // Q 是非零矩阵 { 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; // 当前行的首个非零元素在三元组中的位置为此行 前所有非零元素+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; // 在 N 中找到 i 值也操作元素的 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++) // 对已经求出的累加器中的值压缩到 Q 中 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; } 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; // 初始化各行,列头指针,分别为 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]; //定义辅助指针, pa, pb 分别为 M,N 当前比较的元素, pre 为 pa 的前驱元素 for (int x = 1; x <= M.nu; x++) hl[x] = M.chead[x]; for (int k = 1; k <= M.mu; k++) // 对 M 的每一行进行操作 { pa = M.rhead[k]; pb = N.rhead[k]; pre = NULL; while (pb) // 把 N 中此行的每个元素取出 { 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) // 当 M 此行已经检查完或者 pb 因该放在 pa 前 面 { 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; } 开辟新节点, 存储 N 中取出

hl[p->j] = p; pb = pb->right; } else if ((NULL != pa) && pa->j < pb->j) // 如果此时的 pb 元素因该放在 pa 后面, 则取以后的 pa 再来比较 { pre = pa; pa = pa->right; } else if (pa->j == pb->j) // 如果 pa,pb 位于同一个位置上,则将值相加 { pa->e += pb->e; if (!pa->e) { // 如果相加后的和为 0,则删除此节点,同时改变此元素坐在行,列的 前驱元素的相应值 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()

{ int t; cout.fill('*'); cout << setw(80) << '*'; cout.fill(' '); cout << setw(50) << "***欢迎使用矩阵运算程序***" << endl; //输出头菜单 cout.fill('*'); cout << setw(80) << '*'; cout.fill(' '); cout << " cout << " cout << " cout << " cout << " while(t) { 请选择要进行的操作:" << endl; 1:矩阵的转置。" << endl; 2:矩阵的加法。" << endl; 3:矩阵的乘法。" << endl; 4:退出程序。" << endl;

cout<<"请输入您要进行的操作:"<<endl; cin>>t; switch(t) { case 1: TransposeSMatrix(); //调用矩阵转置函数 break; case 2: AddSMatrix(); //调用矩阵相加函数 break; case 3: MultSMatrix(); //调用矩阵相乘函数 break; case 4: t=0; break; } } return 0; }


赞助商链接
相关文章:
实验报告---数据结构课程设计稀疏矩阵的应用
在此基础上用 C/C++实现其操作。 五、进度安排按教学计划规定,数据结构课程设计为 2 周,其进度及时间大致分配如下: 稀疏矩阵应用 序号 1 2 3 4 5 设计...
数据结构课程设计(稀疏矩阵运算器)
数据结构课程设计(稀疏矩阵运算器)_工学_高等教育_教育专区。【问题描述】稀疏矩阵...实现一个能进行稀疏矩阵基本运算的运 算器。 2.【基本要求 基本要求】 基本...
数据结构课程设计(稀疏矩阵运算器)
课程设计报告 ***大学 数据结构课程设计说明书 题 目:稀疏矩阵运算器 学生姓名: 学专班号: 业: 级: 指导教师: 2013 年 7 月 24 日 1 / 33 课程设计...
数据结构课程设计题目 (1)
数据结构课程设计题目 (1)_其它课程_高中教育_教育...可以实现如下功能: 录入:可以录入航班情况(数据可以...实现用三元组表示法实现稀疏矩阵相加及转置算法 3. ...
数据结构课程设计 报告 (十字链表实现稀疏矩阵的加法)
、问题描述 十字链表实现稀疏矩阵的加法 1、 功能要求:根据用户输入的矩阵,实现稀疏矩阵的求和运算,并输出结果。 2、 输入要求:矩阵的数据在程序运行的时候由...
数据结构稀疏矩阵课程设计报告
数据结构课程设计报告:稀疏矩阵应用包括三元组表下稀疏矩阵的创建,以及加、乘...1 月 8 日 ***大学一、问题概述、分析及研究意义 问题概述:实现三元组下的...
稀疏矩阵(算法与数据结构课程设计)
稀疏矩阵(算法与数据结构课程设计)_工学_高等教育_教育专区。算法与数据结构课程...通过本次实验实现稀疏矩阵的转置、加法和乘法 等多种运算。 二、基本要求 1、...
数据结构课程设计论文,稀疏矩阵的转置
数据结构课程设计 课程设计任务书学生姓名: 学生姓名: 李敏龙 指导教师: 指导教师: 严宇题目: 稀疏矩阵的转置 初始条件: 初始条件:(1)稀疏矩阵采用三元组...
数据结构课程设计41号李家福
数据结构课程设计稀疏矩阵运算器 班级: 10班级:计算机应用 10-1 班 学号: 学号: 姓名: 姓名: 10602101041 李家福 20112011-12-27 1、设计综述 用三元组实现稀...
数据结构C语言版-稀疏矩阵三元组的基本操作
熟练掌握数据结构的知识,利用C语言,用三元组表示稀疏矩阵,并实现稀疏矩阵的加减,...1.2 课程设计的目的巩固和深刻理解―数据结构(C 语言版)‖课程所讲解的 C ...
更多相关标签: