Работа со строками длиной более 255 символов

Помимо представления строки с помощью типа данных string, в языке Pascal существует и другой способ реализации строк с помощью типа данных PChar. Для работы со строками, представленными типом данных PChar, разработано множество процедур и функций, которые находятся в стандартном модуле String.

В отличие от переменной/константы объявленной типа string, где максимальное количество символов равно 255, переменная/константа типа PChar может содержать множество символов, ограниченное только размером памяти одного сегмента 65534 байтов. В конце строки PChar имеется признак конца строки, называемый «нуль-символ», он обозначается \0.

Строки с завершающим нулем хранятся в памяти в виде символьных массивов с нулевой базой, то есть нижняя граница которых равна нулю.

Const Len=300;

Type TStr=array[0..Len] of Char;

Для работы со строками типа PChar используются следующие процедуры и функции:

function StrCat(Dest, Source: PChar): PChar; добавляет одну строку к концу другой строки и возвращает указатель на результирующую строку;

function StrComp(S1, S2: PChar): integer; сравнивает две строки S1 и S2. Если S1< S2, то результатом будет отрицательное число; если S1= S2, то результатом будет 0; если S1> S2, то результатом будет положительное число;

function StrCopy(Dest, Source: PChar): PChar; копирует значение одной строки в другую. Возвращает указатель на начало результирующей строки;

procedure StrDispose(S: PChar); уничтожает строку, распределенную ранее с помощью функции StrNew;

function StrECopy(Dest, Source: PChar): PChar; копирует значение одной строки в другую. Возвращает указатель на конец результирующей строки;

function StrEnd(S: PChar): PChar; возвращает указатель на завершающий строку нулевой символ;

function StrIComp(S1, S2: PChar): integer; сравнивает две строки аналогично StrComp без учета регистра символов;

function StrLCat(Dest, Source: PChar; MaxLen: Word): PChar; добавляет одну строку к концу другой строки аналогично StrCat с установленной максимальной длиной результирующей строки и возвращает указатель на результирующую строку;

function StrLComp(S1, S2: PChar; MaxLen: Word): integer; сравнивает две строки аналогично StrComp, учитывая только установленное количество символов;

function StrLCopy(Dest, Source: PChar; MaxLen: Word): PChar; копирует заданное число символов из Source в Dest аналогично StrCopy и возвращает указатель результирующей строки;

function StrLen(S: PChar): Word; возвращает длину строки;

function StrLIComp(S1, S2: PChar): integer; сравнивает две строки аналогично StrLIComp без учета регистра;

function StrLower(S: PChar): PChar; преобразовывает каждую букву строки в нижний регистр;

function StrMove(Dest, Source: PChar; Count: Word): PChar; копирует заданное количество символов из Source в Dest и возвращает указатель результирующей строки;

function StrNew(S: PChar); выделяет для строки память в динамической распределяемой области;

function StrPas(S: PChar): string; преобразовывает строку типа PChar в строку типа string;

function StrPCopy(Dest: PChar; Source: string): PChar; копирует значение строки string в строку типа PChar и возвращает указатель результирующей строки;

function StrPos(S1, S2: PChar): PChar; возвращает указатель на первое вхождение строки S2 в S1, если совпадения нет, то возвращается nil;

function StrRScan(S: PChar; Ch: char): PChar; возвращает указатель на последнее вхождение символа Ch в строку S, если совпадения нет, то возвращается nil;

function StrScan(S: PChar; Ch: char): PChar; возвращает указатель на первое вхождение символа Ch в строку S, если совпадения нет, то возвращается nil;

function StrUpper(S: PChar): PChar; преобразовывает каждую букву строки в верхний регистр.

Сортировка данных

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

Для оценки быстродействия алгоритмов различных методов сортировки, как правило, используют два показателя:

· количество присваиваний;

· количество сравнений.

Все методы сортировки можно разделить на две большие группы:

· прямые методы сортировки;

· улучшенные методы сортировки.

Прямые методы сортировки по принципу, лежащему в основе методы, в свою очередь, разделяются на три подгруппы:

1) сортировка вставкой (включением);

2) сортировка выбором (выделением);

3) сортировка обменом («пузырьковая» сортировка).

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

Сортировка вставкой

Принцип метода

Массив разделяется на две части: отсортированную и неотсортированную. Элементы из неотсортированной части поочередно выбираются и вставляются в отсортированную часть так, чтобы не нарушить в ней упорядоченность элементов. В начале работы алгоритма в качестве отсортированной части массива принимают только один первый элемент, а в качестве неотсортированной части – все остальные.

Таким образом, алгоритм будет состоять из (n-1)-го прохода (n – размерность массива), каждый из которых будет включать четыре действия:

· взятие очередного i-го неотсортированного элемента и сохранение его в дополнительной переменной;

· поиск позиции j в отсортированной части массива, в которой присутствие взятого элемента не нарушит упорядоченности элементов;

· сдвиг элементов массива от (i-1)-го до (j-1)-го вправо, чтобы освободить найденную позицию вставки;

· вставка взятого элемента в найденную j-ю позицию.

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

· выбор текущего элемента из отсортированной части массива;

· сравнение текущего элемента со значением, сохраненным в дополнительной переменной;

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

Пример:

Сдвиг элементов можно производить простым последовательным копированием каждого элемента, находящимся между текущим элементом в неотсортированной части массива и найденным местом вставки.

Сортировка выбором

Принцип метода

Находим (выбираем) в массиве элемент с минимальным значением на интервале от 1-го элемента до n-го (последнего) элемента и меняем его местами с первым элементом. На втором шаге находим элемент с минимальным значением на интервале от 2-го до n-го элемента и меняем его местами со вторым элементом. И так далее для всех элементов до n-1-го.

Пример: