1. 数据结构中对称矩阵的压缩存储的一 一对应关系怎么算的
先看上面一个谈雀圆：
下三角有i>=j
第1行一个，第2行两个，。。岁判。，第i-1行i-1个（i, j下标都是从1开始的）
所以含塌第i行前有1+2+...+(i-1)= i(i-1)/2个元素
再看本行，本元素前有j-1个元素
因为计算的是元素之间的位置差，因此就是i(i-1)/2+(j-1)了
下面一个上三角i<j：
对于对称矩阵有a(i,j)=a(j,i)，即行列互换，代入上式即可得
2. 数据结构特殊矩阵压缩存储问题
这个问题出在下标的问题上吧，第一个问题，明确说明第一个非零元素a(1,1)存于B[0]中，所以推导时没问题。
第二个问题并没有说第一个非零元素a(1,1)存于B[0]中，但大多教材推导是，是将第一个非零元素a(0，0)存于B[0]中，所以公式就不一样了，你的推导逻辑没问题。
3. 数据结构（C语言）矩阵压缩存储
A[0][0] 1
A[1][0] A[1][1] 2
A[2][0] A[2][1] A[2][2] 3
A[3][0] A[3][1] A[3][2] A[3][3] 4
A[4][0] A[4][1] A[4][2] A[4][3] A[4][4] 5
A[5][0] A[5][1] A[5][2] A[5][3] A[5][4] A[5][5] 4
偏移位置在 1+2+3+4+5+4=19*4，十六进制为4c，故为1000H+4C=104CH
4. 特殊矩阵的压缩存储
数组是一组偶对(下标值，数据元素值)的集合。在数组中，对于一组有意义的下标，都存在一个与其对应的值。一维数组对应着一个下标值，二维数组对应着两个下标值，如此类推。
数组是由 n(n>1)个具有相同数据类型的数据元素 组成的有序序列，且该序列必须存储在一块地址连续的存储单元中。
数组中的数据元素具有相同数据类型。闭凯敏
数组是一种随机存取结构，给定一组下标，就可以访问与其对应的数据元素。
数组中的数据元素个数是固定的。
计算机的内存结构是一维(线性)地址结构，对于多维数组，将其存放(映射)到内存一维结构时，有个次序约定问题。即必须按某种次序将数组元素排成一列序列，然后将这个线性序列存放到内存中。
二维数组是最简单的多维数组，以此为例说明多维数组存放(映射)到内存一维结构时的次序约定问题。
对于 ，通常有两种顺序存储方式
(1) 行优先顺序(Row Major Order) :将数组元素按行排列，第 i+1个行向量紧接在第 i 个行向量后面。对二维数组，按行优先顺序存储的线性序列为:
PASCAL、C 是按行优先顺序存储的。
(2) 列优先顺序(Column Major Order) :将数组元素按列向量排列，第 j+1 个列向量紧接在第 j 个列向量之后，对二维数组，按列优先顺序存储的线性序列为:
FORTRAN 是按列优先顺序存储的。
设有二维数组 ，若每个元素占用的存储单元数为L个， 表示元素 的首地址，即数组的首地址
(1)以“行优先顺序”存储
第 1 行中的每个元素对应的(首)地址是:
第 m 行中的每个元素对应的(首)地址是:
(2)以“列优先顺序”存储
(1) 第 1 列中的每个元素对应的(首)地址是:
(3) 第 n 列中的每个元素对应的(首)地址是:
特殊矩阵(对称矩阵，对角矩阵，三角矩阵)压缩存储:
多个相同的非零元素只分配一个元素值的存储空间；
零元素不分配空间。
(1)对称矩阵
对称矩阵的特点是:在一个 n 阶方阵中，有 ，其中 1≤i，j≤n，对称矩阵关于主对角线对称，因此只需存储上三角或下三角部分即可。
设有对称矩阵A[i][j]如下图示:
(2)三角矩阵
①下三角矩阵:
设有下三角矩阵 A[i][j]如下图所示:
在下三角矩阵中，主对角线以上的元素是一个常量。存完下三角中的元素之后，紧接着存储对角线上方的常量，因为是同一个常数，所以存一个即可，其压缩存储后如下图所示:
②上三角矩阵
设有上三角矩阵 A[i][j]如下图所示:
在上三角矩阵中, K 与 i,j 的对应关系为:
(3)对轿枝角矩阵
对角矩阵也称为带状矩阵,如下图所示:
在这种三对角矩阵中，所有非零元素都集中在以主对角线为中心的对角区域中，即除了主对角线和它的上下方若干条对角线的元素外，所有其他元素都为零(或同一个常数 C)。
对角矩阵 A 也可以采用压缩存储，将三对角矩阵压缩到向量 SA[k]中去，按以行为主序，顺序的存储其非零元素，按其压缩规律，孙桥找到相应的映象函数。k与i,j的对应关系为:
稀疏矩阵:设矩阵 A 是一个 n*m 的矩阵中有 s 个非零元素，设 δ=s/(n m)，称δ为稀疏因子，如果某一矩阵的稀疏因子δ满足δ≦0.05 时称为稀疏矩阵。对于稀疏矩阵，采用压缩存储方法时，只存储非 0 元素。必须存储非 0 元素的行下标值、列下标值、元素值。
(1)三元组顺序表
若以行序为主序，稀疏矩阵中所有非 0 元素的三元组，就可以得构成该稀疏矩阵的一个三元组顺序表。相应的数据结构定义如下:
(2)十字链表
对于稀疏矩阵，当非 0 元素的个数和位置在操作过程中变化较大时，采用链式存储结构表示比三元组的线性表更方便。
矩阵中非 0 元素的结点所含的域有:行、列、值、行指针(指向同一行的下一个非 0 元)、 列指针(指向同一列的下一个非 0 元)。其次，十字交叉链表还有一个头结点，结点的结构如图所示。
由定义知，稀疏矩阵中同一行的非 0 元素的由 right 指针域链接成一个行链表，由 down指针域链接成一个列链表。则每个非 0 元素既是某个行链表中的一个结点，同时又是某个列链表中的一个结点，所有的非 0 元素构成一个十字交叉的链表。称为十字链表。
此外，还可用两个一维数组分别存储行链表的头指针和列链表的头指针。
广义表是线性表的推广和扩充，在人工智能领域中应用十分广泛。
把线性表定义为 n(n≧0 )个元素 a1, a2 ,..., an 的有穷序列，该序列中的所有元素具有相 同的数据类型且只能是原子项(Atom)。所谓原子项可以是一个数或一个结构，是指结构上不 可再分的。若放松对元素的这种限制，容许它们具有其自身结构，就产生了广义表的概念。
广义表(Lists，又称为列表 ):是由 n(n ≧0)个元素组成的有穷序列: LS= 其中 或者是原子项，或者是一个广义表。LS是广义表的名字，n 为它的长度。若 是广义表，则称为 LS 的子表。习惯上:原子用小写字母，子表用大写字母。
若广义表 LS 非空时:
(表中第一个元素)称为表头; 其余元素组成的子表称为表尾; 。 广义表中所包含的元素(包括原子和子表)的个数称为表的长度。
广义表中括号的最大层数称为表深 (度)。
两个基本操作 GetHead() GetTail()。
广义表的重要结论:
(1) 广义表的元素可以是原子，也可以是子表，子表的元素又可以是子表， ...。即广义 表是一个多层次的结构。
(2) 广义表可以被其它广义表所共享，也可以共享其它广义表。广义表共享其它广义表 时通过表名引用。
(3) 广义表本身可以是一个递归表。
(4) 根据对表头、表尾的定义，任何一个非空广义表的表头可以是原子，也可以是子表， 而表尾必定是广义表。
5. 数据结构 稀疏矩阵一般的压缩存储方法有哪几种
来自 严蔚敏《数据结构》
稀疏矩阵的压缩方法主要有：
1：三元组顺序表 （行下标，列下标，值）
2：行逻辑链接的顺序表。
3：十字链表。
6. 矩阵的压缩存储是什么
二维数组在形式上是矩阵，因此一般用二维数组来存储矩阵。在不压缩存储的情况下，矩阵采用按行优先或按列优先方式存储，占用的存储单元数等于矩阵的元素个数。在实际应用中，经常出现一些阶数很高的矩阵，同时在矩阵中非零元素呈某种规律分布或者矩阵中有大量的零元素，若仍然用常规方法存储，可能存储重复的非零元素或零元素，这将造成存储空间的大量浪费。因此对这类矩阵进行压缩存储，从而合理地利用存储空间。
为了节省存储空间，可以利用特殊矩阵的规律，对它们进行压缩存储，也就是说为多个值相同的元素只分配一个存储单元，对零元素不分配空间。适合压缩存储的矩阵一般是值相同的元素或者零元素在矩阵中分布有一定规律的特殊矩阵和稀疏矩阵。常见的特殊矩阵有对称矩阵、三角矩阵和对角矩阵。
7. 请问一下数据结构中对称矩阵的压缩存储的一 一对应关系怎么算的呀。
先看上面一个：
下三角有i>=j
第1行一个，第2行两个，。。。，第i-1行i-1个（i, j下标都是从1开始的）
所以第i行前有1+2+...+(i-1)= i(i-1)/2个元素
再看本行，本元素前有j-1个元素
因为计算的是元素之间的位置差，因此就是i(i-1)/2+(j-1)了
下面一个上三角i<j：
对于对称矩阵有a(i,j)=a(j,i)，即行列互换，代入上式即可得
8. 多维数组-矩阵的压缩存储- 稀疏矩阵（一）
稀疏矩阵
设矩阵A mn 中有s个非零元素 若s远远小于矩阵元素的总数(即s< <m×n)，则称a为稀疏矩阵。 p=""> </m×n)，则称a为稀疏矩阵。>
1、稀疏矩阵的压缩存储
为了节省存储单元，可只存储非零元素。由于非零元素的分布一般是没有规律的，因此在存储非零元素的同时，还必须存储非零
元素所在的行号、列号，才能迅速确定一个非零元素是矩阵中的哪一个元素。稀疏矩阵的压缩存储会失去随机存取功能。
其中每一个非零元素所在的行号、列号和值组成一个三元组(i，j，a ij )，并由此三元组惟一确定。
稀疏矩阵进行压缩存储通常有两类方法：顺序存储和链式存储。链式存储方法【参见参考书目】。
2、三元组表
将表示稀疏矩阵的非零元素的三元组按行优先(或列优先)的顺序排列(跳过零元素)，并依次存放在向量中，这种稀疏矩阵的顺序
存储结构称为三元组表。
注意：
以下的讨论中，均假定三元组是按行优先顺序排列的。
【例】下图(a)所示的稀疏矩阵A的三元组表表示见图(b)
(1)三元组表的类型说明
为了运算方便，将矩阵的总行数、总列数及非零元素的总数均作为三元组表的属性进行描述。.WINGwIT.其类型描述为：
#define MaxSize 10000 //由用户定义
typedef int DataType; //由用户定义
typedef struct { //三元组
int i，j;//非零元的行、列号
DataType v; //非零元的值
}TriTupleNode;
typedef struct{ //三元组表
TriTupleNode data[MaxSize]; //三元组表空间
int m,n，t; //矩阵的行数、列数及非零元个数
}TriTupleTable;
(2) 压缩存储结构上矩阵的转置运算
一个m×n的矩阵A，它的转置矩阵B是一个n×m的矩阵，且：
A[i][j]=B[j][i]，0≤i <m，0≤j<n， p=""> </m，0≤j<n，>
即A的行是B的列，A的列是B的行。
【例】下图中的B和上图中的A互为转置矩阵。
①三元组表表示的矩阵转置的思想方法
第一步：根据A矩阵的行数、列数和非零元总数确定B矩阵的列数、行数和非零元总数。
第二步：当三元组表非空(A矩阵的非零元不为0)时，根据A矩阵三元组表的结点空间data(以下简称为三元组表)，将A的三
元组表a->data置换为B的三元组表b->data。
②三元组表的转置
方法一:简单地交换a->data中i和j中的内容，得到按列优先顺序存储倒b->data;再将b->data重排成按行优先顺序的三元组表。
方法二:由于A的列是B的行，因此，按a->data的列序转置，所得到的转置矩阵B的三元组表b->data必定是按行优先存放的。
按这种方法设计的算法，其基本思想是：对A中的每一列col(0≤col≤a->n-1)，通过从头至尾扫描三元组表a->data，找出所有
列号等于col的那些三元组，将它们的行号和列号互换后依次放人b->data中，即可得到B的按行优先的压缩存贮表示。具体实现参见
【 动画演示 】
③具体算法：
void TransMatrix(TriTupleTable *b，TriTupleTable *a)
{//*a，*b是矩阵A、B的三元组表表示，求A转置为B
int p，q，col;
b->m=a->n; b->n=a->m; //A和B的行列总数互换
b->t=a->t; //非零元总数
if(b->t<=0)
Error("A=0"); //A中无非零元，退出
q=0;
for(col=0;coln;col++) //对A的每一列
for(p=0;pt;p++) //扫描A的三元组表
if(a->data[p].j==col){ //找列号为col的三元组
b->data[q).i=a->data[p].j;
b->data[q].j=a->data[p].i;
b->data[q].v=a->data[p].v;
q++;
}
} //TransMatrix
④算法分析
该算法的时间主要耗费在col和p的二重循环上：
若A的列数为n，非零元素个数t，则执行时间为O(n×t)，即与A的列数和非零元素个数的乘积成正比。
通常用二维数组表示矩阵时，其转置算法的执行时间是O(m×n)，它正比于行数和列数的乘积。
由于非零元素个数一般远远大于行数，因此上述稀疏矩阵转置算法的时间大于通常的转置算法的时间。
lishixin/Article/program/sjjg/201311/23897
9. 数据结构对称矩阵的压缩存储求数据地址
对对称阵进行压缩存取是将对称元素只存一个，并将数据存储在一维数组中
首先来确定a[i][j]在b[k]中的i，j与k的关系
首先是判定i与j的关系，
如果是下三角存储，则分一下两种情况
1、如果i<j,
则交换i与j的值，将上三角的位衫梁清置值变换到下三角位置渣颤
2、如果i>=j，则不用执行操作直接走下面的流程
此时，i表示行坐标，j表示了坐标i之前有i行，即有1+2+...+i
=
(i+1)*i/2，在i标识的第i+1行有j+1个元素，由或前此可以确定k的值为(i+1)*i/2+j+1
=
k+1
由此可得k
=
(i+1)*i/2+j
由此可以的，a[3][6],
i=3,
j=6,
由于i<j,
交换得i=6，
j=3
由此
k
=
(6+1)*6/2+3
=
24
又由于&b[0]
=
1000
每个元素占两个字节,
则b[24]
=
1000+2*24
=
1048
由此便得到a[3][6]的地址为1048
10. 在《数据结构》中，特殊矩阵和稀疏矩阵哪一种压缩存储会失去随机存取的功能，为什么
稀疏矩阵压缩存储后，必会失去随机存取功能。
稀疏矩阵在采用压缩存储后将会失去随机存储的功贺腔侍能。因为在这种矩阵中，非零元素的分布是没有规律的，为了压缩存储，就将每一个非零元素的值和它所在的行、列号做为一个结点存放在圆迅一起，这样禅吵的结点组成的线性表中叫三元组表，它已不是简单的向量，所以无法用下标直接存取矩阵中的元素。