Скачать golang data structures algorithms golang data structures algorithms

golang data structures algorithms

Другой исходный код

1.0.0

Скачать

Структуры данных и алгоритмы

Структуры данных и алгоритмы (DSA) являются одной из наиболее важных тем в информатике, которую каждый студент CS должен быть опытным, и даже студенты, не являющиеся CS, должны иметь базовое понимание этого. Говорят, что DSA похож на хлеб с маслом, необходимость CS. Этот репозиторий создан для тех студентов (таких как я?), Которые хотят учиться и хотят реализовать структуры данных и алгоритмы.

Зачем идти/Голанг, а не c, c ++ или java?

Я бы не согласился с тем, что C, C ++ или Java не были бы отличным языком для реализации DSA, так как нужно позаботиться о многих вещах при написании кода, например, распределения памяти и правильных сделок, и тем самым можно многому научиться.

Однако причина, по которой GO также будет хорошим языком для реализации DSA, заключается в том, что ему не хватает много магии. Там нет перегрузки оператора, поэтому нет способа скрыть дополнительную сложность. Индексная операция - O (1), петля o (n) - всегда. Там нет дженериков, поэтому многих дополнительных абстракций и помощников не существует, что на самом деле довольно здорово. Там нет лени или другой магии, управляемой компиляторами, которые могут значительно изменить время выполнения ваших алгоритмов. И у GO есть указатель и низкоуровневые примитивы для срезов, что означает, что это очевидно, когда данные упакованы или когда данные имеют дополнительную косвенный. Короче говоря : сделайте фактическое алгоритмическое выполнение очевидным из кода, что хорошо для изучения алгоритмов.

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

Инструкции

Чтобы начать, убедитесь, что вы установили язык программирования на вашем компьютере. Следите за тем, как установить инструкции из Golang Trancs.
После того, как go установлен на вашей машине, просто клонируйте или загрузите этот репозиторий.
Теперь cd <folder-name> в папку, где находится файл, который вы хотите запустить.
Теперь беги иди go run . Полем

Пример

Давайте предположим, что вы хотите запустить файлы, расположенные в каталоге graphs/directed_unweighted тогда синтаксис для запуска будет:

 cd graphs/directed_unweighted/

go run .

Имена папок

Алгоритмы -
- 01knapsack_dp - 0-1 Проблема рюкзака с использованием динамического программирования
- a_star -
  - 8_puzzzle - 8 Проблема головоломки с использованием алгоритма ^*
  - directed_graph - алгоритм A ^* для направленного графика
  - Undered_graph - Алгоритм A ^* для неисправенного графика
- Activity_selection_gp - выбор активности с использованием жадного программирования
- Assembly_line_scheduling - Алгоритм планирования сборочной линии с использованием динамического программирования
- Binary_Reflected_gray_codes - двоичные отраженные серые коды
- roless_pair_problem -
  - CPP_BRUTE_FORCE - Ближайшая пара проблема с использованием техники грубой силы
  - CPP_DIVIDE_CONQUER - Ближайшая пара пары с использованием Divide и Conquer Techinque
- Комбинации -
  - with_r - с повторением элементов
  - Без_Р - без повторения элементов
- concex_hull -
  - CH_BRUTE_FORCE - Алгоритм выпуклого корпуса с использованием техники грубой силы
  - CH_DIVIDE_CONQUER - Алгоритм выпуклого корпуса с использованием техники разделения и завоевания
- Express_conversions -
  - infix_postfix - Infix в Postfix преобразование
  - infix_prefix - инфикс в префикс преобразование
  - postfix_infix - postfix в инфикс преобразование
  - postfix_prefix - postfix в префикс
  - prefix_infix - префикс в инфикс преобразование
  - prefix_postfix - префикс в пост -конверсию
