Структуры и алгоритмы компьютерной обработки данных

Структуры и алгоритмы компьютерной обработки
данных

2-е издание, исправленное

Сундукова Т.О.
Ваныкина Г.В.

Национальный Открытый Университет “ИНТУИТ”
2016

2

Структуры и алгоритмы компьютерной обработки данных/ Т.О. Сундукова , Г.В. Ваныкина - М.:
Национальный Открытый Университет “ИНТУИТ”, 2016

Комплекс лекций с упражнениями для обучения моделированию задач на базе основных структур
данных, алгоритмизации и программированию в среде MS Visual Studio 2010. Каждая тема содержит
лекционный материал, примеры программных кодов, задания для аудиторной и самостоятельной
работы.
Комплекс лекций с упражнениями для обучения программированию на языке С++, ориентированный
на работу в среде MS Visual Studio 2010. Каждая тема имеет следующую структуру: название темы,
цель, ключевые слова, теоретическая часть (необходимый для выполнения работы теоретический
материал, который отражает основные положения лекции по соответствующей теме), примеры
программных кодов в среде MS Visual Studio 2010, комплекс задач для аудиторной и
самостоятельной работы (задачи представлены в порядке возрастания сложности).

(c) ООО “ИНТУИТ.РУ”, 2011-2016
(c) Сундукова Т.О., Ваныкина Г.В., 2011-2016

3

Предисловие

Язык программирования С++ был разработан датским ученым Бьёрном Страуструпом
в начале 90-х годов, первоначально как объектно-ориентированное расширение языка
С. В настоящее время язык C++ является одним из наиболее мощных и широко
распространенных языков программирования. Язык характеризуется своей
универсальностью, он успешно применяется для решения разнообразных задач
прикладного и системного программирования с использованием различных парадигм
программирования – процедурной, объектно-ориентированной, параметрической.

Предлагаемый курс представляет собой учебно-методический материал, основным
содержанием которого является лекционно-практические тематические разделы,
которые следуют в порядке, соответствующем последовательности изучения структур
и алгоритмов компьютерной обработки данных. В качестве программной реализации
выбран язык С++ и использована среда MS Visual Studio 2010. Представленный в курсе
набор лекций и упражнений покрывает основные синтаксические и семантические
аспекты языка С++ в объеме вузовских программ по структурам и алгоритмам
компьютерной обработки данных для специальностей 351500 Математическое
обеспечение и администрирование информационных систем. Отдельные разделы могут
быть использованы при обучении программированию студентов специальности 030100
Информатика и направлений подготовки 540200 Физико-математическое образование
(профиль 540203 Информатика), 511900 Информационные технологии.

Данный курс или его разделы могут использоваться для изучения основ
программирования на базе языка С++ и в рамках других направлений/специальностей
высшего профессионального образования, а также использоваться студентами и
преподавателями средних профессиональных и средних общеобразовательных
учреждений. Оно может быть полезным и при самостоятельном изучении способов
организации структур и алгоритмов их обработки на языке С++.

Лекционный и практический материал опирается на сформированные ранее базовые
знания обучающихся по основам алгоритмизации на языке С++. Курс акцентирует
внимание на знакомстве со структурированными типами данных языка С++, более
глубокое изучение приемов и алгоритмов их обработки. В пособии продолжается
реализация идеи процедурной парадигмы программирования, так как обучение знанию
базовых алгоритмов обработки структурированных данных и построение на их основе
решения различных классов задач способствует формированию определенного стиля
мышления и культуры. Формируется база для перехода к изучению альтернативных
парадигм современного программирования.

В состав курса вошли лекции и соответствующие им упражнения, охватывающие
следующие основные разделы.

Типы данных, перегрузка функций, рекурсия
Указатели
Символьные данные и строки
Массивы
Структуры и объединения

4

Файлы
Распределение памяти. Динамические массивы
Динамические структуры данных
Трудоемкость алгоритмов и рекурсия
Алгоритмы поиска, хеширования и сжатия данных
Алгоритмы сортировки массивов. Алгоритмы на графах

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

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

