稀疏数组和稀疏矩阵

Question

我需要一个程序的帮助，允许用户随机读访问阵列的任何条目。如果用户试图在有用区域之外进行读取，则您的数据结构应返回0。此外，它只允许用户对有用区域进行随机写访问。如果用户试图在数组中应该为0的部分中写入内容，则打印一条错误消息。此外，程序应该有构造函数，该构造函数只接受数组参数作为输入，并将所有数组初始化为0。第二个构造函数还应该接受一个int数组作为输入，将它的值复制到您正在创建的数组的有用部分。

这是数组的形式

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

我不确定如何创建稀疏数组，也不想使用现有的库。

我曾尝试创建一个使用重载操作符的动态数组，但我的问题是我甚至不知道什么是稀疏数组以及如何创建它。

#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;
}

Answer 1

有趣的是，我相信我们是在同一个班级。但是请注意，当您动态地将数组初始化为某个用户选择的大小(int N;)和全零时，您可能已经创建了稀疏数组。

由于您立即将所有N个元素填充为零，因此您已经开始了您的稀疏数组。在构造函数完成第一个任务后，您的析构函数会自动清除数组中的所有内存(如果您构建了一个析构函数的话)。因此，您有一个由N个元素插槽组成的数组，可以接收N个元素。然而，在此之前，所有N个元素插槽区域基本上是空的，因此不使用存储器。但是数组仍然存在，因此是稀疏数组。

Answer 2

我认为向量类加上一些if应该可以做你想要的一切，不需要重新创建它。您可以使用两个向量，一个用于存储元素，另一个用于存储元素的位置。

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;