如需轉(zhuǎn)載, 請咨詢作者, 并且注明出處.
有任何問題, 可以關注我的微博: coderwhy, 或者添加我的微信: 372623326

可能你之前經(jīng)常聽說數(shù)據(jù)結(jié)構(gòu)和算法, 但是不知道他們在討論什么.

因為似乎我們學習編程的過程中, 沒有必要了解這些, 我只是在學習基本的語法/高級語法/做出界面效果/實現(xiàn)復雜的邏輯.

數(shù)據(jù)結(jié)構(gòu)和算法? 它是什么? 為什么它如此重要?

一. 什么是數(shù)據(jù)結(jié)構(gòu)和算法?

數(shù)據(jù)結(jié)構(gòu)和算法的概念還真不是那么好定義.

什么是數(shù)據(jù)結(jié)構(gòu)?

• 官方定義: 并沒有…
• 民間定義:
  • “數(shù)據(jù)結(jié)構(gòu)是數(shù)據(jù)對象吧碾，以及存在于該對象的實例和 組成實例的數(shù)據(jù)元素之間的各種聯(lián)系。這些聯(lián)系可以
    通過定義相關的函數(shù)來給出凯旭±颍” --- 《數(shù)據(jù)結(jié)構(gòu)、算法與應用》
  • “數(shù)據(jù)結(jié)構(gòu)是ADT（抽象數(shù)據(jù)類型 Abstract Data Type）的物理實現(xiàn)●陕” --- 《數(shù)據(jù)結(jié)構(gòu)與算法分析》
  • “數(shù)據(jù)結(jié)構(gòu)（data structure）是計算機中存儲姊氓、組織數(shù)據(jù)的方式丐怯。通常情況下，精心選擇的數(shù)據(jù)結(jié)構(gòu)可以 帶來最優(yōu)效率的算法翔横《刘危” ---中文維基百科
• 從上面的定義, 我們可以發(fā)現(xiàn)數(shù)據(jù)結(jié)構(gòu)和算法的關系非常的緊密
• 我們還是從自己的角度來認識數(shù)據(jù)結(jié)構(gòu)吧:
  • 在計算機中, 存儲和組織數(shù)據(jù)的方式
  • 我們知道, 計算機中數(shù)據(jù)量非常龐大, 如何以高效的方式組織和存儲呢?
  • 這就好比一個龐大的圖書館中存放了大量的書籍, 我們不僅僅要把書放進入, 還應該在合適的時候能夠取出來
• 我們從擺放圖書說起

  • 如果是自己的書相對較少, 我們可以這樣擺放

    
    
    img

  • 如果你有一家書店, 書的數(shù)量相對較多, 我們可以這樣擺放

    img

  • 如果我們開了一個圖書館, 書的數(shù)量相當龐大, 我們可以這樣擺放

    img

• 圖書擺放要使得兩個相關操作方便實現(xiàn):
  • 操作1：新書怎么插入？
  • 操作2: 怎么找到某本指定的書禾唁？
• 圖書各種擺放方式:
  • 方法1：隨便放
    • 操作1：哪里有空放哪里效览，一步到位！
    • 操作2: 找某本書, 累死...
  • 方法2：按照書名的拼音字母順序排放
    • 操作1: 新進一本《阿Q正傳》, 按照字母順序找到位置, 插入
    • 操作2: 二分查找法
  • 方法3: 把書架劃分成幾塊區(qū)域, 按照類別存放, 類別中按照字母順序
    • 操作1: 先定類別荡短，二分查找確定位置丐枉，移出空位
    • 操作2: 先定類別，再二分查找
• 結(jié)論:
  • 解決問題方法的效率, 根數(shù)據(jù)的組織方式有關
  • 計算機中存儲的數(shù)據(jù)量相對于圖書館的書籍來說數(shù)據(jù)量更大, 數(shù)據(jù)更加多
  • 以什么樣的方式, 來存儲和組織我們的數(shù)據(jù)才能在使用數(shù)據(jù)時更加方便呢?
  • 這就是數(shù)據(jù)結(jié)構(gòu)需要考慮的問題

常見的數(shù)據(jù)結(jié)構(gòu)

• 比較常見的數(shù)據(jù)結(jié)構(gòu)

  img

• 常見的數(shù)據(jù)結(jié)構(gòu)較多, 每一種都有其對應的應用場景, 不同的數(shù)據(jù)結(jié)構(gòu)的不同操作性能是不同的:

  • 有的查詢性能很快,有的插入速度很快,有的是插入頭和尾速度很快
  • 有的做范圍查找很快,有的允許元素重復,有的不允許重復等等
  • 在開發(fā)中如何選擇,要根據(jù)具體的需求來選擇

