chapter3：棧、隊(duì)列(參考版)
2024-10-03 21:59本頁(yè)面
【正文】 ? return OK。//隊(duì)列空 ? e=[]。Q,QElemType amp。 ? reture OK。//隊(duì)列滿 ? []=e。 ? } ? Status EnQueue (SqQueue amp。 ? ==0。Q){ ? =(ElemType *) malloc(MaxQsize *sizeof (ElemType))。 ? } SqQueue。 ? int front。 出隊(duì)： (front++) MOD QueueSize； x=room[front]。這樣處理，隊(duì)中有一個(gè)元素的空間不被利用。為了處理方便，我們?nèi)匀患俣ǎ宏?duì)頭指示器：指向隊(duì)中第 1個(gè)元素的前一個(gè)位置。 先假定隊(duì)空間的下標(biāo)范圍為 0到 QueueSize 1， 要實(shí)現(xiàn)循環(huán)隊(duì)，只要實(shí)現(xiàn)頭尾指針回繞即可，其它與上面介紹的非循環(huán)隊(duì)列相同，根據(jù)模運(yùn)算特點(diǎn)，將頭尾指針加 1后按QueueSize取模即可。顯然，在循環(huán)隊(duì)列中，元素出隊(duì)后空出的位置可被重復(fù)使用，又免去了移動(dòng)元素的工作。但這種方法效率差，一種更好的方法是使用循環(huán)結(jié)構(gòu) ──這就是所謂循環(huán)隊(duì)列法。所以，這種隊(duì)列無(wú)實(shí)用價(jià)值。 進(jìn)隊(duì)與出隊(duì)操作結(jié)果的示意圖 空隊(duì)（初態(tài)） a aa3相繼進(jìn)隊(duì)后 a a2相繼出隊(duì) a4進(jìn)隊(duì) a a4相繼出隊(duì) a a6相繼進(jìn)隊(duì)（隊(duì)已“滿”） Rear Front Front Front Front Front Front Rear Rear Rear Rear Rear 顯然，若隊(duì)空間為 N個(gè)元素，則進(jìn)行 N次進(jìn)隊(duì)操作后就會(huì)出現(xiàn)隊(duì)滿現(xiàn)象，而不論這中間是否進(jìn)行過(guò)出隊(duì)操作，即出隊(duì)操作所騰出的空位不能重復(fù)利用。 如此 rear已指向隊(duì)空間中最后一個(gè)元素（值為 n1）， 則上列所示的進(jìn)隊(duì)操作將失敗，我們稱(chēng)這種情況為隊(duì)滿?；厮完?duì)頭元素 ? 隊(duì)空： room[rear]=room[front]。 ? 出隊(duì) : front++。room[rear]=x。為了處理方便， 隊(duì)空間的第一個(gè)元素（下稱(chēng)為 0）不利用，front指向隊(duì)中第 i個(gè)元素的前一個(gè)位置（即 front為第 i 個(gè)元素的前趨的下標(biāo)值）， rear指向隊(duì)尾元素，初始時(shí)，令 front與 rear為 0。 隊(duì)列的連續(xù)存貯結(jié)構(gòu) 一、非循環(huán)隊(duì)列 與棧類(lèi)似，隊(duì)列也有相應(yīng)的連續(xù)存貯結(jié)構(gòu)，同樣用一維數(shù)組作隊(duì)元素存貯空間，另設(shè)兩個(gè)指示器分別指示隊(duì)頭與隊(duì)尾（分別稱(chēng)對(duì)頭與隊(duì)尾指針） Rear Front Room …… 隊(duì)頭元素指示器，令其指向第一個(gè)元素的位置 隊(duì)尾元素指示器，令其指向隊(duì)尾的位置 存儲(chǔ)元素的一維數(shù)組 實(shí)現(xiàn) ? 初始化 : front =rear =0 。 ? return OK。 ? if(==p)=。 ? e=pdata。e) { ? //Q為非空隊(duì)列 ,刪除 Q的隊(duì)頭元素 ,并用 e返回其值 ? if(==)return ERROR。} ? Status DeQueue(LinkQueue amp。 ? =p。pnext=NULL。 ? if(!p) exit(OVERFLOW)。} ? Status EnQueue(LinkQueue amp。 ? =。Q) { ? //隊(duì)列 Q存在則銷(xiāo)毀 Q ? while(){ ? =next。 ? return OK。 ? if(!)exit(OVERFLOW)。 一旦 visit()失敗，則操作失敗 ? Status InitQueue(LinkQueue amp。Q,QElemType amp。e) ? //Q為非空隊(duì)列 ,用 e返回 Q的隊(duì)頭元素 ? Status EnQueue(LinkQueue amp。Q) ? //隊(duì)列 Q存在則銷(xiāo)毀 Q ? Status ClearQueue(LinkQueue amp。 ? //操作說(shuō)明 ? Status InitQueue(LinkQueue amp。 ? QueuePtr rear。 ? }QNode,*QueuePtr。 LinkedListItr a1 a2 a3 a4 Front of queue Back of queue 鏈隊(duì)列表示和實(shí)現(xiàn) ? //存儲(chǔ)表示 ? typedef struct QNode{ ? QElemType data。一旦 visit()失敗，則操作失敗 ? }ADT Q
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1