數(shù)據(jù)結(jié)構(gòu)--第三章棧和隊列-資料下載頁
2025-01-18 18:51本頁面
【正文】 。 /*若要刪除的為隊尾元素 ,即刪除后隊列為空 ,則修改尾指針 */ *x=pdata。 free(p)。 /*刪除該元素 */ return(true)。 } 3）出隊 56 二、循環(huán)隊列 盡管鏈隊列使用方便 ,但由于其指針多占存儲空間 ,有時仍需要用順序結(jié)構(gòu)來表示隊列。 順序隊列中也需要兩個“指針”： 頭指針 front指示 隊頭元素的當(dāng)前位置； 尾指針 rear指示 隊尾元素的后一個位置。 初始時 front=rear=0。 57 循環(huán)隊列存儲結(jié)構(gòu)定義 define maxsize 50 QueueElementtype Q[maxsize]。 /*保存隊列元素值的數(shù)組 */ int front,rear。 /*隊列的頭為指針，全局變量 */ 58 此時入隊操作為： Q[rear] =x。 rear= rear+1。 出隊操作為： x=q[front]； front= front+1； 隊空條件： rear = front 假隊滿： rear ==maxsize, 隊滿： rear – front =maxsize 或 rear=front rear – front ＜ maxsize 假 rear front D E G rear front A B C rear front 0 1 2 3 4 5 rear front 假溢出 當(dāng) rearmaxsize 時 , 隊列滿 (即上溢 ), 但此時頭指針指示的元素之前可能還有空單元 , 此現(xiàn)象稱為假溢出 。 59 0 1 2 3 4 5 6 7 A B C D E F G H 隊滿條件： rear = front 隊空條件： rear = front 如何區(qū)分隊空與隊滿呢？ 循環(huán)隊列的元素個數(shù)為： (rear front+maxsize)%maxsize 解決假溢出的方法可以是：把順序結(jié)構(gòu)設(shè)想為一個循環(huán)表 , 這樣就可以利用頭指針前的空單元 , 這就構(gòu)成了循環(huán)隊列。 60 循環(huán)隊列“空”與“滿”的判定 循環(huán)隊列中 , 判隊“空”與“滿”應(yīng)格外注意 : front= =rear 隊“空”？ 隊“滿”？ 解決辦法 1: 少用一個元素空間 , 則： front= =rear+1 為滿 解決辦法 2: 設(shè)隊“空” 、隊“滿” 標志； 61 隊滿條件： （ rear+1) mod maxsize =front 隊空條件： rear = front 0 1 2 3 4 5 6 7 A B C D E F G rear 解決方法 1：少用一個存儲單元 62 循環(huán)隊列基本操作的實現(xiàn) 1) 初始化 void initQueue(int *Q) { front=rear= 0。 } 63 2) 入隊 int Enterqueue(int *Q， int x) {if ((rear+1)% maxsize==front) return(false)。 Q[rear] =x。 rear= (rear+1)% maxsize。 return(true)。 } 64 3）出隊 int Deletequeue(int *Q, int *x) {if (rear==front) return(false)。 *x= Q[front]。 front= (front+1)% maxsize。 return(true)。 } 65 隊滿條件： rear = = front amp。amp。 tag= = 1 隊空條件： rear = = front amp。amp。 tag = = 0 解決方法 2：設(shè)置一個標志位 假設(shè)標志位 tag， 初值＝ 0 當(dāng) 入隊列 操作成功， tag=1。 當(dāng) 出隊列 操作成功， tag=0。 5. 隊列的應(yīng)用 火車調(diào)度； 操作系統(tǒng)中的各種數(shù)據(jù)緩沖區(qū)的先進先出管理； 應(yīng)用系統(tǒng)中的各種事件排隊管理 棧和隊列是兩種常用的數(shù)據(jù)類型 線性表 棧 隊列 Insert(L,i,x) Insert(S,n+1,x) Insert(Q,n+1,x) 1≤i≤n+1 Delete(L,i) Delete(S,n) Delete(Q,1) 1≤i≤n 棧與隊列 棧是限定僅在表尾進行插入和刪除的線性表。 隊列是限定僅在表尾進行插入、在表頭進行 刪除的線性表。 68
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1