Лекция №3. Строковый тип. Массивы
Строковый тип
Строка – особая форма одномерного массива символов, которая имеет существенное отличие. Массив символов имеет фиксированную длину (количество элементов), которая определяется при описании. Строка имеет две разновидности длины:
1. Общую длину строки, которая характеризует размер памяти, выделяемые строке при описании;
2. Текущую длину строки (всегда меньше или равную общей длине), которая показывает количество смысловых символов строки в каждый конкретный момент времени.
Тип STRING в ТР используется для обработки текстов.
Длина строки не должна превышать 255 символов.
К любому символу строки можно обратиться так же, как и к элементу одномерного массива ARRAY [0..N] OF CHAR. Например,
Var
s: string;
s10: string [10];
Begin
…
if s=’Строка’ then …
…
if s[2]=’т’ then …
…
end.
Самый первый байт в строке имеет индекс 0 и содержит текущую длину строки.
Первый значащий символ строки занимает второй байт и имеет индекс 1.
Действия над строками и символами реализуются с помощью описываемых ниже стандартных процедур и функций:
Function Concat(s1 [, s2,..., sn]: String): String;
Возвращает строку, представляющую собой сцепление строк – параметров s1, s2, …, sn.
Function Copy(S: String; Index: Integer; Count: Integer): String;
Копирует из строки S Count символов, начиная с символа с номером Index.
Procedure Delete(var S: String; Index: Integer; Count:Integer);
Удаляет Count символов из строки S, начиная с символа с номером Index.
Procedure Insert(Source: String; var S: String; Index: Integer);
Вставляет подстроку Source в строку S, начиная с символа с номером Index.
Function Length(S: String): Integer;
Возвращает длину строки S.
Function Pos(Substr: String; S: String): Byte;
Отыскивает в строке S первое вхождение подстроки Substr и возвращает номер позиции, с которой она начинается, если подстрока не найдена, возвращается ноль.
Procedure Val (s: String; var v; var Code: Integer);
Назначение: преобразует строковое значение в его числовое представление. Параметр і представляет собой выражение строкового типа. Параметр v является переменной целого или вещественного типа. Параметр Code – это переменная целого типа, которая формирует все число со знаком. Функция Val преобразует строку s в ее численное представление и сохраняет результат в v. Если где-либо в строке встречается недопустимый символ, то его номер сохраняется в параметре Code. В противном случае этот параметр равен нулю. Предшествующие пробелы должны быть удалены.
Procedure Str (x [: Size [: Dec]], var s: String);
Назначение: преобразует численное значение в его строковое представление. Параметр х является выражением целого или вещественного типа. Параметры size и Dec представляют собой выражения целого типа. Параметр s – строковая переменная. Данная функция преобразует х в его строковое представление в соответствии с параметрами форматирования Size (размер) и Dec. Результирующая строка сохраняется в параметре s.
Пример:
var
x: real;
y: integer;
s, s1: string;
begin
s:= concat (‘12’, ‘345’); {s:= ‘12’+’345’; s = ‘12345’}
s1:= copy(s, 4, 2); {s1 = ‘45’}
insert(‘-’,s1,2); {s1 = ‘4-5’}
delete(s,3,3); {s = 12}
str(pi:6:2,s); {s=3.14}
val(‘3.14159’, x, y); {y = 0; x = 3.14159}
end.
Массивы
Массив – это структура данных, которая представляет собой однородную, фиксированную по размеру и конфигурации совокупность элементов простой и составной структуры, упорядоченных по номерам.
Массив – это набор элементов одного типа.
Описание типа массива задается следующим образом:
<имя типа> = ARRAY [ <сп. инд. типов> ] OF <тип>
где <имя типа> - идентификатор, <сп.инд. типов> - список из одного или нескольких индексных типов, разделенных запятыми, <тип> - любой тип ТР.
Массив определяется именем и количеством размерностей, необходимых для указания местонахождения требуемого элемента массива. Имя массива является единым для всех его элементов.
Поскольку конфигурация элементов массива фиксирована, то к отдельному элементу можно обращаться с помощью одного или нескольких индексов могут использоваться константы и переменные порядковых типов. Элементами массивов могут быть как простые переменные любых типов, так и переменные составных типов (массивов, строк, записей и т.д.).
В качестве индексных типов можно использовать любые порядковые типы, кроме LongInt и типов – диапазонов с базовым типом LongInt.
Var
a, b: array [1..10] of real;
Type
matrica = array [0..5] of array [-2..2] of array [char] of byte;
matrica = array [0..5,-2..2, char ] of byte;
Глубина вложенности структурированных типов произвольная, поэтому количество элементов в списке индексных типов (размерность массива) не ограничено, однако суммарная длина внутреннего представления любого массива не может быть больше 65520 байт. В памяти ПК элементы массива следуют друг за другом так, что при переходе от младших адресов к старшим наиболее быстро меняется самым правый индекс массива. Например,
Var
a: array [1..2, 1..2] of byte;
Begin
a[1,1]:=1; a[2,1]:=2;
a[1,2]:=3; a[2,2]:=4;
end.
В памяти последовательно друг за другом будут расположены байты со значениями 1, 3, 2, 4.
В ТР можно одним оператором присваивания передать все элементы одного массива другому массиву того же типа, например,
Var
a, b: array [1..5] of integer;
Begin
…
a:=b;
…
end.
После такого присваивания все пять элементов массива А получат те же значения, что и в массиве В.
Однако над массивами не определены операции отношения. Нельзя, например, записать
IF a=b then …
Сравнивать два массива можно поэлементно, например:
Const
min = 1;
max = 5;
Type
Matr = array [min..max] of byte;
Var
a, b: Matr;
i: Byte;
eq: Boolean;
Begin
…
eq:= true;
for i:= min to max do
if a[i] <> b[i] then
eq:= false;
if eq then
write (‘Массивы тождественны’)
else write(‘Массивы различны’);
…
end.
Сортировка массивов
При решении задачи сортировки обычно выдвигается требование минимального использования дополнительной памяти, из которого вытекает недопустимость применения дополнительных массивов.
Для оценки быстродействия алгоритмов различных методов сортировки, как правило, используют два показателя:
1) количество присваиваний;
2) количество сравнений.
Все методы сортировки можно разделить на две большие группы:
1) прямые методы сортировки;
2) улучшенные методы сортировки.
Прямые методы сортировки по принципу, лежащему в основе метода, в свою очередь разделяются на три подгруппы:
1) сортировка вставкой (включением);
2) сортировка выбором (выделением);
3) сортировка обменом («пузырьковая» сортировка).
Улучшенные методы сортировки основываются на тех же принципах, что и прямые, но используют некоторые оригинальные идеи для ускорения процесса сортировки. Прямые методы на практике используются довольно редко, так как имеют относительно низкое быстродействие. Однако они хорошо показывают суть основанных на них улучшенных методов, кроме того, в некоторых случаях, некоторые из прямых методов могут даже превзойти улучшенные методы.
Сортировка вставкой
Принцип метода:
Массив разделяется на две части: отсортированную и неотсортированную. Элементы из неотсортированной части поочередно выбираются и вставляются в отсортированную часть так, чтобы не нарушать в ней упорядоченность элементов. В начале работы алгоритма в качестве отсортированной части массива принимают только один первый элемент, а в качестве неотсортированной части – все остальные элементы.
Таким образом, алгоритм будет состоять из n-1 -го прохода (n – размерность массива), каждый из которых будет включать четыре действия:
1) взятие очередного i -го неотсортированного элемента и сохранение его в дополнительной переменной;
2) поиск позиции j в отсортированной части массива, в которой присутствие взятого элемента не нарушит упорядоченности элементов;
3) сдвиг элементов массива от i-1 до j-1 -го вправо, чтобы освободить найденную позицию вставки;
4) вставка взятого элемента в найденную j -ю позицию.
Пример:
Алгоритм метода сортировки вставкой
 |
Текст программы
program Sort; {vstavka}
uses
crt;
const
n = 20;
type
Mass = array [1..n] of Integer;
var
i, j, k,
temp: Integer;
a: Mass;
begin
clrscr;
randomize;
for i:=1 to n do
begin
A[i]:=random(1000);
write(a[i]:3, ' ');
end;
for i:=2 to n do
begin
temp:= a[i];
j:=1;
while(temp>a[j]) do
j:= j+1;
for k:=i-1 downto j do
a[k+1]:= a[k];
a[j]:= temp;
end;
writeln;
for i:=1 to n do
write(a[i]:3, ' ');
readln;
end.