что такое строка в информатике

Строка (программирование)

Смотреть что такое «Строка (программирование)» в других словарях:

Класс (программирование) — У этого термина существуют и другие значения, см. Класс. Класс в программировании набор методов и функций. Другие абстрактные типы данных метаклассы, интерфейсы, структуры, перечисления характеризуются какими то своими, другими… … Википедия

Автоматное программирование — Автоматное программирование это парадигма программирования, при использовании которой программа или её фрагмент осмысливается как модель какого либо формального автомата. В зависимости от конкретной задачи в автоматном программировании… … Википедия

SSI (программирование) — У этого термина существуют и другие значения, см. SSI. SSI (Server Side Includes включения на стороне сервера) несложный язык для динамической «сборки» веб страниц на сервере из отдельных составных частей и выдачи клиенту полученного HTML… … Википедия

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

линейное программирование — — [http://www.iks media.ru/glossary/index.html?glossid=2400324] линейное программирование Область математического программирования, посвященная теории и методам решения экстремальных задач, характеризующихся линейной зависимостью между… … Справочник технического переводчика

Обобщённое программирование — (англ. generic programming) парадигма программирования, заключающаяся в таком описании данных и алгоритмов, которое можно применять к различным типам данных, не меняя само это описание. В том или ином виде поддерживается разными… … Википедия

Линейное программирование — [linear programming] область математического программирования, посвященная теории и методам решения экстремальных задач, характеризующихся линейной зависимостью между переменными. В самом общем виде задачу Л.п. можно записать так. Даны… … Экономико-математический словарь

Линейное программирование — [linear programming] область математического программирования, посвященная теории и методам решения экстремальных задач, характеризующихся линейной зависимостью между переменными. В самом общем виде задачу Л.п. можно записать так. Даны… … Экономико-математический словарь

Обобщенное программирование — Обобщённое программирование парадигма программирования, заключающаяся в таком описании данных и алгоритмов, которое можно применять к различным типам данных, не меняя само это описание. В том или ином виде поддерживается разными языками… … Википедия

Объектно-ориентированное программирование на Python — Объектно ориентированное программирование на Python программирование на Python с использованием парадигмы ООП: с самого начала Python проектировался как объектно ориентированный язык программирования[1]. Содержание 1 Введение 1.1 … Википедия

Источник

Строковый тип

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

Содержание

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

Некоторые языки программирования накладывают ограничения на максимальную длину строки, но в большинстве языков подобные ограничения отсутствуют. При использовании Unicode каждый символ строкового типа может требовать двух или даже четырёх байтов для своего представления.

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

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

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

В этом подходе строки представляются массивом символов; при этом размер массива хранится в отдельной (служебной) области. От названия языка Pascal, где этот метод был впервые реализован, данный метод получил название Pascal strings.

Слегка оптимизированным вариантом этого метода является т. н. формат c-addr u (от англ. character-aligned address + unsigned number ), применяемый в Форте. В отличие от Pascal strings, здесь размер массива хранится не совместно со строковыми данными, а является частью указателя на строку.

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

Недостатки

Метод «завершающего байта»

Второй метод заключается в использовании «завершающего байта». Одно из возможных значений символов алфавита (как правило, это символ с кодом 0) выбирается в качестве признака конца строки, и строка хранится как последовательность байтов от начала до конца. Есть системы, в которых в качестве признака конца строки используется не символ 0, а байт 0xFF (255) или код символа «$».

Метод имеет три названия — ASCIIZ (символы в кодировке ASCII с нулевым завершающим байтом), C-strings (наибольшее распространение метод получил именно в языке Си) и метод нуль-терминированных строк.

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

Недостатки

Использование обоих методов

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

Реализация в языках программирования

Операции

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

До последнего времени один символ всегда кодировался одним байтом (8 двоичных битов; применялись также кодировки с 7 битами на символ), что позволяло представлять 256 (128 при семибитной кодировке) возможных значений. Однако для полноценного представления символов алфавитов нескольких языков (многоязыковых документов, типографских символов — несколько видов кавычек, тире, нескольких видов пробелов и для написания текстов на иероглифических языках — китайском, японском и корейском) 256 символов недостаточно. Для решения этой проблемы существует несколько методов:

Источник

Что такое строка в информатике

Любой язык программирования содержит средства представления и обработки текстовой информации. Другое дело, что обычно программист наряду с символами имеет дело с типом данных (формой представления) – строкой, причем особенности ее организации скрыты, а для работы предоставлен стандартный набор функций. В Си, наоборот, форма представления строки является открытой, а программист работает с ней «на низком уровне».

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

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

· работа с текстовыми файлами «вписана» в стандартный ввод-вывод. Например, в Си потоки ввода-вывода могут быть перенаправлены как на текстовый файл, так и на консольный ввод-вывод (клавиатура – экран);

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

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

Константа Название Действие

\ a bel Звуковой сигнал

\b bs Курсор на одну позицию назад

\f ff Переход к началу (перевод формата)

\n lf Переход на одну строку вниз(перевод строки)

\r cr Возврат на первую позицию строки

\ t ht Переход к позиции, кратной 8 (табуляция)

\v vt Вертикальная табуляция по строкам

\nn Символ с восьмеричным кодом nn

\xnn Символ с шестнадцатеричным кодом nn

\0 Символ с кодом 0

Некоторые программы и стандартные функции обработки символов и строк (isdigit,isalpha) используют тот факт, что цифры, прописные и строчные (маленькие и большие) латинские буквы имеют упорядоченные по возрастанию значения кодов:

· строка хранится в массиве символов, массив символов может быть инициализирован строкой, а может быть заполнен программно:

· соответствие размерности массива и длины строки транслятором не контролируется, за это несет ответственность программа (программист, ее написавший):

char C[20], B []=”Строка слишком длинная для C ”;

// следить за переполнением массива

// и ограничить строку его размерностью

char A[80] = «123456\r\n»;

char B[] = «aaaaa\033bbbb»;

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

Стандартные приемы обработки строк

· редактировать строку «на месте», реализуя вставку и удаление символов или фрагментов;

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

Получить символ десятичной цифры из значения целой переменной, лежащей в диапазоне 0..9:

int n; char c; c = n + ‘0’;

Получить символ шестнадцатеричной цифры из значения целой переменной, лежащей в диапазоне 0..15:

Получить значение целой переменной из символа десятичной цифры:

Получить значение целой переменной из шестнадцатеричной цифры:

Преобразовать маленькую латинскую букву в большую:

//— Подсчет количества слов

//— Удаление лишних пробелов при посимвольном переписывании

void nospace(char c1[],char c2[]) <

c 2[ j ++]=’ ‘; // добавить пробел

c 2[ j ++]= c 1[ i ]; // Перенести символ слова

//—- Сравнение строк по значениям кодов

int my_strcmp(unsigned char s1[],unsigned char s2[]) <

if (s1[n] == s2[n]) return 0;

//—- Сравнение строк с заданными «весами» символов

static char ORD[] = » АаБбВвГгДдЕе 1234567890″;

for ( int n=0; ORD[n]!=’\0′; n++)

int my_strcmp(char s1[],char s2[])<

if (c1 == c2) return 0;

Пример: a < b < c >b > a < d < e < g >e > d > a => < c >< b 1 b >< g >< e 3 e > < d 4 d >a 2 a 5 a

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

int i; // Индекс в строке

int k ; // Счетчик вложенности

int max ; // Максимум вложенности

int b; // Индекс максимальной » <"

for (i=0, max=0, b=-1; c[i]!=0; i++)<

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

int i; // Индекс в строке

int b; // Индекс максимальной » <"

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

//—— Копирование вложенных фрагментов с » выкусыванием»

void copy(char c1[], char c2[])<

int i =0; // Индекс в выходной строке

int k ; // Индекс найденного фрагмента

int n ; // Запоминание начала фрагмента

int m ; // Счетчик фрагментов

for ( n = k ; c 1[ k ]!= ‘>’ ; k ++, i ++) c 2[ i ]= c 1[ k ]; // Переписать фрагмент и его «>»

if ( m /10!=0) c 1[ n ++] = m /10 + ‘0’ ; // На его место две цифры

c 1[ n ++] = m %10 + ‘0’ ; // номера во внешней форме

c 1[ n ]=0; > // сдвинуть » хвост» к началу

for ( k =0; c 1[ k ]!=0; k ++, i ++) c 2[ i ]= c 1[ k ]; // перенести остаток

c 2[ i ]=0;> // входной строки

Практический совет – желательно избегать сложные вычисления над индексами. Лучше всего для каждого фрагмента строки заводить свой индекс и перемещать их независимо друг от друга в нужные моменты. Что, например, сделано при «уплотнении» строки – индекс k после переписывания найденного фрагмента «останавливается» на начале «хвоста» строки, который переносится под индекс n – начало удаляемого фрагмента. Причем записываемые цифры номера смещают это начало на один или два символа. Таким образом, фрагмент заменяется во входной строке на его номер.

Внешняя и внутренняя форма представления чисел

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

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

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

На самом деле алгоритмы ввода-вывода числовых данных (вернее, преобразования данных из внешней формы во внутреннюю, и наоборот) идентичны алгоритмам преобразования чисел из произвольной системы счисления в десятичную (см. 1.3). При этом десятичная система играет роль внутренней («родной») формы представления.

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

Значение: 123 1234 = 123 * 10 + 4

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

//—— Ввод десятичного целого числа

int StringToInt(char c[])<

if (c[i]==’\0′) return 0; // Поиск первой цифры

for (n=0; c[i]>=’0′ && c[i] // Накопление целого

//—- Вывод целого десятичного числа

void IntToString(char c[], int n)

for (nn=n, k=0; nn!=0; k++, nn/=10); // Подсчет количества цифр числа

c[k] = ‘\0’; // Конец строки

for (k—; k >=0; k—, n /= 10) // Получение цифр числа

c[k] = n % 10 + ‘0’; // в обратном порядке

При преобразовании дробной части во внешнюю форму используется тот факт, что при умножении дробной части на 10 (точнее, на основание системы счисления) очередная цифра «вылезает» в целую часть. Из нее формируется символ, после чего целая часть отбрасывается.

//—- Вывод вещественного десятичного числа

void FloatToString(char c[], double v)

for (nn=v, k=0; nn!=0; k++, nn/=10); // Подсчет количества цифр

kk=k-1; c[k++] = ‘.’; // целой части числа

for (nn=v; kk >=0; kk—, nn /= 10) // Получение цифр числа

c[kk] = nn % 10 + ‘0’; // в обратном порядке

v-=(int)v; // Убрать целую часть

Фрагменты вывода целой и дробной частей «сшиваются» путем запоминания местонахождения в строке символа «точка», разделяющего целую и дробную части.

//—— Ввод десятичного вещественного числа

double StringToFloat(char c[])<

if (c[i]==’\0′) return 0; // Поиск первой цифры

for (n=0; c[i]>=’0′ && c[i] // Накопление целого

v=v/10; // весом разряда дробной части

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

Посимвольная и пословная обработка.

Одну и ту же программу обработки строки текста можно написать разными способами. Если речь идет о формате текстовой строки, то отслеживать его можно двумя способами (см. 3.8):

// Функция возвращает индекс начала слова или 1, если нет слов

// Логика переменной состояния – n – счетчик символов слова

if (s[i]!=’ ‘) n++; // символ слова увеличить счетчик

n=0; // фиксация максимального значения

>> // то же самое для последнего слова

// Структурная логика – 3 цикла: просмотр слов, пробелов и символов

while (in[i]==’ ‘) i++; // Пропуск пробелов перед словом

for (k=0;in[i]!=’ ‘ && in[i]!=0; i++,k++); // Подсчет длины слова

m=k; b=i-k; > // Одновременно запоминается

По завершении посимвольного просмотра строки последнее слово (если после него нет пробела) оказывается необработанным. Поэтому контекст фиксации максимума повторяется после выхода из цикла.

Здесь можно проиллюстрировать еще один принцип разработки программ: после ее написания для произвольной «усредненной» ситуации необходимо проверить ее «на крайности». В данном случае, при отсутствии в строке слов (строка состоит из пробелов или пуста), установленное начальное значение b =-1 будет возвращено в качестве результата (что и задумывалось при установке значения –1 как недопустимого).

Лабораторный практикум

1. В строке найти последовательности цифр, каждую из них считать числом в той системе счисления, которая соответствует максимальной цифре, заменить числа в строке символами с кодами, полученными из этих чисел. Пример: aaa 010101 bbb 343 ccc – двоичная и пятиричная системы счисления.

2. В строке найти последовательности цифр, каждую из них считать числом в той системе счисления, которая соответствует первой цифре, заменить числа в строке символами с кодами, полученными из этих чисел. Пример: aaa 2010101 bbb 8343 ccc – двоичная и восьмиричная системы счисления.

6. Найти в строке два одинаковых фрагмента (не включающих в себя пробелы) длиной более 5 символов, скопировать их в выходную строку и удалить. Повторять этот процесс, пока такие фрагменты находятся. Остаток строки добавить в выходную.

7. Найти во входной строке самую внутреннюю пару скобок <. >и переписать в выходную строку содержащиеся между ними символы. Во входной строке фрагмент удаляется. Повторять этот процесс, пока во входной строке не останется скобок, остаток также переписать в выходную строку.

10. Определить, является ли строка палиандромом (например, «я у ребят беру наган») – удалить пробелы, найти фрагменты – палиандромы максимальной длины и удалить.

Вопросы без ответов

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

Источник

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

СОДЕРЖАНИЕ

Строковые типы данных

Длина строки

Кодировка символов

Юникод несколько упростил картину. Большинство языков программирования теперь имеют тип данных для строк Unicode. Предпочтительный формат байтового потока Unicode UTF-8 разработан, чтобы не иметь проблем, описанных выше для более старых многобайтовых кодировок. UTF-8, UTF-16 и UTF-32 требуют, чтобы программист знал, что единицы кода фиксированного размера отличаются от «символов», основная трудность в настоящее время заключается в неверно разработанных API-интерфейсах, которые пытаются скрыть эту разницу (UTF-32 действительно сделать кодовые точки фиксированного размера, но они не являются «символами» из-за составления кодов).

Реализации

Представления

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

Большинство строковых реализаций очень похожи на массивы переменной длины с записями, хранящими символьные коды соответствующих символов. Принципиальное отличие состоит в том, что при определенных кодировках один логический символ может занимать более одной записи в массиве. Это происходит, например, с UTF-8, где отдельные коды ( кодовые точки UCS ) могут занимать от одного до четырех байтов, а отдельные символы могут принимать произвольное количество кодов. В этих случаях логическая длина строки (количество символов) отличается от физической длины массива (количества используемых байтов). UTF-32 позволяет избежать первой части проблемы.

С нулевым завершением

Длина строки «» в приведенном выше примере FRANK составляет 5 символов, но занимает 6 байтов. Знаки после терминатора не являются частью изображения; они могут быть частью других данных или просто мусором. (Строки этой формы иногда называют строками ASCIZ после исходной директивы языка ассемблера, используемой для их объявления.)

Байтовые и битовые оканчивающиеся

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

Раннее программное обеспечение для микрокомпьютеров основывалось на том факте, что коды ASCII не используют бит старшего разряда, и устанавливали его для обозначения конца строки. Перед выводом он должен быть сброшен на 0.

С префиксом длины

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

Вот строка Паскаля, хранящаяся в 10-байтовом буфере, вместе с ее представлением ASCII / UTF-8:

Строки как записи

Многие языки, включая объектно-ориентированные, реализуют строки как записи с внутренней структурой, например:

Другие представления

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

Оба эти ограничения можно преодолеть с помощью грамотного программирования.

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

Проблемы безопасности

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

Буквальные строки

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

Два общих представления:

Нетекстовые строки

Алгоритмы обработки строк

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

Некоторые категории алгоритмов включают:

Название стрингология было придумано в 1984 году компьютерным ученым Цви Галилом для проблемы алгоритмов и структур данных, используемых для обработки строк.

Языки и утилиты, ориентированные на символьные строки

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

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

Функции символьных строк

Формальная теория

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

Префиксы и суффиксы

Разворот

Вращения

Лексикографический порядок

Топология

Источник