?第五部分、數(shù)組和廣義表詳解
數(shù)組和廣義表，都用于存儲邏輯關(guān)系為“一對一”的數(shù)據(jù)。
數(shù)組存儲結(jié)構(gòu)，99% 的編程語言都包含的存儲結(jié)構(gòu)，用于存儲不可再分的單一數(shù)據(jù)；而廣義表不同，它還可以存儲子廣義表。
本章重點從矩陣的角度討論二維數(shù)組的存儲，同時講解廣義表的存儲結(jié)構(gòu)以及有關(guān)其廣度和深度的算法實現(xiàn)。
五、行邏輯鏈接的順序表（壓縮存儲稀疏矩陣）詳解
前面學習了如何使用三元組順序表存儲稀疏矩陣，其實現(xiàn)過程就是將矩陣中各個非 0 元素的行標、列標和元素值以三元組的形式存儲到一維數(shù)組中。通過研究實現(xiàn)代碼你會發(fā)現(xiàn)，三元組順序表每次提取指定元素都需要遍歷整個數(shù)組，運行效率很低。
本節(jié)將學習另一種存儲矩陣的方法——行邏輯鏈接的順序表。它可以看作是三元組順序表的升級版，即在三元組順序表的基礎(chǔ)上改善了提取數(shù)據(jù)的效率。
行邏輯鏈接的順序表和三元組順序表的實現(xiàn)過程類似，它們存儲矩陣的過程完全相同，都是將矩陣中非 0 元素的三元組（行標、列標和元素值）存儲在一維數(shù)組中。但為了提高提取數(shù)據(jù)的效率，前者在存儲矩陣時比后者多使用了一個數(shù)組，專門記錄矩陣中每行第一個非 0 元素在一維數(shù)組中的位置。
圖 1 稀疏矩陣示意圖
圖 1 是一個稀疏矩陣，當使用行邏輯鏈接的順序表對其進行壓縮存儲時，需要做以下兩個工作：
- 將矩陣中的非 0 元素采用三元組的形式存儲到一維數(shù)組 data 中，如圖 2 所示（和三元組順序表一樣）：
圖 2 三元組存儲稀疏矩陣
-
使用數(shù)組 rpos 記錄矩陣中每行第一個非 0 元素在一維數(shù)組中的存儲位置。如圖 3 所示:
圖 3 存儲各行首個非 0 元素在數(shù)組中的位置
通過以上兩步操作，即實現(xiàn)了使用行邏輯鏈接的順序表存儲稀疏矩陣。
此時，如果想從行邏輯鏈接的順序表中提取元素，則可以借助 rpos 數(shù)組提高遍歷數(shù)組的效率。
例如，提取圖 1 稀疏矩陣中的元素 2 的過程如下：
- 由 rpos 數(shù)組可知，第一行首個非 0 元素位于data[1]，因此在遍歷此行時，可以直接從第 data[1] 的位置開始，一直遍歷到下一行首個非 0 元素所在的位置（data[3]）之前；
- 同樣遍歷第二行時，由 rpos 數(shù)組可知，此行首個非 0 元素位于 data[3]，因此可以直接從第 data[3] 開始，一直遍歷到下一行首個非 0 元素所在的位置（data[4]）之前；
- 遍歷第三行時，由 rpos 數(shù)組可知，此行首個非 0 元素位于 data[4]，由于這是矩陣的最后一行，因此一直遍歷到 rpos 數(shù)組結(jié)束即可（也就是 data[tu]，tu 指的是矩陣非 0 元素的總個數(shù)）。
以上操作的完整 C 語言實現(xiàn)代碼如下：
#include <stdio.h>
#define MAXSIZE 12500
#define MAXRC 100
#define ElemType int
typedef struct
{
????????int i,j;//行，列
????????ElemType e;//元素值
}Triple;
typedef struct
{
????????Triple data[MAXSIZE+1];
???????? int rpos[MAXRC+1];//每行第一個非零元素在data數(shù)組中的位置
???????? int mu,nu,tu;//行數(shù)，列數(shù)，元素個數(shù)
}RLSMatrix; /
/矩陣的輸出函數(shù)
void display(RLSMatrix M){
????????for(int i=1;i<=M.mu;i++){
????????????????for(int j=1;j<=M.nu;j++){
????????????????????????int value=0;
????????????????????????if(i+1 <=M.mu){
????????????????????????????????for(int k=M.rpos[i];k<M.rpos[i+1];k++){
????????????????????????????????????????if(i == M.data[k].i && j == M.data[k].j){
????????????????????????????????????????????????printf("%d ",M.data[k].e);
????????????????????????????????????????????????value=1;
????????????????????????????????????????????????break;
????????????????????????????????????????}
????????????????????????????????}
????????????????????????????????if(value==0){
???????????????????????????????????????? printf("0 ");
????????????????????????????????}
????????????????????????}else{
????????????????????????????????for(int k=M.rpos[i];k<=M.tu;k++){
????????????????????????????????????????if(i == M.data[k].i && j == M.data[k].j){
????????????????????????????????????????????????printf("%d ",M.data[k].e);
????????????????????????????????????????????????value=1;
????????????????????????????????????????????????break;
????????????????????????????????????????}
????????????????????????????????}
????????????????????????????????if(value==0){
????????????????????????????????????????printf("0 ");
????????????????????????????????}
????????????????????????}
????????????????}
????????????????printf("\n");
????????}
}
int main(int argc, char* argv[])
{
????????RLSMatrix M;
????????M.tu = 4;
????????M.mu = 3;
????????M.nu = 4;
????????M.rpos[1] = 1;
????????M.rpos[2] = 3;
????????M.rpos[3] = 4;
????????M.data[1].e = 3;
????????M.data[1].i = 1;
????????M.data[1].j = 2;
????????M.data[2].e = 5;
????????M.data[2].i = 1;
????????M.data[2].j = 4;
????????M.data[3].e = 1;
????????M.data[3].i = 2;
????????M.data[3].j = 3;
????????M.data[4].e = 2;
????????M.data[4].i = 3;
????????M.data[4].j = 1;
????????//輸出矩陣
????????display(M);
????????return 0;
}
運行結(jié)果：文章來源：http://www.zghlxwxcb.cn/news/detail-811253.html
0 3 0 5
0 0 1 0
2 0 0 0
總結(jié)
通過系統(tǒng)地學習使用行邏輯鏈接的順序表壓縮存儲稀疏矩陣，可以發(fā)現(xiàn)，它僅比三元組順序表多使用了一個 rpos 數(shù)組，從而提高了提取數(shù)據(jù)時遍歷數(shù)組的效率。
六、十字鏈表法，十字鏈表壓縮存儲稀疏矩陣詳解
對于壓縮存儲稀疏矩陣，無論是使用三元組順序表，還是使用行邏輯鏈接的順序表，歸根結(jié)底是使用數(shù)組存儲稀疏矩陣。介于數(shù)組 "不利于插入和刪除數(shù)據(jù)" 的特點，以上兩種壓縮存儲方式都不適合解決類似 "向矩陣中添加或刪除非 0 元素" 的問題。
例如，A 和 B 分別為兩個矩陣，在實現(xiàn) "將矩陣 B 加到矩陣 A 上" 的操作時，矩陣 A 中的元素會發(fā)生很大的變化，之前的非 0 元素可能變?yōu)?0，而 0 元素也可能變?yōu)榉?0 元素。對于此操作的實現(xiàn)，之前所學的壓縮存儲方法就顯得力不從心。
本節(jié)將學習用十字鏈表存儲稀疏矩陣，該存儲方式采用的是 "鏈表+數(shù)組" 結(jié)構(gòu)，如圖 1 所示。
圖 1 十字鏈表示意圖
可以看到，使用十字鏈表壓縮存儲稀疏矩陣時，矩陣中的各行各列都各用一各鏈表存儲，與此同時，所有行鏈表的表頭存儲到一個數(shù)組（rhead），所有列鏈表的表頭存儲到另一個數(shù)組（chead）中。
因此，各個鏈表中節(jié)點的結(jié)構(gòu)應(yīng)如圖 2 所示:
圖 2 十字鏈表的節(jié)點結(jié)構(gòu)
兩個指針域分別用于鏈接所在行的下一個元素以及所在列的下一個元素。
鏈表中節(jié)點的 C 語言代碼表示應(yīng)為：
typedef struct OLNode{
????????int i,j;//元素的行標和列標
????????int data;//元素的值
????????struct OLNode * right,*down;//兩個指針域
}OLNode;
同時，表示十字鏈表結(jié)構(gòu)的 C 語言代碼應(yīng)為：
#include<stdio.h>
#include<stdlib.h>
typedef struct OLNode
{
????????int i, j, e; //矩陣三元組i代表行 j代表列 e代表當前位置的數(shù)據(jù)
????????struct OLNode *right, *down; //指針域 右指針 下指針
}OLNode, *OLink;
typedef struct {
????????OLink *rhead, *chead; //行和列鏈表頭指針
????????int mu, nu, tu; //矩陣的行數(shù),列數(shù)和非零元的個數(shù)
}CrossList;
CrossList CreateMatrix_OL(CrossList M);
void display(CrossList M);
int main() {
????????CrossList M;
????????M.rhead = NULL;
????????M.chead = NULL;
????????M = CreateMatrix_OL(M);
????????printf("輸出矩陣M:\n");
????????display(M);
????????return 0;
}
CrossList CreateMatrix_OL(CrossList M)
{
????????int m, n, t;
????????int i, j, e;
????????OLNode *p, *q;
????????printf("輸入矩陣的行數(shù)、列數(shù)和非0元素個數(shù)：");
????????scanf("%d%d%d", &m, &n, &t);
????????M.mu = m;
????????M.nu = n;
????????M.tu = t;
????????if (!(M.rhead = (OLink*)malloc((m + 1) * sizeof(OLink))) || !(M.chead = (OLink*)malloc((n + 1) * sizeof(OLink))))
????????{
????????????????printf("初始化矩陣失敗");
????????????????exit(0);
????????}
????????for (i = 1; i <= m; i++)
???????? {
????????????????M.rhead[i] = NULL;
????????}
????????for (j = 1; j <= n; j++)
???????? {
????????????????M.chead[j] = NULL;
????????}
????????for (scanf("%d%d%d", &i, &j, &e); 0 != i; scanf("%d%d%d", &i, &j, &e)) {
????????????????if (!(p = (OLNode*)malloc(sizeof(OLNode))))
???????????????? {
????????????????????????printf("初始化三元組失敗");
????????????????????????exit(0);
????????????????}
????????????????p->i = i;
????????????????p->j = j;
????????????????p->e = e;
????????????????//鏈接到行的指定位置
????????????????if (NULL == M.rhead[i] || M.rhead[i]->j > j)
????????????????{
????????????????????????p->right = M.rhead[i];
????????????????????????M.rhead[i] = p;
????????????????}
????????????????else
????????????????{
????????????????????????for (q = M.rhead[i]; (q->right) && q->right->j < j; q = q->right);
????????????????????????????????p->right = q->right;
????????????????????????????????q->right = p;
????????????????}
???????????????? //鏈接到列的指定位置
????????????????if (NULL == M.chead[j] || M.chead[j]->i > i)
????????????????{
????????????????????????p->down = M.chead[j];
????????????????????????M.chead[j] = p;
????????????????}
????????????????else
????????????????{
????????????????????????for (q = M.chead[j]; (q->down) && q->down->i < i; q = q->down);
????????????????????????????????p->down = q->down;
????????????????????????????????q->down = p;
????????????????????????}
????????????????}
????????return M;
}
void display(CrossList M) {
????????for (int i = 1; i <= M.nu; i++)
????????{
????????????????if (NULL != M.chead[i])
????????????????{
????????????????????????OLink p = M.chead[i];
????????????????????????while (NULL != p)
????????????????????????{
????????????????????????????????printf("%d\t%d\t%d\n", p->i, p->j, p->e);
????????????????????????????????p = p->down;
????????????????????????}
????????????????}
????????}
}
運行結(jié)果：
輸入矩陣的行數(shù)、列數(shù)和非0元素個數(shù)：3 3 3
2 2 3
2 3 4
3 2 5
0 0 0
輸出矩陣M:
2?????? 2?????? 3
3?????? 2?????? 5
2?????? 3?????? 4文章來源地址http://www.zghlxwxcb.cn/news/detail-811253.html
到了這里，關(guān)于數(shù)據(jù)結(jié)構(gòu)與算法教程，數(shù)據(jù)結(jié)構(gòu)C語言版教程！（第五部分、數(shù)組和廣義表詳解）三的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
