WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

   Добро пожаловать!


Pages:     | 1 | 2 || 4 |

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

Указатель может принимать значения, равные всем тем адресам ОП, по которым возможна запись данных. Указатель может принимать также значение NIL (пусто), которое говорит о том, что соответствующая динамическая переменная в ОП отсутствует.

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

Type Имя ссылочного типа = ^ Имя базового типа;

Var Имя ссылочной переменной = Имя ссылочного типа;

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

В качестве базового типа могут использоваться простые типы ТР или типы, определяемые программистом.

Например:

Type {Описание базовых типов} typeMas = Array[1..10000] of Real;

typeRec = Record...

...

End;

{Ссылочные типы} ssMas = ^typeMas; { Указатель на массив данных} ssRec = ^typeRec; { Указатель на запись} ssint = ^Integer; { Указатель на переменную типа Integer} sr = ^Real; {Указатель на переменную типа Real} Var A,B,C: ssint;

...

В этом случае А, В, С являются указателями на переменные целого типа.

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

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

Var Имя указателя : pointer;

TP допускает описание типизированных констант типа Pointer (констант ссылочного типа). Начальным значением таких констант может быть только Nil.

Например:

Type Tmas = Array[1..10] of char; { Описание базового типа} sm = ^Tmas; { указатель на массив из 10 символов} Const s1 : sm = Nil; {Задание начального значения Nil для типизированной константы ссылочного типа: s1} Значения указателей можно сравнивать только с помощью проверок на равенство и неравенство. Допустимо использование оператора присваивания, например: A:=Nil;

Для динамических переменных допустимы все те же операции, что и над обычными переменными данного типа.

Все указатели (ссылочные переменные) имеют одинаковый размер, равный 4 байтам. Память под ссылочные переменные отводится на этапе трансляции, а распределение памяти (а затем и её освобождение) под сами динамические объекты осуществляется в процессе работы программы с помощью стандартных процедур и функций ТР.

2.2. Стандартные процедуры и функции для работы с динамическими переменными Любым действиям с динамической переменной должен предшествовать процесс её размещения в динамической памяти. Для этого может быть использована процедура:

New(P);

Р - ссылочная переменная (указатель). Эта процедура создает новую динамическую переменную Р^, отводит место для её хранения в ОП и присваивает её адрес ссылочной переменной Р.

При этом динамической переменной отводится блок памяти, соответствующий размеру типа, с которым объявлен указатель Р.

Если в ходе вычислительного процесса динамическая переменная становится ненужной, её следует удалить. Это осуществляется с помощью процедуры:

Dispose(P);

Эта процедура уничтожает связь между ссылочной переменной Р и значением, на которое она ссылается, тем самым, освобождая память, занятую динамической переменной.

Кроме этих двух процедур модуль TP - System поддерживает следующие стандартные процедуры и функции для работы с указателями и динамическими переменными:

GetMem(P,Size); - используется как и New(P) для размещения динамических переменных. Эта процедура создаёт новую динамическую переменную, отводит для неё в динамической области ОП участок, размером в Size байт и присваивает адрес начала этого участка указателю Р. Значение Size не должно превышать 65521 байт, а переменная Size в программе должна иметь тип Word.

FreeMem(P,Size);- процедура, которая уничтожает динамическую переменную, освобождая в ОП участок размером Size байт, начиная с адреса, записанного в Р. Р - становится не определённым.

Mark(P); - процедура, которая запоминает состояние динамической области ОП в указателе Р, для того, чтобы в дальнейшем все динамические переменные, размещенные в ОП после выполнения Mark, могли быть уничтожены с помощью процедуры Release.

Release(P); - уничтожает все динамические переменные, размещенные в ОП после указателя Р. Значение указателя Р формируется обычно с помощью процедуры Mark.

Функция MaxAvail определяет размер в байтах наибольшего непрерывного блока в динамической области ОП, где может быть размещена (с помощью New или GetMem) динамическая переменная. Тип результата этой функции: Longint.

