Главная | Обратная связь | Поможем написать вашу работу!

Рязанский государственный радиотехнический университет

Федеральное агентство по образованию

ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ
ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ

Рязанский государственный радиотехнический университет

СТРУКТУРЫ И АЛГОРИТМЫ

ОБРАБОТКИ ДАННЫХ

Динамические переменные, ООП

Методические указания

Рязань 2010

Содержание

Введение. РАЗРАБОТКА И ВЫПОЛНЕНИЕ ПРОГРАММ В КОНСОЛЬНОМ РЕЖИМЕ DELPHI 7 4

1. Запуск Delphi 4

2. Работа с консольным приложением.. 4

3. Установка параметров среды Delphi 6

4. Компиляция и выполнение программы.. 7

5. Состав проекта. 8

6. Язык программирования Delphi 8

7. Особенности работы программы в консольном режиме. 10

Тема 1. УКАЗАТЕЛИ И ДИНАМИЧЕСКИЕ ПЕРЕМЕННЫЕ.. 11

1. Статические и динамические переменные. 11

2. Указатели. 11

3. Операция получения адреса. 12

4. Функции и процедуры для работы с динамической памятью.. 12

5. Присваивание значений указателям.. 13

6. Организация ссылок. 13

7. Динамические списковые структуры данных. 14

8. Реализация основных операций со списком.. 15

Контрольные вопросы.. 17

Лабораторная работа 1. Организация списков с помощью динамических переменных 18

Тема 2. МОДУЛИ.. 23

1. Назначение модулей. 23

2. Заголовок модуля. 24

3. Секция интерфейса. 24

4. Секция реализации модуля. 24

5. Секция инициализации. 25

6. Секция деинициализации. 25

7. Использование модуля в основной программе. 26

8. Использование идентификаторов элементов модуля. 26

9. Добавление модуля к проекту. 26

10. Компиляция проекта, использующего модули. 27

Контрольные вопросы.. 27

Лабораторная работа 2. Создание модуля для работы с динамическим списком 27

Тема 3. ОБЪЕКТНО-ОРИЕНТИРОВАННОЕ ПРОГРАММИРОВАНИЕ.. 29

1. Основные концепции ООП.. 29

2. Классы и объекты.. 30

3. Создание и уничтожение объектов. 31

4. Инкапсуляция. Свойства. 33

5. Наследование. Методы.. 35

6. Полиморфизм. Виртуальные и динамические методы.. 36

7. Пример реализации полиморфизма для иерархии графических объектов 37

8. Перегрузка методов. 40

9. Абстрактные методы.. 41

10. Области видимости. 42

11. Объект изнутри. 43

Контрольные вопросы.. 47

Лабораторная работа 3. Создание класса – списка. 47

Библиографический список.. 50

Введение.
РАЗРАБОТКА И ВЫПОЛНЕНИЕ ПРОГРАММ В КОНСОЛЬНОМ РЕЖИМЕ DELPHI 7

1. Запуск Delphi

Для запуска интегрированной среды разработчика Delphi с помощью меню Пуск выполните команду Пуск | Программы | Borland Delphi 7 | Delphi 7.

Если на рабочий стол Windows вынесен ярлык , то для запуска Delphi дважды щелкните по нему левой кнопкой мыши.

На экране появится оконный интерфейс Delphi, основной частью которого является Главное окно:

Заголовок Главного окна Главное меню Палитра компонентов

Панели инструментов

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

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

2. Работа с консольным приложением

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

Создание консольного приложения

В меню File выберите команду New (новый), а затем в открывшемся подменю выбарите Other… (другой). На экране появится окно New Items (новые элементы) с открытой вкладкой New (новый):

Выберите Console Application (консольное приложение), дважды щелкнув по пиктограмме мышкой.

На экране появится окно Редактора кода с заголовком Project1.dpr (номер проекта может изменяться в зависимости от количества ранее созданных проектов в текущем сеансе работы Delphi).

В окне Редактора кода располагается программа. Имя проекта (программы) совпадает с именем файла проекта.

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

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

