Типы данных
Простые
Структурированные
а)статические структуры
б)динамические структуры
Рекурсия
Функция F является рекурсивной, если
1.F(N)=G(N,F(N-1)) , где G-известная функция
2.F(1)= известно
Поиск – обнаружение нужного элемента в некотором наборе (структуре)данных
Линейный поиск – (проверяются все элементы последовательно, пока не найдётся нужный) работа в коротких массивах.
Двоичный поиск – (ключ поиска сравнивается с ключом среднего элемента в массивах), для поиска в больших массивах.
Сортировка – переразмещение данных элементов в возрастающем или убывающем порядке.
При выборе метода сортировки, нужно учитывать количество сортированных элементов.
Сортировка методом выборки (из массива выбирается наименьший элемент и помещается на место первого элемента массива , за тем выбирается наименьший элемент из оставшихся и помещается во второй элемент массива и т.д.)
Ввести массив А(1…N)
For J=1 ,N-1, 1
Do
Мин. Элемент = А(J)
Индекс мин. Элемент =J
For I=J+1, N, 1
Do
If A(I)<мин.элемент
Then
Мин.элемент =А (I)
Индекс минимального элемента =I
End-if
End-do
A(индекс минимального элемента)=A(J)
A(J)= минимальный элемент
End-do
вывести А(1…N)
Сортировка включением
(элементы выбираются по очереди и помещаются в нужное место)
Ввести массив A(1…N)
For I=2, N =1 do
Temp=A(I)
A(0)=temp
J=I-1
While A(J)>temp
Do
A(7+1)=A(I)
J=J-1
End-do
A(J+1)=Temp
End-do
Вывести А(1…)N
3)Сортировка слияния-(два сортированных массива соединяются в один чтобы он стал сортированный)
Ввести массивы B(1…M), C(1…L)
I=1, J=1
For k=1, M+L,1
Do
If I>M
Then
A(k)=C(J), J=J+1
Else
If J>L
Then
A(k)=B(I), I=I+1
Else
If B(I)<C(J)
Then
A(k)=B(I), I=I+1
Else
A(k)= C(J), J=J+1
End-if
End-if
End-if
End-do
Вывести A(1…k)
Абстракция-суждение или представление о некотором объекте которое содержит только свойства, являющимися существенными в данном контексте.
Основные типы операций над объектом.
Конструктор - создает и анализирует объект.
Деструктор -освобождает объект т.е. разрешает его.
Модификатор -изменяет состояние объекта.
Базовые элементы языка программирования.
Синтаксис-это форма, семантика это смысл его выражения.
Есть терминальные (символы алфавита) и нетерминальные символы.
Терминалы (begin, end, array, const, if, then, else)
Форма Бенуса-Наура
<цифра>0I1I2I3I4I5I6I7I8I9
<условный оператор>if<логческоевыражение>then
If <логическое выражение>then<оператор>
Else<оператор>
Синтаксическая диаграмма
Оператор
Лог.выражение
оператор
Индетификатор (имя)-это строка символов, используемая для индентификации некоторой сущности в программе.
Константа- это элемент данных, значение которого не изменяется в процессе выполнения программы.
Значение констант:
Числа.
Вещественные числа.
Символы.
Логические константы.
Строки символов.
Оперативная память разбита на сегменты - непрерывные области памяти по 64кБ.
ОП -совокупность перекрывающихся сегментов.
Логический адрес ячейки:
Сегмент: смещение
Смещение-номер ячейки памяти.
Физический адрес = сегмент*10h+смещение
Переменная-это наименованная область в памяти компьютера выделенная для хранения информации, значения которой изменяется во времени выполнения программы.
Идентификатор переменной
тип
Типы с уникальными именами.
Идентификация типа
тип
Type
LighType = (red, yellow, green);
Var A,B, StreetLight : LightType;
Типизированная константа – с заранее заданным типом данных
А: real=5.6;
Логический тип данных
True = 1 False = 0
Правда Ложь
Var
X:Booleon;
Целочисленные типы
Bute 1 0…255
ShortInt 1 -128…127
Word 2 0…65535
Integer 2 -32768…32768
LongInt 4 -2 147 483 648…2 147 483 648
Div – деление
Mod – возвращение остатка целочисленного деления.
Арифметические операции сдвига
K shl N и K shr N
2 shl 7 = 256 (2)10 =(10)2 ;
161 shr 2 = 40 (161)10=(10100001)2
Операнд 1 Операнд 2 and or xor not
0 0 0 0 0 -
1 0 0 1 1 -
0 1 0 1 1 -
1 1 1 1 0 -
1 - - - - 0
0 - - - - 1
Лекция № 3
Символьный тип:
В основе кодировки лежит семибитный код ASCII. Символы с кодом 128…255 отводятся под национальный алфавит
Var
X: = ‘ф’;
X: =#228;
Под переменную типа Char отводится 1 байт пакета.
CHR (x) – преобразует выражение x: Byte в символ и возвращает этот символ;
UPCASE (x) – возвращает прописанную букву, если x – строчная латинская буква, в противном случае возвращает сам символ x.
Перечисляем тип:
Значение перечисляемого типа должны иметь синтаксис идентификаторов.
Type
Colors: (r, w, b);
Var
Color1, Color2, Color3;
Var
Color3: (r, w, b);
Color3: = red;
Тип диапазон: это подмножество базового типа.
Type
Digit1: = ‘1’…’9’;
Digit2: = ‘1’…’9’;
Var
Latcgt: ‘A’…’Z’;
Функции:
HIGH (x) – возвращает максимальное значение типа – диапазон;
LOW (x) – возвращает минимальное значение типа – диапазон;
Все значения порядкового типа можно упорядочить, с каждым из них можно сопоставить целое число, порядковый номер значения.
Целые типы: ORD (x) = x;
Логические типы: ORD (False) = 0, ORD (True) =1;
Символьный тип: ORD (x) – код символа x;
Перечисляемый тип: ORD (x) = целое число 0…65535 в соответствии с положением x системе;
Тип – диапазон: ORD (x) определяется свойствами базового типа;
Функции:
PRED (x) - возвращает предыдущее значение порядкового типа;
ORD (PRED (x)) = ORD (x) = 1;
SUCC (x) – возвращает следующее значение порядкового типа
ORD (SUCC (x)) = ORD (x) +1;
Var
C, D: Char;
Begin
C: = ‘f’; D: =PRED (C);
End.
Вещественные типы данных:
Название |
Длина, байт |
Кол-во значение цифр |
Диапазоны десятичного порядка |
Real |
6 |
11…12 |
-39…+38 |
Single |
4 |
7…8 |
-45…+38 |
Double |
8 |
15…16 |
-324…+308 |
Extended |
10 |
19…20 |
-4951…+4932 |
Comp |
8 |
19…20 |
-9.2*10^-18…+9.2*10^18 |
Представление типа данных вещественных чисел:
S Знак(1 бит) |
e Экспонент (d бит) |
m мантисса (r бит) |
1+d+r=8N, где N – число байт, отводимых под переменную данного типа.
S=0, если знак числа ‘+’; S=1, если знак ‘-’;
e – задаёт истинное значение числа t=e-(2^d-1);
m – задаёт мантиссу (дробную часть) m1=m*2^-r(0<=m1<1);
Записанное число может быть определено по формуле: (-1)^S*(1+m1)*2^t;
Все вещественные типы (кроме Real) вводятся в расчёте на арифметический сопроцессор – устройство, которое подключается непосредственно к центральному процессору и принадлежащему для выполнения операций над числами в формате с плавающей точкой и длинными, целыми числами. Сопроцессор всегда обрабатывает числа в формате Extended.
Операция отношений:
Операция |
Название |
Выражение |
Результат |
= |
Равно |
A=B |
True, если A=B |
<> |
Неравно |
A<>B |
T |
> |
Больше |
A>B |
True, если A>B |
< |
Меньше |
A<B |
True, если A<B |
>= |
Больше или равно |
A>=B |
True, если A>=B |
<= |
Меньше или равно |
A<=B |
True, если A<=B |
in |
Принадлежность |
A in B |
True, если A находится в множестве М |
rue,
если A=B
Операции |
Приоритет |
@, not |
1 (высший) |
*, /, div, mod, and, shr, she |
2 |
+, -, or, xor |
3 |
>, <, <>, =, <=, >=, in |
4 (низший) |
Выражение заключается в скобки, перед выполнением действий, считается как отдельный операнд;
Если операнд находится между двумя операциями с равным приоритетом, связываются с операцией, которая находится слева;
Структура программы:
Program <имя>;
Uses <имя1>, <имя2>…;
Label
1, m1, stop;
Const
MaxN: Word=100;
Kod=$124;
Type
Matrix=array [1...10] of Real;
Dni=1..31;
Var A, B, C: integer;
Result: Matrix;
Procedure <имя>;
<тело процедуры>;
Function <имя>;
<тело функции>;
Begin
<оператор>;
End.
Комментарий – это произвольный поясняющий текст в любом месте программы, заключается в фигурные скобки { } или между двойными символами (* *).
Всё что используется в программе, должно быть перед этим ОПИСАНО!!!
Директивы компилятора используются программистом для управления режимом компиляции, т.е. включает/выключает контроль ошибок, изменяет распределение памяти и т.д.
Управляющие структуры
Оператор – конструкция языка программирования, служащая для задания какого – либо действия или последовательности действий в программе над данными.
Любой оператор подразумевает некоторое действие;
Оператор присваивания:
Var w, h: integer;
Begin
w:=23;
h:=17;
w:=w+h;
end.
Простой и составной оператор:
Простой оператор не содержит в себе других операторов:
A: =11; B: =A*A; Writeln (A, B);
Составной оператор – последовательность операторов, рассматриваемых как единый:
Begin
A: = 11;
B: =A*A;
Writeln (A, B);
End.
Условный оператор:
Используется для программирования ветвей. В каждой ветви допускается запись только одного оператора:
If k>5 then
Begin
X: = X+5; y: =1;
End;
Else
y:=-1;
Вложенные условные операторы:
Альтернатива else, считается, принадлежит ближайшему условному оператору if, не имеющий своей ветви else.
If <условие1> then
If <условие2> then
<оператор А>;
Else
<оператор Б>;
Оператор множественного выбора:
Используются для реализации нескольких альтернативных вариантов действий, каждый из которых соответствует своим значениям некоторого параметра.
Case I of
1: x: =x+1;
2,3: x: =x+2;
4…9: begin
Writeln (x);
X: = x+3;
End;
Else
X: =x+x;
Writeln (x);
End.
Оператор цикла «Пока» (с предусловием)
Var F, N: LongInt;
Begin
F: =1; N: =1;
While N<=10 do
Begin
F: =F*N; Inc(N);
End;
Writeln (F);
End.
Оператор цикла с параметром (цикл по счётчику)
Var
I: integer;
C: char;
B: Boolean;
E: (E1, E2, E3, E4);
Begin
For I: = -10 to 10 do write (I);
For C: = ‘a’ to ‘z’ do write (C);
For B: = False to True do write (B);
For E: = E1 to E4 do
Begin
I: =ORD (E);
Writeln (I);
End;
End.
Оператор безусловного перехода:
Передаёт управление выполнением, в указанное с помощью метки, место программы. Метка может стоять в программе в любом месте между оператором и отделяется от второго оператора “:”
Label L1, L2;
Begin
…
Go to L1;
…
L1: go to L2;
…
L2: end.
Запрещает переходить по оператору go to между процедурами.
Процедуры Exit и Halt предназначены для выхода из программы блоков:
Halt – выход их программы;
Exit - выход из подпрограммы;
Break – реализует выход из цикла любого типа;
Continue – осуществляет переход на следующее поле цикла, игнорируя оставшиеся до конца тела операторы.
Лекция №4
Структурированные типы данных
Массивы – упорядоченная совокупность однотипных данных.
Type
Vector: = array [1…3] of real;
Var
R, V: Vector;
<тип элемента> массива – любой допустимый в Turbo Pascal тип, кроме файла.
Многомерный массив:
Type
Matrix: = array [0…5; 2…2, char] of real
Доступ к элементам массива:
Var m: Matrix; N: Byte;
Begin
…
m [1, 0; ‘d’]: = 5.2;
N: = 2;
m [N-1] [0] [‘n’]: = 6.3;
…
End.
Присваивание массивов:
Var
A, B: array [1…5] of real;
Begin
A: = B;
…
End.
Запись – структура данных, состоящих из фиксированного числа разнотипных компонентов, называемых полями записи.
Оператор присоединения:
With D do
Begin
R. Rx: = 2;
With R do
Rz: = ‘f’;
End;
Множества – структурированный тип данных, представляющий собой неупорядоченную совокупность неповторяющихся элементов. Количество элементов, входящих во множество, может меняться в пределах от 0 до 256.
Типы совместимы, если:
-Оба типа являются тождественными;
-Оба типа являются вещественными;
-Оба типа являются целыми;
-Оба типа являются поддиапазоном другого;
-Оба типа являются множествами, составленными из одного и того же базового типа;
-Оба типа являются строковым, а другой символьным или строковым;
-Оба типа являются указателем, а другой указателем или ссылкой;
Явное преобразование типов:
TRUNC (x) – преобразует значение вещественного типа в значение целого типа, отбрасывая дробную часть.
ROUND (x) - преобразует значение вещественного типа в значение целого типа, округляя его до ближайшего целого.
ORD (x) – преобразует значение порядкового типа в его номер.
CHR (x) – преобразует код символа в сам символ.
Type M2Word: = array [1…2] of Word;
M4 Byte: = array [1…4] of Byte;
Var V1: M2 Word; V2: M4 Byte;
V3: Long Int; V4: Integer;
Begin
V3: = 10; V1: = M2Word (V3);
V2: = M4 Byte (V3); V4: = Integer (V1 [1]);
End.
Неявное преобразование типов:
Реализуется в выражениях, составленных из вещественных и целочисленных переменных, последние автоматически преобразуется к вещественному типу, и всё выражение в целом преобразует вещественный тип.
Лекция №5
Подпрограммы и модули
Подпрограммы - представляют собой относительно самостоятельные фрагменты программы, оформленные особым способом и снабжённые именем.
Подпрограмма – независимый инструмент (исходный код), который предназначен для экономии ресурсов и памяти, т.к. каждая подпрограмма записывается всего один раз, а вызвать её можно несколько раз.
При разбиении максимально реализуется принцип нисходящего проектирования, – при котором исходный код программы представляется в виде последовательно относительно крупных подпрограмм.
Программа, вызываемая упоминанием в тексте программы, называется вызовом.
Program Calculator;
begin
Initialize;
Draw Screen;
Calculation;
Rest Screen;
end.
Машинные команды, из которых состоит любая программа, хранятся в кодовом сегменте ОЗУ, адрес которого находится в регистре процессора CS. Выполнение программы происходит путём последовательного чтения команд, начиная с первой, следующей выполняется команда, расположенная «выше» только что выполненной. Смещения относительно начала кодового сегмента, определяющего адрес выполняемой команды, процессор хранит в регистре IP. Пара CS,IP указывает на текущую команду и называется активной точкой программы.
Естественный порядок выполнения команд нарушается при обращении к подпрограмме.
Адрес точки возврата хранится в ячейках, специально выделенного сегмента ОЗУ, называется стеком. Кроме того, стек в памяти используется для хранения значений локальных переменных подпрограммы во время выполнения операторов, входящих в её тело.
Значение сегмента стека SS и текущее значение указателя вершины стека SP хранятся в соответствующих регистрах центрального процессора. Особенность заполнения стека в памяти состоит в том, что он заполняется сверху вниз, т.е. ячейки со смещением больше SP заняты, а меньшие – свободны.
Область видимости переменных:
Локальные – константы, типы, переменные, существующие только внутри процедур или функция, и объявленные либо в соответствующих разделах Const, Type, Var внутри данной процедуры или функции, либо в списке формальных параметров.
Глобальные - константы, типы, переменные – это те, которые объявлены в программе вне процедур или функций. Они доступны из любого места программы.
Область видимости переменных – это ряд операторов, в которых переменная «видна».
Время жизни переменной – это время, в течение которого переменная связана с определённой ячейкой памяти.
Program Main;
Var
Xmain, Ymain: integer;
Procedure Pl;
Var
Res: real;
Begin
Res: =0.5;
Ymain: =Res+ Xmain*Ymain;
Xmain: = Xmain+1;
End;
Var
Zmain: Extended;
…
Begin
…
Pl;
…
Параметры - обеспечивают обмен значениями между вызывающей частью программы и вызываемой подпрограммой. Параметры могут быть параметр – значением, параметр – переменной, параметр – константой. Описываемые в заголовке подпрограммы параметры называют формальными.
Procedure Pl (A: Integer; var B: Real);
А те, которые подставляются на их место при вызове – фактическими. Т.к. они при выполнении, как бы замещают, все вхождения в подпрограмму своих формальных «двойников».
Pl (A_fact, B_fact);
Параметр – значения – локальная переменная подпрограммы, стартовой значение которых, задаётся при вызове подпрограммы из внешних блоков.
Если параметр описан как параметр – переменная или параметр – константа, то в подпрограмму передаются адреса фактических параметров. Все изменения параметр – переменной в подпрограмме происходит с переменной, передаваемой в качестве фактического параметра. Параметр – константа не может изменяться в подпрограмме. На место фактического параметра – значения можно поставить литерал, выражающий идентификатор, а на место параметр – переменной и параметр – константы толь идентификатор.
Const
A: Integer =5;
B: Integer =7;
Procedure Plus (var C: integer; B: integer);
Begin
C: = C+C;
B: = B+B;
Writln (C,B);
End;
Begin
Writln (A,B);
Plus (A,B);
Writln (A,B);
End.
Функция – возвращает в вызываемый блок своё значение в виде скаляра, строки и указателя.
Var
X, Y: real;
Function Power (Arg, P: Real): Real;
Begin
If Arg<>0 then
Power: = exp (P*ln (abs (Arg)));
Else
If P: =0 then
Power: = 1
Else
Power: = 0;
End;
Begin
Readln (x;y);
Writln (x;y);
End.
Лекция №6