數據結構小白入門

數據結構指一組相互之間存在一種或多種特定關係的數據元素的集合,
當我們需要在電腦中存儲這些數據時,還涉及到數據的,組織方式,在電腦中的存儲方式,以及定義在該數據上的一組操作;

• 一組數據相互之間有某種關係
• 組織方式
• 存儲方式
• 以及可對其進行的一組操作

理解:

我們學習的最終目的是要在電腦中存儲一組數據,但是不得不先考慮數據的組織方式,在電腦中的存儲方式,以及可以對這些數據進行的一組操作,當然了既然是一組數據必然表明瞭這寫數據之間是存在想換的關聯關係的;關係可能還會有多種;

例如:

一組數據:12345

組織方式:從小到大

存儲方式:可使用線性存儲結構

操作:要取出最大的一個

數據結構研究方向

問題:

• 機外處理
• 處理要求

建模:

• 邏輯結構
• 基本運算

實現:

• 存儲結構
• 演算法

基本術語

數據(Data):

​ 所有能被電腦處理的符號的集合

數據元素(DataElement):

​ 是數據集合中的一個 個體,即數據的基本單位

數據項(DataItem):

​ 數據元素常常可分為若幹個數據項,數據項是數據具有意義的最小單位

組織數據的三個層次:

數據(表)->數據元素(行)->數據項(欄位)

實際問題中的數據成為原始數據

邏輯結構(LogicalStructure)

​ 數據元素之間的結構關係,如從小到大/一對一/一對多

物理結構(PhysicalStructure)

​ 也會叫做存儲結構,指數據在電腦內的表示,邏輯結構在電腦中的具體實現

邏輯結構

常見的邏輯結構如下:

集合:

數據元素屬於同一個集合,表示為R{}; 數據之間不存在特定關係

組織結構鬆散,任意兩節點之間都沒有鄰接關係

線性:

除了起始節點d1和終端階段dn外,每個節點都有一個前驅和一個後繼,表示為R={d1,d2...dn},數據之間存在前後順序關係

各節點按邏輯關係排列,形成一條'鏈'

樹狀:

每個元素最多有一個前驅,可以有多個後繼,表示為(D,{R}),就像一個樹幹長了多個樹枝

具備分支,層次特性,上層節點可以和下層多個節點相鄰接,但是下層節點只能和一個上層節點鄰接

圖狀:

任何兩個元素之間都可以相鄰接,表示為(D,{R})

註意:

邏輯結構

• 與元素本身的形式,內容,無關

• 元素的相對位置,無關

• 與包含的節點個數,無關

存儲結構

存儲結構由 存儲節點(每個存儲節點存放一個數據元素) 和 節點之間的邏輯關係共同組成

反過來說,一個完整的存儲結構必須可以存儲數據元素,以及元素之間的邏輯關係

存儲結構分類 (缺圖)

• 順序存儲

  使用索引(相對起始位置)來表示數據的邏輯結構,數據被存儲在一組連續的存儲單元中

  特點:

  • 需預先分配長度,
  • 插入和刪除慢,需要移動其他元素
  • 存取數據快捷,屬於隨機存儲結構(可通過索引直接訪問任意位置數據)

• 鏈式存儲

  藉助元素地址指針表示數據的邏輯結構,每個元素都會包含指向下一個元素的指針

  這種結構需要在節點上附加一個指針項,指出後繼節點的位置,即每個節點存儲單元包含兩個部分:[數據項,指針項]

  特點:

  • 動態分配內容,不需要預先分配記憶體
  • 插入刪除快捷,不需要移動其他元素
  • 非隨機存取結構(獲取數據必須遍歷前面的所有節點)

• 索引存儲(Map是否屬於索引結構 很疑惑?)

  藉助索引表來指示數據元素的存儲位置

  索引表中包含了所有數據元素的地址,查詢索引表能夠快速的定位到需要的數據

  特點:

  • 索引是一份獨立於實際存放數據,的數據結構(就像書的目錄都在正文前面)
  • 索引需要占用額外的存儲空間
  • 當實際數據發生改變時需要重建索引
  • 查詢數據快
  • 插入修改,刪除慢