Первое сохранение проекта

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

Если, например, в рамках какой-либо дисциплины вы выполняете три лабораторные работы по программированию на Delphi, то на отведенном для вашей группы дисковом пространстве сначала создайте вашу личную папку, имя которой – ваша фамилия (желательно латинскими буквами, например, Ivanov). В этой папке создайте три папки с именами лабораторных работ, например, LW1, LW2, LW3 (LW – аббревиатура от слов Laboratory Work – лабораторная работа).

Папки можно создавать как перед разработкой программы с помощью проводника, так и в процессе сохранения проекта в среде Delphi.

Сразу же после открытия нового проекта сохраните его под нужным именем в предназначенной для этого проекта папке. Для этого в меню File выберите команду Save Project As… (сохранить проект как…) или Save (сохранить) или нажмите кнопку Save на панели инструментов Стандартная. На экране появится окно диалога сохранения проекта:

В поле Имя файла введите имя проекта, например, LabWork1.

В поле Папка нажмите кнопку со стрелкой € – раскроется список доступных дисков и папок на вашем компьютере. Сначала выберите диск (дважды щелкните по нему левой кнопкой мыши). Его название появится в верхнем окне, а в основном окне появится список папок, содержащихся на этом диске.

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

После ввода имени проекта и выбора папки для его сохранения нажмите кнопку Сохранить. Окно проекта и заголовок программы изменят свое название на то, под которым был сохранен проект.

Создание папки в процессе сохранения проекта

Можно создать новую папку в процессе сохранения проекта. Для этого в окне диалога сохранения проекта войдите в папку, в которой хотите создать новую папку, нажмите кнопку Создать папку на верхней панели диалогового окна и введите в заголовке появившейся новой папки имя новой папки и нажмите клавишу Enter или Открыть. Затем сохраняйте документ в созданной папке обычным образом.

Сохранение проекта под прежним именем

После работы с проектом, которому уже было присвоено имя, нажмите кнопку Save на панели инструментов Стандартная,и проект будет сохранен в той же папке под прежним именем.

Сохранение проекта под другим именем

Проект можно сохранить под другим именем или в другом месте. Для такого сохранения используется команда File|Save Project As… (сохранить проект как …). При выполнении этой команды появляется описанное выше окно сохранения проекта, в котором можно задать новое место хранения (поле Папка) или новое имя файла (поле Имя файла).

3. Установка параметров среды Delphi

Для удобства работы в среде Delphi желательно настроить некоторые ее возможности.

Режим автосохранения

Для установки режима автосохранения в меню Tools выберите подменю Environment Options. Появится диалоговое окно настройки параметров среды. На вкладке Preferences в группе Autosave options (опции автосохранения) установите флажок Editor files (редактируемые файлы). Все файлы проекта будут автоматически сохраняться перед выполнением программы.

Создание резервных копий файлов

Если вы хотите, чтобы в процессе редактирования создавались резервные копии файлов, в меню Tools выберите подменю Editor Options. Появится диалоговое окно настройки параметров редактора Editor Properties. На вкладке Display в группе Display and file options (опции дисплея и файлов) установите флажок Create backup files (создавать резервные копии файлов).

Использование русских букв

Чтобы иметь возможность использовать в комментариях к программе и в строковых константах русские буквы, выберите для отображения программы один из шрифтов с кириллицей. Для этого в меню Tools выберите подменю Editor Options. Появится диалоговое окно настройки параметров редактора Editor Properties. На вкладке Display в поле Editor font (шрифт редактора) с помощью клавиши со стрелкой раскройте список шрифтов редактора и выберите один из шрифтов с кириллицей, например, Courier New Cyr. В поле Size (размер) можно выбрать удобный для вас размер шрифта.

Получение информации о данных программы

Возможность получения отладочной информации устанавливается в том же окне настройки параметров редактора Editor Properties на вкладке Code Insight в группе Automatic features:

q Code parameters – разрешает появление подсказки с перечислением формальных параметров подпрограмм при вводе открывающей круглой скобки после имени подпрограммы при записи оператора обращения к ней;

q Tooltip expression evaluation – разрешает показывать текущее значение переменной или выражения при указании на них мышью в процессе отладки программы.

4. Компиляция и выполнение программы

После ввода текста программы необходимо её откомпилировать и выполнить.

Для компиляции проекта в меню Project выберите команду Compile Project или нажмите комбинацию клавиш Ctrl+F9.

Для выполнения программы в меню Run выберите команду Run, или нажмите кнопку на панели инструментов Отладка, или нажмите клавишу F9.

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

Writeln('Press Enter to continue.'); // вывод подсказки для продолжения программы

Readln; // ожидание нажатия клавиши Enter

Выполнение процедуры Readln переведет экран пользователя в состояние ожидания и потребует нажатия на клавишу Enter для продолжения выполнения программы.

5. Состав проекта

Консольный проект Delphi состоит из следующих файлов (в скобках указаны расширения имен файлов):

· файл проекта (dpr);

· файл параметров проекта (dof);

· файл параметров среды (cfg);

· файлы модулей (pas), если при создании программы создаются и используются модули.

Кроме этих файлов могут автоматически создаваться резервные копии файлов: ~dpr – для файла проекта и ~pas – для файлов модулей.

После компиляции создается исполняемый файл (exe) с именем проекта.

6. Язык программирования Delphi

В среде Delphi для разработки приложений используется язык программирования Delphi, основу которого составляет язык Object Pascal (объектно-ориентированное расширение стандартного языка Pascal).

Все основные конструкции Borland Pascal 7.0 сохранены в языке Delphi. Коренному преобразованию подверглась модель объектов – принципы объектно-ориентированного программирования, которые воплощены в языке и определяют правила использования объектов. Delphi поддерживает сразу две модели: «старую», появившуюся в Turbo Pascal 5.5, и «новую», ориентированную на среду визуального программирования. Сочетание старой и новой моделей в одной программе фирмой Borland декларируется как «возможное», однако без необходимости делать это не рекомендуется.

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

Ниже приведены основные отличия языка Delphi от языка Borland Pascal 7.0, относящиеся к комментированию программы и описанию некоторых простых типов данных: целочисленных, вещественных и символьных.

Комментарии

Текст многострочного комментария ограничивается символами (* и *) или их эквивалентами { и }.

