Курс ПЯВУ 2 сем / Лабораторные. 2 сем / Лр №8. Строки / Теоретическая информ1

Строки в языке СИ. Их представление в памяти.

Основные проблемы в машинном представлении строкового типа:

 строки могут иметь достаточно существенный размер (до нескольких десятков

мегабайтов);

 изменяющийся со временем размер — возникают трудности с добавлением и

удалением символов.

Некоторые языки программирования накладывают ограничения на максимальную длину

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

Для представления строк в памяти компьютера существует два подхода.

Представление массивом символов

Строка представляется массивом символов, размер массива хранится в отдельной

(служебной) области. Поскольку этот метод был впервые реализован в языке Pascal, данный

метод получил название Pascal Strings.

Преимущества

1. размер строки всегда известен, поэтому операции добавления символов в конец,

копирования и получения размера строки выполняются быстро;

2. строка может содержать любые данные;

3. возможно на программном уровне следить за выходом за границы строки при её

обработке;

4. возможно быстрое выполнение операции вида «взятие N-ого символа с конца строки».

Недостатки

1. проблемы с хранением и обработкой символов произвольной длины (например UTF8);

2. увеличение затрат на хранение строк — значение «длина строки» также занимает

место и в случае большого количества строк маленького размера может существенно

увеличить требования алгоритма к оперативной памяти;

3. ограничение максимального размера строки. В современных языках программирования

это ограничение скорее теоретическое, так как обычно размер строки хранится в 32-

битовом поле, что даёт максимальный размер строки в 2 147 483 647 байт (2

гигабайта).

Нуль-терминированная строка

Второй подход основан на использовании "завершающего байта" или "нуль-терминатора", в

качестве которого выбирается одно из возможных значений символов алфавита (как правило,

это символ с кодом 0). Нуль-терминатор рассматривается как признака конца строки. Строка

представляется в виде последовательности байтов от начала до нуль-терминатора.

Существуют системы, в которых в качестве признака конца строки используется не символ

0, а байт 0xFF (255) или код символа «$».

Данный подход имеет еще два альтернативных названия:

1. ASCIIZ (символы в кодировке ASCII с нулевым завершающим байтом);

2. C-strings (наибольшее распространение метод получил именно в языке Си).

Для хранения строк в языке Си используют массивы символов. Например строка:

char str[10] = "string";

Будет выглядеть в памяти следующим образом:

s t r i n g NULL

0x73 0x74 0x72 0x69 0x6E 0x67 0x00 0x00 0x00 0x00

В случае если строка была введена пользователем:

char str[10] = "aaaaaaaaaa";

scanf("%s",str); // С клавиатуры вводится строка "string"

s t r i n g NULL a a a

0x73 0x74 0x72 0x69 0x6E 0x67 0x00 0x61 0x61 0x61

Пример программы на языке Си:

#include <stdio.h>

int main()

{

char str[10] = "aaaaaaaaaa";

int i;

printf("Initial string: ");

for(i=0;i<10;i++){

printf("%c - %02x\n",str[i], str[i] & 0xff);

}

printf("Input new string: ");

scanf("%s",str);

printf("Changed string: ");

for(i=0;i<10;i++){

printf("%c - %02x\n",str[i], str[i] & 0xff);

}

return 0;

}

Преимущества

1. отсутствие дополнительной служебной информации о строке (кроме завершающего

байта);

2. возможность представления строки без создания отдельного типа данных;

3. отсутствие ограничения на максимальный размер строки;

4. экономное использование памяти;

5. простота получения суффикса строки;

6. возможность использовать алфавит с переменным размером символа (например, UTF-

8).

Недостатки

1. долгое выполнение операций получения длины и конкатенации строк;

2. отсутствие средств контроля за выходом за пределы строки, в случае повреждения

завершающего байта возможность повреждения больших областей памяти, что может

привести к непредсказуемым последствиям — потере данных, краху программы и

даже всей системы;

3. отсутствие возможности использовать символ завершающего байта в качестве

элемента строки.

Представление символов строки

До недавнего времени для кодирования одного символа всегда использовался один байт (8

двоичных битов; применялись также кодировки с 7 битами на символ), что позволяло

