Основы программирования Национальный технический университет Украины "Киевский политехнический институт" Факультет информатики и вычислительной техники Кафедра вычислительной техники Киев 2000
    Динамическое распределение памяти. Списковые структуры. Технические характеристики предлагаемого модуля для работы с односвязным списком. Листинг модуля Dinamo. Листинг программы, при написании которой был использован модуль Dinamo.
    В языке программирования Паскаль, как и в других языках, всегда много используются переменные. В Паскале все переменные, которые мы используем в программе, должны быть заранее описаны, то есть, должен быть указан их тип: целое число, строка и т.п. Но зачастую не возможно заранее знать, какого типа переменная нам будет нужна. Для этих целей и служат динамические переменные, или указатели. Для их создания следует перед идентификатором вставить специальный символ ^. Прежде чем в программе можно будет использовать динамические переменные, следует выделить память, куда будут накапливаться значения соответствующего типа. Только после этого указатель будет содержать корректный адрес памяти. Размещение динамических переменных производится в специальной области памяти Heap. Динамические переменные ничем не отличаются от обычных переменных. Над ними можно производить все действия, что и с обычными переменными. Для работы с динамическим распределением памяти очень удобно использовать связанные структуры данных, например односвязные списки.
    Простейшим примером списка является массив, в котором последовательно расположены все его элементы. Но у такого представления есть существенный недостаток - требуется заранее точно указать количество элементов массива. Поэтому лучше воспользоваться более гибким механизмом - динамическими переменными. Наглядно это выглядит так:
    Первый элемент Последний элемент
    
    
    
    
    В схеме каждый элемент разбит на два логических поля: Curr - обозначает все содержательные данные, и Next - указатель на следующий элемент списка. У последнего элемента указатель установлен в Nil, что используется для инициализации не распределенных динамических переменных. Данный список называется односвязным, поскольку движение от элемента к элементу в нем происходит только в одном направлении. Односвязный список использован в модуле Dinamo как один из вариантов работы с динамическими структурами.
    Как происходит работа с элементами односвязного списка, например, вставка нового элемента? Лучше всего это можно проиллюстрировать следующим рисунком на примере односвязного списка из трех элементов.
    
    
    
    
    
    
    
    
    
    Как мы видим, первым действием указателю нового элемента присваивается значение указателя второго элемента (на последний элемент списка), вторым действием разрывается связь между вторым и последним элементом, а вместо этого указатель второго элемента связывается с новым элементом списка.
    В данной программе для работы с динамически распределяемой областью используются процедуры New(Var P : Pointer) и Dispose(Var P : Pointer). ............