數(shù)據(jù)結構與算法 文章匯總

基礎名詞解釋

• 數(shù)據(jù)：程序的操作對象，用于描述客觀事物，有以下兩個特點

  • 可以輸入到計算機

  • 可以被計算機處理

• 數(shù)據(jù)元素：組成數(shù)據(jù)對象的基本單元

• 數(shù)據(jù)項：一個數(shù)據(jù)元素由若干數(shù)據(jù)項組成

• 數(shù)據(jù)對象：性質相同的數(shù)據(jù)元素的集合，類似于數(shù)組

以上4種名詞之間的關系如下圖所示：

數(shù)據(jù)、數(shù)據(jù)對象、數(shù)據(jù)元素與數(shù)據(jù)項之間的關系

• 結構：數(shù)據(jù)元素之間不是獨立的，存在特定的關系，這些關系即是結構

• 數(shù)據(jù)結構：指的是相互之間存在一種或多種特定關系的數(shù)據(jù)元素的集合

• 算法：對特定問題求解步驟的一種描述

• 程序設計 = 數(shù)據(jù)結構 + 算法

基本概念

邏輯結構 & 物理結構

一般從兩個視角對數(shù)據(jù)進行描述，一個是邏輯結構，一個是物理結構

• 邏輯結構：描述的是數(shù)據(jù)與數(shù)據(jù)之間的邏輯關系
• 物理結構：描述的是數(shù)據(jù)在內存中存儲的形式

邏輯結構

邏輯結構主要有以下4種：

• 集合結構：集合中的所有元素除了同屬于一個集合外，他們之間沒有其他關系，如下圖所示
  
  邏輯結構之集合結構

• 線性結構：數(shù)據(jù)之間的關系是一對一的，所有符合一對一的都是線性結構，如下圖所示
  

  邏輯結構之線性結構

  • 數(shù)組、鏈表 是線性結構

  • 隊列、棧 是特殊線性結構，區(qū)別在于讀取方式

    • 隊列是先進先出，即FIFO

    • 棧是先進后出，即FILO

  • 字符串 是 特殊線性結構，存儲內容只能是字符串

• 樹形結構：數(shù)據(jù)之間的存在一對多的層次關系，如下所示
  

  邏輯結構之樹形結構
  • 二叉樹、B+、B-、紅黑樹、哈西曼樹 都是屬于樹形結構

• 圖形結構：數(shù)據(jù)之間存在多對多的關系，如下圖所示
  
  邏輯結構之圖形結構

物理結構

數(shù)據(jù)的物理結構就是數(shù)據(jù)存儲在磁盤中的方式，這里的磁盤指的是計算機的內存，主要研究的是數(shù)據(jù)結構在計算機中的實現(xiàn)方式，包括數(shù)據(jù)結構中的元素的表示及元素間關系的表示，有以下兩種

• 順序存儲結構： 邏輯上相鄰的數(shù)據(jù)元素，物理存儲位置也相鄰，順序表的存儲空間需要預先分配，且存儲空間是一段的連續(xù)的內存，順序存儲結構如下圖所示
  

  順序存儲結構
  • 優(yōu)點

    • 方法簡單，易實現(xiàn)，因為在各種高級語言中都有數(shù)組

    • 順序存儲結構具有隨機訪問的特點

  • 缺點

    • 順序表中做插入/刪除 操作時，需要進行大量的數(shù)據(jù)移動，因此對n較大的順序表效率低

    • 需要預先分配空間，如果空間預估過大，會導致順序表后面的大部分空間閑置，浪費內存，如果預估過小，又會造成溢出

• 鏈式存儲結構 ：邏輯上相鄰的數(shù)據(jù)元素，其物理存儲位置不一定相鄰，它使用指針實現(xiàn)元素之間的邏輯關系，且鏈表的存儲空間是動態(tài)分布的，鏈式存儲結構如下圖所示
  

  鏈式存儲結構
  • 優(yōu)點：

    • 不需要提前開辟一段連續(xù)的空間，其空間是動態(tài)分配的

    • 插入、刪除操作方便，只需要改變指針的指向，不需要移動數(shù)據(jù)元素

  • 缺點
    • 鏈表不能隨機存取元素，如果在鏈式存儲中遍歷，需要遍歷所有的元素