程式員必備——資料結構入門

前言：資料結構與算法作為計算機經典的基礎理論課程，同時作為計算機類專業考研課程，并且在校招面試時常被提及，其重要性可見一斑。除此之外，學習這門課程有助于我們用程式設計去解決、思考問題，設計出更簡潔、效率更高的代碼。

一.課程概述

• 資料結構課程研究什麼？
  • 記憶體中基本資料組織和資料處理的方法
  • 非數值問題
• 通過學習資料結構獲得什麼？
  • 經典資料結構和經典算法的基本原理
• 學習重點
  • 資料結構的邏輯特性和存儲結構設計
  • 資料結構算法設計基本方法和分析方法
  • 利用資料結構解決實際問題

二.基本概念與術語

• 資料
  • 能輸入到計算機中，被程式識别和處理的一切事物的符号化表示
• 資料元素
  • 資料的基本機關
• 資料項
  • 構成資料元素的最小機關
• 存儲結構（由想法到算法）
  • 順序存儲結構
  • 鍊式存儲結構
• 邏輯結構（由問題到想法）
  • 一種邏輯結構可由多種存儲結構實作
• 資料結構
  • 邏輯結構
  • 存儲結構
  • 資料運算
• 抽象資料類型（ADT）

  ADT 抽象資料類型名{
      資料對象的定義
      資料元素之間的邏輯關系定義
      基本運算定義
  }ADT           

• 算法的定義
  • 基于存儲結構的運算實作的步驟
  • 滿足有窮性、确定性、可行性
  • 有0個或多個輸入，1個或多個輸出
• 什麼是好的算法
  • 正确性：對于合法輸入，算法能得出正确結果
  • 健壯性：對于非法輸入，算法能做出特别處理
  • 可了解性：算法容易了解、實作
  • 高效性：具有較短執行時間并占用較少空間
  • 可修改、可拓展性

三.算法分析

• 時間複雜度
  • 是算法求解問題規模n的函數，T(n)=F(n)，F(n)是基本語句的執行頻度
  • 增長率：忽略低次幂和最高次幂系數
• 分析規則
  • 加法規則：針對并列程式段
  • 乘法規則：針對嵌套程式段
• 例子

  ++x;  //複雜度O(1)
  
  for(i=1;i<=n;++i)
  ++x;  //複雜度O(n)
  
  for(i=1;i<=n;++i)
  for(j=1;j<=n;++j)
  ++x;  //複雜度O(n²)           

• 常見的時間複雜度

  O(1)<(log2n)<(n)<(nlog2n)<(n²)<...<(2的n次方)<(n!)           

• 空間複雜度
  • 除去輸入輸出占用空間，算法臨時占用的存儲空間
  • S(n)=O(f(n))

完整内容可以通路我的個人部落格：

資料結構 515code.com