上三角矩陣的存儲

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]。