下三角矩阵的压缩存储(实验报告)

数据结构实验五矩阵的压缩存储与运算第五章矩阵的压缩存储与运算【实验目的】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-1k= 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。

精品资料数据结构实验五矩阵的压缩存储与运算........................................第五章矩阵的压缩存储与运算【实验目的】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-1k= 0 1 23 …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= 。

下三角矩阵的压缩存储(实验报告)
1、实验目的和要求理解和掌握下三角矩阵的压缩存储技术，使用C语言根据相应算法编写一个程序，实现下三角矩阵的压缩存储。

要求仔细阅读下面的内容，编写C程序，上机通过，并观察其结果，写出实验报告书。

二、实验内容和原理内容：用一个一维数组存储一个5X5的下三角矩阵。

原理：对于下三角矩阵来说，大约有一半的元素为零，这些元素不必存储，只需存储下三角部分的非零元素。

三、主要仪器设备计算机一台
4、实验主程序#include<stdio、h>int main(void){int
a[15],b[5][5]={{1},{2,3},{4,5,6},{7,8,9,10},{11,12,13,14, 15}},i,j,k;for(i=0,k=0;i<5;++i)for(j=0;j<=i;++j){a[k]=b[i ][j];++k;} for(i=0;i<15;++i)
printf("%d ",a[i]);
printf("\n");for(i=0;i<5;++i){for(j=0;j<5;++j){if(j<=i)pr intf("%-3d",a[i*(i+1)/2+j]);elseprintf("%-
3d",0);}putchar(\n);}getchar();return 0;}实验结果
五、实验心得通过实验学习，理解了下三角矩阵的压缩存储的算法，了解到像了下三角矩阵这样的规则矩阵可以压缩存储，极大节省了空间，使我受益匪浅。

第 1 页共 1 页。

矩阵的压缩存储前⾔ ⼀⼊编程深似海，从此砖头是爱⼈，⽇⽇搬，夜夜搬，搬到天荒地⽼，精尽⼈亡，直教⼈失去了⾃我，忘记了时间，忽然之间发现九⽉份快没了，赶紧写篇博客打个卡，证明⼀下我还活着。

数组与矩阵 数组是由⼀组相同类型的数据元素构成的有限序列，访问数据元素的⽅式是使⽤元素各⾃的序号进⾏访问，也就是下标。

数组它本⾝是线性表的推⼴，⼀维数组就是⼀个向量形式的线性表，⼆维数组就是由⼀维数组组成的线性表。

在许多科学计算和⼯程应⽤中，经常要⽤到矩阵的概念，我们⽤的最多的其实就是Mysql的表，表数据都是⾏列存储，这就是矩阵。

由于矩阵具有元素数⽬固定以及元素按下标关系有序排列等特点，所以在使⽤⾼级语⾔编程时，⼀般都是⽤⼆维数组来存储矩阵。

数组的顺序存储为什么是顺序存储？ 我想问这个问题就太低级了。

因为它是数组，数据的存储⽅式分为顺序存储和链式存储两种，数组⼀旦被定义，他的维数和维界就已固定，除结构的初始化和销毁外，数组只会有存取元素和修改元素的操作，不存在插⼊和删除操作，所以数组适合⽤顺序存储。

数组存放在内存中的映射关系 数组可以是多维的，但是内存空间却是⼀维的，所以我们就要把多维数组通过⼀定的映射顺序把它变成⼀维的，然后存储到内存空间之中。

在⼤多数⾼级编程语⾔中，多维数组在内存中通常有两种不同的顺序存储⽅式，按⾏优先顺序存储和按列优先顺序存储。

举个例⼦，以下3⾏4列的⼀个⼆维数组矩阵：a1,a2,a3,a4b1,b2,b3,b4c1,c2,c3,c4 按⾏优先顺序存储： 按列优先顺序存储：地址计算 地址计算的意思就是给定数组下标，求在⼀维内存空间的地址，从⽽取出数据。

我们先来看⼀维数组的地址计算 ⼀维数组内的元素只有⼀个下标，存储⽅法和普通的线性表⼀样。

如⼀维数组 A = [a1,a2,a3,......ai,.........,an]，每个元素占⽤size个存储单元（就是内存⼤⼩），那么元素ai的存储地址为 A[0]的位置 + (i-1)*size再来看⼆维数组的地址计算 以⼆维数组Amn为例，⾸元素为A[0][0]，数组中任意元素A[i][j]的地址为：A[0][0]的位置 + （n * (i-1) + (j-1)）* size；⽐如：⼀个5⾏4列的⼆维数组A，按⾏存储，其中每个元素占2个存储单元，⾸元素地址是1000，求第3⾏第2列的元素在内存中的地址。

引言概述本文是对工程力学中压缩实验的一个实验报告样本进行详细分析和讨论。

压缩实验是工程力学中非常重要的实验之一，通过对材料在受到压缩力作用下的性能进行研究，可以了解材料的强度、刚度以及变形等特性。

本报告将从实验目的、实验装置、实验步骤、实验结果和分析等五个大点进行阐述，每个大点下分别包含59个小点来详细阐述。

正文内容一、实验目的1.1确定材料的抗压强度1.2研究材料的应力应变关系1.3分析材料的变形特性1.4了解压缩实验的基本原理和方法1.5掌握实验操作和数据处理的技巧二、实验装置2.1压力传感器：用于测量加载给试样的压缩力2.2位移传感器：用于测量试样的变形2.3实验机：用于加载试样，并记录加载过程中的数据2.4数据采集系统：用于记录并处理实验数据三、实验步骤3.1准备试样：根据实验要求选择适当的试样，并进行表面的清洁和标记3.2安装试样：将试样放置在实验机的加载平台上，并进行固定3.3调整实验参数：根据实验要求，设置加载速度、加载范围和数据采集频率等参数3.4进行实验：开始加载试样，并记录加载过程中的压力和变形数据3.5结束实验：当试样出现破坏或达到实验要求的加载条件时，停止加载，并记录相应的数据四、实验结果和分析4.1压力位移曲线：根据实验数据绘制压力位移曲线，分析材料在不同加载条件下的变形行为4.2在加载过程中监测的数据：包括压力、变形、位移速度等数据的变化趋势和规律4.3压力和变形的关系：通过对实验数据进行处理和分析，计算材料的应力和应变，研究材料的力学性能4.4材料的抗压强度：根据实验结果确定材料的抗压强度，比较不同试样的差异4.5讨论：根据实验结果和分析，对材料的性能进行讨论，提出问题和改进方法等五、总结本文对工程力学中压缩实验进行了详细的分析和讨论。

通过实验目的、实验装置、实验步骤、实验结果和分析等五个大点进行了阐述。

实验结果和分析部分包括压力位移曲线、加载过程中的数据变化趋势和规律，材料的抗压强度以及力学性能的研究等内容。

实验：矩阵的压缩存储及相关操作一、实验目的1 理解稀疏矩阵的三元组顺序表类型定义，2 掌握稀疏矩阵的输入( 即根据输入数据创建矩阵的三元组顺序表)3 掌握稀疏矩阵输出(即根据矩阵的三元组顺序表在屏幕上输出完整的矩阵)4 掌握稀疏矩阵的转置算法。

二、实验内容1．编写程序任意输入一个稀疏矩阵M，用三元组顺序表压缩存储该稀疏矩阵M，然后求其转置矩阵T，并输出转置矩阵T。

运行效果图:注意:矩阵要求用三元组顺序表存储三、思考与提高如何计算两个三元组表表示的稀疏矩阵的乘积？【方案一】程序代码：#include <iostream>#include <malloc.h>#include <cmath>#include <iomanip>using namespace std;#define MAXSIZE 12500#define OK 1#define ERROR 0typedef int Status;typedef int ElemType;//#define Triple Mtypedef struct{int i,j;ElemType e;}Triple;typedef struct{Triple data[MAXSIZE+1];int mu,nu,tu;}TSMatrix;CreateSMatrix(TSMatrix &M){int i,m,n;ElemType e;Status k;cout<<"输入矩阵的行、列数、非零元素个数：\n";//Mcin>>M.mu>>M.nu>>M.tu;M.data[0].i=0; // 为以下比较顺序做准备for(i=1;i<=M.tu;i++){do{//printf("请按行序顺序输入第%d个非零元素所在的行(1～%d),列(1～%d),元素值：",i,M.mu,M.nu);cout<<"第"<<i<<"个数所在的行列号元素值\n";//scanf("%d,%d,%d",&m,&n,&e);cin>>m>>n>>e;k=0;if(m<1||m>M.mu||n<1||n>M.nu) // 行或列超出范围k=1;if(m<M.data[i-1].i||m==M.data[i-1].i&&n<=M.data[i-1].j) // 行或列的顺序有错k=1;}while(k); //对于非法操作不予存储，直到输入正确位置M.data[i].i=m;M.data[i].j=n;M.data[i].e=e;}return OK;}Status TransposeSMatrix(TSMatrix M,TSMatrix &T){ // 求稀疏矩阵M的转置矩阵T。

一、实验目的1. 了解矩阵压缩存储的基本原理和方法。

2. 掌握稀疏矩阵的压缩存储方法，包括三元组顺序表存储和压缩存储下三角矩阵。

3. 熟悉矩阵压缩存储在数据结构中的应用，提高数据存储效率。

4. 通过实验验证矩阵压缩存储方法的有效性和优越性。

二、实验原理矩阵压缩存储是一种针对稀疏矩阵的存储方法，通过压缩存储非零元素，减少存储空间，提高数据存储效率。

稀疏矩阵是指矩阵中大部分元素为0的矩阵，其特点是存储空间利用率低，计算效率低。

矩阵压缩存储主要有以下几种方法：1. 三元组顺序表存储：将稀疏矩阵中的非零元素及其对应的行、列索引存储在一个三元组中，形成顺序表。

2. 压缩存储下三角矩阵：对于下三角矩阵，只存储主对角线以下的非零元素及其对应的行、列索引。

3. 压缩存储上三角矩阵：对于上三角矩阵，只存储主对角线以上的非零元素及其对应的行、列索引。

三、实验内容1. 实现稀疏矩阵的三元组顺序表存储。

2. 实现压缩存储下三角矩阵和上三角矩阵。

3. 实现矩阵转置算法，包括压缩存储下三角矩阵的转置和压缩存储上三角矩阵的转置。

4. 比较不同存储方法的存储空间和计算效率。

四、实验步骤1. 创建一个稀疏矩阵，随机生成非零元素及其对应的行、列索引。

2. 实现稀疏矩阵的三元组顺序表存储，将非零元素及其对应的行、列索引存储在一个顺序表中。

3. 实现压缩存储下三角矩阵，只存储主对角线以下的非零元素及其对应的行、列索引。

4. 实现压缩存储上三角矩阵，只存储主对角线以上的非零元素及其对应的行、列索引。

5. 实现矩阵转置算法，包括压缩存储下三角矩阵的转置和压缩存储上三角矩阵的转置。

6. 比较不同存储方法的存储空间和计算效率。

五、实验结果与分析1. 三元组顺序表存储存储空间：n（非零元素个数） 3计算效率：O(n)2. 压缩存储下三角矩阵存储空间：n（非零元素个数） 3计算效率：O(n)3. 压缩存储上三角矩阵存储空间：n（非零元素个数） 3计算效率：O(n)4. 矩阵转置算法计算效率：O(n)通过实验结果可以看出，压缩存储下三角矩阵和上三角矩阵的存储空间和计算效率与三元组顺序表存储相当，且对于稀疏矩阵，压缩存储方法可以显著减少存储空间，提高数据存储效率。

实验5 矩阵的压缩存储实现1. 实验要求(1) 实现矩阵（对称阵和稀疏阵）的压缩存储结构设计；(2) 实现矩阵的操作（稀疏矩阵快速转置和乘法）算法设计；2. 主要实验方法(1) 设计算法思想；(2) 编写算法代码；(3) 运行算法代码，并分析算法的效率；3. 实验内容实验5.1 对称矩阵顺序表存储表示（一）具体要求：（1）初始化一个对称矩阵（2）显示对称矩阵（3）任意取对称矩阵第i行第j列的值（二）测试: 输入如下对称矩阵，测试存储和访问情况对称矩阵为：1 1 0 51 2 0 70 0 1 55 7 5 7实验5.2 稀疏矩阵的三元组顺序表存储表示，及稀疏矩阵快速转置（一）具体要求：（1）初始化一个稀疏矩阵（2）显示初始化后的稀疏矩阵（3）转置（4）显示转置后的稀疏矩阵（二）测试: 输入如下稀疏矩阵，测试用三元组顺序表存储的稀疏矩阵的转置结果稀疏矩阵为：0 0 0 11 0 0 10 0 1 0实验5.3 稀疏矩阵的行逻辑链接顺序表存储表示，及稀疏矩阵乘法（一）具体要求：（1）初始化两个个稀疏矩阵a,b（2）获取这两个矩阵的各行第一个非零元的位置表rpos（2）显示初始化后的稀疏矩阵a,b（3）矩阵a和b相乘，结果存入矩阵c，即c=a*b（4）显示矩阵c（二）测试: 输入如下稀疏矩阵，测试用行逻辑链接顺序表存储的稀疏矩阵的乘积结果稀疏矩阵a为：3 0 0 50 -1 0 02 0 0 0稀疏矩阵b为：0 21 0-2 40 0乘积结果矩阵c为0 6-1 00 44. 实验重点和难点(1) 重点：特殊矩阵的压缩存储结构设计。

(2) 难点：稀疏矩阵的压缩存储结构的设计及操作算法设计。

5. 实验结果与分析（必须写这部分）应用文字、表格、图形等将数据表示出来6. 实验总结与体会必须写这部分7. 部分代码指导实验5.1实验5.2实验5.3。

下三角矩阵的压缩存储下三角矩阵的压缩存储是一种有效的数据结构，用于节省内存空间和提高数据访问效率。

下面将介绍下三角矩阵的定义和压缩存储方法。

一、下三角矩阵的定义下三角矩阵是指主对角线以上的元素均为0的矩阵。

例如，一个3阶的下三角矩阵可以表示为：a21 a22 0a31 a32 a33其中，a11、a21、a22、a31、a32和a33为矩阵中的元素。

下三角矩阵的特点是上三角部分全为0，只有下三角部分有非零元素。

由于下三角矩阵的上三角部分全为0，对于大规模矩阵而言，存储这些0元素是一种浪费。

因此，可以使用一维数组来压缩存储下三角矩阵。

具体的压缩存储方法是，将下三角矩阵按行从上到下、从左到右的顺序压缩成一个一维数组。

压缩后的数组长度为矩阵下三角部分的元素个数，即n * (n + 1) / 2，其中n为矩阵的阶数。

例如，对于上述的3阶下三角矩阵，按行压缩后的一维数组为：a11, a21, a22, a31, a32, a33压缩后的一维数组长度为6，分别对应着下三角矩阵中的非零元素。

在压缩存储的时候，需要注意矩阵元素在一维数组中的下标与矩阵中的行列下标之间的对应关系。

一维数组的下标可以通过如下公式计算得到：arrayIndex = i * (i + 1) / 2 + j其中，i和j分别为矩阵元素在矩阵中的行列下标，arrayIndex为该元素在一维数组中的下标。

通过下三角矩阵的压缩存储，可以减少存储空间的占用，并且提高访问矩阵元素的效率。

在实际应用中，下三角矩阵的压缩存储常用于稀疏矩阵的表示和处理。

总结：下三角矩阵的压缩存储是一种有效的数据结构，可以节省内存空间，并提高数据访问效率。

压缩存储的方法是将下三角矩阵按行压缩成一维数组，通过计算数组下标与矩阵元素在矩阵中的下标之间的对应关系，可以实现矩阵元素的访问。

这种压缩存储方式在稀疏矩阵的处理中具有广泛的应用。

三对角矩阵压缩存储转置实验题目：实验八——矩阵实验程序设计2问题分析：1、题目要求：设计算法求三对角矩阵在压缩存储下的转置矩阵2、设计思路：定义一种新的数据结构三元组用来存放数据，该数据结构为以一维数组，结点包括三个量i、j、v，i、j分别用来记录矩阵中元素的下标，v用来记录元素值，这样交换时，仅对下标交换即可达到转置矩阵的目的3、输入与输出：只需输入三对角矩阵中所有非零元素的值，存放在三元组里，输出时，程序自动在没有数字元素处补零，以矩阵形式输出；4、转置：调用转置函数进行转置，转置时仅交换数据的下标5、测试数据：A、输入矩阵阶数：4输入第一行的两个元素：1 2输入第二、三行的元素，各三个：4 5 67 8 9输入最后一行的两个元素：3 8预测结果：原矩阵：转置后矩阵：1 2 0 0 1 4 0 04 5 6 0 2 5 7 00 7 8 9 0 6 8 30 0 3 8 0 0 9 8B、输入矩阵阶数：5输入第一行的两个元素：12 45输入第二、三行的元素，各三个：77 88 9944 55 6611 22 33输入最后一行的两个元素：14 82预测结果：原矩阵：转置后矩阵：12 45 0 0 0 12 77 0 0 077 88 99 0 0 45 88 44 0 00 44 55 66 0 0 99 55 11 00 0 11 22 33 0 0 66 22 140 0 0 14 82 0 0 0 33 82概要设计：1、为了实现上述程序功能，需定义三元组数据结构用来存储数据，建立三元组输入函数，输出函数和矩阵转置函数，最后在屏幕上输出结果；2、本程序包含4个函数：⑴主函数main()⑵三对焦矩阵建立函数Setmatrix()⑶转置函数Trabsmatrix()⑷输出函数Tsmatrixout()各函数关系如下：详细设计：1、数据结构与结点类型：typedef struct //定义结点类型{int i,j,v;}node;typedef struct //定义矩阵类型{node data[max];}TSmatrix;2、各函数的基本操作⑴三对角矩阵的建立函数TSmatrix *Setmatrix(){申请空间；输入第一行的两个元素；输入2~n-1行的元素，每行3个；返回；}⑵转置函数TSmatrix *Trabsmatrix(TSmatrix *T){建立新的三元组；把原三元组数据下标交换，放入新组；返回新三元组；}⑶输出函数void TSmatrixout(TSmatrix *T){定义变量a 、b=0；如果三元表中数据下表等于a 、b 的值，则输出该元素；否则，输出0；a++’;b++;}main() Setmatrix() Trabsmatrix() Tsmatrixout()源代码：#include#include#define max 20typedef struct //定义结点类型{}node;typedef struct //定义矩阵类型{node data[max];int m;}TSmatrix;TSmatrix *Setmatrix() //建立三对角矩阵{TSmatrix *T;T=(TSmatrix *)malloc(sizeof(TSmatrix));printf("请输入矩阵阶数:");scanf("%d",&T->m);printf("建立三对角矩阵:\n");printf("输入第一行的两个数：\n"); //第一行只有两个元素，单独输入 scanf("%d %d",&T->data[0].v,&T->data[1].v);T->data[0].i=0;T->data[0].j=0;T->data[1].i=0;T->data[1].j=1;printf("输入第二行至第%d行的数（每行3个）：\n",T->m-1);int t=2;for(int p=1;pm-1;p++) //循环输入2~n-1行的元素，每行3个for(int q=p-1;q<p+2;q++)< p="">{T->data[t].j=q;T->data[t].i=p;scanf("%d",&T->data[t].v);t++;}printf("输入最后一行的两个数：\n"); //输入最后一行的两个元素scanf("%d %d",&T->data[3*T->m-4].v,&T->data[3*T->m-3].v);T->data[3*T->m-4].i=T->m-1;T->data[3*T->m-4].j=T->m-2;T->data[3*T->m-3].i=T->m-1;T->data[3*T->m-3].j=T->m-1;return T;}TSmatrix *Trabsmatrix(TSmatrix *T) //三对角矩阵转置{int n,temp;TSmatrix *F;F=(TSmatrix *)malloc(sizeof(TSmatrix));F->m=T->m;for(n=0;n<3*T->m-2;n++){ //将结点信息存入新三元组表中temp=2*(T->data[n].j)+(T->data[n].i); //计算待存入三元数组下标F->data[temp].i=T->data[n].j; //进行交换F->data[temp].j=T->data[n].i;F->data[temp].v=T->data[n].v;}return F;}void TSmatrixout(TSmatrix *T) //三对角矩阵输出{int a,b,n;n=0;for(a=0;am;a++){ //输出三对角矩阵，下标只有数据则输出对应元素值for(b=0;bm;b++){ //否则输出0if((T->data[n].i==a)&&(T->data[n].j==b)){printf("%d ",T->data[n].v);n++;}elseprintf("0 ");}printf("\n");}}void main(){TSmatrix *T;T=Setmatrix();printf("原三对角矩阵:\n");TSmatrixout(T);T=Trabsmatrix(T);printf("转置后三对角矩阵:\n");TSmatrixout(T);}调试分析：1、进行矩阵转置时本来采用把两数据进行交换的方法，但这样做容易使程序变的复杂，可读性变差，于是采用交换数据下标的方式，使思路更加清晰，也便于操作。

数据结构实验报告学号：2015111898姓名：许明华专业：计算机科学与技术知识范畴：数组与广义表完成日期：2017年04月21日实验题目：基于压缩存储的半三角矩阵乘法运算的实现实验内容及要求：已知两个n阶下半三角矩阵的乘积仍为n阶下半三角矩阵。

编程输入两个n阶下半三角矩阵，输出这两个矩阵的乘积。

要求n阶下半三角矩阵采用一维数组压缩存储（即只存储下半三角）。

程序先从键盘(或字符文件)输入n值，建立三个矩阵的一维数组动态存储结构，然后从键盘(或字符文件)输入两个半三角矩阵，最后输出计算结果到屏幕上(或另一个字符文件中)。

例如：键盘输入为：312 34 5 6-1-2 -3-4 -5 -6则输出为：-1-8 -9-38 -45 -36实验目的：掌握半三角矩阵的顺序存储结构。

数据结构设计简要描述：序言：这是本学期第五个实验，本实验是要求我们将两个二维半三角矩阵压缩存储为一维矩阵，并对其进行乘法操作，得到一个一维的压缩存储矩阵，并将其打印输出；数据结构简单设计：本实验主要可分为两个大的模块（压缩存储矩阵、压缩矩阵相乘）。

第一，我们通过键盘键入一个数组的阶数，然后输入两个半三角矩阵，，但是这两个半三角矩阵要进行压缩存储为一维矩阵，关键操作即（m = （i*（i+1））/2 + j），即可将二维下标转化为一维下标；第二，运用公式 i]][[*]][[jjkbkia来进行相乘操作，求得两个下三角矩阵的乘积。

算法设计简要描述：1，通过（m = （i*（i+1））/2 + j）将二维下标转化为一维下标进行输入，得到压缩存储矩阵；2，运用公式 i]][[*]][[jjkbkia进行乘积操作，但是乘数矩阵下标和结果矩阵的下标并没有同步，所以运用三个公式来进行分离操作，m1 = （i*（i+1））/2 + k；m2 = (k*（k+1））/2 + j；m = （i*（i+1））/2 + j；c [m] += a[m1]*b[m2];这样即能实现相乘的操作，但是每一次的c[m]没有进行初始化，所以在每一次得到m值后，进行操作c[m] = 0;输入/输出设计简要描述：输入：1，输入下三角存储矩阵的阶数n；2，输入第一个下三角矩阵，如1 2 3 4 5 6；3，输入第二个下三角矩阵，如-1 -2 -3 -4 -5 -6；输出：1，输入2操作后，按存储矩阵格式输出打印第一个下三角矩阵；2，输入3操作后，按存储矩阵格式输出打印第二个下三角矩阵，并输出打印两个矩阵的乘积矩阵编程语言说明：1，编程软件，CodeBlocks 16.0；2，代码均用C语言实现；3，输入输出采用C语言的printf和scanf函数；4，程序注释采用C/C++规范；主要函数说明：void input_Arr( int, int );//输入半三角矩阵声明void print( int, int );//输出打印半三角矩阵声明int print_Array( int, int, int, int);//两个半三角矩阵的乘法运算声明程序测试简要报告：见截图：源程序代码：#include<stdio.h>//函数声明部分void input_Arr( int, int );//输入半三角矩阵声明void print( int, int );//输出打印半三角矩阵声明int print_Array( int, int, int, int);//两个半三角矩阵的乘法运算声明//输入半三角矩阵void input_Arr(int a[], int n){int m;printf("请输入数组：\n");for(int i = 0 ; i < n ; i ++){for(int j = 0 ; j <= i ; j ++)//这里在存储时我只存储了下三角对应的数组元素，，所以是j<=i,而不是j<n{m = (i*(i + 1))/2 + j;//这一步操作是关键所在，因为要将二维数组压缩存储为一维数组的话，我们来看，//二维数组的下标为i和j，但是一维数组的下标只有一个，怎么办呢，//这时候我们就可以根据公式来将二维数组的下标转化为对应的一维数组的下标，所得到的就是对应位置的对应下标scanf("%d",&a[m]); //输入对应的下三角矩阵}}}//输出打印半三角矩阵void print(int a[], int n){int m = 0;for(int i = 0 ; i < n ; i ++){for(int j = 0 ; j <= i ; j ++){m = (i*(i + 1))/2 + j;//打印操作，同上面printf("%d ",a[m]);}printf("\n");}}//两个半三角矩阵的乘法运算int print_Array(int a[], int b[], int c[], int n){int i = 0, j = 0;int k, m, m1, m2 ;//k为进行乘法操作过程的中间变量，m为乘积过后的一维压缩数组的下标，m1为第一个数组的压缩存储的下标，m2为第二个数组的压缩存储的下标for( i = 0; i < n ; i ++){for( j = 0; j <= i ; j ++)//限定在下三角元素中进行{m = (i*(i + 1))/2 + j;//将二维下标转化为压缩存储的一维下标c[m] = 0; //这一步很重要，我想了很久才想到这一步的，就是每一次将c[m]的初值赋为0，因为后面要执行c[m] +=操作，如果不仅赋初值的话，每次的第一个c[m]就是没有进行初始化，//那它就是一个无穷大的数，得出来的乘积之和就是一个无穷大的数for(k = j ; k <= i ; k ++)//由于是下三角进行相乘，所以所有的上三角元素都为零，不需要再进行乘积操作，{m1 = (i*(i + 1))/2 + k;//第一个压缩存储的数组的一维下标m2 = (k*(k + 1))/2 + j;//第二个压缩存储的数组的一维下标c[m] += a[m1]*b[m2];//进行乘积操作}}}return 0;}int main(){int n ;//数组长度nint a[100],b[100],c[100];//定义三个一维数组printf("请输入数组大小n：\n");scanf("%d",&n);input_Arr(a,n);//调用输入下三角矩阵函数printf("数组一为：\n");print(a,n);//输出下三角矩阵input_Arr(b,n);//同上printf("数组二为：\n");print(b,n);//同上print_Array(a,b,c,n);//调用下三角矩阵相乘函数printf("数组的乘积为：\n");print(c,n);//输出相乘之后的下三角矩阵return 0; }。

三角矩阵压缩存储在计算机科学和数学领域，矩阵是一个非常常见的概念。

矩阵可以用来表示线性方程组、图像处理、网络分析等众多领域的问题。

然而，对于大规模的矩阵，存储和计算的开销往往会非常大。

为了解决这个问题，人们提出了一种称为“三角矩阵压缩存储”的方法，可以显著减少存储和计算的开销。

三角矩阵是指上三角矩阵和下三角矩阵。

上三角矩阵是指除了主对角线及其上方的元素外，其余元素都为零的矩阵。

下三角矩阵则是指除了主对角线及其下方的元素外，其余元素都为零的矩阵。

三角矩阵的特点是非常稀疏，即大部分元素都为零，因此可以通过压缩存储来节省空间。

三角矩阵压缩存储的基本思想是只存储非零元素及其对应的行列索引。

对于上三角矩阵来说，我们可以将矩阵按照主对角线划分为两部分，上半部分为非零元素，下半部分为零元素。

然后，我们只需要按照一定的顺序（如按列优先）将非零元素存储起来，同时记录它们的行列索引。

这样，我们可以用一个一维数组来存储所有的非零元素，用一个一维数组来存储它们的行索引，用一个一维数组来存储它们的列索引。

对于下三角矩阵来说，也可以采用类似的方法进行压缩存储。

只不过这次是将矩阵按照主对角线划分为两部分，下半部分为非零元素，上半部分为零元素。

同样地，我们只需要按照一定的顺序将非零元素存储起来，并记录它们的行列索引。

三角矩阵压缩存储的好处是显而易见的。

由于三角矩阵的稀疏性，我们可以大大减少存储空间的开销。

而且，在进行一些特定的运算时，如矩阵乘法、矩阵求逆等，我们也可以大大减少计算的复杂度。

因为在三角矩阵中，大部分元素都为零，所以我们可以直接忽略这些元素，只对非零元素进行运算。

除了上述的基本压缩存储方法外，还有一些其他的优化方法。

比如，在存储非零元素的同时，我们可以将它们按照一定的规则进行排序，以便提高访问效率。

另外，我们还可以利用对称性来减少存储空间的开销。

例如，对于对称的三角矩阵，我们只需要存储其中一半的非零元素即可。

三角矩阵压缩存储是一种非常有效的方法，可以显著减少存储和计算的开销。

中北大学数据结构课程设计说明书2011年12月20日1.设计任务概述问题描述：1）对于特殊矩阵可以通过压缩存储减少存储空间。

基本要求：1)针对多种特殊矩阵进行压缩存储，并能显示压缩后的相关地址和值；2)输入在原来特殊矩阵中的地址，要求能从压缩后的矩阵中读出相应的值。

2.本设计所采用的数据结构应用了关于数组以及顺序存储3.功能模块详细设计3.1 详细设计思想特殊矩阵：值相同元素或者零元素分布有一定规律的矩阵称为特殊矩阵例:对称矩阵、上（下）三角矩阵都是特殊矩阵特殊矩阵压缩存储(以对称矩阵为例)对称矩阵是满足下面条件的n 阶矩阵: aij= aji 1<= i,j<= nk= 0 1 2 3 4 5 6 n(n+1)/2-1对称矩阵元素可以只存储下三角部分，共需n(n+1)/2 个单元的空间( 三角矩阵的存储方式类似）以一维数组sa[0..n(n+1)/2-1]作为n 阶对称矩阵A的存储结构A中任意一元素aij与它的存储位置sa[k] 之间关系：k= 0 1 2 3 4 5 6 n(n+1)/2-13.2 核心代码static shangsanjiao(int n){int i,j,k,z,g;int L[100][100],SA[100];printf("请输入您要压缩矩阵的行列数\n");scanf("%d",&n);printf("请输入您的矩阵内元素：\n");for(i=1;i<n+1;i++)for(j=1;j<n+1;j++){scanf("%d",&L[i][j]);if(i<=j)k=j*(j-1)/2+i-1;elsek=n*(n+1)/2;SA[k]=L[i][j];}printf("您输入的矩阵为：\n");for(i=1;i<n+1;i++){for(j=1;j<n+1;j++)printf("%d ",L[i][j]);printf("\n");}printf("压缩存储后：\n");for(k=0;k<n*(n+1)/2+1;k++)printf("%d %d\n",k,SA[k]);printf("若要读取矩阵的值请输入'100'退出输入'000'。

一、实验目的和要求（1）掌握各种特殊矩阵如对称矩阵、上下三角矩阵和对角矩阵的压缩存储方法。

（2）掌握稀疏矩阵的各种存储结构以及基本运算实现算法。

（3）掌握广义表的递归特性、存储结构以及基本运算实现算法。

二、实验环境、内容和方法实验内容：①打开Visual C++6.0并输入实验指导书上的程序，并进行调试和运行。

②自行尝试编写第六个实验。

实验方法：（一）综合运用课本所学的知识，用不同的算法实现在不同的程序功能。

（二）结合指导老师的指导，解决程序中的问题，正确解决实际中存在的异常情况，逐步改善功能。

（三）根据实验内容，编译程序。

实验环境：Windows xp Visual C++6.0三、实验过程描述实验①以下是一个5*5阶的螺旋方阵。

设计一个程序输出该形式的n*n阶方阵。

1 2 3 4 516 17 18 19 615 24 25 20 714 23 22 21 813 12 11 10 9一、打开Visual C++6.0并输入如下程序#include <stdio.h>#define MaxLen 10void fun(int a[MaxLen][MaxLen],int n){int i,j,k=0,m;if (n%2==0)m=n/2;elsem=n/2+1;for (i=0;i<m;i++){for (j=i;j<n-i;j++){k++;a[i][j]=k;}for (j=i+1;j<n-i;j++){k++;a[j][n-i-1]=k;}for (j=n-i-2;j>=i;j--){k++;a[n-i-1][j]=k;}for (j=n-i-2;j>=i+1;j--){k++;a[j][i]=k;}}}void main(){int n,i,j;int a[MaxLen][MaxLen];printf("\n");printf("输入n(n<10):");scanf("%d",&n);fun(a,n);printf("%d阶数字方阵如下:\n",n);for (i=0;i<n;i++){for (j=0;j<n;j++)printf("%4d",a[i][j]);printf("\n");}printf("\n");}二、,编译并连接此程序，如图三、运行此程序，如图实验②假设n*n的稀疏矩阵A采用三元组表示，设计一个程序实现如下功能：（1）生成如下两个稀疏矩阵的三元组a和b：a:1 0 3 0 b: 3 0 0 00 1 0 0 0 4 0 00 0 1 0 0 0 1 00 0 1 1 0 0 0 2(2)输出a转置矩阵的三元组(3)输出a+b的三元组(4) 输出a*b的三元组一、输入如图所示程序#include <stdio.h>#define N 4typedef int ElemType;#define MaxSize 100typedef struct{ int r;int c;ElemType d;} TupNode;typedef struct{ int rows;int cols;int nums;TupNode data[MaxSize];} TSMatrix;void CreatMat(TSMatrix &t,ElemType A[N][N]){int i,j;t.rows=N;t.cols=N;t.nums=0;for (i=0;i<N;i++){for (j=0;j<N;j++)if (A[i][j]!=0){t.data[t.nums].r=i;t.data[t.nums].c=j;t.data[t.nums].d=A[i][j];t.nums++;}}}void DispMat(TSMatrix t){int i;if (t.nums<=0)return;printf("\t%d\t%d\t%d\n",t.rows,t.cols,t.nums);printf("\t------------------\n");for (i=0;i<t.nums;i++)printf("\t%d\t%d\t%d\n",t.data[i].r,t.data[i].c,t.data[i].d); }void TranMat(TSMatrix t,TSMatrix &tb){int p,q=0,v;tb.rows=t.cols;tb.cols=t.rows;tb.nums=t.nums;if (t.nums!=0){for (v=0;v<t.cols;v++)for (p=0;p<t.nums;p++)if (t.data[p].c==v){tb.data[q].r=t.data[p].c;tb.data[q].c=t.data[p].r;tb.data[q].d=t.data[p].d;q++;}}}int MatAdd(TSMatrix a,TSMatrix b,TSMatrix &c) {int i=0,j=0,k=0;ElemType v;if (a.rows!=b.rows || a.cols!=b.cols)return 0;c.rows=a.rows;c.cols=a.cols;while (i<a.nums && j<b.nums){if (a.data[i].r==b.data[j].r){if(a.data[i].c<b.data[j].c){c.data[k].r=a.data[i].r;c.data[k].c=a.data[i].c;c.data[k].d=a.data[i].d;k++;i++;}else if (a.data[i].c>b.data[j].c){c.data[k].r=b.data[j].r;c.data[k].c=b.data[j].c;c.data[k].d=b.data[j].d;k++;j++;}else{v=a.data[i].d+b.data[j].d;if (v!=0){c.data[k].r=a.data[i].r;c.data[k].c=a.data[i].c;c.data[k].d=v;k++;}i++;j++;}}else if (a.data[i].r<b.data[j].r){c.data[k].r=a.data[i].r;c.data[k].c=a.data[i].c;c.data[k].d=a.data[i].d;k++;i++;}else{c.data[k].r=b.data[j].r;c.data[k].c=b.data[j].c;c.data[k].d=b.data[j].d;k++;j++;}c.nums=k;}return 1;}int value(TSMatrix c,int i,int j){int k=0;while (k<c.nums && (c.data[k].r!=i || c.data[k].c!=j)) k++;if (k<c.nums)return(c.data[k].d);elsereturn(0);}int MatMul(TSMatrix a,TSMatrix b,TSMatrix &c){int i,j,k,p=0;ElemType s;if (a.cols!=b.rows)return 0;for (i=0;i<a.rows;i++)for (j=0;j<b.cols;j++){s=0;for (k=0;k<a.cols;k++)s=s+value(a,i,k)*value(b,k,j);if (s!=0){c.data[p].r=i;c.data[p].c=j;c.data[p].d=s;p++;}}c.rows=a.rows;c.cols=b.cols;c.nums=p;return 1;}void main(){ElemType a1[N][N]={{1,0,3,0},{0,1,0,0},{0,0,1,0},{0,0,1,1}};ElemType b1[N][N]={{3,0,0,0},{0,4,0,0},{0,0,1,0},{0,0,0,2}};TSMatrix a,b,c;CreatMat(a,a1);CreatMat(b,b1);printf("a的三元组:\n");DispMat(a);printf("b的三元组:\n");DispMat(b);printf("a转置为c\n");TranMat(a,c);printf("c的三元组:\n");DispMat(c);printf("c=a+b\n");MatAdd(a,b,c);printf("c的三元组:\n");DispMat(c);printf("c=a*b\n");MatMul(a,b,c);printf("c的三元组:\n");DispMat(c);}二、程序运行结果如图实验③编写一个程序实现广义表的各种运算，并在此基本上设计一个程序完成如下功能：（1）建立广义表g=“(b,(b,a,(#),d),((a,b),c,((#))))”的链式存储结构；（2）输出广义表g的长度；（3）输出广义表g的深度；（4）输出广义表g的最大原子；一、输入如图所示程序#include <stdio.h>#include <malloc.h>typedef char ElemType;typedef struct lnode{ int tag;union{ElemType data;struct lnode *sublist;}val;struct lnode *link;} GLNode;GLNode *CreatGL(char *&s){GLNode *h;char ch;ch=*s++;if (ch!='\0'){h=(GLNode *)malloc(sizeof(GLNode));if (ch=='('){h->tag=1;h->val.sublist=CreatGL(s);}else if (ch==')')h=NULL;else{h->tag=0;h->val.data=ch;}}else h=NULL;ch=*s++;if (h!=NULL)if (ch==',')h->link=CreatGL(s);elseh->link=NULL;return h;}int GLLength(GLNode *g){int n=0;g=g->val.sublist;while (g!=NULL){n++;g=g->link;}return n;}int GLDepth(GLNode *g){int max=0,dep;if (g->tag==0)return 0;g=g->val.sublist;if (g==NULL)return 1;while (g!=NULL){if (g->tag==1){dep=GLDepth(g);if (dep>max) max=dep;}g=g->link;}return(max+1);}void DispGL(GLNode *g){if (g!=NULL){if (g->tag==1){printf("(");if (g->val.sublist==NULL) printf("");else DispGL(g->val.sublist);}else printf("%c", g->val.data);if (g->tag==1) printf(")");if (g->link!=NULL){printf(",");DispGL(g->link);}}}void main(){GLNode *g;char *str="(b,(b,a,a),((a,b),c))";g=CreatGL(str);printf(" 广义表g:");DispGL(g);printf("\n");printf(" 广义表g的长度:%d\n",GLLength(g));printf(" 广义表g的深度:%d\n",GLDepth(g));printf("\n");}二、程序运行结果如图。