本篇文章是對二次學習C語言12——文件操作 二次學習C語言14——預處理及模塊化 二次學習C語言15——鏈表 二次學習C語言17——棧、隊列、二叉樹的部分補充說明，感興趣的話可以了解一下，這一系列C語言blog不會很仔細，主要是幫助有一些C語言基礎但想快速回顧一下的友友；但也不會質量很差，不然就失去了它存在的意義。還是很希望大家在相應blog評論區多多指出疑惑或分享實際問題的，這樣我們就可以共同進步啦！

表棧、隊列、二叉樹

一、二叉樹

• 二叉樹的遍歷

分三種：

1. 先序遍歷，根 左 右
2. 中序遍歷，左 根 右
3. 后序遍歷，左 右 根

	* 先序遍歷（根左右）：ABCDEFGHK
A為根先左B，B為根僅右C，C為根僅左D，D無左右，
A為根后右E，E為根僅右F，F為根僅左G，G為根先左H后右K
下面以對應規則類推* 中序遍歷（左 根 右）：BDCAEHGKF* 后序遍歷（左 右 根）：DCBHKGFEA

• 樹

樹型結構是以分支關系定義的層次結構，它是一種重要的非線性結構。

樹（tree） 是由一個或多個結點組成的有限集合T 。

1. 一個特定的結點稱為該樹的根（root）結點
2. 結點之外的其余結點可分為m（m ≥ 0）個互不相交的有限集合 T1 ,T2 ,…,Tm ，且其中每一個集合本身又是一棵樹，稱之為根的子樹（subtree）。

注意：
樹的遞歸定義刻畫了樹的固有特性：一棵非空樹是由若干棵子樹構成的，而子樹又可由若干棵更小的子樹構成。

樹結構的基本術語如下。

結點的度(Degree)：樹中的一個結點擁有的子樹數目，如：A結點的度為2

樹的度：是指該樹中結點的最大度數。如樹T的度為2。

葉子結點(Leaf) 或終端結點：度為零的結點。如D、H、K都是葉子結點。

分支結點或非終端結點：度不為零的結點。A、B、C、E、F、G都是分支結點。

孩子結點或兒子：樹中某個結點的子樹之根。如A的孩子結點為B、E。

雙親結點或父親：孩子結點的上層結點。

兄弟結點(Sibling)：同一個雙親的孩子。

結點的層數(Level)：從根起算，根的層數為1，它的孩子的層數為2……若某結點在第i層，它的孩子結點就在第i+1層。

樹的高度(Height)或深度(Depth)：樹中結點的最大層數。如樹T的高度為5

有序樹(OrderedTree)：將樹中每個結點的各子樹看成是從左到右有次序的(即不能互換)，二叉樹就是有序樹。（二叉樹的左子樹和右子樹是嚴格區分并且不能隨意顛倒的）

• 二叉樹的性質

1. 性質1： 二叉樹第i層上的結點數目最多為2ⁱ-1(i≥1)。
2. 性質2： 深度為k的二叉樹至多有2^k-1個結點(k≥1)。
3. 性質3： 在任意一棵二叉樹中，若葉子結點（即度為0的結點）的個數為n₀，度為1的結點數為n₁，度為2的結點數為n₂，則n_o=n₂+1。

滿二叉樹(FullBinaryTree) ：一棵深度為k且有2^k-1個結點的二叉樹稱為滿二叉樹。

其特點：
1.每一層上的結點數都達到最大值。即如果高度確定，它是具有最多結點數的二叉樹。

2.滿二叉樹中不存在度數為1的結點，每個分支結點均有兩棵高度相同的子樹，且樹葉都在最下一層上。

完全二叉樹(Complete BinaryTree) :若一棵二叉樹至多只有最下面的兩層上結點的度數可以小于2，并且最下一層上的結點都集中在該層最左邊的若干位置上，則此二叉樹稱為完全二叉樹。

其特點：
1.滿二叉樹是完全二叉樹，完全二叉樹不一定是滿二叉樹。
2.在滿二叉樹的最下一層上，從最右邊開始連續刪去若干結點后得到的二叉樹仍然是一棵完全二叉樹。
3.在完全二叉樹中，若某個結點沒有左孩子，則它一定沒有右孩子，即該結點必是葉結點。

二叉樹的存儲結構有多種，最常用的有兩種：是順序存儲結構和鏈表存儲結構。

優點和缺點：
① 對完全二叉樹而言，順序存儲結構既簡單又節省存儲空間。

② 一般的二叉樹采用順序存儲結構時，雖然簡單，但易造成存儲空間的浪費。

③ 在對順序存儲的二叉樹做插入和刪除結點操作時，要大量移動結點。

二、表棧

• 線性表

  最簡單、最常用的一種數據結構，是具有相同數據類型的n（n≥0）個數據元素（結點）的有限序列。通常記為：（a1，a2，…，an ）。其中n稱為線性表的長度，當n=0的時表示空表。

  • ①順序表

  用一段連續的內存空間來存儲線性表的數據元素，C語言中是通過數組來實現

  • ②鏈表

即二次學習C語言15——鏈表

• 棧（zhan）