представлять 256 (128 при семи-битной кодировке) возможных значений. Однако для

полноценного представления символов алфавитов нескольких языков (многоязыковых

документов, типографских символов — несколько видов кавычек, тире, нескольких видов

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

корейском) 256 символов недостаточно. Для решения этой проблемы существует несколько

методов:

 Переключение языка управляющими кодами. Метод не стандартизирован и лишает

текст самостоятельности (то есть последовательность символов без управляющего

кода в начале теряет смысл); использовался в некоторых ранних русификациях ZXSpectrum

и БК.

 Использование двух или более байт для представления каждого символа (UTF-16,

UTF-32). Главным недостатком этого метода является потеря совместимости с

предыдущими библиотеками для работы с текстом при представлении строки как

ASCIIZ. Например, концом строки должен считаться уже не байт со значением 0, а два

или четыре подряд идущих нулевых байта, в то время как одиночный байт «0» может

встречаться в середине строки, что приводит к некорректным результатам работы

библиотечных функций.

 Использование кодировки с переменным размером символа. Например, в UTF-8 часть

символов представляется одним байтом, часть двумя, тремя или четырьмя. Этот метод

позволяет сохранить частичную совместимость со старыми библиотеками (нет

символов 0 внутри строки и поэтому 0 можно использовать как признак конца строки),

но приводит к невозможности прямой адресации символа в памяти по номеру его

позиции в строке.

Операции со строками

Для работы со строками в стандартной библиотеке языка Си предусмотрен набор функций,прототипы которых объявлены в файле string.h, т.е. Для работы с ними необходимо подключить данный файл:

#include <string.h>

Основные функции работы со строками:

Вычисление длины строки:

Длина строк в среде программирования определяется

системной функцией strlen():

size_t strlen(const char *s);

В качестве аргумента принимается анализируемая строка. Функция возвращает длину строки

в символах без учета

нулевого ограничителя.

void main() /*пример функции*/

{char str[80];

printf("ввести строку: ");

gets(str);

printf("%d", strlen(s));

}

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

переполнение буфера:

size_t strnlen(const char *s, size_t maxlen);

Копирование строки: strcpy()/strncpy()

char *strcpy(char *dest, const char *src); //копирует строку s2 в строку s1

char *strncpy(char *dest, const char *src, size_t n); //копирует первые n

символов из строки s2 в s1

Помните, что указываемый массив-приемник s1 должен быть достаточного

размера, чтобы содержать строку-источник s2, иначе возможно переполнение буфера.

Задавая аргумент-источник не ссылкой на начало символьного массива, а адресом

любого его элемента, мы можем скопировать либо правую, либо среднюю

подстроку:

strcpy(s1,&s2[k]); //копирует правую подстроку из s2 в s1

strncpy(s1,&s[2],n); //копирует среднюю подстроку из s2 в s1

char * strcpy_my (char *s1, char *s2)/* Пример собственной функции

копирования*/

{char *ptrs1 = s1;

while (( *s1++ = *s2++) != 0);

return ptrs1;

}

Конкатенация строк:

В операция конкатенации (объединения) строк реализуется с помощью

функции strcat():

strcat(s1,s2); //добавляет s2 к s1

strncat(s1,s2,n); //добавляет n первых символов из s2 к s1

char * strcat_my (char *s1, char *s2)/*Пример собственной функции

конкатенации*/

{char *p1, *p2;

p1 = s1; p2 = s2;

while ( *p1 != ‘\0’) p1++; //найти конец 1-ой строки.

//или while ( *p1) p1++;

while (( *p1 = *p2) != 0)//копировать строку р2, пока не будет

скопирован

{p1++; // нулевой ограничитель

p2++; //Передвинуть указатели к следующему байту

} //Или while (( *p1++ = *p2++) != 0);/*.

*р1 = ‘\0’;

return s1;

}

Поиск вхождений:

Поиск вхождения одной строки в другую дает ответ на вопрос, содержится ли

значение одного текста в другом и с какой позиции обнаружено это вхождение.

Нулевая позиция в качестве результата такой операции соответствует

отрицательному ответу.

