2020-04-07
99
5.6.1. Класс связного списка целочисленных значений List.
//-------------------------------------------------------------------------------------------
// объявление интерфейса класса List
class List
{
public:
void Add(int number); // добавление нового элемента в список
void Delete(); // удаление последнего элемента списка
// вставка нового элемента в список по заданному индексу
void Insert(int index, int value);
// удаление из списка элемента с заданным индексом
int Delete(int index);
// возвращение значения элемента списка с заданным индексом
int GetValue(int index);
int Count(); // возвращение количества элементов списка
void CopyList(List &list); // копирование элементов
//списка-параметра
List();// конструктор по умолчанию
List(List &Object); // конструктор копирования
~List(); // деструктор
// перегрузка оператора присваивания
List &List::operator =(List &list);
// перегрузка оператора индексирования
int& List::operator [](int number);
private:
class ListElement; // объявление класса "элемент списка"
// удаление заданного элемента списка
void _deleteElement(ListElement *deletedElement);
// возвращение указателя на элемент списка по индексу
ListElement * _getElement (int index);
ListElement* _first; // указатель на первый элемент списка
ListElement* _last; // указатель на последний элемент списка
};
//-------------------------------------------------------------------------------------------
// описание класса ListElement ("элемент списка")
class List::ListElement
{
public:
int _value;
ListElement *_next; // указатель на следующий элемент списка
ListElement *_prev; // указатель на предыдущий элемент списка
ListElement()
{
_next = NULL;
_prev = NULL;
_value = 0;
}
ListElement(int value)
{
_next = NULL;
_prev = NULL;
_value = value;
}
};
//-------------------------------------------------------------------------------------------
// реализация методов класса List
List::List() // конструктор по умолчанию создает пустой список
{
_first=NULL;
_last=NULL;
};
List::List(List & list) // конструктор копирования
{
this->_first = NULL;
this->_last = NULL;
// копирование элементов списка-параметра в текущий объект
this->CopyList(list);
}
// деструктор - освождение памяти, занимаемой элементами списка
List::~List()
{
// во временной переменной запоминается
// указатель на последний элемент списка
ListElement *currentElement = _last;
// цикл выполняется до тех пор, пока он не станет пустым
// (пока существует указатель на его последний элемент)
while(currentElement!= NULL)
{
// во временной переменной запоминается
// указатель на предпоследний элемент
currentElement = _last->_prev;
// освобождение памяти, занимаемой последним элементом
delete _last;
// предпоследний элемент становится последним
_last = currentElement;
}
_first = NULL;
_last = NULL;
}
// копирование элементов списка-параметра в текущий список
void List::CopyList(List &list)
{
// явный вызов деструктора для текущего объекта;
// при вызове метода CopyList в конструкторе копирования
// деструктор вызывается для только что созданного списка,
// который еще не содержит ни одного элемента,
// соответственно необходимости для вызова деструктора нет;
// однако при вызове метода CopyList при перегрузке
// оператора присваивания, нельзя однозначно предугадать,
// будет ли текущий список пустым, если нет -
// необходимо удалить все его элементы (освободить память),
// иначе возникнет ситуация потерянной ссылки;
this->~List();
// при помощи метода Add в текущий список добавляются
// значения элементов списка-параметра list,
// которые считываются при помощи метода GetValue(i)
// последовательно, начиная с первого элемента,
// (индексация элементов списка начинается с нуля)
for (int i = 0; i < list.Count(); i++)
this->Add(list.GetValue(i));
}
// возвращает значение элемента, индекс которого
// соответствует параметру index
int List::GetValue(int index)
{
// в локальной переменной запоминается указатель на элемент,
// индекс которого соответствует параметру index
ListElement *element = _getElement(index);
// если в списке не существует элемента с заданным индексом,
// метод возвращает нулевое значение
if (!element) return -1;
// иначе возвращается значение элемента с заданным индексом
return element -> _value;
}
// возвращает указатель на элемент, индекс которого
// соответствует параметру index
List::ListElement* List::_getElement(int index)
{
ListElement* element = _first;
for(int i = 1; i <= index; i++)
{
element = element->_next;
if (!element) return NULL;
}
return element;
}
//-------------------------------------------------------------------------------------------
// перегруженный оператор присваивания копирует
// значения объекта-параметра в текущий объект,
// а также возвращает ссылку на текущий объект.
List &List::operator =(List &list)
// параметр в операторе присваивания
// передается по ссылке, чтобы
// не создавать памяти его локальную копию
// (конструктор копирования не вызывается);
// данное решение экономит память
{
// копирование элементов списка-параметра в текущий объект
this->CopyList(list);
return *this; // разъименование указателя на текущий объект
// возвращается ссылка на текущий объект
} // так как объект-параметр передается по ссылке,
// деструктор для локального параметра не вызывается
//-------------------------------------------------------------------------------------------
// перегруженный оператор индексирования возвращает ссылку
// на поле, хранящее значение элемента списка с заданным индексом
// его можно использовать как справа от оператора присваивания,
// чтобы считывать значение по заданному индексу,
// так и слева от оператора присваивания
// для изменения значения по заданному индексу.
int& List::operator [](int index)
{
return _getElement(index) -> _value;
.// специфика оператора индекирования такова, что он
.// в обязательном порядке должен возвращать
.// корректную ссылку; если элемента по заданному индексу
.// не существует, то оператор индексирования завершит свою.// работу с ошибкой – выполнение программы прервется.
.// изменить сигнатуру пегружаемого оператора,
.// чтобы ввести, например, флаг ошибки или
.// изменить тип возвращаемого значения, невозможно.
}
//-------------------------------------------------------------------------------------------
// добавление элемента в список
void List::Add(int value)
{
ListElement *newElement = new ListElement(value);
if(!_first) // если список не содержит ни одного элемента
{
_first = newElement;
_last = newElement;
}
_last->_next = newElement;
newElement->_prev = _last;
newElement->_next = NULL;
_last = newElement;
_first->_prev = NULL;
}
//-------------------------------------------------------------------------------------------
// вставка нового элемента в список по заданному индексу
void List::Insert(int index,int value)
{
ListElement *element, *prev, *next;
element = _getElement(index);
if (element)
{
next = element;
prev = element->_prev;
element = new ListElement(value);
element->_prev = prev;
element->_next = next;
if(prev) prev->_next= element;
else _first = element;
if(next) next-> _prev = element;
else _last = element;
}
}
//-------------------------------------------------------------------------------------------
// удаление элемента из списка
void List::_deleteElement(ListElement *deletedElement)
{
ListElement *prev;
ListElement *next;
prev = deletedElement->_prev;
next = deletedElement->_next;
if(prev) prev->_next = next;
else _first = deletedElement->_next;
if(next) next->_prev = prev;
else _last = deletedElement->_prev;
delete deletedElement;
};
void List::Delete()
{
ListElement *last;
last = _last;
_last = _last->_prev;
_last->_next = NULL;
delete last;
};
int List::Delete(int index)
{
ListElement *deletedElement;
deletedElement = _getElement(index);
if (!deletedElement) return -1;
_deleteElement(deletedElement);
return 1;
};
int List::Count()
{
int count = 0; ListElement *currentElement = _first;
while(currentElement)
{ count++; currentElement = currentElement -> _next; }
return count;
}
//-------------------------------------------------------------------------------------------
Внешние функции обработки связного списка: ввод и вывод на консоль
List InputList()
{
List list; int number;
cout<<"Введите 5 элементов списка - целые значения: "<<endl;
for (int i=0; i < 5; i++)
{ cin>>number; list.Add(number); }
return list;
}
void PrintList(List list)
{
for(int i = 0; i < list.Count(); i++) cout << list.GetValue(i) << " ";
cout<<endl;
}
