2. Строки
Строка в языке С++ – это одномерный массив символьного типа char. Массив из n символов на самом деле будет содержать не n, а n-1 значащий символ. Причиной этого является то, что строка всегда содержит маркер или признак конца строки – это символ ’\0’. Строки на С++ заключаются в кавычки.
При объявлении строк нужно учитывать условие решаемой задачи. Если количество символов, содержащихся в строке, можно определить заранее, то можно работать со строкой как со статическим массивом символов. Если количество символов в строке определяется программно или вычисляется некоторым образом, то в этом случае разумнее использовать динамический массив символов.
Объявлять строки можно двумя способами:
-
Строка – динамический массив символов:
char * s;
При таком объявлении массива в программе нужно будет обязательно выделить динамическую память под указатель s. Далее можно работать со строкой как с динамическим массивом символов;
-
Строка – статический массив символов:
char s[500];
Обрабатываются строки, содержащие не более 499 символов, со строкой можно работать как со статическим массивом.
Поскольку строки являются одномерными массивами, то возможна их инициализация при объявлении:
char s[ ]= “строка”;
В данном случае строка s будет содержать 7 элементов (символов): ‘с’, ‘т’, ‘р’, ‘о’, ‘к’, ‘а’, ‘\0’. Однако невозможно присваивание вида
char s[ 20];
s=“строка”;
так как операция присваивания для строк не определена.
Если приходится работать с несколькими строками, то можно объявить массив строк – двухмерный массив символов.
char st [5][200];
Такой массив может содержать 5 строк, в каждой из которых может быть не более 199 символов.
По причине того что над строками в языке С++ не определены операции отношения, сложения и т.п., для этих целей разработаны библиотечные функции, описанные в головных файлах string.h и stdio.h (табл.9).
|
Таблица 9 |
|
|
Файл string.h |
|
|
Функция |
Форма обращения к функции и её краткое описание |
|
1 |
2 |
|
atof |
d = atof(str) ; Преобразует строку str в вещественное число d d – переменная типа double; str – строка, в которой записано вещественное число в виде набора символов–цифр и точки. Переводится часть строки, начиная с крайнего левого символа до первого появления символа, отличного от цифры или точки |
|
atoi |
i = atoi(str); Преобразует строку str в десятичное целое число i i – переменная типа int; str – строка, в которой записано целое число в виде набора символов-цифр. Переводится часть строки, начиная с крайнего левого символа до первого появления символа, отличного от цифры |
|
atol |
l = atol(str); Преобразует строку str в длинное десятичное целое число l l – переменная типа long; str – строка, в которой записано целое число в виде набора символов-цифр. Переводится часть строки, начиная с крайнего левого символа до первого появления символа, отличного от цифры |
|
itoa |
itoa(v,str,baz); Преобразует целое v в строку str. При изображении числа используется основание системы счисления baz (2<=baz<=36) v – переменная типа int; str – строка; baz – переменная типа int |
|
ltoa |
ltoa(v,str,baz); Преобразует длинное целое v в строку str. При изображении числа используется основание baz (2<=baz<=36) l – переменная типа long; str – строка; baz – переменная типа int |
|
strcat |
strcat(str1,str2) ; Приписывает строку str2 в конец строки str1 (конкатенация строк) Результат в строке str1 |
|
strncat |
strncat(str2,str1,kol); Приписывает kol символов строки str1 в конец строки str2 (конкатенация) kol – переменная типа int |
|
strchr |
str2 = strchr(str1,сh); Ищет в строке str1 первое вхождение символа сh (тип char). В строку str2 записывается часть строки str1, начинающаяся с первого вхождения символа ch. Если такой символ не найден, то str2 равно NULL |
|
strrchr |
str2 = strrchr(str1,сh); Ищет в строке str1 последнее вхождение символа сh (тип char). В строку str2 записывается часть строки str1, начинающаяся с последнего вхождения символа ch. Если такой символ не найден, то str1 равно NULL |
|
strcmp |
i = strcmp(strl,str2); Сравнивает строки strl и str2. Результат заносится в переменную i (тип int) i<0, если strl<str2; i=0, если strl==str2; i>0, если strl>str2 (сравнение беззнаковое посимвольное) |
|
Продолжение таблицы 9 |
|
|
1 |
2 |
|
strcpy |
strcpy(str1, str2); Копирует символы строки str2 в строку str1 |
|
strncpy |
strncpy(str2,str1,kol); Копирует kol символов строки str1 в строку str2 («хвост» отбрасывается или дополняется пробелами) kol – переменная типа int |
|
strlen |
i = strlen(str); Вычисляет длину строки str без символа ‘\0’. Результат – в переменной i (типа unsigned int) |
|
Файл stdio.h |
|
|
Функция |
Форма обращения к функции и её краткое описание |
|
gets |
gets(str); Считывает строку str как введенную с клавиатуры последовательность символов до первого нажатия клавиши <enter> |
|
puts |
puts (str); Выводит строку str на экран |
Примечание. Строку можно вводить с клавиатуры с помощью функции gets() и функции scanf(). При этом нужно помнить, что если первая функция заполняет строку символами до первого нажатия клавиши <enter>, то вторая записывает в строку введенные с клавиатуры символы до появления первого пробела.
При решении задач, связанных с обработкой текста, с заданным текстом работают как со строкой. Таким образом, алгоритмы решения подобных задач основаны на алгоритмах обработки массивов. В данном случае это массивы символов.
Пример 1. Дан текст. Распечатать текст в обратном порядке.
Ход выполнения работы
-
Алгоритмы решения задач с использованием строк основаны на алгоритмах обработки одномерных массивов.
-
Написать программу, соответствующую алгоритму:
Алгоритм
Программа
объявление симв: *str; цел: i, n,
// ввод количества символов текста
ввод n
выделить динамическую память под указатель str
ввод строки str
//в цикле проверяется каждый символ,
//начиная с последнего
для i= strlen(str) до 0 шаг -1
печать stri
все для i
освободить выделенную под указатель str динамическую память
#include "stdio.h"
#include "stdlib.h"
#include "string.h"
int main ( )
{
char *str;
int n;
unsigned int i;
//ввод n
printf ("n=" );
scanf ("%i", &n);
//выделяется динамическая память
str=(char*)malloc(n);
//ввод строки
gets(str);
for ( i= strlen(str); i>=0; i-- )
{
printf("%c",*(str+i));
}
printf("\n");
//освобождение выделенной
//динамической памяти
free(str);
return 1;
}
-
Создать проект и реализовать данную задачу в среде Visual C++ 6.0.
Пример 2. Дан текст. Подсчитать, сколько в нем слов. Словом считать набор символов, не содержащий символов: ‘.’ , ‘!’ , ‘?’ , ‘,’ , ‘;’ , ‘:’, ‘ ’. Подсчитать количество слов, содержащих 5 символов.
Ход выполнения работы
-
Для подсчета количества символов, содержащихся в каждом слове текста, необходимо определить начало и конец слова, т.е. определить позиции первого и последнего символов каждого слова. Найдя их разность, сравним её с числом 5. Если нужное слово найдено, то увеличим некоторый счетчик на 1. Первый символ слова определим по правилу: если в позиции i находится один из символов ‘.’ , ‘!’ , ‘?’ , ‘,’ , ‘;’ , ‘:’ , ‘ ’, а в позиции i+1 нет ни одного из них, то, с позиции i+1 начинается слово. Последний символ слова определим по правилу: если в позиции i нет ни одного из символов ‘.’ , ‘!’ , ‘?’ , ‘,’ , ‘;’ , ‘:’ , ‘ ‘, а в позиции i+1 находится один из них, то, начиная с позиции i, слово заканчивается.
-
Написать программу, соответствующую алгоритму:
Алгоритм
Программа
объявление симв: *str; цел: i, n, bw, ew, count, count_5
// ввод количества символов текста
ввод n
выделить динамическую память под указатель str
ввод строки str
count =0, count_5=0
//в цикле проверяется каждый символ
для i=0 до strlen(str) шаг 1
//определяем первый символ слова
пока stri=='.' или stri=='!' или stri=='?'
или stri==',' или stri==';'
или stri==':' или stri==' '
и i<=strlen(str)
//пропускаем эти символы
i++
все_пока
//запоминаем позицию начала слова
bw=i
//определяем последний символ слова
пока stri!='.' и stri!='!' и stri!='?' и stri!=','
и stri!=';' и stri!=':' и stri!=' '
и i<=strlen(str)
//пропускаем символы слова
i++
все_пока
//запоминаем позицию конца слова
ew=i-1
если ew-bw>=0
count++
все_если
если ew-bw+1==5
count_5++
все_если
все для i
вывод count
вывод count_5
вывод строки str
освободить выделенную под указатель str динамическую память
#include "stdio.h"
#include "stdlib.h"
#include "string.h"
int main ( )
{
char *str;
int n, bw, ew, count, count_5;
unsigned int i;
//ввод n
printf ("n=" );
scanf ("%i", &n);
//выделяется динамическая память
str=(char*)malloc(n);
//ввод строки
gets(str);
count =0, count_5=0;
for ( i=0; i<=strlen(str); i++ )
{
//определяем первый символ
//слова
while((*(str+i)=='.' || *(str+i)=='!' ||
*(str+i)=='?' || *(str+i)==',' ||
*(str+i)==';' || *(str+i)==':' ||
*(str+i)==' ')
&& i<=strlen(str))
//пропускаем эти символы
i++;
//запоминаем позицию начала
//слова
bw=i;
//определяем последний символ
//слова
while(*(str+i)!='.' && *(str+i)!='!'
&& *(str+i)!='?'&&
*(str+i)!=',' && *(str+i)!=';'
&& *(str+i)!=':' &&
*(str+i)!=' '&& i<=strlen(str))
//пропускаем символы
//слова
i++;
//запоминаем позицию конца
//слова
ew=i-1;
if(ew-bw>=0)
count++;
if(ew-bw+1==5)
count_5++;
}
//вывод count
printf(“количество слов в тексте = %i\n”,count);
//вывод count_5
printf(“количество слов из 5 символов
= %i\n”,count_5);
//вывод строки str
puts(str);
//освобождение выделенной динамической памяти
free(str);
return 1;
}
-
Создать проект и реализовать данную задачу в среде Visual C++ 6.0.
Запишем те же алгоритм и программу с использованием статического массива:
|
Алгоритм |
Программа |
|
объявление симв: str[200]; цел: i, bw, ew, count, count_5 ввод строки str count =0, count_5=0 //в цикле проверяется каждый символ для i=0 до strlen(str) шаг 1 //определяем первый символ слова пока str[i]=='.' или str[i]=='!' или str[i]=='?' или str[i]==',' или str[i]==';' или str[i]==':' или str[i]==' ' и i<=strlen(str) //пропускаем эти символы i++ все_пока //запоминаем позицию начала слова bw=i //определяем последний символ слова пока str[i]!='.' и str[i]!='!' и str[i]!='?' и str[i]!=',' и str[i]!=';' и str[i]!=':' и str[i]!=' ' и i<=strlen(str) //пропускаем символы слова i++ все_пока //запоминаем позицию конца слова ew=i-1 если ew-bw>=0 count++ все_если если ew-bw+1==5 count_5++ все_если все для i вывод count вывод count_5 вывод строки str
|
#include "stdio.h" #include "stdlib.h" #include "string.h" #define n 200 int main ( ) { char str[n]; int bw, ew, count, count_5; unsigned int i; //ввод строки gets(str); count =0, count_5=0; for ( i=0; i<=strlen(str); i++ ) { //определяем первый символ //слова while((str[i]=='.' || str[i]=='!' || str[i]=='?'|| str[i]==',' || str[i]==';' || str[i]==':' || str[i]==' ') && i<=strlen(str)) //пропускаем эти символы i++; //запоминаем позицию начала //слова bw=i; //определяем последний символ //слова while(str[i]!='.' && str[i]!='!' && str[i]!='?'&& str[i]!=',' && str[i]!=';' && str[i]!=':' && str[i]!=' ' && i<=strlen(str)) //пропускаем символы //слова i++; //запоминаем позицию конца //слова ew=i-1; if(ew-bw>=0) count++; if(ew-bw+1==5) count_5++; } //вывод count printf(“количество слов в тексте = %i\n”,count); //вывод count_5 printf(“количество слов из 5 символов = %i\n”,count_5); //вывод строки str puts(str); return 1; } |
Примечание. Синтаксис программы, использующий статический массив, несколько проще и более понятен при чтении. Однако использование динамических массивов делает решение более гибким, поскольку в этом случае имеется возможность динамического изменения длины строки в ходе выполнения программы.
Пример 3. Дан текст. Распечатать текст по предложениям. Предложением считать набор символов, заканчивающийся одним из символов: ‘.’ , ‘!’ , ‘?’.
Ход выполнения работы
-
Написать программу, соответствующую алгоритму:
Алгоритм
Программа
объявление симв: *str; цел: i, j, n, bp, ep
// ввод количества символов текста
ввод n
выделить динамическую память под указатель str
ввод строки str
//в цикле проверяется каждый символ
для i=0 до strlen(str) шаг 1
//определяем первый символ
// предложения
пока stri=='.' или stri=='!' или stri=='?'
и i<=strlen(str)
//пропускаем эти символы
i++
все_пока
//запоминаем позицию начала
// предложения
bp=i
//определяем последний символ
//предложения
пока stri!='.' и stri!='!' и stri!='?' и
i<=strlen(str)
//пропускаем символы слова
i++
все_пока
//запоминаем позицию конца
//предложения
ep=i
//печатается очередное предложение
для j= bp до ep шаг 1
печать strj
все_для j
все для i
освободить выделенную под указатель str динамическую память
#include "stdio.h"
#include "stdlib.h"
#include "string.h"
int main ( )
{
char *str;
int j, n, bp, ep;
unsigned int i;
//ввод n
printf ("n=" );
scanf ("%i", &n);
//выделяется динамическая память
str=(char*)malloc(n);
//ввод строки
gets(str);
for ( i=0; i<=strlen(str); i++ )
{
//определяем первый символ
// предложения
while((*(str+i)=='.' || *(str+i)=='!' ||
*(str+i)=='?') &&
i<=strlen(str))
//пропускаем эти символы
i++;
//запоминаем позицию начала
//предложения
bp=i;
//определяем последний символ
//предложения
while(*(str+i)!='.'&&*(str+i)!='!'&&
*(str+i)!='?'&& i<=strlen(str))
//пропускаем символы
//слова
i++;
//запоминаем позицию конца
// предложения
ep=i;
//печатается очередное
//предложение
for(j=bp;j<=ep;j++)
//выводится j-ый символ
//предложения
printf("%c",*(str+j));
printf("\n");
}
//освобождение выделенной
//динамической памяти
free(str);
return 1;
}
-
Создать проект и реализовать данную задачу в среде Visual C++ 6.0.
Пример 4. Дан текст. Распечатать позиции, начиная с которых в тексте встречается заданное слово. Определение слова такое, как и в предыдущих примерах.
Ход выполнения работы
-
Написать программу, соответствующую алгоритму
Алгоритм
Программа
объявление симв: *text,*slovo; цел: i, j, n, bw, ew, flag
// ввод количества символов текста
ввод n
выделить динамическую память под указатели text, slovo
ввод text
ввод slovo
//в цикле проверяется каждый символ
для i=0 до strlen(text) шаг 1
//определяем первый символ слова
пока texti=='.' или texti=='!' или
texti=='?' или texti==',' или
texti==';' или texti==':'
или texti==' ' и i<=strlen(text)
//пропускаем эти символы
i++
все_пока
//запоминаем позицию начала слова
bw=i
//определяем последний символ слова
пока texti!='.' и texti!='!' и texti!='?' и
texti!=',' и texti!=';' и texti!=':' и
texti!=' ' и i<=strlen(text)
//пропускаем символы слова
i++
все_пока
//запоминаем позицию конца слова
ew=i-1
//сравниваем slovo и слово текста
если ew-bw+1== strlen(slovo)
flag=1;//длины слов совпадают
для j= 0 до ew-bw шаг 1
если textbw+j !=slovoj
flag=0;//слова не совпадают
выход из цикла по j
все_если
все_для j
все_если
если flag==1
flag=0
печать bw
все_если
все для i
освободить выделенную под указатели text, slovo динамическую память
#include "stdio.h"
#include "stdlib.h"
#include "string.h"
int main ( )
{
char *text,*slovo;
int j, n, bw, ew, flag;
unsigned int i;
//ввод n
printf ("n=" );
scanf ("%i", &n);
//выделяется динамическая память
text=(char*)malloc(n);
slovo=(char*)malloc(20);
//ввод строк
puts("text=");
gets(text);
puts("slovo=");
gets(slovo);
for ( i=0; i<=strlen(text); i++ )
{
//определяем первый символ слова
while((*(text+i)=='.' || *(text+i)=='!' ||
*(text+i)=='?'|| *(text+i)==',' ||
*(text+i)==';' || *(text+i)==':' ||
*(text+i)==' ')
&& i<=strlen(text))
//пропускаем эти символы
i++;
//запоминаем позицию начала
//слова
bw=i;
//определяем последний символ
// слова
while(*(text+i)!='.'&&*(text+i)!='!'
&& *(text+i)!='?'&&
*(text+i)!=','&& *(text+i)!=';'
&&*(text+i)!=':'&&
*(text+i)!=' '
&& i<=strlen(text))
//пропускаем символы слова
i++;
//запоминаем позицию конца
//слова
ew=i-1;
if(ew-bw+1== strlen(slovo))
{
flag=1;
for(j=0;j<=ew-bw;j++)
if(*(text+bw+j)!=*(slovo+j))
{
flag=0;
break;
}
}
if(flag==1)
{
flag=0;
printf("pos=%i\n",bw);
}
}
//освобождение выделенной
//динамической памяти
free(text);
free(slovo);
return 1;
}
-
Создать проект и реализовать данную задачу в среде Visual C++ 6.0.
Пример 5. Дан текст в виде набора 0 и 1 – некоторое число в двоичной системе счисления. Представить это число в десятичной системе счисления.
Ход выполнения работы
-
Алгоритм перевода числа из двоичной системы счисления в десятичную систему счисления поясним на примере.
|
Наименование |
Разряды в двоичной системе счисления |
Число |
||||||
|
6 |
5 |
4 |
3 |
2 |
1 |
0 |
||
|
Число в двоичной системе счисления, записанное по разрядам |
1 |
1 |
0 |
1 |
0 |
0 |
1 |
11010012 |
|
Слагаемые для получения числа в десятичной системе счисления, соответствующие каждому разряду |
1·26 |
1·25 |
0·24 |
1·23 |
0·22 |
0·21 |
1·20 |
10510 |
-
Написать программу, соответствующую алгоритму:
|
Алгоритм |
Программа |
|
объявление вещ: *num_bin; цел: i, j, n, num_dec // ввод количества символов текста ввод n выделить динамическую память под указатель num_bin ввод num_bin j=strlen(num_bin)-1 num_dec=0 //в цикле проверяется каждый символ для i=strlen(num_bin) до 0 шаг -1 //сравниваем символ текста с // символом ‘1’ если num_bini = = ‘1’ num_dec=num_dec+2j-i все_если все для i печать num_dec освободить выделенную под указатель num_bin динамическую память
|
#include "stdio.h" #include "stdlib.h" #include "string.h" #include "math.h" int main ( ) { char *num_bin; int n, num_dec; unsigned int i; //ввод n printf ("n=" ); scanf ("%i", &n); //выделяется динамическая память num_bin=(char*)malloc(n); //ввод строки puts("num_bin="); gets(num_bin ); //определяется количество разрядов j=strlen(num_bin)-1; //инициализируется значение в //десятичной системе num_dec=0; for ( i= strlen(num_bin); i>=0; i-- ) { // сравниваем символ текста с // символом ‘1’ if(*(num_bin+i)= =’1’) { num_dec=num_dec+pow(2, j-i); } } printf("num_dec=%i\n ",num_dec); //освобождение выделенной //динамической памяти free(num_bin); return 1; } |
-
Создать проект и реализовать данную задачу в среде Visual C++ 6.0.
Пример 6. Дано целое число в десятичной системе счисления. Представить это число в двоичной системе счисления.
Ход выполнения работы
-
Алгоритм перевода числа из десятичной системы счисления в двоичную осуществляется путем деления десятичного числа на 2. Запоминается остаток, и полученное частное снова делится на 2. Эта процедура повторяется до тех пор, пока полученное на некотором шаге частное не станет равным 0 или 1. Записав остатки от деления в обратном порядке, получим число в двоичной системе счисления (в программе результат помещается в строку), например:
1
05
2
1 52 2
0 26 2
0 13 2
1 6 2
0 3 2
1 1
Таким образом, 10510 = 11010012 (порядок записи остатков указан стрелкой). Решить данную задачу можно было бы с использованием операции деления, т.е. непосредственно по приведенному алгоритму. Воспользовавшись поразрядными операциями и понятием маски можно упростить решение задачи. Для этого установим начальное значение маски в 1. При помощи операции & проверим, совпадает ли самый правый бит с маской или нет. Если совпадает, то в текущую позицию строки записываем 1, в противном случае – 0. Затем сдвигаем 1 в маске на одну позицию влево. Опять происходит описанная выше проверка и т.д. Количество проверок должно совпадать с количеством бит переменной (десятичным числом), т.е. с размером типа этой переменной, умноженного на 8 (количество байт, занимаемых переменной в ОП, умножаем на количество бит, содержащихся в одном байте).
-
Написать программу, соответствующую алгоритму:
Алгоритм
Программа
объявление вещ: *num_bin; цел: i, n, num_dec, mask=1
ввод num_dec
n=sizeof(num_dec)*8
выделить динамическую память под указатель num_bin из n+1 символов
//в цикле проверяется каждый бит
для i=1 до n+1 шаг 1
//проверяем i-ый бит числа num_dec
//на наличие 1
если num_dec&mask
num_binn+1-i = = ‘1’
иначе
num_binn+1-i = = ‘0’
все_если
сдвиг mask на 1 разряд влево
все для i
печать num_bin
освободить выделенную под указатель num_bin динамическую память
#include "stdio.h"
#include "stdlib.h"
#include "string.h"
#include "math.h"
int main ( )
{
char *num_bin;
int num_dec, mask=1;
int n, i;
//ввод десятичного числа
printf("num_dec=");
scanf("%d",&num_dec);
n=sizeof(num_dec)*8;
//выделяется динамическая память
num_bin=(char*)malloc(n+1);
for ( i= 1; i<=n+1; i++ )
{
// проверяем i-ый бит числа
// num_dec на наличие 1
if(num_dec&mask)
//i–ый бит числа num_dec
//содержит 1
*(num_bin+n+1-i)='1';
else
//i–ый бит числа num_dec
//содержит 0
*(num_bin+n+1-i)='0';
//изменение маски
mask=mask<<1;
}
printf("num_bin=");
// нули до первой 1 не печатаются
for(i= 1; i<=n+1; i++)
if(*(num_bin+i)!=0)
break;
// печатается число в двоичной системе
for( ; i<=n; i++)
printf("%c",*(num_bin+i));
printf("\n");
//освобождение выделенной
//динамической памяти
free(num_bin);
return 1;
}
-
Создать проект и реализовать данную задачу в среде Visual C++ 6.0.