лабораторные работы паскаль. Практикум по программированию на языке Паскаль Учебное пособие
 Скачать 0.89 Mb.
|
|
Тема: Ссылочный тип данных Цель работы 1. Ознакомиться с простой динамической структурой данных -однонаправленным списком. 2. Получить навыки работы с переменными ссылочного типа. 3. Получить навыки программирования списков и операций над ними. Краткие сведения из теории 13.1. Объявление переменной ссылочного типа Любой ссылочный тип определяет множество значений, которые являются указателями на значения некоторого типа. Тип, на значения которого можно конструировать указатели, может быть любым: простым (базовым и переменным) и сложным. Будем называть этот тип базовым. Переменная ссылочного типа содержит адрес ячейки памяти, в которой расположено конкретное значение базового типа. Для описания ссылочных типов используется символ " ^ " (англ. CARET - ссылка, синоним POINTER - указатель) и идентификатор типа, например: TYPE P = ^integer; Это описание определяет множество указателей на целые значения. Ссылочные типы в описаниях переменных можно задавать как осредством идентификаторов, так и явно. Например: TYPE Person = RECORD Name,SecondName,SurName : string[20]; Sex : (male,female); Speciality: word ЕND; VAR P1,P2 : P; { тип P введен выше } Oneman : ^ Person; Значение переменной Oneman ссылается (указывает) на некоторое значение типа Person. Данные ссылочного типа можно описать в разделах TYPE или VAR. Описание ссылочных типов позволяет единственное исключение из общего правила, согласно которому идентификатор может быть не описан перед использованием. В данном случае допускается описание вида TYPE PtrType = ^ BaseType; даже, если тип BaseType еще не был описан. Однако BaseType должен быть описан дальше в _1 _0той же части описания типов, что и тип PtrType: TYPE PtrType = ^ BaseType; BaseType = Record x,y : real End; Для того, чтобы присвоить переменной ссылочного типа некоторое значение, необходимо воспользоваться унарной операцией взятия указателя. Знак этой операции - символ " @ ". Операнд - переменная любого типа, например: если имеется описание VAR i : integer; 95 то применение этой операции к переменной i - @i дает в качестве результата значение типа "указатель на целое". Например: P1 := @i ; В обеих частях оператора стоят конструкции одного и того же типа. В результате такого присваивания P1 получит в качестве своего нового значения указатель на переменную i (адрес переменной i). Операция взятия указателя допустима для любых переменных, в том числе для элементов массивов, полей записи и т.д. Например, если есть описание вида VAR A : array [1..10] of integer; то конструкция @A[i] имеет смысл "указателя на i - тое целое значение в массиве A" и может участвовать в присваивании P1 := @A[i]; Ссылочные типы можно образовывать от любых типов, поэтому допустимо определение вида "указатель на указатель". Так, переменная из следующего описания VAR PP1 : ^P; в качестве своих возможных значений имеет множество указателей, ссылающихся на указатели, которые, в свою очередь, ссылаются на целые значения. 13.2. Пустой указатель Среди всех возможных указателей в языке Паскаль выделяется один специальный указатель, который "никуда не указывает". В этом случае в адресном пространстве оперативной памяти выделяется адрес, в котором заведомо не может быть размещена никакая переменная. На это место в памяти и ссылается пустой или "нулевой" указатель, который обозначается служебным словом NIL. Указатель NIL считается константой, совместимой с любым ссылочным типом, т.е. это значение можно присваивать любому ссылочному типу. 13.3. Основные операции Над значениями ссылочного типа допускается две операции сравнения: а) равенство - " = "; б) неравенство " <> ". Эти операции проверяют, ссылаются ли два указателя на одно и то же место в памяти. Например : sign := p1 = p2; { sign является переменной ссылочного типа } или if p1 <> nil then 13.4. Доступ к переменной по указателю Доступ к переменной ссылочного типа может быть осуществлен двумя способами: 1) прямой доступ - с помощью идентификатора; 2) косвенный доступ - путем использования адреса переменной, который хранится в указателе. Например: p1 := @i; Для реализации 1-го способа достаточно использовать оператор присваивания, например: i := i+2; { здесь считывается текущее значение i и увеличивается на 2} 96 Для реализации косвенного доступа к переменной через указатель (ссылку) используется операция, называемая разыменованием. В этом случае необходимо после переменной - указателя поставить символ " ^ ". Например, запись p1^ является переменной, на которую ссылается указатель p1. Следовательно, операторы i := i+2 и p1^ := p1^+2 считаются эквивалентными. Разыменование по определению имеет тип, совпадающий с базовым типом переменной - указателя, в частности, p1^ является переменной целого типа. Разыменование допускается для любых ссылочных типов. Например, для переменной OneMan допускаются конструкции: OneMan^.Name := 'Иван'; if OneMan^.speciality = 22.01 then ... В случае "указатель на указатель" возможно многократное разыменование: например, для переменной pp1 допустима конструкция pp1^^, которая имеет статус целой переменной. Разыменование считается некорректным, если ссылочная переменная имеет значение NIL. В этом случае не существует переменной, на которую ссылается указатель, поэтому операторы: p1 := nil; p1^ := 2; являются недопустимыми, хотя и не приводят к аварийному их прекращению. 13.5. Динамические переменные. Динамическая память Переменные, для которых память распределяется автоматически, называются статическими. Статические переменные описываются в разделах описаний в каком-либо блоке Паскаль - программы и обозначаются идентификатором. Переменные, созданием и уничтожением которых может явно управлять программист, называются динамическими переменными. Динамические переменные, количество которых и место расположения в памяти заранее не известно, невозможно обозначить идентификатором. Поэтому единственным средством доступа к динамическим переменным является указатель, который указывает текущий адрес ячейки памяти. Следует отметить, что для распределения памяти под статические переменные отводится специальный сегмент оперативной памяти (сегмент данных). Аналогично, образование динамической переменной реализуется в другой области оперативной памяти, которая существует отдельно от сегмента данных и называется кучей или динамической областью памяти. 13.5.1. Основные действия над динамическими переменными 1. Процедура NEW предназначена для создания динамических переменных и имеет вид: New (< имя ссылочной переменной >); 2. Процедура DISPOSE удаляет переменную, на которую указывает значение ссылочной переменной, и имеет вид: Dispose (< имя ссылочной переменной >); Например : Var P : ^ Person; Begin New (P); {В куче отводится область памяти, достаточной для хранения записи типа Person} < Действия с указателем P > Dispose (P) {Область памяти, занимаемая удаляемой переменной, возвращается в кучу и может быть использована для других переменных} End. 97 3. Процедура MARK присваивает ссылочной переменной значение, указывающее на вершину кучи, и имеет следующий вид: Mark ( < имя ссылочной переменной >); 4. Процедура RELEASE удаляет из кучи переменную, указанную указателем, и все переменные, следующие за ней. Release (< имя ссылочной переменной >); 5. Процедура GETMEM резервирует в куче область оперативной памяти: GetMem (< имя ссылочной переменной, размер памяти в байтах >). Процедура FREEMEM возвращает в кучу область оперативной памяти, указанную переменной ссылочного типа: FreeMem (< имя ссылочной памяти, размер памяти в байтах >); 6. Размер области, возвращаемой с помощью процедуры FREEMEM, должен быть таким же, как и у области, определенной с помощью GetMem. Процедуры NEW - DISPOSE, MARK - RELEASE и GETMEM - FREEMEM образуют три механизма управления памятью кучи. Первые два механизма используются для однотипных данных, а их отличие можно пояснить с помощью следующей схемы (рис.2a. и 2б.) Куча После Куча После Dispose Release New(p1) → var1 var1 Mark(p1) → var1 var1 var2 var2 var2 var2 New(p2) → var3 Mark(p1) → var3 var4 var4 var4 New(p3) → var5 var5 Mark(p3) → var5 a) б) Рис.1. Структура памяти типа "куча". Процедуры GetMem - FreeMem используются для данных любого типа. В программе следует пользоваться одним из этих механизмов в зависимости от постановки задачи. 7. Функция MAXAVAIL - эта функция определяет размер наибольшей цельной области в куче. Ее результатом является величина целого типа. 13.6. Динамические списковые структуры. Часто ссылочные типы данных используются для организации динамических списковых структур. К ним относятся очереди, списки, деревья и подобные структуры. Для задания списковых структур необходимо определить объект комбинированного типа, в состав которого входит ссылка на объект данного типа. В языке Паскаль разрешено определять ссылки на объекты до описания объектов, например: Type ukaz = ^ pole; dannye = < тип >; pole = record c : ukaz; d : dannye end; 13.6.1. Однонаправленные списки. Определив ссылочный тип, можно построить связанный однонаправленный список (рис.3). First C C Nil D D D Рис. 2. Однонаправленный список. 98 Указатель First содержит ссылку на первый элемент списка. Каждый элемент списка содержит поле C - ссылку на следующий элемент - и поле данных D, которое, в свою очередь, может быть достаточно сложной структурой. Поле ссылки последнего элемента списка содержит пустую ссылку - NIL. Двигаясь по указателям, можно последовательно просмотреть весь список. Если из списка необходимо удалить любой элемент, кроме первого, то для этого достаточно изменить поле ссылки предыдущего элемента. C C Nil D D D Рис. 3. Механизм исключения элемента из списка. На рис.4 показано исключение из списка элемента F. Для этого адрес элемента B, который хранился в поле ссылки элемента F, записывается в поле ссылки элемента A, после чего элемент A будет указывать на B, а элемент F станет недоступным, так как на него никто не ссылается. Пусть Previous - переменная ссылочного типа, содержащая ссылку на элемент, предшествующий удаляемому. Тогда, чтобы осуществить операцию исключения, достаточно выполнить следующий оператор присваивания: Previous^.C := Previous^.C^.C Правая часть оператора присваивания читается так: идти по ссылке, хранящейся в Previous, взять ссылку из поля C удаляемого элемента. Полученное ссылочное значение записывается в поле C элемента, предшествующего удаляемому. Чтобы вставить элемент в произвольное место связанного списка, кроме начала, также необходимо изменить только значения указателей. Сами элементы списка при этом не перемещаются. На рис.5. показано включение в связанный список элемента X. C C Nil D D C D A F D B X1 Рис. 4. Механизм вставки нового элемента в списке. Пусть ссылочная переменная Next указывает на элемент, после которого необходимо вставить в список элемент X. На элемент X указывает ссылочная переменная New. Операция вставки реализуется двумя операторами присваивания: New^.C := Next^.C; Next^.C := New; Первый оператор заносит в поле ссылки вставляемого элемента ссылочное значение, указывающее на элемент B и содержащееся ранее в F. Второй оператор записывает в поле ссылки элемента F ссылку на вставляемый элемент. Для добавления в конец списка элемента X достаточно найти последний элемент списка (поле ссылки имеет значение NIL) и переслать в его поле ссылки указатель на добавляемый элемент. При этом поле ссылки добавляемого элемента должно содержать NIL. Эти действия реализуются операторами New^.C := Nil; Next^.C := New; Обычно при построении связанных списков вводят ссылочную переменную, указывающую на начало списка, на его первый элемент. Поэтому при удалении первого элемента или при вставке нового элемента в начало списка необходимо переопределять не указатель Previous New Next 99 предыдущего элемента, как в рассмотренных выше примерах, а значение начального указателя. Операция удаления реализуется одним оператором First := First^.C; а операция вставки - двумя операторами: New^.C := First; First := New; Пример: Program spisok; Type name = string[10]; ukaz = ^element; element = record uk : ukaz; dan: name end; Var kniga : name; nach,tek,ob,obpr : ukaz; i : integer; Begin { формирование 1-го элемента списка } New(nach); ReadLn; WriteLn('введите первое название'); Read(kniga); nach^.uk := nil; nach^.dan := kniga; While kniga <> 'AAAAA' do { формирование списка } Begin tek := nach; New(ob); WriteLn(' Введите очередное название '); Read(kniga); While (tek<>nil) and (tek^.dan < kniga) do { Поиск подходящего места } Begin obpr := tek; { ссылка на предыдущий элемент } tek := tek^.uk { переход к следующему элементу } End; { вставка нового элемента } ob^.uk := tek; ob^.dan := kniga; If tek = nach then nach := ob Else obpr^.uk := ob End; { конец формирования списка } WriteLn(' каталог учебников:'); { вывод на экран дисплея упорядоченного каталога книг } tek := nach; While tek^.uk <> nil do Begin 100 WriteLn (tek^.dan); tek := tek^.uk End End. Пояснения к программе: Программа SPISOK вводит с клавиатуры названия учебников и строит из них связанный список, упорядоченный по алфавиту. По окончании формирования каталог книг выводится на экран дисплея. Выводы: Использование списковых структур при решении подобных задач имеет определенные преимущества: исключает предварительное резервирование памяти, дает возможность сортировать (упорядочивать) список одновременно с вводом, удалять и вставлять новые элементы. Такой упорядоченный список можно хранить во внешнем файле. Контрольные вопросы 1. Каково назначение переменных ссылочного типа? 2. Как распределяется память под переменные ссылочного типа? 3. Каково назначение процедур NEW и DISPOSE, MARK и RELEASE? 4. В чем состоит отличие механизмов работы этих процедур? 5. Дайте определение динамической переменной? 6. Чем отличается динамическая переменная от статической? 7. Что понимается в языке Паскаль под кучей? 8. Какие операции выполняются над переменными ссылочного типа? 9. Как организуется однонаправленный список ? 10. Каким образом можно исключить элемент из списка? 11. Как организуется вставка элемента в список? 12. Каким образом можно добавить элемент в конец списка? Задание к работе Выполнить индивидуальное задание. Методические указания 1. Необходимо ознакомиться с примером программы SPISOK. 2. При решении задачи использовать ссылочный тип данных. 3. Разработать алгоритм решения задачи. 4. Написать программу. 5. Отладить программу. 6. Разработать тестовые наборы данных на проверку полноты функционирования программы. 7. Оформить отчет и написать выводы по эффективности использования ссылочных типов данных. Содержание отчета 1. Титульный лист. 2. Словесная постановка задачи. 3. Графический или текстуальный алгоритм решения задачи. 4. Листинг программы. 5. Контрольный тест и результаты тестирования программы. 6. Ответы на контрольные вопросы. Варианты индивидуальных заданий 1. Организовать однонаправленный список всех простых чисел, меньших n. Удалить из списка элементы, значения которых лежат в диапазоне от m1 до m2. Результаты обработки списка вывести на экран. 101 2. Дано натуральное число n (n ≥2). Найти все меньшие n простые числа, используя решето Эратосфена. Решетом Эратосфена называют следующий способ. Выпишем подряд все целые числа от 2 до n. Первое простое число 2. Подчеркнем его, а все большие числа, кратные 2, зачеркнем. Первое из оставшихся чисел 3. Подчеркнем его как простое, а все большие числа, кратные, 3, зачеркнем. Первое число из оставшихся теперь 5, так как 4 уже зачеркнуто. Подчеркнем его как простое, а все большие числа, кратные 5 зачеркнем и т.д.: 2, 3, 4, 5, 6, 7, 8, 9, 10, ... Исходную последовательность чисел организовать в виде однонаправленного списка. Удаление производить внутри этого списка, не используя дополнительные списки. 3. Дана действительная матрица размера n ×m; организовать однонаправленный список строк матрицы, упорядоченных: a) по неубыванию значений первых элементов строк. b) по невозрастанию значений наибольших элементов строк. 4. Даны действительные числа а 1 , ......, а n , р, натуральное число k, так что (а 1 ≤ а 2 ≤ ... ≤ а n , k ≤ n). Удалить из последовательности а 1 , ......, а n элемент с номером k (то есть а k ) и вставить элемент, равный p, так чтобы не нарушилась упорядоченность. Последовательность а 1 , ......, а n представить в виде однонаправленного списка. 5. Дана действительная матрица размера n ×m; организовать однонаправленный список строк матрицы, упорядоченных: a) по невозрастанию сумм элементов строк. b) по неубыванию значений наименьших элементов строк. 6. Таблица выигрышей денежной лотереи представлена массивом выигрышных номеров а 1 , ..., а n и массивом выигрышей в рублях р 1 , ..., р n (р i - это выигрыши, выпавший на номер а i ). Разместите эту таблицу в динамической области памяти в виде однонаправленного списка. Организовать удаление элементов списка по мере получения выигрышей. Результаты обработки выводить на экран. 7. Дано натуральное число n. Среди чисел 1, ...., n найти все такие, запись которых совпадает с последними цифрами записи их квадрата, например 6 2 =36, 25 2 =625 и т.д. Представить их в виде однонаправленного списка, элементами которого являются само число и его квадрат. 8. Пусть дан массив а 1 , ..., а n. Требуется переставить а 1 , ..., а n , так чтобы в начале в массиве шла группа элементов больших того элемента, который в исходном массиве располагался на первом месте, затем - сам этот элемент, потом - группа элементов, меньших или равных ему. Использовать однонаправленный список. 9. Назовем натуральное число палиндромом, если его запись читается одинаково с начала и с конца, например 4884, 393, 1. Найти все меньшие 100 натуральные числа, которые при возведении в квадрат дают палиндром. При решении задачи используйте двунаправленный список. 10. Натуральное число из n цифр является числом Армстронга, если сумма его цифр, возведенных в n-ую степень равна самому числу, например, 153=1 3 +5 3 +3 3 . Получить все числа Армстронга, состоящие из двух, трех и четырех цифр, организовать соответственно 3 однонаправленных списка. |