C語言隊列課件

4.4隊列隊列的概念及運(yùn)算(邏輯結(jié)構(gòu))1隊列只允許在表的一端進(jìn)行插入，而在另一端進(jìn)行刪除。隊頭允許刪除的一端隊尾允許插入的一端隊列的概念出隊入隊隊頭隊尾a1

a2

an

...

隊列是先進(jìn)先出表2隊列的基本運(yùn)算：

創(chuàng)建一個空隊列

QueuecreateEmptyQueue(void)

判隊列是否為空隊列

int

isEmptyQueue(Queuequ)

往隊列中插入一個元素

voidenQueue(Queuequ,DataTypex)

從隊列中刪除一個元素

voiddeQueue(Queuequ)

求隊列頭部元素的值

DataType

frontQueue(Queuequ)

隊列的運(yùn)算34.5隊列的實現(xiàn)4.5.1.順序隊列4.5.2.鏈隊列44.5.1順序隊列

隊列的順序存儲結(jié)構(gòu)簡稱為順序隊列。順序隊列實際上是運(yùn)算受限的順序表。

由于隊列的隊頭和隊尾的位置均是變化的，因而要設(shè)置兩個指針，分別指示當(dāng)前隊頭元素和隊尾元素在向量空間中的位置。5#defineMAXNUM100struct

SeqQueue{datatypeq[MAXNUM];

intf,r;};typedef

struct

SeqQueue*PSeqQueue;PSeqQueuesq;順序隊列的定義4.5.1順序隊列6fr76543210k1k2k3frrfk8k7①隊列空④隊列數(shù)組越界順序隊列②約定③隊列滿k1k2k3fk8rk4k5k6k7開始：sq->f=0;sq->r=0;入隊：

sq->data[sq->r]=x;sq->r++;出隊：

sq->f++;順序隊列的入隊和出隊4.5.1順序隊列8元素個數(shù)（隊列長度）:（sq->r)-(sq->f)

若（sq->r)-(sq->f)=0，則隊列長度為0，即空隊列。再出隊會“下溢”

若(sq->r)-(sq->f)=MAXNUM，則隊滿。隊滿時再入隊會“上溢”4.5.1順序隊列976543210frk1k2k3frrfk6k5隊列空隊列數(shù)組越界順序隊列4.5.1順序隊列假上溢：當(dāng)前隊列并不滿，但不能入隊。每次出隊時向前移一位置。大量移動元素循環(huán)隊列原因:被刪除元素的空間沒有再被使用解決:11采用循環(huán)隊列克服“假上溢”。。。sq->rsq->fMAXNUM-101指針移動方向12入隊：if(sq->r+1>=MAXNUM)sq->r=0;elsesq->r++;利用模運(yùn)算

sq->r=(sq->r+1)%MAXNUM出隊：

sq->f=(sq->f+1)%MAXNUM采用循環(huán)隊列克服“假上溢”4.5.1順序隊列13

某一元素出隊后，若頭指針已從后面追上尾指針，則當(dāng)前隊列為空：

sq->f=sq->r

某一元素入隊后，若尾指針已從后面追上頭指針，則當(dāng)前隊列為滿：

sq->f=sq->r

因此，僅憑

sq->f=sq->r

是無法區(qū)別隊列空還是隊列滿。

判斷隊空和隊滿4.5.1順序隊列14解決辦法標(biāo)志變量測試尾指針在循環(huán)意義下是否等于頭指針

判別隊列滿的條件：

(sq->r+1)%MAXNUM=sq->f使sq->f=sq->r

成為判斷隊列空的條件4.5.1順序隊列元素個數(shù)是MAXNUM-115sq.rearsq.frontk1k2k7k6k5k4k3sq.frontsq.rear圖(a)空隊列圖(b)隊列滿

圖4.9循環(huán)隊列4.5.1順序隊列在循環(huán)隊列上實現(xiàn)五種基本運(yùn)算：

1.置空隊

2.判隊空

3.取隊頭元素

4.入隊

