Лабораторное занятие №24
Тема: Работа со строковыми переменными.
Лабораторное занятие рассчитано на 2 часа, относится к темам:
Тема 7.1. Строки
Формируемые компетенции: ОК1-9, ПК 1.1- 1.5 ПК 3.1
Цель: научиться создавать, инициализировать строки, определять длину строки, используя указатели.
Методическое и техническое обеспечение:
компьютер с ОС Windows, программное обеспечение Borland C, Borland C++.
Теоретические сведения.
Строки относятся к фундаментальным типам данных. Строка – это последовательность символов, принадлежащих конечному множеству символов (алфавиту). Представление строк в языке программирования определяется стандартами этого языка.
В языке Паскаль предусмотрен строковый тип String. Максимальная длина строки равна 255, текущая длина строки S находится в начальном байте строки S[0].
В языке Си строковый тип не предусмотрен, строкой служит массив данных символьного типа char, определяется как charS[n], где n – максимальный размер строки типа unsigned. Заметим, что в прототипах стандартных функций Си используется другое определение этого типа: typedefunsignedsize_t. Конец строки определяется нулевым символом ‘\0’(байт, все биты которого нулевые), текущая длина строки равна числу символов до символа ‘\0’, исключая его. Массив символов без конечного символа ‘\0’ не может рассматриваться как строка, это просто массив символьных данных. В языке предусмотрена строковая константа (литерал) – это последовательность символов заключенных в двойные кавычки, например «Структуры данных». Строковая константа заканчивается нулевым символом ‘\0’.
Для эффективного манипулирования строками современные системы программирования содержат обширные средства и функции.
Рассмотрим алгоритмы выполнения некоторых операций над строками применительно к языку Си и прототипу соответствующих стандартных функций.
Ниже приведем программу с возможными реализациями этих функций, причем названия функций в программе получены добавлением символа 1 к названиям стандартных функций, например, strcmp – strcmp1.
Создание и инициализация строки. Строка определяется как массив данных символьного типа, например chars[80]. Транслятор выделяет под массив 80 байт, значит, максимальная длина строки будет 79 символов. В Си не предусмотрен механизм контроля выхода за пределы массива (строки), по этому ответственность за правильность использования строки несет программист. Если массив определен как автоматический (в пределах функции), то выделенную область памяти транслятор не очищает, статистические массивы инициализируются нулевыми байтами, а это означает, что текущая длина строки равна 0.
Строка может быть инициализирована при ее определении: chars[40]=”Это строка данных”; Здесь оставшиеся свободными байты инициализируются нулями. Однако нельзя присвоить такой строке новое значение оператором присваивания, например оператор S = “Новая строка” является ошибочным.
Можно определить динамическую строку:
Char* s1; s1 = (char*) calloc(40,sizeof(char));
Только такой строке в любой момент оператором присваивания можно присвоить значение строковой константы: S1 = “Иванов Иван Иванович”.
Определение длины строки S; Осуществляется последовательным просмотром и подсчетом символов S[i], пока не встретится символ конца строки ‘\0’. Прототип функции: size_tstrlen(constchar *S); результат (возвращаемое значение) – длина строки в байтах.
Заполнение строки заданным символом. Осуществляется только в пределах текущей длины строки, т.е. все символы строки от ее начала до конечного ‘\0’ заменяется заданным символом, при этом длина строки остается прежней. Прототип функции:
Char* strset(char *S, intc), результат – указатель на начало строки S.
Заполнение части строки заданным символом. Отличается тем, что заполняется только заданное число n символов, но в пределах текущей длины строки. Прототипфункции: Char* strcpy(char *S, int c, size_t n).
Копирование строки S2 в строку S1. Строка S1 заполняется символами из строки S2, включая символ конча строки ‘\0’. Контроль выхода за пределы массива под строку S1 не осуществляется, это возлагается на программиста. Прототип функции:
Char* strcpy(char* S1, char* S2), результат – указатель на строку S1.
Соединение(Конкатенация) строк S1 и S2. К концу строки S1, начиная с символа конца строки ‘\0’, копируется строка S2. Строка S2 сохраняется. Длина строки S1 становиться равной длин строк S1 и S2, по этому память, выделенная под S1, должна быть не меньше этой длины. Прототип функции:
Char* strcat(charS1, constchar* S2), возвращаемое значение – указатель на строку S1.
Можно предложить другой вариант этой операции, когда соединением двух строк создается новая строка динамической памяти.
Сравнение двух строк S1 и S2. Осуществляется посимвольным сравнением строк. Так как длины строк L1 и L2 могут отличаться, то число сравниваемых символов ограничивается значением min(L1,L2) + 1. В этом случае последними сравниваются символ из более длиной строки и нулевой символ ‘\0’, замыкающий короткую строку. Сравнение строк заканчивается, когда будут исчерпаны все сравниваемые символы либо при неравенстве очередной пары символов. Результат операции опре6деляется результатом последнего сравнения:
(S1[i] = = S2[i]) – равеннулю,
(S1[i] < S2[i]) – меньшенуля,
(S1[i] > S2[i]) – большенуля.
Прототипфункции:
Intstrcmp(const char* S1, const char* S2). В ранних версиях ТС сравнение проводиться в предложении, что символы принадлежат к типу signedchar. Это приводит к ошибочным результатам при сравнении строк типа «Иванов» и «Иван», когда начальные символы совпадают, а последний сравниваемый символ более длиной строки является символом из второй половины кодовой таблицы. Этот недостаток устранен в функции strcmp1, приведенной ниже.
Поиск и выделение лексических единиц в строке. Является полезной операцией для выделения отдельных частей строки, разделенных заданными символами – ограничителями. Прототип функции:
Char* strtok(char* S1, constchar* S2); в строке S1 осуществляется поиск до первого любого символа - ограничителя, заданного строкой S2. Найденный символ – ограничитель в строке S1 заменяется символом конца строки ‘/0’. Возвращаемое значение – указатель на начало строки. Таким образом, в виде урезанной начальной строки выделяется первая лексическая единица, а исходная строка оказывается разбитой на две строки по месту первого найденного символа ограничителя, но этого символа в строке S1 уже нет. Если нужно выделить все лексические единицы в строке S1, то достаточно вызывать функцию strtok с первым аргументом, равным NULL, до тех пор, пока возвращаемое значение не станет равным нулю (NULL). Если в строке S1 встретиться несколько подряд идущих символов из строки S2, то первый из них замениться символом ‘/0’, остальные остануться на месте, однако следующий оператор strtok опустит их и вернет указатель на следующую лексему.
Важнейшими операциями для манипулирования строками являются операции поиска по образцу. Поиск по образцу в строке считается успешным, если в ней найдена подстрока или символ, соответствующие образцу с точки зрения заданного условия или совокупности условий.
Поиск заданного символа в строке. Имеет две разновидности. Поиск первого вхождения символа. Определяет позицию, в которой встретился заданный символ при последовательном просмотре символов с начала строки. Поиск последнего вхождения. Отличается тем, что просмотр символа идет от конца строки к ее началу. Прототипы функций:
Char* strchr(constchar* S, intc) и char* strrchr(constchar* S, intc), возвращаемое значение – указатель на найденный символ или NULL, если символ не найден.
Поиск в основной строке S1 символов, заданных в строке S2. Имеют три разновидности операции. Первая из них – поиск в строке S1 первого вхождения одного из символов, заданных в строке S2. Осуществляется просмотр символов S1[i], начиная с начала строки и до ее конца. Если очередной символ S1[i] совпадает с любым из символов строки S2, то поиск прекращается. Возвращаемое значение – указатель на найденный символ или NULL, если в строке не оказалось символа из строки S2. Алгоритм основан на простом переборе: с каждым символом S[i] сравниваются все символы из строки S2, следовательно, временная сложность в худшем случае O(L1*L2), где L1 и L2 – длины строк S1 и S2 соответственно. Прототипфункции:
Char* strpbrk(const char* s1, const char* s2).
Вторая операция отличается от первой только тем, что определяется длина начальной части строки S1, в которой нет символов из строки S2. Прототипфункции:
Size_tstrspn(const char* S1, const char* S2).
Третья операция отличается от второй тем, что определяется длина начальной части строки S1, в которой содержаться только такие символы, которые принадлежат множеству символов из строки S2. Прототипфункции:
size_tstrcspn(const char* S1, const char* S2).
Поиск подстроки (образца) S2 в строке S1. Является наиболее широко используемой операцией. Очевидно, что длина L2 в подстроке S2 не может быть больше длины L1 строки S1. Прототипфункции: char* strstr(const char* S1, const char* S2). Возвращаемое значение – указатель на первы1й символ найденной в S1 подстроки.
Известно несколько алгоритмов поиска подстроки в строке. В алгоритме прямого перебора сначала первые L2 символа строки S1 сравниваются с соответствующими символами образца S2. Если все символы в парах окажутся равными, то на этом поиск заканчивается. В противном случае образ S2 сдвигается в строке S1 на одну позицию вправо и осуществляется сравнение следующих L2 символов и так до тех пор, пока либо все символы не совпадут, либо после (L1 – L2) сдвигов не будет достигнут конец строки S1. Результатом является указатель на первый символ в строке S1, с которого начинается искомая подстрока в случае удачи, либо NULL, если подстрока не найдена. Этот алгоритм достаточно эффективен в том случае, когда не совпадение пары символов происходит после всего лишь нескольких сравнений.
Улучшением алгоритма перебора являются алгоритм Кнута, Мориса и Пратта (КМП) и алгоритм Боуера и Мура (БМ).
Алгоритм КМП базируется на том, что после частичного совпадения начальной части образа s2 с соответствующими символами строки s1 и при несовпадении очередной пары.
1. Функция определения длины строки
int strlen1 (const char *s)
{ inti = 0;
While (s[i]!= ‘\0’) i++; returns;}
2. Заполнение строки заданным символом
char strset1 (char *s, int c)
{ inti = 0;
while (s[i]!= ‘\0’) { s[i] = c; i++; }return s;}
3. Заполнение части строки заданным символом
char strnset1 (char *s, int c, int n)
{ inti = 0;
while (s[i]!= ‘\0’ && j<n) { s[i] = c; i++; j++;}return s;}
4. Соединениедвухстрок
char strcat1 (char *s1, char *s2)
{ inti, j, L1,L2 = 0;
L1=strlen(s1); L2=strlen(s2); j = 0;
for (I = L1; i<=L1+L2; i++) s1[i] =s2[j++];
returns1;}
Пример выполнения задания.
Скопировать строки из s2 в строку s1;
#include <iostream>
#include <string.h>
using namespace std;
char* soedin (char*s1, char*s2)
{
int i, j, L1, L2=0;
L1=strlen(s1); L2=strlen(s2);
j=0;
for (i=L1;i<=L1+L2;i++) {s1[i]=s2[j++];}
return s1;
}
int main()
{ int i;
char* S[30], S1[30], S2[30];
cout<<"Vvedite stroki "<<endl;
cin>>S1;
cin>>S2;
cout<<soedin(S1,S2)<<endl;
return 0;
}
Порядок выполнения работы:
― изучить теоретические сведения;
― изучить индивидуальное задание;
― разработать алгоритм его решения (разработать математическую модель, реализовать в виде блок-схемы);
― написать программу;
― оттестировать программу на различных комбинациях входных значений;
― продемонстрировать работу преподавателю;
― оформить отчет.
Содержание отчета:
1. Задание.
2. Блок-схема.
3. Листинг программы.
4. Тестовый пример.
Контрольные вопросы:
1. Строковый тип данных
2. Описание строковой переменной
3. Операторы для работы со строковыми переменными
4. Стандартные функции для работы со строковыми переменными
Список литературы:
Основная литература
1. Семакин И.Г., Шестаков А.П. Основы алгоритмизации и программирования. Учебник. М.: АСАДЕМА, 2016
2. Семакин И.Г., Шестаков А.П. Основы алгоритмизации и программирования. Практикум. М.: АСАДЕМА, 2016
Дополнительная литература
1. Голицына О.Л., Попов И.И. Программирование на языках высокого уровня Учебное пособие М.: ФОРУМ, 2008
2. Голицына О.Л, Партыка Т.Л., Попов И.И. Программное обеспечение Учебное пособие М.: ФОРУМ, 2008
3. Колдаев В.Д Основы алгоритмизации программирования Учебное пособие М.: ФОРУМ-ИНФРА-М,2009
Индивидуальные задания.
Задание. Составить функции:
1. Соединения двух строк в динамической памяти;
2. Определение начала строки s1, в которой только символы из строки s2;
3. Сравнить две строки;
4. Скопировать строки из s2 в строку s1;
5. Заполнить часть строки указанным символом;
6. Скопировать строку в динамическую память;
7. Определить первое вхождение в строку заданного символа;
8. Определить первое вхождение одного из символов строки s2 в строке s1;
9. Определить начало строки s1, в которой нет символов из строки s2;
10. Определить длину строки s1, в которой нет символов из строки s2;