- GCD - наибольший общий делитель (алгоритм Евклида)
- Графики -
  - articulation_point_detection - обнаружение точек артикуляции в неисправенном графике
  - Bellman_ford - алгоритм Bellman Ford
  - Bridge_detection - Обнаружение моста/обнаружение краев на выявлении на неправомерном графике
  - Дейкстра - алгоритм Дейкстры
  - FLOYD_WARSHALL - Алгоритм Флойда Варшалла (все точки кратчайшего пути)
  - Крускалс - Алгоритм Крускала (обнаружение минимального дерева с использованием жадного подхода)
  - PRIMS - алгоритм PRIM (поиск минимального охватывающего дерева MST с использованием жадного подхода)
  - Topological_sort - топологический сорти
  - Траверсии -
    - cd_directed_graph_traversals - обнаружение цикла на направленных графиках с использованием методов обезвреживания
    - cd_undirected_graph_traversals - обнаружение цикла на неправомерных графиках с использованием методов обезвреживания
  - TSP -
    - tsp_dynamic -
      1. DIRECTED_GRAPH - TSP (проблема с продавцом, используя динамический подход для направленного графика
      2. Undered_graph - TSP (проблема с продавцом, используя динамический подход для неисправного графика
    - tsp_naive -
      1. DIRECTED_GRAPH - TSP (проблема с продавцом, используя наивный подход для направленного графика
      2. Undered_graph - TSP (проблема с продавцом, используя наивный подход для неисправного графика
  - Union_find - Union Find / Discoint Sets (обнаружение циклов в неориентированном графике)
- Huffman_codes - коды Huffman (генерируя коды Huffman)
- job_scheduling_gp - алгоритм планирования заданий с использованием жадного программирования
- LCM - наименьшее распространенное множество (с помощью алгоритма GCD Euclid)
- LCS - самая длинная общая последовательность
  - iterative_dp - самая длинная общая последующая последовательность с использованием динамического программирования (итеративная версия)
- lo_permutations - лексикографические перестановки упорядочения
- longest_palindrome_substring -
  - brute_force - самая длинная подстроение палиндрома с использованием техники грубой силы
  - Manchers - самая длинная подстроение палиндром с использованием алгоритма манчера
- tore_change_dp - Проблема с изменением с использованием динамического программирования
- ORDER_STATISTICS - Поиск наименьшего/самый большой элемент KTH (статистика заказа)
  - NAIVE_APPOACH - Наивный подход с использованием Max Heap - O (k + (nk)*log (k))
  - Quick_select - Quick Select (Quick Sort) - O (n^2), θ (nlogn)
  - худший_КАЗАМИНГОВЕР - Статистика линейного заказа в худшем случае - O (n)
- power_set - набор мощности (набор подмножества)
- идет поиск -
  - binary_search - двоичный поиск - O (log n)
  - Interpolation_search - Поиск интерполяции - O (n)
  - linear_search - линейный поиск - O (n)
  - ternary_search - Ternary Search - O (log ₃ n)
- sief_of_eratosthenes - сито эратостенес (последовательные простые числа не превышают n)
- Сортировка -
  - binary_insertion_sort - бинарная вставка сорта - O (n ² )
  - Bubble_sort - Bubble Sort - O (N ² )
  - Bucket_sort - Bucket Sort - O (N ² )
  - counting_sort - отсчет сортировки - O (n + k)
  - heap_sort - куча сортировки - O (nlog (n)
  - insertion_sort - Sort Sort - O (N ² )
  - merge_sort - merge sort - o (nlog (n))
  - Quick_sort - Quick Sort - θ (nlog (n))
  - radix_sort - Radix sort - O (n+k)
  - selection_sort - selection sort - (o (n ² ))
  - Shell_sort - Shell Sort - O (n)
- string_matching -
  - Boyer_moore - Алгоритм Бойера Мура
  - Horspool - Алгоритм Boyer Moore Horspool
  - knuth_morris_pratt - Knuth Morris Pratt
  - NAIVE_PATTERN_MATCHING - NAIVE STACHTING
  - Rabin_karp - Рабин Карп
- TOH - Башня Ханоя
Графики -
- Directed_unweighed - направленный невзвешенный график
- DIRECTED_WEELED - направленный взвешенный график
- Undered_unweighted - Недоставленный невзвешенный график
- Undered_weighted - Недоставленный взвешенный график
куча -
- max_binary_heap - максимальная бинарная куча
- min_binary_heap - min двоичная куча
linked_lists -
- circular_doubly_ll - круговой вдвойной список
- circular_ll - круговой связанный список
- Doubly_ll - вдвойне связанный список
- pres_rev_single_ll - порядок сохранения во время вставки в отдельный связанный список и переворот один связанный список
- single_ll - один связанный список
очереди -
- Cdqueue - круговая двойная очередь
- Cqueue - круговая очередь
- Dqueue - двойная очередь
- Приоритет
- simple_queue - простая очередь
стек - стек
Деревья -
- AVL_TREE_USING_LL - AVL TREE с использованием связанного списка с BFS и DFS (PRO, IN, POST) ОБРАЩЕНИЕ.
- BST_USING_ARR - Дерево двоичного поиска с использованием массива с BFS и DFS (PRE, IN, POST) ОБРАЩЕНИЕ.
- BST_USING_LL - Дерево бинарного поиска с использованием связанного списка с BFS и DFS (PRE, IN, POST) ТРЕБСЯ
- simple_bt_using_arr - простое двоичное дерево с использованием массива с BFS и DFS (pre, in, post).
- simple_bt_using_ll - простое двоичное дерево с использованием связанного списка с BFS и DFS (pre, in, post).

Примечание : указатель ": point_left:" Указывает неполную реализацию и находится в списке TODO.

Вклад

Этот репозиторий предназначен для обучения, как реализовать структуры данных и алгоритмы, и, поскольку вклады других не будут научить меня, как их реализовать самостоятельно, я не буду принимать никаких запросов на привлечение. Тем не менее, не стесняйтесь разжигать это репо и изменить код, чтобы воспроизводить различные структуры данных и алгоритмы. Более того, во время игры вокруг кода, если вы найдете что -то необычное или неправильное в реализации, я очень признателен, если вы создадите проблему на том же.

Лицензия

Этот репозиторий выпускается по лицензии MIT. Короче говоря, это означает, что вы можете использовать это программное обеспечение в любых личных, открытых или коммерческих проектах. Атрибуция не является обязательной, но ценится.