• 散列存儲(哈希表)

  通過散列函數計算得出元素的位置

  特點:

  • 在散列函數不變時,相同數據會得出相同的位置
  • 存入順序和取出順序通常不一致
  • 無法完成隨機存取(指定獲取某個元素)

順序和鏈式是最基本的也是最常用的存儲結構,需要重點掌握,包括各自的優缺點,使用場景等

鏈式存儲結構可實現樹結構(邏輯結構)

運算

運算指的是某種邏輯結構上可以進行的操作;

運算分為兩類:

• 加工型運算

  會改變原邏輯結構的內容,順序,個數等的操作

• 引用型運行

  與加工型運算相反

常見運算:

建立,查找,讀取,插入,刪除

加工型:建立,插入,刪除

引用型:讀取,查找

演算法

演算法字面意思,計算方法;

演算法規定了求解給定類型問題所需的所有處理步驟以及執行順序,使得問題能在有限時間內機械的求解,一個演算法就是對特定問題求解步驟的一種描述,再具體一點,演算法是一段有窮的指令序列;演算法必須能使用某種語言描述;

例如:

計算1到5的和 ,這個需求,如何來實現,第一步做什麼,第二步做什麼,整個計算步驟和執行順序統稱為演算法,如果最終能夠在有限的步驟下求出正確的和,那這就是一個合格的演算法;

演算法的特點:

• 有窮性

  演算法必須在執行有窮步後結束

• 確定性

  演算法的每一個步驟都必須是明確定義的,

• 可行性

  演算法中的每一步都是可以通過已實現的操作來完成的

• 輸入

  一個演算法具備0或多個輸入

• 輸出

  一個演算法有一個或多個輸出,它們與輸入有著特定的關係

演算法與程式的區別,演算法只是一種描述,可以使用任何語言,但是通常不能直接被電腦運行,而程式則是演算法的具體實現,使用某種電腦語言;

演算法設計應滿足的要求

• 正確性:對於合法的輸入產生符合要求的輸出

• 易讀性:演算法應該儘可能易讀,便於交流,這也是保證正確性的前提(註釋可提高易讀性)

• 健壯性:當輸入非法數據時,演算法可作出適當反應而不至於崩潰(例如輸出錯誤原因);

• 時空性:指的是演算法的時間複雜度和空間複雜度,演算法分析主要也是分析演算法的時間複雜度和空間複雜的,其目的是提高演算法的效率;

演算法分析

解決同一問題的演算法可能有多種,我們希望從中選出最優的演算法,效率高的,占用空間小的,為此我們就需要對演算法進行評估和分析;

通常評估演算法根據兩個度量

• 時間複雜度:演算法運行完成所需的總步數(標準操作),通常是問題規模的函數

• 空間複雜度:演算法執行時所占用的存儲空間,通常是問題規模的函數

確定演算法的計算量

• 合理選擇一種或幾種操作作為'標準操作',無特殊說明預設以賦值操作作為標準操作;
• 確定演算法共執行多少次標準操作,並將此次數規定為演算法的計算量
• 以演算法在所有時輸入下的計算量最大值作為演算法的最壞情況時間複雜度
• 以演算法在所有時輸入下的計算量最小值作為演算法的最好情況時間複雜度
• 以演算法在所有時輸入下的計算量平均值作為演算法的平均情況時間複雜度
• 最壞/平均情況時間複雜度都可作為時間複雜度,通常以最壞情況衡量;

註意:時間複雜度通常以量級來衡量,也就是說不需要精確的計算到底執行了幾步,而是得出其計算量的數量級即可,並忽略常數,因為當數量級足夠大時,常數對於計算量的影響可以忽略不計;

如: (n-1)(n-2) 數量級為 n^2

時間複雜度使用大O表示,如O(1)

案例:

1.

void aFunction(){
    int c = 10 + 20;
    int d = c * c;
        printf(d);
}

