Новинки  ·  Как купить книги  ·  Доставка  ·  Контакты



Ваша корзина
книг: 0 Купить
книги
сумма: 0грн.

 

 


Каталог книг


Книги по бизнесу
  · Книги банки,деньги,кредит
  · Книги по бизнесу
  · Книги по бухучету
  · Книги инвестиционный бизнес
  · Книги коммерция и продажи
  · Книги по маркетингу и рекламе
  · Книги по менеджменту
  · Книги по праву
  · Книги по предпринимательству
  · Книги по финансам
  · Книги по экономике
  · Книги по экономической теории
Книги компьютерные
  · Книги CAD-ы
  · Книги 3d MAX
  · Книги ACCESS
  · Книги Adobe
  · Книги Assembler
  · Книги Basic
  · Книги C, C++,С#
  · Книги Delphi
  · Книги EXCEL
  · Книги HTML,XML, Dynamic, CSS
  · Книги Java
  · Книги JavaScript
  · Книги Linux
  · Книги MAC
  · Книги Maya
  · Книги OFFICE
  · Книги Oracle
  · Книги Pascal
  · Книги Perl
  · Книги PHP
  · Книги SQL
  · Книги UML
  · Книги Unix
  · Книги VBA
  · Книги Visual Studio
  · Книги WEB дизайн
  · Книги Windows 2000
  · Книги Windows Server
  · Книги Windows Vista
  · Книги Windows XP
  · Книги WORD
  · Книги Алгоритмы
  · Книги 1C Учет
  · Книги Издательские системы
  · Книги по информатике
  · Книги по компьютерной безопасности
  · Книги по компьютерному железу
  · Книги компьютерные сети
  · Книги мультимедиа
  · Книги Нейронные сети
  · Книги ООП
  · Книги Примочки программирования
  · Книги по программированию для WEB
  · Книги Прочая графика
  · Книги прочая разработка
  · Книги прочие CAD
  · Книги прочие базы данных
  · Книги прочие ОС
  · Книги прочие офисное ПО
  · Книги самоучители
  · Книги Цифровое фото
  · Книги электронная коммерция
  · Книги Corel
  · Книги Windows 7
  · Книги Прочее для интернет
  · Книги SEO оптимизация и продвижение
  · Книги SolidWorks
Книги по психологии
  · Книги по психоанализу
  · Книги по психологии
  · Книги по психологии бизнеса
  · Книги психология женский клуб
  · Книги психология НЛП
  · Книги психология общая
  · Книги психология популярная
  · Книги психология прикладная
  · Книги психология прочее
  · Книги психология психотерапия
  · Книги психология социальная
  · Книги психология тест
  · Книги психология тренинг
Знаменитые люди
Книги о детях
Естественные науки

On-line консультант
SiteHeart
ICQ:  603-221-314
E-mail:
kniga@bizkniga.com.ua




Принимаем к оплате:
Оплатить WebMoney
Оплатить WebMoney
Оплатить WebMoney
Оплатить WebMoney
Оплатить WebMoney

Реклама

 

 
SiteHeart
     Структуры данных и алгоритмы в Java. Классика Computers Science. 2-е изд. Лафоре почтой  
 
Share |
Структуры данных и алгоритмы в Java. Классика Computers Science. 2-е изд. Лафоре
240.81 грн.
доставка УкрПочта бесплатно
 Заказать книгу Структуры данных и алгоритмы в Java. Классика Computers Science. 2-е изд. Лафоре  Купить Структуры данных и алгоритмы в Java. Классика Computers Science. 2-е изд. Лафоре
SiteHeart
 2011г.
Количество страниц: 704

Второе издание одной из самых авторитетных книг Структуры данных и алгоритмы в Java. Классика Computers Science. 2-е изд. Лафоре  по программированию посвящено использованию структур данных и алгоритмов. Алгоритмы — это основа программирования, определяющая, каким образом разрабатываемое программное обеспечение будет использовать структуры данных. На четких и простых программных примерах автор объясняет эту сложную тему, предлагая читателям написать собственные программы и на практике освоить полученные знания. Рассматриваемые примеры написаны на языке Java, хотя для усвоения материала читателю не обязательно хорошо знать его — достаточно владеть любым языком программирования, например C++. Первая часть книги представляет собой введение в алгоритмизацию и структуры данных, а также содержит изложение основ объектно-ориентированного программирования. Следующие части посвящены различным алгоритмам и структурам данных, рассматриваемым от простого к сложному: сортировка, абстрактные типы данных, связанные списки, рекурсия, древовидные структуры данных, хеширование, пирамиды, графы. Приводятся рекомендации по использованию алгоритмов и выбору той или иной структуры данных в зависимости от поставленной задачи.

Оглавление книги

Структуры данных и алгоритмы в Java. Классика Computers Science. 2-е изд. Лафоре


Введение   . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  18
Второе издание   . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  18
Дополнительные темы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  18
Вопросы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  19
Упражнения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  19
Программные проекты   . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  19
О чем эта книга . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  19
Чем эта книга отличается от других   . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  20
Доступность   . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  20
Приложения Workshop . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  21
Примеры кода Java   . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  21
Для кого написана эта книга . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  22
Что необходимо знать читателю   . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  22
Необходимые программы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  22
Как организован материал книги . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  22
Вперед!   . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  24
Глава 1. Общие сведения   . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
Зачем нужны структуры данных и алгоритмы?   . . . . . . . . . . . . . . . . . . . . . . . . . . . .  25
Хранение реальных данных   . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  26
Инструментарий программиста   . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  26
Моделирование   . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  27
Обзор структур данных   . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  27
Алгоритмы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  28
Определения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  28
База данных . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  29
Запись   . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  29
Поле  . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  29
Ключ  . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  30
Объектно-ориентированное программирование . . . . . . . . . . . . . . . . . . . . . . . . . .  30
Недостатки процедурных языков   . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  30
Объекты в двух словах . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  31
Создание объектов   . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  32
Вызов методов объекта . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  33
Пример объектно-ориентированной программы . . . . . . . . . . . . . . . . . . . . . .  33
Наследование и полиморфизм   . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  36
Программотехника . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  37
Java для программистов C++   . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  37
В Java нет указателей   . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  37
Ввод/вывод . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  41
Вывод . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  41
Структуры данных библиотеки Java   . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  44
Итоги   . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  44
Вопросы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  45
Глава 2. Массивы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
Приложение Array Workshop . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  46
Вставка . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  48
Поиск   . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  48
Удаление   . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  49
Проблема дубликатов   . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  50
Не слишком быстро  . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  51
Поддержка массивов в Java   . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  52
Создание массива   . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  52
Обращение к элементам массива . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  52
Инициализация . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  53
Пример массива . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  53
Деление программы на классы   . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  56
Классы LowArray и LowArrayApp . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  58
Интерфейсы классов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  58
Не слишком удобно   . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  59
Кто чем занимается?  . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  59
Пример highArray.java   . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  60
Удобство пользователя . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  63
Абстракция   . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  63
Приложение Ordered Workshop   . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  63
Линейный поиск   . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  64
Двоичный поиск   . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  65
Реализация упорядоченного массива на языке Java   . . . . . . . . . . . . . . . . . . . . . . .  67
Двоичный поиск с методом find()   . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  67
Класс OrdArray   . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  69
Преимущества упорядоченных массивов   . . . . . . . . . . . . . . . . . . . . . . . . . . . .  72
Логарифмы   . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  72
Формула   . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  73
Операция, обратная возведению в степень   . . . . . . . . . . . . . . . . . . . . . . . . . .  74
Хранение объектов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  75
Класс Person   . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  75
Программа classDataArray.java . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  76
O-синтаксис   . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  79
Вставка в неупорядоченный массив: постоянная сложность . . . . . . . . . . . .  80
Линейный поиск: сложность пропорциональна N . . . . . . . . . . . . . . . . . . . . . .  80
Двоичный поиск: сложность пропорциональна log(N) . . . . . . . . . . . . . . . . . .  80
Константа не нужна   . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  81
Почему бы не использовать только массивы? . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  82
Итоги   . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  83
Вопросы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  84
Упражнения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  85
Программные проекты   . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  85
Глава 3. Простая сортировка   . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87
Как это делается? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  87
Пузырьковая сортировка   . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  89
Пример пузырьковой сортировки   . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  89
Приложение BubbleSort Workshop . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  91
Реализация пузырьковой сортировки на языке Java   . . . . . . . . . . . . . . . . . . .  94
Инварианты . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  97
Сложность пузырьковой сортировки   . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  97
Сортировка методом выбора . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  98
Пример сортировки методом выбора . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  98
Приложение SelectSort Workshop   . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  100
Реализация сортировки методом выбора на языке Java . . . . . . . . . . . . . . .  101
Инвариант   . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  103
Сложность сортировки методом выбора . . . . . . . . . . . . . . . . . . . . . . . . . . . .  103
Сортировка методом вставки . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  104
Пример сортировки методом вставки   . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  104
Приложение InsertSort Workshop . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  106
Сортировка 10 столбцов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  106
Реализация сортировки методом вставки на языке Java   . . . . . . . . . . . . . .  108
Инварианты сортировки методом вставки   . . . . . . . . . . . . . . . . . . . . . . . . . .  111
Сложность сортировки методом вставки . . . . . . . . . . . . . . . . . . . . . . . . . . . .  111
Сортировка объектов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  112
Реализация сортировки объектов на языке Java   . . . . . . . . . . . . . . . . . . . . .  112
Лексикографические сравнения   . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  115
Устойчивость сортировки . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  115
Сравнение простых алгоритмов сортировки . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  116
Итоги   . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  116
Вопросы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  117
Упражнения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  118
Программные проекты   . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  119
Глава 4. Стеки и очереди   . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  121
Другие структуры  . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  121
Инструменты программиста   . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  121
Ограничение доступа   . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  121
Абстракция   . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  122
Стеки   . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  122
Почтовая аналогия . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  123
Приложение Stack Workshop   . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  124
Реализация стека на языке Java   . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  126
Пример использования стека № 1. Перестановка букв в слове . . . . . . . . .  129
Пример № 2. Поиск парных скобок . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  132
Эффективность стеков   . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  136
Очереди . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  136
Приложение Queue Workshop . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  137
Циклическая очередь . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  140
Реализация очереди на языке Java . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  141
Эффективность очередей . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  146
Дек     . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  146
Приоритетные очереди . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  146
Приложение The PriorityQ Workshop   . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  148
Реализация приоритетной очереди на языке Java . . . . . . . . . . . . . . . . . . . .  150
Эффективность приоритетных очередей . . . . . . . . . . . . . . . . . . . . . . . . . . . .  152
Разбор арифметических выражений   . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  152
Постфиксная запись   . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  153
Преобразование инфиксной записи в постфиксную   . . . . . . . . . . . . . . . . . .  154
Как мы вычисляем результаты инфиксных выражений   . . . . . . . . . . . . . . . .  154
Вычисление результата постфиксного выражения   . . . . . . . . . . . . . . . . . . .  170
Итоги   . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  175
Вопросы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  176
Упражнения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  178
Программные проекты   . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  178
Глава 5. Связанные списки . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  180
Строение связанного списка   . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  180
Ссылки и базовые типы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  181
Отношения вместо конкретных позиций   . . . . . . . . . . . . . . . . . . . . . . . . . . . .  182
Приложение LinkList Workshop  . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  183
Вставка . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  183
Поиск   . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  184
Удаление   . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  184
Простой связанный список . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  185
Класс Link . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  185
Класс LinkList . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  186
Программа linkList.java   . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  190
Поиск и удаление заданных элементов   . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  192
Метод find() . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  195
Метод delete() . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  195
Другие методы   . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  196
Двусторонние списки   . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  196
Эффективность связанных списков   . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  200
Абстрактные типы данных . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  200
Реализация стека на базе связанного списка . . . . . . . . . . . . . . . . . . . . . . . .  201
Реализация очереди на базе связанного списка   . . . . . . . . . . . . . . . . . . . . .  204
Типы данных и абстракция   . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  207
Списки ADT   . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  208
Абстрактные типы данных как инструмент проектирования . . . . . . . . . . . .  209
Сортированные списки   . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  209
Реализация вставки элемента в сортированный список на языке Java   . .  211
Программа sortedList.java . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  212
Эффективность сортированных списков . . . . . . . . . . . . . . . . . . . . . . . . . . . .  214
Сортировка методом вставки   . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  215
Двусвязные списки   . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  217
Перебор . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  219
Вставка . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  219
Удаление   . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  221
Программа doublyLinked.java . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  222
Двусвязный список как база для построения дека . . . . . . . . . . . . . . . . . . . .  226
Итераторы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  226
Ссылка на элемент списка?   . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  227
Итератор   . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  227
Другие возможности итераторов   . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  228
Методы итераторов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  229
Программа interIterator.java . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  230
На что указывает итератор?  . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  236
Метод atEnd()   . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  236
Итеративные операции . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  236
Другие методы   . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  238
Итоги   . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  238
Вопросы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  239
Упражнения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  240
Программные проекты   . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  241
Глава 6. Рекурсия   . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  243
Треугольные числа . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  243
Вычисление n-го треугольного числа в цикле . . . . . . . . . . . . . . . . . . . . . . . .  244
Вычисление n-го треугольного числа с применением рекурсии   . . . . . . . .  245
Программа triangle.java . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  247
Что реально происходит?   . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  248
Характеристики рекурсивных методов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  249
Насколько эффективна рекурсия?   . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  250
Математическая индукция   . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  250
Факториал . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  250
Анаграммы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  252
Рекурсивный двоичный поиск   . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  257
Замена цикла рекурсией . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  258
Алгоритмы последовательного разделения   . . . . . . . . . . . . . . . . . . . . . . . . .  262
Ханойская башня   . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  262
Приложение Towers Workshop   . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  263
Перемещение поддеревьев  . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  264
Рекурсивный алгоритм   . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  264
Программа towers.java . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  266
Сортировка слиянием   . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  267
Слияние двух отсортированных массивов . . . . . . . . . . . . . . . . . . . . . . . . . . .  268
Сортировка слиянием   . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  270
Приложение MergeSort Workshop   . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  273
Программа mergeSort.java   . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  274
Устранение рекурсии . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  281
Что дальше?   . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  287
Интересные применения рекурсии . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  289
Возведение числа в степень . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  289
Задача о рюкзаке   . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  291
Комбинации и выбор команды . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  292
Итоги   . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  294
Вопросы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  295
Упражнения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  297
Программные проекты   . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  297
Глава 7. Нетривиальная сортировка   . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  299
Сортировка Шелла . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  299
Сортировка методом вставок: слишком много копирования . . . . . . . . . . .  300
N-сортировка   . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  300
Сокращение интервалов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  302
Приложение Shellsort Workshop . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  303
Реализация сортировки Шелла на языке Java . . . . . . . . . . . . . . . . . . . . . . . .  305
Другие интервальные последовательности   . . . . . . . . . . . . . . . . . . . . . . . . .  307
Эффективность сортировки Шелла   . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  308
Разбиение   . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  309
Приложение Partition Workshop   . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  309
Остановка и перестановка   . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  313
Быстрая сортировка   . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  316
Алгоритм быстрой сортировки   . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  317
Выбор опорного значения   . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  318
Приложение QuickSort1 Workshop . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  323
Вырожденное быстродействие O(N2
) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  327
Определение медианы по трем точкам   . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  328
Обработка малых подмассивов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  333
Устранение рекурсии . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  336
Поразрядная сортировка   . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  339
Проектирование программы   . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  340
Эффективность поразрядной сортировки . . . . . . . . . . . . . . . . . . . . . . . . . . .  340
Итоги   . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  341
Вопросы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  343
Упражнения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  344
Программные проекты   . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  344
Глава 8. Двоичные деревья   . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  346
Для чего нужны двоичные деревья?   . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  346
Медленная вставка в упорядоченном массиве . . . . . . . . . . . . . . . . . . . . . . .  346
Медленный поиск в связанном списке . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  347
Деревья приходят на помощь   . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  347
Что называется деревом? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  347
Терминология  . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  348
Аналогия   . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  351
Как работают двоичные деревья?   . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  352
Приложение Binary Tree Workshop . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  352
Представление деревьев в коде Java . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  354
Поиск узла . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  356
Поиск узла в приложении Workshop   . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  356
Реализация поиска узла на языке Java . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  358
Эффективность поиска по дереву . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  358
Вставка узла   . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  359
Вставка узла в приложении Workshop . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  359
Реализация вставки на языке Java   . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  359
Обход дерева   . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  361
Симметричный обход   . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  361
Реализация обхода на языке Java   . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  362
Обход дерева из трех узлов   . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  362
Обход дерева в приложении Workshop . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  363
Симметричный и обратный обход . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  365
Поиск минимума и максимума . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  367
Удаление узла . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  368
Случай 1. Удаляемый узел не имеет потомков   . . . . . . . . . . . . . . . . . . . . . . .  368
Случай 2. Удаляемый узел имеет одного потомка   . . . . . . . . . . . . . . . . . . . .  370
Случай 3. Удаляемый узел имеет двух потомков . . . . . . . . . . . . . . . . . . . . . .  372
Эффективность двоичных деревьев   . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  379
Представление дерева в виде массива   . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  381
Дубликаты ключей   . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  382
Полный код программы tree.java   . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  383
Код Хаффмана   . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  391
Коды символов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  391
Декодирование по дереву Хаффмана   . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  393
Построение дерева Хаффмана   . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  394
Кодирование сообщения   . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  396
Создание кода Хаффмана   . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  397
Итоги   . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  397
Вопросы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  399
Упражнения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  400
Программные проекты   . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  401
Глава 9. Красно-черные деревья  . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  403
Наш подход к изложению темы   . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  403
Концептуальное понимание . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  404
Нисходящая вставка   . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  404
Сбалансированные и несбалансированные деревья . . . . . . . . . . . . . . . . . . . . . .  404
Вырождение до O(N)   . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  405
Спасительный баланс   . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  406
Характеристики красно-черного дерева   . . . . . . . . . . . . . . . . . . . . . . . . . . . .  406
Исправление нарушений   . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  408
Работа с приложением RBTree Workshop . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  408
Щелчок на узле . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  409
Кнопка Start . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  409
Кнопка Ins   . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  409
Кнопка Del   . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  409
Кнопка Flip . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  410
Кнопка RoL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  410
Кнопка RoR   . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  410
Кнопка R/B . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  410
Текстовые сообщения   . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  410
Где кнопка Find?   . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  410
Эксперименты с приложением Workshop . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  411
Эксперимент 1. Вставка двух красных узлов . . . . . . . . . . . . . . . . . . . . . . . . .  411
Эксперимент 2. Повороты   . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  412
Эксперимент 3. Переключение цветов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  412
Эксперимент 4. Несбалансированное дерево   . . . . . . . . . . . . . . . . . . . . . . .  413
Эксперименты продолжаются   . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  414
Красно-черные правила и сбалансированные деревья . . . . . . . . . . . . . . . .  414
Пустые потомки   . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  415
Повороты . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  415
Простые повороты . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  416
Переходящий узел . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  416
Перемещения поддеревьев   . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  417
Люди и компьютеры . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  419
Вставка узла   . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  419
Общая схема процесса вставки . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  419
Переключения цветов при перемещении вниз   . . . . . . . . . . . . . . . . . . . . . . .  420
Повороты после вставки узла . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  422
Повороты при перемещении вниз . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  427
Удаление   . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  430
Эффективность красно-черных деревьев   . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  431
Реализация красно-черного дерева . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  431
Другие сбалансированные деревья   . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  432
Итоги   . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  433
Вопросы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  433
Упражнения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  435
Глава 10. Деревья 2-3-4   . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  436
Знакомство с деревьями 2-3-4   . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  436
Почему деревья 2-3-4 так называются? . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  437
Структура дерева 2-3-4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  438
Поиск в дереве 2-3-4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  439
Вставка . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  439
Разбиение узлов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  440
Разбиение корневого узла   . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  441
Разбиение при перемещении вниз . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  442
Приложение Tree234 Workshop   . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  442
Кнопка Fill . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  443
Кнопка Find   . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  443
Кнопка Ins   . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  444
Кнопка Zoom   . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  444
Просмотр разных узлов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  445
Эксперименты   . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  446
Реализация дерева 2-3-4 на языке Java . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  447
Класс DataItem   . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  447
Класс Node   . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  447
Класс Tree234   . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  448
Класс Tree234App . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  449
Полный код программы tree234.java . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  450
Деревья 2-3-4 и красно-черные деревья  . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  457
Преобразование деревьев 2-3-4 в красно-черные деревья . . . . . . . . . . . .  457
Эквивалентность операций   . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  459
Эффективность деревьев 2-3-4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  461
Скорость   . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  461
Затраты памяти   . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  462
Деревья 2-3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  462
Разбиение узлов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  463
Реализация   . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  465
Внешнее хранение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  466
Обращение к внешним данным   . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  466
Последовательное хранение   . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  469
B-деревья   . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  471
Индексирование . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  476
Сложные критерии поиска   . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  478
Сортировка внешних файлов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  479
Итоги   . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  482
Вопросы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  484
Упражнения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  485
Программные проекты   . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  485
Глава 11. Хеш-таблицы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  487
Хеширование   . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  487
Табельные номера как ключи   . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  488
Индексы как ключи . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  488
Словарь   . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  489
Хеширование   . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  492
Коллизии   . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  494
Открытая адресация   . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  495
Линейное пробирование . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  495
Реализация хеш-таблицы с линейным пробированием на языке Java   . . .  500
Квадратичное пробирование . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  507
Двойное хеширование . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  509
Метод цепочек   . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  517
Приложение HashChain Workshop   . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  517
Реализация метода цепочек на языке Java   . . . . . . . . . . . . . . . . . . . . . . . . . .  520
Хеш-функции . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  525
Быстрые вычисления . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  526
Случайные ключи   . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  526
Неслучайные ключи   . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  526
Хеширование строк   . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  528
Свертка   . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  530
Эффективность хеширования   . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  530
Открытая адресация   . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  530
Метод цепочек   . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  532
Сравнение открытой адресации с методом цепочек . . . . . . . . . . . . . . . . . .  534
Хеширование и внешнее хранение данных   . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  535
Таблица файловых указателей . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  535
Неполные блоки   . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  535
Полные блоки   . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  536
Итоги   . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  537
Вопросы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  538
Упражнения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  540
Программные проекты   . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  540
Глава 12. Пирамиды   . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  542
Общие сведения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  543
Приоритетные очереди, пирамиды и ADT   . . . . . . . . . . . . . . . . . . . . . . . . . . .  544
Слабая упорядоченность   . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  544
Удаление   . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  545
Вставка . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  547
Условные перестановки   . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  548
Приложение Heap Workshop . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  549
Заполнение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  550
Изменение приоритета . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Быстрый поиск по ключевым словам: Структуры | | данных | | и | | алгоритмы | | в | | Java | | Классика | | Computers | Science | | книги | | 2 | е | изд | | Лафоре |

Доставка Структуры данных и алгоритмы в Java. Классика Computers Science. 2-е изд. Лафоре почтой наложным платежом.

 
     



    Купить книгу в разделе Книги компьютерные - Книги прочая разработка  
 
Книга Flex 3. Сборник рецептов. Ноубл
Купить Книга Flex 3. Сборник рецептов. Ноубл Широкие возможности новых технологий лучше всего раскрываются на практических примерах. Именно такой подход используется в книге "Flex 3. Сборник рецептов" для представления технологии Adobe Flex 3. Рассчитанная на широкий круг читателей и весьма практичная книга "Flex 3. Сборник рецептов" содержит более 300 решений, используемых при построении интерактивных RIA-приложений и сайтов Web 2.0.
Книга CRYSTAL REPORT 9. Пек Дж
Купить Книга CRYSTAL REPORT 9. Пек Дж Рассмотрено создание сложных отчетов профессионального качества с аналитическими средствами как для публикации в Web, так и для использования в корпоративной сети. Обсуждаются все тонкости применения новой версии системы Crystal Reports 9 для анализа и форматирования данных, демонстрации информации из баз данных, а также интеграции с языком Visual Basic и средой разработки Visual Studio .NET.
 
     
 
 
 
Бизнес книга © 2010-2011
Создание сайтов & Раскрутка сайтов SKYLOGIC
 
Купить книги УкрПочтой по всей Украине.
Интернет магазин книг | Новинки | Оплата | Доставка | Контакты | Помощь