Параметры-значения

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

Пример: var a, b: integer;

procedure h(x: integer; var y: integer);

begin x: =x+1; y: =y+1;

writeln(x, ' ', y); end;

begin a: =0; b: =0;

h(a, b); =====> печать: 1 1

writeln(a, ' ', b) =====> печать: 0 1 end.

Тема 8. АЛГОРИТМЫ ПОИСКА И СОРТИРОВКИ. (1 часа)

План лекции 10:

1. Алгоритмы поиска: линейный поиск

2. Алгоритмы поиска: поиск с барьером

3. Алгоритмы сортировки: сортировка выбором

4. Алгоритмы сортировки: сортировка обменом (методом " пузырька")

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

Запишем пошаговую разработку алгоритма. Главное его свойство: все действия выполняются одинаково для всех элементов последовательности. Значит, основой его будет следующий цикл.

1. Инициализация цикла.

2. Пока есть элементы делай

Начало

2.1. Сравнить эталон с очередным элементом последовательности

2.2. Перейти к следующему элементу.

Конец.

Анализируем п.1. Нужно задать номер того элемента, с которого начнется сравнение, и определить эталон. Если в качестве эталонной переменной MIN выберем x₁, то можно начать цикл с элемента номер 2. Тогда

1. I: =2; MIN: =X[1];

Условие п.2. означает, что текущий номер элемента I не превысил заданную длину последовательности: I≤ N.

Шаг 2.1. – условный оператор. Его особенность – в отсутствии действий после иначе, поэтому можем записать укороченную форму оператора

2.1. IF X[I]< MIN

THEN MIN: =X[I];

Шаг 2.2. – в увеличении индекса I на 1:

2.2. I: =I+1;

Объединяя шаги детализации, получим алгоритм:

Ввод (последовательность Х);

I: =2; MIN: =X[1];

WHILE I< =N DO

BEGIN

IF X[I]< MIN

THEN MIN: =X[I];

I: =I+1;

END;

Вывод (MIN);

Простой выбор

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

Идея метода такова. Найдем в последовательности элемент с наименьшим значением и поменяем его местами с первым элементом. Затем проделаем те же действия с оставшимися N-1 элементами, затем с N-2 и так далее до тех пор, пока не останется один элемент – последний. Он будет наибольшим.

Проиллюстрируем процесс (табл.2.4).

Таблица 2.4 – Пример сортировки простым выбором

Номер элемента
Исходная последовательность
После выбора среди 8 элементов
7 элементов
6 элементов
5 элементов
4 элементов
3 элементов
2 элементов
Упорядоченная последовательность

Для составления алгоритма снова воспользуемся методом пошаговой детализации. Отметим, что для получения результата нам нужно N-1 раз находить минимальное значение в последовательности, длина которой каждый раз уменьшается. Кроме того, так как минимальный элемент нужно менять местами с определенным элементом последовательности, то номер минимального элемента нужно запоминать.

Обобщенно наш алгоритм можно записать так.

1. I: =1;

2. Пока I ≤ N-1

Начало

2.1. найти минимальный элемент и его номер в последовательности A_I, …, A_N.

2.2. поменять местами A_I и минимальный элемент.

2.3. I: =I+1;

Конец

Алгоритм поиска минимального элемента и его номера мы рассмотрели ранее, поэтому

2.1.

K: =I;

X: =A[I];

J: =I+1;

WHILE J< =N DO

BEGIN

IF A[J]< X

THEN BEGIN

X: =A[J];

K: =J;

END;

J: =J+1;

END;

В результате значением Х будет значение минимального элемента среди А_I,... A_N, а значением К - номер этого элемента. Поэтому п. 2.2. можно записать конкретнее:

2.2. поменять местами элементы A_i и A_k

Это можно сделать так:

2.2. C: =A[I]; А[I]: =A[K]; A[K]: =C;

Однако в нашей ситуации дополнительная переменная С не нужна, так как ее роль играет Х из п. 2.1. Поэтому запишем:

2.2. A[K]: =A[I]; A[I]: =X;

Мы сэкономили на одном присваивании, а так как действие выполняется в цикле, то это немало.