Однострочный комментарий содержит двойной слэш (//) в начале комментария.

Отличия в описании простых типов данных

Некоторые простые типы данных (целочисленные, вещественные и символьные) делятся на базовые типы Delphi и машинно-ориентированные типы.

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

Машинно-ориентированные типы используются для выполнения арифметических операций в процессоре компьютера, их состав определяется операционной системой и процессором ЭВМ, они представляют собой некоторое подмножество базовых типов. Их использование считается более предпочтительным, т.к. при этом компилятор создает более эффективный код. При использовании базовых типов, не совпадающих с машинно-ориентированными, во время выполнения операций осуществляется предварительное приведение к «ближайшему» машинно-ориентированному типу.

Базовыецелочисленные типы

Имя типа	Диапазон	Представление в памяти
Shortint	–128.. 127	1 байт, со знаком
Smallint	–32 768.. 32 767	2 байта, со знаком
Longint	–2 147 483 648.. 2 147 483 647	4 байта, со знаком
Int64	–2⁶³.. 2⁶³–1	8 байтов, со знаком
Byte	0.. 255	1 байт, без знака
Word	0.. 65 535	2 байта, без знака
LongWord	0.. 4 294 967 295	4 байта, без знака

Машинно-ориентированные целые типы в Delphi представлены типами Integer и Cardinal. Тип Integer эквивалентен базовому типу Longint, а тип Cardinal – типу LongWord. Фактически они представляют собой знаковое и беззнаковое четырехбайтные числа.

Базовыевещественные типы

Имя типа	Минимальное значение	Максимальное значение	Точность (число цифр мантиссы)	Память, байт
Real48	2.9´10^–39	1.7´10³⁸	11–12
Single	1.7´10^–45	3.4´10³⁸	7–8
Double	5.0´10^–324	1.7´10³⁰⁸	15–16
Extended	3.6´10^–4951	1.1´10⁴⁹³²	19–20
Comp	–2´10⁶³+1	2´10⁶³–1	19–20
Currency	–922 337 203 685 477.5808	922 337 203 685 477.5808	19–20

Машинно-ориентированный вещественный тип представлен типом Real, который эквивалентен базовому типу Double.

Значениями символьного типа являются отдельные символы. Базовыесимвольные типы представлены типами AnsiChar и WideChar.

Символ типа AnsiChar занимает один байт, а для кодирования символов используется код ANSI Американского национального института стандартов (American National Standards Institute). Символ типа WideChar занимает два байта, а для кодирования символов используется международный набор символов Unicode. Набор символов Unicode включает в свой состав более 60 тысяч элементов. Первые 256 символов Unicode совпадают с кодом ANSI.

Кроме базовых символьныхтипов в языке Delphi определен машинно-ориентированный тип Char, который эквивалентен типу AnsiChar.

7. Особенности работы программы в консольном режиме

Поскольку код программы представлен в кодировке Windows, а вывод в консольном режиме осуществляется в кодировке DOS, то возможны проблемы с выводом русских букв. Если такие проблемы имеют место, то следует использовать функцию перекодировки символов из кодировки Windows в кодировку DOS. Таблица кодов русских букв в кодировках Windows и DOS, а также текст функции перекодировки с именем WinDOS приведёны ниже.

Кодировка русских букв в соответствии со стандартами
ASCII (DOS) и ANSI (Windows):

Буквы	Коды	Разность кодов ANSI и ASCII
ANSI (Windows)	ASCII (DOS)
А..Я	192..223	128..159
а..п	224..239	160..175
р..я	240..255	224..239
Ё	168	240	–72
ё	184	241	–57

function WinDOS(const s: string): string;

// Перекодировка русских символов строки s из ANSI (Windows) в ASCII (DOS)

var i: Word; // Номер символа в строке

Begin

Result:=s; // копирование исходной Windows-строки в строку-результат

for i:=1 to Length(s) do begin

case Result[i] of

'А'..'п': Dec(Result[i],64); // уменьшение кода ANSI на 64

'р'..'я': Dec(Result[i],16); // уменьшение кода ANSI на 16

'Ё': Inc(Result[i],72); // увеличение кода ANSI на 72

'ё': Inc(Result[i],57); // увеличение кода ANSI на 57

end; // case

end; // for

end; // WinDOS

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

Writeln(WinDOS(‘Результаты обработки матрицы А’));

Тема 1. УКАЗАТЕЛИ И ДИНАМИЧЕСКИЕ ПЕРЕМЕННЫЕ

1. Статические и динамические переменные

Переменные, объявляемые в разделе var главной программы, называются статическими переменными потому, что они являются составной частью программы и существуют в виде ячеек памяти в течение всего времени пребывания программы в ЭВМ. Размещаются статические переменные в сегменте данных программы, память для них выделяется на этапе компиляции, а их физические адреса устанавливаются на этапе загрузки.

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

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

2. Указатели

Работа с динамической памятью осуществляется с помощью величин, называемых указателями. Значение указателя – адрес участка памяти, в котором могут располагаться переменная или подпрограмма. Компилятор отводит под указатель 4 байта памяти. Различают типизированные и нетипизированные (нейтральные) указатели.

Синтаксическая форма описания типизированного указателя:

^BaseType,

где ^ – синтаксический атрибут (символ каре); BaseType – идентификатор типа, называемого базовым типом (любой тип Delphi).

В Delphi действует принцип – любой идентификатор может использоваться только после его определения; для идентификатора базового типа сделано исключение – его можно определять после использования в описании указателя; указанное исключение позволяет создавать списковые структуры данных в динамической памяти.

Описатель ^BaseType может использоваться и в разделе программы type для описания идентификатора типа, и в разделе var для описания конкретных переменных-указателей.

Пример. Описание типизированных указателей.

Type

tArr= array [1..10] of Real;

pArr=^tArr;

Var

p1: pArr;

p2: ^Real;

p3: ^Integer;

Типизированные указатели могут использоваться для хранения адресов объектов только базового типа. Нейтральные указатели могут использоваться для хранения адресов объектов любого типа. Они описываются с помощью ключевого слова Pointer.

Пример. Описание нейтральных указателей.

var p1, p2: Pointer;

3. Операция получения адреса

Операция получения адреса является унарной, кодируется символом @ (коммерческое ИЛИ, транскрипция названия символа – æt) и имеет следующую синтаксическую форму:

где X –идентификатор переменной или подпрограммы.

Конструкция @X представляет собой выражение, тип которого определяется по следующему правилу:

1) если X – имя переменной, то при использовании опции компилятора {$T–} выражение @X имеет тип нейтрального указателя (Pointer); при использовании опции {$T+} выражение @X имеет значение типизированного указателя, базовый тип которого совпадает с типом переменной X;

