对称矩阵的压缩储存讲解

一、存储矩阵用一个二维数组即可;

二、什么是对称矩阵:

设一个N*N的方阵A,A中任意元素Aij,当且仅当 Aij == Aji(0 <= i <= N-1&& 0 <= j <= N-1),则矩阵A是对称矩阵。以矩阵的对角线为分隔,分为上三角和下三角

三、对称矩阵的压缩储存:

压缩存储称矩阵存储时只需要存储上三角/下三角的数据,所以最多存储n(n+1)/2个数据(相当于1+2+…+n,即等差数列求和)。

对称矩阵和压缩存储的对应关系:下三角存储i>=j, SymmetricMatrix[i][j] ==Array[i*(i+1)/2+j]

四、代码实现

#include<iostream>
using namespace std;
template<class T>
class CompressionMatrix
{
public:
  CompressionMatrix(T* arr,int sz)
    :_data(new T[sz*(sz+1)/2])
    ,_size(sz)
  {
    int index=0;
    //压缩储存过程
    for(int i=0;i<sz;++i)
    {
      for(int j=0;j<sz;++j)
      {
        if (i>=j)//_data中储存下三角的数据
        {
          _data[index]=arr[i*sz+j];
          index++;
        }
        else
          break;
      }
    }
  }
  //获取某个坐标的数据,i和j代表该数据在矩阵中的横纵坐标
  T GetDate(int i,int j)
  {
    if (i>=j)//下三角数据
    {
      return _data[i*(i+1)/2+j];
    }
    else//上三角数据
    {
      std::swap(i,j);//将横坐标和从坐标值交换;
      return _data[i*(i+1)/2+j];
    }
  }
    //打印矩阵的数据
  void PrintfMatrix()
  {
    for (int i=0;i<_size;++i)
    {
      for (int j=0;j<_size;++j)
      {
        cout<<GetDate(i,j)<<" ";
      }
      cout<<endl;
    }
  }
  ~CompressionMatrix()
  {
    if (_data!=NULL)
    {
      delete[] _data;
      _data=NULL;
      _size=0;
    }
  }
protected:
  T* _data;//储存数据的数组
  int _size;//储存原始对称矩阵的行数(或列数)
};

测试代码:

int main()
{
  int a[5][5]=
  {
    {0,1,2,3,4},
    {1,0,1,2,3},
    {2,1,0,1,2},
    {3,2,1,0,1},
    {4,3,2,1,0},
  };
  CompressionMatrix<int> cm((int*)a,5);//将二维数组强制转换为一维数组指针,是问题更简单
  cm.PrintfMatrix();
  return 0;
}

五、运行结果

O(∩_∩)O

总结

以上就是这篇文章的全部内容了,希望本文的内容对大家的学习或者工作具有一定的参考学习价值,谢谢大家对我们的支持。如果你想了解更多相关内容请查看下面相关链接

时间: 2019-02-17

C++实践数组类运算的实现参考

