一：數(shù)據(jù)結(jié)構(gòu)緒論
數(shù)據(jù)結(jié)構(gòu)：是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合搓逾。
數(shù)據(jù)結(jié)構(gòu)分為邏輯結(jié)構(gòu)和物理結(jié)構(gòu)
邏輯結(jié)構(gòu)：是指數(shù)據(jù)對象中數(shù)據(jù)元素之間的相互關(guān)系 分為集合結(jié)構(gòu)笋鄙、線性結(jié)構(gòu)吸重、樹形結(jié)構(gòu)、圖形結(jié)構(gòu)歪今。
物理結(jié)構(gòu)：是指數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)中的存儲方式 分為順序存儲結(jié)構(gòu)嚎幸、鏈?zhǔn)酱鎯Y(jié)構(gòu)。
二：算法
算法：解決特定問題求解步驟的描述寄猩，在計(jì)算機(jī)中為指令的有限序列嫉晶，并且每條指令表示一個(gè)或多個(gè)操作。
算法的特性：有窮性田篇、確定性替废、可行性、輸入泊柬、輸出椎镣。
算法設(shè)計(jì)的要求：正確性、可讀性彬呻、健壯性衣陶、高效率和低存儲量需求。
算法的度量方法：事后統(tǒng)計(jì)方法闸氮、事前分析估算方法剪况。
推導(dǎo)時(shí)間復(fù)雜度大O階：
1.用常數(shù)1取代運(yùn)行時(shí)間中的所有加法常數(shù)。
2.在修改后的運(yùn)行次數(shù)函數(shù)中蒲跨，只保留最高階項(xiàng)译断。
3.如果最高階存在且不是1，則去除與這個(gè)項(xiàng)相乘的常數(shù)或悲。
得到的結(jié)果就是大O階孙咪。
常見時(shí)間復(fù)雜度所耗時(shí)間的大小排列：
O(1)<O(log n)<O(n)<O(nlog n)<O(n2)<O(n3)<O(2n)<O(n!)<O(nn)
三：線性表
線性表：零個(gè)或多個(gè)數(shù)據(jù)元素的優(yōu)先序列。
線性表的順序存儲結(jié)構(gòu)巡语，指的是用一段地址連續(xù)的存儲單元依次存儲線性表的數(shù)據(jù)元素翎蹈。
存儲器中的每個(gè)存儲單元都有自己的編號，這個(gè)編號稱為地址男公。
線性表順序存儲結(jié)構(gòu)的優(yōu)缺點(diǎn)：
優(yōu)點(diǎn)：無須為表示表中元素之間的邏輯關(guān)系而增加額外的邏輯空間荤堪。可以快速地存取表中任何位置的元素枢赔。
缺點(diǎn)：插入和刪除操作需要移動大量元素澄阳。當(dāng)線性長度變化較大時(shí)，難以確定存儲空間的容量踏拜。造成存儲空盡的“碎片”碎赢。
線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)，用一組任意的存儲單元存儲線性表的數(shù)據(jù)元素速梗。這組存儲單元可以是連續(xù)的肮塞，也可以是不連續(xù)的襟齿。
鏈?zhǔn)浇Y(jié)構(gòu)中，除了要存儲數(shù)據(jù)元素信息外峦嗤，還要存儲它的后繼元素的存儲地址蕊唐。
存儲數(shù)據(jù)元素信息的域稱為數(shù)據(jù)域，存儲直接后繼位置的域稱為指針域烁设。
指針域中存儲的信息稱作指針或鏈替梨。
兩部分信息組成數(shù)據(jù)元素的存儲映像，稱為結(jié)點(diǎn)装黑。
n個(gè)結(jié)點(diǎn)鏈結(jié)成一個(gè)鏈表副瀑，即為線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)。
如果鏈表的每個(gè)結(jié)點(diǎn)中只包含一個(gè)指針域恋谭，則叫做單鏈表糠睡。
鏈表中第一個(gè)結(jié)點(diǎn)的存儲位置叫做頭指針。
有時(shí)疚颊，我們?yōu)榱烁臃奖愕貙︽湵磉M(jìn)行操作狈孔，會在單鏈表的第一個(gè)結(jié)點(diǎn)前附設(shè)一個(gè)結(jié)點(diǎn)，稱為頭結(jié)點(diǎn)
結(jié)點(diǎn)由存放數(shù)據(jù)元素的數(shù)據(jù)域存放后繼結(jié)點(diǎn)地址的指針域組成材义。
對于插入刪除數(shù)據(jù)越頻繁的操作均抽，單鏈表表的效率優(yōu)勢就越明顯。
單鏈表結(jié)構(gòu)和順序存儲結(jié)構(gòu)對比：
存儲分配方式：
順序存儲結(jié)構(gòu)用一段連續(xù)的存儲單元依次存儲線性表的數(shù)據(jù)元素其掂。
單鏈表采用鏈?zhǔn)酱鎯Y(jié)構(gòu)油挥，用一組任意的存儲單元存放線性表元素。
時(shí)間性能：
1.查找：
順序存儲結(jié)構(gòu)O(1)
單鏈表O(n)
2.插入和刪除：
順序存儲結(jié)構(gòu)需要平均移動表長一半的元素款熬，時(shí)間為O(n)
單鏈表在線出某位置的指針后深寥，插入和刪除 時(shí)間僅為O(1)
3.空間性能：
順序存儲結(jié)構(gòu)需要預(yù)分配存儲空間，分大了浪費(fèi)贤牛，分小了易發(fā)生上溢惋鹅。
單鏈表不需要分配存儲空間，只要有就可以分配殉簸，元素個(gè)數(shù)也不受限制闰集。
讓數(shù)組的元素由兩個(gè)數(shù)據(jù)域組成，data和cur喂链。也就是說數(shù)組每一個(gè)下標(biāo)都對應(yīng)一個(gè)data和一個(gè)cur。數(shù)據(jù)域data妥泉，用來存放數(shù)據(jù)元素椭微，也就是我們要處理的數(shù)據(jù)；而游標(biāo)cur相當(dāng)于單鏈表中的next指針盲链，存放該元素的后繼在數(shù)組中的下標(biāo)蝇率。這種用數(shù)組描述的鏈表叫做靜態(tài)鏈表迟杂。
靜態(tài)鏈表的優(yōu)點(diǎn)：在插入和刪除操作時(shí)，只需要修改游標(biāo)本慕，不需要移動元素排拷，從而改進(jìn)了在順序存儲結(jié)構(gòu)中的插入和刪除操作需要移動大量元素的缺點(diǎn)。
靜態(tài)鏈表的缺點(diǎn)：沒有解決連續(xù)存儲分配帶來的表長難以確定的問題锅尘，失去了順序存儲結(jié)構(gòu)隨機(jī)存取的特性监氢。
將單鏈表中終端結(jié)點(diǎn)的指針端由空指針改為指向頭結(jié)點(diǎn)，就使整個(gè)單鏈表形成一個(gè)環(huán)藤违，這種頭尾相接的單鏈表稱為單循環(huán)列表浪腐，簡稱循環(huán)鏈表。
雙向鏈表是在單鏈表的每個(gè)結(jié)點(diǎn)中顿乒，再設(shè)置一個(gè)指向其前驅(qū)結(jié)點(diǎn)的指針域议街。在雙向鏈表中的結(jié)點(diǎn)中都有兩個(gè)指針域，一個(gè)指向直接后繼璧榄，另一個(gè)指向直接前驅(qū)特漩。
四：棧和隊(duì)列
1.棧
棧是限定僅在表尾進(jìn)行插入和刪除操作的線性表。
允許插入刪除的一端稱為棧頂骨杂，另一端稱為棧底涂身，不含任何元素的棧稱為空棧。
棧又稱為后進(jìn)先出的線性表腊脱，簡稱LIFO結(jié)構(gòu)访得。
棧的插入操作，叫做進(jìn)棧陕凹，也稱壓棧悍抑、入棧。
棧的刪除操作杜耙，叫做出棧搜骡，也有的叫做彈棧。
如果棧的使用過程中元素變化不可預(yù)料佑女，有時(shí)很小记靡，有時(shí)非常大，那么最好是用鏈棧团驱，反之摸吠，如果它的變化在可控范圍內(nèi)，建議使用順序棧嚎花。
一個(gè)直接調(diào)用自己或通過一系列調(diào)用語句間接地調(diào)用自己的函數(shù)寸痢，稱為遞歸函數(shù)。
每個(gè)遞歸定義必須至少有一個(gè)條件紊选，滿足時(shí)遞歸不再進(jìn)行啼止，即不再引用自身而返回值退出道逗。
迭代與遞歸的區(qū)別：迭代使用的是循環(huán)結(jié)構(gòu)，遞歸使用的是選擇結(jié)構(gòu)献烦。
如果是兩個(gè)相同數(shù)據(jù)類型的棧滓窍，則可以用數(shù)組的兩端作棧底的方法來讓兩個(gè)棧共享數(shù)據(jù)，最大化利用數(shù)組的空間巩那。
2.隊(duì)列
隊(duì)列是只允許在一端進(jìn)行插入操作吏夯、而在另一端進(jìn)行刪除操作的線性表。
允許插入的一端稱為隊(duì)尾拢操，允許刪除的一端稱為隊(duì)頭锦亦。
隊(duì)列又稱為先進(jìn)先出的線性表，簡稱FIFO結(jié)構(gòu)令境。
為避免數(shù)組插入和刪除時(shí)需要移動數(shù)據(jù)杠园，于是引入了循環(huán)隊(duì)列，使得隊(duì)頭和隊(duì)尾可以在數(shù)組中循環(huán)變化舔庶。解決了移動數(shù)據(jù)的時(shí)間損耗抛蚁，使得本來插入和刪除時(shí)O(n)的時(shí)間復(fù)雜度變成了O(1)。
五：串
串是由零個(gè)或多個(gè)字符組成的有限序列惕橙。
六：樹
樹是n（n>=0）個(gè)結(jié)點(diǎn)的有限集瞧甩。n=0時(shí)稱為空樹。在任意一顆非空樹中：（1）有且僅有一個(gè)特定的稱為根的結(jié)點(diǎn)弥鹦；（2）當(dāng)n>1時(shí)肚逸，其余結(jié)點(diǎn)可分為m(m>0)個(gè)互不相交的有限集T1、T2彬坏、......Tm,其中每一個(gè)集合本身又是一棵樹朦促，并稱為根的子樹。
樹的結(jié)點(diǎn)包含一個(gè)數(shù)據(jù)元素及若干指向其子樹的分支栓始。結(jié)點(diǎn)擁有的子樹數(shù)稱為結(jié)點(diǎn)的度务冕。度為0的結(jié)點(diǎn)稱為葉結(jié)點(diǎn)或終端結(jié)點(diǎn)；度不為0的結(jié)點(diǎn)稱為非終端結(jié)點(diǎn)或分支結(jié)點(diǎn)幻赚。除根結(jié)點(diǎn)之外禀忆，分支結(jié)點(diǎn)也稱為內(nèi)部結(jié)點(diǎn)。樹的度是樹內(nèi)各結(jié)點(diǎn)的度的最大值落恼。
結(jié)點(diǎn)的子樹的根稱為該結(jié)點(diǎn)的孩子（Child）箩退，相應(yīng)地，該結(jié)點(diǎn)稱為孩子的雙親（Parent）同一個(gè)雙親的孩子之間互稱兄弟（Slibling）佳谦。結(jié)點(diǎn)的祖先是從根到該結(jié)點(diǎn)所經(jīng)分支上的所有結(jié)點(diǎn)戴涝。反之，以某結(jié)點(diǎn)為根的子樹中的任一結(jié)點(diǎn)都稱為該結(jié)點(diǎn)的子孫。
結(jié)點(diǎn)的層次從根開始定義起喊括，根稱為第一層，根的孩子為第二層矢棚。樹中結(jié)點(diǎn)的最大層次稱為樹的深度或高度郑什。
如果將該樹中結(jié)點(diǎn)的各子樹看成從左至右是有次序的，不能互換的蒲肋，則稱該樹為有序樹蘑拯，否則稱為無序樹。
森林是m（m>=0）課互不相交樹的集合兜粘。
線性表與樹對比：
線性結(jié)構(gòu)：
第一個(gè)數(shù)據(jù)元素：無前驅(qū)
最后一個(gè)數(shù)據(jù)元素：無后驅(qū)
中間元素：一個(gè)前驅(qū)申窘，一個(gè)后驅(qū)
樹結(jié)構(gòu)：
根結(jié)點(diǎn)：無雙親，唯一
葉結(jié)點(diǎn)：無孩子孔轴，可以多個(gè)
中間結(jié)點(diǎn)：一個(gè)雙親多個(gè)孩子
樹的存儲結(jié)構(gòu)三種表示法：雙親表示法剃法、孩子表示法、孩子兄弟表示法路鹰。
二叉樹是n（n>=0）個(gè)結(jié)點(diǎn)的有限集合贷洲，該集合或者為空集（稱為空二叉樹），或者由一個(gè)根結(jié)點(diǎn)和兩顆互不相交的晋柱、分別稱為根結(jié)點(diǎn)的左子樹和右子樹的二叉樹組成优构。
二叉樹特點(diǎn)：
每個(gè)結(jié)點(diǎn)最多有兩顆子樹，所以二叉樹中不存在度大于2的結(jié)點(diǎn)雁竞。注意不是只有兩顆子樹钦椭，而是最多有。沒有子樹或者有一顆子樹都是可以的碑诉。
左子樹和右子樹是有順序的彪腔，次序不能任意顛倒。
即使樹中某結(jié)點(diǎn)只有一顆子樹联贩，也要區(qū)分它是左子樹還是右子樹漫仆。
二叉樹具有五種基本形態(tài)：
1.空二叉樹。
2.只有一個(gè)根結(jié)點(diǎn)泪幌。
3.根結(jié)點(diǎn)只有左子樹盲厌。
4.根結(jié)點(diǎn)只有右子樹。
5.根結(jié)點(diǎn)既有左子樹又有右子樹祸泪。
所有結(jié)點(diǎn)都只有左子樹的二叉樹叫左斜樹吗浩。所有結(jié)點(diǎn)都只有右子樹的二叉樹叫有斜樹。這兩者統(tǒng)稱為斜樹没隘。
在一顆二叉樹中懂扼，如果所有分支結(jié)點(diǎn)都存在左子樹和右子樹，并且所有葉子都在同一層上，這樣的二叉樹其為滿二叉樹阀湿。
