![]() |
Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | |
|
Если для каждой динамической переменной описывать и хранить ее "личный" указатель, то никакой выгоды на этапе выполнения программы получить не удастся: часть памяти, как и прежде, будет выделяться статически, а ее общий объем даже увеличится - ведь каждый указатель требует для себя четыре байта.
Следовательно, нужно сделать так, чтобы место под хранение адресов будущих переменных также выделялось динамически. Решением этой проблемы и служат списки - специальные динамические структуры.
Списки применяются, например, в таких ситуациях:
· программист заранее ничего не знает о том, какой именно объем памяти может потребоваться его программе;
· некоторые (особенно "тяжелые") переменные нужны поочередно, и после того как первые "отработали свое", их можно смело стирать из памяти, не дожидаясь конца работы программы, - освобождать место для других "тяжелых" переменных;
· в процессе обработки данных нужно провести большую работу по перестройке всей структуры "на ходу"; и т.д.
Итак, каждый элемент создаваемого списка должен содержать:
1. полезную информацию, которая может иметь любой формат: integer, real, array, record и т.п.;
2. специально выделенное поле (и, может быть, не одно), которое хранит адрес другого элемента этой же структуры.
Приведем примеры различных списочных структур:
· a) Односвязный (линейный) список: структура, каждый элемент которой "знает" адрес только следующего за ним элемента (см. рис. 10.1 (a)). Очень удобно представлять таким списком стек и очередь (см. лекцию 9).
· b) Двусвязный линейный список: структура, каждый элемент которой "помнит" адрес не только следующего, но и предыдущего элемента списка (см. рис. 10.1 (b)). Этот список удобен для работы с деками (см. лекцию 9)
· c) Бинарное дерево (см. лекцию 11) может быть представлено двусвязным нелинейным списком: каждая вершина помнит обоих своих возможных потомков (см. рис. 10.1 (c)). Если каждой вершине необходимо помнить не только потомков, но и предка, то список становится трехсвязным.
· d) Для представления ориентированного графа (см. лекцию 11) можно использовать иерархические списки - комбинацию из двух различных линейных списков (см. рис. 10.1 (d): вершины задаются структурой, содержащей три поля, а дуги - два; справа показан орграф, представленный приведенной списочной структурой).
методы работы со списками:
Дата публикования: 2015-01-26; Прочитано: 699 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!