Существует несколько вариантов функций поиска вхождений:

strstr(s1,s2); //ищет вхождение строки s2 в s1 ищет вхождение

strchr(s1,c); // символа с с начала строки s1

strrcgr(s1,c); //ищет вхождение символа с конца строки s1

strpbrk(s1,s2); //ищет вхождение любого символа из s2 в s1

strspn(s1,s2); //ищет вхождение любого фрагмента, составленного из

символов s2 в s1

Сравнение/преобразование строк:

Операции сравнения отдельных символов или строк основаны на

последовательном анализе отношений числовых значений соответствующих

кодов. В кодовых страницах символы букв упорядочены в соответствии их

расположением в латинском или национальном алфавитах. Поэтому код буквы

"A" меньше кода буквы "F", код буквы "Г" меньше кода буквы "Ю" и т.д.

Необходимо учитывать что одна буква в различных регистрах имеет разные коды. В связи с

этим при упорядочении слов недостаточно выполнять сравнение символов основываясь на их

кодах, требуется,например, предварительная замена кодов всех малых букв в тексте на коды

больших (или

наоборот). Для латинских букв такая замена заключается в простом вычитании (сложении)

из кода буквы некоторого постоянного значения (смещения заглавных букв относительно

малых или наоборот). Для русских букв данное правило не выполняется Например в

кодировке ASCII цепочка малых

букв между "п" и "р" разорвана символами псевдографики, а буквы "Ё" и "ё"

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

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

в кодировке символов в разных регистрах.

Для сравнения строк Си существует набор системных функций, каждая из

которых принимает положительное значение, если ее первый

операнд строго "больше" (лексикографически) второго, нулевое значение при

"равенстве" операндов, и отрицательное значение, если первый операнд оказался

"меньше".

При сравнении русскоязычных строк, по указанным выше причинам, некоторые из них

могут работать некорректно. Рассмотрим следующую программу:

#include <stdio.h>

#include <string.h>

int main()

{

char *ptr1 = "test string";

char *ptr2 = "my test string";

char *ptr3 = "Test string";

char *ptr4 = "тестовая строка";

char *ptr5 = "моя тестовая строка";

char *ptr6 = "Тестовая строка";

char *p;

printf("English strings:\n");

printf("str1 = %s\nstr2 = %s\nstr3 =%s\n",ptr1,ptr2,ptr3);

printf("str1[0]=%d,str2[0]=%d,str3[0]=%d\n",*ptr1,*ptr2,*ptr3);

printf("1) str1 <> str2 = %d\n",strcmp(ptr1,ptr2));

printf("2) str1 <> str3 = %d\n",strcmp(ptr1,ptr3));

printf("3) str2 <> str3 = %d\n",strcmp(ptr2,ptr3));

printf("4) str3 <> str1 = %d\n",strcmp(ptr3,ptr1));

printf("5) str1 <> str1 = %d\n",strcmp(ptr1,ptr1));

printf("6) case: str1 <> str2 = %d\n",strcasecmp(ptr1,ptr2));

printf("7) case: str1 <> str3 = %d\n",strcasecmp(ptr1,ptr3));

printf("8) case: str2 <> str3 = %d\n",strcasecmp(ptr2,ptr3));

printf("Russian strings:\n");

printf("str1 = %s\nstr2 = %s\nstr3 =%s\n",ptr4,ptr5,ptr6);

printf("len(str1)=%d, len(str2)=%d,len(str3)=%d\n",

strlen(ptr4),strlen(ptr5),strlen(ptr6));

printf("1) str1 <> str2 = %d\n",strcmp(ptr4,ptr5));

printf("2) str1 <> str3 = %d\n",strcmp(ptr4,ptr6));

printf("3) str2 <> str3 = %d\n",strcmp(ptr5,ptr6));

printf("4) str3 <> str1 = %d\n",strcmp(ptr6,ptr4));

printf("5) str1 <> str1 = %d\n",strcmp(ptr4,ptr4));

printf("6) case: str1 <> str2 = %d\n",strcasecmp(ptr4,ptr5));

printf("7) case: str1 <> str3 = %d\n",strcasecmp(ptr4,ptr6));

printf("8) case: str2 <> str3 = %d\n",strcasecmp(ptr5,ptr6));

return 0;

}

