[理學(xué)]數(shù)據(jù)結(jié)構(gòu)3第三章：棧和隊(duì)列(已改無錯(cuò)字)
2022-11-16 21:14:46 本頁面
【正文】 return TRUE。 else return FALSE。 } 鏈隊(duì)列的基本操作 int QueueLength(LinkQueue Q) { // 求隊(duì)列的長度 int i=0。 QueuePtr p。 p=。 while(!=p) { i++。 p=pnext。 } return i。 } 鏈隊(duì)列的基本操作 Status EnQueue(LinkQueue amp。Q,QElemType e) { // 插入元素 e為 Q的新的隊(duì)尾元素 p=(QueuePtr)malloc(sizeof(QNode)) if(!p) exit(OVERFLOW)。 // 存儲分配失敗 pdata=e。 pnext=NULL。 next=p。 =p。 return OK。 } 鏈隊(duì)列的基本操作 Status DeQueue(LinkQueue amp。Q,QElemType amp。e) { // 若隊(duì)列不空 ,刪除 Q的隊(duì)頭元素 ,用 e返回其值 if(==) return ERROR。 p=next。 e=pdata。 next=pnext。 if(==p) =。 free(p)。 return OK。 } 順序存儲結(jié)構(gòu) —循環(huán)隊(duì)列 ? 順序隊(duì)列出現(xiàn)假溢出的問題 如果不考慮溢出，入隊(duì)列操作可描述如下： =+1； []=x 出隊(duì)運(yùn)算描述為： =+1 顯然，當(dāng) =，若作出隊(duì)操作，則產(chǎn)生 ? 下溢 ? 。當(dāng) =m時(shí)，隊(duì)滿，再作入隊(duì)操作也會引起 ? 上溢 ? 。 ? 循環(huán)隊(duì)列 :為了提高運(yùn)算的效率，我們用另一種方法表達(dá)數(shù)組中各單元的位置關(guān)系。設(shè)想數(shù)組 Q中的 m個(gè)單元不是排成一行，而是圍成一個(gè)圓環(huán)，即 Q[0]接在 Q[m1]之后，形成一個(gè)閉合的環(huán)，這個(gè)意義下的隊(duì)列叫做循環(huán)隊(duì)列。 隊(duì)列的假溢出 循環(huán)隊(duì)列示意圖 循環(huán)隊(duì)列的定義 define MAXQSIZE 5 // 最大隊(duì)列長度 (對于循隊(duì)列 ， 最大隊(duì)列長度要減 1) struct SqQueue {QElemType *base。 // 初始化的動態(tài)分配存儲空間 int front。 // 頭指針 ,若隊(duì)列不空 ,指向隊(duì)列頭元素 int rear。 // 尾指針 ,若隊(duì)列不空 ,指向隊(duì)列尾元素的下一個(gè)位置 }。 隊(duì)列的順序存儲結(jié)構(gòu) 循環(huán)隊(duì)列的基本操作 Status InitQueue(SqQueue amp。Q) { // 構(gòu)造一個(gè)空隊(duì)列 Q =(QElemType*) malloc(MAXQSIZE*sizeof(QElemType))。 if(!) // 存儲分配失敗 exit(OVERFLOW)。 ==0。 return OK。 } 空隊(duì)列圖例 循環(huán)隊(duì)列的基本操作 int QueueLength(SqQueue Q) { // 返回 Q的元素個(gè)數(shù) ,即隊(duì)列的長度 return(+MAXQSIZE)%MAXQSIZE。 } Status GetHead(SqQueue Q,QElemType amp。e) { // 若隊(duì)列不空 ,則用 e返回 Q的隊(duì)頭元素 ,并返回 OK,否則返回 ERROR if(==) // 隊(duì)列空 return ERROR。 e=*(+)。 return OK。 } 循環(huán)隊(duì)列的基本操作 Status EnQueue(SqQueue amp。Q,QElemType e) { // 插入元素 e為 Q的新的隊(duì)尾元素 if((+1)%MAXQSIZE==) // 隊(duì)列滿 return ERROR。 []=e。 =(+1)%MAXQSIZE。 return OK。 } 入隊(duì)操作 循環(huán)隊(duì)列的基本操作 Status DeQueue(SqQueue amp。Q,QElemType amp。e) { // 若隊(duì)列不空 ,則刪除 Q的隊(duì)頭元素 ,用 e返回其值 ,并返回 OK。否則返
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1