5.出隊17循環(huán)隊列front=n-3……an-3an-2012MaxQsize-1rear=n-1n-3rear=n-1an-3an-20.1...front=n-3n-2插入元素：rear順時針移動一位front=n-3……an-3an-2012MaxQsize-1rear=0xn-3an-3rear=0an-20.1n-1...front=n-3n-2xrear=(rear+1)MODMaxQSize刪除元素：front順時針移動一位front=(front+1)MODMaxQSize;rear0front=9.1...CD刪除Crearfront=00.1...D循環(huán)隊列front指定隊首位置，刪除一個元素就將front順時針移動一位；

rear指向元素要插入的位置，插入一個元素就將rear順時針移動一位；

count存放隊列中元素的個數(shù)，當(dāng)count等于MaxQSize時，不可再向隊列中插入元素。隊空：count=0隊滿：count=

MaxQSize數(shù)組隊列實現(xiàn)在隊列的頭部取出元素。普通的隊列由于空間利用率不高，所以我們一般都用循環(huán)隊列。循環(huán)隊列中最重要的的兩個操作就是判斷是否為空和是否已滿。當(dāng)head==tail時，表示隊列為空。當(dāng)(tail+1)%MAX_SIZE==head，表示隊列已滿。我判斷隊滿的方法：犧牲一個單元來區(qū)分對空和隊滿，入隊時少用一個隊列單元，相當(dāng)于浪費(fèi)一個存儲空間。“隊頭指針的隊尾指針的下一位置作為隊滿的標(biāo)志”。進(jìn)隊列

EnQueue(intvalue){//要先判斷隊列是否已滿

if((tail+1)%QUEUE_SIZE==head){

printf("隊列已滿，無法從隊尾插入元素\n");}else{

queue[tail]=value;tail=(tail+1)%QUEUE_SIZE;}}/出隊列intDeQueue(){inttemp;if(tail==head){printf("隊列為空，元素?zé)o法出隊列\(zhòng)n");}else{temp=queue[head];

head=(head+1)%QUEUE_SIZE;

}

printf("%d\n",temp);

returntemp;

/判斷隊列是否為空intIsEmpty(){if(head==tail){printf("隊列為空\n");return1;}

printf("隊列不為空\n");return0;}判斷隊列是否已滿/***我這里判斷隊滿的的方法：犧牲一個單元來區(qū)分隊空和隊滿，入隊時少用一個隊列單元。如果數(shù)組的大小為Size,那么實際只能存放(Size-1)個元素。（這是比較常用的判滿的方式）**/

intIsFull(){

if((tail+1)%QUEUE_SIZE==head){printf("隊列已滿\n");return1;}

printf("隊列未滿\n");return0;}/打印出隊列元素voidPrintQueue(){

for(inti=head;i<tail;i++){printf("%d",queue[i]);}printf("\n");}#include<stdio.h>#defineQUEUE_SIZE200intqueue[QUEUE_SIZE];inthead=0;//頭指針inttail=0;//尾指針intmain（）{EnQueue(4);EnQueue(1);EnQueue(2);EnQueue(9);EnQueue(8);PrintQueue();DeQueue();DeQueue();PrintQueue();return0;1.置空隊PSeqQueue

createEmptyQueue_seq(void){

PSeqQueuesq;sq=(PSeqQueue)malloc(sizeof(struct

SeqQueue));if(sq==NULL)

printf("Outofspace!!\n"); else {sq->f=0; sq->r=0; } return(sq);}

292.判隊空int

isEmptyQueue_seq(PSeqQueuesq){return(sq->f==sq->r);}

303.取隊頭元素DataType

frontQueue_seq(PSeqQueuesq)/*對非空隊列,求隊列頭部元素

*/{return(sq->q[sq->f]);}314.入隊voidenQueue_seq(PSeqQueuesq,DataTypex)/*在隊列中插入一元素x*/{if((sq->r+1)%MAXNUM==sq->f)

printf("Fullqueue.\n");else { sq->q[sq->r]=x; sq->r=(sq->r+1)%MAXNUM; }}

325.出隊voiddeQueue_seq(PSeqQueuesq)/*刪除隊列頭部元素

*/{ if(sq->f==sq->r)

printf("EmptyQueue.\n"); else sq->f=(sq->f+1)%MAXNUM;}

334.5.2鏈隊列

隊列的鏈?zhǔn)酱鎯Y(jié)構(gòu)簡稱為鏈隊列，它是限制僅在表頭刪除和表尾插入的單鏈表。

顯然僅有單鏈表的頭指針不便于在表尾做插入操作，為此再增加一個尾指針，指向鏈表上的最后一個結(jié)點。于是，一個鏈隊列由一個頭指針和一個尾指針唯一地確定。34

k0

k1

k2

kn-1….

圖4.10隊列的鏈接表示plqu

fr

structNode;

typedef

structNode*pNode;

structNode{DataTypeinfo;

pNode link;};

struct

LinkQueue{PNode f;

PNode r;};

typedef

struct

LinkQueue,*PLinkQueue;隊列的鏈接表示36

^

*plqu頭結(jié)點plqu->fplqu->r

頭結(jié)點

隊頭結(jié)點plqu->fplqu->r空和非空的鏈隊列...

^

374.5.2鏈隊列在鏈隊列上實現(xiàn)的五種基本運(yùn)算如下：

1.置空隊

2.判隊空

3.取隊頭結(jié)點數(shù)據(jù)

4.入隊

5.出隊381.置空隊（算法4.21）PLinkQueue

createEmptyQueue_link(){PLinkQueue

plqu;

plqu=(PLinkQueue)malloc(sizeof(struct

LinkQueue));if(plqu!=NULL){

plqu->f=NULL;

plqu->r=NULL;}else

printf("Outofspace!!\n"); return(plqu);}392.判隊空（算法4.22）int

isEmptyQueue_link(PLinkQueue

plqu){ return(plqu->f==NULL);}

403.取隊頭結(jié)點數(shù)據(jù)（算法4.25）DataType

frontQueue_link(PLinkQueue

plqu)/*在非空隊列中求隊頭元素

*/{ return(plqu->f->info);}

414.入隊（算法4.23）voidenQueue_link(PLinkQueue

plqu,DataTypex){PNodep;p=(PNode)malloc(sizeof(structNode));if(p==NULL)

printf("Outofspace!");else{p->info=x; p->link=NULL;if(plqu->f==NULL) {plqu->f=p; plqu->r=p; }else {plqu->r->link=p; plqu->r=p; }}}

425.出隊（算法4.24）voiddeQueue_link(PLinkQueue

plqu){PNodep; if(plqu->f==NULL)

printf("Emptyqueue.\n"); else {p=plqu->f;

plqu->f=plqu->f->link; free(p); }}43農(nóng)夫過河問題

:

一個農(nóng)夫帶著一只狼、一只羊和一棵白菜，身處河的南岸。他要把這些東西全部運(yùn)到北岸。問題是他面前只有一條小船，船小到只能容下他和一件物品，另外只有農(nóng)夫能撐船。顯然，因為狼能吃羊，而羊愛吃白菜，所以農(nóng)夫不能留下羊和白菜自己離開，也不能留下狼和羊自己離開。好在狼屬于食肉動物，它不吃白菜。請問農(nóng)夫該采取什么方案才能將所有的東西運(yùn)過河?

4.6隊列的應(yīng)用—農(nóng)夫過河問題*44

用計算機(jī)實現(xiàn)上述求解的搜索過程可以采用兩種不同的策略：一種是廣度優(yōu)先(breadth_first)搜索，另一種是深度優(yōu)先(depth_first)。－－實現(xiàn)這兩種策略所依賴的數(shù)據(jù)結(jié)構(gòu)正好是前面介紹的隊列和棧。本節(jié)討論隊列的應(yīng)用，所以下面重點介紹廣度優(yōu)先的策略。4.6隊列的應(yīng)用—農(nóng)夫過河問題*45模擬農(nóng)夫過河問題：用四位二進(jìn)制數(shù)分別順序表示農(nóng)夫、狼、白菜和羊的位置。

0表示在南岸，1表示在北岸Path：15，6，14，2，11，1，9，0從初始狀態(tài)0到最終狀態(tài)15的動作序列為：

隊列的應(yīng)用

－－醫(yī)院門診部病人管理系統(tǒng)工作過程：當(dāng)一病人進(jìn)入門診室時，負(fù)責(zé)掛號的義務(wù)人員就根據(jù)觀察和簡短詢問發(fā)給他一個從0（病危）到4（一般）變化的優(yōu)先數(shù)，讓他到相應(yīng)優(yōu)先數(shù)隊列中去排隊等待。當(dāng)一醫(yī)生空閑時，就根據(jù)優(yōu)先數(shù)和等待時間，通知某候診病人就診。原則：優(yōu)先級高的先考慮，同一優(yōu)先級中，則先來先考慮。47隊列的應(yīng)用

－－醫(yī)院門診部病人管理系統(tǒng)組織數(shù)據(jù)的方式－－數(shù)據(jù)結(jié)構(gòu)分析：

系統(tǒng)中的數(shù)據(jù)：病人的姓名，優(yōu)先數(shù)，到達(dá)時間

48隊列的應(yīng)用

－－醫(yī)院門診部病人管理系統(tǒng)組織方式一：若病人以其到達(dá)門診部的先后次序組織到一個隊列，則具體到達(dá)時間可不考慮。到達(dá)次序優(yōu)先數(shù)姓名12345672303021林文鄭江魯明陳真李軍王紅張兵這樣的單隊列對按就診原則來確定下一就診病人是很不方便的，還將破壞隊列的操作原則。49隊列的應(yīng)用

－－醫(yī)院門診部病人管理系統(tǒng)組織方式二：多個隊列（隊列數(shù)組）：隊列數(shù)組的第i個元素是優(yōu)先級為i的隊列。優(yōu)先數(shù)隱含在隊列的編號中。魯明01234李軍張兵林文王紅鄭江陳真^^^^^50隊列的應(yīng)用

－－醫(yī)院門診部病人管理系統(tǒng)就病人管理系統(tǒng)來說，功能菜單中至少有以下兩個功能： （1）病人登記AddPatient()①提示并讀入病人優(yōu)先數(shù)i；

②提示并讀入病人名

③調(diào)用鏈隊列的入隊算法EnQueue()

（2）確定下一個就診病人GetPatient()

按就診原則確定和顯示下一個就診病人名即：若優(yōu)先數(shù)0的隊列非空，則下一就診病人為隊首元素，否則，考慮優(yōu)先數(shù)1的隊列；依次類推。

51線性表存儲結(jié)構(gòu)

運(yùn)算

隊列鏈表順序表

棧

順序棧

鏈棧

順序隊列

鏈隊列

線性表小結(jié)52順序表typedef

int

datatype;#defineMAXNUM1024typedef

struct{datatypedata[MAXNUM];intlast;}sequenlist;53鏈表typedef

int

datatype;typedef

structnode{datatypedata;structnode*next;}linklist;linklist*head,*p;54

順序棧

typedef

int

datatype;#defineMAXNUM64typedef

struct{datatypedata[MAXNUM];

inttop;}PSeqStack;PSeqStack*s;55

鏈棧

typedef

int

datatype;typedef

structnode{datatypedata;

structnode*next;}linkstack;linkstack*top;56

順序隊列

typedef

struct{datatypedata[MAXNUM];

intf,r;}sequeue;sequeue*sq;57

鏈隊列

typedef

struct{linklist*f,*r;}linkqueue;linkqueue*q;582.6設(shè)計一算法，逆置帶頭結(jié)點的動態(tài)單鏈表L。voidreverse(linklist*L)/*假設(shè)鏈表帶有頭結(jié)點*/{linklist*p,*s;p=L->next;/*用p指向當(dāng)前結(jié)點*/

L->next=NULL;while(p){s=p;/*用s保存當(dāng)前結(jié)點地址*/

p=p->next;/*鏈表指針p后移*//*將當(dāng)前結(jié)點鏈到表頭*/

s->next=L->next;L->next=s;}}/*reverse*/

