Реализация структур данных и алгоритмов на Swift

Автор: 付晨, дата создания: 2017/9/18.

Чтобы лучше повторить структуры данных и алгоритмы, я переработал основные структуры данных и алгоритмы с помощью Swift.

Большая часть кода была протестирована, но не может быть полностью гарантирована правильность. Надеюсь, что эксперты смогут помочь мне исправить ошибки.

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

Содержание

1. Линейные таблицы List

   1. Последовательное хранение SequentialList
      • Получение
      • Вставка
      • Удаление
   2. Однонаправленное связное хранение OneDirectionLinkedList
      • Головная вставка
      • Хвостовая вставка
      • Очистка связного списка
      • Получение узла
      • Вставка
      • Удаление
   3. Двунаправленное связное хранилище DoubleLinkedList
      • Получение
      • Вставка
      • Удаление

2. Стек Stack

   1. Последовательное хранение SequentialStack
      • Вталкивание
      • Выталкивание
   2. Совместное использование двух стеков SequentialDoubleStack
      • Вталкивание
      • Выталкивание
   3. Связное хранение LinkStack
      • Вталкивание
      • Выталкивание
   4. Числа Фибоначчи

3. Очередь Queue

   1. Циклическая очередь, последовательное хранение SequentialQueue
      • Получить длину очереди
      • Поставить в очередь
      • Извлечь из очереди
   2. Связное хранение LinkQueue
      • Поставить в очередь
      • Извлечь из очереди

4. Строка String

   1. Алгоритм сопоставления строк StringMatch
      • Метод грубой силы
      • Алгоритм сопоставления KMP

5. Дерево Tree

   1. Представление с двумя родителями ParentTree
   2. Представление с детьми ChildTree
   3. Представление с братьями ChildBrotherTree
   4. Двоичное дерево BinaryTreeNode
      • Создать двоичное дерево
      • Обход (рекурсия)
        • Предварительный обход
        • Обход в середине
        • Последующий обход
      • Обход (итерация)
        • Предварительный обход
        • Обход в середине
        • Поуровневый обход
   5. Ориентированное двоичное дерево
      • Посредством обхода в середине ориентируется двоичное дерево

6. Граф Graph

   1. Смежная матрица AdjacencyMatrix
   2. Список смежности AdjacencyList
      • Создание
      • Поиск граничных узлов
      • Добавление узлов
      • Обход
        • Глубокий приоритет
        • Широкий приоритет
      • Минимальное остовное дерево
        • Алгоритм Прима
        • Алгоритм Краскала
      • Кратчайший путь
        • Алгоритм Дейкстры
        • Алгоритм Флойда
      • Топологическая сортировка не проверена или содержит ошибки
      • Критический путь

7. Поиск Search

   1. Линейный поиск SequentialSearch
      • Линейный поиск
      • Оптимизация линейного поиска
   2. Поиск упорядоченной таблицы OrderlyTableSearch
      • Бинарный поиск
      • Интерполяционный поиск
      • Фибоначчи-поиск
   3. Двоичное сортировочное дерево BinarySortTreeNode
      • Найти
      • Добавить
      • Удалить
   4. Сбалансированное бинарное дерево BalancedBinaryTree
      • Добавить проблема при обработке двойного вращения, требует решения
      • Левое вращение
      • Правое вращение
      • Левый баланс
      • Правильный баланс
   5. Хеш-таблица HashTable
   6. Сортировка Sort
      1. Пузырьковая сортировка BubbleSort
         • Пузырьковая сортировка начального уровня
         • Улучшенная пузырьковая сортировка
         • Оптимизированная пузырьковая сортировка
   7. Простая сортировка выбором SimpleSelectionSort
   8. Прямая сортировка вставками StraighInsertionSort
   9. Сортировка Шелла ShellSort
   10. Пирамидальная сортировка HeapSort
   11. Объединение сортировки MergeSort
   12. Быстрая сортировка QuickSort

Ссылки

• «Структура данных» (версия на языке C++), автор: 邓俊辉, издательство: Издательство Университета Цинхуа
• «Большое введение в структуру данных», автор: 程杰, издательство: Университет Цинхуа
• Блог 青玉伏案