LS-Sb87108

delete pStroka;

}

2.3. Обработка строки функциями встроенной библиотеки

Модельное векторное представление строки с маркером (символ с кодом 0) является основой для реализации набора функций ее обработки в библиотеке с именем string. В таблице представлены основные функции, обеспечивающие поиск, проверку содержимого на соответствие заданному критерию, элементарные преобразования (операции добавления и соединения) и вспомогательные действия. Во всех функциях обращение к содержимому строки

11

обеспечивается через указатель на используемый для ее размещения массив. Более сложные операции по обработке строки могут быть оформлены последовательным применением представленных основных функций.

2.4. Пример вариантов решения задачи преобразования строки

Рассмотрим задачу, в которой требуется инвертировать текстовую строку (обратить порядок следования символов), например: АБВГД –> ДГВБА. Используем представление строки с маркером:

const unsigned N = 10; unsigned i;

struct StrMark {char Str[N + 1]; char Mark;};

Предварительно необходимо подготовить ряд вспомогательных функций:

// Функция определения индекса последнего информационного символа int LastInd(StrMark S)

{int index = 0;

while( S.Str[index] != S.Mark ) index++; // проход по строке до маркера return index-1; } // если строка пуста, то будет возвращена -1

12

//Функция вывода содержимого строки void OutStr(StrMark S)

{unsigned i = 0;

while( S.Str[i] != S.Mark ) {cout << S.Str[i]); i++; } cout << '\n';

}

//Функция сдвига содержимого n символов строки на 1 символ влево

//Для АБВГД будет сформировано БВГДД, причем последний символ будет удвоен void sdvig1Left(StrMark S, unsigned len)

{unsigned i;

while( i != len ) { S.Str[i] = S.Str[i+1]; i++; }

}

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

//Рекурсивная функция инвертирования строки по индексу len последнего символа:

//– при числе символов в строке меньше 2 обработка не выполняется

//– иначе сохраняется символ по индексу 0, содержимое строки сдвигается на 1 символ

//влево, после чего сохраненный символ заносится на место скопированного маркера

//– предыдущие действия повторяются для строки с индексом len-1

void reverseStr(StrMark S, int len) {char z;

if(len < 1) return;

z = S.Str[0]; // запомнить первый символ строки sdvig1Left(S, len); // сдвиг содержимого от индекса len влево

S.Str[len] = z; // восстановление сохраненного первого символа на позиции len reverseStr(S, len-1); // инвертировать уменьшенную на 1 символ строку

}

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

void reverseStr2(StrMark S, int len) {char z; int i;

for( i=len; i > 0; i-- ) {z = S.Str[0]; sdvig1Left(S, i); S.Str[i] = z;

}

}

Используем оба этих варианта в одной программе.

13

void main()

{StrMark S; S.Mark = '@';

S.Str[0] = 'А'; S.Str[1] = 'Б'; S.Str[2] = 'В'; S.Str[3] = 'Г'; S.Str[4] = 'Д'; int len;

len = LastInd(S); // Для маркера '\0' можно использовать функцию из string: strlen(S.Str)-1 cout << "Исходная строка: "; OutStr(S);

cout << "\nОна содержит " << len+1 <<"символов\n";

//Инвертирование на основе рекурсии reverseStr(S, len);

cout << "Инвертированная строка: "; OutStr(S); cout << "\n";

//Повторное инвертирование - возврат в исходное состояние reverseStr2(S, len);

cout << "Восстановленная строка: "; OutStr(S); cout << "\n";

}

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

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

void swap(char *s1, char *s2) // обмен символов по указателям на их размещение в памяти

{char z;

z = *s1; *s1 = *s2; *s2 = z;

}

void reverseSwap(StrMark S, int len)

{unsigned first = 0, // индекс первого элемента строки last = len; // индекс последнего элемента строки

while(first < last) // до выхода на середину строки

{swap(&S.Str[first], &S.Str[last]); // обмен равноотстоящих от середины символов first++; // изменить индекс символа левее середины строки

last--; // изменить индекс символа правее середины строки

}

}

14

2.5. Набор функций для разных вариантов представления строки

Рассмотрим возможные реализации вспомогательных функций для вариантов представления строки с маркером или длиной – ввода и вывода содержимого строки, а также взаимного перехода между вариантами представления строк.

const N = 60;

struct StrMark {char Str[N + 1]; char Mark;};

void ReadMark1(char s, fstream* f, StrMark& m) // строка по ссылке {m.Mark = s;

int i = 0;

while( !f->eof() ) // чтение до конца файла {*f >> s;

if( !f->eof() ) // чтение до конца файла

