 |
Динамические структуры. Список, очередь, стек
|
|
|
|
Созданию динамических струкутр данных посвящен значительный объем исследований [1,2,3]. Цель этих исследований состоит в конструировании таких способов хранения данных, чтобы они позволяли оптимизировать место на диске и в памяти компьютера, а также обладали свойствами быстрого поиска и/или сортировки элементов.
Нам уже встречались динамические структуры данных при рассмотрении материала о построении двумерных динамических массивов (см. § 5.5). Массивы удобно использовать в том случае, когда наперед известно точное количество элементов для хранения, если же число элементов заранее не известно, то приходится или создавать заведомо больший массив, или постоянно переприсваивать элементы массивов из меньшего в больший. В первом случае мы нерационально обращаемся с памятью, во втором – со временем. Избежать этого позволяет самая простая динамическая структура – список. Рассмотрим класс:
| class list { char data; list *next; public: list (char d) { data= d; next= NULL; } // конструктор ~list (); // деструктор void add_node (list *node) { node->next = this; } // добавление узла list* add_char (char d); // создание и добавление узла list *getnext() { return next; } // get-функции char getdata() { return data; } void show(); // визуализация }; |
Принцип хранения очень прост (см. Рис. 22). Элемент списка сотоит из двух структурных ячеек: первая – для хранения данных (data), а вторая – для хранения указателя на следующий элемент списка (next). При создании первого элемента указатель next указывает на NULL, это и обозначает конец списка (Рис. 22, а). Указатель start указывает на первый элемент списка.
Рис. 22. Список
Как обращаться к элементам такой конструкции? – Последовательно переходя от элемента к элементу. Ведь список пока не имеет оператора operator [ ], - его можно будет написать позже. А пока рассмотрим на листинге ниже реализацию метода show(), последовательно выводящего на экран элементы списка.
|
|
|
В первой строке подпрограммы указателю p присваивается адрес текущего элемента this – того объекта, который вызывает метод show(), например, указатель start. Затем в цикле приозводится вывод данных на экран при помощи метода p->getdata() и переход к следующему элементу списка при помощи метода p = p->getnext(). Эти действия повторяются пока указатель p не станет равным NULL. Все очень просто.
| void list::show() { list *p = this; while(p) // пока указатель p не равен NULL { cout << p->getdata(); // вывести на экран поле data p = p->getnext(); } // перейти к следующему элементу списка } |
Несколько сложнее выглядит процедура добавления и удаления элементов из списка. В нашем примере предложено два метода добавления элемента в список: метод добавления уже созданного ранее объекта void add_node (list *node) и метод одновременного создания и добавления list* add_char (char d). При этом, суть этих подпрограмм одна – ее демонстрирует Рис. 23.
Рис. 23. Список. Добавление узла
Здесь с помощью оператора new создается объект – узел node, указателю node->next присваивается значение start, а указателю start присваивается значение node. Готово.
| list* list::add_char (char d) { list *node = new list(d); node->next = this; return node; } |
Обратите внимание на различия между реализациями методов void add_node (list *node) и list* add_char (char d)., эти различия определяют то, как они используются в программе:
| int main(int argc, char* argv[]) { list *q, *p; list *start= new list('a'); // создание списка for(int i=1; i<13; i++) // заполнение списка при помощи add_node() { q = new list('a' + i); start->add_node(q); start= q; } for(int i=13; i<26; i++) // заполнение списка при помощи add_char() { start= start->add('a' + i); } start->show(); // вывод списка delete start; // удаление списка return 0; } |
Осталось рассмотреть реализацию деструктора класса. Разумеется, нельзя просто уничтожить указатель start, ведь в этом случае все остальные элементы списка останутся в памяти компьютера и обнаружить их адреса станет невозможно, т.к. start удален.
|
|
|
| list::~list() { list *p= this, *q= this; while(p) { q= p->next; free(p); p=q; } } |
На листинге видно, что в деструкторе используются два вспомогательных указателя – p и q, последовательно в цикле пробегающие весь список. Один из них служит для удаления текущего узла списка, а второй – для сохранения адреса следующего за ним элемента.
|
|
|
