上次在面試時被面試官問到學了哪些資料結構，那時簡單答了棧、佇列/(ㄒoㄒ)/~~其它就都想不起來了，今天有空整理了一下幾種常見的資料結構，原來我們學過的資料結構有這麼多~首先，先來回顧下C語言中常見的基本資料型別吧O(∩_∩)OC語言的基本資料型別有：整型int，浮點型float，字元型char等等
新增描述那麼，究竟什麼是資料結構呢？資料結構是計算機儲存、組織資料的方式。資料結構是指相互之間存在一種或多種特定關係的資料元素的集合大部分資料結構的實現都需要藉助C語言中的指標和結構體型別下面，進入今天的重點啦O(∩_∩)O幾種常見的資料結構（1）線性資料結構：元素之間一般存在元素之間存在一對一關係，是最常用的一類資料結構，典型的有：陣列、棧、佇列和線性表（2）樹形結構：結點間具有層次關係，每一層的一個結點能且只能和上一層的一個結點相關，但同時可以和下一層的多個結點相關，稱為“一對多”關係，常見型別有：樹、堆（3）圖形結構：在圖形結構中，允許多個結點之間相關，稱為“多對多”關係下面分別對這幾種資料結構做一個簡單介紹：1、線性資料結構：典型的有：陣列、棧、佇列和線性表（1）陣列和連結串列a、陣列：存放著一組相同型別的資料，需要預先指定陣列的長度，有一維陣列、二維陣列、多維陣列等b、連結串列：連結串列是C語言中一種應用廣泛的結構，它採用動態分配記憶體的形式實現，用一組任意的儲存單元存放資料元素連結串列的，一般為每個元素增設指標域，用來指向後繼元素c、陣列和連結串列的區別：從邏輯結構來看：陣列必須事先定義固定的長度，不能適應資料動態地增減的情況；連結串列動態地進行儲存分配，可以適應資料動態地增減的情況，且可以方便地插入、刪除資料項（陣列中插入、刪除資料項時，需要移動其它資料項）從記憶體儲存來看：（靜態)陣列從棧中分配空間（用NEW建立的在堆中）, 對於程式設計師方便快速,但是自由度小；連結串列從堆中分配空間, 自由度大但是申請管理比較麻煩從訪問方式來看：陣列在記憶體中是連續儲存的，因此，可以利用下標索引進行隨機訪問；連結串列是鏈式儲存結構，在訪問元素的時候只能透過線性的方式由前到後順序訪問，所以訪問效率比陣列要低（2）棧、佇列和線性表：可採用順序儲存和鏈式儲存的方法進行儲存順序儲存：藉助資料元素在儲存空間中的相對位置來表示元素之間的邏輯關係鏈式儲存：藉助表示資料元素儲存地址的指標表示元素之間的邏輯關係a、棧：只允許在序列末端進行操作，棧的操作只能在棧頂進行，一般棧又被稱為後進先出或先進後出的線性結構順序棧：採用順序儲存結構的棧稱為順序棧，即需要用一片地址連續的空間來儲存棧的元素，順序棧的型別定義如下：
新增描述鏈棧：採用鏈式儲存結構的棧稱為鏈棧：
新增描述b、佇列：只允許在序列兩端進行操作，一般佇列也被稱為先進先出的線性結構迴圈佇列：採用順序儲存結構的佇列，需要按佇列可能的最大長度分配儲存空空，其型別定義如下：
新增描述 鏈佇列：採用鏈式儲存結構的佇列稱為鏈佇列，一般需要設定頭尾指標只是連結串列的頭尾結點：
順序表：採用順序儲存結構表示的線性表稱為順序表，用一組地址連續的儲存單元一次存放線性表的資料元素，即以儲存位置相鄰表示位序相繼的兩個元素之間的前驅和後繼關係，為了避免移動元素，一般在順序表的介面定義中只考慮在表尾插入和刪除元素，如此實現的順序表也可稱為棧表：
新增描述
線性表：一般包括單鏈表、雙向連結串列、迴圈連結串列和雙向迴圈連結串列單鏈表：
雙向連結串列：
新增描述線性表兩種儲存結構的比較：順序表： 優點：在順序表中，邏輯中相鄰的兩個元素在物理位置上也相鄰，查詢比較方便，存取任一元素的時間複雜度都為O(1) 缺點：不適合在任意位置插入、刪除元素，因為需要移動元素，平均時間複雜度為O(n)連結串列： 優點：在連結的任意位置插入或刪除元素只需修改相應指標，不需要移動元素；按需動態分配，不需要按最大需求預先分配一塊連續空空 缺點：查詢不方便，查詢某一元素需要從頭指標出發沿指標域查詢，因此平均時間複雜度為O(n)2、樹形結構：結點間具有層次關係，每一層的一個結點能且只能和上一層的一個結點相關，但同時可以和下一層的多個結點相關，稱為“一對多”關係，常見型別有：樹、堆（1）二叉樹：二叉樹是一種遞迴資料結構，是含有n(n>=0)個結點的有限集合，二叉樹具有以下特點：二叉樹可以是空樹；二叉樹的每個結點都恰好有兩棵子樹，其中一個或兩個可能為空；二叉樹中每個結點的左、右子樹的位置不能顛倒，若改變兩者的位置，就成為另一棵二叉樹（2）完全二叉樹：從根起，自上而下，自左而右，給滿二叉樹的每個結點從1到n連續編號，如果每個結點都與深度為k的滿二叉樹中編號從1至n的結點一一對應，則稱為完全二叉樹a、採用順序儲存結構：用一維陣列儲存完全二叉樹，結點的編號對於與結點的下標（如根為1，則根的左孩子為2i=21=2，右孩子為2i+1=21+1=2）
b、採用鏈式儲存結構：二叉連結串列：
三叉連結串列：它的結點比二叉連結串列多一個指標域parent，用於執行結點的雙親，便於查詢雙親結點
兩種儲存結構比較：對於完全二叉樹，採用順序儲存結構既能節省空間，又可利用陣列元素的下標值確定結點在二叉樹中的位置及結點之間的關係，但採用順序儲存結構儲存一般二叉樹容易造成空間浪費，鏈式結構可以克服這個缺點（3）二叉查詢樹：二叉查詢樹又稱二叉排序樹，或者是一課空二叉樹，或者是具有如下特徵的二叉樹：a、若它的左子樹不空，則左子樹上所有結點的值均小於根結點的值b、若它的右子樹不空，則右子樹上所有結點的值均大於根結點的值c、它的左、右子樹也分別是二叉查詢樹（4）平衡二叉樹：平衡二叉查詢樹簡稱平衡二叉樹，平衡二叉樹或者是棵空樹，或者是具有下列性質的二叉查詢樹：它的左子樹和右子樹都是平衡二叉樹，且左子樹和右子樹的高度之差的絕對值不超過1
平衡二叉樹的失衡及調整主要可歸納為下列四種情況：LL型、RR型、LR型、RL型（5）樹：樹是含有n(n>=0)個結點的有限集合，在任意一棵非空樹種： a、有且僅有一個特定的稱為根的結點b、當n>1時，其餘結點可分為m(m>0)個互不相交的有限集T1,T2,…,Tm，其中每一個集合本身又是一棵樹，並且T1,T2,…,Tm稱為根的子樹（6）堆：堆是具有以下特性的完全二叉樹，其所有非葉子結點均不大於（或不小於）其左右孩子結點。若堆中所有非葉子結點均不大於其左右孩子結點，則稱為小頂堆（小根堆），若堆中所有非葉子結點均不小於其左右孩子結點，則稱為大頂堆（大根堆）
（7）並查集：並查集是指由一組不相交子集所構成的集合，記作：S={S1,S2,S3,…,Sn}（8）B樹3、圖形結構：在圖形結構中，允許多個結點之間相關，稱為“多對多”關係，可分為有向圖和無向圖
一些相關的影片資料便於大家學習
C語言與資料結構的經典實戰案例結構體普及與應用C語言玩轉連結串列C高階之結構體迴圈連結串列及線性表的應用
上次在面試時被面試官問到學了哪些資料結構，那時簡單答了棧、佇列/(ㄒoㄒ)/~~其它就都想不起來了，今天有空整理了一下幾種常見的資料結構，原來我們學過的資料結構有這麼多~首先，先來回顧下C語言中常見的基本資料型別吧O(∩_∩)OC語言的基本資料型別有：整型int，浮點型float，字元型char等等
新增描述那麼，究竟什麼是資料結構呢？資料結構是計算機儲存、組織資料的方式。資料結構是指相互之間存在一種或多種特定關係的資料元素的集合大部分資料結構的實現都需要藉助C語言中的指標和結構體型別下面，進入今天的重點啦O(∩_∩)O幾種常見的資料結構（1）線性資料結構：元素之間一般存在元素之間存在一對一關係，是最常用的一類資料結構，典型的有：陣列、棧、佇列和線性表（2）樹形結構：結點間具有層次關係，每一層的一個結點能且只能和上一層的一個結點相關，但同時可以和下一層的多個結點相關，稱為“一對多”關係，常見型別有：樹、堆（3）圖形結構：在圖形結構中，允許多個結點之間相關，稱為“多對多”關係下面分別對這幾種資料結構做一個簡單介紹：1、線性資料結構：典型的有：陣列、棧、佇列和線性表（1）陣列和連結串列a、陣列：存放著一組相同型別的資料，需要預先指定陣列的長度，有一維陣列、二維陣列、多維陣列等b、連結串列：連結串列是C語言中一種應用廣泛的結構，它採用動態分配記憶體的形式實現，用一組任意的儲存單元存放資料元素連結串列的，一般為每個元素增設指標域，用來指向後繼元素c、陣列和連結串列的區別：從邏輯結構來看：陣列必須事先定義固定的長度，不能適應資料動態地增減的情況；連結串列動態地進行儲存分配，可以適應資料動態地增減的情況，且可以方便地插入、刪除資料項（陣列中插入、刪除資料項時，需要移動其它資料項）從記憶體儲存來看：（靜態)陣列從棧中分配空間（用NEW建立的在堆中）, 對於程式設計師方便快速,但是自由度小；連結串列從堆中分配空間, 自由度大但是申請管理比較麻煩從訪問方式來看：陣列在記憶體中是連續儲存的，因此，可以利用下標索引進行隨機訪問；連結串列是鏈式儲存結構，在訪問元素的時候只能透過線性的方式由前到後順序訪問，所以訪問效率比陣列要低（2）棧、佇列和線性表：可採用順序儲存和鏈式儲存的方法進行儲存順序儲存：藉助資料元素在儲存空間中的相對位置來表示元素之間的邏輯關係鏈式儲存：藉助表示資料元素儲存地址的指標表示元素之間的邏輯關係a、棧：只允許在序列末端進行操作，棧的操作只能在棧頂進行，一般棧又被稱為後進先出或先進後出的線性結構順序棧：採用順序儲存結構的棧稱為順序棧，即需要用一片地址連續的空間來儲存棧的元素，順序棧的型別定義如下：
新增描述鏈棧：採用鏈式儲存結構的棧稱為鏈棧：
新增描述b、佇列：只允許在序列兩端進行操作，一般佇列也被稱為先進先出的線性結構迴圈佇列：採用順序儲存結構的佇列，需要按佇列可能的最大長度分配儲存空空，其型別定義如下：
新增描述 鏈佇列：採用鏈式儲存結構的佇列稱為鏈佇列，一般需要設定頭尾指標只是連結串列的頭尾結點：
順序表：採用順序儲存結構表示的線性表稱為順序表，用一組地址連續的儲存單元一次存放線性表的資料元素，即以儲存位置相鄰表示位序相繼的兩個元素之間的前驅和後繼關係，為了避免移動元素，一般在順序表的介面定義中只考慮在表尾插入和刪除元素，如此實現的順序表也可稱為棧表：
新增描述
線性表：一般包括單鏈表、雙向連結串列、迴圈連結串列和雙向迴圈連結串列單鏈表：
新增描述
雙向連結串列：
新增描述線性表兩種儲存結構的比較：順序表： 優點：在順序表中，邏輯中相鄰的兩個元素在物理位置上也相鄰，查詢比較方便，存取任一元素的時間複雜度都為O(1) 缺點：不適合在任意位置插入、刪除元素，因為需要移動元素，平均時間複雜度為O(n)連結串列： 優點：在連結的任意位置插入或刪除元素只需修改相應指標，不需要移動元素；按需動態分配，不需要按最大需求預先分配一塊連續空空 缺點：查詢不方便，查詢某一元素需要從頭指標出發沿指標域查詢，因此平均時間複雜度為O(n)2、樹形結構：結點間具有層次關係，每一層的一個結點能且只能和上一層的一個結點相關，但同時可以和下一層的多個結點相關，稱為“一對多”關係，常見型別有：樹、堆（1）二叉樹：二叉樹是一種遞迴資料結構，是含有n(n>=0)個結點的有限集合，二叉樹具有以下特點：二叉樹可以是空樹；二叉樹的每個結點都恰好有兩棵子樹，其中一個或兩個可能為空；二叉樹中每個結點的左、右子樹的位置不能顛倒，若改變兩者的位置，就成為另一棵二叉樹（2）完全二叉樹：從根起，自上而下，自左而右，給滿二叉樹的每個結點從1到n連續編號，如果每個結點都與深度為k的滿二叉樹中編號從1至n的結點一一對應，則稱為完全二叉樹a、採用順序儲存結構：用一維陣列儲存完全二叉樹，結點的編號對於與結點的下標（如根為1，則根的左孩子為2i=21=2，右孩子為2i+1=21+1=2）
新增描述
b、採用鏈式儲存結構：二叉連結串列：
新增描述
三叉連結串列：它的結點比二叉連結串列多一個指標域parent，用於執行結點的雙親，便於查詢雙親結點
新增描述
兩種儲存結構比較：對於完全二叉樹，採用順序儲存結構既能節省空間，又可利用陣列元素的下標值確定結點在二叉樹中的位置及結點之間的關係，但採用順序儲存結構儲存一般二叉樹容易造成空間浪費，鏈式結構可以克服這個缺點（3）二叉查詢樹：二叉查詢樹又稱二叉排序樹，或者是一課空二叉樹，或者是具有如下特徵的二叉樹：a、若它的左子樹不空，則左子樹上所有結點的值均小於根結點的值b、若它的右子樹不空，則右子樹上所有結點的值均大於根結點的值c、它的左、右子樹也分別是二叉查詢樹（4）平衡二叉樹：平衡二叉查詢樹簡稱平衡二叉樹，平衡二叉樹或者是棵空樹，或者是具有下列性質的二叉查詢樹：它的左子樹和右子樹都是平衡二叉樹，且左子樹和右子樹的高度之差的絕對值不超過1
新增描述
平衡二叉樹的失衡及調整主要可歸納為下列四種情況：LL型、RR型、LR型、RL型（5）樹：樹是含有n(n>=0)個結點的有限集合，在任意一棵非空樹種： a、有且僅有一個特定的稱為根的結點b、當n>1時，其餘結點可分為m(m>0)個互不相交的有限集T1,T2,…,Tm，其中每一個集合本身又是一棵樹，並且T1,T2,…,Tm稱為根的子樹（6）堆：堆是具有以下特性的完全二叉樹，其所有非葉子結點均不大於（或不小於）其左右孩子結點。若堆中所有非葉子結點均不大於其左右孩子結點，則稱為小頂堆（小根堆），若堆中所有非葉子結點均不小於其左右孩子結點，則稱為大頂堆（大根堆）
新增描述
（7）並查集：並查集是指由一組不相交子集所構成的集合，記作：S={S1,S2,S3,…,Sn}（8）B樹3、圖形結構：在圖形結構中，允許多個結點之間相關，稱為“多對多”關係，可分為有向圖和無向圖
一些相關的影片資料便於大家學習
C語言與資料結構的經典實戰案例結構體普及與應用C語言玩轉連結串列C高階之結構體迴圈連結串列及線性表的應用