Циклический список
Циклический список организован в соответствии с принятым принципом совмещения заголовка списка и его элементов в объектах одного класса. Первый элемент списка - текущий объект, доступный через this , является заголовком и не содержит данных. Остальные элементы - динамические, создаются при помещении в список новых данных и удаляются при их исключении.
class zlist
{
void *data;
zlist *next,*prev;
zlist *find(int); // Вспомогательный метод извлечения
public: // элемента списка по номеру
zlist(); // Конструктор пустого списка
~zlist(); //
int size(); // Количество элементов
void *operator[](int); // Извлечение
void operator()(void*,int); // Включение по номеру
void *remove(int); // Удаление по номеру
void *remove(void*); // Удаление по указателю на элемент данных
void *min( int(*)(void*,void*)); // Итератор поиска минимального
};
Конструктор списка определяет текущий объект как единственный элемент, который в соответствии с правилами построения циклического списка "замкнут сам на себя".
zlist::zlist()
{ prev=next=this; }
На вспомогательном методе извлечения элемента списка по его последовательному номеру можно увидеть все особенности объектно-ориентированной реализации. Первый элемент списка-заголовок является текущим объектом ( this ), при этом в процессе "счета" он не учитывается. Цикл просмотра начинается с первого информационного элемента ( this->next или next ) и завершается по возвращении на заголовок. В последнем случае логический номер не найден.
zlist *zlist::find(int n=-1)
{ zlist *p;
for (p=next; n!=0 && p!=this; n--, p=p->next);
return p; }
Метод подсчета количества элементов в структуре данных стандартным образом обходит циклический список .
int zlist::size()
{ int n; zlist *p;
for (n=0, p=next; p!=this; n++, p=p->next);
return n; }
Метод получения указателя на элемент данных по логическому номеру - переопределенная операция [ ] . Получает указатель на элемент списка при помощи внутреннего метода find и выделяет из него данные .
void *zlist::operator[](int n=-1)
{
if (n==-1) n=size()-1;
zlist *p=find(n);
return p==this ? NULL : p->data; }
Метод исключения элемента данных из списка находит прежде всего элемент списка, извлекает из него указатель на элемент данных. Сам элемент списка при этом удаляется, поскольку он является динамическим объектом. Указатель на элемент данных возвращается, поскольку структура данных не несет ответственность за размещение самого элемента данных в памяти и не распределяет память под него.
void *zlist::remove(int n=-1)
{
if (n==-1) n=size()-1; // По умолчанию - удалить последний
zlist *p=find(n); // Найти элемент списка по номеру
if (p==this) return NULL; // Номер не существует - удалить нельзя
void *s=p->data; // Сохранить указатель на данные
p->prev->next=p->next; // "Обойти" элемент двусвязного списка
p->next->prev=p->prev;
p->next=p->prev=p; // Перед удалением - сделать его
delete p; // "единственным"
return s;} // Возвратить указатель на данные
Метод исключения по указателю на элемент данных используется, когда необходимо удалить известный уже элемент данных. Метод ищет заданный указатель и удаляет содержащий его элемент списка.
void *zlist::remove( void *pd)
{
zlist *p= next;
for (; p!=ph; p=p->next)
{
if (p->data==pd)
{
p->prev->next=p->next; // "Обойти" элемент двусвязного списка
p->next->prev=p->prev; //
p->next=p->prev=p; // Перед удалением - сделать его
delete p; // "единственным"
return pd; // Возвратить указатель на данные
}
}
return NULL; }
Метод включения элемента данных по логическом номеру, наоборот, создает динамический объект - элемент списка, после чего включает его в список. Таким образом, элементами списка являются динамические объекты, создаваемые методами, работающими с его заголовком.
void zlist::operator()(void *s,int n=-1)
{ // По умолчанию - включить перед заголовком,
zlist *p=find(n); // в циклическом списке - последним
zlist *q=new zlist; // Создать новый элемент списка
q->data=s;
q->next=p; // Включить перед найденным ( p)
q->prev=p->prev;
p->prev->next=q;
p->prev=q;
}
Метод поиска минимального элемента является типичным итератором (см.5.6.), реализующим стандартный алгоритм поиска минимума в списке.
void *zlist::min( int (*cmp)(void*,void*))
{
if (next==this) return NULL; // Пустой список
zlist *pmin=next;
for (zlist *q=next; q!=this; q=q->next)
{
if ( cmp(pmin->data,q->data) > 0) pmin=q;
}
return pmin->data;
}
Отдельного обсуждения заслуживает деструктор. Дело в том, что деструктор может вызываться в двух совершенно различных ситуациях :
- когда удаляется элемент списка (при выполнении операции remove ). В этой ситуации он всегда является единственным удаляемым ;
- когда в программе удаляется сам объект-список. В этом случае деструктор вызывается для объекта-заголовка. Но если список не будет пустым, то деструктор должен предпринять меры к удалению включенных в него элементов списка.
Вся проблема заключается в том, что деструктор сам не в состоянии определить, в какой из приведенных ситуаций он находится. Ниже приводится один из способов решения проблемы. Метод remove перед удалением динамического объекта-элемента списка делает его "единственным". Деструктор же, наоборот, удаляет при помощи метода remove элементы списка, следующие за текущим объектом, пока он не станет единственным. Заметим, что при этом деструктор освобождает только элементы списка но ничего не делает с указателями на элементы данных (это отдельная проблема).
zlist::~zlist()
{ while (remove(0)!= NULL); }
В заключение рассмотрим пример использования объектов класса в программе . Хранимые в списке данные-строки являются статическими объектами, поэтому проблемы распределения памяти под них здесь не актуальны.
int CMP(void *s1,void *s2) {return strcmp((char*)s1,(char*)s2); }
zlist A;
A((void*)"aaaa");
A((void*)"bbbb");
A((void*)"cccc");
for (i=A.size()-1; i>=0; i--) cout << (char*)A[i] << " ";
cout << (char*)A.min(CMP) << " ";
cout << (char*)A.remove(1);
