GroupBlog

矩阵
数学上，一个m×n的矩阵是一个由m行n列元素排列成的矩形阵列。矩阵里的元素可以是数字、符号或数学式。以下是一个由6个数字元素构成的2行3列的矩阵：

[12095 - 13 - 6]

$\begin{bmatrix}1&9&-13\\20&5&-6\end{bmatrix}$

[12095 - 13 - 6]

$\begin{bmatrix}1 & 9 & -13 \\20 & 5 & -6 \end{bmatrix}$
计算机科学中，三维动画制作也需要用到矩阵。矩阵的运算是数值分析领域的重要问题。将矩阵分解为简单矩阵的组合可以在理论和实际应用上简化矩阵的运算。对一些应用广泛而形式特殊的矩阵，例如稀疏矩阵和准对角矩阵，有特定的快速运算算法。
稀疏矩阵
在数值分析中，稀疏矩阵（Sparse matrix），是其元素大部分为零的矩阵。反之，如果大部分元素都非零，则这个矩阵是稠密的。在科学与工程领域中求解线性模型时经常出现大型的稀疏矩阵。
在使用计算机存储和操作稀疏矩阵时，经常需要修改标准算法以利用矩阵的稀疏结构。由于其自身的稀疏特性，通过压缩可以大大节省稀疏矩阵的内存代价。更为重要的是，由于过大的尺寸，标准的算法经常无法操作这些稀疏矩阵。
稀疏矩阵主要用两种数据结构来表示，三元组和十字链表。
三元组

在学习线性代数的时候，经常用到矩阵。在C语言中，表示矩阵的最直观形式就是二维数组。然而在实际应用中，很多高阶矩阵中的非零元素非常少，这个时候如果继续使用二维数组存储，那么就会浪费很多存储空间。
在数据结构中，我们用三元组存储稀疏矩阵。三元组定义为(i,v,j)，这三个值一次表示矩阵的行、列、值。

这里写图片描述

定义三元组（行，列，值）

typedef struct TRIAD {
    int row;
    int col;
    int value;
}TRIAD;

定义稀疏矩阵（三元组数组，行最大值，列最大值，有效值个数）

typedef struct TRIPLE {
    TRIAD *triad;
    int maxRow;
    int maxCol;
    int valueCount;
}TRIPLE;

初始化三元组

void initTriple(TRIPLE **triple, int maxRow, int maxCol, int valueCount) {
    TRIPLE *tp;

    if(NULL != *triple || maxRow <= 0 || maxCol <= 0 
        || valueCount <= 0 || valueCount >= maxRow*maxCol) {
        return;
    }

    tp = (TRIPLE *)calloc(sizeof(TRIPLE), 1);
    if(NULL != tp) {
        tp->triad = (TRIAD *)calloc(sizeof(TRIAD), valueCount);
        tp->maxRow = maxRow;
        tp->maxCol = maxCol;
        tp->valueCount = valueCount;

        *triple = tp;
    }
}

输入有效数据

void inputTriad(TRIPLE triple) {
    int i;
    int row;
    int col;
    int value;

    printf("请按照行升序，行值相同的按列升序，输入有效数据\n");
    for(i = 0; i < triple.valueCount; i++) {
        printf("%d/%d:", i+1, triple.valueCount);
        scanf("%d%d%d", &row, &col, &value);
        triple.triad[i].row = row;
        triple.triad[i].col = col;
        triple.triad[i].value = value;
    }
}

矩阵的转置（实际就是将三元组的行值和列值进行交换）

void revangeMatrixByTriple(TRIPLE sourceTriple, TRIPLE **targetTriple) {
    int *pointIndex;
    int i;
    int index;

    initTriple(targetTriple, sourceTriple.maxCol, sourceTriple.maxRow, 
            sourceTriple.valueCount);

    pointIndex = (int *)calloc(sizeof(int), sourceTriple.maxCol+1);
    for(i = 0; i < sourceTriple.valueCount; i++) {
        pointIndex[sourceTriple.triad[i].col+1]++;
    }
    for(i = 1; i < sourceTriple.maxCol+1; i++) {
        pointIndex[i] += pointIndex[i-1];

    }

    for(i = 0; i < sourceTriple.valueCount; i++) {
        index = pointIndex[sourceTriple.triad[i].col];
        (*targetTriple)->triad[index].row = sourceTriple.triad[i].col;
        (*targetTriple)->triad[index].col = sourceTriple.triad[i].row;
        (*targetTriple)->triad[index].value = sourceTriple.triad[i].value;
        pointIndex[sourceTriple.triad[i].col]++;
    }

    free(pointIndex);
}

O(∩_∩)O哈哈~

这里写图片描述

显示稀疏矩阵

void showMatrixByTriple(TRIPLE triple) {
    int i;
    int j;
    int index = 0;

    for(i = 0; i < triple.maxRow; i++) {
        for(j = 0; j < triple.maxCol; j++) {
            if(triple.triad[index].row == i && triple.triad[index].col == j) {
                printf("%4d ", triple.triad[index++].value);
            } else {
                printf("%4d ", 0);
            }
        }
        puts("");
    }
}

销毁矩阵^_^

void destoryTriple(TRIPLE **triple) {
    if(NULL == *triple) {
        return;
    }

    free((*triple)->triad);
    free(*triple);

    *triple = NULL;
}

十字链表
十字链表（Orthogonal List)是有向图的另一种链式存储结构。该结构可以看成是将有向图的邻接表和逆邻接表结合起来得到的。用十字链表来存储有向图，可以达到高效的存取效果。

