对称矩阵
 
 
 
n阶矩阵中任意一个元素aij都有aij=aji，则为对称矩阵
 
 
只存储主对角线+下三角区（按行优先存储在一维数组中）
 
数组大小：(1+n)*n/2
 
 
三角矩阵
 
 
三对角矩阵
 
 
 
 
稀疏矩阵
 
 
三元表（行，列，值）
 
 
十字链表
 
 

#include <math.h>
#include <stdio.h>
#define M 3
#define N 3

// 对称矩阵的输入
void Symmetric_input(int **A, int n, int B[])
{
    int i, j, k = 0;

    // 将对称元素及对称轴上的元素存入数组B
    for (i = 0; i < n; i++)
        for (j = 0; j < i + 1; j++)
            B[k++] = *(*(A + i) + j);
}

// 对称矩阵的输出
void Symmetric_output(int B[], int length)
{
    int i, j, k = 0;
    int n = (sqrt(1 + 8 * length) - 1) / 2; //计算矩阵的阶数
    int A[n][n];

    // 恢复对称矩阵A
    for (i = 0; i < n; i++)
        for (j = 0; j < i + 1; j++)
            A[i][j] = A[j][i] = B[k++];

    // 输出对称矩阵
    for (i = 0; i < n; i++)
    {
        for (j = 0; j < n; j++)
            printf("%d ", A[i][j]);

        printf("\n");
    }
}

// 下三角矩阵的输入
void Lower_triangular_input(int **A, int n, int B[])
{
    int i, j, k = 1;

    B[0] = *((*A) + (n - 1)); //存储常量到数组B的第一个位置

    // 将下三角元素存入数组B
    for (i = 0; i < n; i++)
        for (j = 0; j < i + 1; j++)
            B[k++] = *(*(A + i) + j);
}

// 下三角矩阵的输出
void Lower_triangular_output(int B[], int length)
{
    int i, j, k;
    int n = (sqrt(1 + 8 * length) - 1) / 2; //计算矩阵的阶数

    for (k = 0; k < n; k++)
    {
        // 输出下三角元素
        for (i = 0; i < (k + 1); i++)
            printf("%d ", B[k * (k + 1) / 2 + i + 1]);

        // 输出常数
        for (j = 1; j < n - k; j++)
            printf("%d ", B[0]);

        printf("\n");
    }
}

// 上三角矩阵的输入
void Upper_triangular_input(int **A, int n, int B[])
{
    int i, j, k = 0;

    // 将上三角元素存入数组B
    for (i = 0; i < n; i++)
        for (j = i; j < n; j++)
            B[k++] = *(*(A + i) + j);

    B[k] = **(A + (n - 1)); //存储常量到数组B的最后一个位置
}

// 上三角矩阵的输出
void Upper_triangular_output(int B[], int length)
{
    int i, j, k;
    int n = (sqrt(1 + 8 * length) - 1) / 2; //计算矩阵的阶数

    for (k = 0; k < n; k++)
    {
        // 输出常数
        for (j = 0; j < k; j++)
            printf("%d ", B[length - 1]);

        // 输出上三角元素
        for (i = 0; i < n - k; i++)
            printf("%d ", B[k * (n + (n - k + 1)) / 2 + i]);

        printf("\n");
    }
}

// 输出数组
void echo(int *B, int length)
{
    for (int i = 0; i < length; i++)
        printf("%d,", B[i]);
    printf("\n");
}

int main(int argc, char const *argv[])
{
    int Symmetric[M][N] = {
        {1, 2, 3},
        {2, 1, 3},
        {3, 3, 1}};

    int Lower_triangular[M][N] = {
        {1, 0, 0},
        {2, 1, 0},
        {3, 3, 1}};

    int Upper_triangular[M][N] = {
        {1, 2, 3},
        {0, 1, 3},
        {0, 0, 1}};

    int *p[3];
    int length = N * (N + 1) / 2;

    int B[length];

    p[0] = Symmetric[0];
    p[1] = Symmetric[1];
    p[2] = Symmetric[2];

    Symmetric_input(p, N, B);
    printf("对称矩阵：\n");
    Symmetric_output(B, length);
    printf("\n压缩后：\n");
    echo(B, length);
    printf("\n");

    length = N * (N + 1) / 2 + 1;

    p[0] = Lower_triangular[0];
    p[1] = Lower_triangular[1];
    p[2] = Lower_triangular[2];
    Lower_triangular_input(p, N, B);
    printf("下三角矩阵：\n");
    Lower_triangular_output(B, length);
    printf("\n压缩后：\n");
    echo(B, length);
    printf("\n");

    p[0] = Upper_triangular[0];
    p[1] = Upper_triangular[1];
    p[2] = Upper_triangular[2];
    Upper_triangular_input(p, N, B);
    printf("上三角矩阵：\n");
    Upper_triangular_output(B, length);
    printf("\n压缩后：\n");
    echo(B, length);

    return 0;
}

对于N*N的矩阵A，对于任意i和j(N-1>i>=0 && N-1>j>=0)，如果Aij=Aji那么，就称矩阵A是对称矩阵。以矩阵对角线为分界线，矩阵A分为上三角和下三角。
 
如下图：
 
 
由对称矩阵的性质，存储对称矩阵时，只需要存储对称矩阵的上三角或下三角就可以了（压缩存储），最多存储N*(N+1)/2个数据。
 
对称矩阵和压缩存储的对应关系：下三角存储i>=j,  SymmetricMatrix[i][j] == Array[i*(i+1)/2+j]
 

 
 
步骤分析：
 
（1）存储
 
