棧和隊列

1、棧是限定在一端進行插入與刪除的線性表，允許插入與刪除的一端稱為棧頂，不允許插入與刪除的另一端稱為棧底。棧按照“先進后出”（FILO）或“后進先出”（LIFO）組織數(shù)據(jù)，棧具有記憶作用。用top表示棧頂位置，用bottom表示棧底。

?

2、棧的基本運算：

（1）插入元素稱為入棧運算；

（2）刪除元素稱為退棧運算；

（3）讀棧頂元素是將棧頂元素賦給一個指定的變量，此時指針無變化。

?

3、隊列是指允許在一端（隊尾）進入插入，而在另一端（隊頭）進行刪除的線性表。Rear指針指向隊尾，front指針指向隊頭。

4、隊列是“先進行出”（FIFO）或“后進后出”（LILO）的線性表。

5、特殊隊列—循環(huán)隊列

?

線性鏈表

1、數(shù)據(jù)結(jié)構中的每一個結(jié)點對應于一個存儲單元，這種存儲單元稱為存儲結(jié)點，簡稱結(jié)點。

2、結(jié)點由兩部分組成：

（1）用于存儲數(shù)據(jù)元素值，稱為數(shù)據(jù)域；

（2）用于存放指針，稱為指針域，用于指向前一個或后一個結(jié)點。

3、在鏈式存儲結(jié)構中，存儲數(shù)據(jù)結(jié)構的存儲空間可以不連續(xù)，各數(shù)據(jù)結(jié)點的存儲順序與數(shù)據(jù)元素之間的邏輯關系可以不一致，而數(shù)據(jù)元素之間的邏輯關系是由指針域來確定的。

4、鏈式存儲方式即可用于表示線性結(jié)構，也可用于表示非線性結(jié)構。

5、線性鏈表的基本運算：查找、插入、刪除。

樹與二叉樹

1、樹是一種簡單的非線性結(jié)構，所有元素之間具有明顯的層次特性。

2、二叉樹的特點：

（1）非空二叉樹只有一個根結(jié)點；

（2）每一個結(jié)點最多有兩棵子樹，且分別稱為該結(jié)點的左子樹與右子樹。

3、二叉樹的基本性質(zhì)，性質(zhì)很多主要靠理解，這里只說最重要的：

（1）度為的結(jié)點（即葉子結(jié)點）總是比度為2的結(jié)點多一個；

滿二叉樹：是指除最后一層外，每一層上的所有結(jié)點有兩個子結(jié)點

完全二叉樹：是指除最后一層外，每一層上的結(jié)點數(shù)均達到最大值

4、二叉樹的遍歷：

（1）前序遍歷（DLR），首先訪問根結(jié)點，然后遍歷左子樹，最后遍歷右子樹；

（2）中序遍歷（LDR），首先遍歷左子樹，然后訪問根結(jié)點，最后遍歷右子樹；

（3）后序遍歷（LRD）首先遍歷左子樹，然后訪問遍歷右子樹，最后訪問根結(jié)點。