这里写图片描述

定于一个简单布尔型（毕竟C语言:-(）

typedef unsigned char boolean;

#define     TRUE        1
#define     FALSE       0
#define     NOT_FOUND  -1

定义节点（一个值和两个指针域）

typedef struct TRIAD {
    int value;
    struct TRIAD *row;
    struct TRIAD *col;
}TRIAD;

定义稀疏矩阵（最大行值，最大列值，两个头指针，一个代表行链表，一个代表列链表）

typedef struct TRIPLE {
    int maxRow;
    int maxCol;
    TRIAD **row;
    TRIAD **col;
}TRIPLE;

初始化稀疏矩阵

void initTriple(TRIPLE **triple, int maxRow, int maxCol) {
    TRIPLE *tp = NULL;
    int i;

    if(NULL != *triple || maxRow <= 0 || maxCol <= 0) {
        return;
    }

    tp = (TRIPLE *)calloc(sizeof(TRIPLE), 1);
    if(NULL == tp) {
        return;
    }

    tp->maxRow = maxRow;
    tp->maxCol = maxCol;
    tp->row = (TRIAD **)calloc(sizeof(TRIAD *), maxRow);
    tp->col = (TRIAD **)calloc(sizeof(TRIAD *), maxCol);

    for(i = 0; i < maxRow; i++) {
        tp->row[i] = NULL;
    }

    for(i = 0; i < maxCol; i++) {
        tp->col[i] = NULL;
    }

    *triple = tp;
}

创建一个节点

TRIAD *createTriad(int value) {
    TRIAD *triad = (TRIAD *)calloc(sizeof(TRIAD), 1);

    triad->value = value;
    triad->row = triad->col = NULL;

    return triad;
}

找到节点所在行位置和列位置

int colIndexAt(TRIPLE triple, TRIAD *triad) {
    int colIndex;
    TRIAD *node;

    if(NULL == triad) {
        return NOT_FOUND;
    }

    for(colIndex = 0; colIndex < triple.maxCol; colIndex++) {
        for(node = triple.col[colIndex]; NULL != node; node = node->row) {
            if(node == triad) {
                return colIndex;
            }
        }
    }
    return NOT_FOUND;
}

int rowIndexAt(TRIPLE triple, TRIAD *triad) {
    int rowIndex;
    TRIAD *node;

    if(NULL == triad) {
        return NOT_FOUND;
    }

    for(rowIndex = 0; rowIndex < triple.maxRow; rowIndex++) {
        for(node = triple.row[rowIndex]; NULL != node; node = node->col) {
            if(node == triad) {
                return rowIndex;
            }
        }
    }
    return NOT_FOUND;
}

将节点分别插入行链表和列链表

boolean insertNodeIntoRow(TRIPLE triple, TRIAD *newNode, int row, int col) {
    TRIAD *preNode = NULL;
    TRIAD *node = triple.row[row];

    while(NULL != node) {
        int colIndex = colIndexAt(triple, node);
        if(colIndex < col) {
            preNode = node;
            node = node->col;
        } else if(colIndex == col) {
            return FALSE;
        } else {
            break;
        }
    }

    if(NULL == preNode) {
        newNode->col = triple.row[row];
        triple.row[row] = newNode;
    } else {
        newNode->col = preNode->col;
        preNode->col = newNode;
    }

    return TRUE;
}

boolean insertNodeIntoCol(TRIPLE triple, TRIAD *newNode, int row, int col) {
    TRIAD *preNode = NULL;
    TRIAD *node = triple.col[col];

    while(NULL != node) {
        int rowIndex = rowIndexAt(triple, node);
        if(rowIndex < row) {
            preNode = node;
            node = node->row;
        } else if(rowIndex == row) {
            return FALSE;
        } else {
            break;
        }
    }

    if(NULL == preNode) {
        newNode->row = triple.col[col];
        triple.col[col] = newNode;
    } else {
        newNode->row = preNode->row;
        preNode->row = newNode;
    }

    return TRUE;
}

插入节点（把前面几个小功能汇集在一块）

boolean addTriad(TRIPLE triple, int row, int col, int value) {
    TRIAD *newNode = createTriad(value);

    if(FALSE == insertNodeIntoRow(triple, newNode, row, col) 
            || FALSE == insertNodeIntoCol(triple, newNode, row, col)) {
        free(newNode);

        return FALSE;
    }

    return TRUE;
}

显示稀疏矩阵（按列显示）

void showMatrix(TRIPLE triple) {
    int i;
    int j;
    TRIAD *node;

    for(i = 0; i < triple.maxRow; i++) {
        int colIndex;

        node = triple.row[i];
        colIndex = colIndexAt(triple, node);
        for(j = 0; j < triple.maxCol; j++) {
            if(colIndex == j) {
                printf("%4d ", node->value);
                node = node->col;
                colIndex = colIndexAt(triple, node);
            } else {
                printf("%4d ", 0);
            }
        }

        printf("\n");
    }
}

最后还是销毁 O(∩_∩)O哈哈~

void destoryTriple(TRIPLE **triple) {
    if(NULL == *triple) {
        return;
    }

    destoryTriadByRow(**triple);
    free((*triple)->row);
    free((*triple)->col);
    free(*triple);
}

void destoryTriadByRow(TRIPLE triple) {//按行进行销毁
    int i;

    for(i = 0; i < triple.maxRow; i++) {
        while(NULL != triple.row[i]) {
            TRIAD *tmp = triple.row[i];
            triple.row[i] = tmp->col;
            free(tmp);
        }
    }
}