數(shù)據(jù)結(jié)構(gòu)緒論

對于學完基礎語法的你們來講，去做一般的開發(fā)或者說是稍微有點難度的開發(fā)，在去借鑒別人的代碼，工作是完全夠了的，但是，做大型的項目或者難度很大的項目的時候，那么這些知識還不夠，還得繼續(xù)學習，那就是要學習數(shù)據(jù)結(jié)構(gòu)，從本質(zhì)上去理解和實踐這些知識點，加以融會貫通，這是對自己學習能力和編寫代碼能力一個質(zhì)的飛躍。

今天簡單的介紹一下數(shù)據(jù)結(jié)構(gòu)

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

數(shù)據(jù)結(jié)構(gòu)就是數(shù)據(jù)存儲的方式，那我們學習數(shù)據(jù)結(jié)構(gòu)，就是去研究數(shù)據(jù)的存儲方式。

我們都知道，數(shù)據(jù)是存儲在我們計算機存儲空間里面的，那么這些數(shù)據(jù)存儲他是有一定的規(guī)律的額，所謂無規(guī)矩不成方圓，如果沒有規(guī)律，那我們計算機存儲空間就亂套了，那么，我們向計算機存儲數(shù)據(jù)，只有一個目的，那就是讓數(shù)據(jù)得到保留，并且能夠為我們所用（能夠取出數(shù)據(jù)）。而對于數(shù)據(jù)結(jié)構(gòu)來講，有很多種，那么我們應該選擇哪一種數(shù)據(jù)結(jié)構(gòu)進行存儲呢？這是我們值得去研究的，那么學習數(shù)據(jù)結(jié)構(gòu)就是去研究這些數(shù)據(jù)結(jié)構(gòu)類型的特點。

例如

#include <stdio.h>
#include <stdlib.h>
int main(){
    int a[] = {1,2,3,4,5};
    int i;
    for(i = 0;i < sizeof(a)/sizeof(int);i++){
        printf("a[%d] = %p\n",&a[i]);//打印數(shù)組中的每一個元素的地址
    }    
    exit(0);//函數(shù)正常結(jié)束
}
結(jié)論，通過上面這個例子的運行結(jié)果我們可以看出，數(shù)組在我們的內(nèi)存區(qū)域塊存儲的時候，是遵守了一定的規(guī)律的。
以此同時：int a = 1;int b = 2;這樣的初始化定義一樣的是有一定的關系的，后面我們會介紹。

對于數(shù)據(jù)結(jié)構(gòu)來講，它不是單純只是一個簡單的數(shù)據(jù)的存儲，數(shù)據(jù)結(jié)構(gòu)就是把復雜話的數(shù)據(jù)進行整理，讓這些數(shù)據(jù)變得有規(guī)律，方便我們工作人員進行操作。而存儲方式很多，我們需要選取最優(yōu)的那一種方式進行數(shù)據(jù)的存儲。

數(shù)據(jù)結(jié)構(gòu)的分類

數(shù)據(jù)結(jié)構(gòu)可以分為線性結(jié)構(gòu)、圖存儲結(jié)構(gòu)、樹結(jié)構(gòu)。線性結(jié)構(gòu)可以在細分為順序表、鏈表、棧和隊列，樹結(jié)構(gòu)可以細分為普通樹、二叉樹等。當然，這些在后面我們會一一去學習。

算法

對于學習數(shù)據(jù)結(jié)構(gòu)，那么就應該要提到一個東西，那就是算法，算法和數(shù)據(jù)結(jié)構(gòu)有不解的淵源，當然有的教材把算法單獨拿出來和數(shù)據(jù)結(jié)構(gòu)一樣，而有的數(shù)就是把算法歸納到數(shù)據(jù)結(jié)構(gòu)里面的，但是這些都不重要，重要的是，我們都要去學習和理解。

什么是算法？

算法通俗的說，就是去解決問題的辦法，但是，不同解決問題的辦法，就有不同的過程，在實現(xiàn)同一個結(jié)果的時候，所消耗的資源以及時間是不一樣的。所以，算法也分好算法和一般算法，在這里大家可能對算法有點誤解，算法不是說的那么高深，平時我們編寫程序時，其實就是在寫算法。那是因為我們在進行編程的時候，我們腦海里要去想如何實現(xiàn)，可以是數(shù)學的方式去設想，只不過在具體實現(xiàn)的時候，需要通過我們代碼語法和邏輯進行實現(xiàn)而已，而針對于不同的人，那么思考問題的方式可能不同，那么寫出來的代碼也就不同，就會有好與不太好的算法的區(qū)分，那么如何去評判一個算法好與不好呢？

** 評判一個“好”算法的標準**

