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

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

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

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

--------------------------------------------------------------------------------
(答案及點(diǎn)評(píng)) 2.6 下述算法的功能是什么?

LinkList Demo(LinkList L){ // L 是無(wú)頭結(jié)點(diǎn)單鏈表
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
第三章：棧和隊(duì)列(包括習(xí)題與答案及要點(diǎn))

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

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

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

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

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

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