『壹』 棧的鏈式存儲結構是什麼
若是棧中元素的數目變化范圍較大或不清楚棧元素的數目，就應該考慮使用鏈式存儲結構。人們將用鏈式存儲結構表示的棧稱作「鏈棧」。鏈棧通常用一個無頭結點的單鏈表表示。由於棧的插入、刪除操作只能在一端進行，而對於單鏈表來說，在首端插入、刪除結點要比在尾端進行相對容易一些，所以將單鏈表的首端作為棧的頂端，即將單鏈表的頭指針作為棧頂指針。鏈棧如圖1所示。
圖1鏈棧的存儲示意
『貳』 c語言二級考試循環鏈表是循環隊列的鏈式存儲結構
循環隊列本身是一種順序存儲結構，而循環列表是一種鏈式存儲結構。兩者之間是平級關系。（用於解釋第一句話的錯誤原因。）
線性鏈表是線性表的鏈式存儲結構，包括單鏈表，雙鏈表，循環鏈表等。（補充說明）
隊列的順序存儲結構一般採用循環隊列的形式。（用於解釋第二句話的正確原因。）
『叄』 給出用數組描述的棧的存儲結構，以及操作
數據結構復習重點歸納[適於清華嚴版教材]
一、數據結構的章節結構及重點構成
數據結構學科的章節劃分基本上為：概論，線性表，棧和隊列，串，多維數組和廣義表，樹和二叉樹，圖，查找，內排，外排，文件，動態存儲分配。
對於絕大多數的學校而言，「外排，文件，動態存儲分配」三章基本上是不考的，在大多數高校的計算機本科教學過程中，這三章也是基本上不作講授的。所以，大家在這三章上可以不必花費過多的精力，只要知道基本的概念即可。但是，對於報考名校特別是該校又有在試卷中對這三章進行過考核的歷史，那麼這部分朋友就要留意這三章了。
按照以上我們給出的章節以及對後三章的介紹，數據結構的章節比重大致為：
概論：內容很少，概念簡單，分數大多隻有幾分，有的學校甚至不考。
線性表：基礎章節，必考內容之一。考題多數為基本概念題，名校考題中，鮮有大型演算法設計題。如果有，也是與其它章節內容相結合。
棧和隊列：基礎章節，容易出基本概念題，必考內容之一。而棧常與其它章節配合考查，也常與遞歸等概念相聯系進行考查。
串 ：基礎章節，概念較為簡單。專門針對於此章的大型演算法設計題很少，較常見的是根據KMP進行演算法分析。
多維數組及廣義表
：基礎章節，基於數組的演算法題也是常見的，分數比例波動較大，是出題的「可選單元」或「侯補單元」。一般如果要出題，多數不會作為大題出。數組常與「查找，排序」等章節結合來作為大題考查。
樹和二叉樹
：重點難點章節，各校必考章節。各校在此章出題的不同之處在於，是否在本章中出一到兩道大的演算法設計題。通過對多所學校的試卷分析，絕大多數學校在本章都曾有過出大型演算法設計題的歷史。
圖 ：重點難點章節，名校尤愛考。如果作為重點來考，則多出現於分析與設計題型當中，可與樹一章共同構成演算法設計大題的題型設計。
查找
：重點難點章節，概念較多，聯系較為緊密，容易混淆。出題時可以作為分析型題目給出，在基本概念型題目中也較為常見。演算法設計型題中可以數組結合來考查，也可以與樹一章結合來考查。
排序
：與查找一章類似，本章同屬於重點難點章節，且概念更多，聯系更為緊密，概念之間更容易混淆。在基本概念的考查中，尤愛考各種排序演算法的優劣比較此類的題。演算法設計大題中，如果作為出題，那麼常與數組結合來考查。
二、數據結構各章節重點勾劃：
第0章 概述
本章主要起到總領作用，為讀者進行數據結構的學習進行了一些先期鋪墊。大家主要注意以下幾點：數據結構的基本概念，時間和空間復雜度的概念及度量方法，演算法設計時的注意事項。本章考點不多，只要稍加註意理解即可。
第一章 線性表
作為線性結構的開篇章節，線性表一章在線性結構的學習乃至整個數據結構學科的學習中，其作用都是不可低估的。在這一章，第一次系統性地引入鏈式存儲的概念，鏈式存儲概念將是整個數據結構學科的重中之重，無論哪一章都涉及到了這個概念。
總體來說，線性表一章可供考查的重要考點有以下幾個方面：
1.線性表的相關基本概念，如：前驅、後繼、表長、空表、首元結點，頭結點，頭指針等概念。
2.線性表的結構特點，主要是指：除第一及最後一個元素外，每個結點都只有一個前趨和只有一個後繼。
3.線性表的順序存儲方式及其在具體語言環境下的兩種不同實現：表空間的靜態分配和動態分配。靜態鏈表與順序表的相似及不同之處。
4.線性表的鏈式存儲方式及以下幾種常用鏈表的特點和運算：單鏈表、循環鏈表，雙向鏈表，雙向循環鏈表。其中，單鏈表的歸並演算法、循環鏈表的歸並演算法、雙向鏈表及雙向循環鏈表的插入和刪除演算法等都是較為常見的考查方式。此外，近年來在不少學校中還多次出現要求用遞歸演算法實現單鏈表輸出（可能是順序也可能是倒序）的問題。
在鏈表的小題型中，經常考到一些諸如：判表空的題。在不同的鏈表中，其判表空的方式是不一樣的，請大家注意。
5.線性表的順序存儲及鏈式存儲情況下，其不同的優缺點比較，即其各自適用的場合。單鏈表中設置頭指針、循環鏈表中設置尾指針而不設置頭指針以及索引存儲結構的各自好處。
第二章 棧與隊列
棧與隊列，是很多學習DS的同學遇到第一隻攔路虎，很多人從這一章開始坐暈車，一直暈到現在。所以，理解棧與隊列，是走向DS高手的一條必由之路，。
學習此章前，你可以問一下自己是不是已經知道了以下幾點：
1.棧、隊列的定義及其相關數據結構的概念，包括：順序棧，鏈棧，共享棧，循環隊列，鏈隊等。棧與隊列存取數據（請注意包括：存和取兩部分）的特點。
2.遞歸演算法。棧與遞歸的關系，以及藉助棧將遞歸轉向於非遞歸的經典演算法：n!階乘問題，fib數列問題，hanoi問題，背包問題，二叉樹的遞歸和非遞歸遍歷問題，圖的深度遍歷與棧的關系等。其中，涉及到樹與圖的問題，多半會在樹與圖的相關章節中進行考查。
3.棧的應用：數值表達式的求解，括弧的配對等的原理，只作原理性了解，具體要求考查此為題目的演算法設計題不多。
4.循環隊列中判隊空、隊滿條件，循環隊列中入隊與出隊演算法。
如果你已經對上面的幾點了如指掌，棧與隊列一章可以不看書了。注意，我說的是可以不看書，並不是可以不作題哦。
第三章 串
經歷了棧一章的痛苦煎熬後，終於迎來了串一章的柳暗花明。
串，在概念上是比較少的一個章節，也是最容易自學的章節之一，但正如每個過來人所了解的，KMP演算法是這一章的重要關隘，突破此關隘後，走過去又是一馬平川的大好DS山河了，呵呵。
串一章需要攻破的主要堡壘有：
1.串的基本概念，串與線性表的關系（串是其元素均為字元型數據的特殊線性表），空串與空格串的區別，串相等的條件
2.串的基本操作，以及這些基本函數的使用，包括：取子串，串連接，串替換，求串長等等。運用串的基本操作去完成特定的演算法是很多學校在基本操作上的考查重點。
3.順序串與鏈串及塊鏈串的區別和聯系，實現方式。
4.KMP演算法思想。KMP中next數組以及nextval數組的求法。明確傳統模式匹配演算法的不足，明確next數組需要改進之外。其中，理解演算法是核心，會求數組是得分點。不用我多說，這一節內容是本章的重中之重。可能進行的考查方式是：求next和nextval數組值，根據求得的next或nextval數組值給出運用KMP演算法進行匹配的匹配過程。
第四章 數組與廣義表
學過程序語言的朋友，數組的概念我們已經不是第一次見到了，應該已經「一回生，二回熟」了，所以，在概念上，不會存在太大障礙。但作為考研課程來說，本章的考查重點可能與大學里的程序語言所關注的不太一樣，下面會作介紹。
廣義表的概念，是數據結構里第一次出現的。它是線性表或表元素的有限序列，構成該結構的每個子表或元素也是線性結構的，所以，這一章也歸入線性結構中。
本章的考查重點有：
1.多維數組中某數組元素的position求解。一般是給出數組元素的首元素地址和每個元素佔用的地址空間並組給出多維數組的維數，然後要求你求出該數組中的某個元素所在的位置。
2.明確按行存儲和按列存儲的區別和聯系，並能夠按照這兩種不同的存儲方式求解1中類型的題。
3.將特殊矩陣中的元素按相應的換算方式存入數組中。這些矩陣包括：對稱矩陣，三角矩陣，具有某種特點的稀疏矩陣等。熟悉稀疏矩陣的三種不同存儲方式：三元組，帶輔助行向量的二元組，十字鏈表存儲。掌握將稀疏矩陣的三元組或二元組向十字鏈表進行轉換的演算法。
4.廣義表的概念，特別應該明確表頭與表尾的定義。這一點，是理解整個廣義表一節演算法的基礎。近來，在一些學校中，出現了這樣一種題目類型：給出對某個廣義表L若干個求了若干次的取頭和取尾操作後的串值，要求求出原廣義表L。大家要留意。
5.與廣義表有關的遞歸演算法。由於廣義表的定義就是遞歸的，所以，與廣義表有關的演算法也常是遞歸形式的。比如：求表深度，復制廣義表等。這種題目，可以根據不同角度廣義表的表現形式運用兩種不同的方式解答：一是把一個廣義表看作是表頭和表尾兩部分，分別對表頭和表尾進行操作；二是把一個廣義表看作是若干個子表，分別對每個子表進行操作。
第五章 樹與二叉樹
從對線性結構的研究過度到對樹形結構的研究，是數據結構課程學習的一次躍變，此次躍變完成的好壞，將直接關繫到你到實際的考試中是否可以拿到高分，而這所有的一切，將最終影響你的專業課總分。所以，樹這一章的重要性，已經不說自明了。
總體來說，樹一章的知識點包括：
二叉樹的概念、性質和存儲結構，二叉樹遍歷的三種演算法（遞歸與非遞歸），在三種基本遍歷演算法的基礎上實現二叉樹的其它演算法，線索二叉樹的概念和線索化演算法以及線索化後的查找演算法，最優二叉樹的概念、構成和應用，樹的概念和存儲形式，樹與森林的遍歷演算法及其與二叉樹遍歷演算法的聯系，樹與森林和二叉樹的轉換。
下面我們來看考試中對以上知識的主要考查方法：
1.二叉樹的概念、性質和存儲結構
考查方法可有：直接考查二叉樹的定義，讓你說明二叉樹與普通雙分支樹的區別；考查滿二叉樹和完全二叉樹的性質，普通二叉樹的五個性質：第i層的最多結點數，深度為k的二叉樹的最多結點數，n0=n2+1的性質，n個結點的完全二叉樹的深度，順序存儲二叉樹時孩子結點與父結點之間的換算關系（左為：2*i，右為：2*i+1）。
二叉樹的順序存儲和二叉鏈表存儲的各自優缺點及適用場合，二叉樹的三叉鏈表表示方法。
2.二叉樹的三種遍歷演算法
這一知識點掌握的好壞，將直接關繫到樹一章的演算法能否理解，進而關繫到樹一章的演算法設計題能否順利完成。二叉樹的遍歷演算法有三種：先序，中序和後序。其劃分的依據是視其每個演算法中對根結點數據的訪問順序而定。不僅要熟練掌握三種遍歷的遞歸演算法，理解其執行的實際步驟，並且應該熟練掌握三種遍歷的非遞歸演算法。由於二叉樹一章的很多演算法，可以直接根據三種遞歸演算法改造而來（比如：求葉子個數），所以，掌握了三種遍歷的非遞歸演算法後，對付諸如：「利用非遞歸演算法求二叉樹葉子個數」這樣的題目就下筆如有神了。我會在另一篇系列文章（）里給出三種遍歷的遞歸和非遞歸演算法的背記版，到時請大家一定熟記。
3.可在三種遍歷演算法的基礎上改造完成的其它二叉樹演算法：
求葉子個數，求二叉樹結點總數，求度為1或度為2的結點總數，復制二叉樹，建立二叉樹，交換左右子樹，查找值為n的某個指定結點，刪除值為n的某個指定結點，諸如此類等等等等。如果你可以熟練掌握二叉樹的遞歸和非遞歸遍歷演算法，那麼解決以上問題就是小菜一碟了。
4.線索二叉樹：
線索二叉樹的引出，是為避免如二叉樹遍歷時的遞歸求解。眾所周知，遞歸雖然形式上比較好理解，但是消耗了大量的內存資源，如果遞歸層次一多，勢必帶來資源耗盡的危險，為了避免此類情況，線索二叉樹便堂而皇之地出現了。對於線索二叉樹，應該掌握：線索化的實質，三種線索化的演算法，線索化後二叉樹的遍歷演算法，基本線索二叉樹的其它演算法問題（如：查找某一類線索二叉樹中指定結點的前驅或後繼結點就是一類常考題）。
5.最優二叉樹（哈夫曼樹）：
最優二叉樹是為了解決特定問題引出的特殊二叉樹結構，它的前提是給二叉樹的每條邊賦予了權值，這樣形成的二叉樹按權相加之和是最小的。最優二叉樹一節，直接考查演算法源碼的很少，一般是給你一組數據，要求你建立基於這組數據的最優二叉樹，並求出其最小權值之和，此類題目不難，屬送分題。
6.樹與森林：
二叉樹是一種特殊的樹，這種特殊不僅僅在於其分支最多為2以及其它特徵，一個最重要的特殊之處是在於：二叉樹是有序的！即：二叉樹的左右孩子是不可交換的，如果交換了就成了另外一棵二叉樹，這樣交換之後的二叉樹與原二叉樹我們認為是不相同的兩棵二叉樹。但是，對於普通的雙分支樹而言，不具有這種性質。
樹與森林的遍歷，不像二叉樹那樣豐富，他們只有兩種遍歷演算法：先根與後根（對於森林而言稱作：先序與後序遍歷）。在難度比較大的考試中，也有基於此二種演算法的基礎上再進行擴展要求你利用這兩種演算法設計其它演算法的，但一般院校很少有這種考法，最多隻是要求你根據先根或後根寫出他們的遍歷序列。此二者的先根與後根遍歷與二叉樹中的遍歷演算法是有對應關系的：先根遍歷對應二叉樹的先序遍歷，而後根遍歷對應二叉樹的中序遍歷。這一點成為很多學校的考點，考查的方式不一而足，有的直接考此句話，有的是先讓你求解遍歷序列然後回答這個問題。二叉樹、樹與森林之所以能有以上的對應關系，全拜二叉鏈表所賜。二叉樹使用二叉鏈表分別存放他的左右孩子，樹利用二叉鏈表存儲孩子及兄弟（稱孩子兄弟鏈表），而森林也是利用二叉鏈表存儲孩子及兄弟。
樹一章，處處是重點，道道是考題，大家務必個個過關。
第六章 圖
如果說，從線性結構向樹形結構研究的轉變，是數據結構學科對數據組織形式研究的一次升華，那麼從樹形結構的研究轉到圖形結構的研究，則進一步讓我們看到了數據結構對於解決實際問題的重大推動作用。
圖這一章的特點是：概念繁多，與離散數學中圖的概念聯系緊密，演算法復雜，極易被考到，且容易出大題，尤其是名校，作為考研課程，如果不考查樹與圖兩章的知識，幾乎是不可想像的。
下面我們看一下圖這一章的主要考點以及這些考點的考查方式：
1.考查有關圖的基本概念問題：
這些概念是進行圖一章學習的基礎，這一章的概念包括：圖的定義和特點，無向圖，有向圖，入度，出度，完全圖，生成子圖，路徑長度，迴路，（強）連通圖，（強）連通分量等概念。與這些概念相聯系的相關計算題也應該掌握。
2.考查圖的幾種存儲形式：
圖的存儲形式包括：鄰接矩陣，（逆）鄰接表，十字鏈表及鄰接多重表。在考查時，有的學校是給出一種存儲形式，要求考生用演算法或手寫出與給定的結構相對應的該圖的另一種存儲形式。
3.考查圖的兩種遍歷演算法：深度遍歷和廣度遍歷
深度遍歷和廣度遍歷是圖的兩種基本的遍歷演算法，這兩個演算法對圖一章的重要性等同於「先序、中序、後序遍歷」對於二叉樹一章的重要性。在考查時，圖一章的演算法設計題常常是基於這兩種基本的遍歷演算法而設計的，比如：「求最長的最短路徑問題」和「判斷兩頂點間是否存在長為K的簡單路徑問題」，就分別用到了廣度遍歷和深度遍歷演算法。
4.生成樹、最小生成樹的概念以及最小生成樹的構造：PRIM演算法和KRUSKAL演算法。
考查時，一般不要求寫出演算法源碼，而是要求根據這兩種最小生成樹的演算法思想寫出其構造過程及最終生成的最小生成樹。
5.拓撲排序問題：
拓撲排序有兩種方法，一是無前趨的頂點優先演算法，二是無後繼的頂點優先演算法。換句話說，一種是「從前向後」的排序，一種是「從後向前」排。當然，後一種排序出來的結果是「逆拓撲有序」的。
6.關鍵路徑問題：
這個問題是圖一章的難點問題。理解關鍵路徑的關鍵有三個方面：一是何謂關鍵路徑，二是最早時間是什麼意思、如何求，三是最晚時間是什麼意思、如何求。簡單地說，最早時間是通過「從前向後」的方法求的，而最晚時間是通過「從後向前」的方法求解的，並且，要想求最晚時間必須是在所有的最早時間都已經求出來之後才能進行。這個問題拿來直接考演算法源碼的不多，一般是要求按照書上的演算法描述求解的過程和步驟。
在實際設計關鍵路徑的演算法時，還應該注意以下這一點：採用鄰接表的存儲結構，求最早時間和最晚時間要採用不同的處理方法，即：在演算法初始時，應該首先將所有頂點的最早時間全部置為0。關鍵路徑問題是工程進度控制的重要方法，具有很強的實用性。
7.最短路徑問題：
與關鍵路徑問題並稱為圖一章的兩只攔路虎。概念理解是比較容易的，關鍵是演算法的理解。最短路徑問題分為兩種：一是求從某一點出發到其餘各點的最短路徑；二是求圖中每一對頂點之間的最短路徑。這個問題也具有非常實用的背景特色，一個典型的應該就是旅遊景點及旅遊路線的選擇問題。解決第一個問題用DIJSKTRA演算法，解決第二個問題用FLOYD演算法。注意區分。
第七章 查找
在不少數據結構的教材中，是把查找與排序放入高級數據結構中的。應該說，查找和排序兩章是前面我們所學的知識的綜合運用，用到了樹、也用到了鏈表等知識，對這些數據結構某一方面的運用就構成了查找和排序。
現實生活中，search幾乎無處不在，特別是現在的網路時代，萬事離不開search，小到文檔內文字的搜索，大到INTERNET上的搜索，search占據了我們上網的大部分時間。
在復習這一章的知識時，你需要先弄清楚以下幾個概念：
關鍵字、主關鍵字、次關鍵字的含義；靜態查找與動態查找的含義及區別；平均查找長度ASL的概念及在各種查找演算法中的計算方法和計算結果，特別是一些典型結構的ASL值，應該記住。
在DS的教材中，一般將search分為三類：1st，在順序表上的查找；2nd，在樹表上的查找；3rd，在哈希表上的查找。下面詳細介紹其考查知識點及考查方式：
1.線性表上的查找：
主要分為三種線性結構：順序表，有序順序表，索引順序表。對於第一種，我們採用傳統查找方法，逐個比較。對於及有序順序表我們採用二分查找法。對於第三種索引結構，我們採用索引查找演算法。考生需要注意這三種表下的ASL值以及三種演算法的實現。其中，二分查找還要特別注意適用條件以及其遞歸實現方法。
2.樹表上的查找：
這是本章的重點和難點。由於這一節介紹的內容是使用樹表進行的查找，所以很容易與樹一間的某些概念相混淆。本節內容與樹一章的內容有聯系，但也有很多不同，應注意規納。樹表主要分為以下幾種：二叉排序樹，平衡二叉樹，B樹，鍵樹。其中，尤以前兩種結構為重，也有部分名校偏愛考B樹的。由於二叉排序樹與平衡二叉樹是一種特殊的二叉樹，所以與二叉樹的聯系就更為緊密，二叉樹一章學好了，這里也就不難了。
二叉排序樹，簡言之，就是「左小右大」，它的中序遍歷結果是一個遞增的有序序列。平衡二叉樹是二叉排序樹的優化，其本質也是一種二叉排序樹，只不過，平衡二叉樹對左右子樹的深度有了限定：深度之差的絕對值不得大於1。對於二叉排序樹，「判斷某棵二叉樹是否二叉排序樹」這一演算法經常被考到，可用遞歸，也可以用非遞歸。平衡二叉樹的建立也是一個常考點，但該知識點歸根結底還是關注的平衡二叉樹的四種調整演算法，所以應該掌握平衡二叉樹的四種調整演算法，調整的一個參照是：調整前後的中序遍歷結果相同。
B樹是二叉排序樹的進一步改進，也可以把B樹理解為三叉、四叉....排序樹。除B樹的查找演算法外，應該特別注意一下B樹的插入和刪除演算法。因為這兩種演算法涉及到B樹結點的分裂和合並，是一個難點。B樹是報考名校的同學應該關注的焦點之一。
鍵樹也稱字元樹，特別適用於查找英文單詞的場合。一般不要求能完整描述演算法源碼，多是根據演算法思想建立鍵樹及描述其大致查找過程。
3.基本哈希表的查找演算法：
哈希一詞，是外來詞，譯自「hash」一詞，意為：散列或雜湊的意思。哈希表查找的基本思想是：根據當前待查找數據的特徵，以記錄關鍵字為自變數，設計一個function，該函數對關鍵字進行轉換後，其解釋結果為待查的地址。基於哈希表的考查點有：哈希函數的設計，沖突解決方法的選擇及沖突處理過程的描述。
第八章 內部排序
內排是DS課程中最後一個重要的章節，建立在此章之上的考題可以有多種類型：填空，選擇，判斷乃至大型演算法題。但是，歸結到一點，就是考查你對書本上的各種排序演算法及其思想以及其優缺點和性能指標（時間復雜度）能否了如指掌。
這一章，我們對重點的規納將跟以上各章不同。我們將從以下幾個側面來對排序一章進行不同的規納，以期能更全面的理解排序一章的總體結構及各種演算法。
從排序演算法的種類來分，本章主要闡述了以下幾種排序方法：插入、選擇、交換、歸並、計數等五種排序方法。
其中，在插入排序中又可分為：直接插入、折半插入、2路插入、希爾排序。這幾種插入排序演算法的最根本的不同點，說到底就是根據什麼規則尋找新元素的插入點。直接插入是依次尋找，折半插入是折半尋找。希爾排序，是通過控制每次參與排序的數的總范圍「由小到大」的增量來實現排序效率提高的目的。
交換排序，又稱冒泡排序，在交換排序的基礎上改進又可以得到快速排序。快速排序的思想，一語以敝之：用中間數將待排數據組一分為二。快速排序，在處理的「問題規模」這個概念上，與希爾有點相反，快速排序，是先處理一個較大規模，然後逐漸把處理的規模降低，最終達到排序的目的。
選擇排序，相對於前面幾種排序演算法來說，難度大一點。具體來說，它可以分為：簡單選擇、樹選擇、堆排。這三種方法的不同點是，根據什麼規則選取最小的數。簡單選擇，是通過簡單的數組遍歷方案確定最小數；樹選擇，是通過「錦標賽」類似的思想，讓兩數相比，不斷淘汰較大（小）者，最終選出最小（大）數；而堆排序，是利用堆這種數據結構的性質，通過堆元素的刪除、調整等一系列操作將最小數選出放在堆頂。堆排序中的堆建立、堆調整是重要考點。樹選擇排序，也曾經在一些學校中的大型演算法題中出現，請大家注意。
歸並排序，故名思義，是通過「歸並」這種操作完成排序的目的，既然是歸並就必須是兩者以上的數據集合才可能實現歸並。所以，在歸並排序中，關注最多的就是2路歸並。演算法思想比較簡單，有一點，要銘記在心：歸並排序是穩定排序。
基數排序，是一種很特別的排序方法，也正是由於它的特殊，所以，基數排序就比較適合於一些特別的場合，比如撲克牌排序問題等。基數排序，又分為兩種：多關鍵字的排序（撲克牌排序），鏈式排序（整數排序）。基數排序的核心思想也是利用「基數空間」這個概念將問題規模規范、變小，並且，在排序的過程中，只要按照基排的思想，是不用進行關鍵字比較的，這樣得出的最終序列就是一個有序序列。
本章各種排序演算法的思想以及偽代碼實現，及其時間復雜度都是必須掌握的，學習時要多注意規納、總結、對比。此外，對於教材中的10.7節，要求必須熟記，在理解的基礎上記憶，這一節幾乎成為很多學校每年的必考點。
至此，數據結構所有章節的章節重點問題，我們已經規納完畢，使用清華嚴版教材的同學，在復習的同時，可以參照本貼給出的重點進行復習。但是，由於作者本人水平有限，可能有很多考點沒有規納出來，也可能有些考點規納有誤，在此，作者本人誠懇希望諸位朋友直面提出，我會不斷完善和發布新的關於數據結構復習的總結以及筆記
嚴蔚敏數據結構為主的筆記二
第二章：線性表(包括習題與答案及要點)
--------------------------------------------------------------------------------
本章的重點是掌握順序表和單鏈表上實現的各種基本演算法及相關的時間性能分析，難點是使用本章所學的基本知識設計有效演算法解決與線性表相關的應用問題。
要求達到<識記>層次的內容有:線性表的邏輯結構特徵；線性表上定義的基本運算，並利用基本運算構造出較復雜的運算。
要求達到<綜合應用>層次的內容有：順序表的含義及特點，順序表上的插入、刪除操作及其平均時間性能分析，解決簡單應用問題。
鏈表如何表示線性表中元素之間的邏輯關系；單鏈表、雙鏈表、循環鏈表鏈接方式上的區別；單鏈表上實現的建表、查找、插入和刪除等基本演算法及其時間復雜度。循環鏈表上尾指針取代頭指針的作用，以及單循環鏈表上的演算法與單鏈表上相應演算法的異同點。雙鏈表的定義和相關演算法。利用鏈表設計演算法解決簡單應用問題。
要求達到<領會>層次的內容就是順序表和鏈表的比較，以及如何選擇其一作為其存儲結構才能取得較優的時空性能。
--------------------------------------------------------------------------------
線性表的邏輯結構特徵是很容易理解的，如其名，它的邏輯結構特徵就好象是一條線，上面打了一個個結，很形象的，如果這條線上面有結，那麼它就是非空表，只能有一個開始結點，有且只能有一個終端結點，其它的結前後所相鄰的也只能是一個結點(直接前趨和直接後繼)。
關於線性表上定義的基本運算，主要有構造空表、求表長、取結點、查找、插入、刪除等。
--------------------------------------------------------------------------------
線性表的邏輯結構和存儲結構之間的關系。在計算機中，如何把線性表的結點存放到存儲單元中，就有許多方法，最簡單的方法就是按順序存儲。就是按線性表的邏輯結構次序依次存放在一組地址連續的存儲單元中。在存儲單元中的各元素的物理位置和邏輯結構中各結點相鄰關系是一致的。
在順序表中實現的基本運算主要討論了插入和刪除兩種運算。相關的演算法我們通過練習掌握。對於順序表的插入和刪除運算，其平均時間復雜度均為O(n)。
--------------------------------------------------------------------------------
線性表的鏈式存儲結構。它與順序表不同，鏈表是用一組任意的存儲單元來存放線性表的結點，這組存儲單元可以分布在內存中任何位置上。因此，鏈表中結點的邏輯次序和物理次序不一定相同。所以為了能正確表示結點間的邏輯關系，在存儲每個結點值的同時，還存儲了其後繼結點的地址信息(即
『肆』 用單鏈表表示的鏈式棧的棧底在鏈表的表尾位置 這句話對還是錯，盡量給下理由，必採納，謝謝
這句話是對的。
只能將表頭作為棧頂。如果用表尾作為棧頂，出棧後將無法找到前一個結點，因為是單向。
單鏈表的隊頭可以在O(1)的時間下，實現鏈表的插入跟刪除。對於單鏈表的插入跟刪除，存在尾指針的話 插入O（1），刪除O(n)；不存在尾指針的話， 插入O(n), 刪除O(n)。
顯然對於隊列而言，我們希望EnQueue和DelQueue的操作都是O（1），而且這兩個操作必然在鏈表的兩端，不難發現，對於鏈隊列的話，只存在一種可行的情況，就是使用帶尾指針的鏈表結構， 其中頭指針負責刪除，尾指針負責插入。
再根據隊列的定義可知，刪除操作發生在隊頭，插入操作發生在隊尾。
(4)設鏈式棧用循環單鏈表存儲擴展閱讀
單鏈表的特點：
當訪問過一個節點後，只能接著訪問它的後繼節點，而無法訪問它的前趨節點。
鏈表的第一個結點和最後一個結點，分別稱為鏈表的 首結點和 尾結點。
尾結點的特徵是其 next 引用為空（null）。
鏈表中每個結點的 next 引用都相當於一個指針，指向另一個結點，
藉助這些 next 引用，我們可以從鏈表的首結點移動到尾結點。
在單鏈表中通常使用 head 引用來指向鏈表的首結點，由 head 引用可以完成對整個鏈表中所有節點的訪問。
在單鏈表結構中還需要注意的一點是，由於每個結點的數據域都是一個 Object 類的對象，
因此，每個數據元素並非真正如圖中那樣，而是在結點中的數據域通過一個 Object類的對象引用來指向數據元素的。
與數組類似，單鏈表中的結點也具有一個線性次序，即如果結點 P 的 next 引用指向結點 S，則 P 就是 S 的直接前驅，S 是 P 的直接後續。
『伍』 假定棧用單鏈表的存儲結構表示，棧的棧頂指針為top，進行退棧時執行的操作
top->next指向棧頂，top->next->next指向棧頂第二個元素，現在要退棧就是移除棧頂元素，而第二個元素現在變成了棧頂元素了，所以選D
『陸』 c語言鏈表問題
鏈式存儲結構就是鏈表。
單鏈表是只有一個方向的鏈式存儲結構。
單鏈表實現棧的意思就是用單向鏈式存儲結構實現棧，但是注意，頭結點作為棧頂，這樣出棧入棧操作的時間復雜度是O(1)，如果頭結點作為棧底則需要遍歷整個鏈表。
鏈式存儲結構有很多種，單鏈表、雙鏈表、十字鏈表等，一般用到的確實就只有兩種，就是單和雙，但是細分又可分為帶或不帶頭結點，是否是循環鏈表等。
棧和隊列是受限的線性表，有其特殊用途，隨著學習的深入你就知道了，比方說計算表達式，就用到了棧（操作符棧和操作數棧），避免了很多誤操作，直接用鏈表當然也可以，但是不保險，可能會誤操作或被別有用心的人利用。
『柒』 假定棧用單鏈表的存儲結構表示，棧的棧頂指針為top，進行退棧時執行的操作
用c++還是java描述？
假設用c++吧，思想都一樣
length--;//棧頂指針後移
Node<T> *currentNode=tail;
Node<T> *tempTail=head;
for(int i=1; i<=length; i++)//這個地方到底是小於還是小於等於自己調試一下吧
tempTail=tempTail->next;//取到出棧後應該為尾節點；
delete tail;
tail=tempTail;//恢復尾節點
return currentNode;
『捌』 棧往往用單鏈表實現，可以用雙鏈表嗎哪個更好
棧往往用單鏈表實現，可以用雙鏈表，雙鏈表更好。
最好是用數組，其次應該用雙鏈，因為它是雙向變化的。雙鏈表除了有一個指向下一結點的指針外，還有一個指向前一結點的指針，可以通過prev()快速找到前一結點，顧名思義，單鏈表只能單向讀取。
介紹
棧是只能在某一端插入和刪除的特殊線性表。它按照後進先出的原則存儲數據，先進入的數據被壓入棧底（push），最後的數據在棧頂（top），需要讀數據的時候從棧頂開始彈出數據（top）最後一個數據被第一個讀出來。鏈式棧中的元素以Node的形式存儲，節點Node中存有此節點存於棧中的元素以及指向下個節點的指針。鏈式棧的數據成員只用保存指向棧頂節點的指針 *top_node。
『玖』 C語言二級考試循環鏈表是循環隊列的鏈式存儲結構
循環隊列本身是一種順序存儲結構，而循環列表是一種鏈式存儲結構。兩者之間是平級關系。
線性鏈表是線性表的鏈式存儲結構，包括單鏈表，雙鏈表，循環鏈表等。
隊列的順序存儲結構一般採用循環隊列的形式。
循環隊列的操作是按數組取摸運算的，所以是順序存儲，而循環鏈表本身就是收尾相連的，所以循環鏈表不是循環隊列，兩種不同的存儲結構，雖然實現的功能是一樣的，實現循環兩種方式 順序存儲就是循環隊列，鏈式存儲就是循環鏈表。
(9)設鏈式棧用循環單鏈表存儲擴展閱讀：
1、比順序存儲結構的存儲密度小(鏈式存儲結構中每個結點都由數據域與指針域兩部分組成，相比順序存儲結構增加了存儲空間)。
2、邏輯上相鄰的節點物理上不必相鄰。
3、插入、刪除靈活 (不必移動節點，只要改變節點中的指針)。
4、查找節點時鏈式存儲要比順序存儲慢。
5、每個節點是由數據域和指針域組成。
6、由於簇是隨機分配的，這也使數據刪除後覆蓋幾率降低，恢復可能提高。
『拾』 長度為n的鏈隊列用單循環鏈表表示，若只設頭指針，則怎樣進行入隊和出隊操作；若只設尾指針呢
就行了，准過！
第一章：緒論
1.1：數據結構課程的任務是：討論數據的各種邏輯結構、在計算機中的存儲結構以及各種操作的演算法設計。
1.2：數據：是客觀描述事物的數字、字元以及所有的能輸入到計算機中並能被計算機接收的各種集合的統稱。
數據元素：表示一個事物的一組數據稱作是一個數據元素，是數據的基本單位。
數據項：是數據元素中有獨立含義的、不可分割的最小標識單位。
數據結構概念包含三個方面：數據的邏輯結構、數據的存儲結構的數據的操作。
1.3數據的邏輯結構指數據元素之間的邏輯關系，用一個數據元素的集合定義在此集合上的若干關系來表示，數據結構可以分為三種：線性結構、樹結構和圖。
1.4：數據元素及其關系在計算機中的存儲表示稱為數據的存儲結構，也稱為物理結構。
數據的存儲結構基本形式有兩種：順序存儲結構和鏈式存儲結構。
2.1：演算法：一個演算法是一個有窮規則的集合，其規則確定一個解決某一特定類型問題的操作序列。演算法規則需滿足以下五個特性：
輸入——演算法有零個或多個輸入數據。
輸出——演算法有一個或多個輸出數據，與輸入數據有某種特定關系。
有窮性——演算法必須在執行又窮步之後結束。
確定性——演算法的每個步驟必須含義明確，無二義性。
可行性——演算法的每步操作必須是基本的，它們的原則上都能夠精確地進行，用筆和紙做有窮次就可以完成。
有窮性和可行性是演算法最重要的兩個特徵。
2.2：演算法與數據結構：演算法建立數據結構之上，對數據結構的操作需用演算法來描述。
演算法設計依賴數據的邏輯結構，演算法實現依賴數據結構的存儲結構。
2.3：演算法的設計應滿足五個目標：
正確性：演算法應確切的滿足應用問題的需求，這是演算法設計的基本目標。
健壯性：即使輸入數據不合適，演算法也能做出適當的處理，不會導致不可控結
高時間效率：演算法的執行時間越短，時間效率越高。 果。
高空間效率：演算法執行時佔用的存儲空間越少，空間效率越高。
可讀性：演算法的可讀性有利於人們對演算法的理解。
2.4：度量演算法的時間效率，時間復雜度，（課本39頁）。
2.5：遞歸定義：即用一個概念本身直接或間接地定義它自己。遞歸定義有兩個條件：
至少有一條初始定義是非遞歸的，如1！=1.
由已知函數值逐步遞推計算出未知函數值，如用（n-1）！定義n！。
第二章：線性表
1.1線性表：線性表是由n(n>=0)個類型相同的數據元素a0,a1,a2,…an-1,組成的有限序列,記作： LinearList = (a0,a1,a2,…an-1)
其中，元素ai可以是整數、浮點數、字元、也可以是對象。n是線性表的元素個數，成為線性表長度。若n=0，則LinearList為空表。若n>0，則a0沒有前驅元素，an-1沒有後繼元素，ai（0<i<n-1）有且僅有一個直接前驅元素ai-1和一個直接後繼元素ai+1。
1.2線性表的順序存儲是用一組連續的內存單元依次存放線性表的數據元素，元素在內存的物理存儲次序與它們在線性表中的邏輯次序相同。
線性表的數據元素數據同一種數據類型，設每個元素佔用c位元組，a0的存儲地址為
Loc（a0），則ai的存儲地址Loc（ai）為：Loc（ai） = Loc（a0）+ i*c
數組是順序存儲的隨機存儲結構，它佔用一組連續的存儲單元，通過下標識別元素，元素地址是下標的線性函數。
1.3：順序表的插入和刪除操作要移動數據元素。平均移動次數是 屬數據表長度的一半。（課本第50頁）
1.4：線性表的鏈式存儲是用若乾地址分散的存儲單元存儲數據元素，邏輯上相鄰的數據元素在物理位置上不一定相鄰，必須採用附加信息表示數據元素之間的順序關系。
它有兩個域組成：數據域和地址域。通常成為節點。（課本第55頁及56頁）
1.5單鏈表（課本56頁）
單鏈表的遍歷：Node<E> p = head; while(p!=null)
單鏈表的插入和刪除操作非常簡便，只要改變節點間的鏈接關系，不需移動數據元素。
單鏈表的插入操作：1）：空表插入/頭插入 2)中間插入/尾插入
if(head == null) Node<E> q = new Node<E>(x);
{ head = new Node<E>(x); q.next = p.next;
}else{ p.next = q;
Node<E> q=new Node<E>(x); 中間插入或尾插入都不會改變單表
q.next = head; 的頭指針head。
head = q;
}
單鏈表的刪除操作：
頭刪除：head = head.next;
中間/尾刪除：if(p.next!=null)
循環單鏈表：如果單鏈表最後一個節點的next鏈保存單鏈表的頭指針head值，則該單鏈表成為環形結構，稱為循環單鏈表。（課本67）
若rear是單鏈表的尾指針，則執行（rear.next=head;）語句，使單鏈表成為一條循環單鏈表。當head.next==head時，循環單鏈表為空。
1.6：雙鏈表結構：雙鏈表的每個結點有兩個鏈域，分別指向它的前驅和後繼結點，
當head.next==null時，雙鏈表為空。
設p指向雙鏈表中非兩端的某個結點，則成立下列關系：p=p.next.prev=p.prev.next。
雙鏈表的插入和刪除：1）插入 2)刪除
q=new DLinkNode（x）； p.prev.next = p.next;
q.prev=p.prev;q.next =p; if(p.next=null){
p.prev.next = q;p.prev=q; (p.next).prev = p.prev;}
循環雙鏈表：當head.next==head且head.prev==head時，循環雙鏈表為空。
第三章：棧和隊列
1.1棧：棧是一種特殊的線性表，其中插入和刪除操作只允許在線性表的一端進行。允許操作的一端稱為棧頂，不允許操作的一端稱為棧底。棧有順序棧和鏈式棧。
棧中插入元素的操作稱為入棧，刪除元素的操作稱為出棧。沒有元素的中稱為空棧。
棧的進出棧順序：後進先出，先進後出。（及75頁的思考題）。
1.2：隊列：隊列是一種特殊的線性表，其中插入和刪除操作分別在線性表的兩端進行。
向隊列中插入元素的過程稱為入隊，刪除元素的過程稱為出對，允許入隊的一端稱為隊尾，允許出隊的一端稱為對頭。沒有元素的隊列稱為空隊列。隊列是先進先出。
第四章：串
1.1：串是一種特殊的線性表，其特殊性在於線性表中的每個元素是一個字元。一個串記為： s=「s0s1s2…sn-1」 其中n>=0,s是串名，一對雙引號括起來的字元序列s0s1s2…sn-1是串值，si（i=0，1，2，…n-1）為特定字元集合中的一個字元。一個串中包含的字元個數稱為串的長度。
長度為0的串稱為空串，記作「」，而由一個或多個空格字元構成的字元串稱為空格串。
子串：由串s中任意連續字元組成的一個子序列sub稱為s的子串，s稱為sub的主串。子串的序號是指該子串的第一個字元在主串中的序號。
串比較：兩個串可比較是否相等，也可比較大小。兩個串（子串）相等的充要條件是兩個串（子串）的長度相同，並且各對應位置上的字元也相同。
兩個串的大小由對應位置的第一個不同字元的大小決定，字元比較次序是從頭開始依次向後。當兩個串長度不等而對應位置的字元都相同時，較長的串定義為較「大」。
第五章：數組和廣義表
1.1：數組是一種數據結構，數據元素具有相同的數據類型。一維數組的邏輯結構是線性表，多維數組是線性表的擴展。
1.2：一維數組：一維數組採用順序存儲結構。一個一維數組佔用一組連續的存儲單元。
設數組第一個元素a0的存儲地址為Loc（a0），每個元素佔用c位元組，則數組其他元素ai的存儲地址Loc（ai）為： Loc（ai）= Loc（a0）+i*c
數組通過下標識別元素，元素地址是下標的線性函數。一個下標能夠唯一確定一個元素，所劃給的時間是O（1）。因此數組是隨機存取結構，這是數組最大的優點。
1.3：多維數組的遍歷：有兩種次序：行主序和列主序。
行主序：以行為主序，按行遞增訪問數組元素，訪問完第i行的所有元素之後再訪問第i+1行的元素，同一行上按列遞增訪問數組元素。
a00,a01,…a0(n-1), a10,a11,…a1(n-1),…a(m-1)0,a(m-1)1,…,a(m-1)(n-1)
2)列主序：以列為主序，按列遞增訪問數組元素，訪問完第j列的所有元素之後再訪問第j+1列的元素，同一列上按列遞增訪問數組元素。
多維數組的存儲結構：多維數組也是由多個一維數組組合而成，組合方式有一下兩種。
靜態多維數組的順序存儲結構：可按行主序和列主序進行順序存儲。
按行主序存儲時，元素aij的地址為：Loc（aij）= Loc（a00）+（i*n+j）*c
按列主序存儲時，Loc（aij）= Loc（a00）+（j*m+i）*c
動態多維數組的存儲結構。
二維數組元素地址就是兩個下標的線性函數。無論採用哪種存儲結構，多維數組都是基於一維數組的，因此也只能進行賦值、取值兩種存取操作，不能進行插入，刪除操作。
第六章：
樹是數據元素（結點）之間具有層次關系的非線性結構。在樹結構中，除根以外的結點只有一個直接前驅結點，可以有零至多個直接後繼結點。根沒有前驅結點。
樹是由n（n>=0）個結點組成的有限集合（樹中元素通常稱為結點）。N=0的樹稱為空樹；n>0大的樹T；
@有一個特殊的結點稱為根結點，它只有後繼結點，沒有前驅結點。
@除根結點之外的其他結點分為m（m>=0）個互不相交的集合T0,T1,T3……..,Tm-1，其中每個集合Ti（0<=i<m）本身又是一棵樹，稱為根的子樹。
樹是遞歸定義的。結點是樹大的基本單位，若干個結點組成一棵子樹，若干棵互不相交的子樹組成一棵樹。樹的每個結點都是該樹中某一棵子樹的根。因此，樹是由結點組成的、結點之間具有層次關系大的非線性結構。
結點的前驅結點稱為其父母結點，反之，結點大的後繼結點稱為其孩子結點。一棵樹中，只有根結點沒有父母結點，其他結點有且僅有一個父母結點。
擁有同一個父母結點的多個結點之間稱為兄弟結點。結點的祖先是指從根結點到其父母結點所經過大的所有結點。結點的後代是指該結點的所有孩子結點，以及孩子的孩子等。
結點的度是結點所擁有子樹的棵數。度為0的結點稱為葉子結點，又叫終端結點；樹中除葉子結點之外的其他結點稱為分支結點，又叫非葉子結點或非終端結點。樹的度是指樹中各結點度的最大值。
結點的層次屬性反應結點處於樹中的層次位置。約定根結點的層次為1，其他結點的層次是其父母結點的層次加1。顯然，兄弟結點的層次相同。
樹的高度或深度是樹中結點的最大層次樹。
設樹中x結點是y結點的父母結點，有序對（x，y）稱為連接這兩個結點的分支，也稱為邊。
設（X0,X1,….,Xk-1）是由樹中結點組成的一個序列，且（Xi，Xi+1）（0<=i<k-1）都是樹中的邊，則該序列稱為從X0到Xk-1的一條路徑。路徑長度為路徑上的邊數。
在樹的定義中，結點的子樹T0，T1…..,Tm-1之間沒有次序，可以交換位置，稱為無序樹，簡稱樹。如果結點的子樹T0,T1……,Tm-1從左到右是有次序的，不能交換位置，則 稱該樹為有序樹。
森林是m（m>=0）棵互不相乾的樹的集合。給森林加上一個根結點就變成一棵樹，將樹的根節點刪除就變成森林。
二叉樹的性質1：若根結點的層次為1，則二叉樹第i層最多有2 的i-1次方（i>=1）個結點。
二叉樹的性質2：在高度為k的二叉樹中，最多有2的k次方減一個結點。
二叉樹的性質3：設一棵二叉樹的葉子結點數為n0,2度結點數為n2，則n0=n2+1。
一棵高度為k的滿二叉樹是具有2的k次方減一個結點的二叉樹。滿二叉樹中每一層的結點數目都達到最大值。對滿二叉樹的結點進行連續編號，約定根節點的序號為0，從根節點開始，自上而下，每層自左至右編號。
一棵具有n個結點高度為k的二叉樹，如果他的每個節點都與高度為k的滿二叉樹中序號為0~n-1
的結點一一對應，則這棵二叉樹為為完全二叉樹。
滿二叉樹是完全二叉樹，而完全二叉樹不一定是滿二叉樹。完全二叉樹的第1~k-1層是滿二叉樹第k層不滿，並且該層所有結點必須集中在該層左邊的若干位置上。
二叉樹的性質4：一棵具有n個結點的完全二叉樹，其高度k=log2n的絕對值+1
二叉樹的性質5：一棵具有n個結點的完全二叉樹，對序號為i的結點，有
@若i=0，則i為根節點，無父母結點；若i>0，則i的父母結點的序號為[（i-1）/2]。
@若2i+1<n，則i的左孩子結點序號為2i+1；否則i無左孩子。
@若2i+2<n，則i的右孩子結點的序號為2i+2，否則i無右孩子。
二叉樹的遍歷
二叉樹的遍歷是按照一定規則和次序訪問二叉樹中的所有結點，並且每個結點僅被訪問一次。
二叉樹的三種次序遍歷
1：先根次序；訪問根節點，遍歷左子樹，遍歷右子樹。
2：中根次序；遍歷左子樹，訪問右子樹，遍歷右子樹。
3：後根次序；遍歷左子樹，遍歷右子樹，訪問根節點。
先根次序遍歷時，最先訪問根節點；後根次序遍歷時，最後訪問根節點；中根次序遍歷時，左子樹上的結點在根節點之前訪問，右子樹上的結點在根節點之後訪問。
二叉樹的插入和刪除操作P147
二叉樹的層次遍歷P149
習題P167 6—10，6—19
第七章
圖是由定點集合及頂點間的關系集合組成的一種數據關邊系。頂點之間的關系成為邊。一個圖G記為G=（V,E），V是頂點A的有限集合，E是邊的有限集合。即 V=
E=或E=其中Path（A,B）表示從頂點A到B的一條單向通路，即Path（A,B）是有方向的。
無向圖中的邊事沒有方向，每條邊用兩個頂點的無序對表示。
有向圖中的邊是有方向，每條邊用兩個頂點的有序對表示。
完全圖指圖的邊數達到最大值。n個頂點的完全圖記為Kn。無向完全圖Kn的邊數為n*（n-1）/2,有向完全圖Kn的邊數為n*（n-1）。
子圖：設圖G==(V,E),G』=(V』,E』)，若V』包含於V且E』包含於E,則稱圖G』是G的子圖。若G』是G的真子圖。
連通圖：在無向圖G中，若從頂點VI到Vj有路徑，則稱Vi和Vj是聯通的。若圖G中任意一對頂點Vi和Vj（Vi不等於Vj）都是聯通的，則稱G為連通圖。非連通圖的極大聯通子圖稱為該圖的聯通分量。
強連通圖：在有向圖中，若在每一對頂點Vi和Vj（Vi不等於Vj）之間都存在一條從Vi到Vj的路徑，也存在一條從Vi到Vj的路徑，也存在一條從Vi到Vj的路徑，則稱該圖的強連通圖。非強連通圖的極大強連通子圖稱為該圖的強連通圖分量。
圖的遍歷
遍歷圖是指從圖G中任意一個頂點V出發，沿著圖中的邊前行，到達並訪問圖中的所有頂點，且每個頂點僅被訪問一次。遍歷圖要考慮一下三個問題：
@指定遍歷的第一個訪問頂點
@由於一個頂點可能與多個頂點相鄰，因此要在多個鄰接頂點之間約定一種訪問次序。
@由於圖中可能存在迴路，在訪問某個頂點之後，可能沿著某條路徑又回到該頂點。
深度優先搜索
圖的深度優先搜索策略是，訪問某個頂點v，接著尋找v的另一個未被訪問的鄰接頂點w訪問，如此反復執行，走過一條較長路徑到達最遠頂點；若頂點v沒有未被訪問的其他鄰接頂點，則回到前一個被訪問頂點，再尋找其他訪問路徑。
圖的深度優先搜索遍歷演算法P188
聯通的無迴路的無向圖，簡稱樹。樹中的懸掛點又成為樹葉，其他頂點稱為分支點。各連通分量均為樹的圖稱為森林，樹是森林。
由於樹中無迴路，因此樹中必定無自身環也無重邊（否則他有迴路）若去掉樹中的任意一條邊，則變成森林，成為非聯通圖；若給樹加上一條邊，形成圖中的一條迴路，則不是樹。P191
生成樹和生成森林：
一個連通無向圖的生成樹是該圖的一個極小聯通生成子圖，它包含原圖中所有頂點（n個）以及足以構成一棵樹的n-1條邊。
一個非聯通的無向圖，其各連通圖分量的生成圖組成該圖的生成森林。
圖的生成圖或生成森林不是唯一的，從不同頂點開始、採用不同遍歷可以得到不同的生成樹或森林。
在生成樹中，任何樹中，任何兩個頂點之間只有唯一的一條路徑。
第八章
折半查找演算法描述 P206,P207
二叉排序樹及其查找：
二叉排序樹或者是一棵空樹；或者是具有下列性質的二叉樹：
@每個結點都有一個作為查找依據的關鍵字，所有結點的關鍵字互不相同。
@若一個結點的左子樹不空，則左子樹上所有結點的關鍵字均小於這個節點的關鍵字；
@每個結點的左右子樹也分別為二叉排序樹。
在一棵二叉排序樹中，查找值為value的結點，演算法描述如下：
@從根結點開始，設p指向根結點
@將value與p結點的關鍵字進行比較，若兩者相等，則查找成功；若value值較小，則在p的左子樹中繼續查找；若value值較大，則在p的右子樹中繼續查找。
@重復執行上一步，直到查找成功或p為空，若p為空，則查找不成功。
習題 8-6
第九章
直接插入排序演算法描述：p228
冒泡排序演算法的描述：p232
快速排序演算法描述p233
直接選擇排序演算法描述p236
直接選擇排序演算法實現如下：
Public static void selectSort(int[]table){
for(int i=0;i<table.length-1;i++){
int min=I;
for(int j=i+1;j<table.length;j++){
if(table[j]<table[min])
min=j;
if(min!=i){
int temp=table[i];
table[i]==table[min];
table[min]=temp;
}
}
}
}
堆排序是完全二叉樹的應用，是充分利用完全二叉樹特性的一種選擇排序。
堆定義：設n個元素的數據序列，當且僅當滿足下列關系
k1<=k2i+1且ki<=k2i+2 i=0,1,2,3,….,[n/2-1]
或ki>==k2i+1且ki>=2i+2i=0,1,2,3,…..[n/2-1]時，序列稱為最小堆或最大堆。將最小（大）堆看成是一顆完全二叉樹的層次遍歷序列，則任意一個結點的關鍵字都小於等於（大於等於）它的孩子節點的關鍵字值，由此可知，根結點值最小（大）。根據二叉樹的性質5，完全二叉樹中的第i（0<=i<n）個結點，如果有孩子，則左孩子為第2i+1個結點，右孩子為第2i+2個結點。
希望對你會有所幫助。