Типы структур данных
Благонравов А. А. Материальная часть стрелкового оружия. В 2-х т, Воениздат, 1946.
Богданов И. Р., Груздина Н.Ф., Захваткин С. С.. Старостин К. И. Основания стрелкового оружия. Воениздат, 1953.
Боевой устав горнострелковых подразделений. Воениздат, 1944.
Боевой устав НКВД. Воениздат, 1944 Боевой устав пехоты. Воениздат, 1944.
Жамков Ф. И. Начальная подготовка стрелка-спортсмена. Ц.С. Динамо. Москва, 1979.
Как стать стрелком-спортсменом. Сборник статей ведущих стрелков СССР. ДОСААФ, 1968.
Кириллов М. В. Основания устройства и проектирования стрелкового оружия. Пензенское высшее артиллерийское училище, 1963.
Конспекты лекций снайпера Василия Зайцева.
Листовки инструкции маршала В. Чуйкова.
Материалы фронтовых газет периода Великой Отечественной войны
Основы стрельбы из пехотного оружия. Воениздат, 1946.
Основы стрельбы из стрелкового оружия. Воениздат, 1970.
Отдельные инструкции по снайперскому делу.
Руководство по ремонту 7,62-мм винтовок и карабинов Воениздат, 1958.
Федоров В. Г. Эволюция стрелкового оружия. Воениздат, 1939.
Оглавление
Введение 6
1. Типы структур данных 7
2. Стек 7
2.1. Применения стека 9
2.1.1. Программный стек 9
2.1.2. Реализация рекурсии 10
2.1.2.1. Обход шахматной доски ходом коня 11
2.1.2.1. Вычисление определенного интеграла 13
2.1.3. Польская инверсная запись (ПОЛИЗ) 15
2.1.4. Вычисление выражения, представленного в ПОЛИЗ 19
Контрольные вопросы 20
3. Очередь 20
Контрольные вопросы 22
4. Массивы 22
4.1. Размещение прямоугольных массивов в последовательной памяти 22
4.2. Метод Айлиффа 23
Контрольные вопросы 24
5. Списочные структуры 24
5.1. Односвязный линейный список 25
5.1.1. Представление односвязного списка 25
5.1.2. Операции над односвязным списком 25
5.1.3. Голова списка 27
5.1.4 Циклический список 27
5.1.5. Пример. Сложение многочленов 28
5.2. Двусвязный линейный список 30
5.3. Ортогональные списки 31
5.4. Списки общего вида 32
5.4.1. Пример. Топологическая сортировка. 34
5.5. Стек свободного пространства 39
5.6. Обслуживание свободного пространства 40
5.6.1. Счетчик ссылок 40
5.6.2. Сбор мусора 40
Контрольные вопросы 41
6. Множества 42
Контрольные вопросы 46
7. Деревья 47
7.1. Бинарные деревья 48
7.2. Обход бинарного дерева 48
7.3. Прошитые деревья 52
7.4. Другие представления бинарных деревьев 53
7.5. Представление деревьев общего вида 54
7.5.1. Представление деревьев общего вида бинарными деревьями 55
Контрольные вопросы 55
8. Конечный автомат 56
Контрольные вопросы 59
9. Таблицы 59
9.1. Последовательные таблицы 60
Контрольные вопросы 61
9.2. Сортированные таблицы 61
9.2.1. Алгоритмы поиска в сортированной таблице 61
9.2.1.1. Бинарный поиск (дихотомия) 61
9.2.2. Вставка и удаление в сортированной таблице 63
9.2.3. Оценка трудоемкости сортировки 64
9.2.4. Внутренняя сортировка 64
9.2.4.1. Сортировка подсчетом 65
9.2.4.2. Сортировка простым выбором 65
9.2.4.3. Квадратичный выбор 66
9.2.4.4. Выбор из дерева 67
9.2.4.5. Сортировка простыми вставками 67
9.2.4.6. Сортировка методом "пузырька" 68
9.2.4.7. Сортировка слиянием 69
9.2.4.8. Сортировка фон Неймана 70
9.2.4.9. Сортировка Хоара (1962 г.) 72
9.2.4.10. Двоичная поразрядная сортировка 73
9.2.4.11. Цифровая поразрядная сортировка 75
9.2.1. Внешняя сортировка 77
9.2.1.1. Многопутевое слияние и выбор с замещением 78
9.2.1.2. Многофазное слияние 79
9.2.1.3. Фибоначчиево слияние 80
9.2.1.4. Каскадное слияние 82
9.2.1.5. Сортировка в одном файле 83
Контрольные вопросы 85
9.3. Древовидные таблицы 86
9.3.1. Оценка трудоемкости поиска в случайном дереве 89
9.3.2. Оптимальные деревья 90
9.3.3. Сбалансированные деревья 91
9.3.4.1. Поддержание балансировки 93
9.3.5. Представление линейных списков деревьями 94
9.3.6. В-деревья 95
Контрольные вопросы 98
9.4. Таблицы с прямым доступом 99
9.5. Рассеянные таблицы (Hash) 99
9.5.1. Анализ трудоемкости операций над рассеянной таблицей 101
Контрольные вопросы 102
Литература 104
Введение
Основное содержание курса "Структуры и алгоритмы обработки данных" составляет изложение типовых структур данных, методов их хранения и алгоритмов работы с ними. Изложенные методы и средства, по нашему убеждению, должны входить в инструментарий, которым должен владеть каждый профессиональный программист. К изучению курса можно приступать после того, как прослушаны курсы, посвященные алгоритмическим языкам и понятиям объектно-ориентированного программирования.
В пособии рассмотрены такие структуры, как стек, очередь, массив. В разделе, посвященном списочным структурам, описаны методы представления линейных и нелинейных списков, в частности, деревьев. Значительное внимание уделено методам представления таблиц. Рассмотрены последовательные, сортированные, древовидные и рассеянные таблицы. Этот раздел, по сути, является введением в курс ”Базы данных” и содержит описание их методов физической организации. Отдельный раздел посвящен методам сортировки, как внутренней, так и внешней.
Для каждой структуры данных или для алгоритма работы с ней анализируются те возможности, которые они предлагают и те недостатки, которые они в себе несут. Для алгоритмов, как правило, дана оценка порядка быстродействия. Большинство алгоритмов иллюстрируется текстами их программной реализации на языке С++. Реализация алгоритмов зачастую приводится в упрощенной трактовке, чтобы не загромождать изложение техническими деталями. Так, например, в разделе ”Внутренняя сортировка” рассматривается, в основном, сортировка целых чисел. Все программные тексты отлажены в среде Borland Cbuilder 5.
Типы структур данных
Любой набор знаков, рассматриваемый безотносительно к его содержательному смыслу, называют данными. Данные обычно изображают некоторую информацию, которую можно получить, если известен смысл, приписываемый данным. Однако в программировании обычно приходится иметь дело именно с данными. Например, разрабатывая систему хранения и поиска текстов, программист может и не знать их содержания. Его задача - обеспечить экономное использование памяти и быстрый поиск требуемых текстов по заданным признакам. Для решения этой задачи достаточно знать лишь количественные характеристики текстов, рассматриваемых как данные. Вообще, компьютеры выполняют только обработку данных, которая заинтересованным лицам представляется как обработка информации.
Совокупности данных, организованные некоторым образом, называются структурами данных. Структура данных определяется набором элементов и отношениями между ними. Структура данных в программе отображается в ту или иную структуру хранения. Так, например, стек может храниться в массиве или линейном списке; массив может быть представлен как последовательность элементов, ортогональный список или дерево и т.д. В настоящем пособии рассматриваются типовые структуры данных, такие как стек, очередь, массив, множество, списки – линейные и нелинейные, различные модификации деревьев; особое внимание уделено четырем базисным методам представления таблиц.
Стек
Стек – одномерный, динамически изменяемый набор данных. Новый элемент всегда добавляют к одному и тому же концу набора, называемому вершиной стека. Удаление элемента допустимо тоже только из вершины стека. Таким образом, над стеком возможны только две операции: поместить в стек и взять из стека. Стек называют также магазином по аналогии с магазином огнестрельного оружия, в котором патрон последним вставленный в магазин, первым поступает в ствол. По этой же причине дисциплину работы со стеком называют "последний пришел, первый ушел". В английском языке используется аббревиатура LIFO (Last In, First Out). Стек может быть реализован в массиве или в списке. Реализация класса STACK, использующего массив, приведена ниже.
// Определение класса
const int MAXSTACK=20; // максимальное число элементов в стеке
class STACK {
// элементы стека -целые числа
private:
int A[MAXSTACK]; // массив для элементов стека
int v; // указатель на вершину стека
// (индекс элемента на вершине стека)
bool OverFlow; // индикатор переполнения стека
bool Empty; // признак "стек пуст"
public:
STACK(); // конструктор
void Push(int NewElement); // поместить в стек
int Pop(); // вытолкнуть из стека
// возвращает выталкиваемый элемент
bool StackOwerFlow(){return OverFlow;}; // Стек переполнен ?
bool StackIsEmpty(){return Empty;}; // стек пуст ?
AnsiString ToString(); // создать строку по содержимому
// стека для показа
};
// Методы класса STACK
#include "Stack.h"
//---------------------------------
STACK::STACK(){ // конструктор
v=-1; // стек пуст
OverFlow=false; // стек не переполнен
Empty=true; // стек пуст
}
//----------------------------------
void STACK::Push(int NewElement){
// поместить в стек значение NewElement
if(v>=MAXSTACK){
// переполнение
OverFlow=true;
Дата добавления: 2014-12-02; просмотров: 1175;