Полный обучающий курс (стр. 67 )

{Найдем предпоследний элемент}

x := Head;

dx :=Head;

while x^.Next<>Nil do

Begin

dx := x;

x := x^.Next;

End;

{Удаляем элемент x^ из списка и освобождаем занимаемую им память}

dx^.Next := Nil;

Dispose(x);

Теперь опишем процедуру удаления элементов из списка в общем случае:

Procedure Del(Gigit : integer; Var u : Ukazatel );

Var

x, dx : UKAZATEL ;

Begin

x := Head;

while x<>Nil do

if x^.Data=Digit

then

Begin

if x=y

then

Begin

Head := Head^.Next;

Dispose(x);

x := Head;

End;

else

Begin

dx^.Next := x^.Next;

Dispose(x);

x := dx^.Next;

End;

End;

else

Begin

dx := x;

x := x^.Next;

End;

End;

Задание. Напишите полный текст программы, решающей рассматриваемую задачу. Протестируйте программу, дополните комментарием покажите учителю для оценки.

Выберите с учителем задачи для самостоятельного решения.

1. Написать программу, содержащую процедуру, которая удаляет из списка М второй элемент, если такой есть.

2. Написать программу, содержащую процедуру, которая удаляет из списка М N-ый элемент, если такой есть. N задает пользователь.

3. Написать программу, содержащую процедуру удаления из заданного списка все вхождения элемента с заданным значением информационной части.

4. Написать программу, содержащую процедуру, которая удаляет из списка М за каждым вхождением элемента Е один элемент, если такой есть и он отличен от Е.

5. Написать программу, содержащую процедуру, которая удаляет из списка М первый отрицательный элемент, если такой есть.

6. Написать программу, содержащую процедуру, которая удаляет из списка М все отрицательные элементы.

7. Написать программу, содержащую процедуру, которая формирует список М, включив в него по одному разу элементы, которые входят хотя бы в один из списков М1 и М2.

8. Написать программу, содержащую процедуру, которая формирует список М, включив в него по одному разу элементы, которые входят одновременно в оба списка М1 и М2.

9. Написать программу, содержащую процедуру, которая формирует список М, включив в него по одному разу элементы, которые входят в список М1, но не входят в список М2.

10. Познакомившись с текстами предыдущих задач, придумайте свою задачу и решите ее.

Занятие 7. Зачет.

Приготовьте для проверки файлы с решенными задачами и листинги.

Проверьте свои знания, ответив на вопросы:

1. Дайте определение динамической структуре список.

2. Сколько элементов может содержать список? Как заканчивается список?

3. Сколько полей может содержать элемент списка? От чего зависит количество полей? Приведите примеры.

4. Какого типа могут быть поля элементов списка? Приведите примеры.

5. Обязательно ли применять процедуру освобождения памяти, занятой элементом, когда мы избавляемся от этого элемента в списке? Каким образом это влияет на работу программы?

6. Можно ли ссылку одного элемента направить сразу на два или больше других элемента? Как необходимо поменять тип указателя, чтобы решить эту проблему?

7. Может ли элемент списка быть такого типа, чтобы содержать несколько полей типа указателя? Если – да, то приведите пример для чего это может быть нужно.

8. Можно ли последовательно "связать" два списка разного типа и почему?

9. Можно ли одновременно работать с несколькими списками сразу?

10. Как Вы считаете, на что нужно обращать особое внимание при работе со списками?

Динамические структуры данных

Занятие I. Динамические структуры данных. Статические и динамические переменные. Адреса. Указатели и их объявление.

В любой вычислительной системе память относится к таким ресурсам, которых всегда не хватает. Управление памятью – одна из главных забот программиста, так как для него очень важно создавать программы, эффективно использующие память, ведь во время выполнения программы память необходима для следующих элементов программ и данных:

• сама программа пользователя;

• системные программы времени выполнения, которые осуществляют вспомогательные действия при работе программы пользователя;

• определяемые пользователем структуры данных и константы;

• точки возврата для программ;

• временная память для хранения промежуточных результатов при вычислении выражений;

• временная память при передаче параметров;

• буферы ввода-вывода, используемые как временные области памяти, в которых хранятся данные между моментом их реальной физической передачи с внешнего устройства или на него и моментом инициализации в программе операции ввода или вывода;

• различные системные данные (информация о статусе устройств ввода-вывода и др.).

Из этого перечня видно, что управление памятью касается широкого класса объектов.

До сих пор мы использовали простейший способ распределения памяти – статическое распределение, т. е. распределение памяти при трансляции программы. То есть когда Вы объявляете переменную

