что такое строка в информатике в
Строковый тип
В программировании, строковый тип (англ. 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 символов недостаточно. Для решения этой проблемы существует несколько методов:
Строка (программирование)
Смотреть что такое «Строка (программирование)» в других словарях:
Класс (программирование) — У этого термина существуют и другие значения, см. Класс. Класс в программировании набор методов и функций. Другие абстрактные типы данных метаклассы, интерфейсы, структуры, перечисления характеризуются какими то своими, другими… … Википедия
Автоматное программирование — Автоматное программирование это парадигма программирования, при использовании которой программа или её фрагмент осмысливается как модель какого либо формального автомата. В зависимости от конкретной задачи в автоматном программировании… … Википедия
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 … Википедия
В зависимости от языка программирования и используемого точного типа данных переменная, объявленная как строка, может либо вызывать статическое выделение памяти в памяти на заранее определенную максимальную длину, либо использовать динамическое выделение, позволяющее хранить переменное количество элементов.
СОДЕРЖАНИЕ
Строковые типы данных
Длина строки
Кодировка символов
Юникод несколько упростил картину. Большинство языков программирования теперь имеют тип данных для строк Unicode. Предпочтительный формат байтового потока Unicode UTF-8 разработан, чтобы не иметь проблем, описанных выше для более старых многобайтовых кодировок. UTF-8, UTF-16 и UTF-32 требуют, чтобы программист знал, что единицы кода фиксированного размера отличаются от «символов», основная трудность в настоящее время заключается в неверно разработанных API-интерфейсах, которые пытаются скрыть эту разницу (UTF-32 действительно сделать кодовые точки фиксированного размера, но они не являются «символами» из-за составления кодов).
Реализации
Представления
Термин « байтовая строка» обычно указывает на строку байтов общего назначения, а не на строки только (читаемых) символов, строки битов и т. Д. Строки байтов часто подразумевают, что байты могут принимать любое значение, и любые данные могут храниться как есть, что означает, что не должно быть никакого значения, интерпретируемого как значение завершения.
Большинство строковых реализаций очень похожи на массивы переменной длины с записями, хранящими символьные коды соответствующих символов. Принципиальное отличие состоит в том, что при определенных кодировках один логический символ может занимать более одной записи в массиве. Это происходит, например, с UTF-8, где отдельные коды ( кодовые точки UCS ) могут занимать от одного до четырех байтов, а отдельные символы могут принимать произвольное количество кодов. В этих случаях логическая длина строки (количество символов) отличается от физической длины массива (количества используемых байтов). UTF-32 позволяет избежать первой части проблемы.
С нулевым завершением
| F | R | A | N | K | NUL | k | e | f | w |
| 46 16 | 52 16 | 41 16 | 4Э 16 | 4Б 16 | 00 16 | 6Б 16 | 65 16 | 66 16 | 77 16 |
Длина строки «» в приведенном выше примере FRANK составляет 5 символов, но занимает 6 байтов. Знаки после терминатора не являются частью изображения; они могут быть частью других данных или просто мусором. (Строки этой формы иногда называют строками ASCIZ после исходной директивы языка ассемблера, используемой для их объявления.)
Байт- и битовое завершение
В чем-то похожем, машины для «обработки данных», такие как IBM 1401, использовали специальный бит словарной метки для разграничения строк слева, где операция начиналась бы справа. Этот бит должен быть очищен во всех остальных частях строки. Это означало, что, хотя в IBM 1401 было семибитное слово, почти никто никогда не думал использовать его как функцию и отменять назначение седьмого бита (например) для обработки кодов ASCII.
Раннее программное обеспечение для микрокомпьютеров основывалось на том факте, что коды ASCII не используют бит старшего разряда, и устанавливали его для обозначения конца строки. Перед выводом он должен быть сброшен на 0.
С префиксом длины
В последнем случае само поле префикса длины не имеет фиксированной длины, поэтому фактические строковые данные необходимо перемещать, когда строка растет, так что поле длины необходимо увеличивать.
Вот строка Паскаля, хранящаяся в 10-байтовом буфере, вместе с ее представлением ASCII / UTF-8:
| длина | F | R | A | N | K | k | e | f | w |
| 05 16 | 46 16 | 52 16 | 41 16 | 4Э 16 | 4Б 16 | 6Б 16 | 65 16 | 66 16 | 77 16 |
Строки как записи
Многие языки, в том числе объектно-ориентированные, реализуют строки как записи с внутренней структурой, например:
Другие представления
И завершение символа, и коды длины ограничивают строки: например, символьные массивы C, содержащие нулевые (NUL) символы, не могут обрабатываться напрямую функциями библиотеки строк C : строки, использующие код длины, ограничены максимальным значением кода длины.
Оба эти ограничения можно преодолеть с помощью грамотного программирования.
Хотя эти представления обычны, возможны и другие. Использование веревок делает некоторые строковые операции, такие как вставки, удаления и конкатенации, более эффективными.
Проблемы безопасности
Различная структура памяти и требования к хранению строк могут повлиять на безопасность программы, осуществляющей доступ к строковым данным. Строковые представления, требующие завершающего символа, обычно подвержены проблемам переполнения буфера, если завершающий символ отсутствует, что вызвано ошибкой кодирования или злоумышленником, намеренно изменяющим данные. Строковые представления, использующие отдельное поле длины, также восприимчивы, если длиной можно манипулировать. В таких случаях программный код, обращающийся к строковым данным, требует проверки границ, чтобы гарантировать, что он случайно не получит доступ или не изменит данные за пределами строковой памяти.
Буквальные строки
Иногда строки необходимо встраивать в текстовый файл, который удобен для чтения и предназначен для использования машиной. Это необходимо, например, в исходном коде языков программирования или в файлах конфигурации. В этом случае символ NUL не работает как терминатор, поскольку обычно он невидим (не печатается) и его трудно вводить с клавиатуры. Сохранение длины строки также будет неудобным, поскольку ручное вычисление и отслеживание длины утомительно и подвержено ошибкам.
Два распространенных представления:
Нетекстовые строки
Алгоритмы обработки строк
Существует множество алгоритмов обработки строк, каждый из которых имеет различные компромиссы. Конкурирующие алгоритмы можно анализировать с точки зрения времени выполнения, требований к хранилищу и т. Д.
Некоторые категории алгоритмов включают:
Название стрингология было придумано в 1984 году компьютерным ученым Цви Галилом для проблемы алгоритмов и структур данных, используемых для обработки строк.
Языки и утилиты, ориентированные на символьные строки
Символьные строки являются настолько полезным типом данных, что было разработано несколько языков, чтобы упростить написание приложений для обработки строк. Примеры включают следующие языки:
Многие утилиты Unix выполняют простые операции со строками и могут использоваться для простого программирования некоторых мощных алгоритмов обработки строк. Файлы и конечные потоки можно рассматривать как строки.
Функции символьных строк
Формальная теория
Конкатенация и подстроки
Префиксы и суффиксы
Разворот
Вращения
Лексикографический порядок
Топология
§ 28. Строки символов
Рассмотрим еще один структурный тип данных — строковый тип. Строковый тип данных был введен в Турбо Паскале. Он позволяет программировать обработку слов, предложений, текстов.
Строка — это последовательность символов. Каждый символ занимает 1 байт памяти (код ASCII). Количество символов в строке называется ее длиной. Длина строки может находиться в диапазоне от 0 до 255. Строковые величины могут быть константами и переменными.
Строковая константа записывается как последовательность символов, заключенная в апострофы. Например:
‘ Язык программирования ПАСКАЛЬ’
Строковая переменная описывается в разделе описания переменных следующим образом:
Параметр длины может и не указываться в описании. В таком случае подразумевается, что он равен максимальной величине — 255. Например:
Строковая переменная занимает в памяти на 1 байт больше, чем указанная в описании длина. Дело в том, что один (нулевой) байт содержит значение текущей длины строки. Если строковой переменной не присвоено никакого значения, то ее текущая длина равна нулю. По мере заполнения строки символами ее текущая длина возрастает, но она не должна превышать максимальной по описанию величины.
Символы внутри строки индексируются (нумеруются), начиная с единицы. Каждый отдельный символ идентифицируется именем строки с индексом, заключенным в квадратные скобки. Например:
Значение индекса может быть задано положительной константой, переменной, выражением целочисленного типа. Оно не должно выходить за границы описания.
Тип String и стандартный тип Char совместимы: строки и символы могут употребляться в одних и тех же выражениях.
Строковые выражения строятся из строковых констант, переменных, функций и знаков операций. Над строковыми данными допустимы операция сцепления и операции отношения.
Операция сцепления (+) применяется для соединения нескольких строк в одну результирующую строку. Сцеплять можно как строковые константы, так и переменные.
В результате получится строка:
Длина результирующей строки не должна превышать 255.
Если строки имеют различную длину, но в общей части символы совпадают, считается, что более короткая строка меньше, чем более длинная. Строки равны, если они полностью совпадают по длине и содержат одни и те же символы.
Функции и процедуры
Функция Copy(S, Poz, N) выделяет из строки S подстроку длиной N символов, начиная с позиции Роz. N и Роz — целочисленные выражения.
Функция Length (S) определяет текущую длину строки S. Результат — значение целочисленного типа.
Функция Pos(S1, S2) обнаруживает первое появление в строке S2 подстроки S1. Результат — целое число, равное номеру позиции, где находится первый символ подстроки S1. Если в S2 не обнаружена подстрока S1, то результат равен 0.
Процедура Delete (S, Poz, N) удаляет N символов из строки S, начиная с позиции Poz.
В результате выполнения процедуры уменьшается текущая длина строки в переменной S.
Процедура Insert (S1,S2, Poz) выполняет вставку строки S1 в строку S2, начиная с позиции Poz.
Примеры программ обработки строк
Пример 1. Составить программу, формирующую символьную строку, состоящую из N звездочек (N — целое число, 1 ≤ N ≤ 255).
Здесь строковой переменной А вначале присваивается значение пустой строки, обозначаемой двумя апострофами (‘ ‘). Затем к ней присоединяются звездочки.
В этой программе переменная К играет роль счетчика цифр, а переменная I — роль параметра цикла. Цикл закончит выполнение при первом же выходе на символ Т или если в строке такого символа нет, то при выходе на конец строки. Символ S[I] является цифрой, если истинно отношение: ‘0’ ≤ S[I] ≤ 9’.
Строка (информатика)
В зависимости от языка программирования и используемого точного типа данных переменная, объявленная как строка, может либо вызывать статическое выделение памяти в памяти на заранее определенную максимальную длину, либо использовать динамическое выделение, позволяющее хранить переменное количество элементов.
Содержание
Строковые типы данных [ править ]
Длина строки [ править ]
Кодировка символов [ править ]
Юникод несколько упростил картину. В большинстве языков программирования теперь есть тип данных для строк Unicode. Предпочтительный формат байтового потока Unicode UTF-8 разработан, чтобы не иметь проблем, описанных выше для старых многобайтовых кодировок. UTF-8, UTF-16 и UTF-32 требуют, чтобы программист знал, что единицы кода фиксированного размера отличаются от «символов», основная трудность в настоящее время заключается в неправильно разработанных API-интерфейсах, которые пытаются скрыть эту разницу (UTF-32 делает сделать кодовые точки фиксированного размера, но они не являются «символами» из-за составления кодов).
Реализации [ править ]
Представления [ править ]
Термин « байтовая строка» обычно обозначает строку байтов общего назначения, а не строки только (читаемых) символов, строки битов и т. Д. Строки байтов часто подразумевают, что байты могут принимать любое значение и любые данные могут храниться как есть, что означает, что не должно быть никакого значения, интерпретируемого как значение завершения.
Завершено нулем [ править ]
| F | R | A | N | K | NUL | k | e | f | w |
| 46 16 | 52 16 | 41 16 | 4Э 16 | 4Б 16 | 00 16 | 6Б 16 | 65 16 | 66 16 | 77 16 |
Длина строки «» в приведенном выше примере FRANK составляет 5 символов, но занимает 6 байтов. Знаки после терминатора не являются частью изображения; они могут быть частью других данных или просто мусором. (Строки этой формы иногда называют строками ASCIZ после исходной директивы языка ассемблера, используемой для их объявления.)
Завершение байтом и битом [ править ]
В чем-то похожем, машины «обработки данных», такие как IBM 1401, использовали специальный бит словарной метки для разграничения строк слева, где операция начиналась бы справа. Этот бит должен быть очищен во всех остальных частях строки. Это означало, что, хотя в IBM 1401 было семибитное слово, почти никто никогда не думал использовать его в качестве функции и отменять назначение седьмого бита (например) для обработки кодов ASCII.
Раннее программное обеспечение для микрокомпьютеров основывалось на том факте, что коды ASCII не используют старший бит, и устанавливали его для указания конца строки. Перед выводом он должен быть сброшен на 0. [4]
С префиксом длины [ править ]
В последнем случае само поле префикса длины не имеет фиксированной длины, поэтому фактические строковые данные необходимо перемещать, когда строка растет, так что поле длины нужно увеличивать.
Вот строка Паскаля, хранящаяся в 10-байтовом буфере, вместе с ее представлением ASCII / UTF-8:
| длина | F | R | A | N | K | k | e | f | w |
| 05 16 | 46 16 | 52 16 | 41 16 | 4Э 16 | 4Б 16 | 6Б 16 | 65 16 | 66 16 | 77 16 |
Строки как записи [ править ]
Многие языки, в том числе объектно-ориентированные, реализуют строки как записи с внутренней структурой, например:
Другие представления [ править ]
И завершение символа, и коды длины ограничивают строки: например, символьные массивы C, содержащие нулевые (NUL) символы, не могут обрабатываться напрямую функциями библиотеки строк C : строки, использующие код длины, ограничены максимальным значением кода длины.
Оба эти ограничения можно преодолеть с помощью грамотного программирования.
Хотя эти представления распространены, возможны и другие. Использование веревок делает некоторые строковые операции, такие как вставки, удаления и конкатенации, более эффективными.
Проблемы безопасности [ править ]
Различная структура памяти и требования к хранению строк могут повлиять на безопасность программы, обращающейся к строковым данным. Строковые представления, требующие завершающего символа, обычно подвержены проблемам переполнения буфера, если завершающий символ отсутствует, что вызвано ошибкой кодирования или злоумышленником, намеренно изменяющим данные. Строковые представления, использующие отдельное поле длины, также восприимчивы, если длиной можно управлять. В таких случаях программный код, обращающийся к строковым данным, требует проверки границ, чтобы гарантировать, что он случайно не получит доступ или не изменит данные за пределами строковой памяти.
Буквальные строки [ править ]
Иногда строки необходимо встраивать в текстовый файл, который удобен для чтения и предназначен для использования машиной. Это необходимо, например, в исходном коде языков программирования или в файлах конфигурации. В этом случае символ NUL плохо работает в качестве терминатора, поскольку обычно он невидим (не печатается) и его трудно вводить с клавиатуры. Сохранение длины строки также будет неудобным, поскольку ручное вычисление и отслеживание длины утомительно и подвержено ошибкам.
Два общих представления:
Нетекстовые строки [ править ]
Алгоритмы обработки строк [ править ]
Существует множество алгоритмов обработки строк, каждый из которых имеет различные компромиссы. Конкурирующие алгоритмы могут быть проанализированы с точки зрения времени выполнения, требований к хранилищу и так далее.
Некоторые категории алгоритмов включают:
Название стрингология было придумано в 1984 году компьютерным ученым Цви Галилом для проблемы алгоритмов и структур данных, используемых для обработки строк. [9] [ необходим сторонний источник ]
Языки и утилиты, ориентированные на символьные строки [ править ]
Символьные строки являются настолько полезным типом данных, что было разработано несколько языков, чтобы упростить написание приложений для обработки строк. Примеры включают следующие языки:
Многие утилиты Unix выполняют простые операции со строками и могут использоваться для простого программирования некоторых мощных алгоритмов обработки строк. Файлы и конечные потоки можно рассматривать как строки.