Результат работы программы:

$ ./str-register

English strings:

str1 = test string

str2 = my test string

str3 =Test string

str1[0]=116,str2[0]=109,str3[0]=84

1) str1 <> str2 = 1

2) str1 <> str3 = 1

3) str2 <> str3 = 1

4) str3 <> str1 = -1

5) str1 <> str1 = 0

6) case: str1 <> str2 = 7

7) case: str1 <> str3 = 0

8) case: str2 <> str3 = -7

Russian strings:

str1 = тестовая строка (15 символов)

str2 = моя тестовая строка (19 символов)

str3 =Тестовая строка (15 символов)

len(str1)=29, len(str2)=36,len(str3)=29

1) str1 <> str2 = 1

2) str1 <> str3 = 1

3) str2 <> str3 = 1

4) str3 <> str1 = -1

5) str1 <> str1 = 0

6) case: str1 <> str2 = 1

7) case: str1 <> str3 = 1

8) case: str2 <> str3 = 26

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

1. Код символа 't' > 'T' и 't' > 'm' и 'm' > 'T'. Поэтому сравнения 1-3 дают положительный

результат (первый параметр лексикографически больше второго). Сравнение 4 дает

отрицательный результат, поскольку оно эквивалентно сравнению 2, но строки поменялись

местами. В сравнении 5 результат = 0, поскольку строка сравнивается сама с собой.

2. Для сравнения без учета регистра видим, что сравнение 6 также как и 1 дает

положительный результат. Сравнение 7 в отличие от 2 дает нулевой результат, поскольку в

строках использованы одинаковые буквы в разных регистрах. Сравнение 8 также дает другой

результат относительно сравнения 3, поскольку 'm' > 'T'; 'm' < 't' (или 'M' < 'T').

Результаты работы программы для русских строк:

1. Неверно вычислены длины строк.

2. Простые сравнения выполняются верно, поскольку отношения между русскими

символами сохраняются.

3. Сравнения без учета регистра выполняются неверно.

Поддержка кодировок, в которых один символ кодируется одним и более байтами.

Функции обработки строк можно разделить на две группы:

Не поддерживающие много-байтовые кодировки. Например:

char * strncpy (char *restrict to, const char *restrict from, size_t size)

size_t strxfrm (char *restrict to, const char *restrict from, size_t size)

char *strncat(char * restrict s1, const char * restrict s2, size_t n);

int strncasecmp (const char *s1, const char *s2, size_t n)

int islower (int c)

int strncmp(const char *s1, const char *s2, size_t n);

size_t strspn (const char *string, const char *skipset)

char * strpbrk (const char *string, const char *stopset)

char * strtok (char *restrict newstring, const char *restrict delimiters)

Поддерживающие много-байтовые кодировки. Например:

char * strcpy (char *restrict to, const char *restrict from)

strcoll (const char *s1, const char *s2)

char *strcat(char * restrict s1, const char * restrict s2)

int strcmp(const char *s1, const char *s2)

Существуют аналоги функций первой группы позволяющие корректно работать с

многобайтовыми кодировками. Они зависят от используемой кодировки, поэтому перед их

использованием необходимо задать тип используемой кодировки:

setlocale(LC_ALL, "ru_RU.UTF-8");

Далее требуется преобразование строки, хранящейся в массиве типа char к массиву

символов типа wchar_t — Wide Character type:

wchar_t *wptr3[256];

int ws1 = mbstowcs(wptr1,ptr1,strlen(ptr1));

Функция mbstows (MultiByte String TO Wide Character String) выполняет преобразование

основываясь на ранее заданном типе кодировки.

Для работы со строками с "широким" (более одного байта) символом импользуются

специальные функции. Вот некоторые из них:

#include <wchar.h>

size_t wcslen(const wchar_t *s);

int wcscasecmp(const wchar_t *s1, const wchar_t *s2);

Следующая программа позволяет выполнять корректную обработку локализованных

(записанных не латинскими символами) строк. Для работы со строками используется

специальный тип данных wchat_t — Wide Character type