寫在前面
偷懶，先寫了數(shù)組，隊(duì)列要畫圖，所以今天就先不寫了
數(shù)組的定義
數(shù)組是由n個(gè)相同類型的數(shù)據(jù)元素構(gòu)成的有限序列。每個(gè)數(shù)據(jù)元素被稱為一個(gè)數(shù)組元素，每個(gè)元素在n個(gè)線性關(guān)系中的序號(hào)稱為該元素的下標(biāo)，下標(biāo)的取值范圍稱為數(shù)組的維界。
數(shù)組與線性表的關(guān)系：數(shù)組是線性表的推廣。一維數(shù)組可視為一個(gè)線性表，二維數(shù)組可視為其元素是定長(zhǎng)數(shù)組的線性表。因此，除結(jié)構(gòu)的初始化和銷毀外，數(shù)組只會(huì)有存取元素和修改元素的操作。
數(shù)組的順序存儲(chǔ)
一維數(shù)組
以\(A[0 \dots n-1]\)為例，其存儲(chǔ)結(jié)構(gòu)關(guān)系式為：
其中，\(L\)是每個(gè)數(shù)組元素所占的存儲(chǔ)單元。
多維數(shù)組
以二維數(shù)組為例。設(shè)二維數(shù)組的行下標(biāo)與列下標(biāo)的范圍分別為\([0, h_1]\)和\([0,h_2]\)。
按行優(yōu)先
先行后列，先存儲(chǔ)行號(hào)較小的元素，行號(hào)相等先存儲(chǔ)列號(hào)較小的元素。存儲(chǔ)結(jié)構(gòu)關(guān)系式為：
例如對(duì)于數(shù)組\(A_{[2][3]}\)。它按行優(yōu)先方式在內(nèi)存中的存儲(chǔ)形式如下所示：
| \(a_{[0][0]}\) | \(a_{[0][1]}\) | \(a_{[0][2]}\) | \(a_{[1][0]}\) | \(a_{[1][1]}\) | \(a_{[1][2]}\) |
|---|
列優(yōu)先
存儲(chǔ)結(jié)構(gòu)關(guān)系式為：
例如對(duì)于數(shù)組\(A_{[2][3]}\)。它按行優(yōu)先方式在內(nèi)存中的存儲(chǔ)形式如下所示：
| \(a_{[0][0]}\) | \(a_{[1][0]}\) | \(a_{[0][1]}\) | \(a_{[1][1]}\) | \(a_{[0][2]}\) | \(a_{[1][2]}\) |
|---|
特殊矩陣的壓縮存儲(chǔ)
壓縮存儲(chǔ)：指為多個(gè)值相同的元素只分配一個(gè)存儲(chǔ)空間，對(duì)零元素不分配空間；
特殊矩陣：指具有許多相同矩陣元素或零元素，并且這些相同矩陣元素或零元素的分布具有一定規(guī)律性的矩陣；
特殊矩陣的壓縮存儲(chǔ)：找出特殊矩陣中值相同的矩陣元素的分布規(guī)律，把那些呈現(xiàn)規(guī)律性分布的、值相同的多個(gè)矩陣元素壓縮存儲(chǔ)到一個(gè)存儲(chǔ)空間中。
對(duì)稱矩陣
對(duì)一個(gè)n階矩陣\(A\)中的任意一個(gè)元素\(a_{i,j}\)都有\(a_{i, j} = a_{j, i}(1 \leq i, j \leq n)\)，則稱其為對(duì)稱矩陣
很顯然，對(duì)于n階對(duì)稱矩陣，上三角區(qū)所有元素和下三角區(qū)的對(duì)應(yīng)元素相同，采用二維數(shù)組存放，會(huì)造成大范圍的空間浪費(fèi)，因此我們把其存放在一維數(shù)組\(B[\frac{n(n+1)}{2}]\)中。
比如只存放下三角部分的元素：
在數(shù)組\(B\)中，位于元素\(a_{i, j}\)前的元素個(gè)數(shù)為：
第1行：1個(gè)（\(a_{1,1}\)）
第2行：2個(gè)（\(a_{2,1},a_{2,2}\)）
\(\dots\)
第\(i-1\)行：\(i-1\)個(gè)（\(a_{i-1,1},a_{i-1,2} \dots ,a_{i-1,i-1}\)）
第\(i\)行：\(j-1\)個(gè)（\(a_{i,1},a_{i,2}, \dots , a_{i,j-1}\)）
因此，元素\(a_{i,j}\)在數(shù)組\(B\)中的下標(biāo)\(k = 1 + 2 + \dots + (i - 1) + j - 1 = \frac{i(i - 1)}{2} + j - 1\)
因此，元素下標(biāo)之間對(duì)應(yīng)關(guān)系如下：
三角矩陣
下三角矩陣
上三角區(qū)為統(tǒng)一常量。元素下標(biāo)之間的對(duì)應(yīng)關(guān)系為：
| 下標(biāo) | 0 | 1 | 2 | 3 | 4 | 5 | \(\cdots\) | \(\frac{n(n+1)}{2}\) | ||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 元素 | \(a_{1,1}\) | \(a_{2,1}\) | \(a_{2,2}\) | \(a_{3,1}\) | \(a_{3,2}\) | \(a_{3,3}\) | \(\cdots\) | \(a_{n,1}\) | \(a_{n,2}\) | \(\cdots\) | \(a_{n,n}\) | \(c\) |
| 行號(hào) | 第一行 | 第二行 | 第二行 | 第三行 | 第三行 | 第三行 | \(\cdots\) | 第n行 | 第n行 | \(\cdots\) | 第n行 | 常數(shù)項(xiàng) |
上三角矩陣
與上文類似地，位于元素\(a_{i,j}(i \leq j)\)前面的元素個(gè)數(shù)為：
第1行：\(n\)個(gè)
第2行：\(n-1\)個(gè)
\(\dots\)
第\(i-1\)行：\(n - i + 2\)個(gè)
第\(i\)行：\(j-1\)個(gè)
因此，元素\(a_{i,j}\)在數(shù)組\(B\)中的下標(biāo)\(k = n + (n - 1) + \dots + (n - i + 2) + (j - i + 1) - 1\)
因此，元素下標(biāo)之間對(duì)應(yīng)關(guān)系如下：
| 下標(biāo) | 0 | 1 | \(\cdots\) | \(\frac{n(n+1)}{2}\) | |||||||
|---|---|---|---|---|---|---|---|---|---|---|---|
| 元素 | \(a_{1,1}\) | \(a_{1,2}\) | \(\cdots\) | \(a_{1,n}\) | \(a_{2,2}\) | \(a_{2,3}\) | \(\cdots\) | \(a_{2,n}\) | \(\cdots\) | \(a_{n,n}\) | \(c\) |
| 行號(hào) | 第一行 | 第一行 | 第一行 | 第一行 | 第二行 | 第二行 | 第二行 | 第二行 | \(\cdots\) | 第n行 | 常數(shù) |
三對(duì)角矩陣
對(duì)n階矩陣\(A\)中的任意元素\(a_{i,j}\)，都有當(dāng)\(|i-j| >1\)時(shí)，\(a_{i,j} = 0\)。
稀疏矩陣
矩陣中非零元素的個(gè)數(shù)t，相對(duì)于矩陣元素的個(gè)數(shù)s來說非常少，即\(s >> t\)的矩陣稱為稀疏矩陣
我們可以用對(duì)應(yīng)的三元組線性表來存儲(chǔ)稀疏矩陣，如下例：
對(duì)應(yīng)的三元組為：文章來源：http://www.zghlxwxcb.cn/news/detail-825340.html
下面，上代碼，可以實(shí)現(xiàn)稀疏矩陣的輸入、輸出，稀疏矩陣對(duì)應(yīng)三元組的加法、乘法、轉(zhuǎn)置：文章來源地址http://www.zghlxwxcb.cn/news/detail-825340.html
#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 10000
typedef int ElemType;
typedef struct {
int i, j;
ElemType e;
}Triple;
typedef struct {
Triple data[MAXSIZE + 1];
int mu, nu, tu; //矩陣行數(shù)，列數(shù)和非0元個(gè)數(shù)
}TSMatrix;
//輸入稀疏矩陣數(shù)據(jù)
void InPutM(TSMatrix& M) {
printf("輸入稀疏矩陣的 行數(shù), 列數(shù), 非0元個(gè)數(shù) :\n");
scanf_s("%d %d %d", &M.nu, &M.mu, &M.tu);
printf("輸入矩陣非0元素的 所在行i, 所在列j, 值e:\n");
for (int k = 1; k <= M.tu; k++) {
scanf_s("%d %d %d", &M.data[k].i, &M.data[k].j, &M.data[k].e);
}
}
//打印稀疏矩陣三元組數(shù)據(jù)
void PrintM(TSMatrix T) {
printf(" %d %d %d\n", T.mu, T.nu, T.tu);
printf(" ------------\n");
for (int k = 1; k <= T.tu; k++) {
printf(" %d %d %d\n", T.data[k].i, T.data[k].j, T.data[k].e);
}
}
//稀疏矩陣三元組加法
void AddSMatrix(TSMatrix a, TSMatrix b, TSMatrix& c) {
int i = 0, j = 0, k = 0;
ElemType v; //用于計(jì)算和
if (a.mu != b.mu || a.nu != b.nu) //兩矩陣無法相加
return;
c.mu = a.mu;
c.nu = a.nu;
while (i < a.tu || j < b.tu)
{
//若行相等，看列
if (a.data[i + 1].i == b.data[j + 1].i)
{
//行相同時(shí)的第一種情況
if (a.data[i + 1].j < b.data[j + 1].j)
{
c.data[k + 1].i = a.data[i + 1].i;
c.data[k + 1].j = a.data[i + 1].j;
c.data[k + 1].e = a.data[i + 1].e;
k++;
i++; //前往下一個(gè)a中的非0元
}
//行相同時(shí)的第二種情況
else if (a.data[i + 1].j > b.data[j + 1].j)
{
c.data[k + 1].i = b.data[j + 1].i;
c.data[k + 1].j = b.data[j + 1].j;
c.data[k + 1].e = b.data[j + 1].e;
k++;
j++; //前往下一個(gè)b中的非0元
}
//行相同的第三種情況
else
{
v = a.data[i + 1].e + b.data[j + 1].e;
if (v != 0)
{
c.data[k + 1].i = a.data[i + 1].i;
c.data[k + 1].j = a.data[i + 1].j;
c.data[k + 1].e = v;
k++;
}
i++;
j++;
}
}
//若行不相同 的兩種情況
else if (i == a.tu || a.data[i + 1].i > b.data[j + 1].i && j != b.tu)
{
c.data[k + 1].i = b.data[j + 1].i;
c.data[k + 1].j = b.data[j + 1].j;
c.data[k + 1].e = b.data[j + 1].e;
k++;
j++; //前往下一個(gè)b的非0元
}
else if (j == b.tu || a.data[i + 1].i < b.data[j + 1].i && i != a.tu)
{
c.data[k + 1].i = a.data[i + 1].i;
c.data[k + 1].j = a.data[i + 1].j;
c.data[k + 1].e = a.data[i + 1].e;
k++;
i++; //前往下一個(gè)a的非0元
}
}
c.tu = k;
}
//乘法輔助函數(shù)
int Getval(TSMatrix a, int i, int j) {
int k = 1;
while (k <= a.tu && (a.data[k].i != i || a.data[k].j != j))
k++;
if (k <= a.tu)
return a.data[k].e;
else
return 0;
}
//稀疏矩陣三元組乘法
void MultSMatrix(TSMatrix a, TSMatrix b, TSMatrix& c) {
int p = 0;
ElemType s;
if (a.nu != b.mu)
return;
for (int i = 1; i <= a.mu; i++) {
for (int j = 1; j <= b.nu; j++) {
s = 0;
for (int k = 1; k <= a.nu; k++)
s += Getval(a, i, k) * Getval(b, k, j);
if (s != 0) {
c.data[p + 1].i = i;
c.data[p + 1].j = j;
c.data[p + 1].e = s;
p++;
}
}
}
c.mu = a.mu;
c.nu = b.nu;
c.tu = p;
}
//稀疏矩陣轉(zhuǎn)置 （適用于 tu << mu × nu 的情況）
void TransposeSMatrix(TSMatrix M, TSMatrix& T) {
T.mu = M.nu; //T行數(shù)等于原矩陣列數(shù)
T.nu = M.mu; //T列數(shù)等于原矩陣行數(shù)
T.tu = M.tu;
if (!T.tu)
return;
int q = 1; //從列數(shù)小的開始，一一對(duì)應(yīng)賦值
for (int col = 1; col <= M.nu; ++col) {
for (int p = 1; p <= M.tu; ++p) {
if (M.data[p].j == col) {
T.data[q].i = M.data[p].j;
T.data[q].j = M.data[p].i;
T.data[q].e = M.data[p].e;
q++;
}
}
}
}
//稀疏矩陣的快速轉(zhuǎn)置算法
int cpot[MAXSIZE + 1], num[MAXSIZE + 1]; //輔助數(shù)組
//cpot[col] 表示M中第col列第一個(gè)非0元在T.data中的位置
//num[col] 表示M中第col列中非0元的個(gè)數(shù)
void FastTransposeSMatrix(TSMatrix M, TSMatrix& T) {
T.mu = M.nu;
T.nu = M.mu;
T.tu = M.tu;
if (!T.tu)
return;
for (int col = 1; col <= M.mu; col++)
num[col] = 0; //初始化為0
for (int k = 1; k <= M.tu; k++)
num[M.data[k].j]++; //記錄M.data[k].j列中非0元個(gè)數(shù) （簡(jiǎn)易哈希表）
cpot[1] = 1; //初始化第一個(gè)非0元的序號(hào)
for (int col = 2; col <= M.mu; col++) //求第col列中第一個(gè)非零元在T.data中的序號(hào)
cpot[col] = cpot[col - 1] + num[col - 1];
for (int p = 1; p <= M.tu; p++) {
int col = M.data[p].j; //此時(shí)M對(duì)應(yīng)三元組中的非0元的所在列
int q = cpot[col]; //q為當(dāng)前非0元的應(yīng)當(dāng)放置的序號(hào)位置
T.data[q].i = M.data[p].j;
T.data[q].j = M.data[p].i;
T.data[q].e = M.data[p].e;
cpot[col]++; //cpot[col]++,對(duì)應(yīng)下一個(gè)此列中非0元的序號(hào)
//cpot[col]最后一直加到等于cpot[col + 1],第col列也就不會(huì)有更多的非0元了
}
}
int main() {
TSMatrix A, B, C, D;
printf("輸入稀疏矩陣A的三元組:\n");
InPutM(A);
PrintM(A);
printf("\n輸入稀疏矩陣B的三元組:\n");
InPutM(B);
PrintM(B);
//printf("\n矩陣A與B相加得到矩陣C:\n");
//AddSMatrix(A, B, C);
//PrintM(C);
printf("\n矩陣A與B相乘得到矩陣D:\n");
MultSMatrix(A, B, D);
PrintM(D);
printf("\n");
system("pause");
system("cls");
TSMatrix M, T, FT;
printf("————稀疏矩陣轉(zhuǎn)置測(cè)試————\n\n");
InPutM(M);
printf("\n稀疏矩陣轉(zhuǎn)置前三元組: \n");
PrintM(M);
printf("\n稀疏矩陣轉(zhuǎn)置結(jié)果: \n");
TransposeSMatrix(M, T);
PrintM(T);
printf("\n稀疏矩陣的快速轉(zhuǎn)置結(jié)果: \n");
FastTransposeSMatrix(M, FT);
PrintM(FT);
}
到了這里，關(guān)于[數(shù)據(jù)結(jié)構(gòu)] 數(shù)組與特殊矩陣的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
