Создание и обработка динамических структур

Практическая работа №10

Тема: Создание и обработка динамических структур

Цель: получение знаний и навыков по созданию динамических структур, их использованию, сферам применения.

Вид работы: фронтальная.

Время выполнения: 2 часа.

Теоретический материал:

Линейные списки — это данные динамической структуры, которые представляют собой совокупность линейно связанных однородных элементов, и для которых разрешается добавлять элементы между любыми другими, и удалять любой элемент.

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

Очередь — частный случай линейного односвязного списка, для которого разрешены только два действия: добавление элемента в конец (хвост) очереди и удаление элемента из начала (головы) очереди.

Стек — частный случай линейного односвязного списка, для которого разрешено добавлять или удалять элементы только с одного конца списка, который называется вершиной (головой) стека.

Указатель объявляется с помощью специального символа каре (^), за которым записывается идентификатор типа динамической переменной:

Type имя_типа=^тип;

Var имя переменной=имя типа;

Или

Var имя переменной:^имя типа;

Например:

A,B,C:^Integer;

В этом случае переменные A,B,C являются указателями на переменные типа Integer. Для обращения к значениям этих переменных служат идентификаторы A^,B^,C^, то есть имя переменной и знак каре.

Кроме того, указатель может быть объявлен явно следующим образом:

Var p:Pointer;

Значения указателей можно сравнивать только с помощью проверки на равенство и неравенство. Допустимо также использование оператора присваивания. Для динамических переменных (A^,B^,C^) допустимы все те же операции, что и над обычными переменными данного типа.

Задания:

1)  Задан файл целых чисел. Перепишите элементы этого файла в обратном порядке, используя динамическую структуру данных в качестве промежуточного звена.

2)  Создайте очередь из n элементов и стек из m элементов. Добавьте элементы очереди в вершину стека.

Ход работы:

         В тетрадь оформите листинг второй программы с комментариями

1. За исходный файл целых чисел можно принять файл из предыдущей работы – ‘1.res’, или создать свой, что более предпочтительно. В качестве динамической структуры используем массив указателей на целый тип:

var x: array[1..50] of ^integer; {символ ^ определяет указатель}

В цикле записываем данные из файла в динамический массив. Удаляем файл (erase(f) – удаляет файл, связанный с файловой переменной f), перед этим целесообразно убедиться в том, что массив создан. Перебираем все элементы массива с последнего по первый и записываем их во вновь созданный файл с таким же именем ‘1.res’.

Это один из способов решения задачи.

2. Очередь и стек – это динамические структуры данных. Очередь организованна по принципу “последним пришёл – последним ушёл”, стек по принципу – “последним пришёл – первым ушёл”. Описание переменных, обозначающих стек и очередь, будет выглядеть, например, так:

type din=^xxx;     {описание типа указатель, представляет собой односвязный список}

xxx=record {тип запись с полями}

chislo: integer;      {поле, содержащее данные}

next: ^din;   {поле, содержащее указатель на следующую запись в списке}

end;   {завершение описание типа запись}

var stek, ocher: din;

В теле программы с клавиатуры вводится количество элементов очереди (n) и количество элементов стека(m). Организуются циклы для заполнения очереди и стека. Необходимо учесть, что элементы очереди добавляются в конец, а элементы стека в начало.

Контрольные вопросы и задания:

1)  В чём заключается особенность объявления данных динамической структуры?

2)  Что выполняет операция разыменования?

3)  С помощью каких процедур происходит распределение памяти под динамические переменные?

4)  Какие состояния может принимать указательная переменная?

5)  Каким образом выражаются динамические свойства несвязанных динамических данных?

В чём заключаются отличия при обработке стека и очереди?

Скачано с www.znanio.ru