【文章內(nèi)容簡介】 next。pnextprior = pprior。6. 順序表與單鏈表的比較表 順序表和單鏈表的比較順序表單鏈表以地址相鄰表示關(guān)系用指針表示關(guān)系隨機(jī)訪問，取元素O(1)順序訪問，取元素O(n)插入、刪除需要移動元素O(n)插入、刪除不用移動元素O(n)(用于查找位置)總結(jié)：需要反復(fù)插入、刪除，宜采用鏈表；反復(fù)提取，很少插入、刪除，宜采用順序表。二、 習(xí)題 將順序表中的元素反轉(zhuǎn)順序。 在非遞減有序的順序表中插入元素x，并保持有序。 刪除順序表中所有等于x的元素。 編寫算法實(shí)現(xiàn)順序表元素唯一化(即使順序表中重復(fù)的元素只保留一個(gè))，給出算法的時(shí)間復(fù)雜度。 非遞減有序的順序表元素唯一化()，要求算法的時(shí)間復(fù)雜度為O(n)。 將單鏈表就地逆置，即不另外開辟結(jié)點(diǎn)空間，而將鏈表元素翻轉(zhuǎn)順序。 采用插入法將單鏈表中的元素排序。 采用選擇法將單鏈表中的元素排序。 將兩個(gè)非遞減有序的單鏈表歸并成一個(gè)，仍并保持非遞減有序。第3章 棧和隊(duì)列一、 基礎(chǔ)知識和算法1. 棧棧，棧頂，棧底，空棧，后進(jìn)先出(LIFO)，入棧(Push)，出棧(Pop)。順序棧：棧的順序存儲結(jié)構(gòu)；鏈棧：棧的鏈?zhǔn)酱鎯Y(jié)構(gòu)。2. 鏈棧(1) 存儲結(jié)構(gòu)a1/\anS...an1用不帶頭結(jié)點(diǎn)的單鏈表實(shí)現(xiàn)。(2) 類型定義同單鏈表。(3) 基本形態(tài)a1/\anS...an1S/\1176。. ?？諚l件: S == NULL2176。. 棧非空3176。. 棧滿（一般不出現(xiàn)）(4) 基本算法1176。. 入棧 Push (amp。s, x)bool Push ( LinkList amp。s, DataType x ){ // 新建結(jié)點(diǎn) p = (LinkList) malloc (sizeof(LNode))。 if ( !p ) return false。 // 失敗 pdata = x。 // 插入棧頂 pnext = s。 s = p。 return true。}2176。. 出棧 Pop (amp。s, amp。x)前提：棧非空。bool Pop ( LinkList amp。s, DataType amp。x ){ if ( s==NULL ) return false。 // ?？? // 刪除棧頂元素 p = s。 s = snext。 x = pdata。 free ( p )。 return true。}3176。. 棧頂元素前提：棧非空。bool Top ( LinkList amp。s, DataType amp。x ){ if ( s==NULL ) return false。 // ?？? x = sdata。 return true。}3. 順序棧(1) 存儲結(jié)構(gòu)類似于順序表，插入和刪除操作固定于表尾。(2) 類型定義簡單說，“數(shù)組 + 長度” 不準(zhǔn)確的說法，只為便于理解和記憶，不要在正式場合引用。const int MAXSIZE = 棧的最大容量；typedef struct { DataType elem[MAXSIZE]。 int top。} SqStack。(3) 基本形態(tài)1176。. 棧空條件 == 0。2176。. 棧滿條件 == MAXSIZE3176。. 棧不空、不滿(4) 基本算法1176。. 入棧 Push (amp。s, x)前提：棧不滿bool Push ( SqStackamp。 s, DataType x ){ if ( == MAXSIZE ) return false。 // 棧滿 [top] = x。 // [top++] = x。 top++。 // 代替這兩行 return true。}2176。. 出棧 Pop (amp。s, amp。x)前提：棧非空bool Pop ( SqStack amp。s, DataType amp。x ){ if ( ==0 ) return false。 top。 // 可用x=[top]。 x = [top]。 // 代替這兩行 return true。}3176。. 棧頂元素前提：棧非空[top1] 即是。4. 隊(duì)列隊(duì)列，隊(duì)頭，隊(duì)尾，空隊(duì)列，先進(jìn)先出(FIFO)。鏈隊(duì)列：隊(duì)列的鏈?zhǔn)酱鎯Y(jié)構(gòu)。循環(huán)隊(duì)列：隊(duì)列的順序存儲結(jié)構(gòu)之一。5. 鏈隊(duì)列(1) 存儲結(jié)構(gòu)/\a1a2an/\...簡而言之，“單鏈表 + 尾指針” 不準(zhǔn)確的說法，只為便于理解和記憶，不要在正式場合引用。(2) 類型定義課本P61。typedef struct { LinkList front。 LinkList rear。} LinkQueue。(3) 基本形態(tài)隊(duì)列空：==。非空隊(duì)列。(4) 基本算法1176。. 入隊(duì)列課本P62。插入隊(duì)尾。2176。. 出隊(duì)列課本P62。刪除隊(duì)頭元素，特別注意：如果隊(duì)列中只有一個(gè)元素，則隊(duì)頭也同時(shí)是隊(duì)尾，刪除隊(duì)頭元素后也需要修改隊(duì)尾指針。6. 循環(huán)隊(duì)列(1) 存儲結(jié)構(gòu)簡單說，“數(shù)組 + 頭、尾位置” 不準(zhǔn)確的說法，只為便于理解和記憶，不要在正式場合引用。(2) 類型定義const int MAXSIZE = 隊(duì)列最大容量。typedef struct { DataType elem[MAXSIZE]。 int front, rear。 // 隊(duì)頭、隊(duì)尾位置} SqQueue。(3) 基本形態(tài)通常少用一個(gè)元素區(qū)分隊(duì)列空和隊(duì)列滿，也可以加一標(biāo)志。約定front指向隊(duì)頭元素的位置，rear指向隊(duì)尾的下一個(gè)位置，隊(duì)列內(nèi)容為 [front, rear)。1176。. 隊(duì)列空條件： == 。不能出隊(duì)列。2176。. 隊(duì)列滿條件：(+1)%MAXSIZE == （少用一個(gè)元素時(shí)）。不能入隊(duì)列。3176。. 隊(duì)列不空也不滿frontreara1rearfronta3a2a4a1rearfronta3a2frontreartag:0frontreara3a4a1a2frontreartag:1a3a4a5a1a24176。. 加一標(biāo)志區(qū)分隊(duì)列空和隊(duì)列滿的情況可以用滿所有空間。==，再用標(biāo)志區(qū)分。隊(duì)列空：== and ==0；隊(duì)列滿：== and ==1。(4) 基本算法1176。. 入隊(duì)列前提：隊(duì)列不滿。bool EnQueue ( SqQueue amp。Q, DataType x ){ if ( (+1)%MAXSIZE== ) return false。 // 隊(duì)列滿 // 入隊(duì)列 [] = x。 = (+1)%MAXSIZE。 return true。}2176。. 出隊(duì)列前提：隊(duì)列非空。bool DeQueue ( SqQueue amp。Q, DataType amp。x ){ if ( == ) return false。 // 隊(duì)列空 // 出隊(duì)列 x = []。 = (+1)%MAXSIZE。 return true。}3176。. 隊(duì)列中元素個(gè)數(shù)結(jié)論：(+MAXSIZE)%MAXSIZE。注：，需要加上MAXSIZE。int QueueLength ( SqQueue Q ){ return (+MAXSIZE)%MAXSIZE。}4176。. 用標(biāo)志區(qū)分隊(duì)列空和滿用標(biāo)志區(qū)分隊(duì)列空和滿時(shí)，隊(duì)列初始化、入隊(duì)列、出隊(duì)列和隊(duì)列長度的算法如下：void InitQueue ( SqQueue amp。Q ) { = = 0。 = 0。}bool EnQueue ( SqQueue amp。Q, DataType x ) { if ( == and ==1 ) return false。 [ ] = x。 = (+1)%MAXSIZE。 if ( ==0 ) = 1。 // 隊(duì)列非空 return true。}bool DeQueue ( SqQueue amp。Q, DataType amp。x ) { if ( == and ==0 ) return false。 x = [ ]。 = (+1)%MAXSIZE。 if ( == ) = 0。 // 隊(duì)列空 return true。}int QueueLength ( SqQueue Q ){ if ( == and ==1 ) return MAXSIZE。 // 隊(duì)列滿 else return (+MAXSIZE)%MAXSIZE。 // 隊(duì)列不滿(包含隊(duì)列空的情況)}7. 棧和隊(duì)列比較都是線形結(jié)構(gòu)，棧的操作LIFO（后進(jìn)先出），隊(duì)列操作FIFO（先進(jìn)先出）。8. 簡化的棧和隊(duì)列結(jié)構(gòu)在算法中使用棧和隊(duì)列時(shí)可以采用簡化的形式。表 簡化的棧和隊(duì)列結(jié)構(gòu)簡化棧簡化隊(duì)列結(jié)構(gòu)“s[] + top”結(jié)構(gòu)“q[] + front + rear”初始化top = 0。初始化front=rear=0。入棧s[top++] = x。入隊(duì)列q[rear] = x。rear = (rear+1)%MAXSIZE。出棧x = s[top]。出隊(duì)列x = q[front]。front = (front+1)%MAXSIZE。棧頂s[top1]隊(duì)列頭q[front]?？誸op == 0隊(duì)列空front == rear說明：只要棧(隊(duì)列)的容量足夠大，算法中可以省去檢查棧(隊(duì)列)滿的情況。9. 棧和隊(duì)列的應(yīng)用1176。. 表達(dá)式求值參見課本P53。2176。. 括號匹配例：檢查表達(dá)式中的括號是否正確匹配。如{ ( ) [ ] }正確，( [ ) ] }則錯誤。分析：每個(gè)左括號都“期待”對應(yīng)的右括號，匹配成功則可以消去。思路：遇到左括號則入棧，遇到右括號則與棧頂括號相比較，如果匹配則消去，否則匹配失敗。當(dāng)然，如果棧中沒有括號可以匹配，或者最后棧中還有未匹配的左括號，也都是匹配錯誤。// 檢查輸入的表達(dá)式中括號是否匹配bool MatchBrackets (){ const int MAXSIZE = 1024。 // 棧的最大容量 char s [MAXSIZE]。 // 簡化的棧結(jié)構(gòu) int top。 // 棧頂 // 棧初始化 top = 0。 // 檢查括號是否匹配 ch = getchar()。 while ( ch!=EOF ) { switch ( ch ) { case ‘(‘, ‘[’, ‘{’: s [top++] = ch。 // 所有左括號入棧 break。 case ‘)’: if ( top==0 or s [top]!=’(’ ) return false。 // ?？栈蛴依ㄌ柵c棧頂左括號失配 case ‘]’: if ( top==0 or s [top]!=’[’ ) return false。 case ‘}’: if ( top==0 or s [top]!=’{’ ) return false。 } ch = getchar()。 // 取下一個(gè)字符 } if ( top==0 ) return true。 // 正好匹配 else return false。 // 棧中尚有未匹配的左括號}3176。. 遞歸程序的非遞歸化將遞歸程序轉(zhuǎn)化為非遞歸程序時(shí)常使用棧來實(shí)現(xiàn)。4176。. 作業(yè)排隊(duì)如操作系統(tǒng)中的作業(yè)調(diào)度中的作業(yè)排隊(duì)，打印機(jī)的打印作業(yè)也排成隊(duì)列。5176。. 按層次遍歷二叉樹void LevelOrder ( BinTree bt, VisitFunc visit ){ const int MAXSIZE = 1024。 // 隊(duì)列容量(足夠大即可) BinTree q [MAXSIZE]。 // 簡化的隊(duì)列結(jié)構(gòu) int front, rear。 // 隊(duì)頭、隊(duì)尾 if ( ! bt ) return 。 // 初始化隊(duì)列，根結(jié)點(diǎn)入隊(duì)列 front = rear = 0。 q [rear] = bt。 rear = (rear+1)%MAXSIZE。 // 隊(duì)列不空，則取出隊(duì)頭訪問并將其左右孩子入隊(duì)列 while ( front!=rear ) { p = q [front]。 front = (front+1)%MAXSIZE。 if ( p ) { visit ( pd