数据结构稀疏矩阵的压缩存储
1.实验目的：
掌握稀疏矩阵的压缩存储方法及主要运算的实现。
2.实验内容与要求：
设计一个稀疏矩阵计算器，要求能够：⑴输入并建立稀疏矩阵；⑵输出稀疏矩阵；⑶执行两个矩阵相加；⑷执行两个矩阵相乘；⑸求一个矩阵的转置矩阵；⑹求一个矩阵的逆矩阵（选做）。
3.数据结构设计：
逻辑结构：线性结构
存储结构：顺序存储结构
4.算法设计：
#include
#include
#include
#include
#define PI 3.14
//直接引用书上定义好了
#define OK 1
#define ERROR 0
//接下来就是三元组了
#define MAXSIZE 125
#define MAXRC 100
typedef struct
{
int i,j;
int e;
}Triple;
typedef struct
{
Triple data[MAXSIZE+1];
int rpos[MAXRC+1];
int mu,nu,tu;
}RLSMatrix;
//写各种函数的预留地
void menu()
{
printf("******************************* **************\n");
printf("* 作者：Dick *\n");
printf("* 信计1001 xxxxxxxxxx *\n");
printf("*********************MENU********************\n");
printf("1 输入并建立稀疏矩阵M,N\n");
printf("2 输出稀疏矩阵(有几个输出几个)\n");
printf("3 矩阵M,N相加,结果存在Q中\n");
printf("4 矩阵M,N相乘,结果存在Q中\n");
printf("5 求矩阵M的转置矩阵T\n");
printf("6 退出程序\n");
}
//这个得摆在最前面,后面全部得有容错语
句
void CreateSMatrix(RLSMatrix * M , RLSMatrix * N,RLSMatrix * Q , RLSMatrix * T)
{
//变量席位
int i,col;
int tempi,tempj,tempe;
int num[20];
void PrintSMatrix(RLSMatrix * M , RLSMatrix * N , RLSMatrix * Q , RLSMatrix * T);
//第一个！
//这里还有bug,比如输入的顺序是乱的
//基本思路是先对i进行排序
//然后再对列数进行循环
//嵌套利用rpos的循环对j进行排序
printf("请输入第一个矩阵的行数\n");
scanf("%d",&(*M).mu);
printf("请输入第一个矩阵的列数\n");
scanf("%d",&(*M).nu);
printf("请输入第一个矩阵的非零元个数\n");
scanf("%d",&(*M).tu);
for(i = 0; i < (*M).tu ; i++)
{
printf("请输入第一个矩阵的第%d 个元素:\n",i+1);
printf("格式为:行数,列数,非零元的值\n");
scanf("%d,%d,%d", &tempi ,
&tempj , &tempe );
if( tempi > (*M).mu || tempj >
(*M).nu )
{
printf("超出范围,重新输
入!\n");
i--;
continue;
}
else
{
(*M).data[i+1].i = tempi;
(*M).data[i+1].j = tempj;
(*M).data[i+1].e = tempe;
}
}
//不要忘记还得让rops搞定。。。
//貌似和下面的num[]和cpot[]一样的生成。。。抄袭之
for (col=1; col<=(*M).mu; ++col)
num[col] = 0;
for(i = 1; i < (*M).tu ; i++)
++num[(*M).data[i].i];
(*M).rpos[1] = 1;
for(col=2; col<=(*M).mu; ++col)
(*M).rpos[col] =
(*M).rpos[col-1]+num[col-1];
//搞定了吧。。
//第二个！
printf("请输入第二个矩阵的行数\n");
scanf("%d",&(*N).mu);
printf("请输入第二个矩阵的列数\n");
scanf("%d",&(*N).nu);
printf("请输入第二个矩阵的非零元个数\n");
scanf("%d",&(*N).tu);
for(i = 0; i < (*M).tu ; i++)
{
printf("请输入第一个矩阵的第%d 个元素:\n",i+1);
printf("格式为:行数,列数,非零元的值\n");
scanf("%d,%d,%d", &tempi ,
&tempj , &tempe );
if( tempi > (*N).mu || tempj >
(*N).nu )
{
printf("超出范围,重新输
入!\n");
i--;
continue;
}
else
{
(*N).data[i+1].i = tempi;
(*N).data[i+1].j = tempj;
(*N).data[i+1].e = tempe;
}
} for(col=1; col<=(*N).mu; ++col) num[col] = 0;
for(i = 1; i < (*N).tu ; i++)
++num[(*N).data[i].i];
(*N).rpos[1] = 1;
for (col=2; col<=(*N).mu; ++col)
(*N).rpos[col] = (*N).rpos[col-1]+num[col-1];
//估计老师又要在这里输出三元组了。。。
PrintSMatrix(M,N,Q,T);
}
//注意条件是矩阵存在,暂定三元组输出
//其实可以编写win32的程序的，加个滚动条
void PrintSMatrix(RLSMatrix * M , RLSMatrix * N , RLSMatrix * Q , RLSMatrix * T)
{
//变量席位
int numofMat;
printf("如果是零矩阵则不输出!\n");
if((*M).tu != 0)
{
printf("现以三元组形式输出矩阵M\n");
printf("**************************\n ");
printf("行数\t列数\t非零元素值\n");
printf("**************************\n ");
for(numofMat = 1 ; numofMat <= (*M).tu ; numofMat++)
printf("%2d\t%2d\t%5d\n",(*M).data[nu mofMat].i,(*M).data[numofMat].j,(*M).data[ numofMat].e);
printf("\n");
}
if((*N).tu != 0)
{
printf("现以三元组形式输出矩阵N\n");
printf("**************************\n ");
printf("行数\t列数\t非零元素值\n");
printf("**************************\n ");
for(numofMat = 1 ; numofMat <= (*N).tu ; numofMat++)
printf("%2d\t%2d\t%5d\n",(*N).data[nu mofMat].i, (*N).data[numofMat].j,
(*N).data[numofMat].e);
printf("\n");
}
if((*Q).tu != 0)
{
printf("现以三元组形式输出矩阵Q\n");
printf("**************************\n ");
printf("行数\t列数\t非零元素值\n");
printf("**************************\n ");
for(numofMat = 1 ; numofMat <= (*Q).tu ; numofMat++)
printf("%2d\t%2d\t%5d\n",(*Q).data[nu mofMat].i, (*Q).data[numofMat].j,
(*Q).data[numofMat].e);
printf("\n");
}
if((*T).tu != 0)
{
printf("现以三元组形式输出矩阵T\n");
printf("**************************\n ");
printf("行数\t列数\t非零元素值\n");
printf("**************************\n ");
for(numofMat = 1 ; numofMat <= (*T).tu ; numofMat++)
printf("%2d\t%2d\t%5d\n",(*T).data[nu mofMat].i, (*T).data[numofMat].j,
(*T).data[numofMat].e);
printf("\n");
}
printf("按任意键继续\n");
getchar();
getchar();
}
//注意条件是两个矩阵存在而且M与N行列相对应
//注意先让Q为空
int AddSMatrix(RLSMatrix * M , RLSMatrix * N , RLSMatrix * Q , RLSMatrix * T)
{
//变量预留
void PrintSMatrix(RLSMatrix * M , RLSMatrix * N , RLSMatrix * Q , RLSMatrix * T);
int ctemp,i,j,k;
//正式代码
if ( ((*M).mu != (*N).mu ) || ((*M).nu != (*N).nu ))
return ERROR;
(*Q).mu = (*M).mu; (*Q).nu = (*N).nu; (*Q).tu = 0; // Q初始化
if ((*M).tu != 0 && (*N).tu != 0)
for(i = 1 , j = 1 ,k = 1; i <= (*M).tu && j <= (*N).tu ; k++)
{
if( ( (*M).data[i].i-1) * (*M).nu + (*M).data[i].j >
( (*N).data[i].i-1) *
(*N).nu + (*N).data[i].j )
{
(*Q).data[k].i =
(*M).data[i].i;
(*Q).data[k].j =
(*M).data[i].j;
(*Q).data[k].e =
(*M).data[i].e;
i++;
(*Q).tu++;
}
else if( ( (*M).data[i].i-1) * (*M).nu + (*M).data[i].j <
( (*N).data[i].i-1) *
(*N).nu + (*N).data[i].j )
{
(*Q).data[k].i =
(*N).data[j].i;
(*Q).data[k].j = (*N).data[j].j;
(*Q).data[k].e =
-(*N).data[j].e;
j++;
(*Q).tu++;
}
else
{
ctemp =
(*M).data[i].e-(*N).data[j].e;
if(ctemp != 0)
{
(*Q).data[k].i = (*M).data[i].i;
(*Q).data[k].j = (*M).data[i].j;
(*Q).data[k].e = ctemp;
i++;
j++;
(*Q).tu++;
}
else
{
k--;
i++;
j++;
}
}
}
//这里某一个矩阵已经进行完了,剩下来的复制就可以了
if( i = (*M).tu+1 )
for(;j <= (*N).tu ; j++)
{
(*Q).data[k].i = (*N).data[j].i;
(*Q).data[k].j = (*N).data[j].j;
(*Q).data[k].e =
-(*N).data[j].e;
}
else
for(;i <= (*M).tu+1 ; i++)
{
(*Q).data[k].i = (*M).data[i].i;
(*Q).data[k].j = (*M).data[i].j;
(*Q).data[k].e = (*M).data[i].e;
}
PrintSMatrix(M,N,Q,T);
return OK;
}
//注意条件是两个矩阵存在而且M与N行列相对应
//注意这里生成Q之后需要对其进行rpos的操作
int MultSMatrix(RLSMatrix * M , RLSMatrix * N , RLSMatrix * Q , RLSMatrix * T)
{
// 求矩阵乘积Q=M?N，采用行逻辑链接存储表示。
int arow,brow,p,q,t,ctemp[30],l,ccol,tp;
void PrintSMatrix(RLSMatrix * M , RLSMatrix * N , RLSMatrix * Q , RLSMatrix * T);
if ( ((*M).nu != (*N).mu ))
return ERROR;
(*Q).mu = (*M).mu;
(*Q).nu = (*N).nu;
(*Q).tu = 0; // Q初始化
if ((*M).tu*(*N).tu != 0)
{ // Q是非零矩阵
for (arow=1; arow<=(*M).mu;
++arow)
{ // 处理M的每一行
for (l=1; l<=(*M).nu; ++l)
ctemp[l] = 0; // 当前行各元素累加器清零
(*Q).rpos[arow] = (*Q).tu+1;
if (arow<(*M).mu)
tp=(*M).rpos[arow+1];
else
tp=(*M).tu+1;
for (p=(*M).rpos[arow];
p { // 对当前行中每一个非零元 brow=(*M).data[p].j; // 找到对应元在N中的行号 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; // 乘积元素在Q中列号 ctemp[ccol] += (*M).data[p].e * (*N).data[q].e; } // for q } // 求得Q中第crow( =arow)行的非零元 for (ccol=1; ccol<=(*Q).nu; ++ccol) // 压缩存储该行非零元 if (ctemp[ccol]) { if (++(*Q).tu > MAXSIZE) return ERROR; (*Q).data[(*Q).tu].i=arow; (*Q).data[(*Q).tu].j=ccol; (*Q).data[(*Q).tu].e=ctemp[ccol]; } // if } // for arow } // if return OK; } //注意条件是M存在 int FastTransposeSMatrix(RLSMatrix * M , RLSMatrix * N , RLSMatrix * Q , RLSMatrix * T) { // 采用三元组顺序表存储表示，求稀疏矩阵M的转置矩阵T int col, t, p, q; int num[20], cpot[20]; void PrintSMatrix(RLSMatrix * M , RLSMatrix * N , RLSMatrix * Q , RLSMatrix * T); (*T).mu = (*M).nu; (*T).nu = (*M).mu; (*T).tu = (*M).tu; if ((*T).tu) { for (col=1; col<=(*M).nu; ++col) num[col] = 0; for (t=1; t<=(*M).tu; ++t) // 求M 中每一列所含非零元的个数 ++num[(*M).data[t].j]; cpot[1] = 1; // 求M 中每一列的第一个非零元在b.data 中的序号 for (col=2; col<=(*M).nu; ++col) cpot[col] = cpot[col-1]+num[col-1]; for (p=1; p<=(*M).tu; ++p) { 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]; } // for } // if PrintSMatrix(M,N,Q,T); return OK; } // FastTransposeSMatrix void main() { //写变量预留地 int i; RLSMatrix *M,*N,*Q,*T; M = (RLSMatrix *)malloc(sizeof(RLSMatrix)); N = (RLSMatrix *)malloc(sizeof(RLSMatrix)); Q = (RLSMatrix *)malloc(sizeof(RLSMatrix)); T = (RLSMatrix *)malloc(sizeof(RLSMatrix)); char str[]="按回车键继续"; if(!M||!N||!Q||!T) exit(2); (*M).tu=(*N).tu=(*T).tu=(*Q).tu=0; while(1) { menu(); do //这里循环直到你输入正确的数字为止 { printf ( "请输入要进行的操作\n" ); scanf ("%d",&i); if (i<1||i>6) printf("错误数字，请重新输入\n"); }while (i<1||i>6); switch (i) { case 1: CreateSMatrix(M,N,Q,T); system("CLS");break; case 2: PrintSMatrix(M,N,Q,T); system("CLS");break; //清屏函数放到break前面可以有效的在执行完一系列函数之后才清屏 case 3: AddSMatrix(M,N,Q,T); system("CLS");break; case 4: MultSMatrix(M,N,Q,T); PrintSMatrix(M,N,Q,T); system("CLS");break; case 5: FastTransposeSMatrix(M,N,Q,T); system("CLS");break; case 6: exit(0); break; } } } 5.实验结果： 图1：输出功能 图2：相乘功能 图3：相加功能 图4：转置功能 数据结构实验五矩阵的压缩存储与运算 第五章矩阵的压缩存储与运算 【实验目的】 1. 熟练掌握稀疏矩阵的两种存储结构(三元组表和十字链表)的实现； 2. 掌握稀疏矩阵的加法、转置、乘法等基本运算； 3. 加深对线性表的顺序存储和链式结构的理解。 第一节知识准备 矩阵是由两个关系（行关系和列关系）组成的二维数组，因此对每一个关系上都可以用线性表进行处理；考虑到两个关系的先后，在存储上就有按行优先和按列优先两种存储方式，所谓按行优先，是指将矩阵的每一行看成一个元素进行存储；所谓按列优先，是指将矩阵的每一列看成一个元素进行存储；这是矩阵在计算机中用一个连续存储区域存放的一般情形，对特殊矩阵还有特殊的存储方式。 一、特殊矩阵的压缩存储 1. 对称矩阵和上、下三角阵 若n阶矩阵A中的元素满足= （0≤i，j≤n-1 ）则称为n阶对称矩阵。对n阶对称矩阵，我们只需要存储下三角元素就可以了。事实上对上三角矩阵（下三角部分为零）和下三角矩阵（上三角部分为零），都可以用一维数组ma[0.. ]来存储A的下三角元素（对上三角矩阵做转置存储），称ma为矩阵A的压缩存储结构，现在我们来分析以下，A和ma之间的元素对应放置关系。 问题已经转化为：已知二维矩阵A[i，j]，如图5-1， 我们将A用一个一维数组ma[k]来存储，它们之间存在着如图5-2所示的一一对应关系。 任意一组下标(i,j)都可在ma中的位置k中找到元素m[k]= ；这里： k=i(i+1)/2+j (i≥j) 图5-1 下三角矩阵 a00 a10 a11 a20 … an-1,0 … an-1,n-1 k= 0 1 2 3 …n(n- 1)/2 …n(n+1)/2-1 图5-2下三角矩阵的压缩存储 反之，对所有的k=0,1，2,…,n(n+1)/2-1，都能确定ma[k]中的元素在矩阵A中的位置（i,j）。这里，i=d-1，（d是使sum= > k的最小整数），j= 。 2. 三对角矩阵 在三对角矩阵中，所有的非零元素集中在以主对角线为中心的带内状区域中，除了主对角线上和直接在对角线上、下方对角线上的元素之外，所有其它的元素皆为零，见图5-3。 图5-3 三对角矩阵A 与下三角矩阵的存储一样，我们也可以用一个一维数组ma[0..3n-2]来存放三对角矩阵A，其对应关系见图5-4。 a00 a01 a10 a11 a12 … an-1,n-2 an-1,n-1 k= 0 1 2 3 4 … 3n-3 3n-2 图5-4下三角矩阵的压缩存储 A中的一对下标(i,j)与ma中的下标k之间有如下的关系： 公式中采用了C语言的符号，int()表示取整，‘%’表示求余。 特殊矩阵计算器 1、特殊矩阵计算器 问题描述：创建两个特殊矩阵 A 和 B，计算 A+B、A-B、A*B、B*A、A（或 B）的逆、A（或 B）的转置、A（或 B）的行列式等，具体要求如下：① A、B 均是压缩存储的特殊矩阵，如上/下三角矩阵、对称矩阵、对角矩阵、单位矩阵等。 ② A、B 的矩阵类型、行列数、各位置的元素值等信息均在运行时指定（对于不同类型的矩阵，要求输入的数据也不尽相同）。③各运算若可行，则打印结果；若不可行，则给出提示信息。④各运算需自己实现，禁止调用语言内建或第三方类库的矩阵 API。 涉及算法及知识：特殊矩阵的压缩存储、矩阵相关运算。 #include<> #include<> #define max 100 typedef struct{ int row,col;//定义矩阵行数、列数 int a[max][max]; }Matrix; //存储结构 typedef struct{ int array[max]; int n; //定义矩阵的阶 }M; Matrix A,B,C,D; M p; //*************矩阵的压缩存储*********************// int CompressMatrix(int m,int i,int j,int n){ int k; if(m==1){ if(i<=j) k=(2*n-i+1)*i/2+(j-i)+1; else k=0; return k; } if(m==2){ if(i>=j) k=i*(i+1)/2+j+1; else k=0; return k; } if(m==3){ if(i>=j) k=i*(i+1)/2+j; else k=j*(j+1)/2+i; return k; } if(m==4){ if(i!=j) k=0; else k=i+1; 数据结构知识点概括 第一章概论 数据就是指能够被计算机识别、存储和加工处理的信息的载体。 数据元素是数据的基本单位，可以由若干个数据项组成。数据项是具有独立含义的最小标识单位。 数据结构的定义： ·逻辑结构：从逻辑结构上描述数据，独立于计算机。·线性结构：一对一关系。 ·线性结构：多对多关系。 ·存储结构：是逻辑结构用计算机语言的实现。·顺序存储结构：如数组。 ·链式存储结构：如链表。 ·索引存储结构：·稠密索引：每个结点都有索引项。 ·稀疏索引：每组结点都有索引项。 ·散列存储结构：如散列表。 ·数据运算。 ·对数据的操作。定义在逻辑结构上，每种逻辑结构都有一个运算集合。 ·常用的有：检索、插入、删除、更新、排序。 数据类型：是一个值的集合以及在这些值上定义的一组操作的总称。 ·结构类型：由用户借助于描述机制定义，是导出类型。 抽象数据类型ADT：·是抽象数据的组织和与之的操作。相当于在概念层上描述问题。 ·优点是将数据和操作封装在一起实现了信息隐藏。 程序设计的实质是对实际问题选择一种好的数据结构，设计一个好的算法。算法取决于数据结构。 算法是一个良定义的计算过程，以一个或多个值输入，并以一个或多个值输出。 评价算法的好坏的因素：·算法是正确的； ·执行算法的时间； ·执行算法的存储空间（主要是辅助存储空间）； ·算法易于理解、编码、调试。 时间复杂度：是某个算法的时间耗费，它是该算法所求解问题规模n的函数。 渐近时间复杂度：是指当问题规模趋向无穷大时，该算法时间复杂度的数量级。 评价一个算法的时间性能时，主要标准就是算法的渐近时间复杂度。 算法中语句的频度不仅与问题规模有关，还与输入实例中各元素的取值相关。 时间复杂度按数量级递增排列依次为：常数阶O（1）、对数阶O（log2n）、线性阶O（n）、线性对数阶O（nlog2n）、平方阶O （n^2）、立方阶O（n^3）、……k次方阶O（n^k）、指数阶O（2^n）。 专业课程设计I报告（2011 / 2012 学年第二学期） 题目稀疏矩阵的转换 专业软件工程 学生姓名张鹏宇 班级学号 09003018 指导教师张卫丰 指导单位计算机学院软件工程系 日期 2012年6月18号 指导教师成绩评定表 附件： 稀疏矩阵的转换 一、课题内容和要求 1．问题描述 设计程序用十字链表实现稀疏矩阵的加、减、乘、转置。 2．需求分析 （1）设计函数建立稀疏矩阵，初始化值。 （2）设计函数输出稀疏矩阵的值。 （3）构造函数进行两个稀疏矩阵相加，输出最终的稀疏矩阵。 （4）构造函数进行两个稀疏矩阵相减，输出最终的稀疏矩阵。 （5）构造函数进行两个稀疏矩阵的相乘，输出最终的稀疏矩阵。 （6）构造函数进行稀疏矩阵的转置，并输出结果。 （7）退出系统。 二、设计思路分析 （1）设计函数建立稀疏矩阵，初始化值。 （2）设计函数输出稀疏矩阵的值。 （3）构造函数进行两个稀疏矩阵相加，输出最终的稀疏矩阵。 （4）构造函数进行两个稀疏矩阵相减，输出最终的稀疏矩阵。 （5）构造函数进行两个稀疏矩阵的相乘，输出最终的稀疏矩阵。 （6）构造函数进行稀疏矩阵的转置，并输出结果。 （7）退出系统。 三、概要设计 为了实现以上功能，可以从3个方面着手设计。 1．主界面设计 为了实现对稀疏矩阵的多种算法功能的管理，首先设计一个含有多个菜单项的主 控菜单子程序以链接系统的各项子功能，方便用户交互式使用本系统。本系统主控菜单运行界面如图所示。 2．存储结构设计 本系统采用单链表结构存储稀疏矩阵的具体信息。其中：全部结点的信息用头结点为指针数组的单链表存储。 3．系统功能设计 本系统除了要完成稀疏矩阵的初始化功能外还设置了4个子功能菜单。稀疏矩阵的初始化由函数i typedef int ElemType 实现。建立稀疏矩阵用void Creat()实现，依据读入的行数和列数以及非零元素的个数，分别设定每个非零元素的信息。4个子功能的设计描述如下。 （1）稀疏矩阵的加法： 此功能由函数void Xiangjia( )实现，当用户选择该功能，系统即提示用户初始化要进行加法的两个矩阵的信息。然后进行加法，最后输出结果。 （2）稀疏矩阵的乘法： 此功能由函数void Xiangcheng( )实现。当用户选择该功能，系统提示输 /* c1.h (程序名) */ #include #include 稀疏矩阵及其压缩存储方法 1.基本概念 稀疏矩阵(SparseMatrix)：是矩阵中的一种特殊情况，其非零元素的个数远小于零元素的个数。 设m行n列的矩阵含t个非零元素，则称 以二维数组表示高阶的稀疏矩阵时，会产生零值元素占的空间很大且进行了很多和零值的运算的问题。 特殊矩阵：值相同的元素或0元素在矩阵中的分布有一定的规律。如下三角阵、三对角阵、稀疏矩阵。 压缩存储：为多个值相同的元素只分配一个存储空间；对0元素不分配空间。目的是节省大量存储空间。 n x n的矩阵一般需要n2个存储单元，当为对称矩阵时需要n(1+n)/2个单元。 2.三元组顺序表——压缩存储稀疏矩阵方法之一（顺序存储结构） 三元组顺序表又称有序的双下标法，对矩阵中的每个非零元素用三个域分别表示其所在的行号、列号和元素值。它的特点是，非零元在表中按行序有序存储，因此便于进行依行顺序处理的矩阵运算。当矩阵中的非0元素少于1/3时即可节省存储空间。 （1）稀疏矩阵的三元组顺序表存储表示方法 #define MAXSIZE 12500 // 假设非零元个数的最大值为12500 typedef struct { int i, j; // 该非零元的行下标和列下标 ElemType e; //非零元素的值 } Triple; // 三元组类型 typedef union { //共用体 Triple data[MAXSIZE + 1]; // 非零元三元组表，data[0]未用 int mu, nu, tu; // 矩阵的行数、列数和非零元个数 } TSMatrix; // 稀疏矩阵类型 （2）求转置矩阵的操作 ◆用常规的二维数组表示时的算法 for (col=1; col<=nu; ++col) for (row=1; row<=mu; ++row) T[col][row] = M[row][col]; 其时间复杂度为: O(mu×nu) ◆用三元组顺序表表示时的快速转置算法 Status FastTransposeSMatrix(TSMatrix M, TSMatrix &T) { // 采用三元组顺序表存储表示，求稀疏矩阵M的转置矩阵T T.mu = M.nu; T.nu = M.mu; T.tu = M.tu; if (T.tu) { for (col=1; col<=M.nu; ++col) num[col] = 0; for (t=1; t<=M.tu; ++t) ++num[M.data[t].j];// 求M 中每一列所含非零元的个数 常熟理工学院 《数据结构与算法》实验指导与报告书 _2017-2018_____学年第__1__ 学期 专业：物联网工程 实验名称：特殊矩阵和稀疏矩阵 实验地点： N6-210 指导教师：聂盼红 计算机科学与工程学院 2017 实验五特殊矩阵和稀疏矩阵 【实验目的】 1、掌握数组的结构类型（静态的内存空间配置）；通过数组的引用下标转换成该数据在内存中的地址； 2、掌握对称矩阵的压缩存储表示； 3、掌握稀疏矩阵的压缩存储-三元组表表示，以及稀疏矩阵的转置算法。 【实验学时】 2学时 【实验预习】 回答以下问题： 1、什么是对称矩阵？写出对称矩阵压缩存储sa[k]与aij之间的对应关系。 若n阶矩阵A中的元素满足下述性质：a ij=a ji，则称为n阶对称矩阵。 sa[k]与矩阵元素a ij之间存在着一一对应的关系： 若i>=j，k=i*(i+1)/2+j; 若i 的关系。（注意C程序中，i，j，k均从0开始） （2）调试程序与运行。对称矩阵存储下三角部分即i>=j。 对称矩阵为3,9,1,4,7 9,5,2,5,8 1,2,5,2,4 4,5,2,1,7 7,8,4,7,9 参考程序如下： #include<> #define N 5 int main() { int upper[N][N]= {{3,9,1,4,7}, {9,5,2,5,8}, {1,2,5,2,4}, {4,5,2,1,7}, {7,8,4,7,9} }; /*对称矩阵*/ int rowMajor[15]; /*存储转换数据后以行为主的数组*/ int Index; /*数组的索引值*/ int i,j; printf("Two dimensional upper triangular array:\n"); for (i=0; i 稀疏矩阵基本操作实验报告 一、实验内容 稀疏矩阵的压缩储存结构，以及稀疏矩阵的三元组表表示方法下的转置、相加、相乘等算法 二、实验目的 1.熟悉数组、矩阵的定义和基本操作 2.熟悉稀疏矩阵的储存方式和基本运算 3.理解稀疏矩阵的三元组表类型定义，掌握稀疏矩阵的输入、输出和转置算法 三、实验原理 1.使用三元组储存矩阵中的非零元素（三元组分别储存非零元素的行下标，列下标和 元素值）。除了三元组表本身，储存一个稀疏矩阵还需要额外的三个变量，分别储存矩阵的非零元个数，矩阵的行数和矩阵的列数。 2.稀疏矩阵的创建算法： 第一步：根据矩阵创建一个二维数组，表示原始矩阵 第二步：取出二维数组中的元素（从第一个元素开始取），判断取出元素是否为非零元素，如果为非零元素，把该非零元素的数值以及行下标和列下表储存到三元数组表里，否则取出下一个元素，重复该步骤。 第三步：重复第二步，知道二维数组中所有的元素已经取出。 3.稀疏矩阵倒置算法： 第一步：判断进行倒置的矩阵是否为空矩阵，如果是，则直接返回错误信息。 第二步：计算要倒置的矩阵每列非零元素的数量，存入到num数组（其中num[i] 代表矩阵中第i列非零元素的个数）。以及倒置后矩阵每行首非零元的位置，存入cpot 数组中（其中cpot表示倒置后矩阵每行非零元的位置，对应表示原矩阵每列中第一个非零元的位置）。 第三步：确定倒置后矩阵的行数和列数。 第四步：取出表示要导致矩阵中三元组表元素{e, I, j}（第一次取出第一个，依次取出下一个元素），从第二步cpot数组中确定该元素倒置后存放的位置（cpot[j]），把该元素的行下标和列下标倒置以后放入新表的指定位置中。cpot[j] 变量加一。 第五步：重复第四步，直到三元组表中所有的元素都完成倒置。 第六步：把完成倒置运算的三元组表输出。 4.稀疏矩阵加法算法： 第一步：检查相加两个矩阵的行数和列数是否相同，如果相同，则进入第二步，否则输出错误信息。 第二步：定义变量i和j，用于控制三元组表的遍历。 第三步：比较变量矩阵M中第i个元素和矩阵N中第j个元素，如果两个元素是同一行元素，如果不是则进入第四步，如果是，再继续比较两个元素是否为同一列元素，如果是，把两个元素值相加，放到三元组表中；否则把列下表小的元素依次放到三元组表中。进入第五步 第四步：如果矩阵M中第i个元素的行下标大于矩阵N中第j个元素的行下标，则把矩阵N中第j个元素所在行的所有非零元素添加到三元组表中；如果矩阵M中第 第五章矩阵的压缩存储与运算 【实验目的】 1. 熟练掌握稀疏矩阵的两种存储结构(三元组表和十字链表)的实现； 2. 掌握稀疏矩阵的加法、转置、乘法等基本运算； 3. 加深对线性表的顺序存储和链式结构的理解。 第一节知识准备 矩阵是由两个关系（行关系和列关系）组成的二维数组，因此对每一个关系上都可以用线性表进行处理；考虑到两个关系的先后，在存储上就有按行优先和按列优先两种存储方式，所谓按行优先，是指将矩阵的每一行看成一个元素进行存储；所谓按列优先，是指将矩阵的每一列看成一个元素进行存储；这是矩阵在计算机中用一个连续存储区域存放的一般情形，对特殊矩阵还有特殊的存储方式。 一、特殊矩阵的压缩存储 1. 对称矩阵和上、下三角阵 若n阶矩阵A中的元素满足 = （0≤i，j≤n-1 ）则称为n阶对称矩阵。对n阶对称矩阵，我们只需要存储下三角元素就可以了。事实上对上三角矩阵（下三角部分为零）和下三角矩阵（上三角部分为零），都可以用一维数组ma[0.. ]来存储A的下三角元素（对上三角矩阵做转置存储），称ma为矩阵A的压缩存储结构，现在我们来分析以下，A和ma之间的元素对应放置关系。 问题已经转化为：已知二维矩阵A[i，j]，如图5-1， 我们将A用一个一维数组ma[k]来存储，它们之间存在着如图5-2所示的一一对应关系。 任意一组下标(i,j)都可在ma中的位置k中找到元素m[k]= ；这里： k=i(i+1)/2+j (i≥j) 图5-1 下三角矩阵 a00 a10 a11 a20 … an-1,0 … an-1,n-1 k= 0 1 2 3 … n(n-1)/2 … n(n+1)/2-1 图5-2下三角矩阵的压缩存储 反之，对所有的k=0,1，2,…,n(n+1)/2-1，都能确定ma[k]中的元素在矩阵A中的位置（i,j）。这里，i=d-1，（d是使sum= > k的最小整数），j= 。 2. 三对角矩阵 P-219-29T template for(int j=0;j 课程设计 题目矩阵乘法 教学院计算机学院 专业09计算机科学与技术 班级 姓名 指导教师 年月日 目录 1 概述 (3) 2 设计目的 (3) 3 设计功能说明 (3) 4 详细设计说明 (3) 5 流程图 (4) 6 调试及结果 (5) 1程序调试 (5) 2运行编译连接过程......................................................... 5-8 7 总结 (9) 附录...........................................................................10-24 参考文献 (25) 成绩评定表 (26) 1 概述 数据结构是一门理论性强、思维抽象、难度较大的课程，是基础课和专业课之间的桥梁只有进行实际操作，将理论应用于实际中，才能确实掌握书中的知识点。通过课程设计，不仅可以加深学生对数据结构基本概念的了解，巩固学习成果，还能够提高实动手力。为学生后继课程的学习打下良好的基础。 2 设计目的 《数据结构》课程设计是在教学实践基础上进行的一次大型实验，也是对该课程所学理论知识的深化和提高。因此，要求学生能综合应用所学知识，设计与制造出具有较复杂功能的应用系统，并且在实验的基本技能方面上进行一次全面的训练。通过程序的编译掌握对程序的调试方法及思想，并且让学生学会使用一些编程技巧。促使学生养成良好的编程习惯。 1.使学生能够较全面地巩固和应用课堂中所学的的基本理论和程序设计方法，能够较熟练地完成程序的设计和调试。 2.培养学生综合运用所学知识独立完成程序课题的能力。 3.培养学生勇于探索、严谨推理、实事求是、有错必改，用实践来检验理论，全方位考虑问题等科学技术人员应具有的素质。 4．提高学生对工作认真负责、一丝不苟，对同学团结友爱，协作攻关的素质。 5.培养学生从资料文献、科学实验中获得知识的能力，提高学生从别人经验中找到解决问题的新途径的悟性，初步培养工程意识和创新能力。 6.对学生掌握知识的深度、运用理论去处理问题的能力、实验能力、课程设计能力、书面及口头表达能力进行考核。 3 设计功能分析 本设计的功能如下： 1、对于用户给定的矩阵相乘可以进行存储，并且用户可以更改 2、根据用户的要求可以选择相应的功能加减乘及转置 3、然后显示用户输入的矩阵进行运算并得到结果后保存到文件 4 详细设计说明 本程序用数据存储的方式建立矩阵。然后用相加，减，乘，转置的方式计算出 为了节省存储空间并且加快处理速度，需要对这类矩阵进行压缩存储，压缩存储的原则是：不重复存储相同元素；不存储零值元素。 一、相关概念 ㈠特殊矩阵：矩阵中存在大多数值相同的元,或非0元，且在矩阵中的分布有一定规律。 ⒈对称矩阵：矩阵中的元素满足 a ij=a ji 1≤i,j≤n ⒉三角矩阵：上（下）三角矩阵指矩阵的下（上）三角（不包括对角线）中的元素均为常数c或0的n阶矩阵。 ⒊对角矩阵（带状矩阵）：矩阵中所有非0元素集中在主对角线为中心的区域中。 ㈡稀疏矩阵：非0元素很少（≤ 5%）且分布无规律。 二、存储结构及算法思想 1、对称矩阵 存储分配策略：每一对对称元只分配一个存储单元,即只存储下三角（包括对角线）的元, 所需空间数为: n(n+1)/2。 存储分配方法：用一维数组sa[n(n+1)/2]作为存储结构。 sa[k]与a ij之间的对应关系为: 2、三角矩阵 也是一个n阶方阵，有上三角和下三角矩阵。下(上)三角矩阵是主对角线以上（下）元素均为零的n阶矩阵。设以一维数组sb[0..n(n+1)/2]作为n阶三角矩阵B的存储结构，仍采用按行存储方案，则B中任一元素b i,j和sb[k]之间仍然有如上的对应关系，只是还需要再加一个存储常数c的存储空间即可。如在下三角矩阵中，用n(n+1)/2的位置来存储常数。 对特殊矩阵的压缩存储实质上就是将二维矩阵中的部分元素按照某种方案排列到一维数组中，不同的排列方案也就对应不同的存储方案 2、稀疏矩阵 常见的有三元组表示法、带辅助行向量的二元组表示法（也即行逻辑链表的顺序表），十字链表表示法等。 1）、三元组表示法 三元组表示法就是在存储非零元的同时，存储该元素所对应的行下标和列下标。稀疏矩阵中的每一个非零元素由一个三元组(i,j,a ij)唯一确定。矩阵中所有非零元素存放在由三元组组成的数组中。 软件学院 上机实验报告 课程名称：数据结构 实验项目：矩阵 实验室：耘慧420 姓名：学号 专业班级：实验时间：2016.11.24 实验成绩评阅教师 一、实验目的及要求 1. 掌握稀疏矩阵压缩存储方法(三元组顺序表存储)。 2. 完成压缩存储下矩阵计算(矩阵转置)。 二、性质 验证性 三、实验学时 2 学时 四、实验环境 C 与C++ 程序设计学习与实验系统 五、实验内容及步骤 实验内容： 1.实现矩阵压缩存储。(静态数组压缩存储或直接输入矩阵非0 元均可) 2.实现矩阵转置算法。 3.实现矩阵快速转置。 实验步骤： 1.实现矩阵压缩存储。(静态数组压缩存储或直接输入矩阵非0 元均可) 2. 实现矩阵转置算法TransposeSMatrix(TSMatrix M,TSMatrix &T) 。 3. 实现矩阵快速转置FastTransposeSMatrix(TSMatrix M,TSMatrix &T) 。 4. 主函数中创建矩阵M，将M 调用转置算法转置成矩阵N，调用快速转置算法转化 成矩阵T。 六、实验数据及结果分析 七、总结 了解了矩阵的一些知识，懂得了矩阵的一些算法。并且在实际上机中，学会了矩阵的程序的编写方法。 附录源程序清单插入; #include 《数据结构》试卷及答案 1．算法分析的目的是( )。 A.找出数据结构的合理性 B.研究算法中输入和输出的关系 C.分析算法的效率以求改进 D.分析算法的易懂性和文档性 2．（）是具有相同特性数据元素的集合，是数据的子集。 A.数据符号 B.数据对象 C.数据 D.数据结构 3．用链表表示线性表的优点是( )。 A.便于随机存取 B.花费的存储空间比顺序表少 C.便于插入与删除 D.数据元素的物理顺序与逻辑顺序相同 4．输入序列为（A,B,C,D）不可能的输出有（）。 A.(A,B,C,D) B. (D,C,B,A) C. (A,C,D,B) D . (C,A,B,D) 5．在数组表示的循环队列中，front、rear分别为队列的头、尾指针，maxSize为数组的最大长度，队满的条件是( )。 A. front=maxSize B. (rear+1)%maxSize=front C. rear=maxSize D. rear=front 6．设有串t='I am a good student '，那么Substr(t,6,6)=（）。 A. student B. a good s C. good D. a good 7．设有一个对称矩阵A，采用压缩存储方式，以行序为主序存储a11为第一个元素，其存储地址为1，每个元素占一个地址空间，则a85地址为（）。 A.23 B.33 C.18 D. 40 8．已知广义表LS=(A,(B,C,D),E)运用head和tail函数，取出LS中原子b的运算（）。 A. Gethead(Gethead(LS)) B. Gettail(Gethead(LS)) C. Gethead(Gethead(Gettail(LS))) D. Gethead(Gettail(LS)) 9．若已知一棵二叉树先序序列为ABCDEFG，中序序列为CBDAEGF，则其后序序列为( ) A. CDBGFEA B. CDBFGEA C. CDBAGFE D. BCDAGFE 10．下列存储形式中，( ) 不是树的存储形式。 A.双亲表示法 B.左子女右兄弟表示法 C.广义表表示法 D.顺序表示法 11．对待排序的元素序列进行划分，将其分为左、右两个子序列，再对两个子序列施加同样的排序操作，直到子序列为空或只剩一个元素为止。这样的排序方法是( )。 A.直接选择排序 B.直接插入排序 C.快速排序 D.起泡排序 12．采用折半查找方法进行查找，数据文件应为（），且限于（）。 专业课程设计I报告（ 2011 / 2012 学年第二学期） 题目稀疏矩阵的转换 专业软件工程 学生姓名鹏宇 班级学号 09003018 指导教师卫丰 指导单位计算机学院软件工程系 日期 2012年6月18号 指导教师成绩评定表 附件： 稀疏矩阵的转换 一、课题容和要求 1．问题描述 设计程序用十字链表实现稀疏矩阵的加、减、乘、转置。 2．需求分析 （1）设计函数建立稀疏矩阵，初始化值。 （2）设计函数输出稀疏矩阵的值。 （3）构造函数进行两个稀疏矩阵相加，输出最终的稀疏矩阵。 （4）构造函数进行两个稀疏矩阵相减，输出最终的稀疏矩阵。 （5）构造函数进行两个稀疏矩阵的相乘，输出最终的稀疏矩阵。 （6）构造函数进行稀疏矩阵的转置，并输出结果。 （7）退出系统。 二、设计思路分析 （1）设计函数建立稀疏矩阵，初始化值。 （2）设计函数输出稀疏矩阵的值。 （3）构造函数进行两个稀疏矩阵相加，输出最终的稀疏矩阵。 （4）构造函数进行两个稀疏矩阵相减，输出最终的稀疏矩阵。 （5）构造函数进行两个稀疏矩阵的相乘，输出最终的稀疏矩阵。 （6）构造函数进行稀疏矩阵的转置，并输出结果。 （7）退出系统。 三、概要设计 为了实现以上功能，可以从3个方面着手设计。 1．主界面设计 为了实现对稀疏矩阵的多种算法功能的管理，首先设计一个含有多个菜单项的主控菜单子程序以系统的各项子功能，方便用户交互式使用本系统。本系统主控菜单运行界面如图所示。 2．存储结构设计 本系统采用单链表结构存储稀疏矩阵的具体信息。其中：全部结点的信息用头结点为指针数组的单链表存储。 3．系统功能设计 本系统除了要完成稀疏矩阵的初始化功能外还设置了4个子功能菜单。稀疏矩阵的初始化由函数i typedef int ElemType 实现。建立稀疏矩阵用void Creat()实现，依据读入的行数和列数以及非零元素的个数，分别设定每个非零元素的信息。4个子功能的设计描述如下。 （1）稀疏矩阵的加法： 此功能由函数void Xiangjia( )实现，当用户选择该功能，系统即提示用户初始化要进行加法的两个矩阵的信息。然后进行加法，最后输出结果。 （2）稀疏矩阵的乘法： 此功能由函数void Xiangcheng( )实现。当用户选择该功能，系统提示输入要进行相乘的两个矩阵的详细信息。然后进行相乘，最后得到结果。 （3）稀疏矩阵的转置： 此功能由函数void Zhuanzhi( )实现。当用户选择该功能，系统提示用户初始 实验四数组的运算 实验目的： 掌握稀疏矩阵的压缩存储方法及主要运算的实现。 实验内容与要求： 设计一个稀疏矩阵计算器，要求能够：⑴输入并建立稀疏矩阵；⑵输出稀疏矩阵；⑶执行两个矩阵相加；⑷执行两个矩阵相乘；⑸求一个矩阵的转置矩阵；⑹求一个矩阵的逆矩阵（选做）。 实验代码： Rect.h #define MAXSIZE100 typedef struct { int h_num; int v_num; int elem; }Triple; typedef struct { Triple *arry; int h_i; int v_j; int elem_num; }TSMatrix; void Init_TS(TSMatrix *T ); void creat(TSMatrix *T); void Print_TS(TSMatrix *); void sum_TS(TSMatrix *T1,TSMatrix *T2,TSMatrix *T); void mul_TS(TSMatrix *T1,TSMatrix *T2,TSMatrix *T); void transpose_TS(TSMatrix *T); void equal_Triple(Triple *t1,Triple *t2); Rect.cpp #include void Init_TS(TSMatrix *T) { T->arry=(Triple *)malloc(MAXSIZE*sizeof(Triple)); if(!T->arry) printf("error\n") ; T->elem_num=0; T->h_i=0; T->v_j=0; } void Init_Tr(Triple *t) { t->elem=0; t->h_num=0; t->v_num=0; } void creat(TSMatrix *T) { printf("要输入的数组的行数和列数\n"); scanf("%d,%d",&T->h_i,&T->v_j); printf("要输入稀疏数组的元素个数\n"); scanf("%d",&T->elem_num); printf("输入要输入的稀疏数组的信息\n"); printf("行值列值元素值\n"); for(int i=0;i 数据结构课程设计稀疏矩阵的运算 学生姓名： 学号： 指导教师： 完成日期： 目录： 1、分析问题和确定解决方案 (3) 1.1问题描述 (3) 1.2 输入的形式和输入值的范围 (3) 1.3 输出的形式 (3) 1.4 程序所能达到的功能 (3) 1.5 测试数据 (3) 1.6 确定解决方案 (4) 1.7所有抽象数据类型的定义 (4) 2、详细设计 (5) 2.1稀疏矩阵加法运算思路 (5) 2.2稀疏矩阵减法运算思路 (7) 2.3稀疏矩阵转置运算思路 (9) 2.4创建稀疏矩阵 (11) 3、系统调试与测试 (12) 3.1程序的菜单界面 (12) 3.2 实现加法运算 (12) 3.3 实现减法运算 (13) 3.4实现转置运算 (14) 4、结果分析 (15) 4.1、算法的时空分析 (15) 4.2、经验和体会 (15) 5、参考文献 (15) 1、分析问题和确定解决方案 1.1问题描述 稀疏矩阵是指那些多数元素为零的矩阵。利用“稀疏”特点进行存储和计 算可以大大节省存储空间，提高计算效率。实现一个能进行稀疏矩阵基本运算的运算器。用三元组实现稀疏矩阵的相加、相减，转置； 1.2输入的形式和输入值的范围 以三元组的形式输入，首先应输入矩阵的行数和列数，并判别给出的两个 矩阵的行、列数对于所要求作的运算是否相匹配。可设矩阵的行数和列数均不超过20； 例如：输入的三元组为：((1,1,10),(2,3,9),(3,1,-1))其对应的稀疏矩阵为： ???? ??????-0019000010 1.3 输出的形式 运算结果的矩阵以通常的阵列形式输出； 1.4程序所能达到的功能 该程序可以实现以三元组形式输入两个矩阵，求出两个矩阵的和、差、转置； 并可根据输入的矩阵的行列数不同判别是否可以进行相加、减、转置，并重新输 入正确的矩阵； 1.5测试数据 测试的数据及其结果如下： 矩阵M 矩阵N 矩阵Q 加法： ???? ??????-0019000010 + ????? ?????--301100000 = ????? ?????-3008000010 减法： ???? ? ?????-0190010 - ???? ? ?????--311000 = ???? ??????-32100010 转置：数据结构实验五矩阵的压缩存储与运算学习资料
数据结构课程设计-特殊矩阵计算器
(完整版)非常实用的数据结构知识点总结
稀疏矩阵的运算(完美版)
数据结构矩阵的转置
三角矩阵在压缩存储下的转置矩阵源代码
稀疏矩阵及其压缩存储方法
数据结构与算法 特殊矩阵和稀疏矩阵
稀疏矩阵基本操作 实验报告
数据结构实验五矩阵的压缩存储与运算
数据结构—矩阵课后题
数据结构矩阵相关操作的课程设计
矩阵压缩1
数据结构——矩阵
数据结构试卷及答案压缩版
稀疏矩阵的运算(完美版)
压缩矩阵的运算
稀疏矩阵的运算