10. Построение структур данных

Данные бывают двух видов:

Простейшие данные – элементы данных, являющиеся неделимыми (числа, строки, знаки). Для простейших данных существуют стандартные типы (Integer,Real, Char, String, Boolean).

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

Массив – структура однотипных данных с индексированным доступом.

Запись – структура данных с доступом по идентификатору.

Массивы

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

Массивы бывают следующих видов:

Одномерные – каждый элемент массива получает два индекса (пр. [2,3]).

Многомерные – каждый элемент получает более 2-х индексов (пр. [1,1,k]).

Описание массивов

Каждый из индексов массива находится в некотором диапазоне (<нач. элемент>…<кон. элемент>). Причем конечный элемент больше либо равен начальному элементу. В качестве диапазона можно использовать: Integer, Char, Boolean.

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

Var <переем. массив>: array[<диапазон 1>..<диапазон N>]

Of <тип переменной>;

Пример: список студентов группы

Var Spisok: array[1..40] String[20];

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

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

<перем. массив>[<индекс>,..,<индекс N>]

Пример:

Spisok[1]:=’Иванов’;

Ввод массива с клавиатуры

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

<приглашение к вводу массива>;

<ввод количества элементов массива>;

For i:=1 to <кол-во элементов> do

Begin

<приглашение к вводу i-го элемента>;

<ввод i-го элемента>;

End;

Пример:

WriteLn (‘ввод списка студентов’);

WriteLn (‘введите количество студентов’);

ReadLn (kolvo);

For i:=1 to kolvo do

Begin

WriteLn (i,’ ’);

ReadLn (spisok[i]);

End;

Вывод массива на экран

Вывод в строку. При выводе массива в строку нужно использовать Write, которая будет находиться в цикле с параметром, а после цикла нужно поставить WriteLn.

Пример:

For i:=1 to kolvo do

Write(spisok[i],’ ‘);

WriteLn;

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

Пример:

For i:=1 to kolvo do

Write (i:2,’. ’,spisok[i]);

Действия с массивами

Над массивами нельзя выполнять арифметические действия (вычитать, складывать и др.). Все действия выполняются поэлементно.

Пример: Написать программу, которая выполняет поэлементное суммирование массивов A и B.

Program Summ;

Var A,B Array [1..10] of Integer;

Kolvo:Integer;

C: Array [1..10] of Integer;

i: Integer;

Begin

WriteLn (‘введите количество элементов массивов’);

ReadLn (Kolvo);

WriteLn (‘введите элементы маcсива A’);

For i:=1 to Kolvo do

begin

Write(i, ‘) ’);

ReadLn (A[i]);

end;

WriteLn (‘введите элементы маcсива B’);

For i:=1 to Kolvo do

begin

Write(i, ‘) ’);

ReadLn (B[i]);

end;

For i:=1 to Kolvo do

C[i]:= A[i]+B[i];

For i:=1 to Kolvo do

Writeln (C[i]:5);

End.

Двухмерные массивы

Ввод построчно

<приглашение ввода массива>;

<цикл по строкам>;

Begin

<приглашение ввода строки>;

<цикл по столбцам>;

Begin

<приглашение ввода элемента>;

<ввод элемента массива>;

End;

End.

Ввод по столбцам

<приглашение ввода массива>;

<цикл по столбцам>;

Begin

<приглашение ввода столбца>;

<цикл по строкам>;

Begin

<приглашение ввода элемента>;

<ввод элемента массива>;

End;

End

11.

СТРОКИ

Тип STRING (строка) в Турбо Паскале широко используется для обработки текстов. Он во многом похож на одномерный массив символов ARRAY [0..N] OF CHAR, однако, в отличие от последнего, количество символов в строке – переменной может менятся от 0 до N, где N – максималльное количество символов в строке. Значение N определяется объявлением типа STRING[N] N и может быть любой константой порядкового типа, но ен больше 255. Турбо Паскаль разрешает не указывать N, в том случае длина строки принимается максимально возможной, а именно N=255.

Строка в Турбо Паскале трактуется как цепочка символов. К любому символу в строке можно обратиться точно так же, как к элементу одномерного массива ARRAY [0..N] OF CHAR.

Множественный тип данных Паскаля

Множественный тип данных Паскаля напоминает перечислимый тип данных. Вместе с тем множественный тип данных – набор элементов не организованных в порядке следования.

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

Понятие множества в языке программирования значительно уже математического понятия.

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

В качестве базовых типов могут использоваться:

перечислимые типы;

символьный;

байтовый;

диапазонные на основе вышеперечисленных.

Такие ограничения связаны с формой представления множественного типа данных в Паскале и могут быть сведены к тому, чтобы функция ord() для используемого базового типа лежала в пределах от 0 до 255.

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

Символьный тип (Char) - это тип данных, состоящих из одного символа (знака, буквы, кода). Значением типа Char может быть любой символ из набора ASCII. Если символ имеет графическое представление, то в программе он записывается заключенным в одиночные кавычки (апострофы), например:

'ж' 's' '.' '*' ' '-(пробел)

Для представления самого апострофа его изображение удваивается: ''''.

Если же символ не имеет графического представления, например, символ табуляции или символ возрата каретки, то можно воспользоваться эквивалентной формой записи символьного значения, состоящего из префикса # и ASCII-кода символа:

#9 #32 #13

Допустимые операции:

- присваивание;

- сравнение: <, >, >=, <=, <>, =. Большим считается тот символ, который имеет больший ASCII-номер.

12. Комбинированный тип данных (записи)

Запись - тип данных, состоящий из фиксированного числа компонентов (называемых полями) одного или нескольких типов.

Приведём примеры описания типа запись:

type Point=RECORD

x,y: Real

END;

Dates=RECORD

day : 1..31;

mon : String[3];

year: 1..3000

END;

var p,r: Point;

dt: Dates;

Можно определить массив записей, поля которых также являются массивами:

type Student=Array [1..N] of Record

fam : String[15];

birth: Dates;

man : Boolean;

marks: Array[1..10] of 0..5

end;

var Group: Student;

Идентификатор Group можно использовать для хранения информации о группе студентов (фамилия, дата рождения, пол и оценки по 10 предметам).

Обращение к значению поля записи происходит при помощи составного имени, содержащего идентификатор переменной и имя поля, разделённые точкой. Например, p.x, dt.mon, group[1].man, group[2].marks[1].

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

Обращение к полю записи с помощью составного имени может иметь громоздкий вид. Оператор WITH, решающий эту проблему, имеет следующий вид:

WITH <Переменная типа запись> DO <Оператор>

Если после слова WITH задать имя записи, то в операторе, следующим за DO, для доступа к полю можно указывать только имя поля без имени переменной.

Записи с вариантами

Записи могут иметь варианты. В качестве примера приведём исследование для проверки качества

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

Мы используем две структуры данных типа запись: Nomer

Proverka

Prinimal

Nomer

Proverka

GolovBol

Lihoradka

Toshnota

Что можно сделать с описаниями переменных, чтобы мы могли работать одновременно с обеими структурами? Для этого в описании записи можно применить специальный переключатель Case. После возможного результата Proverka в скобках приводится описание соответствующих полей. Это иллюстрируется ниже:

type Effect=Record

Nomer: Integer;

Case Proverka: Boolean of

FALSE: (PrinimalRanee: Boolean);

TRUE : (GolovBol,Lihoradka,Toshnota: Boolean)

end;

var Nekto: Effect;

Переключатель Case используется здесь для описания переменных и отличается от оператора Case: в переключателе Case используются скобки и отсутствует служебное слово end, обязательное в конце "обычного" Case.

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

В случае, когда один из вариантов не содержит полей (т.е. список полей пуст), в скобках после соответствующей константы ничего не пишут, например:

Type Pogoda=Record

Temperatura: Integer;

Vlagnost : Integer;

Case Veter: Boolean of

TRUE : (Napravlenie: (S,N,V,O); Skorost : Integer);

FALSE: ()

end;

Замечания.

После вариантной части записи поля появляться не могут.

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

Вариантная часть может содержать другие записи, в том числе и с вариантами. Степень вложенности записей в вариантной части не ограничена

13. Стандартные процедуры и функции при работе с файлами в Паскале

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

1) assign(fail, filename)

обеспечивает связь файловой переменной fail с физическим файлом. Полное имя этого физического файла помещено в строку filename. Закрепленная связь будет действительной до конца выполнения программы, либо пока не будет произведено некое переназначение.

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

2) reset(fail)

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

Если fail является типизированным файлом, то при использовании процедуры reset происходит открытие этого файла для чтения и записи единовременно.

3) rewrite(fail)

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

4) close(fail)

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

5) eof(fail):boolean

принимает значение истина (true), если при чтении был достигнут конец файла. Данная ситуация означает, что последний элемент файла уже прочтен, либо файл оказался пустым после открытия.

6) rename(fail,failnewname)

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

7) erase(fail)

осуществляет уничтожение физического файла на диске, связанного с файловой переменной fail. Как и в случае с rename, так и в нашем случае процедура erase выполняется по окончании закрытия файла.

8) ioresult

функция, возвращающая целое число, которое соответствует коду конечной ошибки ввода/вывода. В случае нормального завершения операции данная функция вернет значение 0. Необходимо присвоить какой-нибудь переменной значение рассматриваемой функции ioresult, поскольку при каждом следующем вызове она обнуляет свои значения. Работа функции ioresult возможна лишь в выключенном режиме проверки ошибок ввода/вывода, либо с использованием ключа компиляции {$I-}.

15. <<Графика в Паскале>> (Turbo Pascal). Примеры компьютерной графики

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

Цель урока – это познакомиться с возможностями графических операторов,построение графических изображений в Паскале.

Следует отметить, что графическое изображение на экране составляется из точек (например, как фотографии в газетах, журналах и др.). Количество точек (пикселей) на экране зависит от разрешающей способности экрана. Каждая точка задается двумя координатами (x, y). Точка с координатами (0,0) находится в левом верхнем углу экрана. Ось Х направлена вправо, а ось У вниз.

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

1. Переключить монитор в графический режим с помощью оператора InitGraph (Driver, mode, <путь к драйверу>).

2. Установить разрешающую способность экрана по умолчанию режимом Detect или процедурой SetGraphMode. Режим Detect устанавливает разрешающую способность экрана 640*480 пикселей, т.е. координата Х может принимать значения от 0 по 639, а У от 0 по 479.

3. Очистить и инициализировать графический экран процедурой ClearDevice.

4. Установить цвет фона оператором SetBkColor и цвет изображения оператором SetColor.

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

6. Вывести на экран закрашенные фигуры.

7. Вывести тексты и подписи на экран. Для использования операторов Write и Writeln в графическом режиме необходимо выполнить следующую операцию присваивания : DirectVideo := FALSE; Или использовать процедуру Outtextxy(x,y,st), которая выводит строку st, начиная с позиции x, y.

Цвета в операторах задаются с помощью своих кодов:

0 – черный; 4 – красный; 8 – темно-серый; 12 – ярко-красный;

1 – синий; 5 – пурпурный; 9 – ярко-синий; 13 – ярко-пурпурный;

2 –зеленый; 6 – коричневый; 10 – ярко-зеленый; 14 – желтый;

3 – бирюзовый; 7 – светло-серый; 11 – ярко-бирюзовый; 15 – белый.

Цифровое кодирование цвета соответствует последовательности IRGB для 0-3 битов. Бит 3 – бит интенсивности I, бит 2 – бит красного R, бит 1 – бит зеленого G, бит 0 – бит синего B. Например, 11=8+2+1, т.е. биты 3,1,0 – интенсивный сине-зеленый (бирюзовый).

Основные графические операторы для построения изображений:

PutPixel (X, Y, цвет) - вывод точки на экран, где X, Y - координаты точки ;

Line ( X1, Y1, X2, Y2 ) - проводит линию из точки с координатами (X1, Y1 ) в точку с координатами ( X2, Y2 );

Rectangle (X1, Y1, X2, Y2 ) - прямоугольник со сторонами, параллельными осям координат; (X1, Y1) и (X2, Y2) - координаты, определяющие одну из диагоналей прямоугольника ;

Bar ( X1, Y1, X2, Y2 ) - закрашенный прямоугольник (без окантовки);

Circle ( X, Y, радиус ) – на экран выводится окружность с центром в точке ( X, Y )(тип integer) ;

Arc (X, Y, начальный угол, конечный угол, радиус) - на экран выводится дуга окружности с центром в точке (X, Y ); углы задаются в градусах; дуга рисуется ПРОТИВ часовой стрелки;

Ellipse ( X, Y, начальный угол, конечный угол, горизонтальный радиус, вертикальный радиус) - на экран выводится эллиптическая дуга с центром в точке с координатами ( X, Y ) (тип integer);

SetFillStyle (заполнение, цвет) – определение вида и цвета заполнения области;

FloodFill (x, y, цвет границы) – заливка замкнутой области.

Пример программы построения графика функции.

program graphic;

uses graph;

var driver, mode, errorcode : integer; xm,ym,i,j : integer;

pi,pi300,x1,y1,x2,y2, sc : real;

st1,st2,st3 : string;

function f(x:real) : real;

begin

f:=sin(x)+sin(2*x)+sin(3*x)-1-cos(x)-cos(2*x);{ функция для построения}

end; {графика}

begin

st1:='x';st2:='y';

st3:=' Press ENTER';

sc:=50;

driver:=9; {egavga}

mode:=2; {640х480 пикселей}

initgraph(driver,mode,'d:\bp\bgi'); {инициализация графического режима }

errorcode:=graphresult;

if errorcode<>grok then {ошибка }

begin

writeln('Error init Graph');

closegraph;

halt;

end;

xm:=getmaxx div 2;

ym:=getmaxy div 2;

{ xm=320;ym=240;центр экрана}

line(xm,20,xm,460);{ось y}

line(20,ym,620,ym);{ ось x}

outtextxy(630,ym,st1); {маркировка оси х}

outtextxy(xm,10,st2); {маркировка оси у}

pi:=3.1415926; pi300:=pi/300;

x1:=-pi;

for i:=0 to 24 do {разметка оси х вертикальными черточками}

begin

line(xm+round(80*x1),230,xm+round(80*x1),250);

x1:=x1+pi300*25;

end;

x1:=-pi; {собственно построение графика отрезками прямых}

while x1<pi do

begin

y1:=f(x1);x2:=x1+pi300;

y2:=f(x2);

line(xm+round(80*x1), ym-round(sc*y1),

xm+round(80*x2), ym-round(sc*y2));

x1:=x2;

end;

outtextxy(270,470,st3);

readln;

closegraph;

end.

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

16. В середине 80-х годов в программировании возникло новое направление, основанное на понятие объекта. Реальные объекты окружающего мира обладают тремя базовыми характеристиками: они имеют набор свойств, способны разными методами изменять эти свойства и реагировать на события, возникающие как в окружающем мире, так и внутри самого объекта. Именно в таком виде в языках программирования и реализовано понятие объекта, как совокупности свойств (структур данных, характерных для этого объекта), методов их обработки (подпрограмм изменения свойств) и событий, на которые данный объект может реагировать и которые приводят, как правило, к изменению свойств объекта.

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

Объектно-ориентированный подход использует следующие базовые понятия:

– объект – совокупность свойств (параметров) определенных сущностей и методов их обработки (программных средств) (объект содержит инструкции (программный код), определяющий действия, которые может выполнять объект, и обрабатываемые данные);

– свойство объекта – характеристика объекта, его параметр;

– метод обработки – программа действий над объектом или его свойствами;

– событие – изменение состояния объекта;

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

Объектно-ориентированный подход основан на трёх основополагающих концепциях:

– инкапсуляция;

– полиморфизм;

– наследование.

Рассмотрим эти концепции.

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

Например, класс «животное» имеет свойства «название», «размер», методы «идти» и «размножаться». Созданный на его основе класс «кошка» наследует все эти свойства и методы, к которым дополнительно добавляется свойство «окраска» и метод «пить».

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

Таким образом, наследование – это процесс, посредством которого один объект может приобретать свойства другого. Точнее, объект может наследовать основные свойства другого объекта и добавлять к ним черты, характерные только для него. Наследование является важным, поскольку оно позволяет поддерживать концепцию иерархии классов. Например, подумайте об описании жилого дома. Дом – это часть общего класса, называемого строением. С другой стороны, строение – это часть более общего класса – конструкции, который является частью ещё более общего класса объектов, который можно назвать созданием рук человека. В каждом случае порождённый класс наследует все, связанные с родителем, качества и добавляет к ним свои собственные определяющие характеристики. Без использования иерархии классов, для каждого объекта пришлось бы задать все характеристики, которые бы исчерпывающи его определяли. Однако при использовании наследования можно описать объект путём определения того общего класса (или классов), к которому он относится, с теми специальными чертами, которые делают объект уникальным.

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

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

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

В объектно-ориентированном программировании код и данные могут быть объединены вместе; в этом случае говорят, что создаётся так называемый «чёрный ящик». Когда коды и данные объединяются таким способом, создаётся объект. Другими словами, объект – это то, что поддерживает инкапсуляцию. Внутри объекта коды и данные могут быть закрытыми. Закрытые коды или данные доступны только для других частей этого объекта.

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

17. Рекурсивная реализация алгоритмов

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

F(n);

If n=0 or n=1 (проверка возможности прямого вычисления)

Then

F <-- 1

Else

F <-- n*F(n-1); ( рекурсивный вызов функции)

Return (F);

End;

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

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