Пособие написано на основе курса лекций и лабораторно-практических занятий по
дисциплинам “Программирование” и “Структуры и алгоритмы компьютерной
обработки данных” со студентами факультета математики, физики и информатики
ТГПУ им. Л.Н. Толстого. Для базовой подготовки студентов, обучающихся на основе
материалов пособия, необходимо знание основ программирования, умение работать с
массивами, строками и реализовывать метод процедурной абстракции средствами
языка С++.

Авторы выражают благодарность техническому консультанту по среде MS Visual
Studio 2010 ассистенту кафедры информатики и МОИ ТГПУ им. Л.Н.Толстого Титову
Андрею Валерьевичу.

5

Типы данных в языке С++

В лекции рассматриваются понятие типов данных в языках программирования,
приводится классификация типов данных в С++, излагаются особенности
представления базовых типов и операций над ними, рекомендации и правила
выполнения операции преобразования базовых типов в С++.

Цель лекции: изучить классификацию типов и их внутреннее представление в языке С
++, научиться работать со стандартными и пользовательскими типами.

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

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

Тип данных – это множество допустимых значений, которые может принимать тот или
иной объект, а также множество допустимых операций, которые применимы к нему. В
современном понимании тип также зависит от внутреннего представления
информации.

Таким образом, данные различных типов хранятся и обрабатываются по-разному. Тип
данных определяет:

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

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

Классификация типов данных в С++

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

Объектно-ориентированные языки программирования позволяют определять типы
класса.

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

6

Тип данных определяет размер памяти, выделяемой под переменную данного типа при
ее создании. Язык программирования C++ поддерживает следующие типы данных
(рис. 1.1).

Базовые типы. Базовые типы предопределены стандартом языка, указываются
зарезервированными ключевыми словами и характеризуются одним значением.
Их не надо определять и их нельзя разложить на более простые составляющие без
потери сущности данных. Базовые типы объектов создают основу для построения
более сложных типов.
Производные типы. Производные типы задаются пользователем, и переменные
этих типов создаются как с использованием базовых типов, так и типов классов.
Типы класса. Экземпляры этих типов называются объектами.

Рис. 1.1.  Типы данных в языке С++

Существует четыре спецификатора типа данных, уточняющих внутреннее
представление и диапазон базовых типов:

short (короткий)
длина

long (длинный)

signed (знаковый)
знак (модификатор)

unsigned (беззнаковый)

Рассмотрим более подробно базовые типы данных.

Целочисленный (целый) тип данных (тип int)

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

7

Границы диапазона целых чисел, которые можно хранить в переменных типа int,
зависят от конкретного компьютера, компилятора и операционной системы (от
реализации). Для 16-разрядного процессора под него отводится 2 байта, для 32разрядного – 4 байта.

Для внутреннего представления знаковых целых чисел характерно определение знака
по старшему биту (0 – для положительных, 1 – для отрицательных). Поэтому число 0
во внутреннем представлении относится к положительным значениям. Следовательно,
наблюдается асимметрия границ целых промежутков.

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

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

short int – занимает 2 байта, следовательно, имеет диапазон от –32 768 до +32
767;

int – занимает 4 байта, следовательно, имеет диапазон от –2 147 483 648 до +2 147
483 647;

long int – занимает 4 байта, следовательно, имеет диапазон от –2 147 483 648 до
+2 147 483 647;

long long int – занимает 8 байтов, следовательно, имеет диапазон от –9 223 372
036 854 775 808 до +9 223 372 036 854 775 807.

Модификаторы signed и unsigned также влияют на множество допустимых значений,
которые может принимать объект:

unsigned short int – занимает 2 байта, следовательно, имеет диапазон от 0 до 65
535;

unsigned int – занимает 4 байта, следовательно, имеет диапазон от 0 до 4 294 967
295;

unsigned long int – занимает 4 байта, следовательно, имеет диапазон от 0 до 4
294 967 295;

unsigned long long int – занимает 8 байтов, следовательно, имеет диапазон от 0
до 18 446 744 073 709 551 615.

Например:

unsigned int b; 
signed int a; 
int c; 
unsigned d; 

8

signed f;

Приведем несколько правил, касающихся записи целочисленных значений в исходном
тексте программ.