592.10已知，由單鏈表表示的線性表中，含有三類字符的數(shù)據(jù)元素（如：字母字符、數(shù)字字符和其它字符），試編寫算法構(gòu)造三個以循環(huán)鏈表表示的線性表，使每個表中只含同一類的字符，且利用原表中的結(jié)點空間作為這三個表的結(jié)點空間，頭結(jié)點可另辟空間。linklist*ra,*rb,*rc;voidsort(linklist*head){linklist*s,*p=head;

/*建立三個空的循環(huán)鏈表*/

ra=malloc(sizeof(linklist));ra->next=ra;

rb=malloc(sizeof(linklist));rb->next=rb;

rc=malloc(sizeof(linklist));rc->next=ra;60while(p){s=p;p=p->next;

if((s->data>=‘0’)&&(s->data<=‘9’)){s->next=ra->next;ra->next=s;

ra=s;}

/*將數(shù)字字符結(jié)點鏈接到A表*/

elseif((s->data>=‘a(chǎn)’)&&(s->data<=‘z’)||(s->data>=‘A’)&&(s->data<=‘Z’)){s->next=rb->next;rb->next=s;

rb=s;}

/*將字母字符結(jié)點鏈接到B表*/

else{s->next=rc->next;rc->next=s;

rc=s;}

/*將其它字符結(jié)點鏈接到C表*/

}/*while*/}/*sort*/613.3設(shè)單鏈表中存放著n個字符，試編寫算法，判斷該字符串是否有中心對稱關(guān)系。要求用盡可能少的時間完成。intJudgement1(linklist*head)/*若對稱返回1，否則返回0*/{PSeqStack*s;

linklist*p;

inti,n=0;/*n為計數(shù)器，記錄鏈表的長度*/p=head;

/*先用循環(huán)求出鏈表的長度*/while(p){n++;p=p->next;}623.3設(shè)單鏈表中存放著n個字符，試編寫算法，判斷該字符串是否有中心對稱關(guān)系。要求用盡可能少的時間完成。SETNULL(s);/*設(shè)置空棧s*/p=head;/*先將一半字符進(jìn)棧*for(i=1;i<=n/2;i++){PUSH(s,p->data);p=p->next;}/*若字符個數(shù)為基數(shù)，則跳過中間的字符*if(n%2)p=p->next;633.3設(shè)單鏈表中存放著n個字符，試編寫算法，判斷該字符串是否有中心對稱關(guān)系。要求用盡可能少的時間完成。/*當(dāng)字符串未掃描完畢且棧非空時進(jìn)行匹配*/while(p&&!EMPTY(s))if(p->data!=POP(s)break;elsep=p->next;if(!p&&EMPTY(s))return1;elsereturn0;}/*Judgement*/643.4設(shè)計算法判斷一個算術(shù)表達(dá)式的圓括號是否正確配對Judgement2()

/*判斷表達(dá)式是否配對，表達(dá)式以‘#’結(jié)束*/{PSeqStack

sta;charch,chpop;

intvalid;

SETNULL(&sta);

PUSH(&sta,‘#’);/*把’#’放在棧底*/

ch=getchar();valid=TRUE;

/*valid為FALSE表示括號配對失敗*/65

while(ch!=‘#’){if(ch==‘(’)/*讀入字符為左括號時進(jìn)棧*/PUSH（&sta,ch）；

elseif(ch==‘)’)/*讀入字符為右括號時出棧*/{chpop=POP(&sta);if(chpop==‘#’)/*右括號多于左括號*/{valid=FALSE;break;}}/*else*/

ch=getchar();/*讀入下一字符*/}/*while*/

3.4設(shè)計算法判斷一個算術(shù)表達(dá)式的圓括號是否正確配對66if(POP(&sta)!=‘#’）

valid=FALSE;/*左括號多于右括號*/if(valid)

print