2) если X – имя подпрограммы, то выражение @X имеет тип нейтрального указателя (Pointer) независимо от установки опции {$T}.

4. Функции и процедуры для работы с динамической памятью

· function Addr(var X): Pointer;

Возвращает адрес переменной или подпрограммы с именем X. В отличие от операции @ функция Addr(X) всегда возвращает адрес только в виде нейтрального указателя, независимо от установки опции {$T}.

· procedure GetMem(var p: Pointer; Size: Word);

Выделяет в куче непрерывный участок (блок) памяти размером Size байт, адрес начального байта этого блока присваивается указателю p.

· procedure FreeMem(var p: Pointer; Size: Word);

Освобождает блок памяти размером Size байт, адрес которого хранится в указателе p; значение указателя p, согласно спецификации языка, становится неопределенным; фактически значение p не изменяется.

· procedure New(var p: Pointer);

Создает в куче динамическую переменную того типа, на которую ссылается указатель p, адрес начального байта этой переменной присваивается указателю p; заметим, что обращение к данной процедуре эквивалентно обращению GetMem(p, SizeOf(p^)); напомним, что функция SizeOf(X) возвращает размер переменной X в байтах.

· procedure Dispose(var p: Pointer);

Освобождает блок памяти, занимаемый динамической переменной, адрес которой хранится в указателе p; значение указателя p, согласно спецификации языка, становится неопределенным; фактически значение p не изменяется; заметим, что обращение к данной процедуре эквивалентно обращению FreeMem(p,SizeOf(p^)).

Процедуры GetMem и FreeMem, New и Dispose являются парными.

5. Присваивание значений указателям

Присвоить значение указателю p можно двумя способами:

1) с помощью оператора присваивания

p:=e

где e – выражение, значение которого представляет собой адрес, то есть выражение типа указателя;

2) путем обращения к процедуре, используя p в качестве фактического параметра-переменной.

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

В Delphi определен идентификатор nil константы, называемой пустым адресом, или адресным нулем. Константа nil не адресует никакой объект. По присваиванию она совместима со всеми указателями: как нейтральными, так и типизированными.

6. Организация ссылок

Ссылка – это способ доступа к объекту программы и соответствующая синтаксическая конструкция.

В Delphi реализованы три формы ссылок на переменные:

1) имя переменной;

2) приведение типа;

3) типизированный указатель с последующим квалификатором разыменования.

Предметом изучения в настоящей теме являются ссылки в форме переменной с последующим квалификатором разыменования, имеющие следующую синтаксическую форму

где p – типизированный (не нейтральный!) указатель.

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

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

var x: Real; p: ^Real;

Begin

p:=@x; // теперь p^ и x – синонимы

p^:=7.25; // то же самое, что x:=7.25

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

