數(shù)據(jù)結(jié)構(gòu)線性表ppt課件(參考版)
2025-05-02 02:43本頁面
【正文】 } 。 } else putchar(c)。 if ( c!=e ) { printf(Error\n)。q, amp。c)。 } while ( ! StackEmpty(s) ) /* 判斷 */ { Pop ( amp。 EnQueue (amp。 ) /* 輸入 */ { Push ( amp。 while ( ( c=getchar() ) !=39。 InitQueue (amp。 InitStack (amp。 } Status DeQueue ( SqQueue * q, char * e ) { *e = qbase[qfront++]。 } Status QueueEmpty ( SqQueue q ) { return == 。 qfront = qrear = 0。 /* 隊(duì)列 */ SqQueue q。 int front, rear。 } Status StackEmpty ( SqStack s ) { return (==)。 } Status Push ( SqStack * s, char e ) { * stop ++ =e。 sstacksize = MAX。 第 59 頁 棧和隊(duì)列 Status InitStack ( SqStack * s ) { sbase = (char *)malloc( MAX*sizeof(char) )。 } SqStack。 char * top。 第 58 頁 棧和隊(duì)列 include define MAX 100 define OK 1 define ERROR 0 typedef int Status。 ? 算法設(shè)計(jì) 程序從鍵盤接受一個(gè)字符序列存入字符串 str中，字符串長度 ≤ 80，輸入字符序列以回車符為結(jié)束標(biāo)記，字符串 str中不包括回車換行符。當(dāng)從隊(duì)列中刪除一個(gè)元素，再加入兩個(gè)元素后， rear和 front 的值分別為多少？ A） 1和 5 B） 2和 4 C） 4和 2 D） 5和 1 答案： B 第 55 頁 棧和隊(duì)列 寫出循環(huán)隊(duì)列隊(duì)空、隊(duì)滿的判斷方法及條件（一種）。 在操作系統(tǒng)課程中講到 隊(duì)列 第 53 頁 小 結(jié) 隊(duì)列是限定僅能在表尾一端進(jìn)行插入，表頭一端進(jìn)行刪除的線性表； 隊(duì)列中的元素具有先進(jìn)先出的特點(diǎn)； 隊(duì)頭、隊(duì)尾元素的位置分別由稱為隊(duì)頭指針和隊(duì)尾指針的變量指示； 入隊(duì)操作要修改隊(duì)尾指針，出隊(duì)操作要修改隊(duì)頭指針。 //隊(duì)尾指針，指向隊(duì)尾結(jié)點(diǎn)}LinkQueue。 隊(duì)列 typedef struct // 鏈隊(duì)列的表頭結(jié)點(diǎn)的的類型定義 { QueuePtr front。 struct QNode * next。 //修改隊(duì)頭指針 return OK。 //隊(duì)空 e = [] 。Q, ElemType amp。Q, QElemType amp。 //修改隊(duì)尾指針 return OK。 //隊(duì)滿 [] = e 。Q, ElemType e ) 功能： 將元素 e 插入隊(duì)尾 5 4 0 3 1 2 J1 J3 J2 e 5 4 0 3 1 2 J1 J3 J2 元素 e入隊(duì)前 元素 e入隊(duì)后 隊(duì)列 第 46 頁 入隊(duì) 操作 算法： Status EnQueue_Sq ( SqQueue amp。 Return OK。 if ( ! ) exit (OVERFLOW)。Q ) 參數(shù)： Q是存放隊(duì)列的結(jié)構(gòu)變量 功能：建一個(gè)空隊(duì)列 Q 算法： Status InitQueue_Sq ( SqQueue amp。 front=(front+1)%M。 rear=(rear+1)%M。 rear rear front rear 1 2 3 4 5 0 J1,J2,J3出隊(duì) J1 J2 J3 front front front 又有 J7入隊(duì) ,該怎么辦？ 第 41 頁 隊(duì)列 ? 存在問題 設(shè)數(shù)組大小為 M， 則： – 當(dāng) front=0， rear= M 時(shí)，再入隊(duì)發(fā)生溢出 — — 真溢出 – 當(dāng) front?0， rear= M 時(shí)，再入隊(duì)發(fā)生溢出 — — 假溢出 ? 解決方案 – 隊(duì)首固定，每次出隊(duì)后將剩余元素向下移動(dòng) —— 浪費(fèi)時(shí)間 – 循環(huán)隊(duì)列 ?基本思想：把隊(duì)列設(shè)想成環(huán)形，讓 [M1] 接在 [0] 之后，若 rear+1==M， 則令 rear=0。初值 front=rear=0 隊(duì)空條件： front==rear 入隊(duì)列： [ rear++ ] = e。 隊(duì)頭 ,隊(duì)尾指針 是用整型實(shí)現(xiàn)的 隊(duì)列 第 40 頁 隊(duì)列 ? 隊(duì)列基本操作 1 2 3 4 5 0 隊(duì)空 front=0 rear=0 1 2 3 4 5 0 front J1,J2,J3入隊(duì) J1 J2 J3 rear J4,J5,J6入隊(duì) rear 1 2 3 4 5 0 J4 J5 J6 front 設(shè)兩個(gè)指針： front,rear。 //隊(duì)頭指針，指向隊(duì)頭元素 int rear。 隊(duì)列 第 38 頁 循環(huán)隊(duì)列 —— 隊(duì)列的順序存儲(chǔ)和實(shí)現(xiàn) 一、隊(duì)列的順序存貯結(jié)構(gòu) define MAXSIZE 100 //最大隊(duì)列長度 typedef struct { ElemType * base。Q, e ) 功能：將元素 e插入 Q的隊(duì)尾。e) 功能：取隊(duì)頭元素，并用 e返回。e) 功能：刪除 Q的隊(duì)頭元素。 4）出隊(duì)操作 DeQueue(amp。 3） 置空操作 ClearQueue(amp。 2） 銷毀操作 DestroyQueue(amp。 隊(duì)列 第 35 頁 a1 a2 a3 an 隊(duì)頭 隊(duì)尾 出隊(duì)列 隊(duì)列的示意圖 隊(duì)列的特點(diǎn)
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1