Var

A : Array[1..100] of integer;

Вы даете указание компилятору выделить память размера, соответствующего заданному типу, т. е. 2*100=200 байт. Если в программе на нужный программный объект мы ссылаемся по имени А[3], то машинный код содержит ссылку на номер ячейки памяти (адрес байта), начиная с которой размещается этот объект.

Адреса задаются двумя 16-тиразрядными словами (тип word) – сегментом и смещением. Каждое из них способно адресовать 216=65536 байт (64 Кбайт). Для адресации пространства размером в 1 Мбайт требуется 20 разрядов. Сегменты адресуют память с точностью до параграфа – фрагмента памяти в 16 байт. Смещение адресует память с точностью до байта, но впределах сегмента. Реальный (абсолютный) адрес складывается из значения сегмента, сдвинутого на 4 разряда влево (умноженного на 16), и смещения. Фрагмент программы вычисления абсолютного адреса в реальном режиме:

Var

Segment, Offset : word;

Address : LongInt;

. . .

Address := Segment*16+Offset;

Программа на Паскале получает один сегмент данных, поэтому область памяти, в которой могут быть размещены статические переменные Вашей программы, ограничена 64 Кбайтами. При попытке исполнить программу, требующую большего размера памяти, будет выдана ошибка:

Error 49: Data Segment too large{Слишком большой сегмент данных}

При динамическом распределении памяти Вы можете запросить блоки размером до одного сегмента (64 Кбайт) каждый, причем их можно требовать в пределах основной памяти (640 Кбайт) в реальном режиме и без программных ограничений в защищенном.

Бывают такие данные, размер которых выясняется только при выполнении программ. Кроме того, иногда мы не знаем, будет существовать некоторый объект или нет.

Например, в программе для обработки текстов (такие программы называются "текстовыми процессорами") требуется организовать поиск слов, определенных пользователем. Естественно, что определить заранее длину слова, которое будет задано, невозможно. Часто программный объект, причем значительного размера, бывает нужен на непродолжительное время. Использование статических программных объектов в таких случаях очень неэффективно, поскольку программа должна быть рассчитана на максимальные размеры объектов. Область памяти, в которой могут быть размещены статические переменные, ограничена, и, рассчитывая на максимальный размер переменных, мы ограничиваем их количество. В Паскале, кроме статических, предусмотрены динамические объекты. Память под них отводится во время исполнения программы, а когда программный объект можно удалить, память освобождается.

И статические, и динамические переменные вызываются по их адресам. Без адреса не получить доступ к нужной ячейке памяти, но, используя статические переменные, непосредственно адрес Вы не указываете, а обращаетесь к переменной по имени. Компилятор размещает переменные в памяти и подставляет нужные адреса в коды команд.

Адресация динамических переменных происходит через указатели. В Паскале можно определить переменные, которые имеют тип указатель, их значения определяют адрес объекта. Для работы с динамическими переменными в программе должны быть предусмотрены:

ü  выделение памяти под динамическую переменную;

ü  присвоение указателю на динамическую переменную адреса выделенной памяти (инициализация указателя);

ü  освобождение памяти после использования динамической переменной.

Программист сам должен резервировать место под переменную, определять значения указателей, освобождать память – удалять динамические переменные. Для использования динамической переменной где-то в статике должен быть указатель на нее. Компилятор предусматривает место под указатель, об инициализации указателя должен заботиться программист.

Вместо любой статической переменной можно использовать динамическую, но без реальной необходимости этого делать не стоит. Переменные простых типов нет смысла размещать в динамической области, поскольку они занимают меньше места, чем указатель на них. Например, указатель на целое занимает 4 байта, само целое – 2 байта. Кроме того, при динамическом распределении памяти удлиняется текст программы, снижаются наглядность и быстродействие. Это объясняется тем, что, во-первых, нужно во время исполнения программы определять значения указателей, а во-вторых, усложняется доступ к значению переменной.

Указатели и их объявление

Для работы с динамическими программными объектами в Паскале предусмотрен ссылочный тип или тип указателей. В переменной ссылочного типа хранится ссылка на программный объект (адрес объекта). Указатель состоит из сегмента и смещения. По правилам Паскаля указатели на разные типы данных имеют различные типы, причем эти типы несовместимы, т. е. указатели на разные типы данных не могут ссылаться на один объект.

Чтобы связать ссылочный тип с определенным типом данных, используется символ ^, помещаемый перед именем типа. Например, имеется тип массив:

Type

A = Array[1..100] of integer;

Тип указателя на такой объект: