數(shù)據(jù)結(jié)構(gòu)線性表ppt課件(存儲(chǔ)版)
【正文】 隊(duì)列的表頭結(jié)點(diǎn)的的類型定義 { QueuePtr front。 ? 算法設(shè)計(jì) 程序從鍵盤接受一個(gè)字符序列存入字符串 str中，字符串長(zhǎng)度 ≤ 80，輸入字符序列以回車符為結(jié)束標(biāo)記，字符串 str中不包括回車換行符。 第 59 頁(yè) 棧和隊(duì)列 Status InitStack ( SqStack * s ) { sbase = (char *)malloc( MAX*sizeof(char) )。 int front, rear。 } Status DeQueue ( SqQueue * q, char * e ) { *e = qbase[qfront++]。 ) /* 輸入 */ { Push ( amp。q, amp。 } 。c)。 while ( ( c=getchar() ) !=39。 } Status QueueEmpty ( SqQueue q ) { return == 。 } Status StackEmpty ( SqStack s ) { return (==)。 } SqStack。當(dāng)從隊(duì)列中刪除一個(gè)元素，再加入兩個(gè)元素后， rear和 front 的值分別為多少？ A） 1和 5 B） 2和 4 C） 4和 2 D） 5和 1 答案： B 第 55 頁(yè) 棧和隊(duì)列 寫出循環(huán)隊(duì)列隊(duì)空、隊(duì)滿的判斷方法及條件（一種）。 struct QNode * next。Q, QElemType amp。 Return OK。 rear=(rear+1)%M。 //隊(duì)頭指針，指向隊(duì)頭元素 int rear。e) 功能：刪除 Q的隊(duì)頭元素。 隊(duì)列 第 35 頁(yè) a1 a2 a3 an 隊(duì)頭 隊(duì)尾 出隊(duì)列 隊(duì)列的示意圖 隊(duì)列的特點(diǎn) 先進(jìn)先出 第一個(gè)入隊(duì)的元素在隊(duì)頭 最后一個(gè)入隊(duì)的元素在隊(duì)尾 第一個(gè)出隊(duì)的元素為隊(duì)頭元素 最后一個(gè)出隊(duì)的元素為隊(duì)尾元素 出隊(duì)列 隊(duì)列 第 36 頁(yè) 二、隊(duì)列的基本操作 1）初始化操作 InitQueue(amp。 //進(jìn)行二元運(yùn)算 a ? b break。 break。 InitStack(OPTR)。 棧的鏈?zhǔn)酱鎯?chǔ)和實(shí)現(xiàn) 棧 Data next S an1 a1 an ∧ 第 24 頁(yè) 小 結(jié) 棧是限定僅能在表尾一端進(jìn)行插入、刪除操作的線性表 棧的元素具有后進(jìn)先出的特點(diǎn) 棧頂元素的位置由一個(gè)稱為棧頂指針的變量指示，進(jìn)棧和出棧操作都要修改棧頂指針 棧 第 25 頁(yè) 1）問(wèn)題的提出 從鍵盤一次性輸入一串算術(shù)表達(dá)式，給出計(jì)算結(jié)果。S, ElemType amp。 //存儲(chǔ)分配失敗 = + 。e ) { if ( == ) return ERROR。 return OK。 = STACK_INIT_SIZE。 //當(dāng)前分配的?？臻g大小 }SqStack。S, e) 功能：元素 e進(jìn)棧。S) 功能：構(gòu)造一個(gè)空棧 S。 第 3 頁(yè) 棧 出棧 進(jìn)棧 棧的特點(diǎn) 后進(jìn)先出 第一個(gè)進(jìn)棧的元素在棧底 最后一個(gè)進(jìn)棧的元素在棧頂 第一個(gè)出棧的元素為棧頂元素 最后一個(gè)出棧的元素為棧底元素 棧的示意圖 棧頂 棧底 an a2 a1 第 4 頁(yè) 棧 二、棧的基本操作 1）初始化操作 InitStack(amp。 第 5 頁(yè) 棧 二、棧的基本操作 5）進(jìn)棧操作 Push(amp。 //棧頂指針 int stacksize。 //分配失敗 = 。 = 0。e ) 功能： 取棧頂元素，并用 e返回 棧 第 18 頁(yè) Status GetTop ( SqStack S, ElemType amp。 if ( ! S. base ) exit(OVERFLOW)。 棧 e an 出棧操作后 100 99 n n1 n2 1 0 an1 a2 a1 第 22 頁(yè) Status Pop ( SqStack amp。 棧頂 棧底 在前面學(xué)習(xí)了線性鏈表的插入、刪除操作算法，不難寫出鏈?zhǔn)綏３跏蓟?、進(jìn)棧、出棧等操作的算法 。設(shè) OPTR和 OPND分別為運(yùn)算符棧和運(yùn)算數(shù)棧， OP為運(yùn)算符、界限符集合。 c=getchar( )。 Push ( OPND, Operate(a, theta, b) )。 稱插入操作為入隊(duì)，刪除操作為出隊(duì)。Q,amp。 //初始化時(shí)分配 存儲(chǔ)空間的基址 int front。 rear 1 2 3 4 5 0 J4,J5,J6入隊(duì) J4 J5 J6 front 0 M1 1 front rear 第 42 頁(yè) 隊(duì)列 實(shí)現(xiàn)：利用“?！边\(yùn)算 入隊(duì)： [rear]=e。 //存儲(chǔ)分配失敗 = = 0。 } //EnQueue_Sq 隊(duì)列 第 47 頁(yè) 3)出隊(duì) 操作 DeQueue_Sq (SqQueue amp。 } //EnQueue_Sq 隊(duì)列 第 49 頁(yè) 鏈隊(duì)列 —— 隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)和實(shí)現(xiàn) 一、鏈隊(duì)列 ∧ 空鏈隊(duì)列 J1 ∧ J2 ∧ 鏈隊(duì)列圖示 隊(duì)列 第 50 頁(yè) 二、 鏈隊(duì)列的類型定義 typedef struct QNode //鏈隊(duì)列結(jié)點(diǎn)的類型定義 { ElemType data。 隊(duì)列 第 54 頁(yè) 棧和隊(duì)列練習(xí) 已知一堆棧的進(jìn)棧序列為： 1234，則下列哪個(gè)序列為不可能的出棧序列： A） 1234 B） 4321 C） 2143 D） 4123 答案： D 若用一個(gè)大小為 6 的數(shù)組來(lái)實(shí)現(xiàn)循環(huán)隊(duì)列，且當(dāng)前 rear 和 front 的值分別為 0 和 3。 int stacksize。 } Status Pop ( SqStack * s, char * e ) { *e = *
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1