[理學]數(shù)據(jù)結構3第三章：棧和隊列(編輯修改稿)
2024-11-12 21:14 本頁面
【文章內容簡介】 printf(%c,e+55)。 } } 棧的應用舉例 Void lineEdit() {//行編輯算法描述 ,利用字符棧 s,從終端接收一行并傳送至調用過程的數(shù)據(jù)區(qū) Setnull(s)； // 構造空棧 s ch = getchar( )； //從終端接收第一個字符 while (ch! = EOF)//EOF為全文結束符 { while (ch ! = EOF amp。amp。 ch ! =`\ n`) {switch (ch) { case ` ` ： Pop(s， c)； break； //僅當棧非空時退棧 case `@` ： ClearStack(s)。break； //重置 s為空棧 default： Push(S,c)； break； ch = getchar( )； //從終端接收下一個字符 } clearStack(s)； //重置 s為空棧 if (ch ! = EOF) ch = getchar( )； } 隊列的定義及其運算 ? 隊列 （ Queue） :也是一種特殊的線性表，它只允許在表的一端進行插入而在另一端進行刪除。通常又把隊列叫做先進先出 （ FIFO—Fist In Fist Out） 表。 ? 有關術語 – 允許刪除的一端稱隊頭 （ Front） ，允許插入的一端稱隊尾 （ Rear） 。隊列 （ Queue） 也是一種特殊的線性表，它只允許在表的一端進行插入而在另一端進行刪除。 ? 隊列的基本運算： （ 1） 置空隊列 SETNULL（ Q） （ 2） 判隊列 EMPTY（ Q） （ 3） 入隊列 ENQUEUE（ Q， X） （ 4） 出隊列 DEQUEUE（ Q） （ 5） 取隊頭 FRONT（ Q） 鏈隊列 ? 鏈隊列 – 鏈式存儲結構簡稱鏈隊列 ， 對于使用中數(shù)據(jù)元素變動較大數(shù)據(jù)結構 ， 用鏈式存儲結構比順序結構更有利 。 ? 鏈隊列的特點 – 鏈隊列它是限制僅在表頭刪除和表尾插入的單鏈表 。 為了便于單鏈表的頭指針在表尾做插入操作 。再設置一個尾指針 ， 指向鏈表上的最后一個結點 。于是 ， 一個鏈隊列由一個頭指針和一個尾指針唯一確定 。 其中隊首指針 first指向單鏈表的表頭 ，隊尾指針 rear指向單鏈表的表尾 。 圖 例 單鏈隊列的定義 單鏈隊列－－隊列的鏈式存儲結構 typedef struct QNode { QElemType data。 QNode *next。 }*QueuePtr。 struct LinkQueue { QueuePtr front,rear。 // 隊頭 、 隊尾指針 }。 單鏈隊列圖例 鏈隊列 鏈隊列圖例 鏈隊列的基本操作 Status InitQueue(LinkQueue amp。Q) { // 構造一個空隊列 Q if(!(==(QueuePtr) malloc(sizeof(QNode)))) exit(OVERFLOW)。 next=NULL。 return OK。 } 空隊列圖例 鏈隊列的基本操作 Status DestroyQueue(LinkQueue amp。Q) { // 銷毀隊列 Q(無論空否均可 ) while() { =next。 free()。 =。 } return OK。 } 銷毀后的隊列 隊列的基本操作 Status ClearQueue(LinkQueue amp。Q) { // 將 Q清為空隊列 =。 p=next。 next=NULL。 while(p) {q=p。 p=pnext。 free(q)。 } return OK。 } 隊列的基本操作 Status QueueEmpty(LinkQueue Q) { // 若 Q為空隊列 ,則返回 TRUE,否則返回 FALSE if(==)
教學課件相關推薦
鄂ICP備17016276號-1