This C++ Program demonstrates the implementation of Sparse Array.
Here is source code of the C++ Program to demonstrate the implementation of Sparse Array. The C++ program is successfully compiled and run on a Linux system. The program output is also shown below.
/*
* C++ Program to Implement Sparse Array
*/
#include <iostream>
#include <iomanip>
#include <string>
using namespace std;
/*
* Class List Declaration
*/
class List
{
private:
int index;
int value;
List *nextindex;
public:
List(int index)
{
this->index = index;
nextindex = NULL;
value = NULL;
}
List()
{
index = -1;
value = NULL;
nextindex = NULL;
}
void store(int index, int value)
{
List *current = this;
List *previous = NULL;
List *node = new List(index);
node->value = value;
while (current != NULL && current->index < index)
{
previous = current;
current = current->nextindex;
}
if (current == NULL)
{
previous->nextindex = node;
}
else
{
if (current->index == index)
{
cout<<"DUPLICATE INDEX"<<endl;
return;
}
previous->nextindex = node;
node->nextindex = current;
}
return;
}
int fetch(int index)
{
List *current = this;
int value = NULL;
while (current != NULL && current->index != index)
{
current = current->nextindex;
}
if (current != NULL)
{
value = current->value;
}
else
{
value = NULL;
}
return value;
}
int elementCount()
{
int elementCount = 0;
List *current = this->nextindex;
for ( ; (current != NULL); current = current->nextindex)
{
elementCount++;
}
return elementCount;
}
};
/*
* Class Sparse Array Declaration
*/
class SparseArray
{
private:
List *start;
int index;
public:
SparseArray(int index)
{
start = new List();
this->index = index;
}
void store(int index, int value)
{
if (index >= 0 && index < this->index)
{
if (value != NULL)
start->store(index, value);
}
else
{
cout<<"INDEX OUT OF BOUNDS"<<endl;
}
}
int fetch(int index)
{
if (index >= 0 && index < this->index)
return start->fetch(index);
else
{
cout<<"INDEX OUT OF BOUNDS"<<endl;
return NULL;
}
}
int elementCount()
{
return start->elementCount();
}
};
/*
* Main
*/
int main()
{
int iarray[5];
iarray[0] = 1;
iarray[1] = NULL;
iarray[2] = 2;
iarray[3] = NULL;
iarray[4] = NULL;
SparseArray sparseArray(5);
for (int i = 0; i < 5; i++)
{
sparseArray.store(i, iarray[i]);
}
cout<<"NORMAL ARRAY"<<endl;
for (int i = 0 ; i < 5; i++)
{
if (iarray[i] == NULL)
cout<<"NULL"<<"\t";
else
cout<<iarray[i] <<"\t";
}
cout<<"\nSPARSE ARRAY"<<endl;
for (int i = 0; i < 5; i++)
{
if (sparseArray.fetch(i) != NULL)
cout<<sparseArray.fetch(i) <<"\t";
}
cout<<"The Size of Sparse Array is "<<sparseArray.elementCount()<<endl;
}
$ g++ sparse_array.cpp $ a.out NORMAL ARRAY 1 NULL 2 NULL NULL SPARSE ARRAY 1 2 The Size of Sparse Array is 2 ------------------ (program exited with code: 1) Press return to continue
Sanfoundry Global Education & Learning Series – 1000 C++ Programs.
advertisement
advertisement
If you wish to look at all C++ Programming examples, go to C++ Programs.
Next Steps:
- Get Free Certificate of Merit in C++ Programming
- Participate in C++ Programming Certification Contest
- Become a Top Ranker in C++ Programming
- Take C++ Programming Tests
- Chapterwise Practice Tests: Chapter 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
- Chapterwise Mock Tests: Chapter 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
Related Posts:
- Apply for Computer Science Internship
- Practice Computer Science MCQs
- Buy C++ Books
- Apply for C++ Internship
- Apply for Information Technology Internship