Структуры данных в C++
Покупка
Тематика:
Программирование на C и C++
Год издания: 2020
Кол-во страниц: 158
Дополнительно
Вид издания:
Учебное пособие
Уровень образования:
ВО - Бакалавриат
ISBN: 978-5-7038-5256-9
Артикул: 804303.01.99
Рассмотрены методики, идиомы и приемы решения задач обработки динамических структур данных на языке С++. Подробно описаны вычислительные алгоритмы, реализованные с использованием нотации указателей.
Приведены краткие теоретические сведения и примеры приложений по изучаемому материалу. Изложена методика выполнения лабораторных работ по рассматриваемым темам, которая используется авторами в процессе проведения практических занятий в МГТУ им. Н.Э. Баумана.
Для студентов, обучающихся по направлениям подготовки «Программная инженерия» и «Информатика и вычислительная техника».
Тематика:
ББК:
УДК:
ОКСО:
ГРНТИ:
Скопировать запись
Фрагмент текстового слоя документа размещен для индексирующих роботов
З.Н. Русакова, И.В. Рудаков Структуры данных в С++ Учебное пособие Федеральное государственное бюджетное образовательное учреждение высшего образования «Московский государственный технический университет имени Н.Э. Баумана (национальный исследовательский университет)»
ISBN 978-5-7038-5256-9 Русакова, З. Н. Структуры данных в С++ : учебное пособие / З. Н. Русакова, И. В. Рудаков. — Москва : Издательство МГТУ им. Н. Э. Баумана, 2020. — 157, [1] с. : ил. ISBN 978-5-7038-5256-9 Рассмотрены методики, идиомы и приемы решения задач обработки динамических структур данных на языке С++. Подробно описаны вычислительные алгоритмы, реализованные с использованием нотации указателей. Приведены краткие теоретические сведения и примеры приложений по изучаемому материалу. Изложена методика выполнения лабораторных работ по рассматриваемым темам, которая используется авторами в процессе проведения практических занятий в МГТУ им. Н.Э. Баумана. Для студентов, обучающихся по направлениям подготовки «Программная инженерия» и «Информатика и вычислительная техника». УДК 519.682 ББК 32.073-018 © МГТУ им. Н.Э. Баумана, 2020 © Оформление. Издательство МГТУ им. Н.Э. Баумана, 2020 Издание доступно в электронном виде по адресу https://bmstu.press/catalog/item/6494/ Факультет «Информатика и системы управления» Кафедра «Программное обеспечение ЭВМ и информационные технологии» Рекомендовано Научно-методическим советом МГТУ им. Н.Э. Баумана в качестве учебного пособия УДК 519.682 ББК 32.073-018 Р88 Р88
ПРЕДИСЛОВИЕ Учебное пособие предназначено для поддержки выполнения лабораторного практикума по дисциплине «Информатика». Цель учебного пособия – содействовать формированию у студентов следующих компетенций: • • владение основными понятиями и методами обработки последовательностей простых переменных; • • владение основными понятиями представления и обработки структур данных производных типов, предназначенных для описания множества однотипных величин, семантически связанных между собой, с применением нотации указателей; • • знание принципов алгоритмической декомпозиции и умение использовать инструментальные средства ее представления на языке С++ (подпрограммы-функции); • • владение представлением абстрактных типов данных и их реализацией. После практического освоения дисциплины студент должен знать: • • способы приведения различных структур данных и алгоритмов их обработки; • • приемы программирования статических и динамических структур данных; • • методы передачи параметров в подпрограммах-функциях (по значению, адресу, ссылке); • • инструментальные средства реализации абстрактных типов данных и их обработки. Студент должен уметь: • • выбирать подходящие структуры данных для решения конкретной задачи и инструментальные средства их обработки; • • использовать инструментальные средства разработки подпрограмм, реализуемые в C++ как функции и классы. Студент должен иметь навыки: • • самостоятельной работы с учебной и справочной литературой; • • освоения и использования приемов программирования для решения базовых вычислительных задач. На конкретных примерах в учебном пособии раскрыты методы и приемы решения задач обработки сложных пользовательских (статических и динамических) структур данных. Подробно рассмотрено решение вычислительных задач,
Предисловие реализованных на языке С++, с использованием нотации указателей, что позволяет обрабатывать большие массивы данных и способствует быстродействию. Учебное пособие состоит из шести глав. В главе 1 рассматриваются базовые типы для описания простых переменных, простейшие конструкции языка, управляющие операторы, программная реализация структурных базовых алгоритмов обработки числовых последовательностей простых переменных. В главе 2 приведены статические одномерные и многомерные массивы и базовые алгоритмы их обработки; динамические переменные и массивы, адресуемые указателями, а также операции адресной арифметики. Рассмотрены алгоритмы и программы обработки динамических массивов, память для которых выделяется по требованию. В главе 3 изложены принципы разработки подпрограмм на языке С++: содержание интерфейса подпрограммы и механизмы передачи параметров по значению, по указателю, по ссылке. Глава 4 посвящена вопросам представления и основным приемам обработки строк с завершающим нулем. В главе 5 приведены определение пользовательского типа — структуры и основные приемы обработки данных этого типа. В главе 6 рассмотрено проектирование приложений, разработанных с применением принципов объектно-ориентированного программирования (ООП). Определены классы, использующие механизмы включения, композиции и наследования. Изложена методика обработки текстовых и бинарных файлов посредством классов файловых потоков C++. Описаны линейные абстрактные типы данных и их представление с помощью классов. Изложение сопровождается примерами приемов программирования на языке С++. Учебное пособие будет полезно при изучении практических основ современного программирования с использованием как процедурного, так и объектноориентированного подхода.
ВВЕДЕНИЕ
Язык программирования С++ — один из наиболее мощных и широко
распространенных языков программирования, для которого существует общедоступный международный стандарт языка С++, не защищенный правом
собственности. Он объединяет в себе процедурные возможности языка С,
принципы ООП, представленного классами, и обобщенное программирование, поддерживаемое шаблонами.
При описании методов создания и использования многомерных массивов
и приемов их обработки используется подход, основанный на указателях и
динамических переменных. Массивы, структуры и указатели — три составных
типа С++. Стратегия указателей позволяет выделять неименованные области
памяти необходимого объема во время выполнения программы, доступ к которой осуществляется через указатели. Для их создания существует специальная
операция С++, возвращающая указатель на выделенную по запросу область.
Применение указателей способствует эффективной реализации передачи
и возвращения структурных переменных при вызове функции. Альтернативный способ передачи аргумента — использование ссылочных переменных.
Конструкции языка в учебном пособии определены с помощью нотации,
предложенной Дж. Бэкусом и П. Науром. Форма Бэкуса — Наура (БНФ) —
форма метаязыка, используемая для описания синтаксиса языков программирования и широко применяемая в справочных системах компиляторов.
Нотация БНФ использует зарезервированные метасимволы, определяемые понятия, символы алфавита языка или терминальные символы:
< > — угловые скобки обозначают определяемые понятия;
::= — читать «определяется как»;
| — читать «или»;
[ ] — заключенная в квадратные скобки синтаксическая конструкция
может отсутствовать;
{ } — фигурные скобки обозначают повторение.
Каждое правило языка в метаязыке имеет следующий вид:
<Определяемое понятие> ::= серия альтернатив разделенных «|».
Альтернатива может содержать как определяемые понятия, так и терминальные символы.
Глава 1. ОСНОВНЫЕ ПОНЯТИЯ C++. АЛГОРИТМЫ ОБРАБОТКИ ПРОСТЫХ ПОСЛЕДОВАТЕЛЬНОСТЕЙ В данной главе рассматриваются базовые типы для описания простых переменных, простейшие конструкции языка, управляющие операторы, принципы структурного программирования и программная реализация структурных алгоритмов обработки последовательностей простых переменных. 1.1. Типы данных и переменные. Структура программы на языке С++. Линейные алгоритмы Алфавит языка C++ состоит из букв латинского алфавита (прописных и строчных), специальных символов и цифр. Лексемы языка — минимальные семантически значимые конструкции языка: ключевые слова, имена объектов. Внутри лексем разделители не допускаются. Имена переменных (идентификаторы) должны начинаться с буквы или символа подчеркивания. Регистры букв различаются. Ключевые слова не могут быть идентификаторами. Любые данные в алгоритмических языках характеризуются своими типами. Типы — специальные конструкции языка, которые рассматриваются компилятором как образцы для создания других элементов программы (переменных, констант и функций). Тип определяет формат внутреннего представления объекта данного типа, т. е. число смежных байтов памяти. Из этого вытекает ограничение на множество допустимых значений и множество допустимых операций. Типы данных подразделяют на базовые (фундаментальные) и пользовательские (составные, производные) типы, определяемые пользователем. Базовые типы определены в языке и предназначены для описания простых скалярных переменных. В языке C++ доопределены следующие базовые типы данных для описания числовых символьных и логических переменных, которым соответствуют ключевые слова: char, int, float, double, void. Тип char предназначен для описания символьных переменных, int – для представления целочисленных переменных, типы float и double – для представления чисел с плавающей точкой одинарной и двойной точности. Тип void служит для описания переменной, не имеющей значений, т. е. для
1.1. Типы данных и переменные. Структура программы на языке С++...
определения обобщенного указателя или функции, не имеющей значения.
К этим типам в С++ добавляются логический тип bool и расширенный
символьный тип wchar_t.
На основе стандартных типов, определенных в языке, создают описания
производных типов, предназначенных для описания множества величин, семантически связанных между собой (массивов, структур, функций, классов,
указателей ссылки).
Все объекты программы должны быть объявлены до их использования
и поименованы. Описание состоит из спецификатора типа и следующего за
ним списка переменных, имеющих этот тип. Каждое описание заканчивается
точкой с запятой. Описание переменных:
<тип> <список идентификаторов переменных>;
где <тип> — допустимый (простой или производный) тип данных; <список
переменных> — идентификаторы переменных одного типа.
Переменные можно инициализировать. Переменная — зарезервированная физическая область памяти из некоторого числа байтов. Число байтов
для внутреннего представления, диапазон их значений и множество допустимых операций определяются типом. У этой области есть свой адрес —
указатель на эту область памяти. Число байтов памяти, отведенных для хранения переменной, определяется ее типом. В эту область можно записать
значение, прочитать и изменить значение. С этой областью памяти связано
имя (идентификатор).
Например: int i, j, n, m; float x, z, d;
Основные характеристики переменных: тип, имя, значение, адрес, область памяти. Тип определяет число байтов памяти, допустистимые операции,
внутреннее представление.
Число байтов памяти, выделяемых компилятором под переменные,
определяется функцией sizeof (<тип>), возвращающей значение, равное
число байтов памяти.
Программа на языке С++ представляет собой набор определений отдельных функций, описаний, директив препроцессора. Каждая программа обязательно должна включать в себя единственную функцию с именем main() —
главную функцию, которая выполняется первой.
Связь между функциями осуществляется через параметры и возвращаемые функциями значения. Каждая функция имеет следующий вид:
<определение функции>::=<заголовок> <тело функции>
<заголовок>::=<тип возвращаемого значения <имя функции>
[(<список параметров>)])
<тело функции–блок>::={[<описания переменных>][<операторы>]}
Директивы препроцессора начинаются со знака #, их основное назначение — подключение заголовочных файлов: # include <имя файла>.
Шаблон файла программы:
<директивы>
[<описания>]
Глава 1. Основные понятия С++. Алгоритмы обработки простых последовательностей
[<прототипы функций>]
<главная функция>
[<описание подпрограмм-функций>]
Функции можно подразделить на два класса: возвращающие значение и
не возвращающие значение (void ). Тип функции void соответствует процедурам в Pascal или Delphi. Если тип функции не void, то в теле функции
необходим оператор return, возвращающий значение. Функция может не
иметь списка передаваемых параметров и не возвращать значение.
Структура простейшей программы без подпрограмм. Такая программа представляет собой главную функцию, в которой есть объявление переменных и
программный код.
Шаблон определения главной функции без параметров и не возвращающей значение:
void main() {
[объявления переменных] [операторы]}
Как следует из описания, главная функция может быть пустой:
void main() {}
Это заглушка, используемая при тестировании созданного проекта в среде.
Программа с объявлениями переменных:
void main() {
float x1, x2, a, b; int i,j,n;
}
Область действия переменных — часть программы, в которой переменные
могут быть использованы (доступны, видимы) и определяются местом и способом их описания. Переменные, объявленные внутри функции, называют
локальными (автоматическими), область их видимости — функцией, в которой они описаны. Переменные, объявленные вне всех функций, называют
глобальными, область их действия — все файлы программы.
Арифметические операции и выражения. Допустимые арифметические
операции для числовых переменных следующие: бинарные арифметические
операции (+, –, *, /), унарная операция (–, минус) и стандартные функции.
При делении ( / ) целых чисел дробная часть отбрасывается. Операция деления
по модулю (%) возвращает остаток от деления целых чисел и применяется
только к целым переменным.
Арифметические операции имеют приоритеты, перечисленные в порядке
уменьшения:
«–» — унарный минус;
«*», «/», «%» — (мультипликативные) — умножение, деление, остаток
от деления целых;
«+» — (аддитивные) — сложение, вычитание.
Операции увеличения «++» и уменьшения «– –» применяются в циклах
и будут рассмотрены далее.
1.1. Типы данных и переменные. Структура программы на языке С++... Выражения представляют собой правила получения новых значений. Выражения состоят из операндов (констант, переменных, стандартных функций), объединенных знаками операций и скобками в соответствии со своим приоритетом. Элементы, из которых сконструировано выражение, характеризуются своим значением и принадлежат к какому-либо типу данных. Частный случай выражения — одиночный элемент, т. е. константа, переменная или обращение к функции. Тип значения выражения определяется типом операндов и видом примененных к ним операций. Правило использования операций с операндами разных типов: при вычислении более короткие типы преобразуются в более длинные, т. е. можно сказать, что тип выражения определяется наиболее точным (или более высоким) типом входящих в него переменных. Функцию можно рассматривать как простую переменную и использовать по месту вызова, учитывая ее тип. Арифметические выражения — это константы, переменные и функции, объединенные знаками арифметических операций. Переменные, входящие в выражение, должны получить свое значение до их использования в выражении. Операция присваивания. Полученные при вычислении выражений значения должны сохраняться в области памяти и использоваться в дальнейших вычислениях. Для этой цели служит операция присваивания: <L-значение>=<R-значение>; где <L-значение> — должно ссылаться на объект, который может принимать значения, т. е. это ссылка на некоторую область памяти; <R-значение> — любое выражение, имеющее значение. В упрощенной форме с практической точки зрения операция присваивания может быть записана так: <переменная>=<выражение>; Вычисляется выражение, его значение записывается в область памяти, на которую ссылается <L-значение>. Старое значение этой области стирается. В область памяти константы ничего записать нельзя, поэтому она не является L-значением. Переменная является <L-значением>. В программе C++ операции присваивания являются выражениями, поэтому можно использовать многократное присваивание: с=f=b. Переменная может получить значение как в результате присваивания, так и заданием при вводе с клавиатуры или файла. Ввод и вывод переменных. Ввод и вывод в C++ поддерживается двумя системами: первая унаследована от языка C, вторая осуществляется с помощью потоков объектно-ориентированной библиотеки C++. В консольном режиме ввод данных осуществляется с клавиатуры, а вывод данных — на экран. Ввод и вывод в системе, унаследованной от языка C, осуществляется с помощью библиотечных функций стандартной библиотеки ввода/вывода. Для использования функции из стандартной библиотеки к программе необходимо подключить заголовочный файл stdio.h: #include <stdio.h> Форматированные ввод и вывод осуществляются функциями scanf_s() и printf(). Эти две функции: scanf_s()(для ввода) и printf()(для
Глава 1. Основные понятия С++. Алгоритмы обработки простых последовательностей вывода) выполняют преобразование числовых величин в символьное представление и обратно. Прототипы функций scanf_s()и printf(): printf(<форматная – управляющая строка>,<список аргументов>); Вызовом функции реализуется вывод аргументов на консоль в соответствии с форматами, определенными в управляющей строке. Управляющая строка состоит из спецификаторов форматов в соответствии с типом выводимого аргумента. Число аргументов должно соответствовать списку форматов. Управляющая строка содержит два типа объектов: обычные символы, копируемые в выходной поток, и спецификации преобразований, вызываемые преобразование и печать очередного аргумента. Спецификация преобразования начинается с символа « % » и заканчивается символом преобразования: % <символ преобразования>. Основные спецификации преобразований для вывода чисел: • • f — аргумент, рассматриваемый как действительная переменная типа float, преобразуется в десятичное число с плавающей точкой; • • lf — аргумент, рассматриваемый как действительная переменная типа double; • • d — аргумент, рассматриваемый как целая переменная типа int, преобразуется к десятичному числу; • • s — спецификация преобразования для вывода символов и строк; аргумент должен быть указателем на массив символов, который достаточен для принятия строки и добавляемого в конце символа \0; аргумент преобразуется в строку; • • c — спецификация преобразования для вывода символов, аргумент — отдельный символ; • • p — аргумент, рассматриваемый как указатель, преобразуется в адрес. Примеры: int k, i; float x; printf (“ввод x:\n”); //вывод текста // Вывод переменных int k, i; float x; printf (“\n i=%d k=%d x=%f\n”, i, k, x); Форматный ввод–функция scanf_s() является аналогом printf(): scanf_s (<управляющая строка>, <список аргументов>); Вызовом функции реализуется чтение данных, вводимых с клавиатуры. Результаты помещаются в аргументы, которые интерпретируются в соответствии с форматом, указанным в управляющей строке. Управляющая строка содержит спецификации преобразования, применяемые для интерпретации входных последовательностей. Символ преобразования определяет интерпретацию поля ввода: % <спецификатор>. Каждый аргумент — указатель на переменную типа, указанного в спецификации преобразования. Число аргументов должно соответствовать числу спецификаций. Аргументы — адреса переменных.