 |
Способы доступа к данным: стек и очередь
|
|
|
|
По способу добавления элементов в динамическую структуру и удаления из нее списки подразделяются на струкутры с независимым доступом (такие как массив, где можно обратиться к любому эленту списка по номеру) и структуры с последовательным доступом – стек и очередь.
Стек – это динамическая структура данных, составленная по принципу «последним вошёл – первым вышел» (LIFO, Last In First Out). Для стеков обязательными операциями являются: операция постановки в стек push(x), где х -элемент, который засылается в вершину стека и операция извлечения pop()., возвращающая последний поставленный элемент из вершины.
Чаще всего принцип работы стека сравнивают со стопкой тарелок: чтобы взять вторую сверху, нужно снять верхнюю.
Очередь – структура данных с дисциплиной доступа к элементам «первый пришёл – первый вышел» (FIFO, First In First Out). Добавление элемента (принято обозначать enqueue(х) – поставить в очередь) возможно лишь в конец очереди, выборка – только из начала очереди (что принято называть dequeue() – убрать из очереди), при этом выбранный элемент из очереди удаляется.
Рис. 24. Способы добавления и удаления элементов: а) стек; б) очередь
Проанализировав предыдущий пример, можно убедиться, что доступ к элементам списка list организован по технологии LIFO – стек.
Сложные динамические струкутры данных
Мы рассмотрели (см. § 11.2) самый простой из вариантов списка – простой список, называемый в литературе так же однонаправленным списком. Но динамических структур много больше и их исследование – отдельная наука. Перечислим кратко основные виды струкутр.
Двунаправленный список
Рис. 25. Список: а) однонаправленный; б) двунаправленный
Двунаправленный список имеет в каждом элементе (узле) два указателя: один – next – указатель на последующий элемент списка, а второй – prev – указатель на предыдущий. Удобство такого списка состоит в том, что по нему можно двигаться в обоих направлениях – как от указателя start до end (совершая в цикле переход node= node->next), так и от конца к началу – от указателя end до start (передвигаясь в цикле node= node->prev).
|
|
|
| class double_list { char data; double_list *next; // указатель на следующий элемент списка double_list *prev; // указатель на предыдущий элемент списка public:... }; |
Кольцевые списки
Кольцевые списки бывают как однонаправленные, так и двунаправленные, суть кольцевых списков (ring) в том, что последний элемент указывает не на NULL, а на первый элемент списка.
Рис. 26. Кольцевые списки: а) однонаправленный; б) двунаправленный
На рисунке (Рис. 26) приведена сруктура однонаправленного (Рис. 26, а) и двунаправленного (Рис. 26, б) кольцевого списка. Имея такую структуру можно двигаться в одном (или в двух) направлениях бесконечно – по кольцу. Условие прохода и обработки элементов всего списка состоит не в том, чтобы встретить NULL, а в том, чтобы встретить начало – указатель start.
| class ring_list { char data; ring_list *next; // указатель на следующий элемент списка ring_list *prev; // указатель на предыдущий элемент списка public: ring_list (char d) { data= d; next= this; prev= this} // конструктор ring_list* add_char (char d);... };ring_list* ring_list::add_char (char d) { list *node= new list(d); // создать новый элемент списка list *temp= this->Prev // запомнить указатель на последний элемент this->prev= node; node->prev= temp; node->next= this; temp->next= node; return node; } // вернуть указатель на новое начало списка |
Бинарное дерево
Рассмотренные выше структуры данных имели линейную конструкцию: после одного элемента списка располагался один следующий элемент и т.д., но существуют структуры, Бинарное дерево ()
Рис. 27. Бинарное древо
Шаблоны классов
В рассмотренном выше (см. § 11.2) примере элементами хранения данных в поле data списка является символьный тип char. Теоретически, класс для хранения любых элементов в виде простого списка ничем не будет отличаться от класса описанного выше кроме типа поля data. Разумно было бы применить шаблон (template) для создания универсального класса, позволяющего организовать хранение объектов произвольного типа.
|
|
|
|
|
|
