C語(yǔ)言隊(duì)列課件

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

a2

an

...

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

創(chuàng)建一個(gè)空隊(duì)列

QueuecreateEmptyQueue(void)

判隊(duì)列是否為空隊(duì)列

int

isEmptyQueue(Queuequ)

往隊(duì)列中插入一個(gè)元素

voidenQueue(Queuequ,DataTypex)

從隊(duì)列中刪除一個(gè)元素

voiddeQueue(Queuequ)

求隊(duì)列頭部元素的值

DataType

frontQueue(Queuequ)

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

隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)簡(jiǎn)稱(chēng)為順序隊(duì)列。順序隊(duì)列實(shí)際上是運(yùn)算受限的順序表。

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

SeqQueue{datatypeq[MAXNUM];

intf,r;};typedef

struct

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

sq->data[sq->r]=x;sq->r++;出隊(duì)：

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

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

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

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

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

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

sq->f=sq->r

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

sq->f=sq->r

因此，僅憑

sq->f=sq->r

是無(wú)法區(qū)別隊(duì)列空還是隊(duì)列滿。

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

判別隊(duì)列滿的條件：

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

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

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

1.置空隊(duì)

2.判隊(duì)空

3.取隊(duì)頭元素

4.入隊(duì)

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

rear指向元素要插入的位置，插入一個(gè)元素就將rear順時(shí)針移動(dòng)一位；

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

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

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

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

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

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

head=(head+1)%QUEUE_SIZE;

}

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

returntemp;

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

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

intIsFull(){

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

printf("隊(duì)列未滿\n");return0;}/打印出隊(duì)列元素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.置空隊(duì)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.判隊(duì)空int

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

303.取隊(duì)頭元素DataType

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

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

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

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

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

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

334.5.2鏈隊(duì)列

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

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

k0

k1

k2

kn-1….

圖4.10隊(duì)列的鏈接表示plqu

fr

structNode;

typedef

structNode*pNode;

structNode{DataTypeinfo;

pNode link;};

struct

LinkQueue{PNode f;

PNode r;};

typedef

struct

LinkQueue,*PLinkQueue;隊(duì)列的鏈接表示36

^

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

頭結(jié)點(diǎn)

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

^

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

1.置空隊(duì)

2.判隊(duì)空

3.取隊(duì)頭結(jié)點(diǎn)數(shù)據(jù)

4.入隊(duì)

5.出隊(duì)381.置空隊(duì)（算法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.判隊(duì)空（算法4.22）int

isEmptyQueue_link(PLinkQueue

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

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

frontQueue_link(PLinkQueue

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

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

414.入隊(duì)（算法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.出隊(duì)（算法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)夫過(guò)河問(wèn)題

:

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

4.6隊(duì)列的應(yīng)用—農(nóng)夫過(guò)河問(wèn)題*44

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

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

隊(duì)列的應(yīng)用

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

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

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

48隊(duì)列的應(yīng)用

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

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

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

②提示并讀入病人名

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

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

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

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

運(yùn)算

隊(duì)列鏈表順序表

棧

順序棧

鏈棧

順序隊(duì)列

鏈隊(duì)列

線性表小結(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

順序隊(duì)列

typedef

struct{datatypedata[MAXNUM];

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

鏈隊(duì)列

typedef

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

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

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

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

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

/*建立三個(gè)空的循環(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é)點(diǎn)鏈接到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é)點(diǎn)鏈接到B表*/

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

rc=s;}

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

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

linklist*p;

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

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

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

sta;charch,chpop;

intvalid;

SETNULL(&sta);

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

ch=getchar();valid=TRUE;

/*valid為FALSE表示括號(hào)配對(duì)失敗*/65

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

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

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

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

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

print