對于一個問題的算法來說，之所以稱之為算法，首先它必須能夠解決這個問題，這個我們稱為準確性）。其次，通過這個算法編寫的程序要求在任何情況下不能崩潰（稱為健壯性）。
如果準確性和健壯性都滿足，接下來，就要考慮最重要的一點：通過算法編寫的程序，運行的效率怎么樣。

運行效率體現(xiàn)在兩方面：1、算法的運行時間。（稱為“時間復雜度”）
2、運行算法所需的內(nèi)存空間大小。（稱為“空間復雜度”）

==好算法的標準就是：在符合算法本身的要求的基礎上，使用算法編寫的程序運行的時間短，運行過程中占用的內(nèi)存空間少，就可以稱這個算法是“好算法”。==

時間復雜度的計算

對于時間復雜度來講，我們都知道要去實現(xiàn)一個算法，不可能會把所有的算法都通過程序的方式進行展示出來，并且讓計算機去運行，這樣做的話就已經(jīng)耗時了，做的是無用功、效率低下，所以，在實際開發(fā)，作為一個優(yōu)秀的程序員要學會去估算算法的時間復雜度，可能大家不太懂，通俗一點就是你這個算法實現(xiàn)這個功能大概所需要的時間。

在講嵌入式C語言基礎的時候，給大家講過程序是由三種結(jié)構(gòu)構(gòu)成：順序結(jié)構(gòu)、分支結(jié)構(gòu)、循環(huán)結(jié)構(gòu)，對于前面兩個，代碼只執(zhí)行一次，而對于循環(huán)結(jié)構(gòu)來講，這個需要看循環(huán)的次數(shù)，所以需要的時間也和循環(huán)次數(shù)有關系。
由于程序員喜歡通過估算算法需要的時間，并且循環(huán)結(jié)構(gòu)對算法執(zhí)行所消耗的時間有很大的關系，所以對于時間復雜度的計算，我們主要是通過代碼的循環(huán)次數(shù)，這個我們一般可以稱為“頻度”，所以，次數(shù)越少，那么算法的時間復雜度就越低，算法就越好。

** example**

#include <stdio.h>
#include <stdlib.h>
int maia(){
    int i = 0,j = 0,sum = 0,n = 0;
    /*第一個，只執(zhí)行一次*/
    ++n;
    sum += n;
    /*第二個，執(zhí)行循環(huán)100次*/
    for(i = 1;i <=100;i++);{++n;sum +=n;}
    /*第三個，執(zhí)行循環(huán)100 * 100次***/
    for(i = 1;i <=100;i++)
        for(j = 1;j <= 100;j++){
            ++n;
            sum += n;
        }
    exit(0);
}

時間復雜度的表示

O(頻度)，這里需要注意一下，這個是大寫的字符O，不是0，對于上面這個例子，第一次可以表示為O(1),第二個就是O(100),第三個是O(100*100)。

時間復雜度的估算

對于上面這個程序，整體執(zhí)行的頻度是O(1+100+100100)，那么假設N = 100,那么就可以得到O（1+N+N^{2）;對于學過高數(shù)求極限的同學都知道，當N的值很大的時候，那么這個值就可以等價于N}2;所以，上面的這個例子，它的頻度可以是100100。

一般計算方法

簡化的過程總結(jié)為3步：
1、去掉運行時間中的所有加法常數(shù)。（例如 nn+n+1，直接變?yōu)?nn+n）
2、只保留最高項。（nn+n 變成 nn）
3、如果最高項存在但是系數(shù)不是1，去掉系數(shù)。（n*n 系數(shù)為 1）

常用時間復雜度的排序

O(1)常數(shù)階 < O(logn)對數(shù)階 < O(n)線性階 < O(n2)平方階 < O(n3)(立方階) < O(2的n次方) (指數(shù)階)

空間復雜度

對于空間復雜度和時間復雜度來講，就好比魚與熊掌不能兼得，意思就是說我們可以通過時間換取空間，同時也可以通過空間換取時間，對于空間復雜度，我們在進行編程時，盡量在算法的時間復雜度滿足的情況下，給予最大的空間。舉一個簡單的例子，大家用百度瀏覽器和迅游瀏覽器的時候，可能大家覺得百度訪問速度是不是要快一點，這是因為它占用的內(nèi)存空間大，用空間換取了時間。

總結(jié)

對于今天所介紹的知識，只是一些概念性的知識，希望大家有所了解，后面我們會通過例子對數(shù)據(jù)結(jié)構(gòu)進行詳細的講解，當然數(shù)據(jù)結(jié)構(gòu)很難，是真的難，這里只希望大家入門就好，有了基礎在去深究。本篇文章里面的內(nèi)容如果有誤，歡迎大家指正，非常感謝，祝大家學習愉快。