close

Вход

Забыли?

вход по аккаунту

?

1618.Динамические структуры данных

код для вставкиСкачать
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Министерство образования и науки Российской Федерации
Орский гуманитарно-технологический институт (филиал)
Государственное образовательное учреждение
высшего профессионального образования
«Оренбургский государственный университет»
М. А. Кузниченко
ДИНАМИЧЕСКИЕ СТРУКТУРЫ ДАННЫХ
Утверждено редакционно-издательским советом ОГТИ
в качестве учебного пособия
Орск 2011
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
УДК 681.3
ББК 32.973-018
К91
Научный редактор
Янё В. С., кандидат экономических наук, доцент,
заведующий кафедрой программного обеспечения
Орского гуманитарно-технологического института
Рецензенты:
Михайличенко И. Н., кандидат физико-математических наук,
доцент кафедры общих и профессиональных дисциплин;
Чурсин В. Б., кандидат физико-математических наук,
доцент кафедры общих и профессиональных дисциплин
(ФГОУ ВПО «Самарский государственный университет
путей сообщения» в г. Орске)
К91 Кузниченко, М. А. Динамические структуры данных :
учебное пособие / М. А. Кузниченко. – Орск : Издательство ОГТИ,
2011. – 102 с. – ISBN 978-5-8424-0551-0.
В пособии кратко изложены основные теоретические положения о динамических
структурах данных, примеры программной реализации на алгоритмическом языке С++,
даны рекомендации по выполнению лабораторных работ. В нем представлены требования к
выполнению курсовой работы по дисциплине «Структуры и алгоритмы обработки данных»,
даются указания по структуре и содержанию пояснительной записки, приводятся
рекомендации по выполнению и оформлению отдельных частей курсовой работы.
Учебное пособие предназначено для студентов, обучающихся по программам высшего профессионального образования по специальности 220400 при изучении дисциплины
«Структуры и алгоритмы обработки данных». Пособие предназначено также для бакалавриата по направлениям подготовки: 231000.62 «Программная инженерия», профиль подготовки «Разработка программно-информационных систем»; 230100.62 «Информатика и
вычислительная техника», профиль подготовки «Программное обеспечение средств вычислительной техники и автоматизированных систем».
ISBN 978-5-8424-0551-0
© Кузниченко М. А., 2011
© Издательство ОГТИ, 2011
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
СОДЕРЖАНИЕ
ВВЕДЕНИЕ .................................................................................................................. 5
1. КЛАССИФИКАЦИЯ ДИНАМИЧЕСКИХ СТРУКТУР ДАННЫХ ................... 6
2. ОРГАНИЗАЦИЯ ВВОДА – ВЫВОДА В ЯЗЫКЕ C++ ..................................... 10
2.1. Иерархия классов ввода – вывода в С++ ...................................................... 10
2.2. Форматирование данных ................................................................................ 16
2.3. Манипуляторы................................................................................................. 17
2.4. Методы обмена с потоками ........................................................................... 18
2.5. Файлы в С++ .................................................................................................... 19
2.6. Задания на лабораторную работу 1 «Файловые потоки» ........................... 30
3. УКАЗАТЕЛИ ......................................................................................................... 35
3.1. Инициализация указателей ............................................................................ 35
3.2. Задания на лабораторную работу 2 «Указатели» ........................................ 39
4. ДИНАМИЧЕСКИЙ СПИСОК, ЕГО РЕАЛИЗАЦИЯ И ПРИМЕНЕНИЕ
В C++ ......................................................................................................................... 41
4.1. Описание динамического списка .................................................................. 41
4.2. Операции над списком ................................................................................... 43
4.3. Задания на лабораторную работу 3 «Динамический список» ................... 47
5. СТЕК ....................................................................................................................... 52
5.1 Операции обработки стека .............................................................................. 52
5.2. Проверка баланса скобок ............................................................................... 54
5.3. Постфиксная запись выражений ................................................................... 55
5.4. Метод стека с приоритетами ......................................................................... 57
5.5. Задания на лабораторную работу 4 «Стек».................................................. 59
6. ДРУГИЕ ВИДЫ ДИНАМИЧЕСКИХ СПИСКОВ ............................................. 61
6.1. Очередь ............................................................................................................ 61
6.2. Циклический список ....................................................................................... 63
6.3. Двунаправленный список............................................................................... 64
6.4. Дек .................................................................................................................... 66
6.5. Задания на лабораторную работу 5 «Другие виды списков» ..................... 68
7. РЕКУРСИЯ ............................................................................................................ 71
7.1. Организация рекурсивных функций ............................................................. 71
7.2. Задания на лабораторную работу 6 «Рекурсия» .......................................... 73
8. ДЕРЕВЬЯ................................................................................................................ 77
8.1. Описание и обработка древовидной структуры .......................................... 77
8.2. Обход дерева ................................................................................................... 83
8.3. Сбалансированные деревья............................................................................ 84
8.4. Оптимальные деревья поиска ........................................................................ 87
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
8.5. Задания на лабораторную работу 7 «Бинарные деревья поиска» .............. 89
9. ПЕРЕЧЕНЬ ЭКЗАМЕНАЦИОННЫХ ВОПРОСОВ 1 ЧАСТИ КУРСА
«СТРУКТУРЫ И АЛГОРИТМЫ ОБРАБОТКИ ДАННЫХ» ............................... 93
10. КУРСОВОЕ ПРОЕКТИРОВАНИЕ ................................................................... 95
10.1 Общие требования ......................................................................................... 95
10.2. Этапы выполнения курсовой работы .......................................................... 96
БИБЛИОГРАФИЧЕСКИЙ СПИСОК ...................................................................... 98
ПРИЛОЖЕНИЕ А Образец оформления титульного листа курсового проекта99
ПРИЛОЖЕНИЕ Б Образец оформления бланка технического задания на
курсовой проект
100
ПРИЛОЖЕНИЕ В Правила присвоения классификационного кода ................ 101
ПРИЛОЖЕНИЕ Г. Образец оформления содержания ....................................... 102
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
ВВЕДЕНИЕ
Обработка информации на персональных компьютерах требует,
чтобы ее структура была определена и точно представлена в программе. Информация, представленная в формализованном виде, пригодном для автоматизированной обработки, является данными.
При разработке приложений, оперирующих с большим количеством входных данных, возникает вопрос об их хранении во время
выполнения программы. Массив, как составной тип данных, решает
вопрос хранения данных, однако очевидно, что он не лишен недостатков. Главным из них, несомненно, является его фиксированный
размер. Это свойство не поддается изменению даже у динамически
созданных массивов, что довольно часто заставляет программистов,
использующих исключительно их, выделять память «с запасом».
Данную проблему решает другой тип хранения данных – связанный динамический список. Компоненты добавляются и удаляются
во время выполнения программы, и их количество зависит исключительно от размера доступной памяти. Однако, за это преимущество
приходится расплачиваться недостатком: если в случае с массивом
мы в любой момент получаем доступ к любому компоненту, то в случае со списком в один момент времени нам доступны максимум 3
компонента (первый, последний и текущий).
На базе динамического списка строятся и другие динамические
структуры данных. Такие, как стек, очередь, дек, дерево и другие. В
зависимости от ограничений и особенностей структуры данных определяется и программная реализация динамического списка.
Память под динамические переменные отводится не из сегмента
данных, как это происходит для статических переменных, а из области динамической памяти, называемой кучей или Heap-областью. Ее
размер зависит от конфигурации компьютера.
5
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
1. КЛАССИФИКАЦИЯ ДИНАМИЧЕСКИХ СТРУКТУР ДАННЫХ
Структуры данных являются неотъемлемой частью любой программы. При разработке программы необходимо определить множество данных, описывающих конкретную задачу, и составить алгоритм
решения.
В зависимости от назначения программы данные могут иметь
разный уровень сложности или организованности, начиная с простых
типов (числа и символы) и заканчивая файлами и системами файлов
достаточно сложной структуры.
Изучение структур данных, правильный их выбор в зависимости
от выполняемых операций, размера требуемой для структур памяти,
частоты использования при выполнении программы позволяет повысить эффективность разрабатываемых программ, уменьшить время и
стоимость программной разработки.
Знание теории структур данных и методов представления данных на логическом и машинном уровнях необходимо для изучения
таких курсов, как «Операционные системы», «Базы данных», «Теория
вычислительных структур».
Данные – это значения или наборы значений, характеризующиеся заданным типом. Тип данных – важная характеристика, которая дает информацию компилятору языка о
 диапазоне возможных значений,
 размере физической памяти,
 наборе функций, применимых к данным типа.
Данные могут быть организованы многими различными способами. Логическая или математическая модель организации данных
называется структурой данных.
Выбор структуры данных зависит от двух обстоятельств:
 структура должна отражать физические связи данных в реальном мире;
6
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
 структура должна быть достаточно проста, чтобы можно было
эффективно обрабатывать данные.
Структура данных, рассматриваемая без учета ее представления
в машинной памяти, называется абстрактной, или логической.
Логическая структура данных – это схема представления, модель соответствующей структуры. Физическая структура данных –
это схема представления или хранения структуры в памяти персонального компьютера.
Например, логическая структура двумерного массива – это прямоугольная матрица, каждый элемент которой характеризуется индексами соответствующей строки и столбца. Физическая структура
того же массива – это последовательность ячеек памяти, реализованная в языке Си через механизм указателей.
Под структурой данных в общем случае понимают множество
элементов данных и множество связей между ними. Такое определение охватывает всевозможные подходы к структуризации данных.
Структуры данных и алгоритмы являются основными составными частями создаваемых программ. По определению Вирта:
Алгоритмы + структуры данных = ПРОГРАММЫ
Часто, говоря о той или иной структуре данных, имеют в виду ее
логическое представление.
Все объекты, используемые в программах, можно разделить на
две большие группы: статические и динамические.
Для статических переменных характерным является то, что память под них выделяется на этапе компиляции программы из небольшого по размеру сегмента данных, а количество и взаимное расположение элементов не изменяется в процессе выполнения программы.
К статическим структурам относятся переменные базовых типов
(числовые, символьные, указатели), составных типов (массивы,
структуры).
7
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Динамические же переменные и объекты занимают динамическую память. Динамическая память (куча, Heap-область) – это часть
оперативной памяти компьютера за исключением памяти, занимаемой самой программой, сегмента данных, стека, а также памяти под
резидентные программы. Это память значительно большего размера,
ее объем зависит от конфигурации компьютера. Выделение памяти
под динамические переменные происходит на этапе выполнения программы, а их количество и взаимное расположение может динамически изменяться. Это выгодно отличает динамические переменные и
наборы данных от статических.
С определенной степенью допустимости можно отнести к динамическим структурам файлы, хотя они занимают не оперативную память, а внешнюю.
Динамические структуры в оперативной памяти можно классифицировать на три большие группы: данные линейной структуры,
данные циклической структуры, данные разветвляющейся структуры.
На основе данных линейной структуры строятся такие полезные
структуры данных, как стеки, очереди, деки. Циклические списки могут быть организованы как на базе односвязного, так и на базе двунаправленного списков, а к разветвленным структурам относятся деревья и графы. Классификация динамических структур данных приведена на рисунке 1.
В программной реализации динамических структур данных используется понятие указателя как абстракции машинного адреса.
Остановимся подробнее на определении переменных указательного
типа, а также рассмотрим операции над указателями в языке С++.
8
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Динамические
структуры
данных
Линейная
структура
Линейный
односвязный
список
Стек
Циклическая
структура
Линейный двунаправленный
список
Циклический
односвязный
список
Циклический
двунаправленный
список
Разветвленная структура
Деревья
Графы
Бинарные
деревья
Дек
Ветвистые
деревья
Очередь
Рис. 1. Классификация динамических структур данных
9
Файлы
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
2. ОРГАНИЗАЦИЯ ВВОДА – ВЫВОДА В ЯЗЫКЕ C++
2.1. Иерархия классов ввода – вывода в С++
Поток – это абстрактное понятие, относящееся к любому переносу данных от источника к приемнику.
Потоки C++, в отличие от функций ввода/вывода в стиле классического языка С (printf(), scanf() и др.), обеспечивают надежную
работу как со стандартными, так и с определенными пользователем
типами данных, а также единообразный и понятный синтаксис.
Чтение данных из потока называется извлечением, вывод в поток – помещением, или включением. Поток определяется как последовательность байтов и не зависит от конкретного устройства, с которым производится обмен (оперативная память, файл на диске, клавиатура или принтер). Обмен с потоком для увеличения скорости передачи данных производится, как правило, через специальную область оперативной памяти – буфер. Фактическая передача данных
выполняется при выводе после заполнения буфера, а при вводе – если
буфер исчерпан.
По направлению обмена потоки можно разделить на входные
(данные вводятся в память), выходные (данные выводятся из памяти)
и двунаправленные (допускающие как извлечение, так и включение).
По виду устройств, с которыми работает поток, можно разделить потоки на стандартные, файловые и строковые.
Стандартные потоки предназначены для передачи данных от
клавиатуры и на экран дисплея, файловые потоки – для обмена информацией с файлами на внешних носителях данных (например, на
магнитном диске), а строковые потоки – для работы с массивами
символов в оперативной памяти.
В языке С++ библиотека ввода/вывода является библиотекой
классов, а не функций. Для поддержки потоков библиотека C++ содержит иерархию классов, построенную на основе двух базовых
классов – ios и streambuf. Класс ios содержит общие для ввода и вы10
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
вода поля и методы, класс streambuf обеспечивает буферизацию потоков и их взаимодействие с физическими устройствами. От этих
классов наследуется класс istream для входных потоков и ostream –
для выходных. Два последних класса являются базовыми для класса
iostream, реализующего двунаправленные потоки. Ниже в иерархии
классов располагаются файловые и строковые потоки. В таблице 1
перечислены часто используемые классы потоков, а на рисунке 2
представлена иерархическая схема их наследования.
Таблица 1
Список классов ввода – вывода в С++
Название класса
Описание
ios
istream
ostream
iostream
istringstream
базовый класс потоков
класс входных потоков
класс выходных потоков
класс двунаправленных потоков
класс входных
строковых потоков
класс выходных
строковых потоков
класс двунаправленных
строковых потоков
класс входных
файловых потоков
класс выходных
файловых потоков
класс двунаправленных
файловых потоков
ostringrstream
stringstream
ifstream
ofstream
fstream
ios
istream
11
Название
заголовочного файла
<ios.h>
<iostream.h>
<iostream.h>
<iostream.h>
<sstream.h>
<sstream.h>
<sstream.h>
<fstream.h>
<fstream.h>
<fstream.h>
streambuf
ostream
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
iostream
istringstream
ostringstream
fstream
stringstream
Рис. 2. Иерархия классов ввода – вывода
Родительский класс ios ссылается на класс streambuf, который
управляет буферизацией ввода – вывода, поэтому всем производным
классам он доступен для использования.
Подключение к С++ – программе файлов <fstream.h> или
<sstream.h> автоматически подключает и файл <iostream>, так как он
является для них родительским. Направление стрелок на схеме отражает политику разрешения области видимости для объектов порожденных классов свойств и методов обработки данных родительских
классов.
Основным преимуществом потоков по сравнению с функциями
ввода/вывода, унаследованными из библиотеки С, является контроль
типов, а также расширяемость, то есть возможность работать с типами, определенными пользователем. Для этого требуется переопределить операции потоков.
Рассмотрим стандартные потоки ввода – вывода, которые позволяют осуществлять эти процессы для стандартных устройств ввода
– вывода, к которым относятся клавиатура и экран монитора.
Работа с файловыми потоками будет рассмотрена в данном учебном пособии позже.
12
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Заголовочный файл <iostream.h> содержит, кроме описания
классов для ввода – вывода, четыре предопределенных объекта, перечисленных в таблице 2.
Таблица 2
Предопределенные стандартные объекты
Объект
cin
Класс
istream
Описание
Связывается с клавиатурой
(стандартным буферизованным вводом)
cout
ostream
сеrr
ostream
Связывается с экраном
(стандартным буферизованным выводом)
Связывается с экраном
(стандартным небуферизованным выводом),
куда направляются сообщения об ошибках
Эти объекты создаются при включении в программу заголовочного файла <iostream.h>, при этом становятся доступными связанные
с ними средства ввода – вывода. Имена этих объектов можно переназначить на другие файлы или символьные буферы.
В классах istream и ostream операции извлечения из потока >> и
помещения в поток << определены путем перегрузки операций сдвига.
Операции извлечения и чтения в качестве результата своего выполнения формируют ссылку на объект типа istream для извлечения и
ссылку на ostream – для чтения. Это позволяет формировать цепочки
операций. Вывод при этом выполняется слева направо. Величины при
вводе должны разделяться пробелами, знаками табуляции или перевода строки. Извлечение прекращается, если очередной символ оказался недопустимым.
Рассмотрим, как обрабатываются с помощью этих операций
данные различных типов.
Числовые значения можно вводить в десятичной или шестнадцатеричной системе счисления (с префиксом 0х) со знаком или без
знака. Вещественные числа представляются в форме с фиксированной точкой или с порядком.
13
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Поскольку ввод буферизован, помещение в буфер ввода происходит после нажатия клавиши <Enter>, после чего из буфера выполняется операция извлечения из потока. Это дает возможность исправлять введенные символы до того, как нажата клавиша Enter.
При вводе строк извлечение происходит до ближайшего пробела
(вместо него в строку заносится нуль-символ).
Значения указателей выводятся в шестнадцатеричной системе
счисления. Под любую величину при выводе отводится столько позиций, сколько требуется для ее представления. Чтобы отделить одну
величину от другой, используются пробелы.
Общий синтаксис ввода с клавиатуры значений переменных с
помощью объекта cin имеет вид:
cin >> переменная1 >> переменная2 >> … >> переменнаяN;
Элементом ввода в этом случае может быть только имя переменной или элемента массива.
Для ввода одной или нескольких переменных с клавиатуры
необходимо использовать объект cin совместно с операцией >>.
Например, если нужно ввести три переменных с клавиатуры, то следует их сначала описать, а затем перечислить в объекте cin, разделяя
их операцией >>.
int a;
float b;
char name[25];
cin >> a >> b >> name;
Общий синтаксис вывода на экран значений переменных с помощью объекта cout имеет вид:
cout << элемент1 << элемент2 << … << элементN;
Элементами вывода могут быть:
 константа числового или строкового типа (выводится значение константы без изменения);
 escape – последовательности (‘\t’ – <Tab>; ‘\n’ - <Enter>);