Теперь запишем полностью алгоритм сортировки простым выбором.

Ввод (последовательность А);

I: =1;

WHILE I< =N-1 DO

BEGIN

K: =I;

X: =A[I];

J: =I+1;

WHILE J< =N DO

BEGIN

IF A[J]< X

THEN

BEGIN

X: =A[J];

K: =J;

END;

J: =J+1;

END;

A[K]: =A[I];

A[I]: =X;

I: =I+1;

END;

Тема 9. ПРОГРАММИРОВАНИЕ В СРЕДЕ DELPHI. (1 часа)

План лекции 11:

1. Обзор интегрированной среды разработки

2. Классы компонентов

3. Свойства элементов

Для знакомства со средой программирования Delphi потребуется рассказать о составе первой страницы Палитры Компонент.

На первой странице Палитры Компонент размещены 14 объектов

(рис.1) определенно важных для использования. Мало кто обойдется длительное время без кнопок, списков, окон ввода и т.д. Все эти объекты такая же часть Windows, как мышь или окно.

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

Рис.1: Компоненты, расположенные на первой странице Палитры.

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

TMainMenu позволяет Вам поместить главное меню в программу. При помещении TMainMenu на форму это выглядит, как просто иконка. Иконки данного типа называют " невидимыми компонентом", поскольку они невидимы во время выполнения программы. Создание меню включает три шага: (1) помещение TMainMenu на форму, (2) вызов Дизайнера Меню через свойство Items в Инспекторе Объектов, (3) определение пунктов меню в Дизайнере Меню.

TPopupMenu позволяет создавать всплывающие меню. Этот тип меню появляется по щелчку правой кнопки мыши.

TEdit - стандартный управляющий элемент Windows для ввода. Он может быть использован для отображения короткого фрагмента текста и позволяет пользователю вводить текст во время выполнения программы.

TMemo - иная форма TEdit. Подразумевает работу с большими текстами. TButton позволяет выполнить какие-либо действия при нажатии кнопки во время выполнения программы. Нужно заполнить заготовку кодом (подчеркнуто то, что нужно написать вручную):

procedure TForm1.Button1Click(Sender: TObject);

begin

MessageDlg('Are you there? ', mtConfirmation, mbYesNoCancel, 0);

end;

TCheckBox отображает строку текста с маленьким окошком рядом. В окошке можно поставить отметку, которая означает, что что-то выбрано. Например, если посмотреть окно диалога настроек компилятора (пункт меню Options | Project, страница Compiler), то можно увидеть, что оно состоит преимущественно из CheckBox’ов.

TRadioButton позволяет выбрать только одну опцию из нескольких. Если Вы опять откроете диалог Options | Project и выберете страницу Linker Options, то Вы можете видеть, что секции Map file и Link buffer file состоят из наборов RadioButton.

TListBox нужен для показа прокручиваемого списка. Классический пример ListBox’а в среде Windows - выбор файла из списка в пункте меню File | Open многих приложений. Названия файлов или директорий и находятся в ListBox’е.

TComboBox во многом напоминает ListBox, за исключением того, что позволяет водить информацию в маленьком поле ввода сверху ListBox. Есть несколько типов ComboBox, но наиболее популярен выпадающий вниз (drop-down combo box), который можно видеть внизу окна диалога выбора файла.

TScrollbar - полоса прокрутки, появляется автоматически в объектах редактирования, ListBox’ах при необходимости прокрутки текста для просмотра.

TGroupBox используется для визуальных целей и для указания Windows, каков порядок перемещения по компонентам на форме (при нажатии клавиши TAB).

TPanel - управляющий элемент, похожий на TGroupBox, используется в декоративных целях. Чтобы использовать TPanel, просто поместите его на форму и затем положите другие компоненты на него. Теперь при перемещении TPanel будут передвигаться и эти компоненты. TPanel используется также для создания линейки инструментов и окна статуса.

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

Это полный список объектов на первой странице Палитры Компонент. Если Вам нужна дополнительная информация, то выберите на Палитре объект и нажмите клавишу F1 - появится Справочник с полным описанием данного объекта.

