Рубанчик В.Б., Михайличенко В.Н.

Лабораторная работа " Ввод и вывод символов"

5/5

Лабораторная работа

Тема: Статическое выделение памяти. Строки и массивы указателей

Цель работы: Освоить некоторые принципы конструирования программ и написания функций для обработки строк.

Статическое выделение памяти

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

Определения объектов используются компилятором, чтобы включить в исполняемый код программы (exe) команды, необходимые для выделения памяти объектам и правильной интерпретации их значений.

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

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

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

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

Замечание

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

Постановка и метод решения задачи лексического разбора строк

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

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

Необходимо

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

• дать возможность программе работать с каждым словом отдельно.

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

Введем ряд ограничений, уточняющих и упрощающих решение задачи.

Анализируемая фраза (строка)

а) имеет длину не более 100 символов,

б) начинается с непробельного символа,

б) содержит не более 9 слов и

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

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

Для решения задачи предлагается использовать следующий алгоритм.

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

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

• адрес нового слова (его первого символа) запоминается в специально созданном массиве указателей.

Исходное предложение

Э

т

о

н

е

б

о

л

ь

ш

а

я

ф

р

а

з

а

\0

Занесение нуль-терминаторов

Запоминание указателей

\0

Массив указателей

NULL

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

1. Первый вопрос — какой размер массива указателей нужно указать в его определении?

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

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

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

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

Более простое решение: когда разбор строки заканчивается в массив указателей добавляется признак конца созданного массива — фиктивный адрес NULL. Тогда информация о количестве элементов окажется "запрятанной" в самом массиве, и дополнительная переменная-счетчик не нужна. Для обработки массива вместо цикла for (цикл с известным числом повторений) нужно будет использовать while (цикл с неизвестным числом повторений)

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

2. Второй вопрос — где определять массив указателей? Есть три места, где может быть описан массив: на глобальном уровне, в функции main, и в функции str_split.

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

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

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

Если внутри функции определить массив класса auto, то при выходе из функции занимаемая массивом память будет освобождена, и результаты выполнения функции str_split будут просто потеряны. Чтобы массив сохранился (и к нему можно было обращаться) после выхода из функции, он должен быть описан со спецификатором static.

ЗАДАНИЕ 1 (первый вариант программы)

Написать программу, решающую задачу простого лексического анализа символьных строк.

Используемые ограничения на длину исходной строки (предлагается 100) и на максимальное количество слов в строке (предлагается 9) задать с помощью именованных констант MAX_STRING и MAX_WORDS.

Программа состоит из двух функций.

1. Функция str_split выполняет лексический анализ строки. Эта функция имеет два аргумента:

а) phrase — "входной" аргумент, символьная строка, которую необходимо "разобрать" на слова,

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

Функция не возвращает никаких значений.

В функции реализован алгоритм замены пробельных символов нуль-терминаторами.

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

2. Функция main используется для тестирования функции str_split.

В этой функции:

а) задается символьная строка, включающая все три типа пробельных символов (' ', '\t' и '\n'),

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

в) вызывается функция str_split,

г) организуется цикл для вывода отдельных слов (каждого с новой строки).

Замечания

1. Чтобы сохранить адреса слов, нужно создать массив указателей на char, размера MAX_WORDS. Тип соответствующего ему аргумента функции str_split можно указать двумя способами:

а) как массив указателей на char, причем количество элементов не указывается,

б) либо как указатель на "указатель на char*, что соответствует типу одномерного массива из указателей на char.

2. Когда массив pWord будет заполнен, то нужно в его очередной элемент поместить указатель NULL. Это будет признаком того, что все слова закончились, и потребуется использоваться при выводе на экран. Очевидно, что этот массив должен иметь длину на единицу больше максимального числа слов.

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

4. Для вывод результата преобразований строки на печать удобно пользоваться циклом типа while.

ЗАДАНИЕ 2 (массив указателей определен в функции)

Условие задачи остается без изменений, меняется реализация программы, так как массив pWord определяется не в функции main, а в str_split.

1. Функция str_split имеет только один аргумент phrase, через который передается анализируемая строка.

Массив указателей pWord, в котором будут храниться адреса слов, определяется в функции str_split, причем как статический.

Функция возвращает указатель на этот массив.

Для проверки, не является ли очередной символ пробельным (пробел, табуляция, новая строка), используется переключатель switch.

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

3. Функция main используется для тестирования новой функции str_split.

В функции main:

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

б) Результат работы функции str_split необходимо сохранить в переменной, которая далее будет использоваться для печати слов (какой тип должна иметь эта переменная?).

Для заданной строки вызывается функция str_split.

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