《2022年数据结构实验四题目和源程序 .pdf》由会员分享，可在线阅读，更多相关《2022年数据结构实验四题目和源程序 .pdf（6页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、实验 4：矩阵的压缩存储及相关操作(第 11周星期三 7、8 节) 一 、实验目的1掌握下三角矩阵的输入、输出、转置算法。2理解稀疏矩阵的三元组表类型定义，掌握稀疏矩阵的输入、输出、转置算法。二 、实验要求1认真阅读和掌握本实验的算法思想。2编写完整程序完成下面的实验内容并上机运行。三、实验内容1所谓上（下）三角矩阵是指矩阵的下（上）三角中的元素均为常数或零的 n 阶矩阵。此时除了存储上（下）三角矩阵中的元素之外再加一个存储常数的空间即可。三角矩阵中的重复元素c 可共享一个存储空间，其余的元素正好有 n(n+1)/2 个，因此，三角矩阵可压缩到向量Sa0n(n+1)/2中，其中 c 存放在向量
2、的最后一个分量中。用向量Sa0n(n+1)/2压缩存储下三角矩阵，编写程序任意输入一个下三角矩阵，对其进行转置，输出转置后的矩阵。2用三元组顺序表压缩存储稀疏矩阵，编写程序任意输入一个稀疏矩阵，对其进行转置，输出转置后的矩阵。四、思考与提高如何计算一个三元组表表示的稀疏矩阵对角线元素之和以及两个三元组表表示的稀疏矩阵的乘积？名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 6 页 - - - - - - - - - /*- * 04_矩阵的压缩存储.cpp - 矩阵的压缩存
3、储及相关操作* 对矩阵的压缩存储的每个基本操作都用单独的函数来实现* 水上飘2009 年写-*/ / ds04.cpp : 定义控制台应用程序的入口点。/ #include stdafx.h #include #include #include #define n 9 / 矩阵的维数#define MAXSIZE 12500 / 假设非零元个数的最大值为12500 using namespace std; typedef struct int i,j; / 该非零元的行下标和列下标int e; /非零元的值 Triple; typedef struct Triple dataMAXSIZE+1
4、; /非零元三元组表，data0未用int mu,nu,tu; / 矩阵的行数、列数和非零元个数TSMatrix; void Input1(int *sa) /给压缩矩阵赋值for(int i = 0; i n*(n+1)/2; i+) sai = rand() % 100; san*(n+1)/2 = 0; void Output(int *sa) /转置前输出static int j = n -1; for(int i = 0; i n*(n+1)/2 + 1;) if(i = n*(n+1)/2) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - -
5、- - - - - - 名师精心整理 - - - - - - - 第 2 页，共 6 页 - - - - - - - - - break; for(int m = 0; m n-j; m+) / 输出压缩矩阵中n-j 个值cout setw(5) sai; i+; for(int k = 0; k j; k+) /用 j 个 san*(n+1)/2 的值填补每一行空余的位置cout setw(5) san*(n+1)/2; cout endl; / 一行完，换行j-; void Output2(int *sa) /转置距阵的输出for(int i = 0; i n; i+) for(int j
6、 = 0; j n; j+) if(i = j) / 将 i 行 j 列的值作为j 行 i 列来输出cout setw(5) saj*(j+1)/2 + i; else cout setw(5) san*(n+1)/2; cout endl; void TSMatrix_Input(TSMatrix &T) /给以三元组顺序表压缩存储的稀疏矩阵随机赋值int mu,nu,tu; cout mu; T.mu = mu; cout nu; T.nu = nu; cout tu; T.tu = tu; T.data0.e = 0; 名师资料总结 - - -精品资料欢迎下载 - - - - - - -
7、 - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 6 页 - - - - - - - - - for(int i = 1; i = T.tu; i+) int k = i; for(int j = 1; j 1 & jk) /判断第 i 行第 j 列中是否已被赋值了，若有，则i-1，重新进行随机i-; break; else T.datai.e = rand() % 100; / 给第 i 行第 j 列位置赋值 for(int i = 1; i = T.tu; i+) /检测用的cout T.datai.i = T.datai.i T.da
8、tai.j = T.datai.j T.datai.e = T.datai.e endl; void Transpose(TSMatrix T, TSMatrix &M) /将 T 矩阵转置到M M.mu = T.nu; M.nu = T.mu; / 行列交叉M.tu = T.tu; M.data0.e = T.data0.e; / 零元if(T.tu) / 若非零元个数不为零 int q = 1; / 记录非零元个数for(int i = 1; i = T.mu; i+) for(int j = 1; j = T.tu; j+) if(T.dataj.i = i) /行列交叉赋值M.data
9、q.i = T.dataj.j; M.dataq.j = T.dataj.i; M.dataq.e = T.dataj.e; q+; cout q: q-1; / 检测用 else continue; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 6 页 - - - - - - - - - void TSMatrix_Output(TSMatrix M) /输出以三元组表存储表示的稀疏矩阵int p = 0; for(int i = 0; i M.mu; i+) /第
10、i 行 for(int j = 0; j M.nu; j+) /第 j 列 for(int k = 1; k = M.tu; k+) if(i = M.datak.i & j = M.datak.j) /判断非零元的行列位置，若匹配就输出cout ( M.datak.e ); p = 1; break; else continue; if(p = 0) cout M.data0.e ; p = 0; cout endl; void Title1() cout 第一题： endl; int san*(n+1)/2 + 1 = 0; Input1(sa); cout 转置前的矩阵： endl; O
11、utput(sa); cout 转置后的距阵： endl; Output2(sa); void Title2() cout 第二题： endl; TSMatrix T,M; TSMatrix_Input(T); cout 矩阵转置前： endl; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 6 页 - - - - - - - - - TSMatrix_Output(T); Transpose(T,M); /实现转置cout 矩阵转置后： endl; TSMatrix_Output(M); int _tmain(int argc, _TCHAR* argv) srand(time(NULL); Title1(); cout - endl; Title2(); cin.get(); return 0; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 6 页 - - - - - - - - -