數(shù)據(jù)結(jié)構(gòu)與算法知識點必備

1、數(shù)據(jù)結(jié)構(gòu)與方法1、算法的基本特征：可行性、確定性、有窮性、擁有足夠的情報2、算法的基本運算和操作：算術(shù)運算、邏輯運算、關(guān)系運算、數(shù)據(jù)傳輸3、算法的基本控制結(jié)構(gòu)：順序結(jié)構(gòu)、選擇結(jié)構(gòu)、循環(huán)（重復(fù)）結(jié)構(gòu)4、算法設(shè)計的基本方法：列舉法、歸納法、遞推、遞歸、減半遞推技術(shù)、回溯法5、算法的復(fù)雜度主要包括：時間復(fù)雜度、空間復(fù)雜度6、算法的時間復(fù)雜度：指執(zhí)行算法所需要的計算工作量7、算法的空間復(fù)雜度：指執(zhí)行這個算法所需要的內(nèi)存空間8、數(shù)據(jù)結(jié)構(gòu)主要研究：數(shù)據(jù)的邏輯結(jié)構(gòu)、數(shù)據(jù)的存儲結(jié)構(gòu)、對各種數(shù)據(jù)結(jié)構(gòu)進行的運算9、數(shù)據(jù)結(jié)構(gòu)研究的目的：提高數(shù)據(jù)處理的效率10、數(shù)據(jù)處理的效率：數(shù)據(jù)處理的速度、減少處理過程中占用計算機

2、的存儲空間11、數(shù)據(jù)處理：指對數(shù)據(jù)集合中的各元素以各種方式進行運算12、數(shù)據(jù)元素：指在數(shù)據(jù)處理中，每一個需要處理的對象都可以抽象成數(shù)據(jù)元素13、數(shù)據(jù)結(jié)構(gòu)：指反映數(shù)據(jù)元素之間關(guān)系的數(shù)據(jù)元素集合的表示14、數(shù)據(jù)的邏輯結(jié)構(gòu)：指反映數(shù)據(jù)元素之間邏輯關(guān)系的數(shù)據(jù)結(jié)構(gòu)，兩要素：數(shù)據(jù)元素的集合、數(shù)據(jù)元素在集合上的關(guān)系15、數(shù)據(jù)的存儲結(jié)構(gòu)：指數(shù)據(jù)的邏輯結(jié)構(gòu)在計算機存儲空間的存放形式，常用的存儲結(jié)構(gòu)有：順序、鏈接、索引等16、數(shù)據(jù)結(jié)構(gòu)的圖形表示中每個元素加上方框成為結(jié)點17、數(shù)據(jù)結(jié)構(gòu)一般分為：線性結(jié)構(gòu)、非線性結(jié)構(gòu)18、線性結(jié)構(gòu)滿足：有且僅有一個根結(jié)點、每個結(jié)點最多有一個前件和后件、在一個線性結(jié)構(gòu)中插入和刪除任何一

3、個結(jié)點后還是線性結(jié)構(gòu)19、線性表定義：線性表是由n個數(shù)據(jù)元素a1、a2、a3、a4an組成的一個有限序列，表中每一個數(shù)據(jù)元素，除了第一個外，有且僅有一個前件，除了最后一個外，有且僅有一個后件20、非線性表的特征：有且只有一個根節(jié)點a1，它無前件、有且只有一個終結(jié)點an，它無后件、除了第一個和最后一個外，其他所有結(jié)點只有一個前件和一個后件21、線性表的長度：線性表中的結(jié)點的個數(shù)n成為線性表的長度，當(dāng)n=0時，成為空表22、線性表的順序存儲的特點：所有元素所占的存儲空間是連續(xù)的、各數(shù)據(jù)元素在存儲空間中是按邏輯順序一次存放的23、線性表的隨機存取地址計算公式：ADD(ai)=ADD(a1)+(i-1

4、)*k24、線性表的主要操作：插入、刪除、查找、排序、分解、合并、復(fù)制、逆轉(zhuǎn)25、棧的定義：棧是限定在一端進行插入和刪除的線性表，它按照“先進后出，后進先出”的原則組織數(shù)據(jù)26、棧的順序存儲：在程序設(shè)計語言中，一般一維數(shù)組S（1：m）作為棧的順序存儲空間，其中m為棧的最大容量27、棧的基本運算：入棧、退棧、讀棧頂元素28、入棧運算：首先將棧頂指針（top）加1，然后將新元素插入到棧頂指針指向的位置。當(dāng)棧頂指針已經(jīng)指向存儲空間的最后一個位置時，說明?？臻g已滿，稱為“上溢”錯誤29、退棧運算：首先將棧頂元素賦給一個指定的變量，然后將棧頂指針（top）減1。當(dāng)棧頂指針為0時，說明棧空，成為“下溢”錯