Наиболее часто динамическая память используется для организации динамических списковых структур данных, кратко называемых списками. Определение «динамическая» по отношению к списковой структуре выражает два аспекта этого понятия: 1) логический – количество элементов в списке может динамически изменяться (увеличиваться и уменьшаться); 2) реализационный – структура создается и уничтожается в динамической памяти во время работы программы. В логическом плане размер списка ничем не ограничен; в реализационном плане он ограничен размером кучи.

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

Список, в котором нет ни одного элемента, называется пустым.

Реализация списка с помощью динамических переменных:

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

Список List можно описать следующим образом:

Type

tValue=Real; // тип значения элемента списка – вещественный

pItem=^tItem; // тип указателя на элемент списка

tItem= record // тип элемента списка

Value: tValue; // содержательная часть элемента списка

Next: pItem; // указатель на следующий элемент списка

end; // tItem

var List: pItem; //идентификатор списка – указатель на его первый элемент

При работе со списком используются следующие основные операции: создание пустого списка; включение элементов в начало, конец и в произвольное место списка; исключение элементов из начала, конца и из произвольного места в списке; получение информации о количестве элементов в списке; очистка списка; поиск элемента с заданным значением; вывод элементов списка на печать и др. Операции со списком следует оформлять в виде подпрограмм, одним из параметров которых является идентификатор списка типа pItem.

8. Реализация основных операций со списком

Создание пустого списка:

procedure Create(var List: pItem);

Begin

List:= nil;

end;

Включение элемента со значением v в начало списка List:

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

procedure InsertFirst(var List: pItem; v: tValue);

// Включение элемента со значением v в начало списка List

var NewItem: pItem; // указатель на новый элемент списка

Begin

New(NewItem); // выделение памяти под новый элемент списка

NewItem^.Value:=v; // запись значения v в поле Value нового элемента

NewItem^.Next:=List; // новый элемент ссылается на первый

List:=NewItem; // новый элемент становится первым

end;

Включение элемента со значением v в конец списка List:

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

procedure InsertLast(var List: pItem; v: tValue);

// Включение элемента со значением v в конец списка List

var NewItem, LastItem:pItem; // указатели на новый и последний элементы

Begin

New(NewItem); // выделение памяти под новый элемент списка

NewItem^.Value:=v; // запись значения v в поле Value нового элемента

NewItem^.Next:= nil; // новый элемент становится последним в списке

if List= nil // если список пуст,

then List:=NewItem // то новый элемент становится первым в списке

else begin // список не пуст – поиск последнего элемента:

LastItem:=List; // устанавливаем LastItem на начало списка,

while LastItem^.Next<> nil do begin // пока не достигнут конец списка,

LastItem:=LastItem^.Next; // сдвигаем LastItem на следующий элемент

end;

LastItem^.Next:=NewItem; // новый элемент следует за последним

end;

Исключение первого элемента списка List:

function DeleteFirst(var List:pItem):tValue;

// Исключение первого элемента списка List и возвращение его значения

var DisItem: pItem; // указатель на удаляемый элемент списка

Begin

if List= nil // если список пуст, то удаление невозможно

Then begin

Writeln('Список пуст'); Halt; end

else begin // список не пуст – удаление:

DisItem:=List; // устанавливаем DistItem на начало списка,

List:=List^.Next; // устанавливаем List на второй элемент списка,

DeleteFirst:=DisItem^.Value; // возвращаем значение удаляемого элемента

Dispose(DisItem); // и удаляем первый элемент списка

end;

Исключение последнего элемента списка List:

function DeleteLast(var List:pItem):tValue;

// Исключение последнего элемента списка List и возвращение его значения

var DisItem, // указатель на удаляемый (последний) элемент списка

PredItem: pItem; // указатель на элемент, предшествующий удаляемому

Begin

if List= nil // если список пуст, то удаление невозможно

Then begin

Writeln('Список пуст'); Halt;

End

else begin // список не пуст – удаление:

// Поиск последнего (удаляемого) и предпоследнего элементов списка

DisItem:=List; PredItem:= nil;

