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