{if( (i > N-1) // чтение пока не заполнен выделенный под строку массив

||(s == m.Mark) // чтение до маркера в файле

||(s=='\n') ) // чтение до конца строки

break; m.Str[i++] = s;

}

}

m.Str[i] = m.Mark; // появление маркера после заполнения содержимого строки

}

void ReadMark2(char s, fstream* f, StrMark* m) // строка по указателю {int i = 0;

m->Mark = s; m->Str[0] = m->Mark; while( ! f->eof() ) // чтение до конца файла {*f >> s;

if(s == '\n') break; // чтение до конца строки else

if( !f->eof() ) // чтение до конца файла

{if( i < N ) // чтение пока не заполнен выделенный под строку массив

{m->Str[i++] = s; m->Str[i] = m->Mark;} // маркер всегда в строке else break;

}

}

}

struct StrLen {char Str[N]; unsigned Len;};

void ReadLen1(fstream* f, StrLen* L) // строка по указателю {int i = 0; char s;

f->seekg(0,ios::beg); // возврат на начало файла

15

while( !f->eof() ) // чтение до конца файла {*f >> s;

if(s == '\n') break; // чтение до конца строки if( !f->eof() ) // чтение до конца файла

L->Str[i++] = s;

if(i >= N) break; // чтение пока не заполнен выделенный под строку массив

}

L->Len = i; // формирование длины после заполнения содержимого строки

}

void ReadL2(fstream* f, StrLen& L) // строка по ссылке {char s;

f->seekg(0,ios::beg); // возврат на начало файла L.Len = 0;

while( !f->eof() ) // чтение до конца файла {*f >> s;

if(s == '\n' ) break; // чтение до конца строки else

if( !f->eof() ) // чтение до конца файла

{if(L.Len < N-1) // чтение пока не заполнен выделенный под строку массив L.Str[L.Len++] = s; // число прочитанных символов всегда известно else break;

}

}

}

//Обобщенная функция чтения из файла в один из вариантов (type) представления строки

//Для представления с маркером первый символ в файле является маркером

int ReadStr(char type, fstream* f, StrMark* m, StrLen* L) // строки по указателям

{f->unsetf(ios::skipws); // указание на включение разделителей в содержимое строки char s, s1; *f>>s; s1=s;

if( !f->eof() ) // файл не пустой {switch(type)

{case 1: ReadMark1(s1, f, m); /* или ReadMark2(s1, f, *m); */ break; case 2: ReadLen1(f, *L); /* или ReadLen2(f, L); */ break;

}

}

else {switch(type)

{case 1: m->Mark = s1; m->Str[0] = m->Mark; break; case 2: L->Len = 0; break;

}

}

}

16

void ConvertLtoM(StrLen* L, StrMark* m) {m->Mark='@';

for(int i=0; i<L->Len; i++) m->Str[i] = L->Str[i]; m->Str[i] = m->Mark;

}

void ConvertMtoL(StrMark* m, StrLen* L) {for(int i=0; m->Str[i] != m->Mark; i++)

L->Str[i] = m->Str[i]; L->Len = i;

}

void OutStrLen(StrLen* L)

{for(int i=0; i<L->Len; i++) cout << L->Str[i]; cout<<endl;

}

void OutStrMark(StrMark* m)

{for(int i=0; m->Str[i] != m->Mark; i++) cout<<m->Str[i]; cout<<endl;

}

int LenStrMark(StrMark* m)

{for(int i=0; m->Str[i] != m->Mark; i++); return i;

}

2.6. Пример поиска в строке заданной группы символов

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

смаркером и длиной. Выбор способа представления должен осуществляться

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

#include <fstream.h> #include <string.h>

const unsigned MaxLen=60; // представления с длиной и маркером struct StrLType {unsigned Len; char StrL[MaxLen]; };

struct StrMType {char Mk; char StrM[MaxLen+1]; };

// ввод ограниченного числа символов из файла в строку с длиной void InputStrL(ifstream* f, StrLType* Str1)

{unsigned i=0; char s; while(i<MaxLen)

{*f>>s; if( (*f).eof() ) break; Str1->StrL[i++]=s;} (*Str1).Len=i;

}

17

//ввод ограниченного числа символов из файла в строку с маркером void InputStrM(ifstream* f, struct StrMType& Str1)

{unsigned i=0; char s; Str1.Mk='\t'; while(i<MaxLen)

{*f>>s; if((*f).eof()) break; if(s=='\n') break; Str1.StrM[i++]=s;}

Str1.StrM[i]=Str1.Mk;

}

//поиск в строке с длиной групп пробелов

void ProcessL(StrLType Str1, unsigned* N) {unsigned i;

*N=0;

for(i=0;i<Str1.Len;i++) {if(Str1.StrL[i]==' ')

{(*N)++;

while(Str1.StrL[i]==' ') {i++; if(i==Str1.Len) break;}

}

}

}

//поиск в строке с маркером групп пробелов void ProcessM(struct StrMType Str1, unsigned* N) {unsigned i=0;

*N=0;

while(1) {if(Str1.StrM[i]==' ')

{(*N)++; while(Str1.StrM[i]==' ') i++;}

if(Str1.StrM[i]==Str1.Mk) break; i++;

}

}

//вывод исходной строки в представлении с длиной

//и результата поиска групп пробелов на экран и в файл void OutResultL(ofstream* f, StrLType Str1, unsigned N) {unsigned i;

cout<<" Введена строка с длиной:"<<endl; *f<<" Введена строка с длиной:"<<endl; for(i=0;i<Str1.Len;i++)

{cout<<Str1.StrL[i]; *f<<Str1.StrL[i];} cout<<endl; cout<<endl;

*f<<endl; *f<<endl;

cout<<" Всего групп пробелов "<<N; *f<<" Всего групп пробелов "<<N;

}

18

//вывод исходной строки в представлении с маркером

//и результата поиска групп пробелов на экран и в файл

void OutResultM(ofstream* f, struct StrMType Str1, unsigned N) {unsigned i=0;

cout<<" Введена строка с маркером:"<<endl; *f<<" Введена строка с маркером:"<<endl; while(Str1.StrM[i]!=Str1.Mk)

{cout<<Str1.StrM[i]; *f<<Str1.StrM[i]; i++;} cout<<endl; cout<<endl; *f<<endl; *f<<endl;

cout<<" Всего групп пробелов "<<N; *f<<" Всего групп пробелов "<<N;

}

//основная функция, обеспечивающая выбор способа представления строки

//и обращение к функциям ее обработки

void main() {unsigned N_Space=0;

StrLType StrL; struct StrMType StrM; // оба варианта представления ifstream f_in; ofstream f_out;

char name_in[MaxLen], name_out[MaxLen]; char ch;

cout<<"Введите имя файла с исходным текстом:"; cin>>name_in; f_in.open(name_in);

if(f_in.bad()) cout<<"Указанный файл не найден."<<endl; else

{if(f_in.eof()) {cout<<"Файл пуст."<<endl; f_in.close();} else

{cout<<"Результаты будут выведены на экран и в файл."<<endl; cout<<"Введите имя файла для вывода результатов:"<<endl; cin>>name_out; f_out.open(name_out);

if(f_out.bad())

{cout<<"Нет возможности сформировать файл с результатом."<<endl; f_in.close();

}

else {do

{cout<<"Выберите форму представления строки:"<<endl; cout<<"L - форма с известной длиной,"<<endl; cout<<"M - форма с маркером конца строки."<<endl; cin>>ch;

}

while((ch!='L')&&(ch!='l')&&(ch!='M')&&(ch!='m')); f_in.unsetf(ios::skipws); // сброс режима пропуска разделителей if((ch=='L')||(ch=='l'))

19

{InputStrL(&f_in, &StrL); ProcessL(StrL, &N_Space); OutResultL(&f_out, StrL, N_Space);

}

else

{InputStrM(&f_in, StrM); ProcessM(StrM, &N_Space); OutResultM(&f_out, StrM, N_Space);

}

f_in.close(); f_out.close();

// -----------------------------------------------------------------------------------------------

//альтернативный способ решения задачи на основе представления строки с маркером –

//символом с кодом 0 и применением функций библиотеки string для пропуска

//пробельных и непробельных символов char *Uk; int pos; N_Space=0;

if((ch=='L')||(ch=='l')) {StrL.StrL[MaxLen-1]='\0'; Uk=StrL.StrL;} else {StrM.StrM[MaxLen-1]='\0'; Uk=StrM.StrM;}

while(1)

{pos=strcspn(Uk," "); /* пропуск символов не пробелов */ Uk+=pos;

pos=strspn(Uk," "); /* пропуск символов пробелов */ if(pos==0) break; N_Space++; Uk+=pos;

}

cout<<endl<<"----- Всего групп пробелов "<<N_Space;

// -----------------------------------------------------------------------------------------------

}

}

}

cout<<endl<<"Конец работы. "<<endl;

}

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

const unsigned MaxLen=60; // представления с длиной и маркером class StrLType

{unsigned Len; char StrL[MaxLen]; public:

void InputStrL(ifstream* f); void ProcessL(unsigned* N);

20