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

          (I>10) V (1≤ I ≤ 10 L C1[I] ¹ C2[I]).

    Причем, это значение I – наименьшее, для которого выполняется       C1[I] ¹ C2[I]. На основе этого постусловия делаем следующий вывод:

    IF I>10

    THEN строки равны

    ELSE IF C1[I]<C2[I]

                THEN строка С1 меньше С2

                ELSE  строка С2 меньше С1

    Применим  алгоритм "пузырька" для сортировки символьных строк. Пусть N = 1000 – количество строк, причем  все строки разные. Тогда алгоритм можно записать в следующем виде (он несколько отличается от рассмотренного ранее, т.к. предполагает однократный просмотр последовательности строк).

    VAR M: ARRAY [1..1000, 1..10] OF CHAR;

    ……………………………

    J:=1;

    WHILE J<N DO

    BEGIN

      I:=1;

      WHILE I<=10 AND M[J, I] = M[J+1, I] DO

      I:=I+1;

      IF I<=10 AND M[J, I] < M[J+1, I]

      THEN J:=J+1;

          ELSE BEGIN {поменять местами строки}

      FOR I:=1 TO 10 DO

      BEGIN

      C:=M[J, I];

      M[J, I]:= M[J+1, I];

      M[J+1, I]:=C;

      END;

      IF J<1

      THEN J:=J-1;

      ELSE  J:=J+1;

END

    END; 

    Самостоятельно  составьте:

1. алгоритм поиска в неупорядоченном массиве строк;
2. алгоритм поиска в упорядоченном массиве строк.

    4.2. Строковый тип  данных в Паскале

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

    Вспомним, что строка-константа – это  произвольная последовательность литер, заключенная в одиночные апострофы, например,

     ‘Таблица    значений    аргумента    и   функции’

    Если  внутри литерной строки-константы (будем  теперь называть ее строковой константой) нужно использовать литеру ‘ (апостроф), то она удваивается

          ‘Д’’Артаньян’

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

          packed array [1..N] of char;

          PACKED ARRAY [1..N] OF CHAR;

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

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

          TYPE INFORM = PACKED ARRAY [1 .. 12] OF CHAR;

          VAR STR1: INFORM;

                STR2: PACKED ARRAY [1 .. 12] OF CHAR;

    Таким образом, переменные STR1 и STR2 имеют один и тот же тип и длину.

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

    STR1[4], STR2[12] и т.д.

    Но  есть и особые свойства, присущие только строкам.

1. Строковой переменной можно присвоить значение строковой константы, например,

       STR1:= ‘Язык     Паскаль’

       STR2:=’LET    IT    BE!’

    Так как пробел – тоже символ, им можно  дополнять строку, чтобы придать значения неопределенным компонентам:

       STR1:=’Строка                 ‘;

2. Значения строковых переменных одинаковой длины можно сравнивать, используя операции отношения

    =, <>, <, <=, >, >=.

    Сравнение производится посимвольно слева  направо. Пусть сравниваются два значения:

          ‘с₁ с₂ … с _n’ и ‘d₁ d₂ … d _n’

    Тогда

          ‘с₁ с₂ … с _n’ = ‘d₁ d₂ … d _n’,  если  с _i = d _i   "  i = 1, 2, … n.

          ‘с₁ с₂ … с _n’ < ‘d₁ d₂ … d _n’,  если $ k (0 < k < n), что с _i = d _i   "  i = 1, 2, … k,

      но с _k+1 < d _k+1.

    Аналогично 

          ‘с₁ с₂ … с _n’ > ‘d₁ d₂ … d _n’,  если  $ k (0 < k < n), что с _i = d _i   "  i = 1, 2, … k,

    но  с _k+1 > d _k+1.

    Строки  различной длины сравнивать нельзя.

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

    TYPE

      STROKA = PACKED ARRAY [1 .. 9] OF CHAR;

      SLOVO = PACKED ARRAY [1 .. 9] OF CHAR;

    VAR

      S1: STROKA;

      S2: SLOVO;

      S3: PACKED ARRAY [1 .. 9] OF CHAR;

      T, R: BOOLEAN;

    Тогда возможен следующий фрагмент программы:

    S1:= ’АЛЕКСАНДР’;

    S2:= S1;

    S3:=’ЕКАТЕРИНА’;

    T:= S2 = S1;

    R:= S2 < S3;

    В Турбо Паскале специально выделен  строковый тип данных STRING. Переменные такого типа описываются, например, так:

    VAR STR: STRING[14];

    Строка  – это последовательность символов произвольной длины (до 255 символов). Строку можно рассматривать как массив символов и выполнять операции над элементами строки как над элементами массива:

    STR[5] := ‘+’;

    STR[7]:= STR[1];

    S:= STR[14]; {VAR S: CHAR}

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

    VAR MaxStr : STRING;

    Можно описать константу строкового типа:

    CONST January: STRING[10] = ‘Январь’;

    В Турбо Паскале существует ряд  операций над строками как над  единым целым.

