稀疏矩阵运算器（数据结构）.docx

发布时间：2022-06-08 发布人：admin 分类：说明书资料大小：0.21M 资料格式：docx 举报版权申诉

u010883062-8360615-4744300845367074627.docx.pdf-第1页.png

第1页 / 共13页

u010883062-8360615-4744300845367074627.docx.pdf-第2页.png

第2页 / 共13页

u010883062-8360615-4744300845367074627.docx.pdf-第3页.png

第3页 / 共13页

u010883062-8360615-4744300845367074627.docx.pdf-第4页.png

第4页 / 共13页

u010883062-8360615-4744300845367074627.docx.pdf-第5页.png

第5页 / 共13页

u010883062-8360615-4744300845367074627.docx.pdf-第6页.png

第6页 / 共13页

u010883062-8360615-4744300845367074627.docx.pdf-第7页.png

第7页 / 共13页

u010883062-8360615-4744300845367074627.docx.pdf-第8页.png

第8页 / 共13页

1．抽象数据类型：

2. 本程序有二个模块：

《数据结构》实验报告题学专班学姓成稀疏矩阵运算器目计算机学院院网络工程业别 12 级( 4)班号名绩 2014 年 06 月 22 日

稀疏矩阵运算器一．需求分析输入要求：稀疏矩阵的行、列和非零元素个数以及每个非零元素在矩阵的位置以三元组格式存储稀疏矩阵输出要求：根据选项输出稀疏矩阵的转置、加法、减法、乘法二．算法设计本程序中采用的数据模型，用到的抽象数据类型的定义，程序的主要算法流程及各模块之间的层次调用关系 1．抽象数据类型：基本操作 : Status CreateSMatrix(TSMatrix &M) 操作结果：初始化稀疏数组 void PrintSMatrix(TSMatrix M) 初始条件：稀疏数组 M 已经存在操作结果：打印矩阵 M Status AddSMatrix(TSMatrix M, TSMatrix N, TSMatrix &Q) 初始条件：稀疏数组 M 、 N 已经存在操作结果：求矩阵的和 Q=M+N Status SubSMatrix(TSMatrix M, TSMatrix N, TSMatrix &Q) 初始条件：稀疏数组 M 、 N 已经存在操作结果：求矩阵的差 Q=M-N Status TransposeSMatrix(TSMatrix M, TSMatrix & T) 初始条件：稀疏数组 M 已经存在操作结果：求矩阵 M 的转置 T Status MultSMatrix(TSMatrix M, TSMatrix N, TSMatrix &Q) 初始条件：稀疏数组 M 已经存在操作结果：求矩阵的积 Q=M*N }ADT List 2. 本程序有二个模块：（ 1）主程序模块 main() { 初始化；输出菜单，命令提示； { 接受命令；显示结果；

｝｝（ 2）三元组表单元模块：实现矩阵抽象数据类型。三．程序设计根据算法设计中给出的有关数据和算法，选定物理结构，详细设计需求分析中所要求的程序。包括：人机界面设计、主要功能的函数设计、函数之间调用关系描述等。程序基本结构： MAIN 功能选择 ADD SUB MUL Trans 矩阵输出 Triple; // 定义三元组的元素 TSMatrix; // 定义普通三元组对象 RLSMatrix; // 定义带链接信息的三元组对象 CrossList; // 定义十字链表对象结构体

2、稀疏矩阵的三元组顺序表存储表示： 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 { OLink *rhead, *chead; int mu, nu, tu; } CrossList; //定义十字链表对象结构体 3、基本函数： 1) 输入矩阵，按三元组格式输入 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; }

2）输出矩阵，按标准格式输出 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; } 3）创建十字链表 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; 创建十字链表 }// 4）按标准输出十字链表 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; cout << setw(3) << "0"; } else } cout << endl; } return true; }// 输出十字链表 5）求矩阵的转置矩阵 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 = 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; } 6）两个矩阵相乘 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) { // 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++) // 对已经求出的累加器中的值压

分享到：

赞收藏

资料库

稀疏矩阵运算器（数据结构）.docx

相关推荐

课程资源

热门标签

最新资料