国产 无码 综合区,色欲AV无码国产永久播放,无码天堂亚洲国产AV,国产日韩欧美女同一区二区

  1. Toy模板網(wǎng)首頁
  2. >Toy博客

【數(shù)據(jù)結(jié)構(gòu)】數(shù)組和字符串（八）：稀疏矩陣的鏈接存儲：十字鏈表的創(chuàng)建、插入元素、遍歷打印（按行、按列、打印矩陣）、銷毀

2年前作者：QomolangmaH分類：Toy博客閱讀(24)違法舉報

這篇具有很好參考價值的文章主要介紹了【數(shù)據(jù)結(jié)構(gòu)】數(shù)組和字符串（八）：稀疏矩陣的鏈接存儲：十字鏈表的創(chuàng)建、插入元素、遍歷打?。ò葱小戳?、打印矩陣）、銷毀。希望對大家有所幫助。如果存在錯誤或未考慮完全的地方，請大家不吝賜教，您也可以點擊"舉報違法"按鈕提交疑問。

4.2.1 矩陣的數(shù)組表示

【數(shù)據(jù)結(jié)構(gòu)】數(shù)組和字符串（一）：矩陣的數(shù)組表示

4.2.2 特殊矩陣的壓縮存儲

??矩陣是以按行優(yōu)先次序?qū)⑺芯仃囋卮娣旁谝粋€一維數(shù)組中。但是對于特殊矩陣，如對稱矩陣、三角矩陣、對角矩陣和稀疏矩陣等, 如果用這種方式存儲，會出現(xiàn)大量存儲空間存放重復(fù)信息或零元素的情況，這樣會造成很大的空間浪費。為節(jié)約存儲空間和算法（程序）運行時間，通常會采用壓縮存儲的方法。

  • 對角矩陣：指除了主對角線以外的元素都為零的矩陣，即對 任意 i ≠ j (1≤ i , j ≤n)，都有M(i, j)=0。由于只有主對角線上有非零元素，只需存儲主對角線上的元素即可。
  • 三角矩陣：指上三角或下三角的元素都為零的矩陣。同樣地，只需存儲其中一部分非零元素，可以節(jié)省存儲空間。
  • 對稱矩陣：指矩陣中的元素關(guān)于主對角線對稱的矩陣。由于對稱矩陣的非零元素有一定的規(guī)律，可以只存儲其中一部分元素，從而減少存儲空間。
  • 稀疏矩陣：指大部分元素為零的矩陣。傳統(tǒng)的按行優(yōu)先次序存儲方法會浪費大量空間來存儲零元素，因此采用壓縮存儲的方法更為合適。常見的壓縮存儲方法有：壓縮稠密行（CSR）、壓縮稠密列（CSC）、坐標列表（COO）等。

a. 對角矩陣的壓縮存儲

【數(shù)據(jù)結(jié)構(gòu)】數(shù)組和字符串（二）：特殊矩陣的壓縮存儲：對角矩陣——一維數(shù)組

b~c. 三角、對稱矩陣的壓縮存儲

【數(shù)據(jù)結(jié)構(gòu)】數(shù)組和字符串（三）：特殊矩陣的壓縮存儲：三角矩陣、對稱矩陣——一維數(shù)組

d. 稀疏矩陣的壓縮存儲——三元組表

【數(shù)據(jù)結(jié)構(gòu)】數(shù)組和字符串（四）：特殊矩陣的壓縮存儲：稀疏矩陣——三元組表

4.2.3三元組表的轉(zhuǎn)置、加法、乘法、操作

【數(shù)據(jù)結(jié)構(gòu)】數(shù)組和字符串（七）：特殊矩陣的壓縮存儲：三元組表的轉(zhuǎn)置、加法、乘法操作

4.2.4十字鏈表

??十字鏈表（Cross-linked List）是一種用于表示稀疏矩陣的數(shù)據(jù)結(jié)構(gòu)。稀疏矩陣是指大部分元素為零的矩陣，而十字鏈表可以有效地存儲和操作這種類型的矩陣。在稀疏矩陣的十字鏈表中，每個非零元素都由一個節(jié)點表示。節(jié)點包含了幾個字段：

  1. LEFT：指向該節(jié)點在同一行中的左鄰非零元素的地址信息。
  2. UP：指向該節(jié)點在同一列中的上鄰非零元素的地址信息。
  3. ROW：存儲該節(jié)點在矩陣中的行號。
  4. COL：存儲該節(jié)點在矩陣中的列號。
  5. VAL：存儲該節(jié)點的元素值。

??每一行都有一個表頭節(jié)點，它引導(dǎo)著該行的循環(huán)鏈表，循環(huán)鏈表中的每個節(jié)點按照列號的順序排列。同樣，每一列也有一個表頭節(jié)點，它引導(dǎo)著該列的循環(huán)鏈表，循環(huán)鏈表中的每個節(jié)點按照行號的順序排列。
??關(guān)于循環(huán)鏈表： 【數(shù)據(jù)結(jié)構(gòu)】線性表（三）循環(huán)鏈表的各種操作（創(chuàng)建、插入、查找、刪除、修改、遍歷打印、釋放內(nèi)存空間）

【數(shù)據(jù)結(jié)構(gòu)】數(shù)組和字符串（八）：稀疏矩陣的鏈接存儲：十字鏈表的創(chuàng)建、插入元素、遍歷打印（按行、按列、打印矩陣）、銷毀,數(shù)據(jù)結(jié)構(gòu),數(shù)據(jù)結(jié)構(gòu),矩陣,鏈表,c語言

  • 在稀疏矩陣的十字鏈表中，每一行和每一列都有一個表頭節(jié)點。

    • 對于行表頭節(jié)點 BASEROW[i]，其中 i 表示行號，范圍從 1 到 m（矩陣的行數(shù)）。如果該行為空（即沒有非零元素），則 COL(Loc(BASEROW[i])) 的值為 -1。否則，COL(Loc(BASEROW[i])) 的值為該行中最右邊的非零元素的列號。

    • 對于列表頭節(jié)點 BASECOL[j]，其中 j 表示列號，范圍從 1 到 n（矩陣的列數(shù)）。如果該列為空（即沒有非零元素），則 ROW(Loc(BASECOL[j])) 的值為 -1。否則，ROW(Loc(BASECOL[j])) 的值為該列中最下邊的非零元素的行號。

  • 由于行和列都是循環(huán)鏈表，行表頭節(jié)點 BASEROW[i] 中的 LEFT 指針循環(huán)地鏈接到該行最右邊的非零元素，列表頭節(jié)點 BASECOL[j] 中的 UP 指針循環(huán)地鏈接到該列最下邊的非零元素。
    ?
    ?通過這種方式，可以用較少的空間表示稀疏矩陣，并且可以快速地進行行和列的遍歷操作。每個節(jié)點的 LEFT 和 UP 指針可以用來定位其左鄰和上鄰非零元素，從而實現(xiàn)矩陣的訪問和操作。

0. 十字鏈表結(jié)構(gòu)

// 定義矩陣節(jié)點結(jié)構(gòu)
typedef struct MatrixNode {
    int row;
    int col;
    int value;
    struct MatrixNode* right;
    struct MatrixNode* down;
} MatrixNode;

// 定義稀疏矩陣結(jié)構(gòu)
typedef struct SparseMatrix {
    int rows;
    int cols;
    MatrixNode** rowHeaders;
    MatrixNode** colHeaders;
} SparseMatrix;

left~up ……right~down

1. 創(chuàng)建