5、誤30、隊列的定義：隊列是指允許在一端進行插入，而在另一端進行刪除的線性表，它按照“先進先出”的原則組織數(shù)據(jù)31、循環(huán)隊列：在實際應(yīng)用中，隊列的順序存儲結(jié)構(gòu)一般采用循環(huán)隊列的形式。所謂循環(huán)隊列，就是將隊列存儲空間的最后一個位置繞到第一個位置，形成邏輯上的環(huán)狀空間，供隊列循環(huán)使用32、循環(huán)隊列空的狀態(tài)：s=0，且front=rear=m循環(huán)隊列滿的狀態(tài)：s=1，且front=rear33、循環(huán)隊列的基本運算：入隊、退隊34、入隊運算：同樣隊列滿時發(fā)生“上溢”錯誤35、退隊運算：同樣隊列空時發(fā)生“下溢”錯誤36、線性鏈表的基本概念：線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)37、線性鏈表的存儲結(jié)構(gòu)：線性鏈表的每個結(jié)點中

6、數(shù)據(jù)域存放數(shù)據(jù)元素的值，指針域存放好后件結(jié)點的存儲地址38、雙向鏈表的存儲結(jié)構(gòu)：雙向鏈表的存儲結(jié)構(gòu)比線性鏈表的存儲結(jié)構(gòu)多出一個指針域，它用來存放前面的存儲地址39、棧的鏈?zhǔn)浇Y(jié)構(gòu)：棧的鏈?zhǔn)浇Y(jié)構(gòu)基本上和線性鏈表的鏈?zhǔn)酱鎯Y(jié)構(gòu)相同。只是線性鏈表的鏈?zhǔn)酱鎯Y(jié)構(gòu)的頭指針變成了棧的鏈?zhǔn)浇Y(jié)構(gòu)的棧頂指針40、隊列的鏈?zhǔn)浇Y(jié)構(gòu)：隊列的鏈?zhǔn)浇Y(jié)構(gòu)和線性鏈表的存儲結(jié)構(gòu)基本相同。只是隊列的鏈?zhǔn)浇Y(jié)構(gòu)保持有兩個指針：一個指向隊列頭的頭指針，一個指向隊列尾的尾指針41、線性鏈表的主要運算：插入、刪除、合并、分解、逆轉(zhuǎn)、復(fù)制、排列、查找42、線性鏈表的特點43、樹結(jié)構(gòu)中結(jié)點的類型：根結(jié)點、父結(jié)點、子結(jié)點、葉子結(jié)點44、結(jié)點的度：

7、一個結(jié)點所擁有的后件個數(shù)成為結(jié)點的度45、樹的度：在所有結(jié)點中最大的度數(shù)46、樹的深度：樹的最大層，也就是樹的高度47、子樹：子結(jié)點構(gòu)成的樹48、二叉樹的特點：一是非空二叉樹只有一個根結(jié)點，二是每一個結(jié)點最多有兩棵子樹49、二叉樹的性質(zhì)：在二叉樹的第k層上，最多有2的（k-1）次方個結(jié)點 深度為m的二叉樹最多有2的m次方減1個結(jié)點 在任意一棵二叉樹中，度為0的結(jié)點（即葉子結(jié)點）總是比度為2的結(jié)點多一個 具有n個結(jié)點的二叉樹，其深度至少為log2(n)+1，其中l(wèi)og2(n)表示log2(n)的整數(shù)部分50、滿二叉樹定義：除最后一層外，每一層上的所有結(jié)點都有兩個子結(jié)點51、完全二叉樹定義：除最后一層外，每一層上的結(jié)點數(shù)均達到最大值，在最后一層上缺少右邊的若干結(jié)點52：二叉樹的存儲結(jié)構(gòu)：L（i）左指針域R（i）右指針域V（i）數(shù)據(jù)域53：二叉樹的遍歷集中用到了遞歸的思