定义一个一维数组_a，开辟N*(N+1)/2个空间，遍历矩阵，若i>=j，说明元素在矩阵的下三角位置，按顺序存入_a；  若i<j，则不存储，继续遍历矩阵的下一个元素。
 
（2）访问矩阵元素
 
要访问压缩存储的矩阵元素，我们可以根据对称矩阵和压缩存储的对应关系： SymmetricMatrix[i][j] == Array[i*(i+1)/2+j]
 
来访问矩阵元素。
 

 
 
实现方法：
 

#pragma once

#include<iostream>
using namespace std;

template<class T>
class SymmetricMatrix
{
public:
	SymmetricMatrix(const T* a, size_t size, size_t n)//构造函数，压缩存储矩阵元素
	:_a(new T[n*(n + 1) / 2])//开辟空间，下三角元素一共有（n*(n + 1) / 2）个
	, _size(n*(n + 1) / 2)//设置一维数组大小
	, _n(n)//矩阵大小（维数）
	{
		int index = 0;
		for (size_t i = 0; i < n; i++)
		{
			for (size_t j = 0; j < n; j++)//遍历
			{
				if (i >= j)   //若为下三角元素
					_a[index++] = a[i*n + j];//存储
				else;         //若不是下三角元素
					break      //直接跳出循环（此步骤优化，若不是下三角元素，则该行剩余元素一定也不是下三角元素）
			}
		}
	}
	~SymmetricMatrix()//析构函数
	{
		if (_a)
			delete[] _a;
	}
	T& Access(int i,int j)//访问元素
	{
		if (i < j)
			swap(i, j);
		return _a[i*(i + 1) / 2 + j];//根据对称矩阵和压缩存储的对应关系访问元素
	}
	void display()//还原打印矩阵
	{
		for (size_t i = 0; i < _n; i++)
		{
			for (size_t j = 0; j < _n; j++)
			{
				if (i >= j)//若要打印下三角元素，则直接根据对称矩阵和压缩存储的对应关系访问元素，打印
					cout << _a[i*(i + 1) / 2 + j] << " ";
				else      //若打印上三角元素，则交换元素行列（根据对称矩阵性质），就可以看做该元素是下三角元素并打印
					cout << _a[j*(j + 1) / 2 + i] << " ";
			}
			cout << endl;
		}
	}
protected:
	T* _a;
	size_t _size;
	size_t _n;
};

 
 
测试代码：
 

#include "SymmetricMatrix.hpp"
void TestSymmetricMatrix()
{
	int a[4][4] = {
		{0,1,2,3},
		{1,0,3,4},
		{ 2, 3, 0, 5 },
		{ 3, 4, 5, 0 }
	};
	size_t size = sizeof(a) / sizeof(a[0][0]);
	SymmetricMatrix<int> matrix((int *)a, size, 4);
	matrix.display();
	cout << matrix.Access(2,3) << endl;
}
int main()
{
	TestSymmetricMatrix();
	getchar();
	return 0;
}

 
 
 
 

 

 
 

 
/*
上三角下三角对称矩阵

说明:
上三角矩阵是矩阵在对角线以下的元素均为0，即A ij = 0，i > j，例如：
1 2 3     4     5     
0 6 7     8     9
0 0 10     11     12
0 0 0     13     14
0 0 0     0     15
下三角矩阵是矩阵在对角线以上的元素均为0，即A ij = 0，i < j，例如：
1 0 0     0     0
2 6 0     0     0
3 7 10     0     0
4 8 11     13     0
5 9 12     14  15
对称矩阵是矩阵元素对称于对角线，例如：
1 2 3     4     5
2 6 8     8     9
3 7 10     11    12
4 8 11     13  14
5 9 12     14  15
上三角或下三角矩阵也有大部份的元素不储存值（为0），我们可以将它们使用一维阵列来储存以节省储存空间，而对称矩阵因为对
称于对角线，所以可以视为上三角或下三角矩阵来储存。

解法:
假设矩阵为nxn，为了计算方便，我们让阵列索引由1开始，上三角矩阵化为一维阵列，若以列为主，其公式为：
loc = n*(i-1) - i*(i-1)/2 + j化为以行为主，其公式为：loc = j*(j-1)/2 + i

下三角矩阵化为一维阵列，若以列为主，其公式为：loc = i*(i-1)/2 + j

若以行为主，其公式为：loc = n*(j-1) - j*(j-1)/2 + i
公式的导证其实是由等差级数公式得到，您可以自行绘图并看看就可以导证出来，对于C/C++或Java等索引由0开始的语言来说，只要
将i与j各加1，求得loc之后减1即可套用以上的公式
*/

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

#define N 5

int main(void){
    int arr1[N][N] = {
        {1,2,3,4,5},
        {0,6,7,8,9},
        {0,0,10,11,12},
        {0,0,0,13,14},
        {0,0,0,0,15}
    };
    int arr2[N*(1+N)/2] = {0};
    int i, j, loc = 0;
    
    printf("原二维矩阵: \n");
    for(i = 0; i < N; i++){
        for(j = 0; j < N; j++){
            printf("%4d", arr1[i][j]);
        }
        printf("\n");
    }
    
    printf("\n以列为主： ");
    for(i = 0; i < N; i++){
        for(j = 0; j < N; j++){
            if(arr1[i][j] != 0){
                arr2[loc++] = arr1[i][j];
            }
        }
    }
    for(i = 0; i < N*(1+N)/2; i++){
        printf("%d ", arr2[i]);
    }
    
    printf("\n输入索引(i, j): ");
    scanf("%d %d", &i, &j);
    loc = N * i - i * (i + 1) / 2 + j;
    printf("(%d, %d) = %d", i, j, arr2[loc]);
    printf("\n");
    
    return 0;
}

 
运行结果：