[项目-数组类运算的实现] 设计数组类Array,为了实现测试函数中要求的功能,请补足相关的函数(构造.析构函数)和运算符重载的函数. 实现策略提示:可以将测试函数中的语句加上注释,取消一句的注释,增加相应的函数,以渐增地实现所有的功能,避免全盘考虑带来的困难. class Array { private: int* list; //用于存放动态分配的数组内存首地址 int size; //数组大小(元素个数) public: //成员函数声明 }; //要求测试函数能够运行出正确.合理的结果:

C++实践Time类中的运算符重载参考方法

[项目-Time类中的运算符重载] 实现Time类中的运算符重载. class CTime { private: unsigned short int hour; // 时 unsigned short int minute; // 分 unsigned short int second; // 秒 public: CTime(int h=0,int m=0,int s=0); void setTime(int h,int m,int s); void display(); //二目的比较运算符

C++实践数组作数据成员的参考

[项目 - 数组作数据成员]下面是设计好的一个工资类(Salary): class Salary { public: void set_salarys( );//输入职工工资(输入-1标志着工资输入结束),工资保存到salary数组中,实际人数保存到number中: void add_salarys(int x); //给每个人涨x元工资 void sort_salarys(); //对工资由大到小排序 void show_salarys( ); //显示工资信息 private: double

Dijkstra算法最短路径的C++实现与输出路径

某个源点到其余各顶点的最短路径 这个算法最开始心里怕怕的,不知道为什么,花了好长时间弄懂了,也写了一遍,又遇到时还是出错了,今天再次写它,心里没那么怕了,耐心研究,懂了之后会好开心的,哈哈 Dijkstra算法: 图G 如图:若要求从顶点1到其余各顶点的最短路径,该咋求: 迪杰斯特拉提出"按最短路径长度递增的次序"产生最短路径. 首先,在所有的这些最短路径中,长度最短的这条路径必定只有一条弧,且它的权值是从源点出发的所有弧上权的最小值,例如:在图G中,从源点1出发有3条弧,其中以弧(1

一张图总结C++中关于指针的那些事

指向对象的指针,指向数据成员的指针,指向成员函数的指针: 数组即指针,数组的指针,指针数组: 指向函数的指针,指向类的成员函数的指针,指针作为函数参数,指针函数: 指针的指针,指向数组的指针:常指针,指向常对象的指针: -- 大哥,这些都是什么鬼?! 用下面一张图全概括.用例子对照图示,有感觉,就用术语将概念大声地念出来,动员所有的感官参与,搞清楚这些,不是事. 图如下: 总结 以上就是这篇文章的全部内容了,希望本文的内容对大家的学习或者工作具有一定的参考学习价值,谢谢大家对我们的支持.如果你想

C++实践分数类中运算符重载的方法参考

[项目-分数类中的运算符重载] (1)实现分数类中的运算符重载,在分数类中可以完成分数的加减乘除(运算后再化简).比较(6种关系)的运算. class CFraction { private: int nume; // 分子 int deno; // 分母 public: //构造函数及运算符重载的函数声明 }; //重载函数的实现及用于测试的main()函数 (2)在(1)的基础上,实现分数类中的对象和整型数的四则运算.分数类中的对象可以和整型数进行四则运算,且运算符合交换律.例如:CFrac

C++稀疏矩阵的各种基本运算并实现加法乘法

代码: #include <iostream> #include<malloc.h> #include<cstdio> using namespace std; #define M 4 #define N 4 #define MaxSize 100 typedef int ElemType; typedef struct { int r; int c; ElemType d;///元素值 } TupNode; ///三元组定义 typedef struct { int

C++实践排序函数模板项目的参考方法

[项目-排序函数模板] 已知 void Sort(int a[],int size); void Sort(double a[],int size); 是一个函数模板的两个实例,其功能是将数组a中的前size个元素按从小到大顺序排列.试设计这个函数模板. 参考解答: #include<iostream> using namespace std; template<class T> void Sort(T set[],int n) { int i,j; T temp; for(i=1

C++实践IP地址类项目参考

[项目-IP地址类] 在互联网中使用的IP地址占4字节,可以用四段法表示,每段值的范围为0-255,中间用"."隔开,例如202.194.116.97.其实,也可以看看一个有4字节的无符号整型值3401741409. 现设计一个IP地址类,用于保存IP地址,并实施在IP地址上的一些操作.如下所示: class IP { private: union //由此匿名联合体可以看出,IP地址共占4个字节 { struct //这是一个由4个字节构成的匿名结构体 { unsigned char

C++项目求Fibonacci数列的参考解答

[项目:求Fibonacci数列] Fibonacci数列在计算科学.经济学等领域中广泛使用,其特点是:第一.二个数是1,从第3个数开始,每个数是其前两个数之和.据此,这个数列为:1 1 2 3 5 8 13 21 34 55 89 --,请设计程序,输出这个数列,直到这个数字超过10000. [提示]数列可以表示为: [参考解答] #include <iostream> using namespace std; int main( ) { int f1,f2,fn,n; f1=f2=1; n

c语言的cps实现求fibonacci数列示例

CPS:http://en.wikipedia.org/wiki/Continuation-passing_style示例代码使用迭代 + 尾递归. 复制代码 代码如下: #include <stdio.h> typedef void (*END_OF_END)(unsigned long);void fibonacci(int, unsigned long, unsigned long, void(*)(unsigned long)); voidnotify(unsigned long re

C语言求Fibonacci斐波那契数列通项问题的解法总结

一:递归实现   使用公式f[n]=f[n-1]+f[n-2],依次递归计算,递归结束条件是f[1]=1,f[2]=1. 二:数组实现   空间复杂度和时间复杂度都是0(n),效率一般,比递归来得快. 三:vector<int>实现   时间复杂度是0(n),时间复杂度是0(1),就是不知道vector的效率高不高,当然vector有自己的属性会占用资源. 四:queue<int>实现   当然队列比数组更适合实现斐波那契数列,时间复杂度和空间复杂度和vector<int&g

求斐波那契(Fibonacci)数列通项的七种实现方法

一:递归实现使用公式f[n]=f[n-1]+f[n-2],依次递归计算,递归结束条件是f[1]=1,f[2]=1.二:数组实现空间复杂度和时间复杂度都是0(n),效率一般,比递归来得快.三:vector<int>实现时间复杂度是0(n),时间复杂度是0(1),就是不知道vector的效率高不高,当然vector有自己的属性会占用资源.四:queue<int>实现当然队列比数组更适合实现斐波那契数列,时间复杂度和空间复杂度和vector<int>一样,但队列太适合这里了,

Python基于递归算法实现的汉诺塔与Fibonacci数列示例

本文实例讲述了Python基于递归算法实现的汉诺塔与Fibonacci数列.分享给大家供大家参考,具体如下: 这里我们通过2个例子,学习python中递归的使用. 1. 找出Fibonacci数列中,下标为 n 的数(下标从0计数) Fibonacci数列的形式是这样的:0,1,1,2,3,5,8,13-- ① 使用while循环,python2代码如下: def fib(n): a,b=0,1 count=0 while count<n: a,b=b,a+b count=count+1 pri

Go语言实现Fibonacci数列的方法

本文实例讲述了Go语言实现Fibonacci数列的方法.分享给大家供大家参考.具体如下: Fibonacci数列:1,1,2,3,5,8,13,21,,, (即从第三项起,每一项的值都等于前两项之后) 第一种,使用递归: 复制代码 代码如下: func fibonacci(a int) int {      if a == 1 || a == 2 {          return 1      }      return fibonacci(a-1) + fibonacci(a-2)  } 第

Java基于高精度整型实现fibonacci数列的方法

本文以实例形式讲述了Java基于高精度整型实现fibonacci数列的方法,分享给大家供大家参考之用.具体方法如下: package com.java.learning.recursion; import java.math.*; public class MainClass { public static void main(String args[]){ for(int i = 0; i < 100; i++){ f(i+1); } } public static BigInteger f(

C语言项目小学生数学考试系统参考

[项目3-小学生数学考试系统] 1.做一个小学生考试系统,功能包括: (1)利用随机数出10道加法题: (2)小学生用户答题给出每道题的答案: (3)对小学生的答题进行评判: (4)计算出小学生答题正确率. 2. 进一步改进,提高题目质量. 要求(1)百以内算术:运算数.结果都在100以内! (2)先随机产生运算符后,针对各个运算产生运算数保证下列要求:对加法,两数之和保证不大于100:对减法,被减数大于减数,且被减数不大于100:对乘法:两数之积不超过100:对除法:被除数大于除数,且被除数不

C语言实现Fibonacci数列递归

/* 问题描述 Fibonacci数列的递推公式为:Fn=Fn-1+Fn-2,其中F1=F2=1. 当n比较大时,Fn也非常大,现在我们想知道,Fn除以10007的余数是多少. */ #include<stdio.h> #include<stdlib.h> int N=10007; /*计算Fibonacci函数*/ int Fibonacci (int n) { int Fn; if (n==1 || n==2) { Fn=1; } else { Fn = (Fibonacci(

C语言项目全正整数后再计算的三种参考解答方法

[项目-全正整数后再计算] 输入3个正整数,其中任一数不是正整数,程序输出Invalid number!,然后结束运行.当第1个数为奇数时,计算后两数之和,当第1个数为偶数时,计算第2数减去第3数的差.无论哪种情形,当结果超过10时按如下示例输出,否则什么也不输出. 示例 1: Enter number 1: 2 Enter number 2: -7 Invalid number! 示例2: Enter number 1: 17 Enter number 2: 3 Enter number 3: