Поиск подстроки в строке
.doc
Министерство образования Российской Федерации
Санкт–Петербургский Государственный
Электротехнический Университет
Кафедра МО ЭВМ
Дисциплина: Программирование
Отчет по лабораторной работе №2
Выполнил:
студент группы 3341, Худяков Я.Д.
Проверил:
Преподаватель Самойленко В. П.
Санкт-Петербург
2003
1) Задание
Найти координаты первого вхождения в заданную строку подстроки, состоящей из 2-х заданных символов.
2) Постановка задачи
В реализации алгоритма решения поставленной задачи нам необходимо пройти строку один раз, либо до конца, либо до первого вхождения в строку искомой подстроки. Строка реализована в 2-х типах: строка с известной длиной и строка с маркером конца. У каждого типа представлены 3 процедуры: чтения строки(input), её анализа(process) и вывода(output) результатов.
Представленные типы строк:
strLtype=record
strL:array[1..maxlen] of char;
len:byte;
end;
strMtype=record
strM:array[1..maxlen+1] of char;
mk:char;
end;
Спецификация функций и процедур:
|
Функция |
Назначение |
Входные параметры |
Выходные параметры |
|
inputstrL |
Чтение строки в тип с известной длиной |
f-дескиптор входного файла, strl-строка с изв. длиной, sim-заданный символ |
f-дескиптор входного файла, strl-строка с изв. длиной |
|
inputstrM |
Чтение строки в тип с маркером конца |
f-дескиптор входного файла, strl-строка с маркером конца строки, sim-заданный символ |
f-дескиптор входного файла, strl-строка с маркером конца строки |
|
processl |
Обработка строки с известной длиной |
strl-строка с известной длиной, sim-заданный символ |
k-координата... |
|
processm |
Обработка строки с маркером конца |
strl-строка с известной длиной, sim-заданный символ |
k-координата... |
|
outL |
Вывод рез-ов по строке с изв. длиной |
f-дескриптор вых файла, strl-строка с изв длиной, k-координаты... |
f-дескриптор вых файла |
|
outM |
Вывод рез-ов по строке с маркером конца |
f-дескриптор вых файла, strl-строка с маркером конца, k-координаты... |
f-дескриптор вых файла |
3) Текст программы
{Программа нахождения координаты первого вхождения в заданную строку подстроки}
{состоящей из двух одинаковых заданных символов (задание 18)}
{Выполнено студентом гр 3341 Худяковым Ярославом}
{входные выражения в файле koordin.txt}
{выходные данные в файле koordout.txt}
{во входном файле в первой строке содержится заданный символ, во второй - строка для поиска}
uses crt;
const
maxlen=60; {количество значащих символов строки}
type
strLtype=record
strL:array[1..maxlen] of char;
len:byte;
end;
strMtype=record
strM:array[1..maxlen+1] of char;
mk:char;
end;
{ввод строки с известной длинной}
procedure inputstrL(var f:text; var strl:strLtype; var sim:char);
{входные данные: f-дескиптор входного файла, strl-строка с изв. длиной, sim-заданный символ}
{выходные данные: f-дескиптор входного файла, strl-строка с изв. длиной}
var i:byte; {локальн. переменные: i-индекс символа строки}
begin
readln(f,sim);
i:=0;
while not eof(f) and (i<maxlen) do
begin
i:=i+1;
read(f,strl.strL[i])
end;
strl.Len:=i;
end;
{ввод строки в форме с маркером конца}
procedure inputstrM(var f:text; var strl:strMtype; var sim:char);
{входные данные: f-дескиптор входного файла, strl-строка с маркером конца строки, sim-заданный символ}
{выходные данные: f-дескиптор входного файла, strl-строка с маркером конца строки}
var i:byte; {локальн. переменные: i-индекс символа строки}
begin
strl.mk:=#13; {символ "возврат коретки"}
i:=1;
readln(f,sim);
while not eof(f) and (i<=maxlen) do
begin
read(f,strl.strM[i]);
i:=i+1;
end;
strl.strM[i]:=strl.mk;
end;
{вычисление координаты первого вхождения подстроки из 2-х одинаковых заданных}
{символов в данную строку в форме известной длины}
procedure processl(strl:strLtype; sim:char; var k:byte);
{входн данные: strl-строка с известной длиной, sim-заданный символ}
{выходные данные: k-координата...}
var
i:byte;{лок переменные: i-индекс символа строки}
begin
i:=1;
while (i<strl.len) and ((strl.strl[i]<>sim) or (strl.strl[i+1]<>sim)) do
begin
i:=i+1;
end;
if i=strl.len then k:=0 else k:=i;
end;
{вычисление координаты первого вхождения подстроки из 2-х одинаковых заданных}
{символов в данную строку в форме с меркером конца}
procedure processm(strl:strMtype; sim:char; var k:byte);
{входн данные: strl-строка с известной длиной, sim-заданный символ}
{выходные данные: k-координата...}
var
i:byte;{лок переменные: i-индекс символа строки}
begin
i:=1;
while (strl.strm[i]<>strl.mk) and ((strl.strm[i]<>sim) or (strl.strm[i+1]<>sim)) do
begin
i:=i+1;
end;
if strl.strm[i]=strl.mk then k:=0 else k:=i;
end;
{вывод строки в форме с изв длиной на экран и в файл}
procedure outL(var f:text; strl:strltype; k:integer; sim:char);
{входн данные: f-дескриптор вых файла, strl-строка с изв длиной}
{k-координаты...}
{вых данные: f-дескриптор вых файла, }
var
i:byte;{лок переменные: i-индекс символа строки}
begin
write('Для строки "');
write(f,'Для строки "');
for i:=1 to strl.len do
begin
write(strl.strl[i]);
write(f,strl.strl[i]);
end;
if (k=0) then
begin
writeln('" подстрока "',sim,sim,'" не содержится в ней.');
writeln(f,'" подстрока "',sim,sim,'" не содержится в ней.');
end else
begin
writeln('" координата первого вхождения подстроки "',sim,sim,'" равна ',k,'.');
writeln(f,'" координата первого вхождения подстроки "',sim,sim,'" равна ',k,'.');
end;
end;
procedure outM(var f:text; strl:strmtype; k:integer; sim:char);
{входн данные: f-дескриптор вых файла, strl-строка с маркером конца}
{k-координаты...}
{вых данные: f-дескриптор вых файла, }
var
i:byte;{лок переменные: i-индекс символа строки}
begin
write('Для строки "');
write(f,'Для строки "');
i:=1;
while (strl.strm[i]<>strl.mk) do
begin
write(strl.strm[i]);
write(f,strl.strm[i]);
i:=i+1;
end;
if (k=0) then
begin
writeln('" подстрока "',sim,sim,'" не содержится в ней.');
writeln(f,'" подстрока "',sim,sim,'" не содержится в ней.');
end else
begin
writeln('" координата первого вхождения подстроки "',sim,sim,'" равна ',k,'.');
writeln(f,'" координата первого вхождения подстроки "',sim,sim,'" равна ',k,'.');
end;
end;
var
strl:strltype;
strm:strmtype;
f,f1:text;
k:byte;
s,ch:char;
name_in,name_out:string;
Begin {Основная программа}
clrscr;
{write('Введите имя файла с исходным текстом: ');
readln(name_in);}
name_in:='koordin.txt';
assign(f,name_in);
{$I-}
reset(f);
{$I+}
if ioresult<>0 then
begin
writeln('Файл пуст. Конец работы.'); close(f);
end else
begin
writeln('Результаты будут выведены на экран и в файл.');
{write('Введите имя файла для вывода результатов: ');
readln(name_out);}
name_out:='koordout.txt';
assign(f1,name_out);
{$I-}
rewrite(f1);
{$I+}
if ioresult<>0 then
writeln('Не удается сформировать файл с результатом. Конец работы.')
else
begin
repeat
writeln('Выберите форму представления строки:');
writeln('L-форма с известной длиной,');
writeln('M-форма с маркером конца строки.');
readln(ch);
until (ch='l') or (ch='L') or (ch='m') or (ch='M');
if (ch='L') or (ch='l') then
begin
inputstrl(f,strl,s);
processl(strl,s,k);
outl(f1,strl,k,s)
end
else
begin
inputstrm(f,strm,s);
processm(strm,s,k);
outm(f1,strm,k,s)
end;
close(f);
close(f1);
write('Конец работы.');
{readkey;}
end;
end;
End.
4) Тестирование
|
Входные данные |
Выходные данные |
|
h asddaa |
Для строки "asddaa" подстрока "hh" не содержится в ней. |
|
a asddaa |
Для строки "asddaa" координата первого вхождения подстроки "aa" равна 5. |
|
a aaaa |
Для строки "aaaa" координата первого вхождения подстроки "aa" равна 1. |
|
a sfadasd |
Для строки "sfadasd" подстрока "aa" не содержится в ней. |
|
a sfadaasd |
Для строки "sfadaasd" координата первого вхождения подстроки "aa" равна 5. |
|
a sfadsdfddfsfgaa |
Для строки "sfadsdfddfsfgaa" координата первого вхождения подстроки "aa" равна 14. |
|
a aahaajaakkkaa |
Для строки "aahaajaakkkaa" координата первого вхождения подстроки "aa" равна 1. |
|
a fffcsffdsjcgnjskdfgcnjdfncgsdfgcjsnclnfdjgscndflcngnsckdfncgslgcngaa |
Для строки "fffcsffdsjcgnjskdfgcnjdfncgsdfgcjsnclnfdjgscndflcngnsckdfncg" подстрока "aa" не содержится в ней. |