14
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
 переменная любого базового типа (выводится значение переменной);
 выражение с участием констант, переменных и функций базовых типов (выражение вычисляется, и выводится его значение на
экран);
 обращение к функции, возвращающей значение базового типа;
 манипулятор (выполняет форматирование выходного потока).
Например, для вывода на экран значений трех введенных ранее
переменных можно их перечислить в объекте cout:
cout << a << b << name;
Но такой вывод будет неприемлимым, так как все значения
«сцепятся» в одну строку. Поэтому при выводе сопровождайте выводимые значения пояснительным текстом, заключенным в кавычки:
cout << “a=” <<a<<” b=” << b << “name=” << name <<”\n”;
cout << “a/b=” << a/b << “\t sin(” << b << ”)=” << sin(b)<< “\n”;
Такой прием применения пояснительного текста следует использовать и при вводе значений так, чтобы пользователю было понятно, что нужно ввести с клавиатуры. Например:
a) Запрос имени пользователя:
cout << “ Введите Ваше имя: ”;
cin >> name;
cout << “ Здравствуйте, “ << name << “!”;
б) Запрос сторон треугольника:
float a, b,c;
cout << “ Введите три стороны треугольника: \n”;
cout << “ a=”; cin >> a;
cout << “ b=”; cin >> b;
cout << “ c=”; cin >> c.
Если формат вывода, используемый по умолчанию, не устраивает программиста, он может скорректировать его с помощью методов
классов ввода – вывода, флагов форматирования и так называемых
манипуляторов.
15
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
2.2. Форматирование данных
В потоковых классах форматирование выполняется тремя способами с помощью:
 флагов,
 манипуляторов,
 форматирующих методов.
Значения флагов приведены в таблице 3.
Для управления флагами используются методы ios:flags (флаги)
или cout.setf (флаги). Если используется одновременно несколько
флагов, то для их объединения используется операция «или» (|).
int a=80;
float b=-1.154,c=2;
cout<<a<<b<<c;
cout.setf(ios::showpoint | ios::fixed | ios::showpos);
cout<<a<<” “<<b<<”\t“<<c<<”\n”.
В первом случае будут выведены на экран все значения друг за
другом так, что не ясно будет, где заканчивается одно значение, а где
начинается другое. Такой вывод неудобен для восприятия. Затем
включаются некоторые флаги, значения которых можно посмотреть в
таблице 3, и внешний вид выводимых значений меняется.
Чтобы установить требуемую точность вывода вещественных
чисел с дробной частью, можно использовать манипулятор precision,
описанный ниже.
cout.precision(3);
В этом случае вещественные значения будут выводиться с точностью до тысячных. При этом будет выполняться округление значений по правилам математики.
Таблица 3
Флаги форматирования
16
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Флаг
Положение Умолчание
skipws
0х0001
left
0х0002
right
Описание действия
при установленном флаге
+
При извлечении пробельные
символы игнорируются
Выравнивание по левому краю поля
0х0004
+
Выравнивание по правому краю поля
dec
0х0010
+
Десятичная система счисления
oct
0х0020
Восьмеричная система счисления
hex
0х0040
Шестнадцатеричная система счисления
showbase
0х0080
showpoint
0х0100
Выводится основание системы счисления
(Ох для шестнадцатеричных чисел
и 0 для восьмеричных)
При выводе вещественных чисел печатать десятичную точку и дробную часть
uppercase
0х0200
При выводе использовать
символы верхнего регистра
showpos
0х0400
scientific
0х0800
Печатать знак при выводе
положительных чисел
Печатать вещественные числа
в форме мантиссы с порядком
fixed
0х1000
Печатать вещественные числа в форме
с фиксированной точкой (точность
определяется манипулятором precision)
2.3. Манипуляторы
Манипуляторами называются функции, которые можно включать
в цепочку операций помещения в поток для форматирования данных.
Манипуляторы делятся на простые (не требующие аргументов)
и параметризованные (с аргументами).
К простым манипуляторам относятся: dec, oct, hex – установка
системы счисления; endl – при выводе включает в поток символ новой строки (Enter).
Параметризованные манипуляторы:
17
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
setiosflags(флаги) – устанавливает флаги,
resetiosflags(флаги) – сбрасывает флаги,
setfill(int) – устанавливает символ – заполнитель с кодом, равным значению параметра,
precision(int) – устанавливает максимальное число цифр в дробной части для вещественных чисел,
setw(int) – устанавливает максимальную ширину поля вывода
для следующего параметра.
Форматирующие методы вызываются как функции – члены
классов, то есть с использованием операции точка:
объект.функция(параметры)
Например, установка точности вещественных чисел:
cout.precision(2);
позволит видеть значения чисел с дробной частью с точностью
до сотых.
2.4. Методы обмена с потоками
В потоковых классах наряду с операциями извлечения и включения в поток определены методы для неформатированного чтения и
записи в поток.
Функции чтения, определенные в классе istream:
get(с) – возвращает ссылку на поток, из которого выполняется
чтение, и записывает извлеченный символ в переменную с.
get (s, n,lim=’\n’) – считывает n-1 символов или пока не встретится символ lim и копирует их в строку s. В конец строки вместо lim
записывается признак конца строки. Символ lim остается в потоке.
getline (s, n,lim=’\n’) – аналогична get, но копирует в s символ lim.
ignor (n=1, lim=EOF) – считывает и пропускает n символов или
пока не встретится символ lim, возвращает ссылку на текущий поток.
putback (с) – помещает в поток символ с, который становится текущим при извлечении из потока.
18
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Указанные функции являются буферизированными функциями.
В классе ostreаm определена функция
put(c) – выводит в поток символ с и возвращает ссылку на поток.
Функция getch() – функция небуферизированного ввода, то есть
символы, введенные с клавиатуры, сразу обрабатываются программой, не отображаясь на экране.
getche() – аналогичная функция с отображением символа на
экране.
2.5. Файлы в С++
Основное отличие внешней памяти компьютера от оперативной
памяти – возможность сохранения информации при отключении питания компьютера. Информация во внешней памяти сохраняется в виде
файлов – именованных объектов, доступ к которым поддерживает
(обеспечивает) операционная система компьютера [10]. Поддержка
операционной системы состоит в том, что в ней имеются средства:
создания файлов;
уничтожения файлов;
поиска файлов на внешнем носителе информации (на диске);
чтения и записи данных из файлов и в файлы;
открытия файлов;
закрытия файлов;
позиционирования файлов.
Библиотека ввода – вывода Си++ является библиотекой классов и
включает средства для работы с последовательными файлами. Логически последовательный файл можно представить как именованную цепочку (поток) байтов, имеющую начало и конец. Последовательный
файл отличается от файлов с другой организацией тем простым свойством, что чтение (или запись) из файла (в файл) ведутся байт за байтом от начала к концу. В каждый момент позиции в файле, откуда выполняется чтение и куда производится запись, определяются значениями указателей позиций записи и чтения файла. Позиционирование
19
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
указателей записи и чтения (то есть установка на нужные байты) выполняется либо автоматически, либо за счет явного управления их положением. В стандартной библиотеке ввода – вывода Си++ имеются
соответствующие средства.
Рассматривая взаимосвязь файлов с потоками ввода-вывода,
нужно отметить существование следующих процедур:
 создание файла;
 создание потока;
 открытие файла;
 «присоединение» файла к потоку;
 обмены с файлом с помощью потока;
 «отсоединение» потока от файла;
 закрытие файла;
 уничтожение файла.
Все перечисленные действия могут быть выполнены с помощью
средств библиотеки классов ввода – вывода языка Си++. Однако существует несколько альтернативных вариантов их выполнения. Кратко остановимся на наиболее простых и удобных механизмах реализации указанных действий [10].
Потоки для работы с файлами создаются как объекты следующих классов:
ofstream – выходной файловый поток (для записи данных в
файл);
if stream – входной файловый поток (для чтения данных из файла);
fstream – двунаправленный файловый поток (для чтения и для
записи данных).
Чтобы использовать эти классы, в текст программы необходимо
включить дополнительный заголовочный файл:
#include <fstream.h>
20
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
После этого в программе можно определять конкретные файловые потоки соответствующих типов (объекты классов ofstream,
ifstream, fstream), например, таким образом:
ofstream outFile; // Определяется выходной файловый поток,
ifstream inFile; // Определяется входной файловый поток,
fstream ioFile; // Определяется файловый поток для ввода и вывода.
Создание файлового потока (объекта соответствующего класса)
связывает имя потока с выделяемым для него буфером и инициализирует переменные состояния потока. Так как перечисленные классы
файловых потоков наследуют свойства класса ios, то и переменные состояния каждого файлового потока наследуются из этого базового
класса. Так как файловые классы являются производными от классов
оstream (класс ofstream), istream (класс ifstream), stream (класс fstream),
то они поддерживают форматированный и бесформатный обмен
с файлами подобно обмену данными со страндартными потоками ввода – вывода. Однако прежде чем выполнить обмен, необходимо открыть соответствующий файл и связать его с файловым потоком.
Открытие файла в самом общем смысле означает процедуру, информирующую систему о тех действиях, которые предполагается выполнять с файлом. Существуют функции стандартной библиотеки
языка Си для открытия файлов fopen(), open(). Но работая с файловыми потоками библиотеки ввода – вывода языка Си++, удобнее
пользоваться компонентными функциями соответствующих классов.
Создав файловый поток, можно «присоединить» его к конкретному файлу с помощью компонентной функции ореn(). Функция open()
унаследована каждым из файловых классов ofstream, ifstream, fstream
от класса fstreambase. С ее помощью можно не только открыть файл,
но и связать его с уже определенным потоком.
Формат функции:
void open(const char *fileName, int mode, int protection);
21
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Первый параметр – filename – имя уже существующего или создаваемого заново файла. Это строка, определяющая полное или сокращенное имя файла в формате, регламентированном операционной
системой. Второй параметр – mode (режим) – дизъюнкция флагов,
определяющих режим работы с открываемым файлом (например,
только запись или только чтение). Флаги определены следующим образом:
ios::in – открыть только для чтения,
ios::out – открыть только для записи,
ios::app – открыть для дозаписи файла.
Третий параметр – protection (защита) – определяет защиту и
достаточно редко используется. Точнее, он устанавливается по умолчанию и умалчиваемое значение обычно устраивает программиста.
Итак, открытие и присоединение файла к конкретному файловому потоку обеспечивается таким вызовом функции open ():
имя__потока.open (имя_файла, режим, защита);
Для файлов типа ifstream и ofstream режим открытия можно не
указывать, так как направление обмена данными в этих случаях очевидно. Для потоков класса fstream второй аргумент функции open()
должен быть задан явно, так как по умолчанию неясно, в каком
направлении предполагается выполнять обмен с потоком. Например,
свяжем ранее объявленные файловые переменные с конкретными
файлами на диске.
outFile.open(“negative.dat”);
inFile.open(“c:\\Data\\digits.dat”);
ioFile.open(“positive.dat”, ios::out).
В данном примере открыто два выходных и один входной потоки. Если при открытии не указывается полный путь к файлу, то
транслятор языка С++ будет выполнять поиск файла в текущей директории. Если файл находится где-то в другом месте, то необходимо
указать полный путь к нему, как это указано для файла digits.dat.
22
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Таким образом, файлы negative.dat и positive.dat после удачного
выполнения функции open() будут созданы, а затем открыты для вывода (записи) данных в текстовом режиме обмена и присоединены к
потокам outFile и ioFile. Теперь к этим потокам может применяться
операция включения << как к стандартному выходному потоку cout.
Поток inFile класса ifstream в нашем примере присоединяется
функцией open() к файлу с именем c:\Data\digits.dat. Этот файл открывается для чтения из него данных в текстовом режиме. Если файла с этим именем не существует, то попытка вызвать функцию
inFile.open() приведет к ошибке.
Для проверки удачности завершения функции ореn() используется перегруженная операция отрицания «!». Если унарная операция
«!» применяется к потоку, то результат будет ненулевой при наличии
ошибок. Если ошибок не было, то выражение !имя_потока имеет нулевое значение. Таким образом, можно проверить результат выполнения функции open():
if (!inFile)
{ cout <<"Ошибка при открытии файла \n"; getch(); exit(1);
}
Такую проверку имеет смысл делать в том случае, если файл открывается для чтения.
Аналогичную проверку на существование искомого файла можно выполнить с помощью специальной функции fail(), являющейся
членом класса файловых потоков fstream. Данная функция вызывается для файловой переменной, которая уже связана с конкретным файлом на диске и возвращает ненулевое значение, если при открытии
указанного файла произошла ошибка, и ноль – в противном случае.
Поэтому предыдущий фрагмент проверки установленной связи с
файлом можно записать в следующем виде:
if (inFile.fail())
{ cout <<"Ошибка при открытии файла \n"; getch(); exit(1);
}
В классах ifstream, ofstream, fstream определены конструкторы,
позволяющие по-иному выполнять создание и открытие файлов. При
23
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
объявлении файлового потока он может быть открыт сразу следующим образом:
имя_класса имя_файлового_потока(char *FileName, int mode);
Данная строка создает поток, присоединяет его к файлу с заданным именем Filename, а при необходимости предварительно создает
файл с таким именем. Режим mode указывается только для двунаправленного потока.
Например, файловый поток может быть объявлен и проинициализирован, минуя функции open, следующим образом:
ofstrem outFile(“negative.dat”);
Все файловые классы унаследовали от базовых классов функцию close(), позволяющую очистить буфер потока, отсоединить поток
от файла и закрыть файл. Функцию close() необходимо явно вызывать
при изменении режимов работы с файловым потоком. Автоматически
эта функция вызывается только при завершении программы.
В качестве иллюстрации основных особенностей работы с файлами рассмотрим несколько программ.
Пусть в файле digits.dat хранится произвольное количество целых чисел. Такой файл может быть создан в редакторе среды языка
С++ или в Блокноте. Числа в файле могут быть разделены пробелами,
табуляцией или клавишей <Enter>. Этот файл может иметь вид, изображенный на рисунке 3. Невидимый указатель файла при открытии
его для чтения устанавливается на первом элементе файла.
28 -2 45 56
9 12 -1
10
-8
41
39
-5
Рис. 3. Примерный вид числового файла digits.dat
Файловый поток, связанный с этим файлом, открыт для чтения.
Задача заключается в следующем: необходимо считать все данные из
24
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
файла, вывести их на экран в строку. Все отрицательные элементы
переписать в файл negative.dat, связанный с файловым потоком outFile, а все положительные числа переписать в файл positive.dat, связанный с файлом ioFile.
Все файловые потоки открыты и связаны с конкретными файлами во внешней памяти. Теперь необходимо организовать чтение из
одного файла и запись новых значений в два других файла. Так как
работа с файловыми и стандартными потоками ввода – вывода в языке С++ выполняется аналогично, то будем применять операцию >>
чтения из потока для входного файлового потока, а операцию << помещения в поток для выходного файлового потока:
inFile >> x;
outFile << x << “\t”;
Чтобы числа в новом файле не сливались в одну сплошную
строку, необходимо в выходной поток помещать хотя бы один разделитель: пробел, табуляция, Enter.
Прежде чем написать программу, решающую нашу задачу,
необходимо определить условие выхода из цикла обработки файла.
Это можно сделать разными способами. Одним из способов является
использование самой процедуры чтения из файлового потока непосредственно в условии продолжения цикла. Данная операция возвращает некоторое значение, которое будет ненулевым, если операция
чтения прошла успешна, и ноль – если файл закончился и очередного
чтения не произошло.
Если считанное значение отрицательное, то оно помещается в
поток outFile, а если положительное, то в поток ioFile. Когда файл закончится, произойдет выход из цикла, все три файла должны быть закрыты с помощью функции close().
Фрагмент программы будет иметь вид:
int x;
cout << “Содержимое исходного файла:” << endl ;
25
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
while ( inFile >> x ){
cout << x << “\t”;
if (x<0) outFile << x << “\t”;
if (x>0) ioFile << x << “ ”;
}
inFile.close();
outFile.close();
ioFile.close();
….
Условием выхода из цикла обработки файла может быть проверка значения самого файлового потока или использование функции
eof(), которая возвращает true, если достигнут конец файла, и false – в
противном случае. Таким образом, заголовок цикла мог быть следующим:
while ( inFile){
inFile >> x;
…
}
или
while (! inFile.eof())
{
inFile >> x;
…
}
Для чтения вновь созданных файлов имеет смысл определить
специальную функцию, которая в качестве параметра будет получать
имя файла, локально создавать входной файловый поток, читать и
выводить на экран содержимое файла, а по окончании закрывать поток. Определим такую функцию:
void ReadFile (char nameFile[]) {
int a;
ifstream F;
F.open (nameFile) ;
F>>a;
while(F) {
cout << a << “\t”;
26
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
F>>a;
}
}
Чтобы вывести на экран содержимое новых файлов, в программу необходимо включить двойное обращение к данной функции:
cout<< “Файл отрицательных чисел:\n”;
ReadFile (“negative.dat”);
cout<< “Файл положительных чисел:\n”;
ReadFile (“positive.dat”);
Для обработки текстовых файлов, содержащих строковую информацию, можно использовать построчную или посимвольную обработку входного потока в зависимости от решаемой задачи. Опишем
простую символьную переменную ch и строку символов s.
char ch, s[80];
Для чтения текста из файла можно использовать операцию извлечения >>, которая реагирует на каждый обобщенный пробельный
символ или любой разделитель. Другими словами, чтение из файлового потока будет выполняться по словам.
F >> s;
считывает из потока очередное слово и смещается на следующее за
разделителем слово.
Следующий фрагмент программы объявляет и открывает входной файловый поток, выполняет чтение текстового файла по словам и
вычисляет количество слов в файле.
ifstream F (“letter.txt”);
if (F.fail())
{ cout <<"Ошибка при открытии файла \n"; getch(); exit(1);
}
int k=0;
cout << “Текст письма:”;
while (F>>s)
{
cout << s << “ “;
27
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
k++;
}
F.close();
cout << “В данном файле ” << k << “ слов.”;
Если слова в исходном файле разделены более, чем одним пробелом или текст разделен на абзацы, то подобное чтение будет искажать исходный файл и выводить слова на экран, разделяя их пробелами. Это обстоятельство иногда мешает. Поэтому используются
другие средства для распознания пробельных или любых других значимых символов.
Функция поток.getline(s, lenString) выполняет чтение строки в
переменную s длиной lenString символов. Следующий фрагмент читает файл построчно и выводит на экран в исходном виде.
while (1) // Неограниченный цикл
{
inFile.getline(s, lenString);
if (inFile.eof()) break;
cout << s << endl;
}
Если требуется посимвольная обработка файла, то используется
функция поток.get(ch), которая определена в классе istream и унаследована классом ifstream. Функция get считывает из потока очередной
символ и помещает его в переменную ch. Например, следует считать
файл до первой встретившейся точки. Если же файл вообще не содержит точки, то выход из цикла произойдет, если будет достигнут
конец файла. Это предусмотрено с помощью логического оператора
if внутри цикла.
while (1) {
inFile.get(ch);
if (inFile.eof() || ch==’.’) break;
cout << ch ;
}
28
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
При посимвольной обработке файла могут понадобиться функции библиотеки ctype.h, поэтому ее следует подключить в заголовочной части программы:
#include <ctype.h>
Некоторые полезные функции этой библиотеки приведены в
таблице 4. Воспользуйтесь ими при выполнении лабораторной работы по обработке файлов. В данной работе каждый вариант имеет два
задания: первое задание посвящено обработке числовых файлов, а
второе задание – обработке текстовой информации.
Таблица 4
Функции обработки символов библиотеки ctype.h
Синтаксис
функции
int isalpha(char)
int isupper(char)
int islower(char)
int isdigit(char)
int isdigit(char)
int isspace(char)
int iscntrl(char)
int ispunct(char)
int isalnum(char)
Описание
Возвращает не ноль (истина), если символ-параметр является
буквой английского алфавита 'a'..'z' 'A'..'Z'
Возвращает не ноль (истина), если символ-параметр является
буквой английского алфавита в верхнем регистре 'A'..'Z'
Возвращает не ноль (истина), если символ-параметр является
буквой английского алфавита в нижнем регистре 'a'..'z'
Возвращает не ноль (истина),
если символ-параметр является цифрой '0'..'9'
Возвращает не ноль (истина), если символ-параметр
является цифрой '0'..'9' 'a'..'f' 'A'..'F'
Возвращает не ноль (истина), если символ-параметр является
пробелом, табуляцией или переходом на новую строку.
Возвращает не ноль (истина), если символ-параметр является
управляющим символом в диапазоне ASCII 0..31 и 127
Возвращает не ноль (истина), если символ-параметр
является знаком пунктуации
Возвращает не ноль (истина), если символ-параметр
является цифрой или буквой английского алфавита
29
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
2.6. Задания на лабораторную работу 1 «Файловые потоки»
При выполнении данной лабораторной работы пользуйтесь манипуляторами для форматирования выходного потока.
Вариант 1
1. В файле salary.dat хранится заработная плата рабочего за каждый месяц года. Вычислить и вывести на экран среднемесячную зарплату и номера месяцев, в которые рабочий получал максимальную
зарплату.
2. Дан текстовый файл с текстом телеграммы. Прочитать и вывести содержимое файла. Вычислить стоимость телеграммы, если цена 1 слова запрашивается с клавиатуры. Дописать файл сообщением о
стоимости телеграммы.
Вариант 2
1. Программным путем создать числовой файл из простых чисел
первой сотни. Разместить по 5 чисел в строке. Прочесть созданный
файл и вывести его содержимое на экран, используя функцию.
2. Дан текстовый файл. Вывести содержимое файла. Определить
и вывести отдельно самую длинную и самую короткую строку.
Вариант 3
1. В файле data.dat хранятся фамилии и годы рождения участников юношеских соревнований. Найти средний возраст участников,
вывести фамилии тех участников, возраст которых наибольший.
2. Дан текстовый файл письма клиенту фирмы, состоящий из нескольких строк. Вместо имени указаны символы “###”. Запросить
имя клиента с клавиатуры. Создать новый файл, заменив в исходном
файле спецсимволы на имя клиента.
30
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Вариант 4
1. Сначала создать, а затем прочесть и вывести на экран содержимое файла, в котором хранятся двузначные числа, в записи которых есть цифра N или число кратно N. Посчитать количество таких
чисел.
2. Дан непустой текстовый файл. Вывести на экран содержимое
файла. Вывести отдельно на экран слова, начинающиеся на заданную
букву и определить их количество.
Вариант 5
1. Числовой файл создать программным путем следующим образом:
1
22
333
…
999999999
Вывести содержимое файла на экран, используя функцию.
2. Дан текстовый файл, состоящий из нескольких строк. Вывести
содержимое файла на экран. Посчитать количество строк и значащих
символов в файле. Дополнить файл информацией об этом.
Вариант 6
1. Файл произвольной длины заполнить случайными числами
программным путем. Вывести содержимое файла по 10 чисел в строке. Вычислить минимальное, максимальное и среднее значение файла. Использовать двунаправленный поток.
2. Текстовый файл содержит ответы по одному в каждой строке.
Организовать диалог с пользователем, который задает вопрос с клавиатуры и получает очередной ответ из файла. По окончании файла
организовать его просмотр сначала.
31
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Вариант 7
1. В файле хранится числовая последовательность из вещественных чисел. Вывести на экран содержимое файла, а так же сообщение
о количестве чисел и о том, является ли данная последовательность
возрастающей.
2. В текстовом файле в столбик записаны слова или числа. Вывести на экран содержимое файла, указав рядом с каждым словом,
является ли оно палиндромом, то есть читается в прямом и обратном
порядке одинаково.
Вариант 8
1. Создать файл случайным образом из диапазона от –20 до 20 до
первого встретившегося 0. Вывести содержимое файла на экран с сообщением о количестве элементов файла. Используя функцию дважды, вычислить количество чисел, кратных 2 и 3 одновременно, а так
же количество чисел, кратных 5.
2. Дан текстовый файл, в котором слова разделены 1 и более
пробелами. Вывести на экран содержимое файла, удалив лишние
пробелы между словами.
Вариант 9
1. В числовом файле хранятся тройки положительных чисел –
стороны треугольника. В новый файл вывести содержимое этого
файла, поместив рядом с каждой тройкой площадь треугольника, если треугольник с такими длинами сторон можно построить, иначе –
сообщение.
2. Дан непустой текстовый файл. Вывести его содержимое до
первой точки. Посчитать количество значащих символов (отличных
от пробелов, табуляции, Enter).
Вариант 10
32
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
1. Программным путем создать файл, состоящий из трехзначных
чисел (по 10 в строке), в записи которых все цифры различны.
2. В файле записан столбик чисел. Вывести на экран содержимое
файла, записав рядом с каждым значением сообщение о том, является
ли оно правильной записью целого десятичного числа или нет.
Вариант 11
1. Программно создать файл из чисел первой сотни, значения которых кратны 2 и 3 одновременно. Вывести содержимое файла на
экран по 10 чисел в строке.
2. Дан непустой текстовый файл. Вывести его содержимое на
экран, удвоив каждый пробел (вместо одного пробела выводить два).
Вариант 12
1. Программным путем создать файл следующего вида:
1
12
123
1234
…
123456789
Доработайте программу так, чтобы количество строк запрашивалось у пользователя с клавиатуры.
2. Даны два текстовых файла. Вывести их содержимое на экран.
Сравнить файлы на совпадение и вывести результат проверки.
Вариант 13
1. Даны два числовых файла одинаковой длины, значения в которых упорядочены по возрастанию. Создать третий файл из чисел
первых двух файлов так, чтобы упорядоченность элементов не
нарушилась. Массивы и сортировку не использовать.
33
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
2. Дан текстовый файл. Вывести его содержимое на экран. Рядом
с каждой строкой вывести сообщение о том, является ли она правильной записью шестнадцатеричного числа или нет.
Вариант 14
1. Случайным образом промоделировать бросание монеты N раз,
и результаты записать в файл. Вычислить процент выпаданий «орла»
(1) и «решки» (0). Дополнить файл информацией об этом.
2. Дан текстовый файл. Вывести его содержимое в другой файл,
заменив каждое вхождение пробела на символ нижнего подчеркивания. Вывести оба файла на экран, используя функцию.
Вариант 15
1. Случайным образом создать файл из 20 положительных целых
чисел из диапазона от 0 до 50. Определить, сколько четных, нечетных
и нулевых значений. Вывести на экран содержимое файла в строку и
результаты подсчета.
2. Дан текстовый файл. Вывести его на экран, определив, сколько слов файла начинаются на букву «а». Учесть регистр буквы.
34
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
3. УКАЗАТЕЛИ
3.1. Инициализация указателей
Когда компилятор обрабатывает оператор определения переменной, например,
int i=10;
он выделяет память в соответствии с типом (int) и инициализирует ее указанным значением (10). Все обращения, в программе к переменной по ее имени i заменяются компилятором на адрес области
памяти, в которой хранится значение переменной. Программист может определить собственные переменные для хранения адресов областей памяти. Такие переменные называются указателями.
Итак, указатели предназначены для хранения адресов областей
памяти.
В C++ различают три вида указателей – указатели на объект, на
функцию и на void, отличающиеся свойствами и набором допустимых операций. Указатель не является самостоятельным типом, он
всегда связан с каким-либо другим конкретным типом.
Указатель на функцию содержит адрес в сегменте кода, по которому располагается исполняемый код функции, то есть адрес, по которому передается управление при вызове функции. Указатели на функции используются для косвенного вызова функции (не через ее имя, а
через обращение к переменной, хранящей ее адрес), а также для передачи имени функции в другую функцию в качестве параметра. Указатель функции имеет тип «указатель функции, возвращающей значение
заданного типа и имеющей аргументы заданного типа»:
<тип> (*имя) ( список_типов_аргументов );
Например, объявление:
int (*fun) (double, double);
задает указатель с именем fun на функцию, возвращающую значение
типа int и имеющую два аргумента типа double.
35
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Указатель на объект содержит адрес области памяти, в которой
хранятся данные определенного типа (основного или составного).
Простейшее объявление указателя на объект (в дальнейшем называемого просто указателем) имеет вид:
<тип> *<имя1>, *<имя2>, …;
где тип может быть любым, кроме ссылки.
Указатель на объект содержит адрес области памяти, в которой
хранятся данные определенного типа (основного или составного).
Простейшее объявление указателя на объект (в дальнейшем называемого просто указателем) имеет вид:
<тип> *<имя1>, *<имя2>, …;
где тип может быть любым, кроме ссылки.
Размер указателя зависит от модели памяти. Можно определить
указатель на указатель и т. д.
Указатель на void применяется в тех случаях, когда конкретный
тип объекта, адрес которого требуется хранить, не определен (например, если в одной и той же переменной в разные моменты времени
требуется хранить адреса объектов различных типов).
Указателю на void можно присвоить значение указателя любого
типа, а также сравнивать его с любыми указателями, но перед выполнением каких-либо действий с областью памяти, на которую он ссылается, требуется преобразовать его к конкретному типу явным образом.
Указатели чаще всего используют при работе с динамической
памятью. Это свободная память, в которой можно во время выполнения программы выделять место в соответствии с потребностями. Доступ к выделенным участкам динамической памяти, называемым динамическими переменными, производится только через указатели.
Время жизни динамических переменных – от точки создания до конца программы или до явного освобождения памяти. В C++ используется два способа работы с динамической памятью. Первый использует семейство функций malloc и достался в наследство от С, второй
использует операции new и delete.
36
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
При определении указателя надо стремиться выполнить его
инициализацию, то есть присвоение начального значения.
Непреднамеренное использование неинициализированных указателей – распространенный источник ошибок в программах. Инициализатор записывается после имени указателя либо в круглых скобках, либо после знака равенства.
Способы инициализации указателя:
1. Присваивание указателю адреса существующего объекта:
a) с помощью операции получения адреса &:
int a = 5;
// целая переменная
int *р= &а; //в указатель записывается адрес а
int *р (&а); // то же самое другим способом;
b) с помощью значения другого инициализированного указателя:
int *r = р;
c) с помощью имени массива или функции, которые трактуются
как адрес:
int b[10];
// массив
int *t= b;
// присваивание адреса начала массива
void f(int a ){ /* ... */ } // определение функции
void (*pf)(int);
// указатель на функцию
pf = f;
// присваивание адреса функции.
2. Присваивание указателю адреса области памяти в явном виде:
char *vp = (char *)0xB800;
здесь 0хB800 – шестнадцатеричная константа, (char *) – операция приведения типа: константа преобразуется к типу «указатель на char».
3. Присваивание пустого значения:
int *s = NULL, *r =0;
В первой переменной используется константа NULL, определенная в некоторых заголовочных файлах С как указатель, равный нулю
0х0000. Рекомендуется использовать просто 0, так как это значение
типа int будет правильно преобразовано стандартными способами в
соответствии с контекстом. Поскольку гарантируется, что объектов с
37
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
нулевым адресом нет, пустой указатель можно использовать для проверки, ссылается указатель на конкретный объект или нет.
4. Выделение участка динамической памяти и присваивание ее
адреса указателю:
• с помощью операции new:
int *n = new int;
//1
int *m = new int (10);
//2
int *q = new int [10];
//3
• с помощью функции mallос:
int *u = (int *)malloc(sizeof(int));
//4
В операторе 1 операция new выполняет выделение достаточного
для размещения величины типа int участка динамической памяти и
записывает адрес начала этого участка в переменную n. Память под
саму переменную n (размера, достаточного для размещения указателя) выделяется на этапе компиляции.
В операторе 2, кроме описанных выше действий, производится
инициализация выделенной динамической памяти значением 10.
В операторе 3 операция new выполняет выделение памяти под
10 величин типа int (массива из 10 элементов) и записывает адрес
начала этого участка в переменную q, которая может трактоваться
как имя массива. Через имя можно обращаться к любому элементу
массива. Такие массивы называются динамическими.
В операторе 4 делается то же самое, что и в операторе 1, но с помощью функции выделения памяти mаlloс, унаследованной из библиотеки С. В функцию передается один параметр – количество выделяемой памяти в байтах. Конструкция (int*) используется для приведения
типа указателя, возвращаемого функцией, к требуемому типу.
Если память выделить не удалось, функция возвращает 0 или
NULL. Операцию new использовать предпочтительнее.
Освобождение памяти, выделенной с помощью операции new,
должно выполняться с помощью delete, а памяти, выделенной функ38
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
цией mallос, – посредством free. Для того чтобы использовать malloc,
требуется подключить к программе заголовочный файл <malloc.h>.
После освобождения памяти переменная – указатель сохраняется и может инициализироваться повторно.
Пример:
delete n; delete m; delete [] q;
free(u);
Если при удалении динамического массива опустить [], то никакого сообщения об ошибке не выводится, но помечен как свободный
будет только первый элемент массива, а остальные окажутся недоступны для дальнейших операций. Такие ячейки памяти называются
мусором.
3.2. Задания на лабораторную работу 2 «Указатели»
1. Описать три вещественных указателя (р1, р2, р3) и два целочисленных указателя (i1, i2). Указатель р3 обнулить (NULL). Выделить динамическую память под остальные указатели. Проинициализировать участок памяти , на который указывает р1 значением 31.5,
p2 – значением 79.9
2. Участок памяти, на который указывает i1 значением 50. В *i2
записать целую часть от значения, которое хранится по указателю р1.
3. Вывести значение указателей и тех участков памяти, на которые они указывают.
4. Совместите указатели р1 и р3, а затем увеличьте в 3 раза содержимое по указателю р3. Выведите оба указателя и их разыменование на эран.
5. Затем присвойте разыменованной ячейке i1 содержимое разыменованной ячейки i2. Затем замените ячейку по адресу i2 на значение 15. После каждого присваивания выводите значения указателей и
их разыменований.
6. Описать структуру info, изображенную на рисунке 4, и задать
соответствующие значения полей.
fam
year
39
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
L
Smith
1980
Рис. 4. Структура из двух полей fam, year
7. Вывести на экран значение полей. С помощью функции
sizeof() определить и записать в тетрадь длины указателей разных типов: целого, вещественного, структурного. Какой вывод можно сделать о размере памяти?
8. Описать массив указателей R[5] на структуру info. Внесите в
него данные с клавиатуры.
9. Упорядочить массив указателей по алфавиту фамилий любым
способом.
10. Описать функцию вывода данных, используя массив указателей. Вывести массив до и после сортировки, используя данную функцию.
40
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
4. ДИНАМИЧЕСКИЙ СПИСОК,
ЕГО РЕАЛИЗАЦИЯ И ПРИМЕНЕНИЕ В C++
4.1. Описание динамического списка
Динамический список – это динамическая структура данных, в
которой каждый компонент (узел) содержит непосредственно информационную часть и ссылку на следующий компонент.
Количество элементов в списке характеризует размер списка.
Список идентифицируется указателем на первый узел списка, называемый головой списка. Количество элементов в списке называют его
размером.
В программной реализации списка используется указательный
тип данных, а память под каждый узел списка выделяется из кучи
(области динамической памяти) с помощью оператора new. Синтаксис его использования следующий:
указатель = new тип;
Слева от знака присваивания находится переменная указательного типа, а справа указывается тип, на который указывает данный
указатель. При объявлении указатель должен быть связан с какимлибо конкретным типом.
Так как каждый узел динамического списка, кроме информационной части, содержит ссылку на соседний элемент, то структура узла списка состоит, как минимум, из двух полей: информационного и
ссылочного.
Информационная часть узла списка может быть любого базового типа, кроме файлового, или пользовательского типа согласно требованию постановленной задачи.
41
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Head
10
*
20
30
*
40
*
Рис. 5. Линейный односвязный список
Линейный динамический список представляет собой связное
хранение компонентов, проиллюстрированное на рисунке 5.
Таким образом, получаем следующую структуру List, описывающую один узел списка, предназначенного для хранения целых чисел:
struct List {
int data; // информационная часть
List* next; // ссылочная часть
};
Сам же список представляет совокупность его узлов и задается
обычно одной или двумя ссылками – на первый элемент и последний.
Рассмотрим случай, когда список задается только головой, указателем на первый элемент списка.
В программах обработки списка приходится работать, в основном, с указательным на List типом. Поэтому рекомендуется объявить
пользовательский тип, который является указательным на List типом,
и дать ему специальное имя, например, ListPtr. Это можно сделать с
помощью оператора typedef, который позволяет создавать любые
названия пользовательским типам. В разделе глобальных описаний
после объявления структуры List необходимо поместить следующую
строку:
typedef List* ListPtr;
Теперь все указательные переменные, связанные с типом List,
будем объявлять как переменные типа ListPtr.
ListPtr Head; // объявление головы списка
42
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Несложно понять, что значит создать пустой список. Фактически делать ничего не нужно, разве что присвоить ссылке на первый
элемент списка значение NULL.
Head =NULL;
Следует помнить, что обращение к полям структуры узла
выполняется через указатель на узел, а для этого используется
операция косвенного доступа -> в виде:
указатель_на_структуру->поле_структуры
4.2. Операции над списком
Над динамическим списком допустимы следующие операции:
1) добавление нового элемента в список;
2) просмотр содержимого списка;
3) вывод элементов списка в выходной поток;
4) поиск элемента в списке по значению;
5) удаление одного или всех элементов списка, значение которых совпадает с заданным значением;
6) сцепление нескольких списков в один;
7) разделение исходного списка на два, начиная с заданного
элемента.
Добавление нового элемента может выполняться в голову (перед
первым элементом), в хвост (после последнего) или в определенное
место списка.
Рассмотрим функцию добавления insertHead нового элемента со
значением а в голову формального списка h. Прежде всего, нам необходимо создать новый компонент (tmp), выделить под него динамическую память и заполнить его информационную часть значение а.
Так как мы будем помещать его в голову списка, то ссылочная часть
узла будет совмещаться с головой списка, а голова списка изменит
свое значение, то есть будет указывать на этот вновь созданный элемент. Значение головы списка в результате изменится, следовательно,
43
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
этот параметр необходимо передавать по адресу, чтобы сделанные
изменения передались в вызывающую программу.
// Включение в голову списка нового компонента
void insertHead (ListPtr &h, int a)
{
ListPtr tmp= new List;
tmp->data = a;
tmp->next = h;
h = tmp;
}
Реализуем функцию поиска первого вхождения компонента. Искать будем по значению информационного поля. В качестве аргументов, функции поиска передаем сам список h и искомое значение n.
Возвращать функция будет адрес найденного узла или NULL, если
ничего не найдено. Искать начнем с компонента, на который указывает голова h, и, двигаясь вперед, сравнивать имя текущей переменной с искомым. Для этого можно использовать саму переменную h
или вспомогательную переменную tmp, которую предварительно
совместим с головой списка, а затем в теле цикла будем смещать на
следующий компонент следующим образом:
tmp = tmp->next;
Так как в задаче требуется найти только первое вхождение элемента, то условием продолжения цикла будет, во-первых, несовпадение информационной части узла с искомым значением и, во-вторых,
ненулевое значение переменной tmp. Переменная tmp обратится в
NULL, если дойдет до конца списка, так как указатель последнего узла содержит значение NULL.
// Поиск компонента в списке по имени
ListPtr search(ListPtr h, int n)
{
ListPtr tmp=h;
while (tmp != NULL && tmp->data!=n)
44
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
{
tmp = tmp->next;
}
return tmp;
} //search
Условия цикла объединены логическим «И». Таким образом, если нарушится хотя бы одно условие, указанное в while, то произойдет
выход из цикла и функция вернет значение переменной tmp.
Рассмотрим программную реализацию функции вывода на экран
монитора содержимого линейного списка h. Функция в качестве параметра получает голову списка h. С помощью вспомогательной переменной tmp происходит движение по списку, начиная с головы. В
теле цикла содержатся только два действия – вывод на экран информационного поля текущего компонента и смещение на следующий
узел списка.
// Вывод на экран содержимого списка
void showList(ListPtr h)
{
ListPtr tmp=h;
while (tmp != NULL)
{
сout << tmp->data<<”\t”;
tmp = tmp->next;
}
}
В функцию вывода можно добавить подсчет количества компонентов списка, вычисление среднего значения и т.д.
Для удаления компонента необходимо рассмотреть 2 случая.
Первый случай простой: если компонент является первым (то есть на
него указывает голова head), то достаточно лишь переместить ссылку
на первый элемент вперед. В противном случае понадобится рабочая
переменная – узел r, которую можно использовать для движения по
45
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
списку. Двигаться необходимо до тех пор, пока текущий узел не будет тем, который мы собираемся удалить, например значением с. После этого «перепрыгиваем» удаляемый компонент, присваивая ссылочной части предшествующего удаляемому компоненту адрес следующего за удаляемым узлом. Следовательно, необходимо перед
смещением на следующий компонент надо запомнить ссылку на
предыдущий узел во вспомогательной переменной p. После изменения ссылки узел r необходимо удалить с помощью оператора delete.
На рисунке 6 показана схема удаления узла со значениями 20.
p
r
Head
10
20
*
30
*
40
*
Рис. 6. Схема удаления узла
Следующий фрагмент программы иллюстрирует удаление узла
из списка head:
ListPtr r = head, p=NULL;
while (r->data != c)
{
p=r;
r = r->next;
}
p->next = r->next;
delete r;
}
Самостоятельно определите функцию удаления, предусмотрев
также ситуации удаления из головы и из хвоста списка.
46
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
4.3. Задания на лабораторную работу 3
«Динамический список»
Примечание: Для информационной части узла списка следует
описать структуру отдельно. Затем необходимо описать и проинициализировать массив этого типа произвольного размера. Предусмотреть в
программе создание списка из элементов этого массива структур.
Вариант 1
1. Организовать связный список, хранящий фамилии и табельные номера 10 сотрудников отдела.
2. Используя функцию, вывести весь список в столбик, указав
общую численность отдела.
3. Используя функцию, вставить в список нового сотрудника в
список после заданного.
4. Удалить из списка заданного сотрудника (табельный номер
ввести с клавиатуры).
5. Вывести информацию о требуемом сотруднике по его табельному номеру, используя функцию поиска.
Вариант 2
1. Организовать связный список, хранящий 15 целых чисел.
2. Используя функцию, вывести весь список в столбик, а так же
максимальное и минимальное значения.
3. Используя функцию, заменить минимальный элемент на значение 100, а максимальный – на 1000.
4. Удалить из списка узлы с нулевым значением, если такие есть.
Использовать функцию.
5. Вывести сообщение, есть ли в списке заданное значение и каков его порядковый номер.
47
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Вариант 3
1. Организовать два связных списка по m элементов, используя
функцию создания списка с помощью генератора случайных чисел.
2. Вывести оба списка в строку, используя функцию. В функцию
вывода добавить подсчет элементов.
3. В первом списке удалите узлы с нулевым значением, а во втором списке – узлы со значением 1.
4. Слить оба списка в один простым сцеплением. Вывести на
экран.
Вариант 4
1. Организовать связный список L из m элементов, упорядоченный по возрастанию.
2. Используя функцию, вывести список в строку.
3. Определить, есть ли в списке заданное значение. Вывести сообщение об этом.
4. Используя функцию, вставить в список некоторое значение Р,
введенное с клавиатуры, чтобы упорядоченность списка не нарушилась.
5. Перенести в начало одного списка его последний узел. Вывести список.
Вариант 5
1. Организовать связный список L, содержащий 8 названий отделов и количество сотрудников в них.
2. Вывести список в столбик, используя функцию.
3. Используя функцию, определить, упорядочены ли узлы списка
по алфавиту названий отделов.
4. Вывести информацию о заданном отделе, если такой существует.
5. Удалить из списка отдел, в котором нет сотрудников.
Вариант 6
48
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
1. Организовать связный список L, содержащий 8 названий отделов и количество сотрудников в них.
2. Вывести список в столбик.
3. Используя функцию, определить название отдела, в котором
наибольшее количество сотрудников.
4. Удалить из списка отдел по его названию.
Вариант 7
1. Организовать связный список L, содержащий 8 названий отделов и количество сотрудников в них (список упорядочен по алфавиту) Вывести список в столбик.
2. Используя функцию, определить суммарное количество сотрудников всего предприятия и среднюю численность отделов.
3. Вывести информацию о заданном отделе, если такой существует.
4. Вывести информацию об отделах, численность которых
меньше средней по предприятию.
Вариант 8
1. Организовать связный список, хранящий фамилии по алфавиту и оклады 10 сотрудников отдела. Оклад – вещественное число с
двумя знаками после запятой из диапазона от 3000 до 6000.
2. Используя функцию, вывести весь список в столбик, а так же
средний оклад отдела.
3. Используя функцию, вставить в список нового сотрудника в
список так, чтобы не нарушился порядок следования.
4. Удалить из списка заданного сотрудника (фамилию ввести с
клавиатуры).
5. Вывести информацию о требуемом сотруднике.
Вариант 9
1. Организовать связный список, хранящий фамилии и оклады
20 сотрудников отдела.
49
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
2. Используя функцию, вывести весь список в столбик, а также
суммарный оклад отдела.
3. Используя функцию, вставить в список новых N сотрудников
в голову списка. Вывести полученный список.
4. Удалить из списка сотрудника по номеру его следования в
списке.
5. Вывести информацию о требуемом сотруднике.
Вариант 10
1. Организовать связный список, хранящий названия товаров,
цену и их количество.
2. Используя функцию, вывести весь список в столбик, а также
общую сумму товара.
3. Используя функцию, вставить в список новый товар в голову
списка. Вывести список.
4. Удалить из списка информацию о товаре, который закончился.
5. Вывести информацию о требуемом товаре (название вводится
с клавиатуры).
Вариант 11
1. Организовать связный список, хранящий прейскурант цен на
товары.
2. Используя функцию, вывести весь список в столбик, а также
среднюю цену товара.
3. Самый дешевый товар поменять местами с первым, а самый
дорогой – с последним элементами. Вывести список.
4. Удалить из списка информацию о заданном товаре. Вывести
список после удаления.
Вариант 12
1. Организовать связный список из m элементов, используя
функцию создания списка с помощью генератора случайных чисел.
50
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
2. Вывести список в строку, используя функцию. В функцию
вывода добавить подсчет элементов.
3. В списке удалите узлы с заданным значением Х. Выведите
сообщение о количестве сделанных удалений, если такие были.
4. Вывести список на экран после удаления элементов.
Вариант 13
1. Организовать связный список, хранящий названия товаров,
фирму – изготовителя, цену.
2. Используя функцию вывести весь список в столбик, а также
среднюю цену товара.
3. Используя функцию, измените цену товаров заданной фирмы
с учетом некоторого коэффициента. Вывести полученный список.
4. Удалить из списка информацию о заданном товаре.
5. Вывести информацию о требуемом товаре (название вводится
с клавиатуры).
51
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
5. СТЕК
5.1 Операции обработки стека
Стек является одной из наиболее используемых важных структур данных. Стеки используются для распознавания синтаксиса в
компиляторе, для оценки правильности записи выражений. На нижнем уровне стек используется для передачи параметров функциям,
выполнения функции и возвращения из нее. Рекурсивные функции
работают по принципу стека.
Стек – это динамическая структура данных, в которой размещение новых элементов и удаление существующих выполняется
только с одного конца, называемого вершиной стека.
Стек предназначен для хранения элементов, доступных естественным путем в вершине стека.
В стеке, в отличие от списка, доступной является только одна
вершина. Стек используется в разных областях вычислительной техники. Он организован по принципу LIFO – «Last Input – First Output».
Что означает «последний пришел – первый ушел» (рис. 7).
top
NULL
Рис. 7. Стек
В структуре стека важнейшее место занимают операции, добавляющие и удаляющие элементы. Операция Push добавляет в вершину
стек, а операция Pop извлекает элемент с вершины стека. Следует
помнить, что удалять из пустого стека нельзя!
52
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Рассмотрим стек для хранения данных литерного типа. Опишем
сначала структуру элемента стека Stack, а затем – указательный тип.
struct Stack
{
char data; //информационное поле
Stack *pred; //ссылка на предыдущий элемент стека
};
typedef Stack* StackPtr;
Опишем функцию Push добавления нового элемента c в стек
top. Функция формирует новый узел tmp, заполняет его информационное поле значением с, ссылочную часть совмещает с вершиной
стека, а затем изменяет ссылку на новую вершину стека. Функция
напоминает добавление элемента в голову динамического линейного
списка.
void Push (StackPtr &top, char c)
{
StackPtr tmp= new Stack;
tmp-> data= c;
tmp->pred= top;
top=tmp;
}
Теперь рассмотрим функцию Pop извлечения очередного элемента из стека top. Функция возвращает информационную часть удаляемой вершины стека top, смещает указатель на предыдущий элемент стека и удаляет старую вершину. Важно, что удалять из пустого
стека нельзя, так как это может привести к аварийному останову программы.
char Pop (StackPtr &top)
{
if (top==NULL)
{ cout << “Ошибка! Стек пуст.”;
getch();
return 0;
53
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
}
char c= top-> data;
StackPtr tmp= top;
top = top->pred;
return c;
}
Рассмотрим применение стека на практических задачах. Стек
удобно использовать для проверки баланса скобок в арифметическом
выражении, для преобразования выражения в постфиксную форму
записи, а также для вычисления выражения, записанного в постфиксной форме. Эти приемы используются в алгоритмических анализаторах и трансляторах.
5.2. Проверка баланса скобок
Баланс скобок – это соответствие количества открывающихся и
закрывающихся скобок в записи выражения, причем открывающиеся
скобки должны встречаться раньше, чем закрывающиеся. В приведенных ниже примерах только первое выражение (а) записано верно,
а остальные содержат ошибки, хотя во втором случае (b) количество
открывающихся скобок равно количеству закрывающихся.
a) (d*(a-d/c)) *(1+a)^(3*b)
b) )a-c(
c) x*(y-z*x+1))
Баланс скобок любых типов должен соблюдаться как в любом
арифметическом или логическом выражениях, так и в программе в
целом. Эту проверку удобно делать с использованием стека.
Суть метода состоит в следующем: просматривая исходное выражение слева направо, каждую открывающую скобку будем помещать в стек, а встретившаяся закрывающая скобка будет вызывать
выталкивание из стека очередного элемента. Если при этом произойдет попытка удаления из пустого стека, то это означает, что баланс
54
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
скобок нарушен. Если по окончании просмотра выражения стек будет пустым, то баланс скобок соблюден, иначе – нет, то есть открывающихся скобок оказалось больше, чем закрывающихся.
Определим функцию, реализующую данный алгоритм. В качестве параметров функция получает строку, содержащую арифметическое выражение, а возвращает 0 или 1 в зависимости от результата
проверки. Ноль означает ошибку, а единица – правильность расстановки скобок. Для этого введем переменную – флаг flag, состояние
которой определяет результат проверки.
int check ( char s[])
{
int flag=1;
StackPtr t=NULL;
for (int i=0; i<strlen(s) && flag ; i++)
{
if (s[i]==’(‘) ) Push(t, s[i]);
if (s[i]==’)‘) )
if (t) Pop(t);
else flag=0;
}// for
if (t) flag=0;
return flag;
}//check
5.3. Постфиксная запись выражений
Электронные калькуляторы иллюстрируют одно из основных
применений стека. Пользователь вводит математическое выражение с
числами (операндами) и операторы, а калькулятор использует один
стек для вычисления числовых результатов. Алгоритм калькулятора
предусматривает ввод выражения в определенном числовом формате.
Такое выражение, как:
(4*12 + 5^2)/3
55
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
содержит бинарные операторы (+, *, /, ^), операнды ( 4, 12, 5, 2, 3) и
круглые скобки, которые создают подвыражения.
Выражение записывается в инфиксной (infix) форме, если каждый бинарный оператор помещается между его операндами и каждый
унарный оператор предшествует его операнду. Например,
-2+7*5
является инфиксным выражением. Инфиксный формат является
наиболее общим для записи выражений и используется в большинстве языков программирования и калькуляторов. Такое выражение
нельзя выполнить за один просмотр его слева направо.
Альтернативной рассмотренной форме является постфиксное
представление, в котором операнды предшествуют оператору. Этот
формат называется также RPN или Польской инверсной нотацией
(Reverse Polish Notation). Например, инфиксное выражение "а + b" записывается в постфиксной форме как "a b +". В постфиксной форме
переменные и числа вводятся по мере их появления, а оператор – там,
где имеются два его операнда. Например, в таблице 5 приведены
примеры эквивалентных выражений в инфиксной и постфиксной
формах записи.
Таблица 5
Примеры постфиксной записи выражений
Инфиксная запись
а+b*с
(а + b) * с
(a – с)/(b+a)
Постфиксная запись
abс*+
ab+с*
aс–ba+/
Особенности постфиксной записи выражений:
1) постфиксное выражение не содержит скобок;
2) постфиксное выражение можно вычислить за один просмотр
слева направо, используя стек для хранения операндов.
Эти особенности используются в анализаторах алгоритмических
языков.
56
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Простое выражение можно преобразовать в постфиксную форму
на интуитивном уровне, а для сложных выражений необходимо следовать алгоритму преобразования. Рассмотрим такой алгоритм преобразования, который носит название метода стека с приоритетами.
5.4. Метод стека с приоритетами
Метод стека с приоритетами позволяет преобразовать выражение из инфиксной в постфиксную форму. Скобкам и арифметическим
операциям ставится в соответствие их приоритет согласно таблице 6.
Таблица 6
Приоритет операций
Операция
(
)
+, *, /
^
Приоритет
0
1
2
3
4
В качестве входной строки рассматривается инфиксное выражение, оно сканируется слева направо. Выходная строка будет содержать
выражение в постфиксной форме. Для формирования выходной строки
будем использовать стек, который предварительно должен быть пуст.
Правила формирования выходного выражения:
1) Встретившийся операнд сразу помещается в выходную строку
результата.
2) Каждая открывающаяся скобка (нулевой приоритет) входной
строки помещается в стек без каких- либо проверок.
3) Каждая встретившаяся закрывающаяся скобка ни в стек, ни в
выходную строку не помещается, но выталкивает из стека в выходную строку все операции вплоть до открывающейся скобки, но сама
скобка в выходную строку не помещается, так как постфиксное выражение не должно содержать скобок.
57
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
4) Если приоритет входной операции больше приоритета операции в вершине стека, то она помещается в стек, иначе – она выталкивает в выходную строку все операции с приоритетом меньше либо
равным приоритету входного знака, а затем помещается в стек.
5) Если по окончании просмотра входной строки стек окажется
заполненным, то все операции выталкиваются из него в выходную
строку.
Таким образом, получим арифметическое выражение в постфиксной форме, к которому можно применять постфиксный калькулятор.
Пример. Рассмотрим преобразование выражения:
(a * (b+c))/(c-a)^2 +a*b/c
a) Выходная строка: a
Состояние стека: (, *
b) Выходная строка: a b c
Состояние стека: (, *, (, +
c) Выходная строка: a b c + *
Состояние стека: пуст
d) Выходная строка: a b c + * с a
Состояние стека: /, (, e) Выходная строка: a b c + * с a - 2
Состояние стека: /, ^
f) Выходная строка: a b c + * с a – 2 ^ /
Состояние стека: +
g) Выходная строка: a b c + * с a – 2 ^ / a
Состояние стека: +, *
h) Выходная строка: a b c + * с a – 2 ^ / a b * c
Состояние стека: +, /
i) Выходная строка: a b c + * с a – 2 ^ / a b * c / +
Состояние стека: пуст
Получили эквивалентную запись арифметического выражения в
постфиксной форме.
58
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Для вычисления такого выражения также используется стек, но
уже для хранения операндов, а не операций. Следовательно, тип информационной части стека будет вещественным.
При просмотре постфиксного выражения слева направо каждый
операнд помещается в стек, а встретившаяся операция выталкивает из
стека два операнда, затем вычисляется результат этой операции и помещается в стек. Следует помнить, что первым из стека выталкивается
второй операнд, а затем – первый. Это имеет значение для разности,
деления и возведения в степень. По окончании просмотра выражения в
стеке окажется его результат. Так работает постфиксный калькулятор.
5.5. Задания на лабораторную работу 4 «Стек»
Вариант 1
Составить функцию проверки правильности расстановки всех
типов скобок ([], (), {}) в арифметическом выражении. Сначала выражение считывать с клавиатуры, затем преобразовать программу для
чтения выражения из файла.
Вариант 2
Составить программу постфиксного калькулятора, которая вычисляет арифметическое выражение, записанное в постфиксной форме, используя стек для хранения операндов и результатов очередной
операции. Например,
17.5 0.3 + 2 1.2 5.17 * / *
Вариант 3
Составить программу преобразования арифметического выражения из инфиксной формы в постфиксную, используя метод стека с
приоритетами.
Выражение в инфиксной форме считывать с клавиатуры, а полученное постфиксное выражение выводить на экран.
59
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Вариант 4
Используя стек, определить, является ли введенная с клавиатуры
строка палиндромом (палиндром – строка, которая читается в прямом
и обратном порядке одинаково). Преобразовать программу для чтения данных из файла.
Вариант 5
Описать функцию, которая, используя стек, преобразует десятичное число N в любую другую систему счисления с основанием В.
Используя эту функцию, вывести числа в двоичной, восьмеричной и
шестнадцатеричной системах счисления.
Проверить полученные результаты с помощью соответствующих манипуляторов (oct, hex).
Вариант 6
Составить программу «постфиксный калькулятор», которая вычисляет арифметическое выражение в постфиксной записи, используя
стек для хранения операндов и результатов очередной операции.
Например,
-1.5 4.13 2.11 + * 15.1 /
Вариант 7
Составить функцию проверки правильности расстановки всех
типов скобок ([], (), {}) в программном файле с расширением cpp.
Пусть имя файла передается для функции как параметр, а функция
возвращает номер строки, в которой произошла ошибка.
Вариант 8
Обработать текстовый файл, все числа, встретившиеся в файле,
вывести в обратном порядке. При сканировании файла создавать
стек. А по окончании просмотра вытолкнуть все значения из стека на
экран.
60
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
6. ДРУГИЕ ВИДЫ ДИНАМИЧЕСКИХ СПИСКОВ
6.1. Очередь
Очередь – это динамическая структура данных, в которой добавление элементов выполняется в хвост, а удаление – из головы.
В англоязычной литературе для обозначения очередей довольно
часто используется аббревиатура FIFO (first-in-first-out – «первый
вошёл – первым вышел»).
Можно привести много примеров из жизни, в которых используется очередь. Это очередь людей в магазине, заявки на обслуживание клиентов поступают и выполняются в порядке очереди, каждая
нажатая на клавиатуре клавиша помещается в очередь, а затем обрабатывается компьютером и т. д.
Очередь разумнее всего моделировать на основе динамического
списка. В этом случае в идентификаторе очереди будет присутствовать информация как об указателе на голову, так и на хвост очереди.
Схема очереди приведена на рисунке 8.
Выделим типовые операции над очередями:
– добавление элемента в очередь (помещение в хвост);
– удаление элемента из очереди (удаление из головы);
– проверка очереди на пустоту;
Q
First
5
Last
10
*
7
*
12
*
Рис. 8. Очередь
61
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Узел очереди может быть описан подобно динамическому односвязному списку List (см. Динамический список). Для указательного
на узел типа используется тип ListPtr. Структура идентификатора
очереди будет хранить два указателя: на первый элемент списка –
First и указатель на последний элемент – Last.
struct Queue
{ ListPtr First, Last;
};
Опишем функцию добавления Qput в очередь нового элемента с
значением х. Пусть функция в качестве параметра получает очередь
Q и переменную х. Выделим новую память под вспомогательную переменную tmp и заполним ее поля: информационное и ссылочное.
Ссылочное поле будет нулевым, так как новый элемент добавляется в
хвост списка. Если очередь в момент добавления пуста, то оба указателя (Last и First) будут указывать на этот узел. Если очередь не пуста, то необходимо добавить узел после последнего элемента и переопределить ссылку Last.
void Qput (Queue &Q, int x)
{
ListPtr tmp;
tmp = new List;
tmp->data=x; tmp-> next = NULL;
if (Q.Last==NULL)
Q.Last= Q.First= tmp;
else {
Q.Last-> next = tmp;
Q.Last = tmp;
}
}
Так как в результате работы функции может измениться ее параметр Q, то он должен передаваться по адресу &Q.
62
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Функцию извлечения из очереди предлагается определить самостоятельно. При этом удаление выполняется из головы, поэтому она
идентична функции удаления из стека. Функция в качестве параметра
должна получать очередь, с которой выполняется работа, а возвращать она должна значение информационной части удаленного элемента, то есть целочисленный тип.
6.2. Циклический список
Циклическим называется список, последний элемент которого
содержит ссылку на первый элемент списка, то есть на голову.
Внешний вид циклического списка приведен на рисунке 9.
С
10
20
30
40
Рис. 9. Циклический список
В циклическом списке нет ни одного элемента с нулевой ссылочной частью, поэтому о голове списка можно говорить лишь
условно. Каждый элемент может выступать в качестве головы списка.
Вывод содержимого списка на экран или в какой-либо другой
выходной поток можно выполнять, начиная с любого элемента. Дополнительной структуры для описания циклического списка не требуется, можно использовать ранее описанный тип, например ListPtr.
Однако при формировании списка необходимо его зациклить, то есть
ссылке последнего элемента присвоить указатель на голову, например Head:
tmp- > next = С;
При выводе содержимого списка рекомендуется воспользоваться циклом с постусловием, который позволяет сначала выполнить
действие, а затем проверить условие.
63
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Приведем пример функции ShowCycle вывода списка С на экран
с подсчетом количества узлов.
void ShowCycle (ListPtr C)
{
int k=0;
ListPtr tmp = C;
cout<<”Циклический список” << endl;
do {
tmp = tmp = > next;
} while (tmp! = C);
cout<< endl << “ в списке ”<< k << “ элементов”<< endl;
}
Над циклическим списком допустимы следующие операции:
 добавление нового узла после заданного;
 удаление узла по значению;
 вывод списка на экран;
 формирование циклического списка;
 сцепление двух циклических списков в один;
 расщепление одного циклического списка на два, начиная с
