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

З.Н. Русакова, И.В. Рудаков

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

Учебное пособие

Федеральное государственное бюджетное  

образовательное учреждение высшего образования  

«Московский государственный технический университет имени Н.Э. Баумана  

(национальный исследовательский университет)»

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 (<управляющая строка>, <список аргументов>); 

Вызовом функции реализуется чтение данных, вводимых с клавиатуры. 

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