0

I need help with a program which allows the user random read access to any entry of the array. If the user attempts to read outside the useful region, your data structure should return a 0. Also It allows the user random write access to the useful region only. In case the user tries to write something in the part of the array that is supposed to be 0, print an error message. in addition the program should have constructor that take the array parameters as input only and initialize all of the array to 0. The second constructor should additionally take as input an array of ints copy its values to the useful part of the array you are making.

This is the form of the array

[ 0 0 0 0 ... 0 0 1 2 3 4 5 0 0 .... 0 0 ] 

I am not sure how to create Sparse Array, also I don't want to use existing libraries.

I have tried creating a dynamic array, which uses Overload operator, but my problem is that I don't even know what is Sparse Array and how to create it.

#include <iostream>

using namespace std;

class MyArray
{
    friend ostream& operator<< (ostream &os, MyArray &array);

    public:
        MyArray (int size);
        MyArray (const MyArray &rhs);
        ~MyArray ();

        MyArray& operator= (const MyArray& rhs);
        int& operator[] (int index);
        int read_element (int index);
        void write_element (int index, int value);

    private:
        int *storage;
        int size;
};

#include "sparse_array_1d.h"

MyArray::MyArray (int size)
{
    storage = new int[size];
    this->size = size;
}

MyArray::MyArray (const MyArray &rhs)
{
    size = rhs.size;
    storage = new int[size];
    (*this) = rhs;
}

MyArray::~MyArray ()
{
    delete [] storage;
}

int MyArray::read_element (int index)
{
    return storage[index]; 
}

void MyArray::write_element (int index, int value)
{
    storage[index] = value;
}

MyArray& MyArray::operator= (const MyArray &rhs)
{
    int i,min_size;

    if (size < rhs.size)
        min_size = size;
    else
        min_size = rhs.size;

    for (i=0; i<min_size; i++)
        storage[i] = rhs.storage[i];

    return (*this);
}

int& MyArray::operator[] (int index)
{
    if (index < size && index >=0)
        return storage[index];

    return storage[0]; 
}

ostream& operator<< (ostream &os, MyArray &array)
{
    int i;

    os << "[ ";

    for (i=0; i<array.size; i++)
        os << array[i] << " ";

    os << "]" << endl;
    return os;
}

#include <iostream>
#include "sparse_array_1d.h"

using namespace std;

int main()
{
    int i,size;

    cout << "What array sizes would you like?" << endl;
    cin >> size;

    MyArray p1 (size);

    //int q=1;
    for (i=0; i<size; i++)
    {
        p1[i] = 0;
        //q++;
    }

    cout << "p1: " << endl;
    cout << p1;

    int x;

    cout << endl;
    cout << "enter numbers : " << endl;

    for (i=0 ; i<size; i++)
    {   
        cin >> p1[i];
    }

    cout << "This is the array" << endl;
    cout << p1;
    cout << endl;

    return 0;
}
9
  • 1
    What is your specific question? Feb 25, 2012 at 21:33
  • i just don't know how to initialize all of the array to 0. also i don't really understand how the Sparse Array works
    – toky
    Feb 25, 2012 at 21:37
  • Is this homework? From reading your question it appears to be? If it is, then please tag your question accordingly, and update it with the following information. What did you try? How did it fail? What did you expect? Feb 25, 2012 at 21:48
  • "what is Sparse Array" An array that allocates memory only for non-zero elements. Or for chunks of array that contain at least one non-zero element. When you "don't know what is it", google it.
    – SigTerm
    Feb 25, 2012 at 23:04
  • 1
    @toky: "i initialize all of the array to 0". Nope, that isn't it. Let's say you have array of 100000 elements, all of them are set zero except one. Ideal sparse array will allocate memory only for that single non-zero element.
    – SigTerm
    Feb 26, 2012 at 1:13

2 Answers 2

0

Funnily enough, I believe we are in the same class. But listen, you already probably created the sparse array when you dynamically initialized the array to some user chosen size (int N;) and all zeros.

Since you immediately filled all N elements as zero you have started your sparse array. After the first is done by your constructor your destructor automatically (well if you built one) clears all memory from the array. So you have an array of N element slots ready to receive N elements. However, until then all N element slots area basically empty and therefore use no memory. But the array still exists, hence your sparse array.

1
  • Entries that are set to zero still take memory. The memory consumed by the array is defined by how much memory you allocated in the new statement. The key idea behind a proper sparse-array implementation would be to only allocate memory for elements that are non-zero.
    – jogojapan
    Mar 2, 2012 at 4:17
-2

i think the vector class plus some if should do everything you want, no need to recreate it. You can use two vectors, one to store the elements and one to store their position.

vector<int> values,positions;
int c,success;

cout<<"Insert element"<<endl;
cin>>c;
positions.push_back(c);
cout<<"Insert value"<<endl;
cin>>c;
values.push_back(c);

cout<<"Which element you want to read?"<<endl;
cin>>c;
success=0;
for(int i=0;i<values.size();;i++){
if(positions[i]==c){
cout<<values[i]<<endl;
success=1;
}
if(success==0)
cout<<"Out of bounds: 0"<<endl;

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.