4.4. параметризованный связный список
Связным списком называется последовательность элементов данных, связанных ссылками. Связные списки могут иметь одиночные или двойные связи. В списке с одиночными связями каждый элемент содержит ссылку на следующий элемент данных. В списке с двойными связями каждый элемент содержит ссылки на предшествующий и последующий элементы. Хотя списки с одиночными связями встречаются достаточно часто, но списки с двойными связями распространены наиболее широко. Основную роль в этом играют следующие три фактора:
список с двойными связями можно читать в обоих направлениях: и от начала к концу, и от конца к началу. Список с одиночными связями можно читать только в одном направлении; поврежденный список с двойными связями проще перестраивать, так как с каждым из членов списка ассоциированы две ссылки; некоторые типы операций над списками (например, удаление) проще выполняются над списками с двойными связями.
Рассмотрим метод построения параметризованного списка с двойными связями. Список организовывается с помощью двух классов, первый из которых listob определяет природу элементов списка, а второй, dlist, реализует механизм списка с двойными связями. Первый из этих классов определяется следующим образом:
template <class DataT> class listob // класс элемента списка { public: DataT info; // информационная часть listob <DataT> *next; // указатель на следующий элемент listob <DataT> *prior; // указатель на предшествующий элемент listob() // конструктор { info = 0; next = prior = NULL; }; listob (DataT c) // конструктор { info = c; next = prior = NULL; }; listob <DataT> *getnext() { return next;} listob <DataT> *getprior() { return prior;} void getinfo (DataT& c) { c = info; } void change (DataT c) { info = c;} // изменение элемента friend ostream &operator << (ostream &stream, listob <DataT> o); friend ostream &operator << (ostream &stream, listob <DataT> *o); friend istream &operator >> (istream &stream, listob <DataT> &o); }; // перегрузка операции << для объекта listob template <class DataT> ostream &operator << (ostream &stream, listob <DataT> o) { stream << o.info << endl; return stream; } template <class DataT> ostream &operator << (ostream &stream, listob <DataT> *o) { stream << o -> info << endl; return stream; } // Перегрузка операции >> template <class DataT> istream &operator >> (istream &stream, listob <DataT> &o) { cout << “Введите информацию: ”; stream << o.info; return stream; }
Оператор << перегружается как для объектов типа listob, так и для указателей на объекты этого типа. Это связано с тем, что при использовании связных списков широко распространена практика получения доступа к элементам списка через указатель. Поэтому оператор << полезно перегружать, с тем, чтобы он мог оперировать с переданным ему указателем на объект. Механизм построения связного списка реализуется классом, приведенным ниже. Этот класс является производным от класса listob и оперирует с объектами класса listob.
template <class DataT> // параметризованный класс объекта списка class dlist: public listob<DataT> // класс списка - производный от класса узла
{ listob<DataT> *start, *end; // указатели на первый и последний элементы
public: dlist(){start=end=NULL;} // конструктор ~dlist(); // деструктор void store(DataT c); // запись в список void remove(listob<DataT> *ob); // удаление элемента void frwdlist(); // чтение в прямом направлении void bkwdlist(); // чтение в обратном направлении listob<DataT> *find(DataT c); // поиск listob<DataT> *getstart(){return start;} // начало поиска listob<DataT> *getend(){return end;} // указатель на конец списка }
Поскольку каждый узел списка содержит указатели на следующий и предшествующий узлы, то список является двухсвязным. Объектами класса dlist будут двухсвязные списки. Каждый объект этого класса содержит указатель на начало и указатель на конец списка. Оба эти указателя являются указателями на объекты класса listob. При создании списка оба указателя инициализируются значением NULL. Класс dlist поддерживает целый ряд операций над двухсвязными списками, в том числе: ввод нового элемента в список; удаление элемента из списка; просмотр списка в любом направлении (от начала к концу или от конца к началу); поиск элемента в списке; получение указателей на начало и на конец списка.
Разработаем подпрограммы, выполняющие эти операции и тестовую программу.
// dlist.cpp - parametrised class of the double connected list #include <conio.h> #include <iostream.h> #include <stdlib.h> template <class DataT> class listob; template <class DataT> ostream &operator << (operator &stream, listob<DataT> o) { stream<<o.info<<endl; // вывод объекта return stream; }
/* template <class DataT> ostream &operator<<(ostream &stream, listob<DataT> *o) { stream<<o->info<<endl; // вывод объекта по указателю return stream; }*/ /* template <class DataT> istream &operator>>(istream &stream, listob<DataT> &o) { cout<<"Input data: "; stream>>o.info; // ввод объекта return stream; } */
template <class DataT> class listob // класс узла { public: DataT info; // информационная часть Listob<DataT> *next, // указатель на следующий элемент *prior; // указатель на предшествующий элемент listob() { info=0; next = NULL; prior=NULL; // конструктор } listob(DataT c) { info=c; next=NULL; prior=NULL; // конструктор } listob<DataT> *getnext(){return next;} // чтение адреса следующего элемента
listob<DataT> *getprior(){return prior;} //чтение адреса предшествующего элемента
void getinfo(DataT &c){c=info;} // чтение информации в аргумент void change(DataT c){info=c;} // изменение информации
friend ostream &operator<<(ostream &stream, listob<DataT> o); // дружественные функции //friend ostream &operator<<(ostream &stream, listob<DataT> *o); // ввода - вывода //friend istream &operator>>(istream &stream, listob<DataT> &o); };
template <class DataT> // параметризованный класс объекта списка class dlist: public listob<DataT> // класс списка - производный от класса узла
{ listob<DataT> *start, *end; // указатели на первый и последний элементы
public: dlist(){start=end=NULL;} // конструктор ~dlist(); // деструктор void store(DataT c); // запись в список void remove(listob<DataT> *ob); // удаление элемента void frwdlist(); // чтение в прямом направлении void bkwdlist(); // чтение в обратном направлении listob<DataT> *find(DataT c); // поиск listob<DataT> *getstart(){return start;} // начало поиска listob<DataT> *getend(){return end;} // указатель на конец списка } template <class DataT> dlist<DataT>::~dlist { listob<DataT> *p, *p1; // деструктор p=start; while(p) { p1=p->next; delete p; p=p1; // освобождение памяти, занятой } // элементами списка }
template <class DataT> void dlist<DataT>::store(DataT c) { listob<DataT> *p; p= new listob<DataT>; // запись нового элемента if(!p){cout<<"Error of memory allocation "; exit(1);} p->info=c; if(start==NULL) // если список пуст, то создается список, состоящий из одного элемента { end=start=p; } else // иначе изменяем значения указателей { p->prior=end; end->next=p; end=p; } }
template <class DataT> void dlist<DataT>::remove(listob<DataT> *ob) // удаление элемента списка
{ if(ob->prior) // если не первый элемент { ob->prior->next=ob->next; if(ob->next) // если не последний элемент ob->next->prior=ob->prior; else // иначе удаляется последний end=ob->prior; // обновление указателя на конец списка
} else // удаляется первый элемент списка, если список не пуст { if(ob->next) { ob->next->prior = NULL; start=ob->next; } else // иначе, т.е. если список пуст, start=end=NULL; // установить начало и конец на 0 } }
template <class DataT> void dlist<DataT>::frwdlist() // вывод элементов списка в прямом направлении
{ listob<DataT> *temp; temp=start; while(temp) { cout<<temp->info<< " "; temp = temp -> getnext(); } cout<<endl; }
template <class DataT> void dlist<DataT>::bkwdlist() // вывод элементов списка в обратном направлении
{ listob<DataT> *temp; temp=end; while(temp) { cout<<temp->info<< " "; temp = temp -> getprior(); } cout<<endl; }
template <class DataT> listob<DataT> *dlist<DataT>::find(DataT c) // поиск объекта, содержащего информацию, совпадающую с указанной
{ listob<DataT> *temp; temp=start; while(temp) { if(c==temp->info) return temp; // совпадение найдено temp = temp->getnext(); } return NULL; // совпадение не найдено }
main() { dlist<double> list; // демонстрация списка элементов типа double double i; listob<double> *p; clrscr(); list.store(1); // запись элементов 1, 2, 3 list.store(2); list.store(3); cout<<" Direct list"; list.frwdlist(); // вывод в прямом направлении cout<<" reverse list"; list.bkwdlist(); // вывод в обратном направлении cout<<endl; cout<<"Hand viewing of the list"; // ручной просмотр списка p=list.getstart(); while(p) { p->getinfo(i); cout<<i<<" "; p=p->getnext(); // следующий элемент } cout<<endl<<endl; cout<<" find of 2 "; p=list.find(2); // поиск элемента 2 if(p) { p->getinfo(i); cout<<"we have find" <<i<<endl; // найден элемент i } cout<<endl;
p->getinfo(i); cout<<"delete"<<i<<" "; list.remove(p); // удаление элемента cout<<"list after deleting"; list.frwdlist(); // список после удаления cout<<endl;
cout<<"insert the new 4"; // запись элемента 4 list.store(4); cout<<" list after insert"; list.frwdlist(); // вывод в прямом направлении cout<<endl; p=list.find(1); // поиск элемента 1 if(!p) { cout<<"Error. No such element "; return 1; // если не найден, выйти } p->getinfo(i); // чтение в i cout<<"Change"<<i<<"to 5 "; // вывод значения i p->change(5); // изменение 1 на 5 cout<<"list after the change"; list.frwdlist(); // вывод в прямом направлении cout<<"Reverse list": list.bkwdlist(); // вывод в обратном направлении cout<<endl;
getch(); return 0; }
Результаты работы программы
Список в прямом направлении: 1 2 3
Список в обратном направлении: 3 2 1
Ручной просмотр списка: 1 2 3
Поиск числа 2 в списке Число 2 было найдено
Удаление числа 2 из списка Список после удаления: 1 3
Запись нового элемента 4 в список Список после вставки нового элемента: 1 3 4
Заменим 1 на 5 Список после замены: 5 3 4 Просмотр полученного списка в обратном порядке: 4 3 5
|
| Оглавление| |