1. Строковой переменной можно присвоить значение строковой константы:

    VAR STR, STR1, STR2: STRING[80];

    STR1:= ‘Язык Паскаль’;

    STR2:=’Let It Be’;

    STR3:=’Yesterday’;

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

    STR2 > STR2

    Пусть VAR T, R: BOOLEAN; тогда возможны следующие  операторы:

    STR1:= ’АЛЕКСАНДР’;

    STR2:=’ЕКАТЕРИНА’;

    T:= STR2 = STR1;

    R:= STR2 > STR1;

3. Конкатенация (объединение) двух строк. Обозначается символом ‘+’. Если

    STR1:= ’Турбо ’;

    STR2:= ‘Паскаль’;

    STR:= STR1 + STR2; то значением STR является  ‘Турбо Паскаль’.

    Для работы со строками в Турбо Паскале  предусмотрены следующие процедуры и функции.

    Процедуры:

1. DELETE (S, Pos, L);

    S – строка, Pos – номер первого удаляемого символа, L – число удаляемых символов.

    Удаляет из строки S   L элементов, начиная с позиции Pos.

2. INSERT (ST, S, Pos)

    Вставляет подстроку ST в строку S, начиная с позиции Pos.

3. STR ( X, S);

    X – выражение целого или вещественного типа,

    S – строка.

    Процедура преобразует число в X в последовательность символов S.

4. VAL ( S, V, Code);

    S – строка,

    V – переменная целого или вещественного типа.

    Процедура преобразует строку символов S в число V (с представлением в двоичной форме).

    Code – код ошибки:

    0 – если представление числа  правильное;

    номер неправильного символа в случае ошибки.

    Функции:

1. COPY ( S, Pos, L);

    Выделяет  в строке S подстроку длины L, начиная с позиции Pos.

          L, Pos – целые, S – строка, COPY: строка. Пусть

          S := ‘ABCDEFGH’;

          S1 := COPY (S, 3, 4); тогда S1 = ‘CDEF’.

2. LENGTH (S) – целого типа

    S – строка.

    Функция определяет текущую длину строки S.

          LENGTH (S) = 8;

    При использовании данных типа STRING процедуры сортировки и поиска внешне ничем не отличаются от аналогичных процедур в числовых массивах.

    4.3. Перекодировка символов

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

1. сколько имеется различных кодов для символов;
2. какие коды приписаны тем или иным символам.

    Принятая  в настоящее время для ПК в  России 8-битовая система кодировки (1 байт) содержит 256 кодов (0 .. 255). При этом коды символов с номерами 32 – 127 соответствуют стандартным кодам ASCII (American Standard Code for Information Interchange). Коды символов от 128 до 241, включающие русские буквы и символы псевдографики, соответствуют так называемой “альтернативной ” кодировке. Коды букв в принятой системе следующие.

          A – Z : 65 – 95,

          a – z  : 97 – 122,

          А – Я : 128 – 159, (А – П : 128 – 143, Р – Я : 144 – 159),

          а – п :           160 – 175, р – я : 224 – 239,

          Ё, ё :          240, 241,  Е, е: 133, 165.

    Нам нужно отождествить все большие  и малые буквы, а также буквы  Е, е, Ё и ё. Для этой цели нужно  завести таблицу перекодировки, которая представляет собой массив Т[0 .. 255]. Номер элемента массива Т соответствует старому коду, значение – новому коду.