Лабораторная работа №8

Тема: “Разреженные массивы”

Пример: Класс, описывающий разреженный массив

Разреженным называется массив, в котором не все элементы фактически используются, при этом размер массива очень большой, возможно даже превышает размер доступной памяти. Разреженные массивы можно реализовать различными способами. Одним из наиболее простых методов реализации разреженным массивов является использование связного списка. Узлы списка содержат индекс и значение элемента. Индексация осуществляется путем последовательного поиска узла, содержащего заданный индекс.

// Параметризованный класс разреженного массива,

// реализованный на основе связного списка:

#include <iostream>

#include <conio.h>

#include <windows.h>

#include <assert.h>

using namespace std;

// Класс, определяющий один элемент, хранящийся в разреженном массиве:

template <class Type> class SparseList;

template <class Type> class SparseOb

{

friend class SparseList<Type>;

// Обратите внимание на то, что класс SparseList предварительно объявлен

long index; // индекс элемента массива

SparseOb<Type> *next; // указатель на следующий узел

SparseOb<Type> *prior; // указатель на предыдущий объект

SparseOb() { info = 0; index = -1; next = prior = NULL;}

// конструктор

public:

Type info; // элемент данных

};

// Класс списка:

template <class Type>

class SparseList

{

SparseOb<Type> *start, *end; // указатели на начало и конец списка

public:

SparseList() {start = end = NULL;}

~SparseList();

SparseOb<Type> * store(long ix, Type c); // добавление элемента

void remove(long ix); // удаление элемента

// возвращение указателя на элемент по заданному индексу:

SparseOb<Type> * find(long ix);

};

// Параметризованный класс разреженного массива:

template <class Type>

class SparseArray: public SparseList<Type>

{

long length; // размер массива

public:

SparseArray(long size = 0) : length(size) {} // конструктор

Type& operator [](long i); // операция [ ]

};

// Определение функций:

// Деструктор:

template <class Type> SparseList<Type>::

~SparseList()

{

SparseOb<Type>* p, *p1 ;

// удаление всех элементов списка:

p = start;

while (p)

{

p1 = p->next;

delete p;

p = p1;

}

}

// Добавление элемента в список:

template <class Type> SparseOb<Type> * SparseList<Type>::

store (long ix, Type c)

{

SparseOb<Type> *p = new SparseOb<Type>;

assert(p); // проверяем, выделена ли память

p->info = c;

p->index = ix;

if (start == NULL) start = end = p;

// если добавляется первый элемент списка

else // добавление элемента в конец списка

{

p->prior = end; end->next = p; end = p;

}

return p;

}

// нахождение элемента массива по индексу:

template <class Type> SparseOb<Type> * SparseList<Type>::

find(long ix)

{

SparseOb<Type> *temp;

temp = start;

while(temp)

{

if (ix == temp->index) return temp;

// если найдено вхождение элемента, возвращается указатель на него

temp = temp->next;

}

return NULL; // если нет в списке

}

/* Удаление из списка элемента с указанным индексом и

обновление указателей на начало и конец списка: */

template <class Type> void SparseList<Type>::

remove(long ix)

{

SparseOb<Type> *ob = find(ix); // получаем указатель на элемент

if (!ob) return; // если элемент не существует

if (ob->prior) // если удаляется не первый элемент

{

ob->prior->next = ob->next;

if (ob->next) // если удаляется не последний элемент

ob->next->prior = ob->prior;

else // последний

end = ob->prior;

delete ob;

}

else // удаляется первый

if (ob->next) // если элемент - не единственный

{

ob->next->prior = NULL;

start = ob->next;

delete ob;

}

else start = end = NULL; // теперь список пуст

}

// Индексация в массиве:

template <class Type> Type& SparseArray<Type>::

operator [] (long ix)

{

if (ix<0 || ix > length-1)

{

cout<<"Индекс выходит за пределы области определения\n\n\n";

exit(1);

}

SparseOb<Type> * p;

p = find(ix); // получаем указатель на элемент

if (!p) // эсли это новый элемент

{

p = store(ix, 0); // добавляем его в массив со значением 0

}

return p->info;

/* функция возвращает ссылку на эту ячейку, поэтому значение элемента можно изменять */

}

// пример использования разреженного массива:

int main()

{

//Настройки шрифтов и региональных стандартов:

if(SetConsoleCP(1251)==0)

//проверка правильности установки кодировки символов для ввода

{

cerr<<"Fialed to set codepage!"<<endl;

/* если не удалось установить кодовую страницу, вывод сообщения об ошибке */

}

if(SetConsoleOutputCP(1251)==0)//тоже самое для вывода

{

cerr<<"Failed to set OUTPUT page!"<<endl;

}

SparseArray <int> iob(100000); // Объявляем массив целых чисел

// поместим в массив некоторые значения:

for (int i=0; i<5; i++)

iob[i] = i+1;

iob[2] = iob[3];

iob[1000] = 9345;

iob[2000] = iob[1000]+100;

// выведем значения элементов на экран:

cout << "Значения элементов массива:\n";

for (int i=0; i<5; i++) cout << iob[i] << " ";

cout <<iob[1000] << " " << iob[2000] << endl;

cout << "Удалили элемент с номером 0: ";

iob.remove(0);

for (int i=0; i<5; i++) cout << iob[i] << " ";

cout << endl;

// попробуем обратиться к элементу, которому не присваивалось значение:

cout << "Неприсвоенное значение: " << iob[3000] << " " << endl;

// попробуем обратиться к элементу с недопустимым номером:

cout << iob[100001]<< endl;

cout << endl;

_getch();

return 0;

}