Автор работы: Пользователь скрыл имя, 26 Апреля 2012 в 21:22, курсовая работа
За время существования профессии программиста сущность его труда изменилась коренным образом. В 50-х годах программы писали в командах ЭВМ (в “машинных кодах”). При этом вся информация переводилась в двоичную систему счисления. Это очень тяжелый и напряженный труд, требующий от человека особой аккуратности. Облегченно вздохнули программисты при появлении в 1956 г. специального языка для решения вычислительных задач. Это был FORTRAN (Formula Translator). С тех пор были разработаны другие, более совершенные языки, или специализированные применительно к какой-то конкретной области: КОБОЛ, АЛГОЛ, ПЛ/1, ЛИСП, СИМУЛА, ПАСКАЛЬ, СИ, АДА, ПРОЛОГ и др.
При сравнении символов в Паскале фактически сравниваются их коды, выдаваемые функцией ord. Например, при сравнении С1<С2 сравниваются
ord (C1) < ord (C2).
Чтобы сравнить коды в новой системе кодировки, будем сравнивать новые коды литер
T [ord (C1)] < T [ord (C2)].
символ
старый код
новый код
Для
решения нашей задачи нужно таблицу
перекодировки (массив Т) заполнить следующим
образом. В приведенной таблице первая
строка показывает значение элемента
массива, вторая – его номер.
| 0 | 1 | 2 | … | 96 | 65 | … | 90 | 123 | … | 159 | 128 | … | 163 |
| 0 | 1 | 2 | … | 96 | 97 | … | 122 | 123 | … | 159 | 160 | … | 175 |
| 176 | … | 223 | 144 | … | 159 | 133 | 133 | 242 | … | 255 |
| 176 | … | 223 | 224 | … | 239 | 240 | 241 | 242 | … | 255 |
const T: array [0 .. 255] of Integer = (0, 1, 2, …);
С
учетом перекодировки
FUNCTION SCOMP (VAR S1, S2: STRING): INTEGER;
VAR I,R,N1,N2: INTEGER;
BEGIN
N1:= LENGTH (S1);
N2 := LENGTH (S2);
R:=0;
I:=1;
WHILE (I<=N1) AND (I<=N2) AND ( T [ ORD ( S1[I] ) ] = T [ ORD ( S2[I] ) ] ) DO
I:=I+1;
IF (I<N1) AND (I<N2) THEN
BEGIN
IF T [ ORD ( S1[I] ) ] < T [ ORD ( S2[I] ) ] THEN R:=-1;
ELSE R:=1;
END
ELSE
IF (I<N1) THEN R:=-1;
ELSE IF (I<N2) THEN R:=1
SCOMP:=R;
END;
Таким образом, результат равен:
0, если строки равны
-1, если S1 < S2,
1, если S1 > S2.
С помощью функции SCOMP мы можем организовать дихотомический поиск в упорядоченном массиве А строк из N элементов. Ищем значение A[I], равное строке P. Если такого значения нет, то I=0.
B:=1; L:=N; {временные границы}
WHILE B<L DO
BEGIN
C:= (B+L) DIV 2;
IF SCOMP (A[C], P) < 0
THEN B:=C+1;
ELSE L:=C;
END;
IF SCOMP (A[B], P) =0
THEN I := B;
ELSE I := 0;
Мы рассмотрели типы данных, которые принято называть простыми (INTEGER, REAL, CHAR, BOOLEAN). Паскаль характерен тем, что имеет хорошо развитую концепцию типов данных, позволяющую создавать достаточно сложные структуры, объединяющие данные различных типов.
Подробное изучение структур данных предусмотрено дисциплиной "Структуры и алгоритмы обработки данных в ЭВМ" (для специальности 220400). Здесь же мы рассмотрим лишь основы структурирования данных
В
частности, в Паскале существует
возможность объединения
Примером может служить
- телефоны, дата рождения – целые числа;
- остальные данные – символьные строки.
Информационная система деканата содержит, например, следующие сведения о студенте: Ф.И.О., курс, группа, оценки по отдельным предметам в каждую сессию, наличие и количество пересдач по каждому предмету и т.д. Эти сведения тоже представляют собой данные разных типов.
Каждая запись содержит фиксированное число компонент, называемых ее полями. Каждому полю записи дается свое имя, и задается тип значения этого поля. При этом никаких ограничений на тип поля записи не накладывается, поэтому компонентой поля записи может быть в свою очередь тоже запись и т.д. Таким образом, значение комбинированного типа может иметь иерархическую структуру.
Остановимся на простейшем случае, когда структура, задаваемая комбинированным типом, имеет один уровень иерархии.
Пусть нужно произвести некоторые действия над комплексными числами
а + bi, где a, b- вещественные, i2 = -1.
Так
как в Паскале нет
Каждое поле будет иметь тип REAL. Описание типа выглядит так:
TYPE COMPL = RECORD
Оно говорит о том, что любое значение типа COMPL есть структура данных, являющаяся записью, состоящей из двух компонент (полей), одной из которых дано имя RE, а другой IM, и каждая из компонент есть значение типа REAL. Описания, заключенные между служебными словами RECORD и END, образуют список полей, а каждое из описаний списка называется секцией записи. Более точное определение с помощью металингвистических формул:
<список полей> ::= <секция записи>{;<секция записи>},
<секция записи> ::= <имя поля>{,<имя поля>}:<тип поля>.
В нашем описании список полей состоит из двух секций, разделенных символом ‘;’, а каждая секция определяет одно поле. Поскольку оба поля имеют один и тот же тип, их можно объединить в одну секцию записи:
TYPE COMPL = RECORD
EN
Теперь, как обычно, можно в разделе переменных ввести переменные типа COMPL, например,
VAR X, Y: COMPL;
X,
Y называются полными
<имя полной переменной>.<имя поля>
Например, мы хотим переменной Х присвоить значение 5.65 + 0.77i. Для этого надо задать значения полям с именами RE и IM:
X.RE := 5.65;
X.IM := 0.77;
Теперь, если мы хотим, чтобы переменная Y приняла то же значение, мы должны сделать это с помощью оператора присваивания
Y := X;
Для полных переменных существует только одна операция – присваивание.
Пример. Программа вычисления суммы, разности и произведения двух комплексных чисел: U = X+Y, W = X-Y, V=X*Y, где X, Y, U, W, V – комплексные переменные.
PROGRAM COMPLAR (INPUT, OUTPUT);
TYPE COMPL = RECORD RE, IM: REAL; END;
VAR X, Y, U, W, V: COMPL;
BEGIN
READ (X.RE, X.IM, Y.RE, Y.IM);
U.RE := X.RE + Y.RE; U.IM :=X.IM +Y.IM;
W.RE:= X.RE - Y.RE; W.IM:=X.IM - Y.IM;
V.RE := X.RE*Y.RE – X.IM*Y.IM;
V.IM := X.RE*Y.IM + X.IM*Y.RE;
WRITELN (‘X+Y= ’, U.RE,’+’, U.IM, ’*i’);
WRITELN (‘X-Y= ‘, W.RE, ‘-‘, W.IM, ‘*i’);
WRITELN (‘X*Y= ‘, V.RE, ‘*’, V.IM, ‘*i’)
END;
В общем случае комбинированный тип определяется следующим образом.
TYPE
T = RECORD
S1: T1;
S2: T2;
…….
Sn: Tn;
END;
Здесь S1, …, Sn – имена компонент (полей) записи, T1, …, Tn – их типы. Типы полей могут быть самые разные, например,
TYPE DATE = RECORD
DAY: 1 .. 31;
MON: (JAN, FEB, APR, MAR, MAY, JUN, JUL, AUG, SEP, OCT, NOV, DEC);
YE
END;
Здесь в списке полей описания присутствуют, кроме известного нам стандартного простого типа данных INTEGER, два так называемых простых нестандартных типа.
DEC) – скалярный или перечисляемый (перечислимый) тип данных. При определении этого типа просто перечисляют все возможные значения переменных этого типа.
Переменным перечислимого типа можно присваивать только значения из перечня, заданного при определении типа.
Над переменными перечислимого типа можно выполнять только операции отношения. При этом считается, что значения упорядочены в соответствии с порядком их следования в списке описания типа. То есть