Программирование на ЭВМ

    При сравнении символов в Паскале  фактически сравниваются их коды, выдаваемые функцией 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;

    Контрольные вопросы и задания

1. Какой принцип  лежит в основе упорядочения символьных данных?
2. Оформите в виде процедуры алгоритм упорядочения символьных строк, заданных массивами символов.
3. Оформите в виде процедуры алгоритм поиска в неупорядоченном массиве символьных строк, заданных массивами символов.
4. Оформите в виде процедуры алгоритм поиска в упорядоченном массиве символьных строк, заданных массивами символов.
5. Что представляет собой строковый тип данных Паскаля?
6. Какие операции над строками допустимы в Паскале?
7. Назовите основные процедуры и функции для работы со строками в Паскале.
8. Напишите процедуру сортировки символьных строк методом простого обмена.
9. Напишите процедуру сортировки символьных строк методом простого выбора.
10. Напишите процедуру поиска заданной строки в неупорядоченном массиве символьных строк.
11. Напишите процедуру поиска заданной строки в упорядоченном массиве символьных строк.
12. Для каких целей используется и как осуществляется перекодировка символов?

5. Работа с нестандартными

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

    5.1. Записи. Перечислимый  и интервальный  типы 

           данных

        Мы рассмотрели типы данных, которые принято называть простыми (INTEGER, REAL, CHAR, BOOLEAN). Паскаль характерен тем, что имеет хорошо развитую концепцию типов данных, позволяющую создавать достаточно сложные структуры, объединяющие данные различных типов.

    Подробное изучение структур данных предусмотрено  дисциплиной "Структуры и алгоритмы  обработки данных в ЭВМ" (для  специальности 220400). Здесь же мы рассмотрим лишь основы структурирования данных

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

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

    - телефоны, дата рождения – целые  числа;

    - остальные данные – символьные  строки.

        Информационная система деканата содержит, например, следующие сведения о студенте: Ф.И.О., курс, группа, оценки по отдельным предметам в каждую сессию, наличие и количество пересдач по каждому предмету и т.д. Эти сведения тоже представляют собой данные разных типов.

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

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

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

    а + bi, где a, b- вещественные, i² = -1.

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

1. действительная часть числа (значение а);
2. мнимая часть числа (значение b).

    Каждое  поле будет иметь тип REAL. Описание типа выглядит так:

                TYPE COMPL  = RECORD

                                        RE: REAL;

                                        IM: REAL;

                                  END;

    Оно говорит о том, что любое значение типа COMPL есть структура данных, являющаяся записью, состоящей из двух компонент (полей), одной из которых дано имя RE, а другой IM, и каждая из компонент есть значение типа REAL. Описания, заключенные между служебными словами RECORD и END, образуют список полей, а каждое из описаний списка называется секцией записи. Более точное определение с помощью металингвистических формул:

    <список полей>  ::= <секция записи>{;<секция записи>},

    <секция записи> ::= <имя поля>{,<имя поля>}:<тип поля>.

    В нашем описании список полей состоит  из двух секций, разделенных символом ‘;’, а каждая секция определяет одно поле. Поскольку оба поля имеют один и тот же тип, их можно объединить в одну секцию записи:

    TYPE COMPL  = RECORD

                                        RE, IM: REAL;

                            END;

    Теперь, как обычно, можно в разделе  переменных ввести переменные типа 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

      S₁: T₁;

      S₂: T₂;

      …….

      S_n: T_n;

      END;

    Здесь S₁, …, S_n – имена компонент (полей) записи, T₁, …, T_n – их типы. Типы полей могут быть самые разные, например,

    TYPE DATE = RECORD

      DAY: 1 .. 31;

MON: (JAN, FEB, APR, MAR, MAY, JUN, JUL, AUG, SEP, OCT, NOV, DEC);

                            YEAR: INTEGER;

                      END;

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

1. (JAN, FEB, APR, MAR, MAY, JUN, JUL, AUG, SEP, OCT, NOV,

DEC) –  скалярный или перечисляемый (перечислимый) тип данных. При определении этого типа просто перечисляют все возможные значения переменных этого типа.

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

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