上三角矩阵的存储

1. 上三角矩阵按行优先存储公式

题目出错了，上三角肯定是 i<=j
公式也不对，怎么可能跟n无关呢，第i行的元素个数是n-i+1，
a(i,j)前面有i-1行，这i-1行共有(n-1+1)+...+(n-(i-1)+1)个元素，第i行有j-i+1，加在一起再减1就是k(因为数组下标为0)

2. 上三角矩阵及存储的算法

K=(i-1)*(2n-i)/2+j (i<=j) 或者K=n*(n+1)/2+1

3. 简述一下如何将一个上三角矩阵以列为主序压缩存储在一个一维数组

给一维数组分配矩阵数据总数+2的长度。

数组第一个和第二个存储矩阵的行数和列数
然后你将矩阵每列顺序的存储到该数组中

应该可以

列数判断何时数组结束
行数判断每列的界限

4. 思考上三角矩阵用数组sa【n（n+1）/2+1】压缩存储时的下标对应。

：假定对称矩阵按行序为主序，顺序存储下三角元素到一维数组SA[1..n(n-1)/2]中，对下三角中任一元素aij在一维数组SA中的下标k值为 i(i-1)/2+j-1i(i-1)/2+j i(i+1)/2+j-1 i(i+1)/2+j

5. 特殊矩阵的压缩存储：上三角、对称、下三角存储，有三个问题。求大侠们解答~亲一个~这个图能看清吗

1.k=n*(n+1)/2的原因是：对于三角矩阵，从1到N的总和是这么多，也就是说整个矩阵有这么多元素。另外正三角阵对应正方形。
对称矩阵满足A的转置也就是自身的特点，元素上，a[i,j] = a[j,i]。实际上的存储可以利用三角阵。所以老实说我对于他对称阵算法为什么少一个元素也有疑惑。
可能是三角阵可以对应不等长的矩阵，所以造成了k值不一样。
2.上三角阵，存在的元素是满足[1<= j <=n, i >= j]的关系[这里用i表横坐标j表纵坐标]，如果是长3宽4的当然不能和长4宽3的相提并论，试着画画就明白了。
3.对称阵不会出现像三角阵那样有一小角还是其他数字的情况。这个其他数字就是(6+1)-1=6。
4.压缩存储，只是将部分符合条件的矩阵减少一部分的存储空间。老实说我也感觉不很有用，除非他处理的数据本身必然具备此类特点。
5.固定的，多试几次自己记下来然后找找就好。如果没记错的话，在矩阵上画画就可以看出来。
6.stdlib.h是标准的输入输出库，最为常用，至少里面包括了scanf等函数，只要你需要printf你就不能扔掉它。否则会出现函数未定义的问题。毕竟语言本身不提供函数类库，类库需要另行引用。

6. 数据结构,求三角矩阵的存储位置

aij i和j只是起始位置代号，并不是行号，只要是顺序的对称的即可。
题目完全可以说a99是第一个元素，那么a[18]a[18]就是矩阵右下角即最后一个元素，
如果这样代表i=9就是第一行，i=10是第二行 。

7. 数据结构-特殊矩阵的压缩存储

本文介绍对称矩阵、三角矩阵、对角矩阵和稀疏矩阵的压缩存储方法。

在一个n阶矩阵A中，若元素满足aij=aji,0<=i,j<=n-1，则称矩阵A为对称矩阵。

按行优先顺序将这些元素存放在一个一维数组s[n(n+1)/2]中，元素aij在s中对应的下标为k：

以主对角线划分，三角矩阵分为上三角和下三角两种，上三角矩阵的下三角所有元素均为常数c，下三角矩阵正好相反。

按行优先顺序将三角矩阵存放在一维数组s[n(n+1)/2+1]，其中常数c存放在数组的最后一个分量中。

上三角矩阵元素aij在s中对应的下标为k：

下三角矩阵元素aij在s中对应的下标为k：

对角矩阵是指矩阵中所有的非零元素集中在以主对角线为中心的带状区域中。一个k对角矩阵（k为奇数）A满足若|i-j|>(k-1)/2则元素aij=0。

将三对角矩阵A中的非零元素按行优先顺序存放到数组s[3n-2]中，在三对角矩阵A中，除第一行和最后一行只有两个非零元素外，其他每行中均有三个非零元素。三对角矩阵中的元素aij在s中对应的下标为 k=3×i-1+j-(i-1)=2×i+j .

设矩阵Amn中有s个非零元素，若s远远小于矩阵元素的总数，即s<<mxn，则称A为稀疏矩阵。

对于稀疏矩阵的压缩存储方法通常有两种，分别是三元组顺序表和十字链表。

1. 三元组顺序表

每个元素是一个结构体，包括该元素在矩阵中的行数、列数和数值，所有元素存在一个向量vector中，并同时记录矩阵的行数、列数及非零元素个数等信息。

2. 十字链表

为了克服顺序表中对非零元素插入和删除操作带来的不便，采用链接存储结构存储稀疏矩阵。

十字链表将每个元素存储为一个结构体，除了包括元素的行号、列号、数值外，还包括一个向右指针域用于指向同一行中的下一个非零元素和一个向下指针域用于指向同一列中的下一个非零元素。所有结构体通过两个一维指针数组分别存储各个行链表的头指针和各个列链表的头指针组织成一个整体。

目标是将每个元素的行号列号交换，并按照新的行列号按序存放。关键在于如何高效地进行按序存放。

方法一：朴素转置算法

按照原列号分别从头至尾扫描，依次放入新的矩阵中。对于一个m行n列且非零元素个数为t的稀疏矩阵而言，该算法的时间复杂度为O(t×n)。

方法二：快速转置算法

采用一个数组cnum[cols]记录每一列中的元素个数，一个数组cpot[cols]记录每一列的第一个非零元素在转置矩阵顺序表中的下标。cnum和cpot各采用一次遍历得到，其中cpot[0]=0，cpot[col]=cpot[col-1]+cnum[col-1]。