• 注意: 數(shù)據(jù)結(jié)構(gòu)和語言無關, 基本常見的編程語言都有直接或者間接的使用上述常見的數(shù)據(jù)結(jié)構(gòu)

• 為什么之前學習JavaScript沒有接觸過數(shù)據(jù)結(jié)構(gòu)呢? 好像只見過數(shù)組.

  • 單純從客戶程序員的角度, 我們并不需要過多的了解它們的實現(xiàn)細節(jié).
  • 但是簡單的使用不能讓我們更加靈活的使用它們. 了解真相, 你才能獲得真正的自由.

什么是算法?

• 算法(Algorithm)的認識

  • 在之前的學習中, 我們可能學習過幾種排序算法. 并且知道, 不同的算法, 執(zhí)行效率是不一樣的.
  • 也就是說進行某些操作的過程中, 不僅僅數(shù)據(jù)的存儲方式會影響效率, 算法的優(yōu)劣也會影響著效率
  • 那么到底什么是算法呢?

• 算法的定義:

  • 一個有限指令集, 每條指令的描述不依賴于語言
  • 接受一些輸入（有些情況下不需要輸入）
  • 產(chǎn)生輸出
  • 一定在有限步驟之后終止

• 算法通俗理解:

  • Algorithm這個單詞本意就是解決問題的辦法/步驟邏輯.
  • 數(shù)據(jù)結(jié)構(gòu)的實現(xiàn), 離不開算法.

• 舉例: 電燈不工作的解決算法

  img

二. 生活中的數(shù)據(jù)結(jié)構(gòu)和算法

前面我們提了一下生活中的數(shù)據(jù)結(jié)構(gòu)和算法: 圖書的擺放.

為了更加方便的插入和搜索書籍, 需要合理的組織數(shù)據(jù), 并且通過更加高效的算法插入和查詢數(shù)據(jù).

除了這些, 生活中還有很多案例.

數(shù)據(jù)結(jié)構(gòu)的案例

• 快遞員的快遞
  • 上大學期間不知道大家有沒有收過快遞.
  • 大學的快遞通常情況不是送到宿舍的(要不快遞員不愿意挨著去送, 要不宿舍壓根不讓進), 通尘蛲校快遞會放在某個固定的地方, 讓大家自己去拿.
  • 當你跑到固定的地方拿快遞, 還有兩種情況: 一種自己去海量的快遞中找, 另一種快遞員讓你報出名字, 它幫你找.
  • 自己尋找相當于線性查找, 一個個挨著看吧. 當然我們?nèi)祟愌劬μ幚頂?shù)據(jù)的能力非呈萸拢快, 眼觀六路耳聽八方, 可能很快也能找到.
  • 但是比較好的方式, 應該是快遞員幫我們找. 如果這個快遞員動動腦筋的話, 最好的方式是對快遞進行分類, 比如按照名字分類.
  • 這個時候, 只要你報出名字, 它會根據(jù)姓氏立馬鎖定到一塊快遞中, 再根據(jù)名字馬上幫你找到.
  • 這就體現(xiàn)了合理的組織數(shù)據(jù), 對于我們獲取數(shù)據(jù)效率的重要性至關重要.

算法的案例

• 找出線纜出問題的地方:
  • 假如上海和杭州之間有一條高架線, 高架線長度是1,000,000米, 有一天高架線中有其中一米出現(xiàn)了故障.
  • 請你想出一種算法, 可以快速定位到處問題的地方.
• 線性查找:
  • 從上海的起點開始一米一米的排查, 最終一定能找到出問題的線段.
  • 但是如果線段在另一頭, 我們需要排查1,000,000次. 這是最壞的情況. 平均需要500,000次.
• 二分查找:
  • 從中間位置開始排查, 看一下問題出在上海到中間位置, 還是中間到杭州的位置.
  • 查找對應的問題后, 再從中間位置分開, 重新鎖定一般的路程.
  • 最壞的情況, 需要多少次可以排查完呢? 最壞的情況是20次就可以找到出問題的地方.
  • 怎么計算出來的呢?log(1000000, 2), 以2位底, 1000000的對數(shù) ≈ 20.
• 結(jié)論:
  • 你會發(fā)現(xiàn), 解決問題的辦法有很多. 但是好的算法對比于差的算法, 效率天壤之別.