SparseMatrix* createSparseMatrix(int rows, int cols) {
    SparseMatrix* matrix = (SparseMatrix*)malloc(sizeof(SparseMatrix));
    matrix->rows = rows;
    matrix->cols = cols;

    // 創(chuàng)建行表頭節(jié)點數(shù)組
    matrix->rowHeaders = (MatrixNode**)malloc((rows + 1) * sizeof(MatrixNode*));
    for (int i = 0; i <= rows; i++) {
        matrix->rowHeaders[i] = NULL;
    }

    // 創(chuàng)建列表頭節(jié)點數(shù)組
    matrix->colHeaders = (MatrixNode**)malloc((cols + 1) * sizeof(MatrixNode*));
    for (int j = 0; j <= cols; j++) {
        matrix->colHeaders[j] = NULL;
    }

    return matrix;
}
  • 分配稀疏矩陣結(jié)構(gòu)體的內(nèi)存，并將行數(shù)和列數(shù)存儲在結(jié)構(gòu)體的相應(yīng)字段中。
  • 分配行表頭節(jié)點數(shù)組的內(nèi)存，并將每個元素初始化為NULL。
  • 分配列表頭節(jié)點數(shù)組的內(nèi)存，并將每個元素初始化為NULL。
  • 返回指向創(chuàng)建的稀疏矩陣的指針。

2. 銷毀

void destroySparseMatrix(SparseMatrix* matrix) {
    if (matrix == NULL) {
        return;
    }

    // 釋放所有節(jié)點內(nèi)存
    for (int i = 1; i <= matrix->rows; i++) {
        MatrixNode* current = matrix->rowHeaders[i];
        while (current != NULL) {
            MatrixNode* temp = current;
            current = current->right;
            free(temp);
        }
    }

    // 釋放行表頭節(jié)點數(shù)組
    free(matrix->rowHeaders);

    // 釋放列表頭節(jié)點數(shù)組
    free(matrix->colHeaders);

    // 釋放稀疏矩陣結(jié)構(gòu)
    free(matrix);
}
  • 檢查稀疏矩陣指針是否為NULL，如果是，則直接返回。
  • 釋放所有節(jié)點的內(nèi)存：
    • 遍歷每一行，從第一行到最后一行：
      • 通過行表頭節(jié)點數(shù)組獲取當(dāng)前行的行鏈表頭節(jié)點。
      • 遍歷行鏈表中的每個節(jié)點：
        • 釋放當(dāng)前節(jié)點的內(nèi)存，并將當(dāng)前節(jié)點指針移動到下一個節(jié)點。
    • 釋放行表頭節(jié)點數(shù)組的內(nèi)存。
    • 遍歷每一列，從第一列到最后一列：
      • 通過列表頭節(jié)點數(shù)組獲取當(dāng)前列的列鏈表頭節(jié)點。
      • 遍歷列鏈表中的每個節(jié)點：
        • 釋放當(dāng)前節(jié)點的內(nèi)存，并將當(dāng)前節(jié)點指針移動到下一個節(jié)點。
    • 釋放列表頭節(jié)點數(shù)組的內(nèi)存。
  • 釋放稀疏矩陣結(jié)構(gòu)體的內(nèi)存。

3. 插入

