Книжная полка Сохранить
Размер шрифта:
А
А
А
|  Шрифт:
Arial
Times
|  Интервал:
Стандартный
Средний
Большой
|  Цвет сайта:
Ц
Ц
Ц
Ц
Ц

Структуры данных в C++

Покупка
Артикул: 804303.01.99
Доступ онлайн
1 100 ₽
В корзину
Рассмотрены методики, идиомы и приемы решения задач обработки динамических структур данных на языке С++. Подробно описаны вычислительные алгоритмы, реализованные с использованием нотации указателей. Приведены краткие теоретические сведения и примеры приложений по изучаемому материалу. Изложена методика выполнения лабораторных работ по рассматриваемым темам, которая используется авторами в процессе проведения практических занятий в МГТУ им. Н.Э. Баумана. Для студентов, обучающихся по направлениям подготовки «Программная инженерия» и «Информатика и вычислительная техника».
Русакова, З. Н. Структуры данных в C++ : учебное пособие / З. Н. Русакова, И. В. Рудаков. - Москва : МГТУ им. Баумана, 2020. - 158 с. - ISBN 978-5-7038-5256-9. - Текст : электронный. - URL: https://znanium.com/catalog/product/2013678 (дата обращения: 19.11.2026). – Режим доступа: по подписке.
Фрагмент текстового слоя документа размещен для индексирующих роботов
З.Н. Русакова, И.В. Рудаков
Структуры данных в С++ 
Учебное пособие
Федеральное государственное бюджетное 
образовательное учреждение высшего образования 
«Московский государственный технический университет имени Н.Э. Баумана 
(национальный исследовательский университет)»


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 (<управляющая строка>, <список аргументов>); 
Вызовом функции реализуется чтение данных, вводимых с клавиатуры. 
Результаты помещаются в аргументы, которые интерпретируются в соответствии с форматом, указанным в управляющей строке. Управляющая строка 
содержит спецификации преобразования, применяемые для интерпретации 
входных последовательностей. Символ преобразования определяет интерпретацию поля ввода: % <спецификатор>. Каждый аргумент — указатель 
на переменную типа, указанного в спецификации преобразования. Число 
аргументов должно соответствовать числу спецификаций. Аргументы —
адреса переменных. 


Доступ онлайн
1 100 ₽
В корзину