Лекция "Организация списков в языке Турбо Паскаль"

Организация списков в языке Турбо Паскаль Главная   возможность,   которую   предоставляет   наличие   ссылочных   типов   и   ссылочных переменных в Паскале, ­ это возможность построения с их помощью объектов со сложной, меняющейся   структурой.  Примерами  таких  структур являются   списки,   стеки,  деревья. Список ­ это набор записей, каждая из которых имеет поле данных и указатель (ссылку) на следующую запись в списке. Та, в свою очередь, тоже содержит поле данных и ссылку на продолжение списка. Последний элемент списка содержит значение Nil, т.е. уже ни на что не ссылается. Начало списка формирует переменная типа "указатель", содержащая адрес первого элемента списка (рис. 6). Поле данных еще называют информационной частью списка. Указатель в списке должен быть типизированным. Базовым типом для него является тот же тип данных, что и тип информационной части списка. Рассмотрим методы работы со списками, информационная часть которых состоит из  одного поля типа Integer. Такие списки естественно называть списками целых чисел.  Обозначим тип элемента списка идентификатором Elem, а ссылочный тип на элемент  списка ­ идентификатором Uk. Стек ­ линейный список, в котором добавления и исключения элемента производятся с одного конца, называемого вершиной стека. Соблюдается принцип "первым пришел  ­ последним ушел". Считается,   что   доступ   возможен   только   к   верхнему   элементу.   Стек   оптимален   для случаев, когда требуется просчитать и запомнить большое число структур данных, а потом обработать их в обратном порядке. Работа со стеком осуществляется через указатель стека. При выполнении загрузки  элемента в стек данные записываются на место, определяемое указателем стека, а  указатель стека изменяет свое состояние и задает следующую свободную ячейку блока  памяти. Списки могут быть не только линейными, но и кольцевыми. В кольцевом списке  для последнего элемента следующим является первый, а если список двунаправленный, то  для первого предыдущим является последний. Как и линейный, кольцевой список  определяется указателем на свой первый элемент. Мультисписки представляют собой структуру, каждый элемент которой входит в более  чем один список одновременно и имеет соответствующее числу списков количество полей  связи. Часто в виде мультисписков представляют матрицы очень большой размерности, в  которых большинство элементов равны 0 (такие матрицы называются разреженными).  Мультисписки обеспечивают эффективное хранение таких структур в памяти: хранятся  только те элементы, которые отличны от 0. Каждый элемент входит в два списка: в  список­ строку и список­столбец. Вся матрица представлена m + n списками, где m и n ­  соответственно число строк и число столбцов матрицы, каждый элемент хранит значение  элемента матрицы и две ссылки: на следующий элемент в строке и на следующий элемент в столбце, указатели на начала этих списков хранятся в двух массивах.