void insertElement(SparseMatrix* matrix, int row, int col, int value) {
    if (row <= 0 || row > matrix->rows || col <= 0 || col > matrix->cols) {
        printf("Invalid position!\n");
        return;
    }

    // 創(chuàng)建新節(jié)點
    MatrixNode* newNode = (MatrixNode*)malloc(sizeof(MatrixNode));
    newNode->row = row;
    newNode->col = col;
    newNode->value = value;
    newNode->right = NULL;
    newNode->down = NULL;

    // 插入到行鏈表
    if (matrix->rowHeaders[row] == NULL || matrix->rowHeaders[row]->col > col) {
        // 插入到行鏈表的頭部
        newNode->right = matrix->rowHeaders[row];
        matrix->rowHeaders[row] = newNode;
    } else {
        MatrixNode* current = matrix->rowHeaders[row];
        while (current->right != NULL && current->right->col < col) {
            current = current->right;
        }
        newNode->right = current->right;
        current->right = newNode;
    }

    // 插入到列鏈表
    if (matrix->colHeaders[col] == NULL || matrix->colHeaders[col]->row > row) {
        // 插入到列鏈表的頭部
        newNode->down = matrix->colHeaders[col];
        matrix->colHeaders[col] = newNode;
    } else {
        MatrixNode* current = matrix->colHeaders[col];
        while (current->down != NULL && current->down->row < row) {
            current = current->down;
        }
        newNode->down = current->down;
        current->down = newNode;
    }
}
  • 檢查行數(shù)和列數(shù)是否在有效范圍內(nèi)，如果不是，則打印錯誤消息并返回。
  • 創(chuàng)建一個新的節(jié)點，并將行、列和值存儲在節(jié)點的相應(yīng)字段中。
  • 在行鏈表中插入節(jié)點：
    • 如果當(dāng)前行的行鏈表為空，或者當(dāng)前行的行鏈表頭節(jié)點的列大于要插入的列：
      • 將要插入的節(jié)點的右指針指向當(dāng)前行的行鏈表頭節(jié)點。
      • 將當(dāng)前行的行鏈表頭節(jié)點更新為要插入的節(jié)點。
    • 否則，遍歷當(dāng)前行的行鏈表，直到找到插入位置：
      • 將要插入的節(jié)點的右指針指向當(dāng)前節(jié)點的右指針。
      • 將當(dāng)前節(jié)點的右指針指向要插入的節(jié)點。
  • 在列鏈表中插入節(jié)點：
    • 如果當(dāng)前列的列鏈表為空，或者當(dāng)前列的列鏈表頭節(jié)點的行大于要插入的行：
      • 將要插入的節(jié)點的下指針指向當(dāng)前列的列鏈表頭節(jié)點。
      • 將當(dāng)前列的列鏈表頭節(jié)點更新為要插入的節(jié)點。
    • 否則，遍歷當(dāng)前列的列鏈表，直到找到插入位置：
      • 將要插入的節(jié)點的下指針指向當(dāng)前節(jié)點的下指針。
      • 將當(dāng)前節(jié)點的下指針指向要插入的節(jié)點。

4. 打印矩陣形式

void printSparseMatrix(SparseMatrix* matrix) {
    for (int i = 1; i <= matrix->rows; i++) {
        MatrixNode* current = matrix->rowHeaders[i];
        for (int j = 1; j <= matrix->cols; j++) {
            if (current != NULL && current->col == j) {
                printf("%d ", current->value);
                current = current->right;
            } else {
                printf("0 ");
            }
        }
        printf("\n");
    }
}
  • 從第一行開始遍歷稀疏矩陣的每一行：
    • 通過行表頭節(jié)點數(shù)組獲取當(dāng)前行的行鏈表頭節(jié)點。
    • 遍歷當(dāng)前行的每一列，從第一列到最后一列：
      • 如果當(dāng)前節(jié)點存在且與當(dāng)前列匹配，則打印節(jié)點的值。
      • 否則，打印0。
    • 打印換行符。

5. 按行打印

void printRowNodes(SparseMatrix* matrix) {
    printf("Row Nodes:\n");
    for (int i = 1; i <= matrix->rows; i++) {
        printf("Row %d: ", i);
        MatrixNode* current = matrix->rowHeaders[i];
        while (current != NULL) {
            printf("(%d, %d, %d) ", current->row, current->col, current->value);
            current = current->right;
        }
        printf("\n");
    }
}
  • 從第一行開始遍歷稀疏矩陣的每一行：
    • 打印當(dāng)前行的行號。
    • 通過行表頭節(jié)點數(shù)組獲取當(dāng)前行的行鏈表頭節(jié)點。
    • 遍歷當(dāng)前行的行鏈表，打印每個節(jié)點的行、列和值。
    • 打印換行符。

6.按列打印

void printColumnNodes(SparseMatrix* matrix) {
    printf("Column Nodes:\n");
    for (int j = 1; j <= matrix->cols; j++) {
        printf("Column %d: ", j);
        MatrixNode* current = matrix->colHeaders[j];
        while (current != NULL) {
            printf("(%d, %d, %d) ", current->row, current->col, current->value);
            current = current->down;
        }
        printf("\n");
    }
}
  • 與行打印等價

7. 主函數(shù)

