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

Алгоритмические языки и программирование

Работа с массивами

Методические указания

к выполнению лабораторной работы №4

для студентов очной формы обучения

специальности 230201 – "Информационные системы

и технологии"

Брянск 2007

УДК 004.43

Алгоритмические языки и программирование. Работа с массивами: методические указания к выполнению лабораторной работы №4 для студентов очной формы обучения специальности 230201 – "Информационные системы и технологии". – Брянск: БГТУ, 2007. - 15 с.

Разработали:

С.М. Рощин, к.т.н., доц.

Ю.А. Леонов, асс.

Рекомендовано кафедрой «Компьютерные технологии и системы» БГТУ (протокол № от )

ЦЕЛЬ РАБОТЫ

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

Продолжительность работы – 4ч.

Теоретическая часть

Одномерные массивы

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

Массив определяется именем (идентификатором) и количеством размерностей (координат), необходимых для указания местонахождения требуемого элемента массива. Имя массива является единым для всех его элементов.

Синтаксис объявления одномерного массива:

var имя_массива: array [a..b] of тип_данных;

где a, b – номера (индексы) первого и последнего элементов массива соответственно. Тип данных элементов массива может быть как простым, так и составным.

При обращении к элементу массива в квадратных скобках указывается его индекс.

Пример объявления:

const n=100;

var A: array [1..n] of Real; {Массив из 100 элементов типа Real}

или

const n=100;

type T_Vector = array [1..n] of Real; {Тип данных - массив}

var A: T_Vector; {Массив из 100 элементов типа Real}

Пример работы:

A[1]:=5; {В массив А в ячейку с индексом 1 записано число 5.}

Двумерные и многомерные массивы

Синтаксис объявления двумерного массива:

var имя_массива: array [a..b, c..d] of тип_данных_массива;

где a, b – номера первой и последней строк массива соответственно; с, d – номера первой и последней ячеек строки массива соответственно. Тип данных также может быть как простым, так и составным.

Пример объявления и использования:

Const n=5; m=5;

{Объявление массива из 10 строк, в каждой из которых 5 ячеек}

Var A: array [1..m, 1..n] of real;

i, j : integer; {Переменные цикла}

Begin

{Инициализация значений массива}

For j:=1 to n do {Проход массива по столбцам}

For i:=1 to m do begin {Проход массива по строкам}

Write(‘Введите A[’, i, ’,’, j, ’]=’);

ReadLn(A[i, j]); {Заполнение массива}

end;

{Вывод массива на экран}

Writeln(‘Массив А’);

For j:=1 to n do begin

For i:=1 to m do Write(A[i, j]);

WriteLn;

end;

End.

В некоторых случаях используются многомерные массивы. Синтаксис объявления многомерного массива:

var имя_массива: array [a..b, c..d, … , x..y] of тип_данных;

где a..b, c..d, … , x..y – диапазоны, определяющие количество элементов для соответствующей размерности массива.

Строки

Для работы с символьной информацией принято использовать структуру данных – строка. Определение переменных типа «строка» содержит служебное слово string, за которым может следовать максимальная длина строки в квадратных скобках (целочисленная константа в диапазоне от 0 до 255).

Например:

Var a: string [14]; {Определение строки с именем a длиной 14 символов}

line: string; {Определение строки с именем line с максимально возможной длиной}

Объявление переменной line типа string подобно следующему объявлению:

Var line: array [0..255] of char;

Доступ к отдельным элементам строки (символам) выполняется с помощью индексации. В результате получается величина типа char, например: a[6] – обращение к шестому символу строки. Тип string и стандартный тип char совместимы, т.е. строки и символы могут употребляться в одних и тех же выражениях.

Две сравниваемые строки являются одинаковыми, если они совпадают посимвольно и имеют одинаковую длину.

Подпрограммы для работы со строками

Для работы со строками типа string в Pascal используются следующие процедуры и функции, находящиеся в модуле System:

function Concat(s1 [, s2, …,sn]: string): string; выполняет конкатенацию (сцепление) последовательности строк;

function Copy(s: string; index, count: integer): string; возвращает копию подстроки с позиции index длиною count из заданной строки s;

procedure Delete(var s: string; index, count: integer); удаляет из строки подстроку начиная с позиции index длиною count;

procedure Insert(source: string; var s: string; index: integer); добавляет в строку s подстроку source на позицию index;

function Length(s: string): integer; возвращает текущую длину строки;

function Pos(substr, s: string): byte; производит поиск подстроки substr в строке s, если подстрока встречается, возвращается позиция ее начала;

procedure Str(x [: width [: decimals]]; var s: string); преобразует численное значение x в его строковое представление s;

procedure Val(s; var v; var code: integer); преобразует строковое значение s в его численное представление code.

Пример.

{Удаление переданного символа из строки}

Var s: string;

ch: char;

Function DelChars(_s: string; _ch: char): string;

Var i: byte;

Begin

For i:=1 To length(s) Do

if (_s[i]=_ch) then Delete(_s, i, 1);

DelChars:=_s;

End;

BEGIN

Writeln('Input string');

Readln(s);

Writeln('Input char');

Readln(ch);

Writeln(DelChars(s, ch));

END.

Работа со строками длиной более 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-го.

Пример:

Не нашли, что искали? Воспользуйтесь поиском по сайту: