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. 在《數據結構》中，特殊矩陣和稀疏矩陣哪一種壓縮存儲會失去隨機存取的功能，為什麼
稀疏矩陣壓縮存儲後，必會失去隨機存取功能。
稀疏矩陣在採用壓縮存儲後將會失去隨機存儲的功賀腔侍能。因為在這種矩陣中，非零元素的分布是沒有規律的，為了壓縮存儲，就將每一個非零元素的值和它所在的行、列號做為一個結點存放在圓迅一起，這樣禪吵的結點組成的線性表中叫三元組表，它已不是簡單的向量，所以無法用下標直接存取矩陣中的元素。