【正文】 隊(duì)一元素，剩余元素向隊(duì)頭方向平移 —— 費(fèi)時(shí) (2)當(dāng)不能入隊(duì)時(shí)，檢查隊(duì)列中是否有空，若有則平移 —— 耗時(shí) 有效辦法：使 0單元接在 MaxSize1單元后 (邏輯上 )， 形成環(huán)形結(jié)構(gòu) —— 循環(huán)隊(duì)列 循環(huán)隊(duì)列 : ? 在循環(huán)隊(duì)列中，其存儲(chǔ)空間是首尾循環(huán)利用的，當(dāng)隊(duì)尾指針rear指向最后一個(gè)存儲(chǔ)位置時(shí)，下一個(gè)所求的位置自動(dòng)為數(shù)組空間的開(kāi)始位置（即下標(biāo)為 0的位置） m1 0 1 2 3 …… 隊(duì)列的初始狀態(tài) front rear 循環(huán)隊(duì)列的運(yùn)算 設(shè) 以 Queue(0:MaxSize1)為循環(huán)隊(duì)列的存儲(chǔ)空間 初始隊(duì)空時(shí)， front=rear=0 入隊(duì)指針操作： rear= (rear+1)% MaxSize 退隊(duì)指針操作： front= (front+1)% MaxSize 在隊(duì)列操作時(shí)，由于有兩個(gè)指針，而且這兩個(gè)指針都會(huì)移動(dòng)，因此判斷其隊(duì)空和隊(duì)滿(mǎn)的方法與普通的線性表的判斷方法有較大的不同，特別是在循環(huán)隊(duì)列。 循環(huán)隊(duì)列的判斷隊(duì)空、隊(duì)滿(mǎn)的辦法為： 當(dāng)隊(duì)尾指針追上隊(duì)頭指針時(shí)為隊(duì)滿(mǎn) 即： if ((rear+1)% MaxSize= =front) 則隊(duì)滿(mǎn)； 否則： front= =raer 則為隊(duì)空。 此法優(yōu)點(diǎn)：僅根據(jù) front、 rear指針就可做判斷 ,算法較簡(jiǎn)單。 不足：實(shí)際利用的存儲(chǔ)單元為 MaxSize1個(gè) （浪費(fèi)一個(gè)存儲(chǔ)單元） 二、隊(duì)列的數(shù)據(jù)類(lèi)型定義 ⑴ 隊(duì)列和指針?lè)珠_(kāi)定義 ElemType queue[MaxSize]。 /* MaxSize為已定義的常量*/ int front, rear, len。 其中 MaxSize的值確定了 queue數(shù)組所能存儲(chǔ)隊(duì)列的最大長(zhǎng)度。 ⑵ 隊(duì)列的記錄定義 隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)同樣可以被定義在一個(gè)記錄類(lèi)型中，假定該記錄類(lèi)型用 QueueSq表示，則定義為： struct QueueSq { ElemType queue[MaxSize]。 int front, rear, len。 }。 ⑶ 隊(duì)列數(shù)組采用動(dòng)態(tài)分配的動(dòng)態(tài)定義 若要對(duì)存儲(chǔ)隊(duì)列的數(shù)組空間采用動(dòng)態(tài)分配，則 QueueSq結(jié)構(gòu)類(lèi)型可定義為： struct QueueSq { ElemType *queue。 /*指向存儲(chǔ)隊(duì)列的數(shù)組空間 */ int front, rear, len。 /*隊(duì)首指針、隊(duì)尾指針、隊(duì)列 長(zhǎng)度變量 */ int MaxSize。 /*queue數(shù)組長(zhǎng)度 */ }。 1. 初始化隊(duì)列 第一種情況是隱含分配用于存儲(chǔ)隊(duì)列的固定大小的動(dòng)態(tài)存儲(chǔ)空間，假定動(dòng)態(tài)存儲(chǔ)空間的大小為 10。 void InitQueue(struct QueueSq* Q) { /*置隊(duì)列空間初始最大長(zhǎng)度為 10*/ QMaxSize=10。 /*動(dòng)態(tài)存儲(chǔ)空間分配 */ Qqueue=malloc(10*sizeof(ElemType))。 /*置隊(duì)列為空 */ Qfront=Qrear=0。 } 第二種情況是分配由參數(shù)指定大小的動(dòng)態(tài)存儲(chǔ)空間。實(shí)用中使用任一種初始化算法均可。 void InitQueue(struct QueueSq* Q, int ms) { /*檢查 ms是否有效，若無(wú)效則退出運(yùn)行 */ if(ms=0) {printf(ms值非法 !\n)。 exit(1)。} /*置隊(duì)列空間大小為 ms*/ QMaxSize=ms。 /*動(dòng)態(tài)存儲(chǔ)空間分配，若分配失敗則退出運(yùn)行 */ Qqueue=malloc(ms*sizeof(ElemType))。 if(!Qqueue) { printf(內(nèi)存空間用完 !\n)。 exit(1)。 } /*初始置隊(duì)列為空 */ Qfront=Qrear=0。 2. 向隊(duì)列插入元素 void EnQueue(struct QueueSq* Q, ElemType x) { /*當(dāng)隊(duì)列滿(mǎn)時(shí)進(jìn)行動(dòng)態(tài)重分配 */ if((Qrear+1)%QMaxSize==Qfront) againMalloc(Q)。 /*求出隊(duì)尾的下一個(gè)位置 */ Qrear=(Qrear+1)%QMaxSize。 /*把 item的值賦給新的隊(duì)尾位置 */ Qqueue[Qrear]=x。 } againMalloc()算法的具體定義如下： void againMalloc(struct QueueSq* Q) { /*空間擴(kuò)展為原來(lái)的 2倍，并由 p所指向，原內(nèi)容被自動(dòng)拷貝到 p所指向的存儲(chǔ)空間中 */ ElemType *p。 p=realloc(Qqueue, 2*QMaxSize*sizeof(ElemType))。 if(!p) { /*分配失敗退出運(yùn)行 */ printf(存儲(chǔ)空間用完 !\n)。 exit(1)。 } /*使 queue指向新的隊(duì)列空間 */ Qqueue=p。 /*把原隊(duì)列的尾部?jī)?nèi)容向后移動(dòng) MaxSize個(gè)位置 */ if(Qrear!=QMaxSize1) { int i。 for(i=0。 i=Qrear。 i++) Qqueue[i+QMaxSize]=Qqueue[i]。 Qrear+=QMaxSize。 /*隊(duì)尾指針后移 MaxSize個(gè)位置 */ } /*把隊(duì)列空間大小修改為新的長(zhǎng)度 */ QMaxSize=2*QMaxSize。 } 3. 從隊(duì)列中刪除元素并返回 ElemType OutQueue(struct QueueSq* Q) { /*若隊(duì)列為空則終止運(yùn)行 */ if(Qfront==Qrear) { printf(隊(duì)列已空，無(wú)法刪除 !\n)。 exit(1)。 } /*使隊(duì)首指針指向下一個(gè)位置 */ Qfront=(Qfront+1)%QMaxSize。 /*返回隊(duì)首元素 */ return Qqueue[Qfront]。 } 隊(duì)列的鏈接存儲(chǔ)結(jié)構(gòu)和操作實(shí)現(xiàn) ?隊(duì)列的鏈接存儲(chǔ)結(jié)構(gòu)也是通過(guò)由結(jié)點(diǎn)構(gòu)成的單鏈表實(shí)現(xiàn)的，此時(shí)只允許在單鏈表的表頭進(jìn)行刪除和在單鏈表的表尾進(jìn)行插入，因此它需要使用兩個(gè)指針：隊(duì)首指針 front和隊(duì)尾指針 rear。 ? front指向隊(duì)首結(jié)點(diǎn)的存儲(chǔ)位置， rear指向隊(duì)尾結(jié)點(diǎn)的存儲(chǔ)位置。 ?用于存儲(chǔ)隊(duì)列的單鏈表簡(jiǎn)稱(chēng) 鏈接隊(duì)列 或 鏈隊(duì) 。 采用鏈接存儲(chǔ)結(jié)構(gòu)的隊(duì)列中數(shù)據(jù)節(jié)點(diǎn)的定義： struct QueueLk { sNode* front。 //隊(duì)首指針 sNode* rear。 //隊(duì)尾指針 }。 其中 sNode結(jié)點(diǎn)類(lèi)型重寫(xiě)如下： struct sNode { ElemType data。 /*值域 */ struct sNode* next。 /*鏈接指針域 */ }。 ? 一個(gè)鏈接存儲(chǔ)的隊(duì)列如下圖所示。 ...frontreara1 a 2an在類(lèi)型為 QueueLk的鏈隊(duì) HQ上進(jìn)行隊(duì)列的各種操作的算法如下： 1. 初始化鏈隊(duì) void InitQueue(struct QueueLk* HQ) { /*把隊(duì)首和隊(duì)尾指針置為空 */ HQfront=HQrear=NULL。 } 2. 向鏈隊(duì)中插入一個(gè)元素 void EnQueue(struct QueueLk* HQ, ElemType x) { /*得到一個(gè)由 newp指針?biāo)赶虻男陆Y(jié)點(diǎn) */ struct sNode* newp。 newp=malloc(sizeof(struct sNode))。 if(newp==NULL) { printf(內(nèi)存動(dòng)態(tài)空間用完，退出運(yùn)行 !\n)。 exit(1)。 } /*把 x的值賦給新結(jié)點(diǎn)的值域，把新結(jié)點(diǎn)的指針域置空 */ newpdata=x。 newpnext=NULL。 /*若鏈隊(duì)為空，則新結(jié)點(diǎn)既是隊(duì)首結(jié)點(diǎn)又是隊(duì)尾結(jié)點(diǎn) */ if(HQrear==NULL) HQfront=HQrear=newp。 /*若鏈隊(duì)非空，則依次修改隊(duì)尾結(jié)點(diǎn)的指針域和隊(duì)尾指針， 使之指向新的隊(duì)尾結(jié)點(diǎn) */ else HQrear=HQrearnext=newp。 } 3. 從隊(duì)列中刪除一個(gè)元素 ElemType OutQueue(struct QueueLk* HQ) { struct sNode* p。 ElemType temp。 /*若鏈隊(duì)為空則中止運(yùn)行 */ if(HQfront==NULL) { printf(隊(duì)列為空無(wú)法刪除 !\n)。 exit(1)。 } /*暫存隊(duì)首元素以便返回 */ temp=HQfrontdata。 /*暫存隊(duì)首指針以便回收隊(duì)首結(jié)點(diǎn) */ p=HQfront。 /*使隊(duì)首指針指向下一個(gè)結(jié)點(diǎn) */ HQfront=pnext。 /*若刪除后鏈隊(duì)變?yōu)榭?，則需同時(shí)使隊(duì)尾指針變?yōu)榭?*/ if(HQfront==NULL) HQrear=NULL。 /*回收原隊(duì)首結(jié)點(diǎn)，返回被刪除的隊(duì)首元素 */ free(p)。 return temp。 } 作業(yè) ? 第 3 題 ? 算法分析題 第 2 題 ? 題中 第 1 題