資本貧窮，精神貧窮，你是不是雙窮？

資料結構概述

做好軟體開發作業，就必須了解如何組織各種資料在計算機中的存盤、傳遞和轉換，

你真的了解嗎？

一、離散數學和資料結構

"資料結構"課程脫胎于“離散數學結構”，它涉及各種離散結構（如向量、集合、樹、圖、代數方程、多項式等）在計算機上如何存盤和處理，

二、資料和資料結構

現在網路世界，是我們的現實世界通過計算機構建出來的，而我們的資訊需要轉換成為資料才能在計算機中進行處理；

資料（data）是資訊的載體，是描述客觀事物的數、字符，以及所有能輸入到計算機中并被計算機程式識別和處理的符號的集合，
資料大致可以分成兩類數值型資料和非數值性資料；

數值型資料：就是咱們從上學開始接觸的數字（整數、浮點數、復數等），用它就是各種計算唄，比如說計算核彈軌道或者是買菜算賬啥的，你能想到的數學上運算相關的，只要是他能干的都干（這是個廢話）；

非數值資料：包括字符和字串以及文字、影像、語音等資料；比如說李誕的脫口秀，帥氣的臉龐、高笑的段子和魔性的笑聲，

資料結構：

資料結構由某一資料元素的集合和該集合中資料元素之間的關系組成；

Data_Structure = {D,R}
D是某一資料元素的集合；
R是該集合中所有資料元素之間的關系的有限集合；

三、線性結構和非線性結構

根據資料元素之間的關系的不同，我們可以將資料結構分成兩大類：
線性結構和非線性結構；
線性結構：

最常用的資料結構，其特點是資料元素之間存在一對一的線性關系；
兩種不同的存盤結構：順序存盤結構和鏈式存盤結構；
順序存盤的線性表稱為順序表，順序表存盤元素是連續的；
鏈式存盤的線性表稱為鏈表，鏈表中的存盤元素不一定是連續的，元素節點中存盤資料元素以及相鄰元素的地址資訊；

順序表的存盤空間是連續的，就是各個表項的邏輯順序和其存放的物理順序是一致的；就和你考試一樣，你坐的順序和你考號的順序他是一致的，不一致那絕對會出事的；
單鏈表的一個存盤節點包括兩個部分：資料域（data）他是存資料的，指標域（link）他是一個指標，指向下一個節點的開始存盤地址；
線性結構常見的有一維陣列、佇列、堆疊、鏈表；
非線性結構：樹、圖、多維陣列、廣義表；

四、演算法的衡量

演算法是指用來操作資料、解決程式問題的一組方法；

對于同一個問題，使用不同的演算法，或許最后我們得到的最終結果是一樣的，但是在這個程序中消耗的資源和時間會有很大的區別；

就好比我們從青島去北京旅游，你可以坐飛機，這樣會比較節省時間，但是相對的花費可能會比較高；有人可能會開車，這樣雖然比較節省成本，但是花費的時間會比較長，對于演算法也是一樣的，我們如何去衡量不同演算法之間的優劣吶？

我們衡量算發的好壞主要是從時間和空間兩個維度去考量；
時間維度：執行當前演算法消耗的時間，用時間復雜度衡量；
空間維度：執行當前演算法需要占用多少記憶體，用空間復雜度衡量；
當然兩個指標都好更好，但是有時候魚和熊掌不可兼得，就像左手右手不能同時做兄弟一樣，

時間復雜度

可能你會想，比較時間還不容易，把程式都運行一邊不就知道時間了，這個方法當然是可取的，但是很容易受你的硬體的影響還有你的資料規模，
這里我們來一個統一的衡量辦法–大O符號表示法；

T(n) = O(f(n))

常見的時間復雜度的量級：

• 常數階O(1)
• 對數階O(logN)
• 線性階O(n)
• 線性對數階O(nlogN)
• 平方階O(n2)
• 立方階O(n3)
• K次方階O(n^k)

當然時間復雜度越大，執行的效率就越低；

常數階O（1）

public class changshu {
    public static void main(String[] args) {
        int i = 1;
        i++;
        int j = 3;
        ++j;
        System.out.println(i+j);
    }
}

這段代碼執行的時間不會隨著某個變數的增長而增長，無論這類代碼有多長，它的時間復雜度都是O（1）；
如果你每天只是寫一些CRUD的代碼，那么你的復雜度也不會很高；不斷學習，不斷提高；

斗之氣 到斗者到斗皇直到斗帝

對數階O(logN)

public class duishu {
    public static void main(String[] args) {
        int i = 1;
        int m = 0;
        while (i<1024){
            i = i * 2;
            m++;
        }
        System.out.println("m = " + m);
    }
}

在while回圈里面，i每次都是在接近1024的，假設1024用n表示，回圈m次，跳出回圈,m是約等于 log2^n，轉換一下就是當回圈 log2^n 次以后，這個代碼就結束了，因此這個代碼的時間復雜度為：O(logN)；

線性階O(n)

public class xianxing 
{
    public static void main(String[] args) {
        for (int i = 0; i < n; i++) {
            System.out.println("重要的話說n遍");
            
        }
    }
}

for回圈中的n會影響代碼 執行的次數，一個for回圈，這類代碼都可以用O(n)來表示它的時間復雜度，

線性對數階O(nlogN)

for(m=1; m<n; m++)
{
    i = 1;
    while(i<n)
    {
        i = i * 2;
    }
}

這個很容易理解吧，就是線性階和對數階的組合；

平方階O(n2)

for(x=1; i<=m; x++)
{
   for(i=1; i<=n; i++)
    {
       j = i;
       j++;
    }
}

for回圈套for回圈

立方階O(n3)

O(n3)相當于三層n回圈；

K次方階O(n^k)

O(n3)相當于k層n回圈；

空間復雜度

空間復雜度是對一個演算法在運行程序中臨時占用存盤空間大小的一個量度，同樣反映的是一個趨勢，

S(n)=O(f(n))

常見的有 O(1)、O(n)、O(n2)

0(1)：

public class changshu {
    public static void main(String[] args) {
        int i = 1;
        i++;
        int j = 3;
        ++j;
        System.out.println(i+j);
    }
}

不論i j怎么變，演算法需要的空間都是一個固定的常數，空間復雜度O(1)；
對單一變數；
0(n) :

int sum(int x){
            int m;
            int arr[x];
            ......
        }

int型別占用4個位元組，這個程式需要的空間 4+4+4n，S(n)=O(n);
一維陣列；
0(n^2)：

 int add(int n){
            int a;
            int arr1[n];
            int arr2[n][n];
        }

這段代碼占用的空間4+4+4n+4n^2,
S(n)= O(n^2)
二維陣列；

遞回函式的空間復雜度

遞回函式不斷的呼叫自己，函式的引數和區域變數占用的記憶體空間在遞去的程序中會持續增長，在歸來的時候逐層釋放，
當遞回的深度達到一定的數量級，可能會造成堆疊記憶體空間不足的情況；