矩陣
一洞慎、對稱矩陣
- 定義：矩陣元素
aij = aji; -
一維數(shù)組存儲
對稱矩陣存儲方式
如圖所示，由于對稱矩陣的對稱性嘿棘，我們使用二維數(shù)組存儲劲腿，會使得二維數(shù)組重復(fù)存儲一部分?jǐn)?shù)據(jù)，我們可以使用邏輯處理來節(jié)省這部分重復(fù)數(shù)據(jù)鸟妙。
- 處理方式
我們按照行存儲來存儲三角區(qū)域元素, 包含了對角線焦人，下三角區(qū)域。 - 解決兩個問題
1.存儲的數(shù)據(jù)多大?
第一行有:1
第二行有:2
第三行有:3
第n行有:n
總共有:1+2+3+4....+n = (1+n)n/2個元素.
2.元素aij對應(yīng)一維數(shù)組存儲的index是多少重父？
i:行花椭，j:列，按行存儲 =>index =( 1+i-1)(i-1)/2 + j-1 = i(i-1)/2 + j - 1房午，注意元素從a11開始的矿辽。
3.上三角怎么邏輯處理？
由于aij = aji=>index上三角 = j(j-1)/2 + i -1
4.總結(jié)
index下三角=( 1+i-1)(i-1)/2 + j-1 = i(i-1)/2 + j - 1
index上三角= j(j-1)/2 + i -1
二郭厌、上下三角矩陣
-
下三角矩陣定義： 除了主對角線和下三角區(qū)袋倔，其余元素都相同
下三角矩陣，c為常數(shù) 解決問題
1.如何存儲常數(shù)項,因?yàn)閿?shù)組從零開始所以存儲下三角折柠，最后一個元素宾娜，索引為(1+n)*n/2 -1，故常數(shù)項存儲位置為(1+n)*n/2扇售。
2.如何存儲下三角前塔？
按行存儲，和對稱矩陣下三角是一樣的
index下三角=( 1+i-1)(i-1)/2 + j-1 = i(i-1)/2 + j - 1-
上三角矩陣定義：除了主對角線和上三角區(qū)承冰，其余元素都相同华弓。
上三角矩陣 解決問題
1.如何存儲？
第一行：有n個
第二行：有n-1個
第n行：有1個
總計：(1+n)n/2個困乒，故常數(shù)部分存儲index為(1+n)n/2
第aij元素存儲位置：
index上三角 = (n-(i-1) + 1 + n) * (i-1)/2 + j-i = (2n-i+2)(i-1)/2 + j -i
三寂屏、三對角矩陣
-
定義：|i-j| > 1 時，有aij = 0 （i>=1,j<=n）
對三角矩陣 - 如何存儲
1.只需要存儲帶區(qū)域中的元素顶燕，
總共有：3*n-2個元素凑保，一共n行，首行末行均為2個涌攻。
2.第aij元素對應(yīng)的index為欧引？
index =3*(i-1)-1 + j-i+2 -1 = 2i+j-3
3.知道數(shù)組中索引為k的元素如何推出時aij中的i和j?
索引為k，對應(yīng)的是k+1個元素
第i-1行有3*(i-1)-1個元素
第i行有3i-1個元素
3(i-1) < k+1<=3i-1 => i = k+2/3向上取整.
因?yàn)?code>k = 2i+j-3聯(lián)立可得j = k-2i +3
四恳谎、稀疏矩陣
-
定義： 非零元素遠(yuǎn)遠(yuǎn)小于矩陣元素的個數(shù).
稀疏矩陣 - 存儲方式
1.三元組<行芝此，列憋肖，值> 不支持隨機(jī)存儲
2.十字鏈表 支持隨機(jī)存儲.
