C++ Program to Implement Sparse Matrix

«
»
This C++ Program demonstrates the implementation of Sparse Matrix.

Here is source code of the C++ Program to demonstrate the implementation of Sparse Matrix. The C++ program is successfully compiled and run on a Linux system. The program output is also shown below.

  1. /*
  2.  * C++ Program to Implement Sparse Matrix
  3.  */
  4. #include <iostream>
  5. #include <iomanip>
  6. #include <string>
  7. using namespace std;  
  8.  
  9. /*
  10.  * Class List Declaration
  11.  */
  12. class List
  13. {
  14.     private: 
  15.         int index;
  16.         int value;
  17.         List *nextindex;
  18.     public: 
  19.         List(int index)
  20.         {
  21.             this->index = index;
  22.             nextindex = NULL;
  23.             value = NULL;
  24.         }
  25.         List()
  26.         {
  27.             index = -1;
  28.             value = NULL;
  29.             nextindex = NULL;
  30.         }
  31.         void store(int index, int value)
  32.         {
  33.             List *current = this;
  34.             List *previous = NULL;
  35.             List *node = new List(index);
  36.             node->value = value;
  37.             while (current != NULL && current->index < index)
  38.             {
  39.                 previous = current;
  40.                 current = current->nextindex;
  41.             }
  42.             if (current == NULL)
  43.             {
  44.                 previous->nextindex = node;
  45.             } 
  46.             else
  47.             {
  48.                 if (current->index == index)
  49.                 {
  50.                     cout<<"DUPLICATE INDEX"<<endl;
  51.                     return;
  52.                 }
  53.                 previous->nextindex = node;
  54.                 node->nextindex = current;
  55.             }
  56.             return;
  57.         }
  58.  
  59.         int fetch(int index)
  60.         {
  61.             List *current = this;
  62.             int value = NULL;
  63.             while (current != NULL && current->index != index)
  64.             {
  65.                 current = current->nextindex;
  66.             }
  67.             if (current != NULL)
  68.             {
  69.                 value = current->value;
  70.             } 
  71.             else
  72.             {
  73.                 value = NULL;
  74.             }
  75.             return value;
  76.         }
  77.  
  78.         int elementCount()
  79.         {
  80.             int elementCount = 0;
  81.             List *current = this->nextindex;
  82.             for ( ; (current != NULL); current = current->nextindex)
  83.             {
  84.                 elementCount++;
  85.             }
  86.             return elementCount;
  87.         }
  88. };
  89. /*
  90.  * Class SpareArray Declaration
  91.  */
  92. class SparseArray
  93. {
  94.     private:
  95.         List *start;
  96.         int index;
  97.     public:
  98.         SparseArray(int index)
  99.         {
  100.             start = new List();
  101.             this->index = index;
  102.         }
  103.         void store(int index, int value)
  104.         {
  105.             if (index >= 0 && index < this->index)
  106.             {
  107.                 if (value != NULL)
  108.                     start->store(index, value);
  109.             } 
  110.             else
  111.             {
  112.                 cout<<"INDEX OUT OF BOUNDS"<<endl;
  113.             }
  114.         }
  115.         int fetch(int index)
  116.         {
  117.             if (index >= 0 && index < this->index)
  118.                 return start->fetch(index);
  119.             else 
  120.             {
  121.                 cout<<"INDEX OUT OF BOUNDS"<<endl;
  122.                 return NULL;
  123.             }
  124.         }
  125.         int elementCount()
  126.         {
  127.             return start->elementCount();
  128.         }
  129. };
  130. /*
  131.  * Class SparseMatrix Declaration
  132.  */
  133. class SparseMatrix
  134. {
  135.     private:
  136.         int N;
  137.         SparseArray **sparsearray;
  138.     public: 
  139.         SparseMatrix(int N)
  140.         {
  141.             this->N = N;
  142.             sparsearray = new SparseArray* [N];
  143.             for (int index = 0; index < N; index++)
  144.             {
  145.                 sparsearray[index] = new SparseArray(N);
  146.             }
  147.         }
  148.         void store(int rowindex, int colindex, int value)
  149.         {
  150.             if (rowindex < 0 || rowindex > N)
  151.             {
  152.                 cout<<"row index out of bounds"<<endl;
  153.                 return;
  154.             }
  155.             if (colindex < 0 || colindex > N)
  156.             {
  157.                 cout<<"col index out of bounds"<<endl;
  158.                 return;
  159.             }
  160.             sparsearray[rowindex]->store(colindex, value);
  161.         }
  162.  
  163.         int get(int rowindex, int colindex)
  164.         {
  165.             if (rowindex < 0 || colindex > N)
  166.             {
  167.                 cout<<"row index out of bounds"<<endl;
  168.                 return 0;
  169.             }
  170.             if (rowindex < 0 || colindex > N)
  171.             {
  172.                 cout<<"col index out of bounds"<<endl;
  173.                 return 0;
  174.             }
  175.             return (sparsearray[rowindex]->fetch(colindex));
  176.         }
  177.         int elementCount()
  178.         {
  179.             int count = 0;
  180.             for (int index = 0; index < N; index++)
  181.             {
  182.                 count += sparsearray[index]->elementCount();
  183.             }
  184.             return count;
  185.         }
  186. };
  187. /*
  188.  * Main
  189.  */
  190. int main()
  191. {
  192.     int iarray[3][3];
  193.     iarray[0][0] = 1;
  194.     iarray[0][1] = NULL;
  195.     iarray[0][2] = 2;
  196.     iarray[1][0] = NULL;
  197.     iarray[1][1] = 3;
  198.     iarray[1][2] = NULL;
  199.     iarray[2][0] = 4;
  200.     iarray[2][1] = 6;
  201.     iarray[2][2] = NULL;
  202.     SparseMatrix sparseMatrix(3);
  203.     for (int rowindex = 0; rowindex < 3; rowindex++)
  204.     {
  205.         for (int colindex = 0; colindex < 3; colindex++)
  206.         {
  207.             sparseMatrix.store(rowindex, colindex, iarray[rowindex][colindex]);
  208.         }
  209.     }
  210.  
  211.     cout<<"the sparse Matrix is: "<<endl;
  212.     for (int rowindex = 0; rowindex < 3; rowindex++)
  213.     {
  214.         for (int colindex = 0; colindex < 3; colindex++)
  215.         {
  216.             if (sparseMatrix.get(rowindex, colindex) == NULL)
  217.                 cout<<"NULL"<< "\t";
  218.             else
  219.                 cout<<sparseMatrix.get(rowindex, colindex) << "\t";
  220.         }
  221.         cout<<endl;
  222.     }
  223.     cout<<"The Size of Sparse Matrix is "<<sparseMatrix.elementCount()<<endl;
  224.  
  225. }

advertisement
$ g++ sparse_matrix.cpp
$ a.out
 
the sparse Matrix is:
1       NULL    2
NULL    3       NULL
4       6       NULL
The Size of Sparse Matrix is 5
 
 
------------------
(program exited with code: 1)
Press return to continue

Sanfoundry Global Education & Learning Series – 1000 C++ Programs.

advertisement
If you wish to look at all C++ Programming examples, go to C++ Programs.

advertisement
advertisement
advertisement
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He is Linux Kernel Developer & SAN Architect and is passionate about competency developments in these areas. He lives in Bangalore and delivers focused training sessions to IT professionals in Linux Kernel, Linux Debugging, Linux Device Drivers, Linux Networking, Linux Storage, Advanced C Programming, SAN Storage Technologies, SCSI Internals & Storage Protocols such as iSCSI & Fiber Channel. Stay connected with him @ LinkedIn