Способы представления текстовых строк

Строки в языке C

Строка — это последовательность ASCII или UNICODE символов.

Строки в C, как и в большинстве языков программирования высокого уровня рассматриваются как отдельный тип, входящий в систему базовых типов языка. Так как язык C по своему происхождению является языком системного программирования, то строковый тип данных в C как таковой отсутствует, а в качестве строк в С используются обычные массивы символов.

Исторически сложилось два представления формата строк:

1. формат ANSI;
2. cтроки с завершающим нулем (используется в C).

Формат ANSI устанавливает, что значением первой позиции в строке является ее длина, а затем следуют сами символы строки. Например, представление строки «Моя строка!» будет следующим:

11 ‘М’ ‘о’ ‘я’ ‘ ‘ ‘с’ ‘т’ ‘р’ ‘о’ ‘к’ ‘а’ ‘!’
В строках с завершающим нулем, значащие символы строки указываются с первой позиции, а признаком завершения строки является значение ноль. Представление рассмотренной ранее строки в этом формате имеет вид:

‘М’ ‘о’ ‘я’ ‘ ‘ ‘с’ ‘т’ ‘р’ ‘о’ ‘к’ ‘а’ ‘!’ 0

Объявление строк в C

Строки реализуются посредством массивов символов. Поэтому объявление ASCII строки имеет следующий синтаксис:

char имя[длина];
Объявление строки в С имеет тот же синтаксис, что и объявление одномерного символьного массива. Длина строки должна представлять собой целочисленное значение (в стандарте C89 – константа, в стандарте C99 может быть выражением). Длина строки указывается с учетом одного символа на хранение завершающего нуля, поэтому максимальное количество значащих символов в строке на единицу меньше ее длины. Например, строка может содержать максимально двадцать символов, если объявлена следующим образом:
char str[21]; Инициализация строки в С осуществляется при ее объявлении, используя следующий синтаксис:
char str[длина] = строковый литерал;

Строковый литерал – строка ASCII символов заключенных в двойные кавычки. Примеры объявления строк с инициализацией:

char str1[20] = «Введите значение: «, str2[20] = «»;

const char message[] = «Сообщение об ошибке!»;

Работа со строками в С

Так как строки на языке С являются массивами символов, то к любому символу строки можно обратиться по его индексу. Для этого используется синтаксис обращения к элементу массива, поэтому первый символ в строке имеет индекс ноль. Например, в следующем фрагменте программы в строке str осуществляется замена всех символов ‘a’ на символы ‘A’ и наоборот.

Массивы строк в С

Объявление массивов строк в языке С также возможно. Для этого используются двумерные массивы символов, что имеет следующий синтаксис:
char имя[количество][длина];

Первым размером матрицы указывается количество строк в массиве, а вторым – максимальная (с учетом завершающего нуля) длина каждой строки. Например, объявление массива из пяти строк максимальной длиной 30 значащих символов будет иметь вид:

При объявлении массивов строк можно производить инициализацию:
char имя[количество][длина] = <строковый литерал №1, . строковый литерал №N>;

Число строковых литералов должно быть меньше или равно количеству строк в массиве. Если число строковых литералов меньше размера массива, то все остальные элементы инициализируются пустыми строками. Длина каждого строкового литерала должна быть строго меньше значения длины строки (для записи завершающего нуля).

При объявлении массивов строк с инициализацией допускается не указывать количество строк в квадратных скобках. В таком случае, количество строк в массиве будет определено автоматически по числу инициализирующих строковых литералов.
Например, массив из семи строк:

Функции для работы со строками в С

Все библиотечные функции, предназначенные для работы со строками, можно разделить на три группы:

1. ввод и вывод строк;
2. преобразование строк;
3. обработка строк.

Ввод и вывод строк в С

Для ввода и вывода строковой информации можно использовать функции форматированного ввода и вывода (printf и scanf). Для этого в строке формата при вводе или выводе строковой переменной необходимо указать спецификатор типа %s. Например, ввод и последующий вывод строковой переменной будет иметь вид:

char str[31] = «»;
printf(«Введите строку: «);
scanf(«%30s”,str);
printf(«Вы ввели: %s”,str);

Недостатком функции scanf при вводе строковых данных является то, что символами разделителями данной функции являются:

Поэтому, используя данную функцию невозможно ввести строку, содержащую несколько слов, разделенных пробелами или табуляциями. Например, если в предыдущей программе пользователь введет строку: «Сообщение из нескольких слов», то на экране будет выведено только «Сообщение».
Для ввода и вывода строк в библиотеке stdio.h содержатся специализированные функции gets и puts.

Функция gets предназначена для ввода строк и имеет следующий заголовок:
char * gets(char *buffer);

Между тем использовать функцию gets категорически не рекомендуется, ввиду того, что она не контролирует выход за границу строки, что может произвести к ошибкам. Вместо нее используется функция fgets с тремя параметрами:

char * fgets(char * buffer, int size, FILE * stream);

где buffer — строка для записи результата, size — максимальное количество байт, которое запишет функция fgets, stream — файловый объект для чтения данных, для чтения с клавиатуры нужно указать stdin. Эта функция читает символы со стандартного ввода, пока не считает n — 1 символ или символ конца строки, потом запишет считанные символы в строку и добавит нулевой символ. При этом функция fgets записывает в том символ конца строки в данную строку, что нужно учитывать.

Функция puts предназначена для вывода строк и имеет следующий заголовок:
int puts(const char *string);

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

Для считывания одного символа можно использовать функцию fgetc(FILE * stream) . Она считывает один символ и возвращает значение этого символа, преобразованное к типу int, если же считывание не удалось, то возвращается специальная константа EOF, равная -1. Функция возвращает значение -1 для того, чтобы можно было обрабатывать ситуацию конца файла, посимвольное чтение до конца файла можно реализовать следующим образом:

int c;
while ((c = fgetc(stdin)) != EOF) <
// Обработка символа
>

Для вывода одного символа можно использовать функцию int fputc(int c, FILE *stream); .

Помимо функций ввода и вывода в потоки в библиотеке stdio.h присутствуют функции форматированного ввода и вывода в строки. Функция форматированного ввода из строки имеет следующий заголовок:

int sscanf(const char * restrict buffer, const char * restrict string, [address] . );

Функции форматированного вывода в строку имеют следующие заголовки:

Преобразование строк

В С для преобразования строк, содержащих числа, в численные значения в библиотеке stdlib.h
предусмотрен следующий набор функций:
double atof(const char *string); // преобразование строки в число типа double
int atoi(const char *string); // преобразование строки в число типа int
long int atol(const char *string); // преобразование строки в число типа long int
long long int atoll(const char *string); // преобразование строки в число типа long long int

Корректное представление вещественного числа в текстовой строке должно удовлетворять формату:

После символов E, e указывается порядок числа. Корректное представление целого числа в текстовой строке должно удовлетворять формату:

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

Аналогичные функции присутствуют и для преобразования строк в целочисленные значения:

Функции обратного преобразования (численные значения в строки) в библиотеке stdlib.h присутствуют, но они не регламентированы стандартом, и рассматриваться не будут. Для преобразования численных значений в строковые наиболее удобно использовать функции sprintf и snprintf.

Обработка строк

В библиотеке string.h содержаться функции для различных действий над строками.
Функция вычисления длины строки:
size_t strlen(const char *string);

Функции копирования строк:

Функции сравнения строк:

Функции осуществляют сравнение строк по алфавиту и возвращают:

положительное значение – если string1 больше string2;
отрицательное значение – если string1 меньше string2;
нулевое значение – если string1 совпадает с string2;

Функции объединения (конкатенации) строк:

Функции поиска символа в строке:

Функция поиска строки в строке:
char * strstr(const char *str, const char *substr);

Функция поиска первого символа в строке из заданного набора символов:
size_t strcspn(const char *str, const char *charset);

Функции поиска первого символа в строке не принадлежащему заданному набору символов:
size_t strspn(const char *str, const char *charset);

Функции поиска первого символа в строке из заданного набора символов:
char * strpbrk(const char *str, const char *charset);

Функция поиска следующего литерала в строке:
char * strtok(char * restrict string, const char * restrict charset);

Источник

Способы представления текстовых строк

Строки обладают следующими важными свойствами:

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

Обычно под строками подразумевают текстовые строки, то есть строки, состоящие из символов, входящих в алфавит какого-либо выбранного языка, цифр, знаков препинания и других служебных символов. Действительно, текстовая строка является наиболее универсальной формой представления любой информации. Однако, следует иметь в виду, что символы, входящие в строку могут принадлежать любому алфавиту. Например, битовые строки, составляются из 1-битовых символов, принадлежащих алфавиту: <0, 1>. Все строковые операции с равным успехом применимы как к символьным, так и к битовым строкам.

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

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

В зависимости от ориентации языка программирования средства работы со строками занимают в языке более или менее значительное место.

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

Базовыми операциями над строками являются:

• определение длины строки;
• присваивание строк;
• конкатенация (сцепление) строк;
• выделение подстроки;
• поиск вхождения.

Операция определения длины строки имеет вид функции, возвращаемое значение которой (целое число) — это текущее число символов в строке. Операция присваивания имеет тот же смысл, что и для других типов данных.

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

Результатом операции сцепления двух строк является строка, длина которой равна суммарной длине строк-операндов, а значение соответствует значению первого операнда, за которым непосредственно следует значение второго операнда. Операция сцепления дает результат, длина которого в общем случае больше длин операндов. Как и во всех операциях над строками, которые могут увеличивать длину строки (присваивание, сцепление, сложные операции), возможен случай, когда длина результата окажется большей, чем отведенный для него объем памяти. Естественно, эта проблема возникает только в тех языках, где длина строки ограничивается. Возможны три варианта решения этой проблемы, определяемые правилами языка или режимами компиляции:

• никак не контролировать такое превышение, возникновение такой ситуации неминуемо приводит к труднолокализуемой ошибке при выполнении программы;
• завершать программу аварийно с локализацией и диагностикой ошибки;
• ограничивать длину результата в соответствии с объемом отведенной памяти.

Операция выделения подстроки выделяет из исходной строки последовательность символов, начиная с заданной позиции n, с заданной длиной l.

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

• аварийное завершение программы с диагностикой ошибки;
• формирование результата меньшей длины, чем задано, возможно, даже пустой строки.

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

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

• выделение из исходной строки подстроки, начиная с позиции 1, длиной n₁ — 1;
• выделение из исходной строки подстроки, начиная с позиции n₂ + 1, длиной, равной длине исходной строки минус n₂;
• сцепление подстрок, полученных на предыдущих шагах.

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

Представление строк в памяти зависит от того, насколько изменчивыми являются строки в каждой конкретной задаче, и средства такого представления варьируются от абсолютно статического до динамического. Универсальные языки программирования в основном обеспечивают работу со строками переменной длины, но максимальная длина строки должна быть указана при ее создании. Если программиста не устраивают возможности или эффективность тех средств работы со строками, которые предоставляет ему язык программирования, то он может либо определить свой тип данных «строка» и использовать для его представления средства динамической работы с памятью, либо сменить язык программирования на специально ориентированный на обработку текста, в которых представление строк базируется на динамическом управлении памятью.

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

Самым простым способом является представление строки в виде вектора постоянной длины. При этом в памяти отводится фиксированное количество байт, в которые записываются символы строки. Если строка меньше отводимого под нее вектора, то лишние места заполняются пробелами, а если строка выходит за пределы вектора, то лишние (обычно справа строки) символы должны быть отброшены.

Этот и все последующие за ним методы учитывают переменную длину строк. Признак конца строки — это особый символ, принадлежащий алфавиту (таким образом, полезный алфавит оказывается меньше на один символ), и занимает то же количество разрядов, что и все остальные символы. Издержки памяти при этом способе составляют 1 символ на строку.

Счетчик символов — это целое число, и для него отводится достаточное количество битов, чтобы их с избытком хватало для представления длины самой длинной строки,какую только можно представить в данной машине. Обычно для счетчика отводят от 8 до 16 битов. Тогда при таком представлении издержки памяти в расчете на одну строку составляют 1-2 символа. При использовании счетчика символов возможен произвольный доступ к символам в пределах строки, поскольку можно легко проверить, что обращение не выходит за пределы строки. Счетчик размещается в таком месте, где он может быть легко доступен — начале строки или в дескрипторе строки. Максимально возможная длина строки, таким образом, ограничена разрядностью счетчика. В Паскале, например, строка представляется в виде массива символов, индексация в котором начинается с 0, а однобайтный счетчик числа символов в строке является нулевым элементом этого массива. И счетчик символов, и признак конца могут быть доступны для программиста как элементы вектора.

В двух предыдущих вариантах обеспечивалось максимально эффективное расходование памяти (1-2 «лишних» символа на строку), но изменчивость строки обеспечивалась крайне неэффективно. Поскольку вектор — статическая структура, каждое изменение длины строки требует создания нового вектора, пересылки в него неизменяемой части строки и уничтожения старого вектора. Это сводит на нет все преимущества работы со статической памятью. Поэтому наиболее популярным способом представления строк в памяти являются векторы с управляемой длиной.

Память под вектор с управляемой длиной отводится при создании строки. Ее размер и размещение остаются неизменными все время существования строки. В дескрипторе такого вектора-строки может отсутствовать начальный индекс, так как он может быть зафиксирован раз и навсегда установленными соглашениями, но появляется поле текущей длины строки. Размер строки, таким образом, может изменяться от 0 до значения максимального индекса вектора. «Лишняя» часть отводимой памяти может быть заполнена любыми кодами — она не принимается во внимание при оперировании со строкой. Поле конечного индекса может быть использовано для контроля превышения длиной строки объема отведенной памяти.

Хотя такое представление строк не обеспечивает экономии памяти, проектировщики систем программирования, возможно, считают это приемлемой платой за возможность работать с изменчивыми строками в статической памяти.

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

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

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

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

Такой метод спискового представления строк особенно удобен в задачах редактирования текста, когда большая часть операций приходится на изменение, вставку и удаление целых слов. Поэтому в этих задачах целесообразно список организовать так, чтобы каждый его элемент содержал одно слово текста. Символы пробела между словами в памяти могут не представляться.

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

Источник