Инспектор Объектов состоит из двух страниц, каждую из которых можно использовать для определения поведения данного компонента. Первая страница - это список свойств, вторая - список событий. Если нужно изменить что-нибудь, связанное с определенным компонентом, то Вы обычно делаете это в Инспекторе Объектов. К примеру, Вы можете изменить имя и размер компонента TLabel изменяя свойства Caption, Left, Top, Height, и Width.

Тема 10. РАБОТА С ФАЙ­ЛАМИ. РАЗЛИЧНЫЕ ТИПЫ ФАЙЛОВ.

(1 часа)

План лекции 12:

1. Переменные файловых типов

2. Установочные и завершающие операции над файлами

3. Примеры работы с файлами

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

В результате совершения операций ввод-вывода текущий указатель может перемещаться, настраиваясь на тот или иной элемент файла. Один и тот же внешний файл в различных программах (или даже в различных частях одной и той же программы) может интерпретироваться по-разному, например как последовательность целых чисел или как последовательность некоторых массивов, и т.д.

< файловый тип>:: = file of < тип>

Тип элементов может быть любым, за исключением файлового.

Пример: type sequence=file of char;

var F1, F2: sequence; inputData: file of real;

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

assign(< идентификатор – файловая переменная>, < строковое выражение>);

Значение второго параметра – литеральное имя файла. Имя файла строится по правилам, принятым в операционной системе MS-DOS для именования файлов.

Пример:

assign(f, 'd: \mydir\myfile.dta');

После выполнения данного вызова файловая переменная f будет связана с файлом myfile.dta в каталоге mydir диска d.

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

· con - консоль, т.е. для случая вывода информация помещается на экране дисплея, а в случае ввода информация воспринимается с клавиатуры;

· prn - вывод на принтер;

· kbd - ввод с клавиатуры без «эха»;

· nul - фиктивное (несуществующее) устройство. Может использоваться для вывода информации «в никуда», когда в программе почему-либо нужно указать имя выходного файла, а информация, записываемая в него, не требуется.

Процедуры reset и rewrite имеют один параметр – файловую переменную и предназначены для открытия файлов. При этом файловая переменная, указываемая в качестве параметра, должна быть уже связана с конкретным дисковым файлом с помощью процедуры assign. Rewrite используется, и когда файл еще не существует, а если существует, то он очищается. Процедура close имеет один параметр – файловую переменную и завершает действия с файлом – ликвидируются внутренние буферы, образованные при открытии этого файла.

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

Процедуры write и read, в отличие от многих других процедур, могут вызываться с различным числом параметров, и эти параметры могут иметь различные типы.

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

Если указатель файла указывает на «конец файла», то чтение невозможно. Функция eof(< файловая переменная>) – булевская функция, равна истине, если имеется ситуация «конец файла».

Процедура write позволяет записывать в файл информацию из программы. Первым параметром этой процедуры должна быть файловая переменная, открытая процедурой reset или rewrite. Далее должен идти список переменных, тип которых совпадает с базовым типом файла из первого параметра.

Порядок выполнения процедуры write:

· Значение очередной переменной будет помещено в файл в место, отмеченное текущим указателем.

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

var s: string[126];

f: text;

begin

assign(f, 'name.pas');

reset(f);

while not eof(f) do

begin readln(f, s); write(s) end;

close(f)

end.

Представителем текстового файла в программе является переменная файлового типа, которая должна быть описана с указанием стандартного типаtext:

var

textInf: text;