int main() {
    // 創(chuàng)建一個3x3的稀疏矩陣
    SparseMatrix* matrix = createSparseMatrix(3, 3);

    // 插入元素
    insertElement(matrix, 1, 1, 1);
    insertElement(matrix, 1, 2, 2);
    insertElement(matrix, 2, 2, 3);
    insertElement(matrix, 3, 1, 4);
    insertElement(matrix, 3, 3, 5);

    // 打印稀疏矩陣
    printf("Sparse Matrix:\n");
    printSparseMatrix(matrix);

    // 輸出每行節(jié)點
    printRowNodes(matrix);

    // 輸出每列節(jié)點
    printColumnNodes(matrix);

    // 銷毀稀疏矩陣
    destroySparseMatrix(matrix);

    return 0;
}

【數(shù)據(jù)結(jié)構(gòu)】數(shù)組和字符串（八）：稀疏矩陣的鏈接存儲：十字鏈表的創(chuàng)建、插入元素、遍歷打?。ò葱?、按列、打印矩陣）、銷毀,數(shù)據(jù)結(jié)構(gòu),數(shù)據(jù)結(jié)構(gòu),矩陣,鏈表,c語言文章來源地址http://www.zghlxwxcb.cn/news/detail-739156.html

8. 代碼整合

#include <stdio.h>
#include <stdlib.h>

// 定義矩陣節(jié)點結(jié)構(gòu)
typedef struct MatrixNode {
    int row;
    int col;
    int value;
    struct MatrixNode* right;
    struct MatrixNode* down;
} MatrixNode;

// 定義稀疏矩陣結(jié)構(gòu)
typedef struct SparseMatrix {
    int rows;
    int cols;
    MatrixNode** rowHeaders;
    MatrixNode** colHeaders;
} SparseMatrix;

// 創(chuàng)建稀疏矩陣
SparseMatrix* createSparseMatrix(int rows, int cols) {
    SparseMatrix* matrix = (SparseMatrix*)malloc(sizeof(SparseMatrix));
    matrix->rows = rows;
    matrix->cols = cols;

    // 創(chuàng)建行表頭節(jié)點數(shù)組
    matrix->rowHeaders = (MatrixNode**)malloc((rows + 1) * sizeof(MatrixNode*));
    for (int i = 0; i <= rows; i++) {
        matrix->rowHeaders[i] = NULL;
    }

    // 創(chuàng)建列表頭節(jié)點數(shù)組
    matrix->colHeaders = (MatrixNode**)malloc((cols + 1) * sizeof(MatrixNode*));
    for (int j = 0; j <= cols; j++) {
        matrix->colHeaders[j] = NULL;
    }

    return matrix;
}

// 銷毀稀疏矩陣
void destroySparseMatrix(SparseMatrix* matrix) {
    if (matrix == NULL) {
        return;
    }

    // 釋放所有節(jié)點內(nèi)存
    for (int i = 1; i <= matrix->rows; i++) {
        MatrixNode* current = matrix->rowHeaders[i];
        while (current != NULL) {
            MatrixNode* temp = current;
            current = current->right;
            free(temp);
        }
    }

    // 釋放行表頭節(jié)點數(shù)組
    free(matrix->rowHeaders);

    // 釋放列表頭節(jié)點數(shù)組
    free(matrix->colHeaders);

    // 釋放稀疏矩陣結(jié)構(gòu)
    free(matrix);
}

// 插入元素
void insertElement(SparseMatrix* matrix, int row, int col, int value) {
    if (row <= 0 || row > matrix->rows || col <= 0 || col > matrix->cols) {
        printf("Invalid position!\n");
        return;
    }

    // 創(chuàng)建新節(jié)點
    MatrixNode* newNode = (MatrixNode*)malloc(sizeof(MatrixNode));
    newNode->row = row;
    newNode->col = col;
    newNode->value = value;
    newNode->right = NULL;
    newNode->down = NULL;

    // 插入到行鏈表
    if (matrix->rowHeaders[row] == NULL || matrix->rowHeaders[row]->col > col) {
        // 插入到行鏈表的頭部
        newNode->right = matrix->rowHeaders[row];
        matrix->rowHeaders[row] = newNode;
    } else {
        MatrixNode* current = matrix->rowHeaders[row];
        while (current->right != NULL && current->right->col < col) {
            current = current->right;
        }
        newNode->right = current->right;
        current->right = newNode;
    }

    // 插入到列鏈表
    if (matrix->colHeaders[col] == NULL || matrix->colHeaders[col]->row > row) {
        // 插入到列鏈表的頭部
        newNode->down = matrix->colHeaders[col];
        matrix->colHeaders[col] = newNode;
    } else {
        MatrixNode* current = matrix->colHeaders[col];
        while (current->down != NULL && current->down->row < row) {
            current = current->down;
        }
        newNode->down = current->down;
        current->down = newNode;
    }
}

// 打印稀疏矩陣
void printSparseMatrix(SparseMatrix* matrix) {
    for (int i = 1; i <= matrix->rows; i++) {
        MatrixNode* current = matrix->rowHeaders[i];
        for (int j = 1; j <= matrix->cols; j++) {
            if (current != NULL && current->col == j) {
                printf("%d ", current->value);
                current = current->right;
            } else {
                printf("0 ");
            }
        }
        printf("\n");
    }
}

// 輸出每行節(jié)點
void printRowNodes(SparseMatrix* matrix) {
    printf("Row Nodes:\n");
    for (int i = 1; i <= matrix->rows; i++) {
        printf("Row %d: ", i);
        MatrixNode* current = matrix->rowHeaders[i];
        while (current != NULL) {
            printf("(%d, %d, %d) ", current->row, current->col, current->value);
            current = current->right;
        }
        printf("\n");
    }
}

// 輸出每列節(jié)點
void printColumnNodes(SparseMatrix* matrix) {
    printf("Column Nodes:\n");
    for (int j = 1; j <= matrix->cols; j++) {
        printf("Column %d: ", j);
        MatrixNode* current = matrix->colHeaders[j];
        while (current != NULL) {
            printf("(%d, %d, %d) ", current->row, current->col, current->value);
            current = current->down;
        }
        printf("\n");
    }
}

int main() {
    // 創(chuàng)建一個3x3的稀疏矩陣
    SparseMatrix* matrix = createSparseMatrix(3, 3);

    // 插入元素
    insertElement(matrix, 1, 1, 1);
    insertElement(matrix, 1, 2, 2);
    insertElement(matrix, 2, 2, 3);
    insertElement(matrix, 3, 1, 4);
    insertElement(matrix, 3, 3, 5);

    // 打印稀疏矩陣
    printf("Sparse Matrix:\n");
    printSparseMatrix(matrix);

    // 輸出每行節(jié)點
    printRowNodes(matrix);

    // 輸出每列節(jié)點
    printColumnNodes(matrix);

    // 銷毀稀疏矩陣
    destroySparseMatrix(matrix);

    return 0;
}

到了這里，關(guān)于【數(shù)據(jù)結(jié)構(gòu)】數(shù)組和字符串（八）：稀疏矩陣的鏈接存儲：十字鏈表的創(chuàng)建、插入元素、遍歷打印（按行、按列、打印矩陣）、銷毀的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！

本文來自互聯(lián)網(wǎng)用戶投稿，該文觀點僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務(wù)，不擁有所有權(quán)，不承擔(dān)相關(guān)法律責(zé)任。如若轉(zhuǎn)載，請注明出處： 如若內(nèi)容造成侵權(quán)/違法違規(guī)/事實不符，請點擊違法舉報進行投訴反饋，一經(jīng)查實，立即刪除！

領(lǐng)支付寶紅包贊助服務(wù)器費用

相關(guān)文章

覺得文章有用就打賞一下文章作者

支付寶掃一掃打賞

博客贊助

微信掃一掃打賞

請作者喝杯咖啡吧~博客贊助

支付寶掃一掃領(lǐng)取紅包，優(yōu)惠每天領(lǐng)

二維碼1

領(lǐng)取紅包

二維碼2

領(lǐng)紅包