Нельзя пользоваться десятичной точкой. Значения 26 и 26.0 одинаковы, но 26.0 не
является значением типа int.
Нельзя пользоваться запятыми в качестве разделителей тысяч. Например, число
23,897 следует записывать как 23897.
Целые значения не должны начинаться с незначащего нуля. Он применяется для
обозначения восьмеричных или шестнадцатеричных чисел, так что компилятор
будет рассматривать значение 011 как число 9 в восьмеричной системе счисления.

На практике рекомендуется использовать основной целый тип, то есть тип int. Данные
основного целого типа практически всегда обрабатываются быстрее, чем данные
других целых типов. Короткий тип short подойдет для хранения больших массивов
чисел с целью экономии памяти при условии, что значения элементов не выходят за
предельные границы для этих типов. Длинные типы необходимы в ситуации, когда не
достаточно типа int.

Вещественный (данные с плавающей точкой) тип данных (типы
float и double)

Для хранения вещественных чисел применяются типы данных float (с одинарной
точностью) и double (с двойной точностью). Смысл знаков “+” и “-” для вещественных
типов совпадает с целыми. Последние незначащие нули справа от десятичной точки
игнорируются. Поэтому варианты записи +523.5, 523.5 и 523.500 представляют одно и
то же значение.

Для представления вещественных чисел используются два формата:

с фиксированной точкой

[знак][целая часть].[дробная часть]

Например: –8.13; .168 (аналогично 0.168); 183. (аналогично 183.0).
с плавающей точкой (экспоненциальной форме)

мантисса Е/е порядок

Например: 5.235e+02 (5.235 x 102 = 523.5); –3.4Е-03 (–3.4 x 10-03 = – 0.0034)

В большинстве случаев используется тип double, он обеспечивает более высокую
точность, чем тип float. Максимальную точность и наибольший диапазон чисел
достигается с помощью типа long double.

Величина с модификатором типа float занимает 4 байта. Из них 1 бит отводится для

9

знака, 8 бит для избыточной экспоненты и 23 бита для мантиссы. Отметим, что
старший бит мантиссы всегда равен 1, поэтому он не заполняется, в связи с этим
диапазон модулей значений переменной с плавающей точкой приблизительно равен от
3.14E–38 до 3.14E+38.

Величина типа double занимает 8 байтов в памяти. Ее формат аналогичен формату

float. Биты памяти распределяются следующим образом: 1 бит для знака, 11 бит для
экспоненты и 52 бита для мантиссы. С учетом опущенного старшего бита мантиссы
диапазон модулей значений переменной с двойной точностью равен от 1.7E–308 до
1.7E+308.

Величина типа long double аналогична типу double.

Например:

float a, b; 
double x, y; 
long double z;

Символьный тип данных (тип char)

В стандарте C++ нет типа данных, который можно было бы считать действительно
символьным. Для представления символьной информации есть два типа данных,
пригодных для этой цели, – это типы char и wchar_t.

Переменная типа char рассчитана на хранение только одного символа (например,
буквы или пробела). В памяти компьютера символы хранятся в виде целых чисел.
Соответствие между символами и их кодами определяется таблицей кодировки,
которая зависит от компьютера и операционной системы. Почти во всех таблицах
кодировки есть прописные и строчные буквы латинского алфавита, цифры 0, …, 9, и
некоторые специальные символы. Самой распространенной таблицей кодировки
является таблица символов ASCII ( American Standard Code for Information Interchange –
Американский стандартный код для обмена информацией).

Так как в памяти компьютера символы хранятся в виде целых чисел, то тип char на
самом деле является подмножеством типа int.

Под величину символьного типа отводится 1 байт.

Тип char может использоваться со спецификаторами signed и unsigned. В данных
типа signed char можно хранить значения в диапазоне от –128 до 127. При
использовании типа unsigned char значения могут находиться в диапазоне от 0 до 255.
Для кодировки используется код ASCII. Символы с кодами от 0 до 31 относятся к
служебным и имеют самостоятельное значение только в операторах ввода-вывода.

Величины типа char также применяются для хранения чисел из указанных диапазонов.

Тип wchar_t предназначен для работы с набором символов, для кодировки которых

10