заданного узла.
6.3. Двунаправленный список
Это самый распространенный вид динамического списка, используемый в современной практике программирования. Все выделяемые объекты интерфейсной среды выстраиваются в динамический
список. Затем над ними выполняются действия. Например, при работе с файлами в программах – оболочках.
Двунаправленный список характеризуется тем, что каждый его
узел, кроме информационной части, содержит две ссылочные части –
на следующий и на предыдущий узлы (рис. 10).
64
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
D
10
20
30
40
Рис. 10. Двунаправленный список
Структура узла двунаправленного списка будет следующей:
struct Dlist
{ int data;
Dlist *next, *prev; } ;
typedef Dlist* DLPtr;
Над двунаправленным списком допустимы те же операции, что
над обычным списком:
 добавление нового узла в определенное место списка;
 удаление узла по значению;
 вывод списка на экран;
 формирование списка;
 сцепление двух списков в один;
 расщепление одного списка на два, начиная с заданного узла.
Рассмотрим функцию Form формирования двунаправленного
списка D из n чисел вида 0, 10, 20, 30 и т. д. Параметр D следует передавать по адресу, так как список должен создаваться и предаваться
в вызывающую программу.
void Form (DLPtr &D, int n)
{ D=new Dlist;
D-> data = 0; D-> next= D-> prev =NULL;
DLPtr tmp =D;
for( int i=1; i<n; i++)
{ tmp-> next = new Dlist;
tmp -> next -> prev = tmp;
tmp = tmp -> next;
tmp-> data=i*10;
65
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
tmp-> next= NULL;
}
}
6.4. Дек
Дек – это динамическая структура данных, в которой добавление и удаление элементов выполняется в голову так и в хвост списка.
Подобно стеку и очереди над деком допустимы только две операции: добавление и извлечение элемента. Функции просмотра и поиска над деком не выполняются. Организацию дека можно сравнить с
железнодорожными путями (рис. 11), вагоны можно добавлять к составу только с одного или другого конца поезда, но не вовнутрь.
Рис. 11. Схема организации дека
При программной реализации дека можно определить отдельную
структуру для идентификации дека, подобно очереди, которая будет
хранить ссылки на первый и последний элементы очереди (рис. 6). Однако динамический список при этом должен быть двунаправленным
для удобства реализации операций добавления и удаления элементов.
Поэтому описание структуры дека содержит ссылки на определение
узла двунаправленного списка.
struct Dek
{ DLPtr First, Last;
// указатели на первый и последний элементы дека
};
66
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Функции добавления и удаления элементов должны содержать в
списке параметров целочисленную переменную – флаг, определяющую место выполнения данной операции – хвост (0) или голова (1).
Опишем заголовки этих функций, реализацию предлагается сделать самостоятельно. Так как идентификатор дека в результате выполнения этих функций изменяет свое значение, то он должен передаваться по адресу.
// Добавление нового элемента t в дек k
void newItem ( Dek &k, int t, int flag);
Если флаг flag будет равен 1, то добавление нового элемента будет выполняться в голову, то есть перед первым элементом. Это операция подобна операции добавления в стек. Если же флаг будет равен
0, то добавление элемента выполняется в хвост, после последнего
элемента. Эта операция подобна операции добавления в очередь.
// Удаление очередного элемента из дека k
int delItem ( Dek &k, int flag);
Операция удаления из дека напоминает удаление из очереди или
из стека, в зависимости от состояния флага. Функция возвращает значение информационной части удаленного элемента, поэтому тип функции должен совпадать с типом информационной части узла двунаправленного списка. В нашем случае используется целочисленный тип.
При выполнении этих действий будут меняться ссылки дека на
первый k.First и последний k.Last элементы списка. На рисунке 12
пунктирными линями показана схема добавления нового элемента в
голову дека.
k
First Last
100
800
210
714
405
Рис. 12. Схема добавления нового элемента в голову дека
67
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
6.5. Задания на лабораторную работу 5
«Другие виды списков»
Вариант 1
Описать структуру двунаправленного списка целых чисел. Из
некоторого массива данных создать список.
Смоделировать на нем функции вывода содержимого списка на
экран, добавления некоторого элемента после заданного, удаления
заданного по значению элемента, разделения списка на два, начиная с
заданного значения.
Вариант 2
Переписать содержимое текстового файла, разделенного на
строки в другой текстовый файл, перенося при этом в конец каждой
строки все входящие в нее цифры (с сохранением исходного порядка
среди них).
При чтении файла цифры сначала помещаются в очередь, а затем из очереди выталкиваются в конец строки.
Вариант 3
N ребят располагаются по кругу (задать в качестве элементов
списка имена). Начав отсчет от первого, удаляют согласно считалке
каждого k-го, смыкая при этом круг. Определить порядок удаления
ребят из круга, выводя на экран имя и порядковый номер удаляемого.
Выполнить ввод данных с клавиатуры, организовав циклический список. Предусмотреть ввод текста считалки, после чего подсчитывается
число слов в ней (k).
Вариант 4
Организовать два циклических списка, содержащих данные о
клиентах (наименование организации, шифр). Информацию получить
из файла. Вывести на экран списки, используя функцию. Сцепить два
циклических списка в один, вывести на экран результат слияния. За68
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
тем удалить из нового списка клиентов, шифр которых начинается с
заданной цифры.
Вариант 5
Организовать циклический список, содержащий данные о клиентах (наименование, шифр). Вывести на экран список, используя
функцию.
Разбить данный список на два, начиная с заданного клиента.
Вывести на экран списки, используя функцию. Добавить в голову
каждого списка по одному новому клиенту.
Вариант 6
Организовать линейный двунаправленный список, содержащий
данные о товарах (шифр, наименование, количество). Каждый элемент, кроме информационной части, содержит указатель на предыдущий и следующий элементы.
Описать основные функции обработки списка (вывод на экран,
добавление элемента, удаление элемента, поиск товара по шифру).
Используя функцию поиска, найти заданный товар и изменить поле
количество на заданную величину.
Вариант 7
В текстовом файле заданы действительные числа. Выбрать из
него убывающую последовательность наибольшей длины и вывести
ее на экран. Если таких последовательностей несколько, то вывести
их все в отдельной строке каждую.
Для запоминания убывающих последовательностей формировать массив очередей, хранить для каждой очереди длину ее (количество элементов).
69
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Вариант 8
C клавиатуры запрашиваются коэффициенты и степень х некоторого полинома. Для хранения коэффициентов и степеней полинома
использовать двунаправленный список.
4x^4-7x^3+3x-2x^3+x^2=0
Привести подобные слагаемые и распечатать выражение в порядке убывания степеней.
Вариант 9
В файле записано математическое выражение, например:
x^3-5x^2+3x +2=0.
Для хранения коэффициентов и степеней полинома использовать двунаправленный список. Вычислить значение полинома для х,
введенного с клавиатуры.
Вариант 10
Создать дек для хранения литерных символов. Читать с клавиатуры или из файла строку символов, состоящую из букв английского
алфавита. Если встречается заглавная буква, то помещать ее в голову,
если маленькая, то в хвост дека.
При извлечении из дека очередного элемента у пользователя запрашивается признак места извлечения (1 – голова, 0 – хвост). Вывести на экран полученную строку.
Вариант 11
Создать дек для хранения литерных символов. Читать с клавиатуры строку символов, состоящую из букв английского алфавита и
цифр. Если встречается буква, то помещать ее в голову, если цифра,
то в хвост дека.
При извлечении из дека очередного элемента у пользователя запрашивается признак места извлечения (1 – голова, 0 – хвост). Вывести на экран полученную строку.
70
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
7. РЕКУРСИЯ
7.1. Организация рекурсивных функций
Все функции в программе, написанной на языке С или С++, равноправны. Каждая из них может вызывать любую другую функцию и,
в свою очередь, каждая может быть вызвана любой другой функцией.
Это делает функции языка Си++ несколько отличными от процедур
Паскаля, поскольку процедуры в Паскале могут быть вложены в другие процедуры, причем процедуры, описанные в разных процедурах,
являются недоступными для процедур, описанных в других независимых процедурах.
Каждая функция может вызвать саму себя. Действие, состоящее
в том, что функция вызывает сама себя, называется рекурсией.
Рекурсивной называют функцию, которая прямо или косвенно
сама вызывает себя. Именно возможность прямого или косвенного
вызова позволяет различать прямую или косвенную рекурсию.
Функция называется косвенно рекурсивной в том случае, если
она содержит обращение к другой функции, содержащей прямой или
косвенный вызов определяемой (первой) функции. В этом случае по
тексту определения функции ее рекурсивность (косвенная) может
быть не видна. Если в теле функции явно используется вызов этой же
функции, то имеет место прямая рекурсия.
Так как при каждом обращении к рекурсивной функции создается новый набор объектов автоматической памяти, локализованных в
теле функции, то при использовании рекурсивных алгоритмов с глубокой вложенностью рекурсии может быстро произойти переполнение стека реализации рекурсий, поэтому надежнее использовать итерационные алгоритмы. Например, пусть нужно реализовать «салфетку Серпинского» (геометрический фрактал). Как она образуется? Рисуется треугольник и в нем средние линии. В образованных при углах
исходного треугольника новых треугольниках опять рисуются средние линии и так далее, до заданного порядка вложенности рекурсии.
71
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Локальные переменные
Переменные, известные только одной функции, а именно той,
которая их содержит, называются локальными переменными. Подчеркнем, что локальные переменные являются действительно локальными. Даже в том случае, когда мы используем одно и то же имя для
переменных в двух различных функциях, компилятор считает их разными переменными.
При каждом обращении к рекурсивной функции создается новый набор объектов автоматической памяти, локализованных в теле
функции.
Управление рекурсией
1) при обращении к функции компилятор выполняет подстановку фактических параметров вместо формальных и передает управление этой функции;
2) когда встречается рекурсивное обращение к этой же функции,
компилятор приостанавливает выполнение текущего фрагмента, запоминая в кадре памяти все значения локальных переменных, а также
все невыполненные операторы и действия;
3) происходит повторное обращение к рекурсивной функции с
новым списком фактических параметров;
4) пункты 2 и 3 повторяются до тех пор, пока не встретится вершина рекурсии, при этом все кадры памяти сохраняются в стеке;
5) при достижении вершины рекурсии компилятор начинает выполнять все накопленные кадры памяти, извлекая их из стека памяти,
то есть в обратном порядке, с соответствующими значениями локальных объектов.
Чтобы рекурсивная функция была корректной и выполнимой,
необходимо соблюдение следующих правил:
1) в одном или более случаев функция должна выполняться
независимо от рекурсивного обращения (вершина рекурсии);
2) при каждом очередном обращении к рекурсивной функции
один или более параметров должны стремиться к вершине рекурсии.
72
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
К рекурсивным алгоритмам приводят задачи, в определении которых рекурсия присутствует явно. Например, при определении члена ряда с помощью рекуррентного соотношения предполагает определения i-го члена через значение i – 1-го члена.
Рассмотрим вычисление факториала n.
n!=1* 2* 3* …. * n
Известно, что
0! =1
1! =0! * 1
2! = 1! * 2 и т. д.
n!= (n-1)! * n
Последнее соотношение позволяет использовать для определения n! рекурсивную функцию, а вершиной рекурсий будет нулевое
значение n. Опишем функцию вычисления факториала n. Так как в
функции выполняется произведение чисел, то имеет смысл дать ей
длинный целый тип.
long factorial (int n)
{
if (n == 0) return 1;
return factorial (n-1)*n;
}
Рекурсивными могут быть не только алгоритмы и функции, но и
типы. К таким рекурсивным типам относятся типы узла динамических структур данных: списки, стеки, очереди, деки, деревья.
7.2. Задания на лабораторную работу 6 «Рекурсия»
Вариант 1
1) Данные о студентах (шифр зачетной книжки, фамилия, оценка)
хранятся в массиве в порядке возрастания шифра зачетной книжки.
Выполнить бинарный поиск информации о студенте по номеру
зачетки, используя рекурсивную функцию.
73
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
2) Описать рекурсивную функцию вычисления числа Фибоначчи. Найти сумму первых N чисел Фибоначчи.
Вариант 2
1) В массиве хранятся упорядоченные по фамилии данные о студентах: номер зачетной книжки, фамилия, оценка.
Выполнить бинарный поиск информации о студенте по его фамилии, используя рекурсивную функцию.
2) Опишите рекурсивную функцию вычисления суммы N первых
чисел натурального ряда. Проверьте результат по формуле
S= n(n+1)/2
Вариант 3
1) В массиве хранятся упорядоченные по алфавиту ключевые
слова алгоритмического языка C++. С клавиатуры вводить любой
идентификатор, выводить на экран сообщение о том, является ли он
ключевым словом языка или нет. Использовать бинарный поиск.
2) Определите рекурсивную функцию вычисления наибольшего
общего делителя положительных чисел а и b:
int nod( int a, int b).
Вариант 4
1) В массиве хранятся упорядоченные по фамилии данные о сотрудниках (табельный номер, фамилия, оклад). Выполнить бинарный
поиск информации о сотруднике по его фамилии, используя рекурсивную функцию бинарного поиска.
2) Описать рекурсивную и не рекурсивную функции вычисления
числа Фибоначчи с порядковым номером N. Сравнить результаты работы обоих алгоритмов.
74
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Вариант 5
1) В массиве хранятся упорядоченные по номеру данные о сотрудниках (табельный номер, фамилия, оклад). Определить рекурсивную функцию поиска сотрудника по его табельному номеру.
2) Опишите рекурсивную функцию вычисления корня нелинейного уравнения методом деления отрезка пополам на отрезке [a,b] с
точностью precision для функции y = 2*(sin(x+0,5) Выполнить проверку полученного результата.
Вариант 6
1) В массиве хранятся упорядоченные по номеру группы данные
о студенческих группах (номер группы, староста, количество студентов). Выполнить бинарный поиск информации о группе по ее номеру,
используя рекурсивную функцию.
2) Определите рекурсивную функцию преобразования целого
числа N в любую систему счисления, основанием В меньше 10.
Вариант 7
1) В массиве хранятся упорядоченные по фамилии данные об
абонентах: номер телефона, фамилия.
Выполнить бинарный поиск информации об абоненте по его
номеру телефона, используя рекурсивную функцию.
2) Описать рекурсивную функцию поиска минимального элемента в неупорядоченном числовом массиве.
Вариант 8
1) В массиве хранятся упорядоченные по номеру данные о квартирах одного дома: номер квартиры, фамилия квартиросъемщика, количество жильцов. Выполнить бинарный поиск информации о квартире по ее номеру, используя рекурсивную функцию.
2) Опишите рекурсивную функцию вычисления корня нелинейного уравнения методом деления отрезка пополам на отрезке [a,b] с
заданной точностью для функции y= sin2x+0,3.
75
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Выполнить проверку полученного результата.
Вариант 9
1) В массиве хранятся упорядоченные по фамилии данные о
квартиросъемщиках одного дома: номер квартиры, фамилия квартиросъемщика, количество жильцов. Выполнить бинарный поиск информации о квартире по фамилии жильца, используя рекурсивную
функцию.
2) Найти k-й член последовательности, если задана рекуррентная
формула вычисления n-го члена ряда:
x0=1, xn=nxn-1 +1/n, при n=1, 2, 3, …
Вариант 10
1) В массиве хранятся упорядоченные по названию данные о ценах на товары: описание товара, цена, количество товара. Выполнить
бинарный поиск информации о товаре по его названию, используя
рекурсивную функцию.
2) Определить рекурсивную функцию вывода массива в прямом
и обратном порядке.
76
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
8. ДЕРЕВЬЯ
8.1. Описание и обработка древовидной структуры
Дерево – иерархическая структура данных, хранящая набор элементов, каждый из которых имеет значение и может указывать на
ноль или более других элементов этого же типа, называемых поддеревьями или потомками. Но на каждый элемент указывает только
один другой элемент, называемый предком. Единственным исключением является корень дерева, на который не указывает ни один элемент. Входящие в дерево элементы называются его вершинами.
Есть много типов деревьев, которые отражают сложные структуры, например, деревья синтаксического разбора (parse trees), хранящие синтаксис предложения или программы, либо генеалогические
деревья, описывающие родственные связи. Мы продемонстрируем
основные принципы на деревьях двоичного (бинарного) поиска, в которых каждая вершина имеет по две связи. Они просто реализуются и
демонстрируют наиболее важные свойства деревьев.
Вершины бывают следующих видов:
 Корень – это вершина, с которой начинается формирование