上列演算法若以賦值運算作為標準操作,則該演算法的計算量為2,其時間複雜度記為O(1),為什麼是O(1)呢,是因為2是一個常數,常數對於函數的增長影響並不大,所以計算量為常數時表示為O(1),按照這種方式,即使計算量為2000,同樣記為O(1),稱為常數

2.

void bFunction(int n){
  for(int i = 0;i < n;i++){ // n
    int c = 2 * i;// 1
    int d = 3 * i;// 2
  }
}

此時函數的迴圈次數由未知數n來決定,迴圈體內計算量為2,當n是一個自然數時,函數的計算量等於(n)(2),此時時間複雜度為O(n),無論用常數2對n進行加減乘除對於n的指數都沒有影響,當n足夠大時,內部的2次計算量可以忽略,所以記為O(n),稱為線性階

更粗陋的度量方法是函數體包含一層迴圈時記為O(n)

3.

void bFunction(int n){
  for(int i = 0;i < n;i++){
      for(int j = 0;j < i;j++){
      }
  }
}

外層迴圈次數為n,內層迴圈次數隨著n的增長而增長且最大值為n-1次,那麼整個函數的計算量為(n)(n-1),常數可以忽略,所以時間複雜度記為O(n^2) ,稱為平方階

粗陋的方法是有兩層嵌套迴圈,且迴圈次數都隨著n的增長而增長,所以是O(n^2),以此類推,但是要註意下麵這種情況

4.

void bFunction(int n){
  for(int i = 0;i < n;i++){
      for(int j = 0;j < 3;j++){
      }
  }
}

此時內層迴圈的迴圈次數是固定(常數)所以不會影響計算量的數量級,時間複雜度記為O(n)

5.

void bFunction(int n){
  for(int i = 3;i < n;){
      i *= 3;
  }
}

此時函迴圈次數會隨著3迴圈體中的常數3的的變化而變化,我們可以用對數來表示,

假設迴圈次數為s,迴圈條件可表示為 s = 3^s < n;(即i本身為3,其次冪會不斷的增長,但結果要小於n)

當然這裡有個條件是i的初值必須和每次乘等的值相同,形成次冪的增長;

用對數表示為s = log3n,時間複雜度記為O(log3n),常數可以忽略,所以最後是O(logn)稱之為對數階

對數階的數量級小於線性階,因為若n的值相同,對數階計算量必然小於線性階

6.

void bFunction(int n){
 for(int i = 0;i < n;i++){
     for(int j = 0;j < n;j++){
         for(int k = 0;k < n;k++){
       }
     }   
 }
}

上述演算法時間複雜度為O(n^3),3為常數,對應著迴圈的嵌套層數;也可以用O(n^C)表示,稱為多項式階

7.

void bFunction(int n){
  int num = 2;
  for(int i = 0;i < n;){ //O(n)
        num *= 2;
  }
  for (int j = 0;j<num;j++){ //O(n)
  }
}

上述函數輸入的參數n將作為迴圈次數的指數,假設迴圈次數為s, s = 2^n,那麼時間複雜度為O(2^n),

稱之為指數階,可記為O(C^n)

8.

void bFunction(int n)
{
    for(int i=0;i<n;i++){
          for(int j=0;j<n;j++){
          }
    }   
  
      for(int i=0;i<n;i++){
      }             
}

對於順序運行的演算法,總時間複雜度等於演算法中最大時間複雜度,即O(n^2)

9.

void bFunction(int n)
{
  if(n % 2 ==0){
    for(int i=0;i<n;i++){
          for(int j=0;j<n;j++){
          }
    }   
  }else{
      for(int i=0;i<n;i++){
      }             
  } 
}

對於具備分支結構的演算法,總時間複雜度等於演算法中時間複雜度最大路徑的複雜度,即O(n^2)

時間複雜度大小順序

常數 < 對數階 < 線性階 < 平方階 < 多項式階 < 指數階

O(1) < O(logn) < O(n) < O(n^2) < O(n^C) < O(C^n)

優劣:

通常具有常數階複雜度的演算法是好的演算法
具有指數階複雜度的演算法是差的演算法

個人觀點,若有錯誤敬請指出,謝謝!