資料結構

資料結構基礎

  • 演算法與效率分析(algorithm and performance analysis)
    • 演算法簡單的來說就是完成一個問題所需要的具體步驟和方法。
  • 陣列(arrays)
  • 指標概念(pointers)
  • 字串處理(string manipulation)

樹狀結構(trees)及其應用

  • 二元樹(binary trees)
  • m路樹(m-way trees)
  • 查找樹(tries))

圖(graphs)及其應用

  • 包括圖的表示方式
  • 圖形演算法(graph algorithms)
  • 擴張樹 Spanning Tree

排序與搜尋

  • 排序演算法(sorting algorithms)
    • 穩定的排序
      • 氣泡排序法(bubble sort)- O(n2)
      • 插入排序(insertion sort)—O(n2)
      • 雞尾酒排序(cocktail sort)—O(n2
      • 合併排序(merge sort)—O(n log n);需要O(n)額外空間)
      • 二叉排序樹排序(binary tree sort)— O(n log n)期望時間;O(n2)最壞時間;需要O(n)額外空間
      • 圖書館排序(library sort)— O(n log n)期望時間;O(n2)最壞時間;需要(1+ε)n額外空間
    • 不穩定的排序
      • 選擇排序(selection sort)—O(n2)
      • 快速排序(quick sort)—O(n log n)期望時間,O(n2)最壞情況;對於大的、亂數串列一般相信是最快的已知排序
      • Binary Search
  • 搜尋演算法(searching algorithms)
    • 深度優先搜尋法 Depth-first search (DFS)
    • 深度限制搜尋法 Depth-limited search (DLS)
    • 加深式搜尋法 Iterative deepening search (IDS)
    • 廣度優先搜尋法 Breadth-first search (BFS)
    • A搜尋法 A searc
  • 雜湊(hashing)
  • 優先佇列(priority queues)

綜合應用

  • 外部儲存的資料處理(processing data in external storage)
  • 資料壓縮(data compression)
  • 選擇適當資料結構的策略

演算法