Иванова Г.С. - Основы программирования

	4. Структурные типы данных
Begin
WriteLn('Введите строку');
ReadLn(st);	{вводим строку}
р:=0;	{обнуляем счетчик слов }
ifst[Length(st)]	<> ' ' then st:=st-^ ' V {если в конце нет пробела,
while Length(st)<>0 do		то добавим его}
begin
spos:^ Pos(' \ St);
ifspos>5	thenp:=p+J;	{определяем длину слова}
Delete(st,l,spos);		{удаляем слово}

end;

WriteLnCB строке \ p, ' слов(а), длина которых больше четырех. ) ; End.

Пример 4.17. Разработать программу, меняющую в строке одно сочетание букв на другое.

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

Program Stroka;

Var mbyte; s, si, s2:string; Begin

WriteLnCBeediwie исходную строку); ReadLn(s);

WriteLnCВведите заменяемое слово: ) ; ReadLn(sl);

WriteLn('Введите заменяюгцее слово: ) ; ReadLn(s2);

n:=Pos(sl,s); {определяем вхождение заменяемого сочетания} while п > О do

begin

Delete(s,n,Length(s 1)); {удаляем заменяемое сочетание} Insert(s2,s,n); {вставляем заменяющее сочетание} n:=Pos(sl,s); {определяем следующее вхождение}

end; WriteLn(Teзyльmam : \s); ReadLn;

End

Пример 4.18. Разработать программу, меняющую в строке местами сло­ ва с указанными номерами. Запретить ввод номеров, которые превышают ко­ личество слов в строке или равны между собой.

121

Часть 1. Основы алгоритмизации и процедурное программирование

Ва р и а н т 1. При решении данной задачи строку приходится просма­ тривать посимвольно, так как необходимо фиксировать начало и длину каж­ дого из слов с указанными номерами. Если очередной символ равен пробелу, то количество слов необходимо увеличить на единицу, проверить, не совпа­ дает ли номер с одним из заданных и если совпадает, то запомнить номер первого символа и длину слова. После чего обнуляем счетчик длины слова и фиксируем начало следующего слова. Если символ не пробел, то увеличива­ ем длину текущего слова.

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

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

Program Stroka2;

Var nsl, ns2, ks, nl, п2, dll, dl2,ns ,dls, i, w:byte; s, si, s2:string;

Begin

WriteLn(*Введите исходную строку'); Readln(s); ks:=0; {обнуляем счетчик слов}

for /.•= 1 to Length(s) do

if(s[i]=' ') or (i=length(s)) then {если конец очередного слова } ks:=ks-\-l: { увеличиваем счетчик слов}

WriteLn('Beedume номера слов для обмена'); ReadLn(nl,n2); {вводим номера}

while (nl>ks) or(n2>ks) ог(п1=п2) do {пока номера не допустимы} begin

WriteLnCКоличество слов в строке \ks:5,

		\ Одинаковые номера не допустимы.
		Повторите ввод номеров. *);
ReadLn(nl,n2); {вводим номера}
end;
ifnl>n2	then	{сортируем номера по возрастанию}
begin	w:-nl;	п1:=п2; n2:=w; end;
ns:=l;	{начало первого слова равно 1}
dls:=0; {длина первого слова равна 0}
ks:=0;	{номер слова пока равен 0}

122

4. Структурные типы данных

for i:^l to Length(s) do {no всей строке} begin

if(sfij=' ') or (i=Length(s)) then {если слово завершено}

	begin
	if (i=Lengt/t(s)) and (sfij <>' ') then {если в конце
		dls:=dls+l;			строки нет пробела}
					{корректируем длину слова}
	b:=ks+l;
	ifks=nl	then		{если это первое слово}
	begin		{то запоминаем начало и длину}
		ns1: =ns;			dll: =dls;
	end;
	ifks=n2	then		{если это второе слово}
	begin		{то запоминаем начало и длину}
		ns2:=ns;			dl2:=dls;
	end;
	dls:=0;	{обнуляем			длину текущего слова}
	ns:=i+l;	{запоминаем начало текущего слова}
	end
else	dls:=dls+l;		{считаем длину очередного слова}
end;
sl:=Copy(s,	nsJ, dll);	{копируем значение первого слова}
s2:=Copy(s, ns2, dl2);		{копируем значение второго слова}
Delete(s, ns2, dl2);		{удаляем дальнее слово}

Insert(sl, S, ns2); {вместо него вставляем ближнее} Delete(s, nsl, dll); {удаляем ближнее слово} Insert(s2,s,nsl); {вставляем дальнее}

WriteLnf'Результат : \ s); End.

В а р и а н т 2. Вначале разобьем текст на слова и поместим каждое сло­ во в элемент вспомогательного массива строк. Затем выполним перестанов­ ку элементов. И, наконец, вновь объединим слова в строку.

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

Program StrokaS;

Var ks, nl, п2, i, kbyte; 5, si .string;

MasStr:array[L. 100] ofstring[20]; {рабочий массив}

123

Часть L Основы алгоритмизации и процедурное программирование

Begin

WriteLnCВведите исходную строку'); Readln(s); ks:^0; {обнуляем счетчик слов}

ifs[length(s)]<>' ' then 5;=л'+' V {если в конце строки нет пробела, то дописываем его}

{разбор строки}
while s<> *' do		{пока в строке остались слова}
begin
b:=ks+l;		{увеличиваем счетчик слов}
k:=Pos('	\s);	{определяем конец слова}
masStr[ks]:=Copy(sJ,k);				{копируем слово в массив}
Delete(sJ,k);				{удаляем слово из строки}
end;
{обмен слов}
WriteLn('Beedume номера слов для обмена');
ReadLn(nl,n2);	{вводим номера}
while (nl>ks) ог(п2>Ь)			ог(п]=п2) do {пока номера не допустимы}
begin
WriteLn('Количество слов в строке \ks:5,
\ Одинаковые номера не допустимыЛовторите ввод номеров. ');
ReadLn(nl,n2);		{вводим номера}
end;
sl:=MasStrfn]J;		{меняем слова местами}
MasStrfnlJ: =MasStrfn2J;
MasStr[n2]:=sl;
{объединение слов в строку}
for /;=7 to ks do s:=s-^MasStr[iJ; {объединяем слова в строку}
Delete(s,Length(s),l);			{удаляем пробел после последнего слова}
WriteLnCРезультат : \ s);				{выводим результат}
End

Пример 4.19. Разработать программу, которая осуш.ествляет поиск за­ данной строки в отсортированном в соответствии с латинским алфавитом массиве строк MasStr[n], п<100. Конкретное количество строк массива опре­ делять в процессе их ввода.

Ввод строк организуем в цикле-пока. В качестве условия завершения ввода будем использовать ввод пустой строки. Количество вводимых записей будем считать. Если введено меньше 99 слов, то после завершения ввода уменьшим количество введенных строк на единицу, чтобы не обрабатывать пустую строку.

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

В а р и а н т 1. Самый простой способ поиска - последовательный. При последовательном способе мы запись за записью сравниваем строки в мас-

124

4, Структурные типы данных

сиве с заданной строкой. Однако данный вид поиска является и самым про­ должительным по времени. Оценим время поиска.

Если искомая строка совпадает с первой строкой массива, то в процессе поиска будет выполнено одно сравнение. Если искомая строка совпадает с последней строкой, то - п сравнений. В среднем в процессе поиска понадо­ бится выполнить (n-fl)/2 сравнений, т.е. вычислительная сложность последо­ вательного поиска Оср(п).

В а р и а н т 2. Для ускорения обработки можно реализовать двоичный поиск. Э^от метод применим, так как массив отсортирован по возрастанию кодов символов строк. Метод двоичного поиска заключается в следующем. Определяют примерную середину массива и проверяют, совпадает ли иско­ мый элемент с элементом в середине массива. Если совпадает, поиск завер­ шен. Если не совпадает, то, если элемент больше среднего, то поиск продол­ жают в левой половине массива, иначе - в правой половине. Таким образом, диапазон элементов на каждом шаге уменьшается больше, чем вдвое. Если диапазон сократился до нуля, а элемент не найден, то такой элемент в масси­ ве отсутствует.

На рис. 4.30 показан пример реализации двоичного поиска для массива, включающего 10 элементов. На первом шаге осуществляется проверка 5-го элемента, и массив разбивается на два подмассива: 1 ...4 и 6... 10. На втором шаге - 2-го, если искомое значение меньше 5-го элемента, или 8-го, если искомое значение больше 5-го элемента. Затем проверяются значения третьего уровня и т. д.

Исходный массив

			1	2	3	4	м	6	7	8	9	10
1-й шаг							5
2-й шаг		1	2	.3	4				6	7	8	9	10
		1 1			11			I	1 I \—Ш				1
	•
3-й шаг		/						6 ^ 7					9 ^10
								• П			ШШ~1
						•				п
									\				\ 10
4-й шаг										7
		[	I —		элемент, анализируемый на данном шаге
	Рис. 4.30. Пример дерева двоичного поиска для исходного
				диапазона из 10 элементов

125

Часть 1. Основы алгоритмизации и процедурное программирование

Оценим время поиска для данного метода. Будем считать, что дерево по­ иска строки получилось сбалансированным, т.е. количество записей п = 2J-1, где j=l, 2, 3 и т.д., тогда количество уровней дерева равно log2 п. Считая, что искомое значение может с равной вероятностью находиться на любом уровне, получаем, что среднее количество сравнений равно (log2 п +1)/2, т.е. вычислительная сложность двоичного поиска 0^,p(log2 п), что при больших значениях п существенно лучше, чем при последователь­ ном поиске.

Примечание. Если бы изначально массив не был отсортирован, а поиск требовалось бы производить многократно, то массив целесообразно было бы сортировать.

Реализуем двоичный поиск.

Program ex;

Var MasStr:array[L. 100] ofstring[22];

n, k, I: integer; st:strmg[22];	key:boolean;
Begin
n:=l;

WriteLnCВведите до 100 строкЗавершение ввода - пустая строка'); ReadLn(MasStr[n]);

while (MasStr[n]<> 7 and (n<100) do

begin
n:=n+l;
ReadLn(MasStr[n]);
end;
ifn<100 then п:=П'1;	{слов в массиве на одно меньше}
WriteLnCВведите строку для поиска.');
ReadLn(st);
к:=1; key:=false;
while (П'к>=0) and not key do		{пока диапазон положителен и
begin		запись не найдена}
1:-(П'к) div 2+к;	{определяем среднее значение индекса}
ifst=MasStr[l] then key:-true		{запись найдена}
else	{уменьшаем диапазон индексов}
if s(>MasStr[l] then k:-lH		{смещаем левую границу}
end;	else n:-l'l;	{смещаем правую границу}

if key then

WriteLn('Строка найдена. Номер равен \1) else WriteLnCCmpoKa не найдена.');

End.

126

4. Структурные типы данных

Задания для самопроверки

Задание 1. Дана строка текста длиной не более 80 символов, состоящая из слов, разделенных пробелом, в конце точка. Разработайте программу, которая определяет номера слов, в которых содержится более трех символов «А». Вывести исходную строку и номера слов. Если слов с таким числом букв не окажется, вывести соответ­ ствующее сообщение.

Задание 2. Дана строка текста длиной не более 40 символов, состоящая из слов, разделенных пробелом, в конце точка. Разработайте программу, которая удаляет из текста слово, содержащее максимальное количество букв «В». Вывести исходную и преобразованную строки. Если в тексте нет слов с буквой «В» - вывести соответст­ вующее сообщение.

Задание 3. Дан массив символьных строк, длиной не более 40 символов. Стро­ ки состоят из слов, разделенных пробелом, в конце точка. Разработайте программу, которая формирует одномерный массив В, содержащий в качестве элементов коли­ чество слов каждой строки, начинающихся на гласную букву. Если таких слов нет, в соответствующий элемент массива В занести 0. Вывести исходный и сформирован­ ный массивы.

Задание 4. Дана строка, состоящая из слов, разделенных одним пробелом. Раз­ работайте программу, которая разбивает исходную строку на подстроки, размер ко­ торых не превышает заданного значения п. Перенос слов считать запрещенным.

Задание 5. Разработайте программу, которая осуществляет «выравнивание по ширине» подстрок, полученных в результате работы программы задания 4. Вырав­ нивание должно выполняться таким образом, чтобы дополнительные пробелы меж­ ду словами распределялись по подстроке равномерно.

4.7. Множества

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

В Borland Pascal предусмотрен структурный тип, предназначенный для представления множеств. Данные множественного типа представляют со­ бой совокупности однотипных элементов, каким-либо образом связанных друг с другом. Характер связей между элементами только подразумевается программистом и никак не контролируется.

Множественный тип объявляется как совокупность элементов некоторо­ го базового типа (рис. 4.31).

Допускается объявлять только конечные множества, количество элемен­ тов которых может меняться от О до 255.

127

Часть l. Основы алгоритмизации и процедурное программирование

^ set \ ^ ^0 1	Базовый	I	Базовым типом может быть
	тип	I	любой порядковый тип за ис­
Рис. 4.3L Синтаксическая диаграмма			ключением типов	integer и
			longint, количество	возмож-
<Объявление множественного типа>			ных значений которых пре­
			вышает 255. В качестве базо­
вого типа могут использоваться только диапазоны значений этих типов.
Порядок расположения элементов во множестве никак не фиксируется.
Это соответствует принятой в математике трактовке множества.
Новый множественный тип обычно сначала объявляют, а затем уже ис­
пользуют при описании переменных		и констант, например:

Туре

Digits = set of L. 100; {тип «множество целых чисел от 1 до 100»} Setchar = set of char; (тип «множество символов таблицы ASCII»} letter=set of 'а'.. *z V {тип «множество прописных латинских букв»} logic = set of boolean; {тип «множество логических значений»}

Var

mychar:setchar; {переменная - множество символов таблицы ASCII} bool: logic; {переменная - множество логических значений} mydig: Digits; {переменная - множество целых чисел от 1 до 100} simst: letter; {переменная - множество прописных латинских букв}

Множественный тип можно определить и непосредственно при объяв­ лении переменных программы, например:

Var number:set <9/"7..37; {переменная - множество целых чисел от 1 до 31} cif: set of 0,,9; {переменная - множество цифр}

kods: set о/#0..#255;{переменная - множество кодов таблицы ASCII} workweek, week: set о/фу«; {переменная - множество дней недели}

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

[] - пустое множество; [2,3,5,7,11] - множество, включающее несколько целых чисел;

['а\ 'd\ f\ Ъ 7 - множество, включающее несколько латинских литер; [1,к] - множество, состоящее из целого числа 1 и текущего значения

переменной к; [к.,2*к] - множество целых чисел от значения переменной к до ре­

зультата выражения 2*к;

128

4. Структурные типы данных

[2„100] - множество целых чисел от 2 до 100;

/"/, 2, i.. 7] - множество целых чисел, включающее числа 1,2,3,4,5,6,7; [red,yellow,green] - множество, состоящее из трех элементов

некоторого перечислимого типа.

Инициализация множеств. Возможна инициализация переменных множественного типа с использованием типизированных констант. Напри­ мер:

Туре setnum=set ofbyte;

Const S:setnum=[LJOJ; {инициализированная переменная, ее исходное значение в программе равно множеству, включающе­ му целые числа от 1 до 10}

Операции над множествами. Для работы со значениями множествен­ ного типа предусмотрены специальные операции, в основном соответствую­ щие операциям, определенным в теории множеств: объединение^ пересечение и дополнение множеств. Это двуместные операции, операндами которых яв­ ляются данные множественного типа - множества и выражения, принимаю­ щие значение множественного типа. Оба операнда должны принадлежать од­ ному и тому же множественному типу. Обозначения этих операций в Borland Pascal и их геометрическая интерпретация представлены в табл. 4.1 приме­ нительно к множествам А и В.

Таблица 4.1

	Математическая	Операция	Геометрическая
	запись	Borland Pascal	интерпретация
	A u B	А^В	(А( J В)
!	А п Б	А *В	€Э
	А\В	А'В	ЙЭ

Результат операции

Обьединение множеств А и В - множество, состоящее из эле­ ментов, принадлежащих мно­

жествам А и В

1

Пересечение множеств А и В ~ множество, состоящее из эле­ ментов, принадлежащих одно­ временно и множеству А и множеству В

Дополнение множеств А и В - множество, состоящее из тех элементов множества А, кото­ рые не принадлежат множеству

В

129

Часть I. Основы алгоритмизации и процедурное программирование

Например:

[1,2] + [3,4] = [U,3,4];

[1..10] * [3,8,9,15,23,45] = [3,8,9]; [1..15] - [3,8,9,15,23,45] = [1,1,4..7,10.Л4];

[red,blue,green,black] * [bIue,magenta,yeIlow] = [blue].

Операции отношения. Наряду с рассмотренными выше операциями над значениями множественного типа определены и операции отношения. Опе­ рандами отношений в этом случае являются переменные или выражения множественного типа. В табл. 4.2 показано соответствие между математиче­ скими операциями сравнения множеств и операциями отношения, опреде­ ленными в Borland Pascal.

Операция проверки вхоэюдеиия элемента во мноэюество. Особое место занимает операция проверки вхождения элемента во множество, обозначае­ мая служебным словом in (рис. 4.32). В отличие от операций отношения, в операции in первый операнд должен принадлежать базовому типу элементов данного множественного типа. Результатом операции in, как во всех опера­

Выражение КЕН Множество	циях отношения, является
	логическое значение.
	Ниже приведены при­
	меры применения операций
Рис. 4.32. Синтаксическая диаграмма	отношения и операции вхо-
	ждения к различным мно-
<Проверка вхождения элемента во множество>	жествам.

Матемэтическая	Операция
запись	Borland Pascal
А = В	А = В
АФЪ	А<>В
А с В	А<=В
А з В	А>=В

	Т а б л и ц а 4.2
	Результат операции
TRUE	FALSE

Множества А и В совпа­ дают

Множества А и В не сов­ падают

Все элементы множества А принадлежат множест­ ву В

Все элементы множества В принадлежат множест­ ву А

Множества А и В не сов­ падают

Множества А и В совпа­ дают

Не все элементы множе­ ства А принадлежат мно- j жеству В

Не все элементы множе­ ства В принадлежат множеству А

130