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

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

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

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

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

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

6、另一端稱(chēng)為棧底。表中無(wú)元素時(shí)為空棧。棧的修改是按后進(jìn)先出的原則進(jìn)行的，我們又稱(chēng)棧為L(zhǎng)IFO表（LastInFirstOut）。通常棧有順序棧和鏈棧兩種存儲(chǔ)結(jié)構(gòu)。棧的基本運(yùn)算有六種：構(gòu)造空棧：InitStack（S）判棧空：StackEmpty（S）判棧滿(mǎn)：StackFull（S）進(jìn)棧：Push（S，x）退棧：Pop（S）取棧頂元素：StackTop（S）在順序棧中有“上溢”和“下溢”的現(xiàn)象?！吧弦纭笔菞ｍ斨羔樦赋鰲５耐饷媸浅鲥e(cuò)狀態(tài)?！跋?/p>

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