while DisItem^.Next<> nil do begin // пока не достигнут конец списка:

PredItem:=DisItem; // сдвиг PredItem на следующий за ним элемент

DisItem:=DisItem^.Next; // и сдвиг DisItem на следующий за ним элемент

end;

if PredItem= nil // если в списке один элемент,

then List:= nil // то после его удаления список станет пустым

// иначе предпоследний элемент становится последним

else PredItem^.Next:= nil;

DeleteLast:=DisItem^.Value; // возвращаем значение удаляемого элемента

Dispose(DisItem); // удаляем последний элемент списка

end;

Вывод в файл f элементов списка List:

procedure WriteList(var f: Text; List: pItem);

// Вывод в файл f элементов списка List

var Item:pItem; // указатель на элемент списка

Begin

Item:=List; // устанавливаем Item на начало списка

while Item<> nil do begin // пока не достигнут конец списка:

Write(f, Item^.Value:8:2); // выводим значение элемента

Item:=Item^.Next; // и сдвигаем указатель Item на следующий элемент

end;

Writeln(f);

end;

Удаление всех элементов списка List:

procedure Clear(var List: pItem);

// Удаление элементов списка

var Item: pItem; // указатель на удаляемый элемент списка

Begin

while List<> nil do begin // пока список не пуст:

Item:=List; // устанавливаем Item на начало списка,

List:=List^.Next; // передвигаем начало списка на следующий элемен т

Dispose(Item); // и удаляем первый элемент

end; // while

end;

Вычисление размера списка List:

function Size(List: pItem): Word;

// Возвращение количества элементов списка

var Item:pItem; // указатель на элемент списка

Begin

Item:=List; // устанавливаем Item на начало списка

Result:=0; // обнуляем счетчик числа элементов

while Item<> nil do begin // пока не достигнут конец списка:

Item:=Item^.Next; Inc(Result); // сдвигаем Item и увеличиваем счетчик

end; // while

end;

Контрольные вопросы

1. Какие переменные программы называются статическими, где они размещаются и на каком этапе под них выделяется память?

2. Какие переменные называются динамическими, где они размещаются и на каком этапе под них выделяется память?

3. Что представляет собой значение указателя?

4. Адреса каких объектов могут хранить типизированные указатели и как они описываются?

5. Адреса каких объектов могут хранить нетипизированные указатели и как они описываются?

6. Каковы характеристики операции получения адреса?

7. Какие функции используются для работы с адресами?

8. Какие процедуры используются для работы с указателями?

9. Каким образом можно присвоить значение переменной-указателю?

10. Что такое ссылка на переменную?

11. Какие структуры данных называют динамическими?

12. Что такое список и как он реализуется с помощью динамических переменных? Как можно описать список в программе?

13. Какие операции определены для работы со списком?

Лабораторная работа 1.
Организация списков
с помощью динамических переменных

Задание

1. Опишите следующие подпрограммы работы со списком: Create(L) – создание пустого списка L; InsertFirst(L, v) – включение элемента со значением v в начало списка L; Size(L) – определение количества элементов списка L; WriteList(f, L) – вывод в файл f элементов списка L; Clear(L) – удаление всех элементов списка L. Тип элемента списка указан в столбце 2 таблицы вариантов заданий (табл. 1).

2. Составьте подпрограмму или подпрограммы обработки списка, указанные в столбце 3 табл. 1. Спецификации всех подпрограмм приведены в табл. 2.

3. С использованием разработанных подпрограмм составьте программу работы со списками в соответствии с вашим вариантом задания (столбец 4).

В программе необходимо:

1) сформировать исходные списки с помощью процедур Create и InsertFirst, вводя элементы из текстового файла;

2) определить размеры исходных списков с помощью процедуры Size;

3) для контроля вывести в текстовый файл размеры исходных списков и их элементы с помощью процедуры WriteList;

4) выполнить задание на обработку списков, указанное в вашем варианте (столбец 4 табл. 1);

5) вывести в текстовый файл результ

Воспользуйтесь поиском по сайту: