OOP_lab03
.pdf
{
return sqrt(arg.re * arg.re + arg.im * arg.im);
}
В реальной программе определение структуры Complex,а также объявления функций их обработки следует вынести в заголовочный файл, например, с именемcomplex.h, не забыв разместить в нем директивы, защищающие от его повторного включения, а реализацию функцийработы с комплексными числами поместить в файлcomplex.cpp. В этом случае подключение стандартного заголовочного файла math.h, содержащего объявление функции sqrt, следует выполнить в файлеcomplex.cpp.
Пример использования структуры Complex:
#include <stdio.h> #include “complex.h”
int main(int argc, char * argv[])
{
Complex a = {2, 3}; Complex b = {3.5, -8.8}; Complex c = Add(a, b);
printf(“Length(c) = %f\n“, GetLength(c)); return 0;
}
Работа суказателями, динамическое выделение памяти
Указателиявляются мощным средством языковC и C++,предоставляющим программиступрямойдоступ к памятикомпьютера (разумеется ,в пределах доступного адресного пространства), а также работус динамическивыделяемой памятью.
Объявлениеиинициализацияуказателей
Указатель – этопростопеременная, хранящая адреснекоторой переменной определенноготипа. Например, объявление указателяс именем pChar на тип char будет записан следующим образом:
char * pChar;
При этом значение указателя (хранимого им адреса) будет не определено – указатель будет считаться неинициализированным.
В других языках программирования указатели (или ссылки), не инициализированные явным образом,могут быть автоматически инициализированынулевым адресом, либо иметь специально зарезервированное неопределенное значение (undefined).
ЯзыкиСи и Си++ в этом плане позволяют себе меньше заботы о программисте, что, с одной стороны,позволяет увеличить быстродействие программы,т.к. не тратится время на инициализацию не инициализированных явно переменных, а с другой стороны,требует от программиста повышеннойвнимательности, т.к. невозможно программным образом отличить неинициализированный указатель от корректно инициализированного. Попытка же чтения или
записи данных при помощи неинициализированного указателя приводит к неопределенному поведению.
Запомните: корректная работа с указателямитребует,чтобы указателибыли инициализированы до своегопервого использования. Под использованием указателя понимается его участие в выражениях,отличных от присваивания ему значений.
Указателюможноприсвоить значение адреса некоторой существующей переменной, значение другого указателя, а также особое значение0. В последнем случаетакойуказатель называется нулевым указателем. В заголовочных файлах стандартных библиотек Си и Си++ объявляется макросNULL, который рекомендуется использовать вместо 0, когда речь идет о значении указателя.
В других языках программирования для нулевого указателя или нулевой ссылки могут также использоваться специальные значения: nil в языкеPascal, null в Java, C#, ActionScript,JavaScript и т.п.
Стандартом языков Си и Си++ гарантируется,чтопо нулевомуадресуне будут размещаться никакие переменные,а также блокипамяти, выделяемые динамически4.Также очевидно,что указатели, хранящие одинаковые адреса, указывают на один и тот же объект в памяти.
Итак, указатель в один момент времени может быть инициализирован адресом некоторого существующего объекта впамяти, быть нулевым или не инициализирован.
Для получения адреса некоторойпеременнойможно воспользоватьсяоператоромвзятияадреса &:
char c = ‘A’; char * pCh = &ch;
Связьуказателейсмассивами,адреснаяарифметика
При помощиоператора& можно получить указатель на заданный элемент массива. Указатели на элементы массива могут участвовать в выражениях адресной арифметики.
Complex numbers[10]; int k = 2;
Complex * pItemk = &numbers[k];
//Имя массива может использоваться как указатель на его нулевой элемент
Complex * pItem0 = numbers;
//Указатели могут использоваться в выражениях адресной арифметики
Complex * pItem5 = pItem0 + 5; Complex * pItem3 = pItem5 – 2;
Complex * pItemNextTo3 = pItem3; ++pItemNextTo3; // указатель на элемент 4
int numberOfItemsBetweenKand5 = pItem5 – pItemk; // numberOfItemsBetweenKand5 = 3
//а вот так нельзя (операция сложения указателей отсутствует):
Complex * pError = pItem3 + pItem5;
Разыменованиеуказателей
4 Речь идетобиспользовании языков в прикладных программах. Разработка системного программного обеспечения может допускать возможность размещения и обращения к данным/коду по нулевому адресу.
Для обращения к данным, находящимся в памяти по адресу, хранимому указателем, необходимо выполнить операцию разыменования указателя, обозначаемую оператором *.Для обращения к полям структур, классов и объединений помимо оператора * можно (и даже рекомендуется) использовать оператор ->.
int k = 5;
int * pK = &k; // это объявление указателя
int b = *pK; // а это – его разыменование. В переменную b будет занесено значение 5 *pK = 8; // это тоже разыменование. По адресу pK (в переменную k) будет записано 8
Complex c;
Complex * pComplex = &c;
(*pComplex).re = 5; // записываем в поле re структуры по адресу pComplex число 5 pComplex->re = 5; // делаем то же самое, но более наглядным образом. pComplex->re = pComplex->im + 4;
Использованиеквалификатораconst совместно с указателями
Как ик обычным переменным к указателям применим квалификатор const,причем в нескольких контекстах:
•Неизменно значение самого указателя (адреса), данные поэтомуадресуможно изменять: k = 0;
int * const pInt = &k;
•Неизменно значение данных, на которые указывает указатель,само значение указателя можно изменять:
int a = 0; int b = 1;
int const * p = &a; // либо const int * p = &a; p = &b;
•Неизменно как значение указателя,так и данных, на которые онуказывает: int d = 0;
const int * const p = &d;
Легкозапомнить,чтоявляется константным, данные или указатель,если прочитать объявление указателя справа налево. Например:
Complex * const pArg = &item; // pArg – это константный указательнатип Complex
Указателю можно присвоитьзначение только указателя на совместимый тип данных. Например:
Complex complex;
Complex const constComplex;
Complex * pComplex = &complex; // можно (1)
pComplex = & constComplex; // нельзя – constComplex доступна только для чтения (2) Complex const * pConstComplex = & constComplex; // можно (3)
pConstComplex = pComplex; // можно (4)
pComplex = pConstComplex; // а вот так нельзя (5)
int * pInt = pComplex; // нельзя, типы не совместимы (6) Complex * const pComplexConst = & complex; // можно (7) pComplex = pComplexConst; // можно (8)
pConstComplex = pComplexConst; // нельзя изменить адрес константного указателя (9)
Присваивание (2) запрещено, т.к. к переменнойconstComplex разрешен доступ толькодля чтения, а, следовательно, указатель на этупеременную,возвращенный оператором &, не должен предоставлять больше прав доступа к переменной, чем сама переменная.
Присваивание (4) разрешено, а (5) запрещено, посколькув первом случаемы посредством указателя pConstComplex получаем к объектуправа доступа меньше,чем разрешено (только для чтения), а во втором
– пытаемся получить больше (для чтения изаписи), чем доступно (только для чтения).
В строке (7) мы имеем дело с обычной инициализацией константного указателя.
Присваивание (8) разрешено,т.к. при присваивании указателей учитываются права доступа к данным, на которые ссылается указатель, а не к самому указателю.
Присваивание (9) запрещено, т.к. значение константного указателя, как илюбой другойконстантной переменной,после инициализации изменить нельзя.
Указателина тип void
Существует специальный тип указателей, которому можно присвоить значение на данные любого типа (присохраненииправ доступа к объекту) – указатель на тип void.
Complex c
Complex * pComplex = &c; int j;
void * pVoid = pComplex; // так можно pVoid = &j; // и так тоже можно pComplex = pVoid; // а вот так нельзя
Использование указателя на void может быть полезным для хранения некоторых адресов памяти, содержимое которых не имеет значения. Например,функции fread и fwrite принимают в качестве одного из своих параметров адресблока памяти, данные которого должны быть прочитаны из файла или записаны в него.
На использование указателейнаvoid накладываются определенные ограничения:
•Операция разыменования для них не определена
•Операции адреснойарифметики для них также не определены
Преобразованиетипов указателей
Ивановабросилажена,егосократилинаработе,отнего отвернулисьдрузья,дажеродныедетиотвернулисьотнего. Но егогоречьбылабынеполнойбезкоробкигорькогошоколада «Россия». «Россия» - щедрая душа.
Анекдотнатемуизвестнойрекламы.
Работа с указателямив Си иСи++ была бы недостаточно мощнойбезоператоров приведения типов, позволяющих преобразовать указатель одного типа в указатель другого типа данных.Заметьте,что происходит лишь преобразованиетиповуказателей, но не данных, на которые они указывают.
В языке Сидля преобразования указателей используется один единственный, уже знакомый нам по лекции, оператор преобразования типов (тип):
int k;
int const * pInt = &k; char * pChar = (char*)pInt;
Однако использование данного способа приведения типов не рекомендуется в программах на языке C++,в виду своей топорности инеинтеллектуальности.Впрограммах на языке C++следуетвоспользоваться одним изследующих операторовприведения типов:
Оператор const_cast<тип>(выражение) позволяет снять константность с константного выражения:
int k = 0;
const int * pConstK = &k;
int * pK = const_cast<int*>(pConstK); const int & constRefK = k;
int & refK = const_cast<int&>(constRefK);
Оператор static_cast<тип>(выражение) позволяет выполнить статическое преобразование типа объекта:
int i = 0;
char ch = static_cast<char>(i); CDerived derived;
CDerived * pDerived = &derived;
CBase * pBase = static_cast<CBase*>(pDerived);
В случае суказателями и ссылками, данныйоператор позволяет привести указатель(или ссылку) на объект унаследованного класса к указателю (ссылке) на объект базового класса инаоборот. Такое преобразование не всегда является безопасным,т.к. оператор static_cast не производит никаких проверок на доступность данного преобразования во время выполнения программы. Склассами Вы познакомитесь в следующей лабораторной работе.
Оператор dynamic_cast<тип>(выражение) позволяет выполнить безопасное преобразование указателяили ссылки на объект базового класса к указателю или ссылке на объект унаследованного класса. Проверка допустимости такогопреобразования осуществляется во время выполнения программы, при этом программист может узнать об успешноститакого преобразования, проверив значение указателя (или перехватив исключение std::bad_cast):
CBase * pBase = new CDerived();
…
CDerived * pDerived = dynamic_cast<CDerived*>(pBase); if (pDerived != NULL)
{
// преобразование успешно
}
else
{
// преобразование невозможно
}
try
{
CDerived & derived = dynamic_cast<CDerived&>(*pBase); // преобразование успешно
}
catch (std::bad_cast & error)
{
// преобразование невозможно
}
Оператор reinterpret_cast<тип>(выражение) позволяет выполнить приведение целочисленного типа к указателю и наоборот, а также преобразование указателей несвязанных друг с другом типов,например, char* в int* илиvoid* в short*.Результат данного преобразования, как правило,может быть безопасно использован только для преобразования его обратно к своемуоригинальному типу.
int k = 5;
int * pInt = &k;
char * pChar = reinterpret_cast<char*>(pInt);
Указателинауказатели
Т.к.указатель тоже является переменной, возможновзятие адреса и у указателя припомощи оператора &:
int k = 5;
int * pInt = &k;
int ** ppInt = &pInt; // указатель на указатель на int
int valueOfK = **ppInt; // двойное разыменование указателя на указатель
Динамическоевыделениепамятив языкеСи
Стандартная библиотека языка Сипредоставляет рядфункций для работы с динамическойпамятью:
•malloc – выделяет блок памятизаданного размера
•realloc – изменяет размер блока памяти, выделенного ранее припомощи функций malloc, calloc и realloc
•calloc – выделяет блок памяти заданного размера и инициализирует его содержимое нулями
•free – освобождает блок памяти, выделенный ранее припомощи функций malloc, calloc иrealloc.
Для подключения данных функций необходимо подключить заголовочный файлmalloc.h.
Пример:
#include <malloc.h> struct Point
{
int x, y;
};
// выделяем блок памяти для хранения массива из 10 элементов типа Point
Point * pArrayOfPoints = reinterpret_cast<Point*>(malloc(10 * sizeof(Point))); if (pArrayOfPoints == NULL)
{
// ошибка выделения памяти
}
pArrayOfPoints[2].x = 3; free(pArrayOfPoints); pArrayOfPoints = NULL;
Динамическоевыделениепамяти в языкеСи++
Функцииmalloc,calloc, иrealloc всего лишь выделяют блоки памятив куче. Динамическое созданиеи удаление объектов в языке Си++требуют еще их корректной инициализации и деинициализации. В составе языка C++ есть следующие операторы:
•new – для создания одиночного объекта заданного типа в динамическойпамяти
•new [] – для создания массива из указанного количества объектов заданного типа
•delete – для удаления одиночного объекта, созданного ранее припомощи оператораnew
•delete [] – для удаления массива объектов, созданного при помощиоператораnew []
int main(int argc, char* argv[])
{
int * pInt = new int; // выделяем целое число без его инициализации
*pInt = 10; delete pInt;
pInt = new int (10); // выделяем целое число с его инициализацией delete pInt;
pInt = NULL;
int * pArrayOfInt = new int [10]; // выделяем массив из 10 целых чисел delete [] pArrayOfInt;
pArrayOfInt = NULL;
return 0;
}
Следует помнить о следующих правилах работы с динамическойпамятью:
•Программа должна освобождать более не используемые блоки динамическойпамяти. В противном случае из-за такихутечек памятипрограмме рано илипоздно просто не хватит памяти для продолжения работы.
•После освобождения динамическивыделенного участка памятипроизводить чтение или запись в нем нельзя.Пренебрежение этим правилом может привести к повреждению кучи и невозможности нормального функционирования программы.
•Повторное удаление блока памятитакже может привести к повреждениюкучи.
•Для освобождения памяти должен использоваться тот же механизм, что и для ее выделения. Функция free должна использоваться только для освобождения блоков памяти, выделенных при помощи malloc, calloc иrealloc.Операторdelete – для удаления объектов, созданных припомощи оператора new, а оператор delete [] – для удаления массивов объектов, созданных припомощи оператора new [].
Практические задания
На оценку «удовлетворительно» необходимо набрать не менее 30 баллов.
На оценку «хорошо» необходимо набрать не менее 90 баллов.
На оценку «отлично» необходимо набрать не менее 160 баллов.
Задание№1
Вариант 1– 30баллов
Разработайте программуsortlines.exe, выполняющую сортировкустрок, поступающих из стандартного потока ввода в лексикографическом порядке ивыводотсортированных строк в стандартныйпоток вывода.
Сортировка строк должна производиться припомощи функцииqsort стандартной библиотеки языка Си, либо ее более безопасного вариантаqsort_s.
В конце каждойстроки, поступающейсо стандартного потока ввода (за исключением, быть может, последней строки) располагается символ конца строки\n. В конце каждой выводимой строки также должен выводиться символ \n. Исключение составляет случай, когда входной файл пуст– в этом случае в output ничеговыводиться недолжно.
Как видно из условия задачи, строки могут быть произвольной длины, а их количество также может быть произвольным числом, поэтому для размещения строк в памятинеобходимо воспользоваться функциями динамического выделения памяти, либо операторамиnew/new[]/delete/delete[].
Примеры входных ивыходных данных программы могут быть найдены в каталоге tests\sortlines.
Вкомплектес программойдолженобязательно поставлятьсянаборфайлов,позволяющих проверить ее работув автоматическомрежиме.
Вариант 2– 100баллов
Разработайте программуinifile.exe, выполняющую считывание содержимого текстового .INI файла, содержащего настройки приложения в виде пар:
«ключ»= «значение»
Ключом является последовательность символов набора:A-Z,a-z, 0-9, точки и символа подчеркивания.
Значением является последовательность символов, начиная спервого печатаемого (т.е. не пробела или табуляции) символа после символа «равно» до последнего печатаемого символа в данной строке, либо заключенная в двойные кавычкипоследовательность символов.Внутри значения могут содержаться следующие стандартныеescape-последовательности(пары символов, начинающиеся с символа «\», трактующиеся особым образом): \\,\”,\r,\n, \t.
Функции работы с .ini файламидолжныбытьвынесенывотдельные.h и.cpp файлы.
.INI файл может содержать однострочные комментарии– строки,первым печатаемым символом которых является символ «точка с запятой», а также пустые строки.
Пример .INI-файла:
; размеры окна приложения
DEFAULT_WINDOW_WIDTH = 640 DEFAULT_WINDOW_HEIGT = 480
; тексты сообщений (при желании их можно перевести на другой язык) MSG_SUCCESS = “Работа завершена успешно”
MSG_EMPTY_LINE = ”” ;пустая строк
MSG_FAILED_TO_OPEN_FILE = “Не удалось открыть файл \”{FILE_NAME}\”” MSG_MENU = “1. Открыть файл\n2. Закрыть файл\n3. Выйти из приложения”
Формат командной строки приложения:
inifile.exe <имя ini-файла>
После запуска приложения приложение считывает указанныйini-файл и производит считывание «ключей» со стандартного потока ввода, пока не встретит символконца файла (EOF). После каждой введеннойстроки приложение производит поиск указанного ключа в памятии в случае успеха выводит в стандартныйпоток вывода «значение» данного ключа (с уже обработанными escape-последовательностями). В случае если ключ не найден, приложение должно вывести «Key ”<имя ключа>” was not found» и считывает следующую строку,вводимую пользователем.
Например, для вышеописанного ini файла при вводе строкиMSG_FAILED_TO_OPEN_FILE в output должно быть выведено:
Не удалось открыть файл “{FILE_NAME}“
Внимание, ключ и значение могут быть произвольной длины (используйтефункции и/или операторы для работы с динамическойпамятью)..INI файл может содержать произвольное количество записей.
Приложение должно обнаруживать и сообщать о различных ошибках в ходе работы программы, например, в случае ошибки при открытииINI-файла, при наличии недопустимых последовательностейв файле, встрече записи с уже существующим ключом. При обнаружении данных ошибок вini файле приложение должно вывести номер строки, в которой была встречена ошибка (начиная с единицы).
Внимание. Все текстовые сообщения, выводимые приложением должны содержаться в отдельном INI файле, которые загружается в самом начале работы приложения. В данном ini-файле также могут содержаться ошибки, чтоможет затруднить дальнейшую работу приложения (еслитолько в приложении не будут прошиты значения по умолчанию для всех используемых сообщений). Прилюбойошибке во время анализа данного ini-файла приложение должно немедленно завершить работу (с ненулевым кодом возврата) и вывести номер строки,в которой была найдена ошибка.
Приложение должно корректно освобождать выделенную память при выходе из программы, даже если этот выходбылвызван некорректнымивходными данными.
Внимание, в ходе работы над программой Вам понадобится самостоятельно разработать структуры данных и функции для работы с .INI файлом (чтение, поиск, возможно, какие-то еще другие). Располагаться объявления структур данных ипрототипы файлов должны в отдельном .h файле, а их реализация- в отдельном .c файле – оба файла должны быть также добавлены в проект. В основном файле main.c Вы должны подключить свой.h файл и использовать функции из него. Инкапсуляция в отдельных модулях кода и структур данных для работы с ini-файлами может облегчить поддержкуini-файлов в других программах.
Вкомплекте с программой должны обязательно поставлятьсянаборфайлов,позволяющие проверить ее работу в автоматическом режиме.
Задание№2 – 80баллов
Разработайте программу tree.exe, выполняющуюсчитываниеизстандартного потока ввода и осуществляющую форматированныйвывод встандартныйпоток вывода сильноветвящегося дерева.
Со стандартного ввода поступает информация о листьях дерева, заданная аналогично путям файловой системы Windows – при помощи символа «\» происходит задание путик листуотносительно корня дерева.
Каждыйузел дерева (не являющийся листом) может хранить внутрисебя другие узлы и листья.
Сами узлы илистья выводятся в output в порядке их поступления извходного файла, однако сперва выводятся узлы данного узла (с их дочерними элементами), а затем листья.
Узлы/листья с пустым именем(символ «\» не является частью имени узла, а служит лишь для разделения узлов призаданиипути) во входном файле являются недопустимыми и должны приводить к завершению работы приложения.
Внутриодного узла не допускаются листья с одинаковыми именами. В случае обнаружения данной ситуации необходимо вывести сообщение и выйти из программы.
Примеры входных ивыходных данных приложения описаны в подкаталоге tests\tree.
Длины имен узлов и листьев, как и их количество– не ограничены – используйте функции работы с кучей выделения блоков памяти необходимогоразмера.
Приложение должно корректно освобождать динамическивыделенную память, даже в случае выхода из приложения в виду встреченнойошибкиво входных данных.
Внимание, в ходе разработкипрограммы потребуется разработать функции и структуры данных для работы с деревом. Необходимообъявления структурданных и прототипы функцийразметить вовнешнем файле tree.h,а реализациюданных функций- в файле tree.c – эти файлы также должны быть добавлены в проект. В основном файле приложенияmain.c необходимо подключить заголовочный файл tree.h (#include
“tree.h”).
Вкомплекте с программой должны обязательно поставляться файлы,позволяющие проверить ее работув автоматическомрежиме.