數(shù)據(jù)結(jié)構(gòu)線性表ppt課件-資料下載頁
2025-04-29 02:43本頁面
【正文】 return OK。 } //EnQueue_Sq 隊列 第 49 頁 鏈隊列 —— 隊列的鏈?zhǔn)酱鎯Y(jié)構(gòu)和實現(xiàn) 一、鏈隊列 ∧ 空鏈隊列 J1 ∧ J2 ∧ 鏈隊列圖示 隊列 第 50 頁 二、 鏈隊列的類型定義 typedef struct QNode //鏈隊列結(jié)點的類型定義 { ElemType data。 struct QNode * next。 }QNode, * QueuePtr。 隊列 typedef struct // 鏈隊列的表頭結(jié)點的的類型定義 { QueuePtr front。 //隊頭指針，指向鏈表的頭結(jié)點 QueuePtr rear。 //隊尾指針，指向隊尾結(jié)點}LinkQueue。 頭結(jié)點 ^ …... front 隊頭 隊尾 rear front指向頭結(jié)點， rear指向隊尾 第 51 頁 隊列 ? 鏈?zhǔn)疥犃械幕静僮? front rear x入 隊 ^ x front rear y入 隊 x ^ y front rear x出 隊 x ^ y front rear 空隊 ^ front rear y出 隊 ^ 判斷隊空的條件：front==rear 第 52 頁 三、隊列的應(yīng)用 1）解決計算機主機與外設(shè)不匹配的問題； 2）解決由于多用戶引起的資源競爭問題； 3）離散事件的模擬 —— 模擬實際應(yīng)用中的各種排隊現(xiàn)象； 4）用于處理程序中具有先進先出特征的過程。 在操作系統(tǒng)課程中講到 隊列 第 53 頁 小 結(jié) 隊列是限定僅能在表尾一端進行插入，表頭一端進行刪除的線性表； 隊列中的元素具有先進先出的特點； 隊頭、隊尾元素的位置分別由稱為隊頭指針和隊尾指針的變量指示； 入隊操作要修改隊尾指針，出隊操作要修改隊頭指針。 隊列 第 54 頁 棧和隊列練習(xí) 已知一堆棧的進棧序列為： 1234，則下列哪個序列為不可能的出棧序列： A） 1234 B） 4321 C） 2143 D） 4123 答案： D 若用一個大小為 6 的數(shù)組來實現(xiàn)循環(huán)隊列，且當(dāng)前 rear 和 front 的值分別為 0 和 3。當(dāng)從隊列中刪除一個元素，再加入兩個元素后， rear和 front 的值分別為多少？ A） 1和 5 B） 2和 4 C） 4和 2 D） 5和 1 答案： B 第 55 頁 棧和隊列 寫出循環(huán)隊列隊空、隊滿的判斷方法及條件（一種）。 答案： 方法：少用一個存儲單元 判滿條件 (+1)%Q. queuesize = = 判空條件 = = 第 57 頁 棧和隊列 ? 問題：編 程判斷一個字符序列是否是回文（回文是指一個字符序列以中間字符為基準(zhǔn)兩邊字符完全相同）。 ? 算法設(shè)計 程序從鍵盤接受一個字符序列存入字符串 str中，字符串長度 ≤ 80，輸入字符序列以回車符為結(jié)束標(biāo)記，字符串 str中不包括回車換行符。 將字符串中字符逐個分別存入隊列和棧，然后逐個出隊和退棧，比較出隊的元素和退棧的元素是否相等，若全部相等則該字符序列是回文，否則就不是回文。 第 58 頁 棧和隊列 include define MAX 100 define OK 1 define ERROR 0 typedef int Status。 /* 返回值狀態(tài) */ typedef struct { char * base。 char * top。 int stacksize。 } SqStack。 /* 棧 */ SqStack s。 第 59 頁 棧和隊列 Status InitStack ( SqStack * s ) { sbase = (char *)malloc( MAX*sizeof(char) )。 stop = sbase。 sstacksize = MAX。 return OK。 } Status Push ( SqStack * s, char e ) { * stop ++ =e。 } Status Pop ( SqStack * s, char * e ) { *e = * stop。 } Status StackEmpty ( SqStack s ) { return (==)。 } 第 60 頁 棧和隊列 typedef struct { char *base。 int front, rear。 } SqQueue。 /* 隊列 */ SqQueue q。 第 61 頁 棧和隊列 Status InitQueue ( SqQueue * q ) { qbase = (char *)malloc( MAX*sizeof(char) )。 qfront = qrear = 0。 return OK。 } Status QueueEmpty ( SqQueue q ) { return == 。 } Status EnQueue ( SqQueue * q, char e ) { qbase[qrear++]=e。 } Status DeQueue ( SqQueue * q, char * e ) { *e = qbase[qfront++]。 } 第 62 頁 棧和隊列 main( ) { char c, e。 InitStack (amp。s)。 InitQueue (amp。q)。 while ( ( c=getchar() ) !=39。\n39。 ) /* 輸入 */ { Push ( amp。s, c)。 EnQueue (amp。q, c)。 } while ( ! StackEmpty(s) ) /* 判斷 */ { Pop ( amp。s, amp。c)。 DeQueue (amp。q, amp。e)。 if ( c!=e ) { printf(Error\n)。 exit ( )。 } else putchar(c)。 } printf (\nOK!)。
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1