В учебном пособии рассматриваются вопросы внутримашинного представления данных и структур разных типов, алгоритмы внутренней и внешней сортировки, организации и обработки динамических структур данных. <...> Любая программа, записанная на любом языке программирования, использующая и изменяющая данные и структуры данных, представляет собой один из способов записи алгоритма - последовательности действий, которую нужно выполнить для получения результата. <...> В третьей главе проиллюстрирован ряд алгоритмов внешней сортировки: прямое слияние, естественное слияние и сбалансированное многопутевое слияние. <...> Четвертая глава вводит понятие абстрактных типов данных. <...> Шестая глава посвящена линейным списковым структурам: односвязный и двусвязный список, стек, дек, очередь. <...> Встроенные типы данных Обычно в состав встроенных типов данных включаются такие типы, операции над значениями которых напрямую или, по крайней мере, достаточно эффективно поддерживаются командами компьютеров. <...> В соответствии с этим, в традиционный набор встроенных типов обычно входят следующие: 1. <...> Тип CHARACTER (или CHAR) в разных языках - это либо набор печатных символов из алфавита, зафиксированного в описании языка (для большинства языков англоязычного происхождения этот алфавит соответствует кодовому набору ASCII); либо произвольная комбинация нулей и единиц, размещаемых в одном байте. <...> В первой интерпретации (свойственной языкам линии Паскаль) для значений типа CHAR определены только операции сравнения в соответствии с принятым алфавитом. <...> Во второй интерпретации (свойственной языкам линии Си) литеральными константами типа CHAR по-прежнему могут быть печатные символы из принятого в языке алфавита, но возможно использование и числовых констант, задающих желаемое содержимое байта. <...> В этом случае, как правило, над значениями типа CHAR возможно выполнение не только операций сравнения, но и операций целочисленной арифметики. <...> В языках линии Си прямая <...>
Структуры_и_алгоритмы_обработки_данных._Часть_1_.pdf
УДК 004.4(07)
Б 282
Рецензенты:
кафедра технологий обработки и защиты информации факультета компьютерных наук
Воронежского государственного университета;
канд. техн. наук, доц. Гончаров И.В.
Батищев, Р.В.
Б282 Структуры и алгоритмы обработки данных. Часть 1 [Текст]: учеб._пос. / Р.В. Батищев. -
Липецк: Изд-во Липецкого государственного технического университета, 2014. – 89 с.
ISBN
ISBN 41
Учебное пособие предназначено для студентов, изучающих курс "Структуры и
алгоритмы обработки данных" и представляет собой первую часть практического руководства к
проведению лабораторных работ по дисциплине "Структуры и алгоритмы обработки данных". В
учебном пособии рассматриваются вопросы внутримашинного представления данных и
структур разных типов, алгоритмы внутренней и внешней сортировки, организации и обработки
динамических структур данных.
Пособие содержит теоретический материал с иллюстрациями алгоритмов и примерами
программ на языке программирования высокого уровня "Си".
Ил. 23. Библиогр. 8 назв.
Печатается по решению Редакционно-издательского совета.
ISBN
ISBN 41
© ФГБОУ ВПО "Липецкий
государственный технический
университет", 2014
© Батищев Р.В., 2014
Стр.3
СОДЕРЖАНИЕ
ВВЕДЕНИЕ ...................................................................................................
1. Типы данных и структуры данных ............................................................
1.1. Встроенные типы данных.....................................................................
5
7
8
1.2. Уточняемые типы данных ................................................................... 12
1.3. Перечисляемые типы данных .............................................................. 13
1.4. Конструируемые типы данных............................................................ 14
1.4.1. Массивы ........................................................................................... 14
1.4.2. Записи ............................................................................................... 16
1.4.3. Множества ........................................................................................ 17
1.5. Указатели ............................................................................................ 17
1.6. Структуры данных .............................................................................. 21
2. Алгоритмы внутренней сортировки .......................................................... 24
2.1. Сортировка выбором ........................................................................... 26
2.2. Сортировка включением ..................................................................... 27
2.3. Обменная сортировка (сортировка перестановками) .......................... 28
2.4. Метод Шелла ....................................................................................... 30
2.5. Сортировка разделением (быстрая сортировка) .................................. 32
2.6. Сортировка двоичными включениями ................................................ 33
2.7. Сортировка со слиянием ..................................................................... 35
3. Алгоритмы внешней сортировки ............................................................... 37
3.1. Прямое слияние ................................................................................... 39
3.2. Естественное слияние.......................................................................... 40
3.3. Сбалансированное многопутевое слияние .......................................... 42
4. Абстрактные типы данных ........................................................................ 44
4.1. Представление типа............................................................................. 45
4.2. Реализация типа................................................................................... 46
4.3. Инкапсуляция ...................................................................................... 46
4.4. Наследование типов ............................................................................ 47
4.5. Разновидности полиморфизма ............................................................ 50
Стр.4
5. Работа с динамической памятью................................................................ 51
5.1. Представление объектов в оперативной памяти, указатели ................ 55
5.2. Динамические структуры .................................................................... 60
6. Линейные списковые структуры................................................................ 65
6.1. Односвязный список ........................................................................... 65
6.1.1. Создание элемента списка ................................................................ 66
6.1.2. Добавление узла ............................................................................... 67
6.1.3. Проход по списку ............................................................................. 68
6.1.4. Поиск узла в списке .......................................................................... 69
6.1.5. Алфавитно-частотный словарь ......................................................... 70
6.1.6. Удаление узла ................................................................................... 71
6.2. Двусвязный список.............................................................................. 72
6.2.1. Операции с двусвязным списком ..................................................... 73
6.3. Циклические списки ............................................................................ 76
6.4. Стек, очередь, дек................................................................................ 76
6.4.1. Стек .................................................................................................. 76
6.4.2. Реализация стека с помощью массива .............................................. 78
6.4.3. Обработка символьной строки с помощью стека ............................. 79
6.4.4. Реализация стека с помощью списка ................................................ 81
6.4.5. Системный стек в программах ......................................................... 82
6.4.6. Очередь............................................................................................. 83
6.4.7. Реализация очереди с помощью массива.......................................... 83
6.4.8. Реализация очереди с помощью списка ........................................... 85
6.4.9. Дек .................................................................................................... 86
7. Библиографический список ................................................................... 88
Стр.5