Структура текстовых файлов отличается от структуры обычных файлов (линейная последовательность элементов одного типа) тем, что содержимое текстового файла рассматривается как п оследовательность символьных строк переменной длины, разделенных специальной комбинацией, называемой «конец строки». Как правило, эта комбинация строится из управляющего кода «перевод каретки» (символ #13), за которым, возможно, следует управляющий код «перевод строки» (символ #10). Текстовый файл завершается специальным кодом «конец файла» (символ #26).

Открытие текстового файла для чтения выполняет процедура reset. Открытие текстового файла для записи выполняет процедура rewrite.

Логическая функция eoln(< файловая переменная>) возвращает true, если текущая строка исчерпана, и false в противном случае.

Тема 11. ДИНАМИЧЕСКИЕ СТРУКТУРЫ ДАННЫХ. УКАЗАТЕЛИ. РАБОТА С ОЧЕРЕДЯМИ И СТЕ­КОМ. (2 часа)

План лекции 13:

1. Ссылочный тип

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

На языке Паскаль, программист может решать вопросы динамического распределения памяти, используя ссылочный тип данных.

Ссылочный тип определяется в следующем виде:

type

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

Примеры:

type

mas=array[1..10] of integer;

Ptr= ^integer;

link = ^mas;

linkchar = ^char;

tie = ^real;

Описание переменных ссылочного типа:

var

p: ptr;

v: link;

a: ^real;

Значение ссылочного типа (неформально) – адрес в памяти, где располагается конкретное значение базового типа. Есть специальный указатель, который «никуда не указывает». В адресном пространстве оперативной памяти выделяется один адрес, в котором заведомо не может быть размещена никакая переменная. На это место в памяти и ссылается такой пустой или «нулевой» указатель, который обозначается служебным словом nil.

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

· Сравнение на равенство (=), сравнение на неравенство (< >)

– ссылаются ли два указателя на одно и то же место в памяти?

Примеры: var p1, p2: ptr;

......

sign: =p1=p2;

if p1< > nil then....

Для того чтобы по указателю на переменную получить доступ к самой этой переменной, необходимо после переменной-указателя поставить знак '^'; p1^ есть «переменная», на которую ссылается p1. Такая конструкция может находиться в любом контексте, в котором допустимо нахождение самой указываемой переменной. Если p1 имеет тип ^integer, то p1^ имеет тип integer.

Разыменование некорректно, если ссылочная переменная имеет значение nil.

Поэтому p1: =nil;

p1^: =2;

некорректно и приводит к трудно распознаваемым ошибкам.

Пример: var p1, p2: ^integer;

Пусть переменные p1^ и p2^ уже имеют значения 1 и 2 соответственно (как это сделать - смотрите ниже). Тогда различные результаты следующих присваиваний изображены на рис. 1.

p1: =p2;

p1^: =p2^;

Исходное состояние:

После присваивания p1: =p2

После присваивания p1^: =p2^

Рис.1 Различия в присваиваниях

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

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

Процедура new(< переменная ссылочного типа>) предназначена для создания динамической переменной:

· в динамической области памяти отводится место для хранения переменной, тип которой совпадает с базовым типом указателя-переменной;

· переменной, переданной в параметре, присваивается указатель на отведенную область памяти.

Пример: type

mas=array[1..10] of integer; link=^mas;

var t: link;

........

new(t);

Отводится память, достаточная для хранения массива типа mas. Переменной t присваивается адрес этой памяти. Теперь возможен доступ к элементам массива, например:

t^[i]: =0;

t^[i]: =t^[j];

Переменная t является статической, место в памяти для ее значения выделено при трансляции. Переменная t^ – динамическая, она появляется только при выполнении процедуры new(t).

Процедура dispose(< переменная ссылочного типа>) служит для освобождения памяти, отведенной с помощью процедуры new с той же переменной.

Рис. 2 иллюстрирует применение процедур new и dispose (переменные p1 и p2 имеют тип ^ integer):

new(p1); new(p2);

p1^: =1; p2^: =2;

p1: =p2;

dispose(p2);

Рис. 2 - Результат выполнения фрагмента

План лекции 14:

1. Линейный список

2. Циклически связанный список

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

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

type

link = ^node;

node = record

info: string;

next: link

end;

var s, p: link;

Мы можем создать с помощью этого типа список, изображенный на рис. 5:

Рис. 1 - Список элементов типа link

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

new(p);

p^.info: ='Петров';

p^.next: =s;

s: =p;

Рис. 2 - Вставить элемент в начало списка

Операция включения элемента в начало списка определяет, как можно построить список: начиная с пустого списка, последовательно добавляя элементы в его начало.

Пусть число связываемых элементов равно n. Тогда формировать список можно следующим образом:

s: =nil; {начали с пустого списка}

while n> 0 do

begin

new(p); p^.next: =s;

read(p^.info);

s: =p; n: =n-1 end;