Функция MemAvail определяет размер в байтах всей свободной памяти в динамической области ОП. Тип результата этой функции: Longint.

Функция Addr(X) - определяет адрес (указатель) объекта Х.

Х - любая переменная, процедура или функция.

2.3. Динамические структуры данных и их описание в Турбо Паскале Указатели являются эффективным средством организации динамических структур данных в виде различных списков. Списком называется структура данных, каждый элемент которой содержит ссылку (указатель), связывающую его со следующим элементом этого списка. Для организации списков чаще всего используются записи, состоящие из двух полей: первое поле содержит подлежащую обработки информацию, второе - указатель на следующую запись. Примерами динамических структур данных являются:



стек, очередь, линейный список, дерево [3,4].

Стек - это список, характеризующийся последовательной организацией и возможностью доступа только с одного края цепочки записей, называемой вершиной стека. Добавление элементов (записей) в стек возможно только в его начало, удаление элементов и их чтение также возможно только из начала стека. Принцип обработки записей стека называется принципом LIFO (Last Input - First Output) - “Последним пришёл - первым ушёл”.

Очередь - это список, характеризующийся последовательной организацией и возможностью доступа с начала и с конца. Добавлять записи можно только в конец очереди, а читать или удалять - только из начала очереди. Принцип обработки записей в очереди называется принципом FIFO (First Input - First Output) - “Первым пришёл - первым ушёл”.

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

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

Рассмотрим пример описания элементов линейного списка.

Type TSpis = ^Element; {Указатель на элемент списка} Element = Record {Описание элемента списка в виде записи} PoleInfo: TypeDan; {Описание поля данных. Здесь TypeDan - любой тип для описания данных} Adres: TSpis; {Указатель на следующий элемент} End;

Var Sbegin, St: TSpis; {Ссылочные переменные - указатели} В этом примере TSpis - имя типа, которое определяет переменную - указатель. Этот указатель будет содержать значения адресов ОП, по которым будут размещаться переменные типа Element (записи). Каждый элемент списка содержит два поля: информационное и адресное. Для работы со списком в программе (в разделе Var) необходимо определить несколько ссылочных переменных: Sbegin - указатель на начало списка, St - указатель на текущий элемент. Все идентификаторы (кроме служебных) программист задает произвольно, в соответствии с алфавитом языка Паскаль.

Описанный выше линейный список может быть изображен в виде последовательности элементов (рис. 1).

PoleInfo PoleInfo PoleInfo PoleInfo Sbegin Adres Adres Adres NIL Рис. С помощью такого представления удобно демонстрировать все возможные действия с линейным списком: удаление элементов, их сортировку, а также добавление новых элементов.

2.4. Лабораторная работа №Линейный динамический список Цель работы: Ознакомиться с процедурами работы с динамическими переменными. Приобрести навыки разработки программ с использованием динамической памяти на примере работы с линейным списком.

Рассмотрим различные действия над линейным динамическим списком на следующем примере: Дан текстовый файл, содержащий список учащихся группы, имеющий вид, представленный в таблице 2.

Таблица №п./п. Ф И О Экзаменационные оценки Сумма 1 2 3 4 5 баллов Разработать программу, которая выполняет следующие функции:

1) Вводит данные о каждом учащемся из текстового файла в линейный список.

2) Выводит сформированный линейный список на экран.

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

4) Выводит измененный линейный список на экран.

5) Упорядочивает список учащихся по убыванию значений сумм баллов.

6) Выводит упорядоченный линейный список на экран.

7) Добавляет одну или несколько записей в упорядоченный линейный список в соответствии с вводимой суммой баллов.

8) Выводит полученный линейный список на экран.

Для реализации каждой из вышеперечисленных функций будем использовать отдельные процедуры со следующими именами:

INPUT_AND_FORM_SPIS - ввод и формирование линейного списка;

OUTPUT_SPIS - вывод линейного списка на экран;

DELETE_ELEM_SPIS - удаление элементов из линейного списка;

SORT_ELEM_SPIS - упорядочение элементов линейного списка;

ADD_ELEM_SPIS - добавление элементов в линейный список.

Cтруктурная схема программы будет иметь вид ( рис. 2.) НАЧАЛО SORT_ELEM_ SPIS INPUT_AND_ ОUTPUT_ FОRM_SPIS SPIS ОUTPUT_ ADD_ELEM_ SPIS SPIS DELETE_ OUTPUT_ SPIS SPIS OUTPUT_ SPIS КОНЕЦ Рис. ОПИСАНИЕ ПРОГРАММЫ Описание глобальных переменных Uses CRT; { Подключение стандартного модуля ТР} Type { Описание типов } Type_Info = Record {Описания типа информационного поля} nom: byte; {Порядковый номер студента в списке } FIO: string[30]; { Фамилия, имя и отчество } Ball: Array[1..5] of byte; { Массив из пяти оценок } Sum_ball: byte; { Сумма баллов } End;

Type_ukaz = ^Type_Elem; { Описание ссылочного типа указатель на элемент динамического линейного списка } Type_Elem= Record { Описание элемента линейного списка } Info: Type_Info; { Информация о каждом студенте } Ukaz: Type_ukaz; { Указатель на следующий элемент } End;

Var { Описание глобальных переменных } Beg_Spis, St, Sp: Type_Ukaz; { Указатель на начало линейного списка в динамической области оперативной памяти, Текущее и предыдущее значение указателя} Для иллюстрации действий с данным списком воспользуемся рис. 3.





Info Info Info Info Beg_Ukaz Ukaz Ukaz Ukaz NIL Рис. Процедура ввода данных и формирования линейного списка Procedure INPUT_AND_FORM_SPIS;

Var { Описание локальных переменных } F_Input: Text; {Текстовый файл с данными} Name_F_Input: String; {Имя файла на диске} i: byte;

Begin Writeln(’ Введите имя файла с исходными данными’);

Readln(Name_F_Input);

Assign(F_Input,Name_F_Input);

Reset(F_Input);

New(St); { Определения начального адреса (указателя) для размещения линейного списка в динамической области ОП } Beg_Spis := St; { Сохранение начального адреса} While Not Eof (F_Input) Do {Цикл до конца файла} begin With St^.Info do begin {Оператор присоединения} Read ( F_Input, nom, FIO); { чтение порядкового номера и фамилии из файла в линейный список} For i := 1 to 5 do Read ( F_Input, Ball[i] ); { То же для всех 5 оценок} Readln ( F_Input, Sum_ball ); { Чтение и запись суммы баллов и переход к новой строке файла} end;

Sp:=St;{ Сохранение текущего указателя в предыдущем} New (St); { Определение указателя на новую ячейку памяти} Sp^.Ukaz := St; { Сохранение указателя на новую ячейку в поле адреса предыдущей} end; { Цикл по записям файла} Sp^.Ukaz := NIL; { Запись в поле указателя последней ячейки занятой списком памяти значения NIL } End; { Конец процедуры ввода и формирования списка} Процедура вывода линейного списка на экран Procedure OUTPUT_SPIS;

Var i: byte; { Описание локальных переменных } Begin St := Beg_Spis; { Установка начального указателя линейного списка } While St <> NIL do { Цикл до конца линейного списка } begin With St^.Info do begin Write (Nom,’ ’, FIO,’ ’);

For i := 1 to 5 do Write ( Ball[i]:3 );

Writeln ( Sum_Ball:4 );

end; { Конец действия оператора присоединения } St := St^.Ukaz; { Переход к следующему элементу списка } end; { Конец цикла по линейному списку } End; { Конец процедуры вывода списка на экран} Процедура поиска и удаления из линейного списка сведений об учащихся, имеющих неудовлетворительные оценки Procedure DELETE_ELEM_SPIS;

Var i: byte;{ Описание локальных переменных } Begin St := Beg_Spis; { Установка начала линейного списка } While St <> Nil do begin With St^.Info do For i := 1 to 5 do If Ball[i] = 2 then { Удаление элемента из списка} begin if St = Beg_Spis then { Удаление из начала см. рис. 4} Beg_Spis := St^.Ukaz Else begin { Удаление из любого места кроме начала линейного списка, см. рис. 5} Sp^.Ukaz := St^.Ukaz;

St := Sp; Break;

end;

end; { Конец цикла по анализу оценок} Sp := St; St := St^.Ukaz; { Переход к следующему элементу линейного списка } end; { Конец цикла по линейному списку } End; { Конец процедуры удаления} St Info Info Info Info Beg_Ukaz Ukaz Ukaz Ukaz NIL Beg_Ukaz := St^.Ukaz Рис. Sp St Info Info Info Info Info Beg_Ukaz Ukaz Ukaz Ukaz Ukaz NIL Sp^.Ukaz := St^.Ukaz;

Рис. Процедура сортировки элементов линейного списка Procedure SORT_ELEM_SPIS;

Var Ss, Sz : Type_ukaz; { Ss - указатель на следующий элемент списка, Sz- переменная для хранения ссылки при перестановке} Key : Boolean; { Признак перестановки} Begin Repeat Key := False; { Перестановок пока не было} St := Beg_Spis; Ss := St^.Ukaz; { Установка первого и второго элементов линейного списка} While Ss <> Nil do begin If St^.Info.Sum_ball < Ss^.Info.Sum_ball then begin { Нужна перестановка} if St = Beg_Spis then begin { Перестановка в начале списка: см. рис. 6} Beg_Spis := Ss;

St^.Ukaz := Ss^.Ukaz;

Ss^.Ukaz := St;

end else begin { Перестановке в произвольном месте списка, кроме начала : см. рис. 7} Sz := Sp^.Ukaz;

Sp^.Ukaz := St^.Ukaz;

St^.Ukaz := Ss^.Ukaz;

Ss^.Ukaz := Sz;

end;

Key := True; { Перестановка произведена } end;

Sp := St;

St := St^.Ukaz; { Переход на следующий элемент списка} If St = Nil then Ss := Nil else Ss := St^.Ukaz; { Изменение значения следующего указателя} end; { Продолжение цикла по просмотру списка } Until Key = False; { Перестановок больше не будет} End; { Конец процедуры сортировки} Обмен St и Ss в начале списка 3. Ss^.Ukaz := St;

St Ss Info Info Info Info Beg_Ukaz Ukaz Ukaz Ukaz NIL 1. Beg_Ukaz := Ss; 2. St^.Ukaz := Ss^.Ukaz;

Рис. Обмен St и Ss в произвольном месте списка 1. Sz := Sp^.Ukaz; 4. Ss^.Ukaz := Sz;

Sp St Ss Info Info Info Info Info Beg_Ukaz Ukaz Ukaz Ukaz Ukaz NIL 2. Sp^.Ukaz := St^.Ukaz; 3. St^.Ukaz := Ss^.Ukaz;

Рис. Процедура добавления элементов в линейный список Procedure ADD_ELEM_SPIS;

Var Key_Insert : Boolean; { Ключ - признак вставки} i, j, Kol_Insert_Zap : byte; { Число добавляемых записей} Ins_Zap : Type_Info; { Добавляемая запись } Begin Writeln( ‘ Введите число добавляемых записей‘ );

Readln( Kol_Insert_Zap );

For i := 1 to Kol_Insert_Zap do Begin With Ins_Zap do begin Writeln( ‘ Введите N n/n, ФИО, 5 оценок и их сумму‘ );

Readln(Nom, Fio );

for j := 1 to 5 do begin Read ( Ball[j]);

Readln ( Sum_ball);

end;

St := Beg_Spis; { Установка на начало списка} Key_Insert := False; { Вставки не было} While ( St <> Nil ) and ( Key_Insert = False ) do begin If St^.Info.Sum_ball < Ins_Zap.Sum_ball then begin { Найдено место для вставки } Key_Insert := True;

Pages:     | 1 | 2 || 4 |










© 2011 www.dissers.ru - «Бесплатная электронная библиотека»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.