數(shù)組與廣義表專題

• 數(shù)組的順序表示和實現(xiàn)
• • 前言
  • 數(shù)組中任意一個元素存儲地址的計算
  • • 一維數(shù)組
    • 二維數(shù)組
    • 更一般的二維數(shù)組
• 矩陣的壓縮存儲
• • 前言
  • 對稱矩陣
  • 三角矩陣
  • • 前言
    • 上三角對應(yīng)關(guān)系
    • 下三角關(guān)系
  • 三對角矩陣
  • • 下標(biāo)對應(yīng)關(guān)系
• 稀疏矩陣
• • 前言
  • 稀疏矩陣的三元組表示
  • 用三元組表示矩陣的轉(zhuǎn)置
  • 優(yōu)化快速轉(zhuǎn)置

數(shù)組的順序表示和實現(xiàn)

前言

在計算機中，內(nèi)存儲器的結(jié)構(gòu)是一維的 。用一維的內(nèi)存來表示多維數(shù)組，就必須按照某種次序?qū)?shù)組元素排成一個線性序列。

數(shù)組中任意一個元素存儲地址的計算

一維數(shù)組

$$Loc(a_i)=Loc(a_0)+i?L(0<=i<n)$$
其中 L為數(shù)組中每個元素需要占用L個存儲單元。

二維數(shù)組

$a_{ij}$位于第i+1行，第j+1列，前面i行一共有$n?i$個元素，在該列前面又有$j$個元素。所以二維數(shù)組$A_{m?n}$中任一元素$a_{ij}$的存儲位置如下
$$LOC(a_{ij})=LOC(a_{00})+(i?n+j)?L$$

更一般的二維數(shù)組

上面假設(shè)的是二維數(shù)組的行、列下界是從0開始的。在更一般的情況下，二維數(shù)組的行下界為$r_1$,行下界為$r_2$,列下界為$c_1$,行下界為$c_2$。即二維數(shù)組$A[r_1..r_2][c_1...c_2]$的存儲地址如下表示
$$LOC(a_{ij})=LOC(a_{r_1{c}_1})+[(i?r_1)?(c_2?c_1+1)+(j?c_1)]?L$$

矩陣的壓縮存儲

前言

二維數(shù)組在形式上是矩陣，因此一般用二維數(shù)組來存儲矩陣。在不壓縮存儲的情況下，矩陣采用按行優(yōu)先或按列優(yōu)先方式存儲，占用的存儲單元數(shù)等于矩陣的元素個數(shù)。在實際應(yīng)用中，經(jīng)常出現(xiàn)一些階數(shù)很高的矩陣，同時在矩陣中非零元素呈某種規(guī)律分布或者矩陣中有大量的零元素，若仍然用常規(guī)方法存儲，可能存儲重復(fù)的非零元素或零元素，這將造成存儲空間的大量浪費。因此對這類矩陣進(jìn)行壓縮存儲，從而合理地利用存儲空間。

為了節(jié)省存儲空間，可以利用特殊矩陣的規(guī)律，對它們進(jìn)行壓縮存儲，也就是說為多個值相同的元素只分配一個存儲單元，對零元素不分配空間。適合壓縮存儲的矩陣一般是值相同的元素或者零元素在矩陣中分布有一定規(guī)律的特殊矩陣和稀疏矩陣。常見的特殊矩陣有對稱矩陣、三角矩陣和對角矩陣。

下面的是針對下標(biāo)從0開始的二維數(shù)組

對稱矩陣

因為對稱矩陣以對角線對稱的元素的值相同，一般可以用一個數(shù)組來存儲矩陣的上三角或者下三角的元素即可。

• 行下標(biāo)大于等于列下標(biāo)稱為下三角。列下標(biāo)大于等于行下標(biāo)稱為上三角。
• 在壓縮之后元素個數(shù)有$n^2$減少到$n?(n+1)/2$
• 設(shè)k為存儲下三角元素的一維數(shù)組的下標(biāo)。其k與二維數(shù)組下標(biāo)中的i、j的關(guān)系如下：
  $$k=i?(i+1)/2+j$$
  如果是上三角則是：
  $$k=j?(j+1)/2+i$$

三角矩陣

前言

以主對角線劃分，三角矩陣有上三角和下三角兩種。把主對角線以下(不包括主對角線)的元素均為常數(shù)c的n階矩陣，稱為上三角矩陣；把主對角線以上(不包括主對角線)的元素均為常數(shù)c的n階矩陣，稱為下三角矩陣。上三角矩陣和下三角矩陣統(tǒng)稱為三角矩陣。三角矩陣中的常數(shù)c在多數(shù)情況下為0。這個c表示的是除了上三角或下三角以外的其余元素，因為都是一樣的所有可以用一個單元位置來存儲即可。

上三角對應(yīng)關(guān)系

