![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Параметры-значения
Формальный параметр в этом случае считается обычной локальной переменной подпрограммы. Фактический параметр может быть произвольным выражением того же типа, что и формальный параметр. Пример: 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 выберем x1, то можно начать цикл с элемента номер 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 – Пример сортировки простым выбором
Для составления алгоритма снова воспользуемся методом пошаговой детализации. Отметим, что для получения результата нам нужно N-1 раз находить минимальное значение в последовательности, длина которой каждый раз уменьшается. Кроме того, так как минимальный элемент нужно менять местами с определенным элементом последовательности, то номер минимального элемента нужно запоминать. Обобщенно наш алгоритм можно записать так. 1. I: =1; 2. Пока I ≤ N-1 Начало 2.1. найти минимальный элемент и его номер в последовательности AI, …, AN. 2.2. поменять местами AI и минимальный элемент. 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,... AN, а значением К - номер этого элемента. Поэтому п. 2.2. можно записать конкретнее: 2.2. поменять местами элементы Ai и Ak Это можно сделать так: 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;
Рис. 2 - Вставить элемент в начало списка Операция включения элемента в начало списка определяет, как можно построить список: начиная с пустого списка, последовательно добавляя элементы в его начало. Пусть число связываемых элементов равно n. Тогда формировать список можно следующим образом: s: =nil; {начали с пустого списка} while n> 0 do begin new(p); p^.next: =s; read(p^.info); s: =p; n: =n-1 end;
|