常見(jiàn)數(shù)據(jù)結(jié)構(gòu)
1.棧
棧（stack）又名堆棧蓄愁，它是一種運(yùn)算受限的線性表峡扩。其限制是僅允許在表的一端進(jìn)行插入和刪除運(yùn)算(先進(jìn)后出)昼激。這一端被稱(chēng)為棧頂限煞，把另一端稱(chēng)為棧底抹恳。
2. 隊(duì)列
隊(duì)列是一種特殊的線性表，特殊之處在于它只允許在表的前端（front）進(jìn)行刪除操作署驻，而在表的后端（rear）進(jìn)行插入操作（先進(jìn)先出）奋献，和棧一樣，隊(duì)列是一種操作受限制的線性表旺上。進(jìn)行插入操作的端稱(chēng)為隊(duì)尾瓶蚂，進(jìn)行刪除操作的端稱(chēng)為隊(duì)頭。
3. 單項(xiàng)鏈表
單鏈表有一個(gè)頭節(jié)點(diǎn)head宣吱，指向鏈表在內(nèi)存的首地址窃这。鏈表中的每一個(gè)節(jié)點(diǎn)的數(shù)據(jù)類(lèi)型為結(jié)構(gòu)體類(lèi)型，節(jié)點(diǎn)有兩個(gè)成員：整型成員（實(shí)際需要保存的數(shù)據(jù)）和指向下一個(gè)結(jié)構(gòu)體類(lèi)型節(jié)點(diǎn)的指針即下一個(gè)節(jié)點(diǎn)的地址（事實(shí)上征候，此單鏈表是用于存放整型數(shù)據(jù)的動(dòng)態(tài)數(shù)組）杭攻。鏈表按此結(jié)構(gòu)對(duì)各節(jié)點(diǎn)的訪問(wèn)需從鏈表的頭找起，后續(xù)節(jié)點(diǎn)的地址由當(dāng)前節(jié)點(diǎn)給出疤坝。無(wú)論在表中訪問(wèn)那一個(gè)節(jié)點(diǎn)兆解，都需要從鏈表的頭開(kāi)始，順序向后查找跑揉。鏈表的尾節(jié)點(diǎn)由于無(wú)后續(xù)節(jié)點(diǎn)锅睛，其指針域?yàn)榭眨瑢?xiě)作為NULL畔裕。
單鏈表更適合插入刪除操作多的數(shù)據(jù)存儲(chǔ)衣撬，而順序結(jié)構(gòu)則適合查找操作比較多的數(shù)據(jù)存儲(chǔ)。
靜態(tài)鏈表扮饶、循環(huán)鏈表具练、雙線鏈表
4. 二叉樹(shù)
a.根二叉樹(shù)(Rooted Binary Tree)：
有一個(gè)根結(jié)點(diǎn)，每個(gè)結(jié)點(diǎn)至多有兩個(gè)孩子甜无。
b.滿二叉樹(shù)(Full Binary Tree)：
要么是葉子結(jié)點(diǎn)(結(jié)點(diǎn)的度為0)扛点，要么結(jié)點(diǎn)同時(shí)具有左右子樹(shù)(結(jié)點(diǎn)的度為2)。
c.完全二叉樹(shù)(Complete Binary Tree)：
每層結(jié)點(diǎn)都完全填滿岂丘，在最后一層上如果不是滿的陵究，則只缺少右邊的若干結(jié)點(diǎn)。
d.完美二叉樹(shù)(Perfect Binary Tree)
所有的非葉子結(jié)點(diǎn)都有兩個(gè)孩子奥帘，所有的葉子結(jié)點(diǎn)都在同一層铜邮。即每層結(jié)點(diǎn)都完全填滿。
e.無(wú)限完全二叉樹(shù)(Infinite Complete Binary Tree)：
每個(gè)結(jié)點(diǎn)都有兩個(gè)孩子，結(jié)點(diǎn)的層數(shù)是無(wú)限的松蒜。
f.平衡二叉樹(shù)(Balanced Binary Tree)：
也稱(chēng)為AVL樹(shù)扔茅，它是一棵空樹(shù)或它的左右兩個(gè)子樹(shù)的高度差的絕對(duì)值不超過(guò)1，并且左右兩個(gè)子樹(shù)都是一棵平衡二叉樹(shù)秸苗。
注意：僅有前序和后序遍歷召娜，不能確定一個(gè)二叉樹(shù)，必須有中序遍歷的結(jié)果
5. 堆
最大堆的根結(jié)點(diǎn)中的元素在整個(gè)堆中是最大的惊楼；
最小堆的根結(jié)點(diǎn)中的元素在整個(gè)堆中是最小的玖瘸。
6. 哈夫曼樹(shù)
定義：給定n個(gè)權(quán)值作為n的葉子結(jié)點(diǎn)，構(gòu)造一棵二叉樹(shù)檀咙，若帶權(quán)路徑長(zhǎng)度達(dá)到最小雅倒，稱(chēng)這樣的二叉樹(shù)為最優(yōu)二叉樹(shù)，也稱(chēng)為哈夫曼樹(shù)(Huffman tree)攀芯。一般用于編碼屯断。
7.二叉排序樹(shù)
a. 二叉排序樹(shù)或者是一棵空樹(shù)，或者是具有下列性質(zhì)的二叉樹(shù)：
b. 若左子樹(shù)不空，則左子樹(shù)上所有結(jié)點(diǎn)的值均小于它的根結(jié)點(diǎn)的值；
c. 若右子樹(shù)不空猾漫，則右子樹(shù)上所有結(jié)點(diǎn)的值均大于或等于它的根結(jié)點(diǎn)的值；
左趴久、右子樹(shù)也分別為二叉排序樹(shù)；
d. 沒(méi)有鍵值相等的節(jié)點(diǎn)
二分查找的時(shí)間復(fù)雜度是O(log(n))搔确，最壞情況下的時(shí)間復(fù)雜度是O(n)（相當(dāng)于順序查找）