$$x=\{\begin{array}{ll}i?(2n?i+1)/2+j?i& i<=j\\ n?(n+1)/2& i>j\end{array}$$

序號 = 所有在它前面元素的個數(shù) = 它所在行前面行的所有元素+它所在行它前面的元素

由于每行元素個數(shù)逐級遞減，構(gòu)成一個等差數(shù)列，公差：d = 1,首項：a1 = n ,末項：an = n+(i-1)*-1 = n-i +1

前i行元素個數(shù)為： $a_n=a_1+(n?1)d$ ,在這里 n = i ,d =-1 。所以有
$a_n=n?(i?1)=n?i+1$ ,有求和公式$n?(a_1+a_n)/2$,所有
$$\begin{gathered} s_n=i?(n+n?i+1)/2 \\ =i?(2n?i+1)/2 \end{gathered}$$

第i行中在它前面的元素個數(shù)為：j-i （元素逐行減少，可以看成從行首拿掉一個元素，所以第i+1行已經(jīng)被拿走了i個元素，第i+1行的第j+1列元素前面就只有j-i = j-i個元素了）

公式：$K=i?(2n?i+1)/2+j?i$

考慮重復(fù)部分元素和下三角一樣：$k=n(n+1)/2$

下三角關(guān)系

$$x=\{\begin{array}{ll}i?(i+1)/2+j& i>=j\\ n?(n+1)/2& i<j\end{array}$$

三對角矩陣

三對角矩陣按行序為主序存儲時，將壓縮到一個數(shù)組中，第0行和第n-1行是2個非零元素，其余每行的非零元素都是3個，則需存儲的元素個數(shù)為3n-2.

下標(biāo)對應(yīng)關(guān)系

$|i?j|>1$：元素$a_{ij}$位于三對角線以外，是零元素不用存儲。

$|i?j|<=1$：元素$a_{ij}$位于三對角線上，則 $k=2i+j$

稀疏矩陣

前言

稀疏矩陣的定義：假設(shè)m行n列的矩陣含t個非零元素，則稱
$$\delta =\frac{t}{n?m},當(dāng)\delta <=0.05時稱為稀疏矩陣。$$

稀疏矩陣的三元組表示

#define MAXSIZE 12500 typedef struct {int i, j; //非零元素所在的行下標(biāo)與列下標(biāo)int val; //非零元素的值 }Triple;typedef struct {Triple data[MAXSIZE]; //非零元素的三元組表data[0]未用int row, col; //矩陣的行數(shù)與列數(shù)int num; //非零元素個數(shù) }TSMatrix;

用三元組表示矩陣的轉(zhuǎn)置

設(shè)稀疏矩陣A是按行優(yōu)先順序壓縮存儲在三元組表A. data中，若僅僅是簡單地交換A daia中i和j的內(nèi)容，得到的三元組表B. data將是一個按列優(yōu)先順序存儲的稀疏矩陣B。要得到按行優(yōu)先順序存儲的B. data，就必須重新排列三元組B. data中元素的順序。其轉(zhuǎn)置矩陣的算法思想是在A的三元組順序表中依次找第1列、第2列、……，直到最后一列的三元組，并將找到的每個三元組的行、列交換后順序存儲到B的三元組順序表中。這樣，每找到矩陣A的一個三元組，需從頭至尾掃描整個三元組A. data。

TSMatrix TransMatrix(TSMatrix A) {TSMatrix B;B.row = A.col; B.col = A.row;B.num = A.num;if (B.num) { //存在非零元素則交換int q = 1;for(int j=1;j<=A.col;++j)//依次考察每一列元素for (int i = 1; i <= A.num; ++i) { //在A中掃描整個數(shù)組if (A.data[i].j == j) { //處理j列元素B.data[q].i = A.data[i].j;B.data[q].j = A.data[i].i;B.data[q++].val = A.data[i].val;}}}return B; }

優(yōu)化快速轉(zhuǎn)置

先遍歷兩遍數(shù)組，第一次統(tǒng)計A中每一列的元素個數(shù)，并有計算公式求出每一列的第一個非零元素在B數(shù)組中的位置，第二次掃描的時候直接交換即可。

計算公式
$$\{\begin{array}{l}cpot[1]=1\\ cpot[col]=cpot[col?1]+num[col?1]\end{array}$$

cpot[col]表示A中第col列的第一個非零元素在B中的位置

代碼；

TSMatrix TransMatrix(TSMatrix A) {TSMatrix B;B.row = A.col; B.col = A.row;B.num = A.num;if (B.num) { //存在非零元素則交換int number[MAXSIZE] = {};int cpot[MAXSIZE] = {};for (int i = 1; i <= A.num; ++i)number[A.data[i].j]++; //計算A中每一列非零元素個數(shù)for (int i = 2; i <= A.num; ++i) cpot[i] = cpot[i - 1] + number[i - 1];for (int i = 1; i <= A.num; ++i) {int col = A.data[i].j;int pos = cpot[col]; //第一個的位置B.data[pos].i = A.data[i].j;B.data[pos].j = A.data[i].i;B.data[pos].val = A.data[i].val;++cpot[col]; //后移}}return B; }

總結(jié)

以上是生活随笔為你收集整理的数据结构----数组与广义表专题的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。