Skip to content

jack74387/Data-Structure-and-Algorithm

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

3 Commits
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

資料結構與演算法專案集合

這個專案集合包含了多種常見的資料結構與演算法的 C++ 實作。每個專案都使用 Qt 框架提供圖形化使用者介面(GUI),讓演算法的執行過程可以被視覺化地展示。每個資料夾都代表一個獨立的專案,專注於一種特定的演算法或資料結構。


專案列表

排序演算法 (Sorting Algorithms)

  • bubble_sort/ - 氣泡排序

    • 功用: 一種簡單的排序演算法。它會重複地遍歷待排序的數列,一次比較兩個元素,如果他們的順序錯誤就把他們交換過來。
  • insertion_sot/ (insertion_sort) - 插入排序

    • 功用: 一種簡單直觀的排序演算法。它的工作原理是通過構建有序序列,對於未排序數據,在已排序序列中從後向前掃描,找到相應位置並插入。
  • quick_sort/ - 快速排序

    • 功用: 一種高效率的排序演算法,採用分治法(Divide and Conquer)策略。它選擇一個「基準」(pivot) 元素,並將數列分割成兩個子陣列,一個子陣列中所有元素都比基準值小,另一個子陣列中所有元素都比基準值大,然後對這兩個子陣列進行遞迴排序。
  • counting_sort/ - 計數排序

    • 功用: 一種非比較排序演算法,適用於整數排序。它通過計算每個不同整數出現的次數,來確定每個整數在排序後數列中的位置。

樹狀資料結構 (Tree Data Structures)

  • binary_search_tree/ - 二元搜尋樹

    • 功用: 一種節點有序的二元樹,其左子樹的所有節點值均小於根節點值,右子樹的所有節點值均大於根節點值。這使得元素的搜尋、插入和刪除等操作非常高效。
  • avl_tree/ - AVL 樹

    • 功用: 自平衡二元搜尋樹。在 AVL 樹中,任何節點的兩個子樹的高度最大差別為 1,這確保了樹的平衡,從而保證了操作的時間複雜度為 O(log n)。
  • 2-3-4-tree/ - 2-3-4 樹

    • 功用: 一種自平衡的多路搜尋樹,其中每個節點可以有 2、3 或 4 個子節點。它能保持樹的平衡,確保所有葉節點都在同一深度。
  • binary_tree_traversal/ - 二元樹遍歷

    • 功用: 實作了遍歷二元樹的幾種基本方法,如前序(Pre-order)、中序(In-order)和後序(Post-order)遍歷。
  • delete_node/ & search_node/ - 樹節點操作

    • 功用: 專注於二元搜尋樹中的特定操作:節點的搜尋與刪除。
  • rebuild_tree/ - 重建二元樹

    • 功用: 根據給定的前序和中序遍歷結果,重建原始的二元樹結構。
  • Optimal_binary_searching_tree/ - 最佳二元搜尋樹

    • 功用: 一種動態規劃的應用,旨在建立一棵平均搜尋成本最低的二元搜尋樹,特別適用於搜尋頻率不均等的元素集合。

圖論演算法 (Graph Algorithms)

  • Directed_graph/ - 有向圖

    • 功用: 實作有向圖的基本結構與操作,其中邊具有方向性。
  • Dijkstra-s_algorithm/ - 戴克斯特拉演算法

    • 功用: 用於尋找圖中單一源點到所有其他節點的最短路徑。適用於權重為非負值的圖。
  • Floyd_warshall_algorithm/ - 佛洛伊德-華歇爾演算法

    • 功用: 一種動態規劃演算法,用於尋找加權圖中所有節點對之間的最短路徑。可以處理帶有負權重的邊。
  • Kruskal-s_Algorithm/ - 克魯斯克爾演算法

    • 功用: 一種尋找圖的最小生成樹(MST)的貪婪演算法。它會選擇權重最小的邊來連接節點,同時避免形成環路。
  • Prime-s_algorithm/ (Prim's_algorithm) - 普林姆演算法

    • 功用: 另一種尋找圖的最小生成樹(MST)的貪婪演算法。它從一個起始節點開始,逐步擴展生成樹,每次都選擇連接到樹的權重最小的邊。

動態規劃與其他演算法 (Dynamic Programming & Others)

  • knapsack/ - 背包問題

    • 功用: 一個經典的組合最佳化問題,旨在在給定容量限制下,選擇一組物品以達到最大價值。此專案實作了 0/1 背包問題的動態規劃解法。
  • knapsack_seafood/ - 海鮮背包問題

    • 功用: 這是背包問題的一個具體應用場景。
  • MatrixChainProduction/ - 矩陣鏈乘法

    • 功用: 一個動態規劃的經典問題,旨在找到計算一系列矩陣乘積的最有效方式(即最少的純量乘法次數)。

其他 (Miscellaneous)

  • koch_curve/ - 科赫曲線

    • 功用: 一個碎形(Fractal)的生成範例。科赫曲線是一個在任何地方都連續但無處可微分的曲線。
  • guess/ - 猜數字遊戲

    • 功用: 一個簡單的互動遊戲,計算各玩家猜拳比賽的勝率。

About

Data Structure and Algorithm

Topics

Resources

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published