дерева; она не имеет предков и находится на нулевом уровне.
 Внутренняя вершина – это вершина, имеющая и предков, и
потомков.
 Лист или терминальная вершина – это вершина дерева, не
имеющая потомков.
Вершина в двоичном дереве имеет значение и два указателя, left и
right, которые показывают на его дочерние вершины. Эти указатели
могут быть равны NULL, если у вершины меньше двух дочерних вершин.
Над деревом допустимы следующие операции:
1) добавление новой вершины в дерево;
2) вывод содержимого дерева на экран или в выходной поток;
3) поиск вершины по значению;
77
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
4) обход дерева по определенному закону;
5) удаление вершины по значению.
Деревья, в основном, предназначены для организации эффективного поиска узла по значению. Для этого предусмотрены деревья
специальной организации. В основной памяти используются так
называемые деревья бинарного поиска, а во внешней памяти – сильноветвящиеся В-деревья, красно-черные деревья и другие их разновидности. Рассмотрим более подробно организацию бинарного (или
двоичного) дерева поиска.
Бинарное дерево называется деревом поиска, если все дочерние
вершины, расположенные левее данной, имеют меньшие значения, а
все дочерние вершины правее – большие.
Комментарии «большие» и «меньшие» относятся к свойствам
связей: левые «дети» хранят меньшие значения, правые – большие.
Благодаря этому свойству мы можем использовать разновидность двоичного поиска для быстрого поиска значения по дереву или
определения, что такого значения нет.
На рисунке 13 приведен пример бинарного дерева поиска, хранящего данные целого типа.
Опишем структуру вершины дерева Tree и определим сразу
пользовательский указательный тип на вершину дерева, назовем его
TreePtr.
struct Tree
{
int key; // информационное поле узла дерева
Tree *left, *right; // ссылки на левого и правого потомков
};
typedef Tree* TreePtr;
78
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
58
67
35
21
46
62
51
73
70
Рис. 13. Пример числового бинарного дерева поиска
Попытайтесь добавить в это дерево значения 42, 14, 65, 94, 78, 7,
15 так, чтобы не нарушилось правило формирования бинарного дерева поиска.
Поскольку в каждой вершине дерева хранится несколько указателей на другие элементы, то многие операции, занимающие время порядка О(n) в списках или массивах, занимают только O(log2n) в деревьях. Наличие нескольких указателей в каждой вершине сокращает время
выполнения операций, так как уменьшается количество вершин, которые необходимо посетить, чтобы добраться до нужной вершины.
Дерево двоичного поиска (которое в данном параграфе мы будем называть просто «деревом») достраивается рекурсивным спуском
по дереву; на каждом шаге спуска выбирается соответствующая правая или левая ветка, пока не найдется место для вставки новой вершины, которая должна быть корректно инициализированной структурой TreePtr. Новая вершина добавляется как лист дерева, то есть у
него пока отсутствуют дочерние вершины.
Будем считать, что дерево строится из уникальных (неповторяющихся) значений. Выполняется рекурсивный поиск места новой
вершины в дерево в зависимости от того, больше или меньше оказалось значение х, чем информационная часть текущего узла дерева.
Поиск всегда выполняется, начиная с корня дерева. Дойдя до нужного места вставки, необходимо выделить динамическую память под
новую вершину, заполнить ее значением х, обнулить ссылки на лево79
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
го и правого потомков, так как новый узел всегда добавляется в терминальную вершину, и возвратить значение этой новой вершины.
Поэтому функция добавления add новой вершины со значением х в
дерево Р будет рекурсивной и иметь следующий вид:
// Функция добавления новой вершины х в дерево Р.
TreePtr add( TreePtr P, int x)
{
if (P==NULL){P=new Tree;
P->key=x;
P->left=P-right=NULL;
return P;
}
if (x<P->key) P->left=add(P->left, x);
else P->right=add(P->right, x);
return P;
}//add
Если необходимо учесть повторяющиеся значения (дубликаты)
среди чисел некоторого входного потока, то в структуру вершины дерева следует добавить новое поле count, которое будет выступать в
качестве счетчика. Первоначальное значение этого поля при первичном добавлении узла будет равным единице, а при встрече совпадения значений х и P->key оно должно увеличиться на 1, то есть
P->key++. Проделайте самостоятельно эти действия, скорректируйте
функцию add с учетом возможных дубликатов.
Рассмотрим функцию поиска элемента со значением х в дереве
Р, которая возвращает указатель на найденную вершину или NULL,
если вершина не найдена. Функция так же будет рекурсивной, так как
повторяет похожие действия в левом или правом поддереве в зависимости от того, как относится х к значению текущего узла. Используется тот же принцип, что и в функции add.
// Функция поиска вершины со значением х в дереве Р.
80
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
TreePtr search( TreePtr P, int x)
{
if (P==NULL || P-> key == x) return P;
if (x<P->key) return search(P->left, x);
else return search (P->right, x);
}//search
Аналогично числовому строится дерево со строковыми значениями вершин. В этом случае сравниваются символы строки согласно
их кодам в таблице кодов ASCII. Меньше будет та строка, символы
которой идут по алфавиту раньше, то есть их коды в таблице кодов
ASCII будут иметь меньшее значение. Например, дерево может строиться по фамилиям сотрудников, шифрам зачетных книжек студентов, ключевым словам языка программирования для организации
быстрого поиска искомого значения.
Информационное поле вершины может быть сложного пользовательского типа и содержать другую значимую информацию, но поиск осуществляется по тому полю, по которому выполнялось построение дерева.
Удаление из дерева поиска выполняется по специальному алгоритму и предусматривает 3 варианта удаления вершин:
1) удаление терминальной вершины (листа);
2) удаление внутренней вершины, у которой имеется только
один потомок;
3) удаление внутренней вершины, у которой имеются два непустых потомка.
В первом простом случае ссылка предка, которая указывает на
удаляемый узел, обнуляется, а листовая вершина ликвидируется с
помощью оператора delete. На рисунке 12 к таким терминальным
вершинам относятся вершины со значениями 21, 51, 62, 70.
Во втором случае ссылка предка удаляемой вершины перенаправляется на этого единственного потомка, который имеется у уда81
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
ляемой вершины. Он может быть как левым, так и правым потомком.
К таким вершинам относятся вершины со значениями 46 и 73.
Третий случай наиболее интересен. При удалении внутренней
вершины, у которой имеются оба потомка (вершины 35, 58, 67), ее
необходимо заменить на терминальную или внутреннюю вершину,
которая является самым правым потомком от левого сына или самым
левым потомком от левого сына. После чего эта заменяющая вершина
удаляется согласно варианту 1 или 2. Так, при удалении корневой
вершины 58 она будет заменяться на значение вершины 51 или 62.
Обратите внимание, что это наиболее близкие по значению к удаляемой вершине значения. Таким образом, принцип бинарного дерева
прииска не нарушается. Из двух возможных алгоритмов такого удаления можно выбрать любой на усмотрение программиста. На рисунке 14 изображено дерево после удаления вершины 58.
51
67
35
21
46
62
73
70
Рис. 14. Дерево поиска после удаления узла 58
Поэкспериментируйте с деревом, в котором больше уровней и
узлов. Функция удаления является также рекурсивной и рассмотрена
у многих авторов предлагаемого списка литературы.
82
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
8.2. Обход дерева
Обход дерева означает посещение каждой вершины по определенному закону. Различают следующие разновидности обхода дерева:
1) Прямой обход – корень, левое поддерево в прямом обходе,
правое поддерево в прямом обходе;
2) Симметричный обход – левое поддерево в симметричном обходе, корень, правое поддерево в симметричном обходе;
3) Обратный обход – левое поддерево в симметричном обходе
правое поддерево в симметричном обходе, корень.
Для программной реализации обхода дерева удобно воспользоваться рекурсивной функцией. Рассмотрим функцию симметричного
обхода бинарного дерева и вывода на экран значения его вершин.
Сначала посещаем левое поддерево, затем, раскручивая рекурсию
назад по принципу стека, выводим на экран значение информационного поля вершины, и для каждой вершины посещаем в симметричном обходе ее правого потомка. Вершиной рекурсии будет значение
нулевой ссылки посещаемой вершины.
// Функция симметричного дерева
void simm(TreePtr P)
{
if (P==NULL) return;
simm(P -> left);
cout << P -> key<<”\t”;
simm(P -> right);
}
Для реализации других функций обхода следует только изменить порядок действий в функции согласно порядку посещения вершин в дереве.
83
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Иногда структура дерева отражает какое-то внутреннее упорядочение данных, как в генеалогических деревьях, и порядок обхода
листьев будет зависеть от отношений, которые дерево представляет.
8.3. Сбалансированные деревья
После того как мы научились перемещаться по дереву, остальные стандартные операции реализуются совершенно естественно. Мы
можем использовать технологии управления списками, например,
написать общую процедуру обхода дерева, которая вызывает заданную функцию для каждой вершины. Однако в этом случае нужно
сделать выбор: когда выполнять операцию над данной вершиной, а
когда обрабатывать оставшееся дерево? Ответ зависит от того, что
представляет собой дерево: если оно хранит упорядоченные данные,
как в дереве двоичного поиска, то мы сначала посещаем левую часть,
а затем уже правую.
Использование алгоритма включения и удаления узла из дерева
может привести к нарушению сбалансированности дерева и увеличению длины пути поиска в дереве. Процедура включения, восстанавливающая идеальную сбалансированность структуры дерева, вряд ли
будет выгодна, поскольку такое восстановление после случайного
включения – довольно сложная операция. Но ее можно упростить,
если дать менее строгое определение «сбалансированности». Такой
несовершенный критерий сбалансированности может потребовать
более простой перестройки дерева при небольшом уменьшении среднего быстродействия поиска.
Одно такое определение сбалансированности было дано Адельсоном-Вельским и Ландисом. Критерий сбалансированности следующий:
Дерево является сбалансированным тогда и только тогда, когда
для каждого узла высота его двух поддеревьев различается не более
чем на 1.
84
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Деревья, удовлетворяющие этому условию, часто называют
АВЛ – деревьями (по фамилиям их изобретателей). Мы будем называть их просто сбалансированными деревьями, так как их критерий
сбалансированности оказывается наиболее подходящим. Все идеально сбалансированные деревья являются также АВЛ – сбалансированными, но не наоборот. Это определение приводит к легко выполнимой балансировке, а средняя длина поиска остается практически такой же, как у идеально сбалансированного дерева.
Авторами было доказано, что АВЛ – дерево не превышает по
глубине аналогичное идеально сбалансированное дерево более, чем
на 45%.
Включение в сбалансированное дерево
Когда в сбалансированное дерево (с корнем R, левым и правым
поддеревьями L и К) включается новый узел, вызывая увеличение его
высоты на 1, возможны три случая:
1. L и R становятся неравной высоты, но критерий сбалансированности не нарушается.
2. L и R приобретают равную высоту, то есть сбалансированность даже улучшается.
3. Критерий сбалансированности нарушается, и дерево нужно
перестраивать.
Рассмотрим дерево на рисунке 15.
17
28
10
5
15
Рис. 15. Сбалансированное АВЛ – дерево
Узлы с ключами, например, 20 и 31 можно вставить без балансировки; однако включение узлов 1, 3, 5 или 11, 12, 13, 14 и 16 требу85
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
ет последующей балансировки. При внимательном изучении этой ситуации можно обнаружить, что имеются лишь две существенно различные возможности, требующие индивидуального подхода. Оставшиеся могут быть получены симметричными преобразованиями этих
двух. Вариант 1 определяется перегрузкой левого поддерева, а вариант 2 – перегрузкой правого поддерева.
Эти два случая показаны на рисунке 16, где поддеревья обозначены прямоугольниками, а увеличение высоты при включении
выделено кружками.
Рис. 16. Нарушение сбалансированности при добавлении вершины
Рис. 17. Восстановление баланса
Простые преобразования этих двух структур восстанавливают
нужную сбалансированность. Их результат приведен на рисунке 17;
отметим, что допускаются перемещения лишь в вертикальном направлении, в то время как относительное горизонтальное расположение
показанных узлов и поддеревьев должно оставаться без изменений.
86
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
8.4. Оптимальные деревья поиска
Рассмотрим сначала определение взвешенной длины пути.
При рассмотрении деревьев поиска мы до сих пор исходили из
предположения, что частота обращения ко всем узлам одинакова, то
есть все ключи с равной вероятностью становятся аргументами поиска. На практике часто бывает другая ситуация, когда необходимо
иметь информацию о вероятности обращений к отдельным ключам,
чтобы общее число шагов поиска было минимальным. Введем определение взвешенной длины пути: взвешенная длина пути есть сумма
всех путей от корня к каждому узлу, умноженных на вероятность обращения к этому узлу:
n
P = ∑ p i * hi
i=1
где рi – вероятность обращения к узлу i;
hi – уровень узла i (или его расстояние от корня + 1).
Задачей является минимизировать взвешенную длину пути для
данного распределения вероятностей. В качестве примера рассмотрим множество ключей 1, 2, 3 с вероятностями обращения:
p1 = 1/7, р2=2/7 и р3=4/7.
Эти три ключа можно расположить в виде деревьев поиска пятью различными способами (рис. 18).
а)
b)
c)
d)
e)
Рис. 18. Деревья поиска с тремя узлами
Взвешенные длины пути этих деревьев вычисляются в соответствии с вышеприведенной формулой:
Рi(а)=1/7(1*3+2*2+4*1)=11/7;
Pi (b)=l/7(1* 2+2*3+4*1)=12/7;
Pi (c)=l/7(1* 2+1*2+4*2)=12/7;
87
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Pi (d)=1/7(1*1+2*3+4*2) =16/7;
Pi(e)=l/7(l*1+2*2+4*3)=17/7.
В этом примере оптимальным оказывается не идеально сбалансированное дерево, а вырожденное дерево, соответствующее случаю а.
Если известна также вероятность qi того, что аргумент поиска х
лежит между двумя ключами ki и ki+1, то это может существенно повлиять на структуру оптимального дерева поиска. Рассмотрим расширенное дерево бинарного поиска, которое представляет собой дерево поиска из n элементов множества К= {k1 ,k2 , ..,kn} с n+1 листьями, представляющими элементы другого множества D (рис. 19).
Рис. 19. Пример расширенного дерева бинарного поиска
В расширенном дереве бинарного поиска листья появляются
слева направо в порядке d0 ,d1 ..., dn и удовлетворяют следующим
условиям:
1. di (l≤ i≤ n-1) представляет множество тех элементов, для которых ki<x<ki+1
2. d0 представляет собой множество элементов, для которых
x<k1;
3. dn представляет множество тех элементов, для которых х>kn.
88
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Общая взвешенная длина для расширенного дерева бинарного
поиска имеет следующий вид:
n
n
P = ∑pi *hi + ∑qi *h 'i
i=1
n
i=1
n
где ∑pi + ∑qi = 1;
i=1
i=1
hi – уровень внутреннего узла ki (или его расстояние от корня + 1);
hi – уровень внешнего узла di.
Среднюю взвешенную длину пути можно назвать «ценой» дерева поиска, так как она является мерой ожидаемого количества затрат
на поиск. Дерево поиска, структура которого дает минимальную цену
для всех деревьев с заданным множеством ключей ki и вероятностями
pi и qi обращений, называется оптимальным деревом.
Для нахождения оптимального дерева не обязательно, чтобы
сумма всех р и Q равнялась 1. На самом деле значения вероятностей
обычно находятся с помощью экспериментов, в которых подсчитываются обращения к узлам.
8.5. Задания на лабораторную работу 7
«Бинарные деревья поиска»
Организовать работу с деревом поиска в меню, предлагающем
пользователю пункты просмотра дерева, добавления нового элемента,
поиск узла по ключу, а также пункты, связанные со своим вариантом
лабораторной работы.
Вариант 1
1. Описать неупорядоченный массив структур, содержащий информацию согласно вашему варианту предыдущей лабораторной работы (бинарный поиск).
Построить дерево поиска по заданному полю поиска.
Вывести дерево на экран в вертикальном виде.
Описать функцию поиска записи по заданной фамилии.
89
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Выполнить симметричный обход дерева.
2. Построить бинарное дерево поиска из чисел входного потока.
Повторяющиеся значения в дерево не добавлять. Вывести дерево на
экран. Вычислить количество листьев в дереве.
Вариант 2
1. Описать неупорядоченный массив структур, содержащий информацию согласно вашему варианту предыдущей лабораторной работы (бинарный поиск).
Построить дерево поиска по заданному полю поиска.
Вывести дерево на экран в вертикальном виде.
Описать функцию поиска записи по заданной фамилии.
Выполнить симметричный обход дерева.
2. Построить бинарное дерево поиска из чисел входного потока.
Повторяющиеся значения узлов указывать в виде счетчика. Вывести
дерево на экран. Вычислить количество вершин в дереве.
Вариант 3
1. Описать неупорядоченный массив структур, содержащий информацию согласно вашему варианту предыдущей лабораторной работы (бинарный поиск).
Построить дерево поиска по заданному полю поиска.
Вывести дерево на экран в вертикальном виде.
Описать функцию поиска записи по заданной фамилии.
Выполнить симметричный обход дерева.
2. Построить бинарное дерево поиска из уникальных чисел входного потока. Вывести дерево на экран. Реализовать удаление листовой
вершины по ее значению, если такая вершина имеется в дереве.
Вариант 4
1. Описать неупорядоченный массив структур, содержащий информацию согласно вашему варианту предыдущей лабораторной работы (бинарный поиск).
90
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Построить дерево поиска по заданному полю поиска.
Вывести дерево на экран в вертикальном виде.
Описать функцию поиска записи по заданной фамилии.
Выполнить симметричный обход дерева.
2. Построить бинарное дерево поиска из уникальных чисел
входного потока. Вывести дерево на экран. Реализовать удаление
внутренней вершины, имеющей единственного потомка (левого или
правого), по ее значению.
Вариант 5
1. Описать неупорядоченный массив структур, содержащий информацию согласно вашему варианту предыдущей лабораторной работы (бинарный поиск).
Построить дерево поиска по заданному полю поиска.
Вывести дерево на экран в вертикальном виде.
Описать функцию поиска записи по заданной фамилии.
Выполнить симметричный обход дерева.
2. В дереве (п. 1) вычислить количество вершин на заданном
уровне. Номер уровня запрашивается с клавиатуры. Корень находится на нулевом уровне.
Вариант 6
1. Описать неупорядоченный массив структур, содержащий информацию согласно вашему варианту предыдущей лабораторной работы (бинарный поиск).
Построить дерево поиска по заданному полю поиска.
Вывести дерево на экран в вертикальном виде.
Описать функцию поиска записи по заданной фамилии.
Выполнить симметричный обход дерева.
2. В дереве (п. 1) вычислить количество листьев. Использовать
для этого рекурсивную функцию.
91
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Вариант 7
1. Описать неупорядоченный массив структур, содержащий информацию согласно вашему варианту предыдущей лабораторной работы (бинарный поиск).
Построить дерево поиска по строковому полю поиска, например, по фамилии или по названию.
Вывести дерево на экран в вертикальном виде.
Описать функцию поиска записи по заданной фамилии.
Выполнить симметричный обход дерева.
2. В дереве (п. 1) вычислить количество вершин дерева, содержащих слова, которые начинаются на заданную букву. Букву запросить с клавиатуры.
92
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
9. ПЕРЕЧЕНЬ ЭКЗАМЕНАЦИОННЫХ ВОПРОСОВ 1 ЧАСТИ
КУРСА «СТРУКТУРЫ И АЛГОРИТМЫ ОБРАБОТКИ ДАННЫХ»
1. Данные. Типизация данных. Логическая и физическая структура.
2. Статические и динамические структуры данных.
3. Классификация динамических структур данных.
4. Указатели. Динамическая память. Инициализация указателей.
5. Указатели. Операции с указателями. Длины указателей.
6. Потоки ввода – вывода. Иерархия классов ввода – вывода.
Стандартные объекты ввода – вывода.
7. Форматирование данных. Манипуляторы вывода.
8. Символьный ввод – вывод.
9. Файловые потоки в С++. Создание и чтение файлов.
10. Линейные односвязные списки. Реализация списков в С++:
описание и создание списка.
11. Операции над динамическими списками: просмотр, поиск по
значению.
12. Стек. Программная реализация стека в С++. Использование
стека: анализатор скобок.
13. Использование стека при вычислении выражения в постфиксной форме.
14. Постфиксная форма записи выражений. Метод стека с приоритетами.
15. Очередь как структура данных. Операции над очередью.
16. Циклические списки. Операции обработки циклических
списков: поиск узла по значению, удаление узла по значению.
17. Двусвязные списки. Операции обработки двусвязных списков: создание списка, просмотр.
18. Двусвязные списки. Операции обработки двусвязных списков: поиск узла по значению, удаление узла по значению.
93
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
19. Дек как динамическая структура данных. Описание типа дека. Операции над деком.
20. Рекурсия. Основные принципы организации рекурсивных алгоритмов. Примеры.
21. Классификация методов поиска в основной памяти. Линейный поиск. Бинарный поиск.
22. Деревья. Основные определения. Полное бинарное дерево.
23. Бинарные деревья поиска. Принцип организации дерева, построение.
24. Операции над бинарными деревьями поиска: добавление и
поиск узла по значению.
25. Удаление узла из дерева поиска по значению.
26. Операции над динамическими списками: удаление одного
или нескольких узлов из списка по значению.
27. Методы обхода деревьев. Рекурсивные функции обхода.
28. Сбалансированные двоичные АВЛ – деревья. Деревья Фибоначчи.
29. Сбалансированные АВЛ – деревья. Включение и исключение
вершины из сбалансированного дерева.
30. Поддержка сбалансированности в АВЛ – деревьях.
31. Циклические списки. Операции обработки циклических
списков: создание, просмотр.
32. Оптимальные деревья поиска. Взвешенная длина пути.
94
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
10. КУРСОВОЕ ПРОЕКТИРОВАНИЕ
10.1 Общие требования
Курсовая работа по курсу «Структуры и алгоритмы обработки
данных» должна включать законченную и протестированную программу и пояснительную записку.
Пояснительная записка должна иметь следующую структуру:
– титульный лист установленного образца (Приложение А) с
указанием классификационного кода (Приложение В);
– техническое задание (Приложение Б);
– содержание курсовой работы (Приложение Г).
В графической части курсового проекта могут быть представлены следующие результаты:
– обобщенная структура всей программы, показывающая функциональное назначение отдельных частей (функций) программы;
– блок-схемы каждой функции, реализующие основные алгоритмы обработки структур данных;
– результаты работы программы, показывающие наиболее типичные результаты.
Пояснительная записка должна быть оформлен на компьютере с
использованием текстового редактора, например, MS Word (шрифт
Times New Roman, размер 12, межстрочный интервал полуторный,
между абзацами интервал отсутствует, наличие красной строки 1,
25 мм, выравнивание по обоим краям текста).
Отчет о курсовой работе должен содержать обязательный перечень пунктов (описание разделов пояснительной записки рассмотрено в Приложении Г). Страницы отчета должны быть пронумерованы.
Пояснительная записка начинается с введения, которое содержит краткое описание проблемы вопроса и собственно постановку
задачи, которую необходимо решить.
В отчет должна быть включена теоретическая часть по теме курсовой работы, объем которой составляет 2-5 страниц. Здесь рассмат95
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
риваются основные понятия, определения, операции над структурами
данных, которые будут реализовываться в курсовой работе.
В разделе «Спецификации структур данных» должны быть описаны все структуры, классы с подробными комментариями к полям и
прототипам функций, раскрывающими смысл всех используемых параметров.
В разделе «Тестирование» необходимо привести внешний вид
приложения, вид экранного меню и результаты выполнения его отдельных пунктов.
В Приложении пояснительной записки следует привести программный код всей задачи. Для печати текста программы в Приложении можно использовать размер шрифта в 10 пт и одинарный междустрочный интервал.
10.2. Этапы выполнения курсовой работы
Курсовая работа по дисциплине «Структуры и алгоритмы обработки данных» является итогом изучения названного курса и имеет
целью закрепление навыков, приобретенных студентами на теоретических, практических занятиях и лабораторных работах по данному
курсу.
Спектр заданий касается рассмотрения базовых алгоритмов сортировки, поиска как во внешней, так и во внутренней памяти компьютера, организации и обработки динамических списочных и древовидных структур, основ объектно-ориентированного программирования.
Студент получает задание согласно варианту, в котором сформулирована постановка задачи. На начальном этапе студент самостоятельно или с помощью преподавателя уточняет задание, выбирает
наиболее оптимальные структуры данных, которые будут подвергаться обработке, или структуру класса, то есть состав данных – членов класса и функций – членов класса, если его задание касается создания класса.
96
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Перед этапом программной реализации студент должен досконально проработать теорию вопроса по лекциям данного курса, а
также с использованием дополнительной литературы, список которой
приведен в конце данного пособия. Теоретическая часть пояснительной записки должна содержать проработку вопроса.
На следующем этапе студент разбивает большую задачу курсовой работы на отдельные, более мелкие подзадачи и приступает к их
реализации на алгоритмическом языке С++. Рекомендуется каждую
подзадачу реализовать в отдельной функции. Для каждой такой
функции должен быть создан алгоритм, показывающий логику выполнения подзадачи. Все алгоритмы, построенные согласно ГОСТ,
затем будут включены в пояснительную записку.
Если в программе применяется построение класса, то следует
отделить описание класса от его реализации и от файла-приложения.
Выполнить раздельную компиляцию. Работу программы, состоящей
из нескольких файлов, организовать в проекте Project.
Курсовая работа должна быть оформлена в виде самостоятельного приложения с применением меню, в котором предусмотрены
всевозможные пункты обработки данных согласно варианту задания.
Следует обратить внимание на создание дружественного интерфейса
с пользователем, а также защиту от неверных действий пользователя
с выводом сообщений об ошибках.
97
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
БИБЛИОГРАФИЧЕСКИЙ СПИСОК
1. Байдуров, А. Динамический список, его реализация и применение C++ [Электронный ресурс] / А. Байдуров. – 18 марта 2009. –
Режим доступа : http : //www.codenet.ru/progr/cpp/dlist.php. – Загл. с
экрана.
2. Вирт, Н. Алгоритмы и структуры данных / Н. Вирт. – М. :
Мир, 1989.
3. Гагарина, Л. Г. Алгоритмы и структуры данных : учебное пособие / Л. Г. Гагарина. – М. : Финансы и статистика : ИНФРА-М,
2009. – 304 с.
4. Кнут, Д. Искусство программирования / Д. Кнут. – М. : Мир,
2000. – Т. 1, 3.
5. Кондратьева, С. Д. Введение в структуры данных : лекции и
упражнения по курсу / С. Д. Кондратьева. – М. : Издательство МГТУ
им. Н. Э. Баумана, 2000. – 376 с.
6. Кузнецов, С. Д. Структуры данных, методы сортировки и поиска / С. Д. Кузнецов. – М. : МГУ, 1998.
7. Лэнгсам, Й. Структуры данных для персональных ЭВМ
/ Й. Лэнгсам, М. Огенстайн, А. Тененбаум. – М. : Мир, 1989.
8. Павловская, Т. А. С/С++. Программирование на языке высокого уровня / Т. А. Павловская. – СПб. : Питер, 2002. – 464 с.
9. Подбельский, В. В. Язык С++ : учебное пособие / В. В. Подбельский. – 5-е изд. – М. : Финансы и статистика, 2003. – 560 с.
10. Свами, М. Графы, сети и алгоритмы / М. Свами, К. Тхуласираман. – М. : Мир, 1984. – 454 с.
11. Сэджвик, Р. Фундаментальные алгоритмы на С++. Анализ.
Структуры данных. Сортировка. Поиск / Р. Сэджвик. – М. : Издательство «ДиаСофт», 2001. – 688 с.
12. Топп, У. Структуры данных в С++ / У. Топп, У. Форд. – М. :
ЗАО «Издательство БИНОМ», 2000. – 816 с.
13. Фейсон, Т. Объектно-ориентированное программирование на
Borland C++ 4.5 / Т. Фейсон. – М. : Мир, 1998.
14. Шилдт, Г. Самоучитель С++ / Г. Шилдт. – М. : Мир, 1998.
98
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
ПРИЛОЖЕНИЕ А
(обязательное)
Образец оформления титульного листа курсового проекта
Министерство образования и науки Российской Федерации
Орский гуманитарно-технологический институт (филиал)
Государственного образовательного учреждения
высшего профессионального образования
“ОРЕНБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ”
Механико-технологический факультет
Кафедра программного обеспечения
КУРСОВАЯ РАБОТА
(16 пт)
по дисциплине «Структуры и алгоритмы обработки данных»
Программная реализация класса обработки динамических
двусвязных списков
(16 пт)
Пояснительная записка
ОГТИ (филиал) ГОУ ОГУ 220400.5111.12 ПЗ
Руководитель:
_____________ Кузниченко М. А.
"____”______________ 2011 г.
Исполнитель:
студент гр. 09ПО
_______________ Иванов Д. И.
"____"______________ 2011 г.
Орск 2011
Примечание – Остальные надписи размером 14 пт.
99
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
ПРИЛОЖЕНИЕ Б
(обязательное)
Образец оформления бланка технического задания
на курсовой проект
Министерство образования и науки Российской Федерации
Орский гуманитарно-технологический институт (филиал)
Государственного образовательного учреждения
высшего профессионального образования
“ОРЕНБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ”
Механико-технологический факультет
Кафедра программного обеспечения
Задание на курсовую работу
Программная реализация класса обработки динамических
двусвязных списков
Разработать программу на алгоритмическом языке С++. Предусмотреть:
1) удобный пользовательский интерфейс с использованием меню;
2) описать и обосновать выбранные структуры данных;
3) реализовать основные операции над динамическим списком;
4) организовать работу с файловыми потоками;
5) оформить программный продукт в виде проекта *.prj;
6) протестировать программный продукт.
Дата выдачи задания "____"_____________ 20 __ г.
Руководитель
Кузниченко М. А.
Исполнитель
студент группы 09ПО1
Иванов Д. И.
Срок защиты "____"____________ 20 __ г.
100
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
ПРИЛОЖЕНИЕ В
(обязательное)
Правила присвоения классификационного кода
101
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
ПРИЛОЖЕНИЕ Г
(обязательное)
Образец оформления содержания
СОДЕРЖАНИЕ
Введение
1. Теоретическая часть
1.1. Подраздел теоретической части
1.2. Подраздел теоретической части
1.3. и т. д.
2. Спецификация и обоснование структур данных.
3. Практическая часть
3.1. Описание структуры программы
3.2. Блок-схемы алгоритмов основных функций
3.3. Описание файлов проекта
4. Тестирование
Список источников
Приложение
102
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Учебное издание
Марина Анатольевна Кузниченко
ДИНАМИЧЕСКИЕ СТРУКТУРЫ ДАННЫХ
Учебное пособие
Ведущий редактор
Е. В. Кондаева
Старший корректор
Е. А. Феонова
Ведущий инженер
Г. А. Чумак
Подписано в печать 08.04.2011 г.
Формат 60х84 1/16. Усл. печ. 4,9.
Тираж 100 экз. Заказ ________
Издательство Орского гуманитарно-технологического института
(филиала) Государственного образовательного учреждения
высшего профессионального образования
«Оренбургский государственный университет»
462403, г. Орск Оренбургской обл., пр. Мира, 15 А
Документ
Категория
Информатика и программирование
Просмотров
443
Размер файла
1 064 Кб
Теги
1618, данных, структура, динамическое
1/--страниц
Пожаловаться на содержимое документа