一、數(shù)據(jù)結(jié)構(gòu)

概念

數(shù)據(jù)結(jié)構(gòu)是指相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。通常情況下，精心選擇的數(shù)據(jù)結(jié)構(gòu)可以帶來(lái)更高的運(yùn)行或者存儲(chǔ)效率。數(shù)據(jù)結(jié)構(gòu)往往同高效的檢索算法和索引技術(shù)有關(guān)。數(shù)據(jù)結(jié)構(gòu)分為邏輯結(jié)構(gòu)和物理結(jié)構(gòu)。

數(shù)據(jù)結(jié)構(gòu)組成

• 數(shù)據(jù): 程序的操作對(duì)象,用于描述客觀事物?？梢暂斎氲接?jì)算機(jī) ，可以被計(jì)算機(jī)處理。
• 數(shù)據(jù)對(duì)象: 性質(zhì)相同的數(shù)據(jù)元素的集合(類似于數(shù)組)。
• 數(shù)據(jù)元素: 組成數(shù)據(jù)的對(duì)象的基本單位。

• 數(shù)據(jù)項(xiàng): 一個(gè)數(shù)據(jù)元素由若干數(shù)據(jù)項(xiàng)組成。
  

  數(shù)據(jù)、數(shù)據(jù)對(duì)象、數(shù)據(jù)元素和數(shù)據(jù)項(xiàng)的關(guān)系如下圖：
  數(shù)據(jù)結(jié)構(gòu)

邏輯結(jié)構(gòu)

指反映數(shù)據(jù)元素之間的邏輯關(guān)系的數(shù)據(jù)結(jié)構(gòu)，其中的邏輯關(guān)系是指數(shù)據(jù)元素之間的前后間關(guān)系，而與他們?cè)谟?jì)算機(jī)中的存儲(chǔ)位置無(wú)關(guān)。數(shù)據(jù)的邏輯關(guān)系包括：

• 集合：數(shù)據(jù)結(jié)構(gòu)中的元素之間除了“同屬一個(gè)集合” 的相互關(guān)系外，別無(wú)其他關(guān)系；（無(wú)序的）
• 線性結(jié)構(gòu)：數(shù)據(jù)結(jié)構(gòu)中的元素存在一對(duì)一的相互關(guān)系；
• 樹形結(jié)構(gòu)：數(shù)據(jù)結(jié)構(gòu)中的元素存在一對(duì)多的相互關(guān)系；
• 圖形結(jié)構(gòu)：數(shù)據(jù)結(jié)構(gòu)中的元素存在多對(duì)多的相互關(guān)系。

物理結(jié)構(gòu)

數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)存儲(chǔ)空間中的存放形式稱為數(shù)據(jù)的物理結(jié)構(gòu)(也稱為存儲(chǔ)結(jié)構(gòu))。

數(shù)據(jù)的物理結(jié)構(gòu)的特點(diǎn)是：

• 順序存儲(chǔ)：借助元素在存儲(chǔ)器中的相對(duì)位置來(lái)表示數(shù)據(jù)元素之間的邏輯關(guān)系。比如數(shù)組存儲(chǔ)在一串連續(xù)的內(nèi)存中就屬于順序存儲(chǔ)。

• 非順序存儲(chǔ)：借助指示元素存儲(chǔ)地址的指針表示數(shù)據(jù)元素之間的邏輯關(guān)系。比如非循環(huán)單向鏈表元素存儲(chǔ)的內(nèi)存地址就可以不是連續(xù)的，可以根據(jù)元素內(nèi)指向下個(gè)元素的地址找到下個(gè)元素。

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

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

二、算法

概念

算法是指解題方案的準(zhǔn)確而完整的描述，是一系列解決問(wèn)題的清晰指令，算法代表著用系統(tǒng)的方法描述解決問(wèn)題的策略機(jī)制。也就是說(shuō)，能夠?qū)σ欢ㄒ?guī)范的輸入，在有限時(shí)間內(nèi)獲得所要求的輸出。

數(shù)據(jù)結(jié)構(gòu)和算法的關(guān)系

