chapter3：棧、隊(duì)列(編輯修改稿)
2024-11-04 21:59 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 現(xiàn)實(shí)世界中有許多問(wèn)題（關(guān)系）可用隊(duì)列描述，顧客服務(wù)部門(mén)的工作方式往往是排隊(duì)方式，這類(lèi)系統(tǒng)稱(chēng)作排隊(duì)系統(tǒng)。在計(jì)算機(jī)算法實(shí)現(xiàn)中，也經(jīng)常使用隊(duì)列記錄需按 FIFO方式處理的數(shù)據(jù)。 ? ────────────── ? 出隊(duì) ← ○ ○ …… ○ ← ○進(jìn)隊(duì) ? ────────────── ? 隊(duì)頭 隊(duì)尾 Queue front rear enqueue dequeue A B C A queue is open at two ends. You can only add entry (enqueue) at the rear , and delete entry (dequeue) at the front. Note that you cannot add/extract entry in the middle of the queue. Firstin Firstout (FIFO) When we enqueue entries in the queue and then dequeue them one by one, we will get the entries in the same order. A B C A A B B C C The first one enqueued is the first one dequeued. (FIFO) 抽象數(shù)據(jù)類(lèi)型隊(duì)列 ? ADT Queue{ ? 數(shù)據(jù)對(duì)象 : D={ai| ai(ElemSet,i=1,2,...,n,n=0} ? 數(shù)據(jù)關(guān)系 : R1={ai1,ai | ai1,ai( D,i=2,...,n} ? 基本操作： ? InitQueue(amp。Q) 構(gòu)造一個(gè)空隊(duì)列 Q ? Destroyqueue(amp。Q) 隊(duì)列 Q存在則銷(xiāo)毀 Q ? ClearQueue(amp。Q) 隊(duì)列 Q存在則將 Q清為空隊(duì)列 ? QueueEmpty(Q) 隊(duì)列 Q存在 ,若 Q為空隊(duì)列則返回 TRUE,否則返回 FALSE ? QueueLenght(Q) 隊(duì)列 Q存在 ,返回 Q的元素個(gè)數(shù) ,即隊(duì)列的長(zhǎng)度 ? GetHead(Q,amp。e) Q為非空隊(duì)列 ,用 e返回 Q的隊(duì)頭元素 ? EnQueue(amp。Q,e) 隊(duì)列 Q存在 ,插入元素 e為 Q的隊(duì)尾元素 ? DeQueue(amp。Q,amp。e) Q為非空隊(duì)列 ,刪除 Q的隊(duì)頭元素 ,并用 e返回其值 ? QueueTraverse(Q,vivsit()) Q存在且非空 ,從隊(duì)頭到隊(duì)尾 ,依次對(duì) Q的每個(gè)數(shù)據(jù)元素調(diào)用函數(shù) visit()。一旦 visit()失敗，則操作失敗 ? }ADT Queue 二、鏈隊(duì)列－隊(duì)列的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn) ? 用鏈表表示的隊(duì)列簡(jiǎn)稱(chēng)為鏈隊(duì)列。一個(gè)鏈隊(duì)列顯然需要兩個(gè)分別指示隊(duì)頭和隊(duì)尾的指針。 LinkedListItr a1 a2 a3 a4 Front of queue Back of queue 鏈隊(duì)列表示和實(shí)現(xiàn) ? //存儲(chǔ)表示 ? typedef struct QNode{ ? QElemType data。 ? struct QNode *next。 ? }QNode,*QueuePtr。 ? typedef struct{ ? QueuePtr front。 ? QueuePtr rear。 ? }LinkQueue。 ? //操作說(shuō)明 ? Status InitQueue(LinkQueue amp。Q) ? //構(gòu)造一個(gè)空隊(duì)列 Q ? Status Destroyqueue(LinkQueue amp。Q) ? //隊(duì)列 Q存在則銷(xiāo)毀 Q ? Status ClearQueue(LinkQueue amp。Q) ? //隊(duì)列 Q存在則將 Q清為空隊(duì)列 ? Status QueueEmpty(LinkQueue Q) ? // 隊(duì)列 Q存在 ,若 Q為空隊(duì)列則返回 TRUE,否則返回 FALSE ? Status QueueLenght(LinkQueue Q) ? // 隊(duì)列 Q存在 ,返回 Q的元素個(gè)數(shù) ,即隊(duì)列的長(zhǎng)度 ? Status GetHead(LinkQueue Q,QElemType amp。e) ? //Q為非空隊(duì)列 ,用 e返回 Q的隊(duì)頭元素 ? Status EnQueue(LinkQueue amp。Q,QElemType e) ? //隊(duì)列 Q存在 ,插入元素 e為 Q的隊(duì)尾元素 ? Status DeQueue(LinkQue
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1