非常實用的數(shù)據(jù)結(jié)構(gòu)知識點總結(jié)

1、1數(shù)據(jù)結(jié)構(gòu)知識點概括第一章概論數(shù)據(jù)就是指能夠被計算機識別、存儲和加工處理的信息的載體。數(shù)據(jù)元素是數(shù)據(jù)的基本單位，可以由若干個數(shù)據(jù)項組成。數(shù)據(jù)項是具有獨立含義的最小標識單位。數(shù)據(jù)結(jié)構(gòu)的定義：邏輯結(jié)構(gòu)：從邏輯結(jié)構(gòu)上描述數(shù)據(jù)，獨立于計算機。線性結(jié)構(gòu)：一對一關(guān)系。線性結(jié)構(gòu)：多對多關(guān)系。存儲結(jié)構(gòu)：是邏輯結(jié)構(gòu)用計算機語言的實現(xiàn)。順序存儲結(jié)構(gòu)：如數(shù)組。鏈式存儲結(jié)構(gòu)：如鏈表。索引存儲結(jié)構(gòu)：稠密索引：每個結(jié)點都有索引項。稀疏索引：每組結(jié)點都有索引項。散列

2、存儲結(jié)構(gòu)：如散列表。數(shù)據(jù)運算。對數(shù)據(jù)的操作。定義在邏輯結(jié)構(gòu)上，每種邏輯結(jié)構(gòu)都有一個運算集合。常用的有：檢索、插入、刪除、更新、排序。數(shù)據(jù)類型：是一個值的集合以及在這些值上定義的一組操作的總稱。結(jié)構(gòu)類型：由用戶借助于描述機制定義，是導(dǎo)出類型。抽象數(shù)據(jù)類型ADT：是抽象數(shù)據(jù)的組織和與之的操作。相當于在概念層上描述問題。優(yōu)點是將數(shù)據(jù)和操作封裝在一起實現(xiàn)了信息隱藏。程序設(shè)計的實質(zhì)是對實際問題選擇一種好的數(shù)據(jù)結(jié)構(gòu)，設(shè)計一個好的算法。算法取決于數(shù)據(jù)

3、結(jié)構(gòu)。算法是一個良定義的計算過程，以一個或多個值輸入，并以一個或多個值輸出。評價算法的好壞的因素：算法是正確的；執(zhí)行算法的時間；執(zhí)行算法的存儲空間（主要是輔助存儲空間）；算法易于理解、編碼、調(diào)試。時間復(fù)雜度：是某個算法的時間耗費，它是該算法所求解問題規(guī)模n的函數(shù)。漸近時間復(fù)雜度：是指當問題規(guī)模趨向無窮大時，該算法時間復(fù)雜度的數(shù)量級。評價一個算法的時間性能時，主要標準就是算法的漸近時間復(fù)雜度。算法中語句的頻度不僅與問題規(guī)模有關(guān)，還與輸入實

4、例中各元素的取值相關(guān)。時間復(fù)雜度按數(shù)量級遞增排列依次為：常數(shù)階O（1）、對數(shù)階O（log2n）、線性階O（n）、線性對數(shù)階O（nlog2n）、平方階O（n^2）、立方階O（n^3）、……k次方階O（n^k）、指數(shù)階O（2^n）。空間復(fù)雜度：是某個算法的空間耗費，它是該算法所求解問題規(guī)模n的函數(shù)。3向的鏈。由頭指針head惟一確定。雙鏈表也可以頭尾相鏈接構(gòu)成雙（向）循環(huán)鏈表。雙鏈表上的插入和刪除時間復(fù)雜度均為O（1）。順序表和鏈表的比較：

5、基于空間：順序表的存儲空間是靜態(tài)分配，存儲密度為1；適于線性表事先確定其大小時采用。鏈表的存儲空間是動態(tài)分配，存儲密度＜1；適于線性表長度變化大時采用?；跁r間：順序表是隨機存儲結(jié)構(gòu)，當線性表的操作主要是查找時，宜采用。以插入和刪除操作為主的線性表宜采用鏈表做存儲結(jié)構(gòu)。若插入和刪除主要發(fā)生在表的首尾兩端，則宜采用尾指針表示的單循環(huán)鏈表。第三章棧和隊列棧（Stack）是僅限制在表的一端進行插入和刪除運算的線性表，稱插入、刪除這一端為棧頂，

6、另一端稱為棧底。表中無元素時為空棧。棧的修改是按后進先出的原則進行的，我們又稱棧為LIFO表（LastInFirstOut）。通常棧有順序棧和鏈棧兩種存儲結(jié)構(gòu)。棧的基本運算有六種：構(gòu)造空棧：InitStack（S）判?？眨篠tackEmpty（S）判棧滿：StackFull（S）進棧：Push（S，x）退棧：Pop（S）取棧頂元素：StackTop（S）在順序棧中有“上溢”和“下溢”的現(xiàn)象。“上溢”是棧頂指針指出棧的外面是出錯狀態(tài)。“下

7、溢”可以表示棧為空棧，因此用來作為控制轉(zhuǎn)移的條件。順序棧中的基本操作有六種：構(gòu)造空棧判?？张袟M進棧退棧取棧頂元素鏈棧則沒有上溢的限制，因此進棧不要判棧滿。鏈棧不需要在頭部附加頭結(jié)點，只要有鏈表的頭指針就可以了。鏈棧中的基本操作有五種：構(gòu)造空棧判?？者M棧退棧取棧頂元素隊列（Queue）是一種運算受限的線性表，插入在表的一端進行，而刪除在表的另一端進行，允許刪除的一端稱為隊頭（front），允許插入的一端稱為隊尾（rear），隊列的操作原