Функции обработки строк в Cи
В программе строки могут определяться следующим образом:
- как строковые константы;
- как массивы символов;
- через указатель на символьный тип;
- как массивы строк.
Кроме того, должно быть предусмотрено выделение памяти для хранения строки.
Любая последовательность символов, заключенная в двойные кавычки «» , рассматривается как строковая константа .
Для корректного вывода любая строка должна заканчиваться нуль-символом '\0' , целочисленное значение которого равно 0. При объявлении строковой константы нуль-символ добавляется к ней автоматически. Так, последовательность символов, представляющая собой строковую константу, будет размещена в оперативной памяти компьютера, включая нулевой байт.
Под хранение строки выделяются последовательно идущие ячейки оперативной памяти. Таким образом, строка представляет собой массив символов. Для хранения кода каждого символа строки отводится 1 байт.
Для помещения в строковую константу некоторых служебных символов используются символьные комбинации. Так, если необходимо включить в строку символ двойной кавычки, ему должен предшествовать символ «обратный слеш»: ‘\»‘ .
Строковые константы размещаются в статической памяти. Начальный адрес последовательности символов в двойных кавычках трактуется как адрес строки. Строковые константы часто используются для осуществления диалога с пользователем в таких функциях, как printf() .
При определении массива символов необходимо сообщить компилятору требуемый размер памяти.
Компилятор также может самостоятельно определить размер массива символов, если инициализация массива задана при объявлении строковой константой:
В этом случае имена m2 и m3 являются указателями на первые элементы массивов:
- m2 эквивалентно &m2[0]
- m2[0] эквивалентно ‘Г’
- m2[1] эквивалентно ‘o’
- m3 эквивалентно &m3[0]
- m3[2] эквивалентно ‘x’
При объявлении массива символов и инициализации его строковой константой можно явно указать размер массива, но указанный размер массива должен быть больше, чем размер инициализирующей строковой константы:
Для задания строки можно использовать указатель на символьный тип .
В этом случае объявление массива переменной m4 может быть присвоен адрес массива:
Здесь m3 является константой-указателем. Нельзя изменить m3 , так как это означало бы изменение положения (адреса) массива в памяти, в отличие от m4 .
Для указателя можно использовать операцию увеличения (перемещения на следующий символ):
Массивы символьных строк
Иногда в программах возникает необходимость описание массива символьных строк . В этом случае можно использовать индекс строки для доступа к нескольким разным строкам.
В этом случае poet является массивом, состоящим из четырех указателей на символьные строки. Каждая строка символов представляет собой символьный массив, поэтому имеется четыре указателя на массивы. Указатель poet[0] ссылается на первую строку:
*poet[0] эквивалентно 'П',
*poet[l] эквивалентно '-'.
Инициализация выполняется по правилам, определенным для массивов.
Тексты в кавычках эквивалентны инициализации каждой строки в массиве. Запятая разделяет соседние
последовательности.
Кроме того, можно явно задавать размер строк символов, используя описание, подобное такому:
Разница заключается в том, что такая форма задает «прямоугольный» массив, в котором все строки имеют одинаковую длину.
Свободный массив
Операции со строками
Большинство операций языка Си, имеющих дело со строками, работает с указателями. Для размещения в оперативной памяти строки символов необходимо:
- выделить блок оперативной памяти под массив;
- проинициализировать строку.
Для выделения памяти под хранение строки могут использоваться функции динамического выделения памяти. При этом необходимо учитывать требуемый размер строки:
Для ввода строки использована функция scanf() , причем введенная строка не может превышать 9 символов. Последний символ будет содержать '\0' .
Функции ввода строк
Для ввода строки может использоваться функция scanf() . Однако функция scanf() предназначена скорее для получения слова, а не строки. Если применять формат "%s" для ввода, строка вводится до (но не включая) следующего пустого символа, которым может быть пробел, табуляция или перевод строки.
Для ввода строки, включая пробелы, используется функция
В качестве аргумента функции передается указатель на строку, в которую осуществляется ввод. Функция просит пользователя ввести строку, которую она помещает в массив, пока пользователь не нажмет Enter.
Функции вывода строк
Для вывода строк можно воспользоваться рассмотренной ранее функцией
или в сокращенном формате
Для вывода строк также может использоваться функция
которая печатает строку s и переводит курсор на новую строку (в отличие от printf() ). Функция puts() также может использоваться для вывода строковых констант, заключенных в кавычки.
Функция ввода символов
Для ввода символов может использоваться функция
которая возвращает значение символа, введенного с клавиатуры. Указанная функция использовалась в рассмотренных ранее примерах для задержки окна консоли после выполнения программы до нажатия клавиши.
Функция вывода символов
Для вывода символов может использоваться функция
которая возвращает значение выводимого символа и выводит на экран символ, переданный в качестве аргумента.
Пример Посчитать количество введенных символов во введенной строке.
Результат выполнения 
2. Содержание и технология работы
Для решения задач необходимо запустить MS VS 2005 (Пуск — Microsoft Visual Studio 2005), создать новый проект.
В диалоговом окне Начальная страница (Start Page) нажать кнопку Create Project.
В появившемся диалоговом окне New Project в полях и областях задать параметры:
поле Name — имя создаваемого проекта;
поле Location — установить папку для размещения файлов проекта;
область Project Types — выбрать вариант Visual C++ Projects;
области Templates — выбрать вариант Win32 Console Application;
нажать кнопку ОК.
Ввести текст программы на языке программирования СИ.
Запустить программу нажатием кнопки Start или F5. Если в программном коде не обнаружено ошибок, будет получен результат.
Рассмотрим примеры задач работы со строками.
Задача 1. Ввод и вывод строк
Составим программу, которая запрашивает имя пользователя и здоровается с ним.
Текст программы будет выглядеть следующим образом:
Подключим библиотеки, в нашей программе их потребуется 3: stdafx.h, stdio.h, conio.h:
Объявим главную функцию:
Объявим две строки:
char name[15];//отведение в памяти компьютера места под строку с максимальной длиной 15 символов
char fam[20];//отведение в памяти компьютера места под строку длиной 20 символов
Организуем считывание (инициализацию) двух строк с клавиатуры:
prinf («Как Вас зовут?\n»);
prinf («Введите свое имя и фамилию, затем нажмите Enter»);
Здесь функция scanf читает из буфера клавиатуры символы до разделителя – пробела.
Выведем строки на экран:
printf («Здравствуйте, %s %s!\n», name, fam);
Задержим результат на экране:
Закроем главную функцию:
Блок-схема данной программы приведена на рисунке 1.
Блок 1 – начало программного блока.
Блок 2 – ввод строк name и fam с клавиатуры.
Блок 3 – вывод значений строк name и fam на экран.
Блок 4 – конец программного блока.
Рис.1. Блок-схема ввода и вывода строк
После запуска программы на выполнение, получим следующий результат:
Как Вас зовут?
Введите свое имя и фамилию, затем нажмите Enter
-> Иван Федоров
Здравствуйте, Иван Федоров!
Задача 2. Организация посимвольного считывания строк
Составим программу, которая запрашивает у пользователя строку, затем выводит эту строку, вставляя после каждой буквы дополнительный символ ‘*’.
Для реализации данной программы необходимо будет определить длину строки, затем в цикле с заданным количеством итераций, от первого символа строки до последнего (который определяется общей длиной строки), выводить отдельной каждый символ строки, вставляя после него символ ‘*’.
Блок-схема данной программы приведена на рисунке 2.
Рис.2. Блок-схема программы посимвольного считывания строк.
Текст программы будет выглядеть следующим образом:
Подключим библиотеки, в нашей программе их потребуется 4: stdafx.h, stdio.h, conio.h, string.h:
Объявим главную функцию:
Объявим строку:
Объявим дополнительные переменные (длину строки l и переменную цикла с заданным числом итераций i, целого типа):
Организуем считывание (инициализацию) строки с клавиатуры:
prinf («Введите строку, затем нажмите Enter»);
Определим длину строки:
В цикле с заданным количеством итераций будем посимвольно считывать каждый символ строки, вставляя после каждого символа знак ‘*’, здесь – переменная i – текущий номер символа в строке:
Задержим результат на экране:
Закроем главную функцию:
После запуска программы на выполнение, получим следующий результат:
Введите строку, затем нажмите Enter
-> Здравствуйте
Задача 3. Работа с кодами символов
Составим программу, которая запрашивает у пользователя строку в нижнем регистре и переводит введенные символы в верхний регистр.
Подобное преобразование основано на использовании таблицы кодировок ASCII. Символы нижнего регистра имеют в ней коды от 97(a) до 122(z), а верхнего – от 65 (A) до 90(Z). При этом символы в таблице располагаются последовательно. В результате чего преобразование можно осуществить просто путем вычитания из кода символа нижнего регистра значения 32. Например, пользователь вводит значение символа в строковом формате:
Для получения кода символа достаточно преобразовать введенный символ в числовой формат:
Далее проверяем, находится ли полученный код символа в нижнем регистре, то есть попадает в диапазон от 97 до 122 и при необходимости вычитаем из него число 32.
Текст программы будет выглядеть следующим образом:
Подключим библиотеки, в нашей программе их потребуется 4: stdafx.h, stdio.h, conio.h, string.h:
Объявим главную функцию:
Объявим строку:
Объявим дополнительные переменные (длину строки l и переменную цикла с заданным числом итераций i, целого типа):
Организуем считывание (инициализацию) строки с клавиатуры:
prinf («Введите строку, затем нажмите Enter»);
Определим длину строки:
Огранизуем посимвольное считывание строки, i – текущий номер символа в строке:
Проверим условие, что текущий символ строки попадает в заданный диапазон, то есть является строчной буквой латинского алфавита. Для преобразования символа в его код используем оператор int, если условие истинно, то изменяем код символа, то есть вычитаем из него 32:
Выводим символ на экран:
Закрываем цикл с заданным количеством итераций:
Задерживаем результат на экране:
Закрываем главную функцию:
В результате выполнения программы получим следующее:
Вариант 1. Все символы введенной строки будут являться строчными буквами латинского алфавита:
Введите строку, затем нажмите Enter
-> hello
Вариант 2. Не все символы введенной строки будут являться строчными буквами латинского алфавита:
Как посимвольно считать строку в си
Добавим к системной функции write еще и read. Тогда мы получим возможность вводить данные в работающую программу. Эти данные могут поступать как с клавиатуры, так и из файлов на диске, а также по конвейеру из других программ. Добавление read делается с головокружительной простотой:
Лст. 1-1. Копирование файла в новый и правка.
Рис. 1-1. Функция read.
Меняется только write на read и номер системной функции 0. Как получить объектный модуль, вы уже видели. Сделайте это сами, а потом мы займемся очень полезным мероприятием: избавимся от бесконечного набора командных строк.
Здесь я предлагаю воспользоваться вот такой полезной вещью:
Лст. 1-2. Очень простой командный файл для компиляции.
Это скрипт для оболочки bash, указание об этом для операционной системы есть в самой первой строке. Я назвал этот файл просто m, чтобы не колотить долго по клавиатуре. Коротко о том, как он работает. Вы уже можете разобрать знакомые строки. Но кое-что для новичков нуждается в пояснении. Не углубляясь в детали программирования для оболочки, запомним следующее:
$1 – это первый параметр, передаваемый в скрипт из командной строки. В нашем случае, ожидается имя главного файла программы на языке C. То есть фактически $1 представляет hello. Командный процессор просто производит подстановку. Остальные объектные модули должны быть уже подготовлены. Компилятор обрабатывает исходный файл на языке C, но перед записью в файл hello.s очищает его от макросов, при помощи потокового редактора sed. Вывод cc подается по конвейеру через фильтр. Программа для sed состоит из набора шаблонов для удаления строк, где они встречаются, поэтому очень важны малозаметные символы апострофов ‘.
Оставшиеся командные строки вам уже знакомы. Всюду, вместо $1, скрипт подставит hello, или другое имя с вашей программой. Только не используйте расширение файла .c – этот скрипт не настолько умен, чтобы его игнорировать.
Немного о ключах в командных строках. cc: Как вы уже знаете, -S это указание компилятору вывести результат в файл с ассемблерным кодом. -fno-builtin – это указание игнорировать имена встроенных функций. Это мы проясним потом, хотя пока ни одной такой функции не используется.
as: -o (output) Это ключ для имени выходного файла, по умолчанию мы получим файл a.out
ld: -o Как и выше, а -s (strip) удаление отладочной информации из исполняемого файла. И в самом деле, нам она только лишняя обуза. Итак, делаем скрипт исполняемым:
Лст. 1-3. Изменение прав доступа к файлу.
и пользуемся им на здоровье.
Чтобы испытать новую функцию read, напишем новую версию hello. Теперь программа должна спросить у пользователя имя и поприветствовать его. После того, как программа заработает, мы разберем ее достаточно подробно. Код программы я показываю пока в скринах редактора, чтобы подчеркнуть синтаксические элементы подсветкой. Позже они пойдут в обычных листингах.
Рис. 1-2. Новая версия hello.
Компилируем программу и запускаем:
Рис. 1-3. Новая версия. (Еще и работает!)
Вот так просто. Вместо длинных командных строк. По сути дела, мы выполнили операции 1, 2 и 5 из предыдущей главы (см. Рис. 0-8). По аналогии с производством можно сказать так: с помощью скрипта/команды m мы из мастера, который бегает между работниками, превратились в начальника цеха, который не занимается мелочами.
Теперь пришло время обратить внимание на сам код в программе C. Сначала на то, что в языке используется понятие типа данных. Есть несколько элементарных типов, мы не будем нудно перечислять, а затронем только используемые.
char – это числовой тип для представления букв, цифр и знков препинания. Занимает размер в 1 байт. Может представлять беззнаковые числа в диапазоне 0т 0 до 255.
int – это числовой тип для представления целых чисел. Любой элемент данных такого типа занимает 4 байта. Представляет числа со знаком в диапазоне от -2147483647 до 2147483647.
Тип данных записывается перед объявлением имени переменной. Так как char – это всего один байт, то для выделения памяти для строки используют массивы. Квадратные скобки – оператор индекса в массивах. Если в квадратных скобках ничего не указано, то компилятор может узнать о размере массива из его инициализирующей части. Например, ask имеет размер 19 байт, так как такова длина строки, записанная после оператора присваивания – знака равенства.
Кстати, строки в языке C всегда записываются в двойных кавычках, а одиночные символы – в одиночных кавычках.
Переменная-массив answer содержит заготовку ответа пользователю и достаточный запас для остатка – имени пользователя. На этот раз мы не просто инициализировали строку, но еще и предусмотрели 256 байтов.
В квадратных скобках указывается размер массива. Массив name резервирует память в размере 32 байта, но ничем не инициализирован.
Кроме того, в программе есть две переменные целого типа i и j, для перебора символов в строке. Как можно заметить, язык допускает перечисление нескольких переменных после объявления типа.
И еще одна очень важная вещь: каждая инструкция в языке C обязательно заканчивается точкой с запятой. Объявление переменной – тоже инструкция.
В этой книжке мы часто будем просматривать код ассемблера, сгенерированный для наших программ или отдельных функций. Это поможет лучше понять язык C, мы увидим его подобно врачу, который смотрит рентгеновский снимок. Сейчас давайте посмотрим на распределение памяти, которое создал компилятор для переменных.
Лст. 1-4. Память для переменных в программе hello v2.
Данные делятся на инициализированные и нет. В первом случае, они “зашиваются” в код программы. Во втором, – для данных выделяется память необходимого размера, но это происходит в процессе загрузки. Инициализированные данные влияют на размер скомпилированной программы, а неинициализированные нет. Неиспользованная память в сегменте данных заполняется нулями. Как мы можем видеть, это делает компилятор, заполняющий остаток строки нулями. Компилятор, как нетрудно догадаться, сам принимал решение, в каких сегментах размещать объявленные в программе переменные. Что касается выравнивания (alignment), то это способ расположить данные в памяти так, чтобы их выборка производилась как можно быстрее. Выравнивание приводит к небольшой потере памяти: для ask мы использовали всего 20 байт памяти, но из-за выравнивания с границей 16 было израсходовано 16+4 и еще 12 байтов образовали дыру, не занятую ничем. Такова оптимизация по умолчанию, которую предлагает компилятор, – по скорости выполнения.
Теперь к коду самой программы. Начнем с пояснения вызова функции. Первой в программе C всегда вызывается функция main (не считая стартового кода). Все остальное, внутри фигурных скобок, делает пользователь, то есть, тот, кто писал программу. Сначала мы вызываем функцию write, которая должна вывести вопрос на экран. Эта функция принимает три аргумента: дескриптор файла, адрес данных, которые надо вывести, и длинну (размер) данных.
Размер данных в нашем случае выполняет оператор sizeof. Он похож на функцию, но называется оператором. Формально это и есть функция, но sizeof выполняется во время компиляции, а не при работе программы. (Математики обычно называют операторами плохо ведущие себя функции.) Здесь sizeof избавляет нас от подсчета букв в строках.
1 – это дескриптор файла stdout, а 0 – stdin (есть еще 2 – stderr). Для каждой запущенной программы автоматически открываются эти три файловых потока. Правда, они имеют указанные символические имена (STanDard OUTtput, standard input, standard error), но у нас пока все так просто, что мы можем позволить себе роскошь пользоваться совсем небольшими числами.
Второй аргумент функции write – адрес строки для вывода. Как давно известно, любое имя всегда относится к определенному адресу, будь то имя переменной или имя функции. Их для того и придумали, чтобы ассемблер (или компилятор более высокого уровня) избавил человека от ужасного геморроя по ручному распределению адресов.
И наконец, третий аргумент – это размер данных. Чтобы знать, когда остановиться. Функция read имеет совершенно аналогичный набор аргументов. Список аргументов этих функций совершенно логичен: куда/откуда, что, и в каком количестве писать или читать.
После того, как функция read запишет в переменную name ввод пользователя, программа должна составить строку из приветствия, имени пользователя, и восклицательного знака. Для этого мы можем просто дописать в строку answer имя пользователя, или то, что он ввел, используя зарезеревированное место. Но что значит “дописать”? Мы должны объяснить это буквально: копируем символы из строки name в строку answer начиная с места после пробела. Копирование должно вовремя остановиться. Для этого мы должны вычислить длину введенного имени. (Можно было бы узнать эту длину другим способом, если вы наблюдательны и можете мыслить по аналогии.)
Цикл for (это тоже оператор, оператор цикла) занимается подсчетом длины. Вообще-то, он может заниматься чем угодно, но в нашем случае он подсчитывает байты. Этот пример цикла не использует инструкции, которые выполняются при его проходе. Бывают и такие циклы. В скобках этого оператора задается начальное значение переменной цикла, i, затем проверяется условие: не равен ли очередной байт нулю?, и затем, переменная цикла увеличивается на единицу. Если условие нарушено – цикл прекращается. Как результат, мы в этом случае используем саму переменную i.
Оператор != – имеет смысл “не равно”. Нулевой байт, как и каждый предстваитель типа char, закавычен апострофами. Причем, это не символ нуля, это именно нулевой байт, поэтому он записывается как \0, а не 0. Дело в том, что ‘0’ – это код символа нуль, он равен 0x30 в шестнадцатеричной системе счисления, а ‘\0’ – это 0x00 (числа записаны по правилам языка C в системе с основанием 16. Десятичный эквивалент 0x30 3*16 = 48).
Следующий цикл for использует переменную j для обращения к name по индексу элемента массива. Здесь проверяется аналогичное условие равенства байта нулю. Таким образом, мы достигаем конца строки name. В языке C признаком конца строки считается нулевой байт, называемый также нуль-терминатором или завершающим нулем, это синонимы. Конструкция answer[i++] означает, что сначала выбирается i-й байт массива answer, а затем i увеличивается на единицу. i++ это пример постинкремента, а у нас есть еще и другой пример, когда переменная сначала инкрементируется, а потом используется. Но об этом чуть ниже.
Последний цикл for имеет инструкцию, именно поэтому в нем нет точки с запятой после закрывающей скобки при for. Инструкция перенесена в следующую строку. Собственно, инструкция как раз и состоит из оператора for и последующего присваивания-копирования.
Странным может показаться последующее, где мы дописываем строку ответа. Когда второй цикл выполняется последний раз, то i увеличивается на единицу, так же, как и во всех предыдущих случаях. Тогда зачем мы обращается к предыдущему элементу answer[i-1]? Все дело в том, что когда данные в файловый поток поступают с клавиатуры, туда же идет и клавиша Enter. И лишь после этого строка завершается нулем. Все логично, вы же ввели строку в файл? Вот строку и получайте. Она интерпретируется как перевод строки, и восклицательный знак переедет на новую строку. Но такая строка, разорванная на две части, нас не устраивает. Поэтому мы подавляем ненужный символ, просто записывая на его место восклицательный знак. А затем, вместо последнего символа записываем перевод строки, символ ‘\n’ или байт 0x0A, что то же самое. И после этого записываем завершающий ноль. Чтобы не затереть \n, мы сначала увеличиваем i на единицу, а затем используем. Это пример преинкремента (предварительного увеличения) ++i. И наконец, записываем на экран строку, которая получилась в результате.
Конечно, в таком сыром виде язык никто не использует. Возможность писать функции предоставляет неисчерпаемые возможности по упорядочиванию и организации кода. И естественно, начинать нужно с самого начала, с работы над самыми простыми элементами текста, отдельными символами.
Обе эти функции были написаны для того, чтобы проще было извлекать символы из потока, или наоборот, помещать их туда. Очень часто такие действия требуются для раздельного перебора символов с какими-то целями. Входной поток символов может управлять работой программы. Но давайте напишем функции getc, putc и проверим их работу в простой программе.
Лст. 1-5. Код функции getc.
Функция получает в качестве аргумента дескриптор файла и возвращает считанный символ. Если происходит ошибка при операции чтения, то read вернет число -1 в переменную e и установит код (причину) ошибки. Мы эту ситуацию пока не обрабатываем (не пользуемся переменной errno, да и бог с ней). Для нас важно, что если read возвращает не -1 и не 0, а что-то другое, то значит, все в порядке. А именно, read возвращает число реально прочитанных байтов. Если read прочитает символ конца файла, EOF, он же число -1, то она, (функция read), вернет ноль.
Как уже нам известно, read передает считанную из файла информацию через указатель в своем втором аргументе. Сначала мы получаем адрес той переменной, куда надо записать результат, а затем преобразуем его в указатель на целое и (третий аргумент), читаем один элемент данных. Так что, мы можем прочитать из файлового потока и -1 в том числе. Но обратите внимание, что на этот раз -1 попадает не в e, а в r, а это другое дело. В e в этом случае окажется 1.
Следующая инструкция проверяет, чем является e. Если это -1, то мы выходим из функции со значением -1. Если это 0, то мы тоже выходим из функции с тем же значением -1. Таким образом, ситуация ошибки также обрабатывается как конец файла, что в целом логично – файл-то, с точки зрения функции, все равно, накрылся медным тазом, до конца он прочитан, или нет. Если же все прошло нормально, то getc вернет считанный символ как целое число. В том числе, и символ UNICODE, который, в подавляющем числе случаев, занимает не более 2 байтов. Если read вернет 0, то из файла читайть больше нечего, а это равносильно концу файла и getc снова должна вернуть EOF, то есть, -1.
Функция putc действует обратным образом и записывает в поток символ, как целое число. Она использует системную функцию write.
Лст. 1-6. Код функции putc.
Эта функция получает два аргумента: символ для записи c, и идентификатор файла f. В случае успеха, то есть, если write вернет число, отличное от нуля, функция putc возвращает записанный символ, иначе -1.
Поскольку очень часто UNIX программы используются в конвейерах или просто терминале, то файловые потоки известны заранее. Это stdin и stdout (числа 0 и 1, в нашем нестрогом изложении). Поэтому были придуманы еще две функции getchar и putchar:
Лст. 1-7. Код функций getchar и putchar.
Обычно эти функции записывают как макросы, это быстрее и кода меньше, но, пока мы не используем препроцессор языка C, мы можем позволить себе такую роскошь. Не думаю, что сейчас хорошо вводить в рассмотрение лишние темы.
Имена функций getchar – взять (прочитать, извлечь) символ и putchar – положить (вывести, напечатать) символ просты и понятны всем англоязычным, а теперь и русским, пользователям языка C, С-программистам. К сожалению, этого не скажешь про множество других функций.
Но пора испытать написанные функции в работе. Это можно сделать в одном, общем файле. Код функций мы напишем в самом начале, а главную функцию, откуда они будут вызываться, ниже. Если функции себя хорошо ведут, то мы скопируем их код в отдельные файлы, а затем сделаем из них отдельные объектные модули и припишем их в список компоновщика в файле m. Это не самый идеальный метод, но пока лучше использовать именно его. Просто поверьте на слово.
Была такая машинка шифровальная, широко известная по грешным делам Кригсмарине времен WW2 (Функшлюссель Ц). Вояки выкупили коммерческую машинку, усилили ее добавочными дисками и снабдили ею свой флот, бывший, в основном, подводным. Предполагалось, что расшифровка займет три месяца, а за это время соответствующая информация устареет. Сама суть шифрования заключалась в том, что каждая буква в тексте преобразовывалась в другую по заданному ключу. И если частотный анализ позволял легко восстановить исходную букву для одной операции, то для двух сделать это было уже труднее, трех, четырех – очень сложно и так далее.
Дело в том, что в каждом языке частота букв в словах своя, и зная статистику по буквам в тексте, можно восстановить исходный текст. Чем чаще мы применяем замену букв, тем “ровнее” делается распределение по частоте букв в тексте. Тем большая выборка, время и объем вычислений понадобятся для расшифровки. Знание метода шифрования тут ничем не поможет. Только угаданный ключ. Технически все эти дела могут быть обставлены очень тонко и хитро, но мы упростим задачу, тем более, что я и сам не сильно большой специалист в тайнописи. (Дж. И. Литтлвуд приводит такую шутку: “предположим для простоты”, что означает простоту самого рассуждающего.)
К сожалению, мы еще не добрались до разбора аргументов командной строки, поэтому просто зашьем ключ шифрования в саму программу. Пусть его длина равняется четырем, как пин-код в телефоне. Однако, мы можем использовать любые символы, набираемые с клавиатуры.
Лст. 1-8. Библиотечка для теста и шифровальная машина.
Работает все это достаточно просто. Программа работает в бесконечном цикле. В этом нет ничего страшного, в таком же цикле работает и любая операционная система. Всегда наступит некое событие, которое это цикл прервет (хотя бы Страшный Суд). В нашем случае цикл прервется в конце файла, поступающего на вход машины.
Внутри цикла читается очередной символ в переменную c. Сразу же проверяем: не пора ли закругляться? Если нет, запускаем машину, то есть, входим в функцию crypt. Функция получает символ и шифрует его. Зашифрованный символ помещается в ту же переменную, откуда был взят. Затем остается только направить его в выходной поток. Вот и вся работа на этом уровне.
Внутри crypt содержится код, на основе статической переменной i, симулирующий работу колеса настоящей машины. Чтобы «колесо» действительно вращалось, мы проверям значение i, и в случае, если оно больше 3, присваиваем ему значение 0. Таким образом, мы перебираем значение ключа key по кругу, что и означает работу колеса.
Сама же функция шифрования – это просто логическая операция XOR, предложенная еще американским инженером из AT&T Джилбертом Вернамом для шифрования телеграфных кодов. Она обратима, как мы позже увидим.
Посмотрим, как работает машинка:
Рис. 1-4. Работа шифровальной машины и тест функций.
Мы создали кодированный файл wetterbericht на диске. При попытке напечатать его мы получили абракадабру, содержащую непечатаемые символы. Для бумажной машинки это недопустимо, но для компьютерного файла, — почему бы и нет? В крайнем случае, мы всегда можем напечатать шестнадцатеричный дамп этого файла.
Мы также просто можем расшифровать зашифрованный файл:
Рис. 1-5. Повторное шифрование шифра.
«Весит» наша машинка всего 904 байта.
Если взять не ключ длиной 4 байта, а случайную последовательность символов очень большой длины, например, читаемую из отдельного файла, то можно обеспечить абсолютно стойкое шифрование. Такой прием использовали дипломаты и шпионы в докомпьютерную эру. Случайный файл назывался шифроблокнотом. Если оба корреспондента имеют такой большой файл, размером в несколько гигабайт, то можно шифровать не меньшее количество текста, при условии, что каждый кусок «ключа» используется однократно. Сгенерировать такой файл можно, имея генератор белого шума (например, на основе диода, включенного определенным образом) и АЦП на 8 бит, если направить поток образующихся данных в файл. Это будет истинно случайная последовательность, а не псевдослучайная, которая обычно применяется в компьютерах.
Перехват кодированных сообщений, полученных таким образом, вполне возможен, но разобрать их, имея доступ лишь к каналу связи, не в силах никто. Все спецслужбы мира, вооруженные хоть квантовыми компьютерами, бессильны. Впрочем, это не помешает добраться до любого из корреспондентов, а магической силы паяльника в жопе еще никто не отменил.
Что касается нашей машинки, это всего лишь игрушка, не так ли? Читателю предлагается как-нибудь на досуге выяснить, что означает:
Лст. 1-9. Послание потомкам.
Метод кодирования и длина ключа прежние. Надо найти ключ и закодированный текст.
На этом тема главы как будто исчерпывается, по крайней мере, для начала. Уже эти функции дают возможность провести кое-какие исследования. Например, можно подсчитывать частоту появления каждой буквы в тексте. К сожалению, пока мы не можем работать с таким составным типом данных, как строки. Не можем работать с числами. Над этим мы поработаем в ближайших двух главах.
Как стать программистом
Это моя личная ссылка-приглашение на Stepik для вас. Регистрируясь по этой ссылке, записываясь на курсы и решая задачи, Вы помогаете автору данного сайта принять участие в конкурсе платформы Stepik! Подробности конкурса здесь: https://vk.cc/75rKuS
понедельник, 17 октября 2011 г.
Занятие 3. Ввод и вывод данных.Справочники функций. Уроки программирования для чайников. Язык Си.
Добрый день уважаемые читатели.
В данном уроке мы подробно остановимся на вводе и выводе данных. Узнаем что такое стандартный поток ввода и вывода. Поговорим о том, зачем нужна стандартная библиотека функций. А так же научимся работать со справочниками по функциям. Это очень полезное умение. Рассмотрим на простом примере, который как раз будет в тему нашего урока.
Прочитайте улучшенную версию этого урока «Ввод/вывод в языке Си».
- Дополнительные материалы
- Задачи с автоматической проверкой решения
- Исследовательские задачи
Пусть нам требуется ввести с клавиатуры в программу какое-то число. Дело в том, что в языке нет никаких специальных конструкций, определяющих ввод-вывод. Если вы внимательно читали первый урок, то я уже вскользь упоминал об этом (помните для того чтобы вывести на экран строчку, нам надо было включить в программу заголовочный файл stdio.h) . Так вот, в самом языке нет даже такой операции как возведение в степень числа, или вычисление квадратного корня. Но обычно, сам по себе язык и не используется. Вместе с языком программирования поставляется и стандартная библиотека функций. Это набор файлов с расширением *.h, в которых описаны различные дополнительные функции, которые любая программа может использовать. Как вы уже догадались, функции ввода вывода описаны в файле stdio.h. Помимо стандартной библиотеки функции, программисты пишут и свои библиотеки функции, и еще существует много других библиотек функций, написанных для какого-то определенного круга задач. Таким образом, разных готовых функций для языка Си очень-очень много, и знать их все вряд ли возможно, а учитывая то, что знать надо не только название функции, но и какие данные она принимает, какие возвращает, что она делает, то это становится почти невозможно задачей. Но к счастью, этого и не требуется. Для стандартной библиотеки функции существуют куча различных справочников и там подробно описано всё это. И вот именно работать с этими справочниками мы сегодня научимся. Так, приступим же.
Стандартная библиотека включает несколько функций для чтения и записи одного символа. Простейшие из них мы сегодня и рассмотрим. Функции getchar и putchar.
Теперь пришло время научиться работать со справочником функции. В интернете можно найти много различных справочников, можно купить так же справочник в книжном магазине, часто в конце различных учебников по программированию есть небольшие справочники по функциям стандартной библиотеки. В общем, не суть важно, какой использовать, содержание везде примерно одинаковое. Для примера используем справочник сайта CodeNet. Никакого скрытого смысла тут нет, просто если в google набрать «справочник по функциям С» то он будет на первой позиции. Выберем там функцию getchar. Вот её описание:
