2006年軟考程序員數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)筆記

若用頭指針來表示該鏈表，則查找終端結(jié)點的時間為O(n)。

--------------------------------------------------------------------------------
(答案及點評) 2.5 在單鏈表、雙鏈表和單循環(huán)鏈表中，若僅知道指針p指向某結(jié)點，不知道頭指針，能否將結(jié)點*p從相應(yīng)的鏈表中刪去?若可以，其時間復(fù)雜度各為多少?

2.5 答：
我們分別討論三種鏈表的情況。
1. 單鏈表。當(dāng)我們知道指針p指向某結(jié)點時，能夠根據(jù)該指針找到其直接后繼，但是由于不知道其頭指針，所以無法訪問到p指針指向的結(jié)點的直接前趨。因此無法刪去該結(jié)點。
2. 雙鏈表。由于這樣的鏈表提供雙向鏈接，因此根據(jù)已知結(jié)點可以查找到其直接前趨和直接后繼，從而可以刪除該結(jié)點。其時間復(fù)雜度為O(1)。
3. 單循環(huán)鏈表。根據(jù)已知結(jié)點位置，我們可以直接得到其后相鄰的結(jié)點位置(直接后繼)，又因為是循環(huán)鏈表，所以我們可以通過查找，得到p結(jié)點的直接前趨。因此可以刪去p所指結(jié)點。其時間復(fù)雜度應(yīng)為O(n)。

--------------------------------------------------------------------------------
(答案及點評) 2.6 下述算法的功能是什么?

LinkList Demo(LinkList L){ // L 是無頭結(jié)點單鏈表
ListNode *Q,*P;
if(L&&L->next){
Q=L;L=L->next;P=L;
while (P->next) P=P->next;
P->next=Q; Q->next=NULL;
}
return L;
}// Demo
第三章：棧和隊列(包括習(xí)題與答案及要點)

轉(zhuǎn)摘www.Ezikao.com

--------------------------------------------------------------------------------
　　 
本章介紹的是棧和隊列的邏輯結(jié)構(gòu)定義及在兩種存儲結(jié)構(gòu)(順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯�結(jié)構(gòu))上如何實現(xiàn)棧和隊列的基本運算。本章的重點是掌握棧和隊列在兩種存儲結(jié)構(gòu)上實現(xiàn)的基本運算，難點是循環(huán)隊列中對邊界條件的處理。

--------------------------------------------------------------------------------
1.棧的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)及其相關(guān)算法(綜合應(yīng)用):
棧的邏輯結(jié)構(gòu)和我們先前學(xué)過的線性表相同，如果它是非空的，則有且只有一個開始結(jié)點，有且只能有一個終端結(jié)點，其它的結(jié)點前后所相鄰的也只能是一個結(jié)點(直接前趨和直接后繼),但是棧的運算規(guī)則與線性表相比有更多的限制，棧(Stack)是僅限制在表的一端進行插入和刪除運算的線性表，通常稱插入、刪除這一端為棧頂，另一端稱為棧底。表中無元素時為空棧。棧的修改是按后進先出的原則進行的，我們又稱棧為LIFO表(Last In First Out).
棧的基本運算有六種：
構(gòu)造空棧：InitStack(S)、
判棧空: StackEmpty(S)、
判棧滿： StackFull(S)、
進棧： Push(S,x)、可形象地理解為壓入，這時棧中會多一個元素
退棧： Pop(S) 、 可形象地理解為彈出，彈出后棧中就無此元素了。
取棧頂元素：StackTop(S),不同與彈出，只是使用棧頂元素的值，該元素仍在棧頂不會改變。

--------------------------------------------------------------------------------
由于棧也是線性表，因此線性表的存儲結(jié)構(gòu)對棧也適用，通常棧有順序棧和鏈棧兩種存儲結(jié)構(gòu)，這兩種存儲結(jié)構(gòu)的不同，則使得實現(xiàn)棧的基本運算的算法也有所不同。

--------------------------------------------------------------------------------
我們要了解的是，在順序棧中有"上溢"和"下溢"的概念。順序棧好比一個盒子，我們在里頭放了一疊書，當(dāng)我們要用書的話只能從第一本開始拿(你會把盒子翻過來嗎?真聰明^^)，那么當(dāng)我們把書本放到這個棧中超過盒子的頂部時就放不下了(疊上去的不算，哼哼)，這時就是"上溢","上溢"也就是棧頂指針指出棧的外面，顯然是出錯了。反之，當(dāng)棧中已沒有書時，我們再去拿，看看沒書，把盒子拎起來看看盒底，還是沒有，這就是"下溢"。"下溢"本身可以表示棧為空棧,因此可以用它來作為控制轉(zhuǎn)移的條件。
鏈棧則沒有上溢的限制，它就象是一條一頭固定的鏈子，可以在活動的一頭自由地增加鏈環(huán)(結(jié)點)而不會溢出，鏈棧不需要在頭部附加頭結(jié)點，因為棧都是在頭部進行操作的，如果加了頭結(jié)點，等于要在頭結(jié)點之后的結(jié)點進行操作，反而使算法更復(fù)雜，所以只要有鏈表的頭指針就可以了。
以上兩種存儲結(jié)構(gòu)的棧的基本操作算法是不同的，我們主要要學(xué)會進棧和退棧的基本算法以解決簡單的應(yīng)用問題。

--------------------------------------------------------------------------------
2.隊列的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)及其相關(guān)算法(綜合應(yīng)用)。
隊列(Queue,念Q音)也是一種運算受限的線性表，它的運算限制與棧不同，是兩頭都有限制，插入只能在表的一端進行(只進不出)，而刪除只能在表的另一端進行(只出不進)，允許刪除的一端稱為隊尾(rear)，允許插入的一端稱為隊頭 (Front) ,隊列的操作原則是先進先出的，所以隊列又稱作FIFO表(First In First Out)
隊列的基本運算也有六種： 轉(zhuǎn)轉(zhuǎn)