Символы и строки. Множества

Стандартные функции

Функция chr(k:byte):char "превращает"; номер символа в символ. Действие этой функции аналогично действию операции #. Например:

c:= chr(48); {c: char}
{c = '0'}

Обратной к функции chr() является уже изученная нами функция ord(). Таким образом, для любого числа k и для любого символа с

ord(chr(k)) = k		и		chr(ord(c)) = c

Надеемся, читатель помнит, что стандартные процедуры и функции pred(), succ(), inc() и dec(), определенные для значений любого порядкового типаСм. лекцию 2., применимы также и к символам (значениям порядкового типа данных char ). Например:

pred('[')  = 'Z'
succ('z')  = '{'
inc('a')   = 'b'
inc('c',2) = 'e'
dec('z')   = 'y'
dec(#0,4)  = '№' {#252}

Стандартная функция upcase(c: char):char превращает строчную букву в прописную. Символы, не являющиеся строчными латинскими буквами, остаются без изменения (к сожалению, в их число попадают и все русские буквы).

Стандартные функции и процедуры обработки строк

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

concat('abc','3de',' ','X','yz') = 'abc3de Xyz'

copy('abc3de Xyz',2,4)  = 'bc3d'
	copy('abc3de Xyz',12,4) = ''
	copy('abc3de Xyz',8,14) = 'Xyz'

{s = 'abc3de Xyz'}			{s = 'abc3de Xyz'}
	delete(s,2,3);				delete(s,8,13);
	{s = 'ade Xyz'}				{s = 'abc3de '}

{s = 'abc3de Xyz'}			{s = 'abc3de'}
	insert('xyz',s,2);			insert('xyz',s,12);
	{s = 'axyzbc3de Xyz'}		{s = 'abc3dexyz'}

length('abc3de Xyz') = 10

pos('X', 'abc3de Xyz') = 8

str(156.4:7:2,s); 
	{s = ' 156.4 '}

{s = '15.47'}
	val(s,x,err);
	{x = 15.47}

Операции со строками

Сравнения

Строки - это единственный структурированный тип данных, для элементов которого определен порядок и, следовательно, возможны операции сравнения ( =, >, < ).

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

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

Итак,

'abc' < 'xyz'
'a' < 'abc'
'1200' < '45'
'Anny' < 'anny'

Обращение к компонентам строки

Доступ к k -му символу строки осуществляется так же, как к k -й компоненте массива (квадратные скобки являются обязательным элементом синтаксиса):

<имя_строки>[<индекс>]

Например:

{s = '15.47'}
c:= s[3];
{c = '.'}

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

s[i]:= 'a';

не вызовет ошибки при компиляции, но, скорее всего, не станет работать во время выполнения программы. Для того чтобы изменить символ в строке, нужно воспользоваться стандартными функциями length(), concat() и copy(). В этом случае простое, казалось бы, действие приходится представлять как последовательность четырех операций:

s1:= copy(s,1,k-1);

s2:= new_char;

s3:= copy(s,k+1,length(s)-k);

s:= concat(s1,s2,s3);

Или можно объединить все четыре действия в одном операторе:

s:= concat(copy(s,1,k-1), new_char, copy(s,k+1,length(s)-k));

Конкатенация

Единственная операция, которую разрешается производить с переменными строкового типа, - это слияние строк или символов ( конкатенация ). Она полностью эквивалентна функции concat() и записывается при помощи знака " + ". Таким образом, предыдущий оператор можно сделать более простым:

s:= copy(s,1,k-1) + new_char + copy(s,k+1,length(s)-k);

Множества

Еще один структурированный тип данных - это множество ( set ). В нем может содержаться не более 256 элементов.

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

Описание множеств

В разделе var множества описываются следующим образом:

var <имя_множества>: set of <тип_элементов_множества>;

Элементы могут принадлежать к любому порядковому типу, размер которого не превышает 1 байт (256 элементов). Например:

var s1: set of char;	{множество из 256-ти элементов}
	s2: set of 'a'..'z','A'..'Z'; 	{множество из 52-х элементов}
	s3: set of 0..10; 	{множество из 11-ти элементов}
	s4: set of boolean; 	{множество из 2-х элементов}

Множество-константа

Неименованная константа

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

[<список_элементов>]

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

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

if c in ['a','e','i','o','u'] 
	then writeln('Гласная буква');
if set1 < [k*2+1..n,13] then set1:=[];

Нетипизированная константа

Множество - это структурированный тип данных, поэтому его невозможно задать нетипизированной константой.

Типизированная константа

Задать множество как типизированную константу можно в разделе const:

<имя_константы> : set of <тип_элементов> =[<список_элементов>];

Например:

type 	cipher = set of '0'..'9';
const odds: cipher = ['1','3','5','7','9'];
	vowels: set of 'a'..'z' = ['a','o','e','u','i'];

Операции с множествами

Все теоретико-множественные операции реализованы и в языке Pascal:

s:=[e1,_,eN];

s1 = s2
s1 > s2
s1 < s2

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

{s: set of type1; k: type1}
for k:= min_type1 to max_type1
	do if k in s then write(k);

Представление множеств массивами

Одно из основных неудобств при работе с множествами - это ограничение размера всего лишь 256-ю элементами. Мы приведем здесь два очень похожих способа представления больших множеств массивами. Единственным условием является наличие некоторого внутреннего порядка среди представляемых элементов: без этого невозможно будет их перенумеровать.

Представление множеств линейными массивами

Задав линейный массив достаточной длины, можно "вручную" сымитировать множество для более широкого, чем 256 элементов, диапазона значений. Например, чтобы работать с множеством, содержащим 10 000 элементов, достаточно такого массива:

set_arr: array[1..10000] of boolean;

При таком способе представления возможно задать множество до 65 000 элементов.

Для простоты изложения мы ограничимся только числовыми множествами, однако все сказанное ниже можно применять и к множествам, элементы которых имеют другую природу. Итак, признаком того, что элемент k является элементом нашего множества, будет значение true в k -й ячейке этого массива.

Посмотрим теперь, какими способами мы вынуждены будем имитировать операции над "массивными" множествами.

pusto:= true;
for i:= 1 to N do
      if set_arr[i] then begin pusto:= false;
                                        break
                         end;

is_in:= set_arr[element];

set_arr[element]:= true;

set_arr[element]:= false;

equal:= true;
for i:=1 to N do
		if set1[i]<> set2[i] 
			then begin equal:= false;
							break
					end;

subset:= true;
for i:= 1 to N do
		if set1[i]and not set2[i]
			then begin subset:= false;
							break
					end;

Представление множеств битовыми массивами

В случае, если 65 000 элементов недостаточно для задания всех необходимых множеств (например, 10 множеств по 10 000 элементов в каждом), это число можно увеличить в 8 раз, перейдя от байтов к битам. Тогда 1 байт будет хранить информацию не об одном, а сразу о восьми элементах: единичный бит будет означать наличие элемента в множестве, а нулевой бит - отсутствие.

Задавая битовый массив, начнем нумерацию его компонент с 0:

set_bit: array[0..N-1] of byte;

Тогда результатом операции <номер_элемента> div 8 будет номер той компоненты массива, в которой содержится информация об этом элементе. А вот номер бита, в котором содержится информация об этом элементе, придется вычислять более сложным образом:

bit:= <номер_элемента> mod 8;
if bit=0 then bit:= 8;

Эти вычисления потребуются нам еще не раз, поэтому запишем их снова, более строго, а затем будем использовать по умолчанию ( element - это "номер" обрабатываемого элемента в нашем множестве):

kmp:= element div 8;	{номер компоненты массива}
bit:= element mod 8;	{номер бита}
if bit=0 then bit:= 8;

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

pusto:= true;
for i:= 0 to N-1 do
        if set_arr[i]<>0 then begin pusto:= false;
                                                  break
                                          end;

if set_arr[kmp]and(1 shl(bit-1))=0
		then is_in:= false
		else is_in:= true;

set_arr[kmp]:= set_arr[kmp]or(1 shl(bit-1));

set_arr[kmp]:= set_arr[kmp]and not(1 shl(bit-1));

for i:= 0 to N-1 do set_res[i]:= set1[i] and set2[i];

for i:= 0 to N-1 do
		set_res[i]:= set1[i] or set2[i];

for i:= 0 to N-1 do
		set_res[i]:= (set1[i] or set2[i]) and not set2[i];

equal:= true;
for i:=0 to N-1 do
      if set1[i]<> set2[i] then begin equal:= false;
                                                    break
                                      end;

subset:= true;
for i:= 0 to N-1 do
    if((set1[i] or set2[i])and not set2[i])
           or set2[i] <> set1[i]
       then begin subset:= false;
                            break
                end;

Замечание. Если предстоит многократно выполнять действия с элементами битовых массивов, то используемые для этого значения "единиц" удобнее всего сразу задать в специальном массиве:

{ed: array[1..8] of byte;}
ed[1]:=1; 	
for k:= 2 to 8 do 
		ed[k]:= ed[k-1] shl 1;

И далее вместо громоздкой конструкции 1 shl(bit-1) можно использовать просто ed[bit].

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

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

program z1;
var s: set of char;
inp, res: string;
i: byte;

begin
	s:=[];
	res:= '';
	for i:= 1 to length(inp) do
			if not(inp[i] in s)
			  then begin res:= res+inp[i];
								s:= s+[inp[i]];
					  end;
end.

Более простой вариант решения - повторить решение задачи 1 с заменой цикла for-to на for-downto. Приведенный же вариант решения можно использовать для обработки не только строк, но и файлов. Оставить в строке только последнее вхождение каждого символа, взаимный порядок оставленных символов сохранить.

program z2;
var inp, res: string; 
i, k: byte;

begin
	res:= '';
	for i:= 1 to length(inp) do
		begin 
			k:= pos(inp[i],res);
			if k<>0 
				then delete(res,k,1);
			res:= res+inp[i];
		end;
end.

Задача 3. Выдать первые 100 000 натуральных чисел в случайном порядке без повторений.

program z3;
var bset: array[0..12499] of byte;   {множество, битовый 
массив}
		  ed: array[1..8] of byte;
		  el,k: longint;
		  kmp,bin: integer;
begin
	ed[1]:= 1; 	{генерация массива 
битовых единиц}
	for k:= 2 to 8 do ed[k]:= ed[k-1] shl 1;
{-------------------------------------------------------}
	k:=0;
	randomize;	{процедура активизации генератора случайных 
чисел}
	while k<100000 do
begin
		   el:= 1+random(99999); 	{случайное число из диапазона 0..99999}
		kmp:= el div 8;
		bin:= el mod 8;
		if bin=0 then bin:= 8;
		   if bset[kmp]and ed[bin]=0	{проверка повторов}
	   then begin inc(k);
								 writeln(el);
								 bset[kmp]:= bset[kmp]or ed[bin]
			  end;
end
end.