лабораторная 1. Лабораторная работа 1. Лабораторная работа 1 Динамические структуры данных

• Название: Лабораторная работа 1 Динамические структуры данных
• Анкор: лабораторная 1
• Дата: 23.04.2023
• Размер: 44.04 Kb.
• Имя файла: Лабораторная работа 1.docx
• Тип: Лабораторная работа; #1083981

Лабораторная работа №1

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

Указатели. Список. Создание списка. Просмотр списка

Указатель — это ячейка памяти, хранящая адрес. В Pascal указатели делятся на типизированные (содержат адрес ячейки памяти данного типа) и бестиповые (содержат адрес оперативной памяти, не связанный с данными какого-либо определенного типа). Типизированный указатель содержит адрес области памяти, предназначенной для размещения данных определенного типа, а для бестипового указателя тип данных заранее не определен. Типизированный и бестиповый указатель можно присваивать друг другу.
Для объявления типизированного указателя используется символ caret («крышечка»):

Тип указателя на тип T имеет форму ^T, например:

Указатель – это переменная, в которую можно записать адрес другой переменной (или блока памяти)

Объявление var pc: ^char; // адрес символа pi : ^integer; // адрес целой переменной

Бестиповый указатель объявляется с использованием ключевого слова pointer:

var p: pointer;

Для того чтобы узнать адрес ячейки памяти с выделенной под какую-то переменную в Паскале зарезервирована специальная операция «@»

begin var i := 3; var p := @i; // автовыведение типа ^integer Writeln(p); // $23ED24 - как пример end.

Вопрос?

Получили адрес памяти, перевидите это число в 2-ю и 10-ю систему счисления.
В приведенном примере адрес переменной i теперь находится в указателе p. Можно говорить, что p теперь указывает на i

Как записать адрес: var m: integer; // целая переменная pi : ^integer; // указатель A: array[1..3] of integer begin pi:= @m; // адрес переменной m pi = @A[1];//адрес элемента массива A[1] pi := nil; // нулевой адрес (указатель не указывает никуда)

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

begin var i := 3; var p := @i; // автовыведение типа ^integer p^ := p^ * 2 + 1; Writeln(i); // теперь i = 7 end.

Рассмотрим, как получилось значение 7. Указатель p хранит адрес переменной i, поэтому теперь разыменованный p является просто еще одним именем для области памяти, названной i. Исходя из этого можно оператор p^ := p^ * 2 + 1 переписать как i := i * 2 + 1, что при i, равном трем, дает новое значение i, равное семи.
Пример «Обращение к данным через указатель»

var n,m:integer; pInt: ^integer; A: array[1..3] of integer; begin n := 4; pInt:= @n;// в область памяти pInt помещаем n writeln('Адрес n =',pInt); // вывод адреса памяти writeln('n = ', pInt^); // вывод значения по адресу m := 4*(7-pInt^); pInt^ := 4*(m-n); writeln('n = ', pInt^); writeln('n = ', m); end.

Использование указателей:

type УказательНаУзел = ^Узел; Узел = record Значение: integer; Связь: УказательНаУзел end;

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

var p: ^integer; q : ^Byte p := q; {p : ^Integer; q : ^Byte}

Обойти эти ограничения позволяет универсальность нетипизированного указателя Pointer, совместимого с указателями любых типов:

{p : ^Integer; q : ^Byte; t : Pointer} t := q; p := t;

Для указателей определены две операции сравнения: = и <>.

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

Динамическое распределение памяти

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

Задумаемся теперь: а если у переменной есть адрес, но нет имени, можно ли оперировать ею с прежней легкостью? Ответ на этот вопрос: «Да, можно!»

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

«Безымянные» переменные отличаются от «нормальных» переменных:

1. Нет имени — нечего описывать в разделе var.

2. Ничего не описано, значит, на этапе компиляции память под переменную не выделена. Следовательно, необходима возможность выделять память (и отменять это выделение) прямо в процессе работы программы. Именно из–за этой гибкости такие переменные и называют динамическими.

3. Если «потерять» указатель на переменную, то «никто не узнает, где могилка» её: переменная останется недоступным «мусором», занимая место в памяти, вплоть до конца работы программы. (Проблема утечки памяти!).

Динамическое выделение памяти

– Типизированные указатели:

Для выделения памяти служит стандартная процедура New():

Эта процедура ищет в незанятой памяти подходящий по размеру кусок и, «застолбив» это место для безымянной динамической переменной, записывает в типизированный указатель адрес выделенного участка. Поэтому часто говорят, что процедура New() создаёт динамическую переменную. Размер выделяемого «куска памяти» напрямую зависит от типа указателя. Например, если переменная p была описана как указатель на Integer–переменную, то процедура New(p) выделит два байта; под Real–переменную необходимо выделить шесть байт и т. д.

– Нетипизированные указатели:

Для того, чтобы выделить память, на которую будет указывать нетипизрованный указатель Pointer, нужно воспользоваться стандартной процедурой GetMem(p : Pointer; size : Word), которая выделит столько байт свободной памяти, сколько указано в переменной size.

Список. Создание списка путем добавления элементов в конец списка. Просмотр списка

Определение. Списком называется структура данных, каждый элемент которой посредством указателя связывается со следующим элементом.

Из определения следует, что каждый элемент списка содержит поле данных (Data) (оно может иметь сложную структуру) и поле ссылки на следующий элемент (Next). Поле ссылки последнего элемента должно содержать пустой указатель (Nil).

Схематически это выглядит так:



Рис. 1 Структура данных типа список

Задача. Сформировать список, содержащий целые числа 3, 5, 1, 9.

Для этого сначала определим запись типа S с двумя полями. В одном поле будут содержаться некоторые данные (в нашем случае числа 3, 5, 1 и 9), а в другом поле будет находиться адрес следующего за ним элемента.

Type Ukazatel = ^S; S = Record Data : integer; Next : Ukazatel ; End;

Таким образом, мы описали типы, с помощью которых можно создать наш связанный однонаправленный список.

Заметим, что все элементы списка взаимосвязаны, т. е. о том, где находится следующий элемент, "знает" только предыдущий. Поэтому самое главное в программе - это не потерять начало списка. Для этого на начало списка установим указатель с именем Head и будем следить за тем, чтобы на протяжении выполнения программы значение этого указателя не менялось.

А теперь опишем переменные для решения нашей задачи:

Var Head, {указатель на начало списка}x {вспомогательный указатель для создания очередного элемента списка}: Ukazatel;

Создадим первый элемент:

New(x); {выделим место в памяти для переменной типа S} x^.Data := 3; {заполним поле Data первого элемента} x^.Next := Nil; {заполним поле Next первого элемента: указатель в Nil} Head := x; {установим указатель головы списка на первый элемент}

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

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

Head^.Next = x^.Next; Head^.Data = x^.Data; Head = x;

Выделим область памяти для следующего элемента списка.

New(x^.Next);

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

x := x^.Next;

Определим значение этого элемента списка, то есть, заполним поля:

x^.Data := 5; x^.Next := Nil;

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

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

Procedure Init(Var u : Ukazatel); Var x : Ukazatel; Digit : integer; {Значение информационной части элемента списка} Begin Writeln('Введите список '); u := Nil; {Список пуст} Writeln ('Введите элементы списка. Конец ввода 0'); Read (Digit); if Digit <> 0 then {Формируем и вставляем первый элемент списка} Begin New(x); x^.Next := Nil; x^.Data := Digit; u := x; Read (Digit); while Digit<>0 do Begin New(x^.Next); {Формируем и вставляем элемент в конец списка} x := x^.Next; x^.Next := Nil; x^.Data := Digit; Read(Digit); End; End; Writeln; End;

Ответьте на вопросы:

1. 
   Какие операции требуется выполнить для вставки в список его элемента?
   
   
   
2. 
   Можно ли для построения списка обойтись одной переменной?
   
   
   
3. 
   Сколько элементов может содержать список?
   
   
   
4. 
   Когда прекращать ввод элементов списка?
   
   
   
5. 
   Запишите операторы, создающие третий и четвертый элементы списка (1, 9).
   

Задание для самостоятельного выполнения
Реализовать односвязный список. Пользователь вводит с клавиатуры, данные в список. Конец ввода данных будет определяться с помощью ввода слова «End». Программа должна:

- вывести все элементы списка;

- вывести количество элементов в списке;

- вывести наибольший элемент;