稀疏矩阵存储

C++ 三元组存储

//C++
#include <iostream>
using namespace std;

#define MAX 100
#define ERROR 0
#define OK 1
typedef int Status;  //函数结果状态类型

typedef struct {
    
	int row, col;  //三元组的行号、列号
	int item;  //三元组的值
} Triple;

//定义 TripleMatrix 类，每个 TripleMatrix 对象访问一个矩阵的信息
class TripleMatrix {
    
private:
	Triple data[MAX]; //非零元三元组
	int mu, nu, num;  //矩阵的行数、列数 和 非零元个数
public:
	TripleMatrix();
	TripleMatrix(int m, int n); //创建对象时，完成属性的初始化
	
	~TripleMatrix();

	Status setItem(int row, int col, int item);  //根据行号、列号 非零元，在尾部添加一个三元 元素
	int getItem(int row, int col); //根据行号 列号， 获得矩阵元素值
	void printMatrix(); //按照矩阵方式打印稀疏矩阵
	void printTriple();  //打印三元组数组
	friend bool matrixAdd(TripleMatrix a, TripleMatrix b, TripleMatrix& result);
	friend bool matrixMulty(TripleMatrix a, TripleMatrix b, TripleMatrix& result);
	
};

TripleMatrix::TripleMatrix() {
    
	//初始化矩阵的行数、列数 非零元个数
	mu = 0;
	nu = 0;
	num = 0;
}

TripleMatrix::TripleMatrix(int m, int n) {
    
	//初始化矩阵的行数、列数 非零元个数
	mu = m;
	nu = n;
	num = 0;
}

TripleMatrix::~TripleMatrix() {
    

}

/* 根据行号 列号 非零元 获得矩阵元素值*/
int TripleMatrix::getItem(int row, int col) {
    
	if (row > mu || col > nu)  //超出范围直接返回0
		return 0;
	for (int i = 0; i < num; i++) {
      //遍历三元组 num是非零的元素个数
		//如果发现行列号匹配的三元组，则返回非零元素值
		if (data[i].row == row && data[i].col == col) {
    
			return data[i].item;
		}
	}
	return 0;	
}

/* 这个成员函数往三元组中存入稀疏矩阵的一个元素 由于三元组是按行 列 由小到大排序的，因此需要先找到需要插入的位置 然后考虑元素后移，然后插入 */
Status TripleMatrix::setItem(int row, int col, int item) {
    
	if (row > mu || col > nu) //超过范围，返回ERROR
		return ERROR;
	//在三元组中存储一个非零元素
	if (num == MAX)  //已存元素个数num达到三元组可以存储的最大范围
		return ERROR;
	if (item == 0)  //输入的数组元素值为0，则什么也不做直接返回
		return OK;

	//利用while循环 先找到合适的存储位置
	int index = 0;
	while (index < num) {
    
		//如果要找到的row col 比已有三元组的行列值大，则继续往后移动
		if (row > data[index].row) {
    
			index++;
		}
		else if (row == data[index].row && (col > data[index].col)) {
    
			index++;
		}
		else {
    
			break;
		}
	}
		
	if ((row == data[index].row) && (col == data[index].col)) {
    
		//如果当前行 列号元素已经存在，则将新输入的数据替换三元组表中的item
		data[index].item = item;
	}
	else {
     //否则 插入新的元素
		//index 的后续元素都移动一个单元，腾出 index 的位置
		for (int i = num; i > index; i--) {
    
			data[i].row = data[i - 1].row;
			data[i].col = data[i - 1].col;
			data[i].item = data[i - 1].item;
		}

		//在index 位置存入新的元素
		data[index].row = row;
		data[index].col = col;
		data[index].item = item;

		//元素个数 num 加 1
		num++;
	}
	return OK;
}

/*打印稀疏矩阵*/
void TripleMatrix::printMatrix() {
    
	int tripleIndex = 0;  //triple用来控制三元组data数组的下标
	cout << "打印稀疏矩阵：" << endl;
	for (int i = 1; i <= mu; i++) {
    
		for (int j = 1; j <= nu; j++) {
    
			//如果发现行列号匹配的三元组，则输出非零元
			if (i == data[tripleIndex].row && j == data[tripleIndex].col) {
    
				cout << data[tripleIndex].item << "\t";
				tripleIndex++;
			}
			else {
      //否则，输出0
				cout << "0\t";
			}
		}
		cout << endl;
	}

	cout << "矩阵有 " << mu << " 行 " << nu << " 列，共 " << num << " 个非零元素" << endl;
	return;
}

/*打印三元组数组*/
void TripleMatrix::printTriple() {
    
	cout << "打印三元组数组：" << endl;
	cout << "row\tcol\titem" << endl;
	for (int i = 0; i < num; i++) {
    
		cout << data[i].row << "\t" << data[i].col << "\t" << data[i].item << endl;
	}
}


void inputMatrix(int m, int n, int num, TripleMatrix& triple) {
    
	int row, col, item;
	for (int i = 1; i <= num; i++) {
    
		cout << "请依次输入行，列 和非零元：";
		cin >> row >> col >> item;
		if (item != 0) {
    
			if (triple.setItem(row, col, item) == ERROR) {
    
				cout << "行号列号不正确，或者三元组数组满，不能正确存储！";
				break;
			}
		}
	}
}

bool matrixAdd(TripleMatrix a, TripleMatrix b, TripleMatrix& result) {
    
	if (a.mu != b.mu || b.mu != result.mu || a.nu != b.nu || b.nu != result.nu)  //行列不正确，矩阵不能相加
	{
    
		return false;
	}
	else {
    
		for (int i = 1; i <= a.mu; i++) {
    
			for (int j = 1; j <= a.nu; j++) {
    
				int item = a.getItem(i, j) + b.getItem(i, j);
				if (item != 0) {
    
					result.setItem(i, j, item);
				}
			}
		}
		return true;
	}

}