==堆棧（Stack）==可以看成是一種“特殊的“線性表，這種線性表上的插入和刪除運算限定在表的某一端進行的。

棧先進后出（FILO）的特點也可以描述為后進先出，簡稱為LIFO表。

1. 通常稱插入、刪除的這一端為棧頂（Top），另一端稱為棧底（Bottom）。
2. 當表中沒有元素時稱為空棧。
3. 退棧：刪除。
4. 進棧：插入。

三、隊列

隊列(Queue) 是只允許在一端進行插入，而在另一端進行刪除的運算受限的線性表。

1. 允許刪除的一端稱為隊頭（Front）。

2. 允許插入的一端稱為隊尾（Rear）。

3. 當隊列中沒有元素時稱為空隊列。

4. 隊列簡稱為FIFO表。

鏈表

一、單向鏈表

在鏈表結構中，每個節點僅存儲本身需要存儲的數據和下一個節點地址的這種鏈表結構，我們稱為單向鏈表結構

數組與鏈表對比①：

數組在進行數據的插入，刪除操作時，為了保證內存數據的連續性，往往需要做大量的數據搬移工作，所以時間復雜度是O(n)。

在鏈表中插入或刪除數據時，因為鏈表結構中的節點并不需要連續的存儲空間，所以在鏈表中進行數據的插入和刪除時并不需要搬移節點。對于鏈表的刪除和插入操作，我們只需要調整相鄰節點的后繼指針即可，所以對應的時間復雜度是O(1)。

數組與鏈表對比②：

數組的內存數據是連續的，當我們需要訪問第k個元素時，通過基地址（base_address）和數據類型大小就可以隨機訪問到數據所在的內存地址，時間復雜度是O(1)。

對于鏈表來講，因為鏈表中各個節點的數據在內存中時分散的，不像數組那樣是連續的存儲空間，所以要訪問鏈表中的第k個元素，只能從頭結點開始，根據節點間的后繼指針或引用逐一遍歷，直到找到相應的節點，所以鏈表的隨機訪問的性能沒有數組好，時間復雜度為O(n)。

二、循環鏈表、雙向鏈表和雙向循環鏈表

將單鏈表的尾節點從指向空地址NULL調整為指向頭結點Head，就形成了循環鏈表。

和單鏈表相比，循環鏈表的優點是從鏈尾到鏈頭比較方便。當要處理的數據具有環型結構特點時，就特別適合采用循環鏈表。

雙向鏈表支持兩個方向，每個節點不止只有一個后繼指針或者引用Next指向后繼節點，還有一個前驅指針或者引用Prev指向前面的節點

從雙向鏈表的結構看，雙向鏈表可以在O(1)的時間復雜度下找到前驅節點，基于此特性，在某些特殊的場景下，對節點的刪除和插入操作，雙向鏈表比單向鏈表會更高效.

上面我們說了單向鏈表、循環鏈表、雙向鏈表，我們將循環鏈表和雙向鏈表整合在一起，就形成了雙向循環鏈表。

不過，數組和鏈表的對比，并不能局限于時間復雜度。而且，在實際的軟件開發中，不能僅僅利用復雜度分析就決定使用哪個數據結構來存儲數據，一切都要根據具體情況具體分析，合適最好。

預處理

一、預處理

編譯預處理是在對源程序正式編譯之前的處理，以“#”開頭，如文件包含“#include”、宏定義“#define”等。預處理命令不是C語言本身的組成部分，不能直接對它進行編譯。所有的預處理指令都是在編譯之前完成的，不占用程序運行時間。

二、宏定義

• 注意事項：

1. 宏名習慣采用大寫，以便與普通變量區分；

2. 宏定義不是C語句，所以不能在行尾加分號；否則，宏展開時，會將分號也算在內

3. 在宏展開時，預處理程序僅按宏定義簡單替換宏名，不做任何檢查。如果有錯誤，只能由編譯器在編譯宏展開后的源程序時發現。

4. 宏定義的位置是任意的，宏名的有效范圍是從定義命令處到本模塊結束。通常寫在文件開頭處。

5. 宏調用時，是原樣替換，不進行任何轉換。

• #define常量定義與typede數據類型定義的異同點：

#define P_INT int* //在編譯前執行 (原樣替換)

typedef int* P_INT //在編譯時執行

相同點：都是定義了一個int指針類型的別名

不同點：用#define時，P_INT a, b;相當于int* a, b;即int*a; int b;此時b不是int *,而是int

用typedef時，P_INT a, b;相當于int *a; int *b;

文件

文件操作補充

• 文件操作的兩種方式

1. 基于文件描述符¹的文件操作，無緩沖區，也稱為低級文件的操作，屬于底層文件系統，函數90多個。

2. 基于文件指針的訪問操作，帶緩沖區，稱為高級的文件操作，屬于高級文件系統，也是標準C文件操作庫函數， ANSI C庫函數 300多個.

注意：在實操中，我使用的是fwrite與fread，故生成的數據文件打開后是無法正常閱讀的，全是二進制數（相當于一層加密）；若想正常閱讀生成的數據文件，可使用fprintf與fscanf

---

1. 文件描述符：就是數字，0,1,2分別表示標準輸入，標準輸出，標準出錯 ??