• 數(shù)據(jù)結(jié)構(gòu)和算法兩個(gè)概念間的邏輯關(guān)系貫穿了整個(gè)程序世界，首先二者表現(xiàn)為不可分割的關(guān)系。沒有數(shù)據(jù)間的有機(jī)關(guān)系和高效處理，程序根本無(wú)法設(shè)計(jì)。
• 數(shù)據(jù)結(jié)構(gòu)為算法提供服務(wù)。算法圍繞數(shù)據(jù)結(jié)構(gòu)操作。

• 解決問(wèn)題和提高程序運(yùn)行速度需要選擇正確的算法，而高效率和低資源耗費(fèi)的算法的設(shè)計(jì)又依賴于數(shù)據(jù)的結(jié)構(gòu)。例如：算法中經(jīng)常需要對(duì)數(shù)據(jù)進(jìn)行增加和刪除用鏈表數(shù)據(jù)結(jié)構(gòu)效率高，數(shù)組數(shù)據(jù)結(jié)構(gòu)因?yàn)樵黾雍蛣h除需要移動(dòng)數(shù)字每個(gè)元素所以效率低。
  

  數(shù)據(jù)結(jié)構(gòu)和算法的關(guān)系就像下圖：
  數(shù)據(jù)結(jié)構(gòu)和算法的關(guān)系

算法知識(shí)點(diǎn)

• 算法的特性

輸入輸出：算法可以有0個(gè)或者多個(gè)輸入；算法至少要有一個(gè)輸出，沒有輸出的算法也就沒有意義。
有窮性：算法必須要在執(zhí)行有限個(gè)步驟之后產(chǎn)生出結(jié)果。
確定性：算法的每個(gè)步驟都要有確切的意義。
可行性：算法的每個(gè)步驟都要切實(shí)有效，可執(zhí)行。

• 算法的設(shè)計(jì)要求

正確性：算法被要求結(jié)果一定正確，不正確就沒有意義了。
健壯性：算法內(nèi)的邏輯處理要考慮到對(duì)不合理數(shù)據(jù)的處理，即容錯(cuò)能力。
可讀性：即算法可供其他人閱讀的能力。
時(shí)間復(fù)雜度：執(zhí)行算法所需要的計(jì)算工作量或時(shí)間長(zhǎng)短。一般用O(n)表示，n越大時(shí)間復(fù)雜度越大。一般作為衡量算法效率的主要方法。
空間復(fù)雜度：執(zhí)行算法所需要的輔助（額外使用的）內(nèi)存空間大小。也可用O(n)表示，計(jì)算比時(shí)間復(fù)雜度簡(jiǎn)單。

算法的時(shí)間復(fù)雜度

時(shí)間復(fù)雜度計(jì)算規(guī)則

• 用常數(shù)1取代運(yùn)行時(shí)間中所有常數(shù)；eg：3->1 O(1)
• 在修改運(yùn)行次數(shù)函數(shù)中,只保留最高階項(xiàng)；eg: n^ 3+2n^2+5 -> O(n^3)
• 如果在最高階存在且不等于1,則去除這個(gè)項(xiàng)目相乘的常數(shù)；eg：2n^3 -> O(n^3)

時(shí)間復(fù)雜度常見計(jì)算情況

• 常數(shù)階
  時(shí)間復(fù)雜度為一個(gè)確定的常數(shù)，最終結(jié)果為O(1)。

//時(shí)間復(fù)雜度  1+1+1+1+1+1 = 6  O(1)
void testSum1(int n) {
    int sum = 0;   //執(zhí)行1次
    sum = (1 + n) * 2; //執(zhí)行1次
    sum = (1 + n) * 2; //執(zhí)行1次
    sum = (1 + n) * 2; //執(zhí)行1次
    sum = (1 + n) * 2; //執(zhí)行1次
    sum = (1 + n) * 2; //執(zhí)行1次
}

• 線性階
  時(shí)間復(fù)雜度是n的一次冪的表達(dá)式，結(jié)果是O(n)。

//時(shí)間復(fù)雜度  1 + n = n   O(n)
void testSum2(int n) {
    int x = 0;
    for (int i = 0; i < n; i ++) {
        x = x + 1; //執(zhí)行n次
    }
}
//時(shí)間復(fù)雜度  1 + (n + 1) + n = 2n + 2  O(n)
void testSum3(int n) {
    int x = 0;  // 1次
    for (int i = 0; i <= n; i ++) {
        x = x + 1; //執(zhí)行 n + 1 次
    }
    for (int j = 0; j < n; j ++) {
        x = x * 2; //執(zhí)行 n 次
    }
}