bool matrixMulty(TripleMatrix a, TripleMatrix b, TripleMatrix& result) {
    
	int i, j, k;

	//如果a 的列数 不等于 b 的行数，则返回false
	if (a.nu != b.mu) {
    
		return false;
	}

	//初始化result 的行列值
	result.mu = a.mu;
	result.nu = b.nu;

	//乘法计算
	for (int i = 1; i <= a.mu; i++) {
    
		for (int j = 1; j <= b.nu; j++) {
    
			int sum = 0;
			for (int k = 1; k <= a.nu; k++) {
    
				sum += a.getItem(i, k) * b.getItem(k, j);
			}
			//如果计算的值不为 0 则插入到稀疏矩阵中
			if (sum != 0) {
    
				result.setItem(i, j, sum);
			}
		}
	}
	return true;
}


/*三元组的测试代码*/
/* 3 4 4 1 1 2 3 4 1 1 1 3 2 2 -1 */

void tripleTest() {
    
	int m, n, num;
	cout << "请输入矩阵的行 列 非零元素个数：";
	cin >> m >> n >> num;
	TripleMatrix triple(m, n);
	inputMatrix(m, n, num, triple);
	triple.printMatrix();
	triple.printTriple();
}


//矩阵加法测试代码
void matrixAddTest() {
    
	int m, n, num;
	cout << "请输入第一个矩阵的行，列，非零元素个数";
	cin >> m >> n >> num;
	cout << "第一个矩阵：" << endl;
	TripleMatrix tripleA(m, n);
	inputMatrix(m, n, num, tripleA);
	tripleA.printMatrix();

	cout << "请输入第二个矩阵的行，列，非零元素个数";
	cin >> m >> n >> num;
	cout << "第二个矩阵：" << endl;
	TripleMatrix tripleB(m, n);
	inputMatrix(m, n, num, tripleB);
	tripleB.printMatrix();

	TripleMatrix tripleResult(m, n);
	if (matrixAdd(tripleA, tripleB, tripleResult)) {
    
		cout << endl << "矩阵相加后：" << endl;
		tripleResult.printMatrix();
	}
	else{
    
		cout << "矩阵不能相加" << endl;

	}
}


//矩阵乘法测试代码
void matrixMultyTest() {
    
	int m, n, num;
	cout << "请输入第一个矩阵的行，列，非零元素个数";
	cin >> m >> n >> num;
	cout << "第一个矩阵：" << endl;
	TripleMatrix tripleA(m, n);
	inputMatrix(m, n, num, tripleA);
	tripleA.printMatrix();

	cout << "请输入第二个矩阵的行，列，非零元素个数";
	cin >> m >> n >> num;
	cout << "第二个矩阵：" << endl;
	TripleMatrix tripleB(m, n);
	inputMatrix(m, n, num, tripleB);
	tripleB.printMatrix();

	TripleMatrix tripleResult;
	if (matrixMulty(tripleA, tripleB, tripleResult)) {
    
		cout << endl << "矩阵相乘后：" << endl;
		tripleResult.printMatrix();
	}
	else {
    
		cout << "矩阵不能相乘" << endl;

	}
}

int main() {
    
	//tripleTest();
	//matrixAddTest();
	matrixMultyTest();

	return 0;	
}

Java 例子

public class SparseMatrix {
    
    public static void main(String[] args) {
    
        //1.创建一个二维数组 11 * 11 0 没有棋子 1 黑子 2 白子
        int[][] array1 = new int[11][11];
        array1[1][2] = 1;
        array1[2][3] = 2;
        //输出原始数组
        System.out.println("输出原始的数组：");

        for (int[] ints : array1) {
    
            for (int anInt : ints) {
    
                System.out.print(anInt + "\t");
            }
            System.out.println();
        }

        System.out.println("==========================");
        //转换为稀疏数组保存
        //获取有效值的个数
        int sum = 0;
        for (int i = 0; i < 11; i++) {
    
            for (int j = 0; j < 11; j++) {
    
                if(array1[i][j] != 0)
                    sum++;
            }
        }
        System.out.println("有效值的个数：" + sum);

        //2.创建一个稀疏数组的数组
        int[][] array2 = new int[sum + 1][3];

        array2[0][0] = 11;
        array2[0][1] = 11;
        array2[0][2] = sum;

        //3.遍历矩阵
        int count = 0;
        for (int i = 0; i < array1.length; i++) {
    
            for (int j = 0; j < array1[0].length; j++) {
    
                if(array1[i][j] != 0){
    
                    count++;
                    array2[count][0] = i;
                    array2[count][1] = j;
                    array2[count][2] = array1[i][j];
                }
            }
        }

        //4.输出稀疏数组
        System.out.println("输出稀疏数组：");
        for (int i = 0; i < array2.length; i++) {
    
            System.out.println(array2[i][0] + "\t" + array2[i][1] + "\t" + array2[i][2]);
        }


        //还原矩阵
        System.out.println("==========================");
        System.out.println("还原矩阵");
        //1.读取稀疏数组
        int[][] array3 = new int[array2[0][0]][array2[0][1]];
        //2.给其中的元素还原它的值
        for (int i = 1; i < array2.length; i++) {
    
            array3[array2[i][0]][array2[i][1]] = array2[i][2];
        }
        //3.打印
        for (int[] ints : array3) {
    
            for (int anInt : ints) {
    
                System.out.print(anInt + "\t");
            }
            System.out.println();
        }
    }

}