• 平方階
  時(shí)間復(fù)雜度是n^2 的表達(dá)式，結(jié)果是O(n^2)。

//時(shí)間復(fù)雜度  1 + n + n^2   O(n^2)
void testSum4(int n) {
    int x = 0; // 1次
    for (int i = 0; i < n; i ++)
    {
        x = x + 1;  //執(zhí)行 n 次
        for (int j = 0; j < n; j ++)
        {
            x = x + 1; //執(zhí)行 n^2 次
        }
    }
}
//時(shí)間復(fù)雜度  n*(n+1)/2 = n^2/2 + n/2  O(n^2)
void testSum5(int n) {
    int x = 0;
    for (int i = 0; i < n; i ++) {
        for (int j = i; j < n; j ++) {
            x = x + 1;
            /** 等差數(shù)列求和
             i = 0, 執(zhí)行n次
             i = 1， 執(zhí)行n-1次
             i = 2， 執(zhí)行n-2次
             ...
             i = n-1, 執(zhí)行 1 次
             
             執(zhí)行總次數(shù)：n*(n+1)/2
             */
        }
    }
}

• 對(duì)數(shù)階
  時(shí)間復(fù)雜度是一個(gè)數(shù)的對(duì)數(shù)， o(logn)。

//時(shí)間復(fù)雜度 假如x是執(zhí)行次數(shù)  2 ^ x >= n , x = log(2)(n)  O(logn)
void testSum6(int n) {
    int count = 1;
    while (count < n) {
        count = count * 2;  //執(zhí)行 log(2)(n)次
    }
}

• 立方階
  時(shí)間復(fù)雜度是包含n^3的表達(dá)式， O(n^3)。

//時(shí)間復(fù)雜度 n + n*n + n*n*n     O(n^3)
void testSum7(int n) {
    int x = 1;
    for (int i = 0; i < n; i ++) {
        x = x + 1; //n次
        for (int j = 0; j < n; j ++) {
            x = x + 1;//n*n次
            for (int k = 0; k < n; k ++) {
                x = x + 1;//n*n*n次
            }
        }
    }
}

時(shí)間復(fù)雜度常見情況

時(shí)間復(fù)雜度的大小如下：
O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3) < O(2^n) < O(n!) < O(n^n)

算法的空間復(fù)雜度

一個(gè)算法執(zhí)行的過(guò)程中可能用到的空間因素有：

• 寄存本身的指令
• 常數(shù)
• 變量
• 輸入
• 對(duì)數(shù)據(jù)進(jìn)行操作的輔助空間
  而算法的空間復(fù)雜度的計(jì)算主要是考慮算法執(zhí)行時(shí)所需要的輔助空間。

例子：數(shù)組逆序,將一維數(shù)組a中的n個(gè)數(shù)逆序存放在原數(shù)組中（n<=a.count）。
方法一：只使用了一個(gè)中間變量temp，空間復(fù)雜度 O(1)

    int temp;
    for(int i = 0; i < n/2 ; i++){
        temp = a[I];
        a[i] = a[n-i-1];
        a[n-i-1] = temp;
    }

方法二：數(shù)組b中創(chuàng)建了n個(gè)元素，空間復(fù)雜度是O(n)

    int b[10] = {0};
    for(int i = 0; i < n;i++){
        b[i] = a[n-i-1];
    }
    for(int i = 0; i < n; i++){
        a[i] = b[i];
    }

總結(jié)

• 數(shù)據(jù)結(jié)構(gòu)是指相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。
• 算法是是一系列解決問(wèn)題的清晰指令，算法代表著用系統(tǒng)的方法描述解決問(wèn)題的策略機(jī)制。
• 數(shù)據(jù)結(jié)構(gòu)為算法提供服務(wù)。算法圍繞數(shù)據(jù)結(jié)構(gòu)操作。二者密不可分，貫穿整個(gè)程序運(yùn)行。
• 算法的效率衡量的主要方法是計(jì)算算法的時(shí)間復(fù)雜度。