C語(yǔ)言基礎(chǔ)課件1第3章 隊(duì)列

隊(duì)列元素之間是一對(duì)一的關(guān)系順序隊(duì)列和鏈隊(duì)列隊(duì)尾入隊(duì)、隊(duì)頭出隊(duì)，遵循先進(jìn)先出（FIFO）的原則存儲(chǔ)結(jié)構(gòu)運(yùn)算規(guī)則邏輯結(jié)構(gòu)只能在表的一端進(jìn)行插入，在表的另一端進(jìn)行刪除的線性表基本操作

入隊(duì)、出隊(duì)、建空隊(duì)列、判隊(duì)空或隊(duì)滿尾部插入頭部刪除隊(duì)列定義隊(duì)列隊(duì)列Q=(a1

,a2,a3,……….,an-1,an

)在隊(duì)尾插入元素稱為入隊(duì)在隊(duì)首刪除元素稱為出隊(duì)隊(duì)首隊(duì)尾cb尾指針頭指針隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)隊(duì)列的順序存儲(chǔ)，稱為順序隊(duì)列由一個(gè)存放隊(duì)列元素的一維數(shù)組，和隊(duì)頭、隊(duì)尾“指針”組成順序隊(duì)列類型定義#definemaxsize100typedefstruct{elemtypev[maxsize];intfront,rear;}squeuetp；squeuetp*sq;sq=(squeuetp*)malloc(sizeof(squeuetp));123450front入隊(duì)J1J2J3rearrear入隊(duì)J4J5J6front初值:sq->front=sq->rear=-1rear:指示當(dāng)前隊(duì)尾元素front:指示隊(duì)頭元素的前一位置空隊(duì)列：sq->front==sq->rearrearrearfrontrear123450出隊(duì)J1J2J3frontfrontfront順序隊(duì)列的幾種狀態(tài)入隊(duì)：sq->v[++(sq->rear)]=x出隊(duì)：x=sq->v[++(sq->front)]假上溢！123450frontrear0M-11frontrear…...…...循環(huán)隊(duì)列的引入循環(huán)隊(duì)列把隊(duì)列設(shè)想成環(huán)形若rear+1==M,則令rear=0;實(shí)現(xiàn)：利用“模”運(yùn)算入隊(duì)：rear=(rear+1)%M;sq[rear]=x;出隊(duì)：front=(front+1)%M;x=sq[front];新問(wèn)題：隊(duì)滿、隊(duì)空的判定條件是什么？012345rearfrontJ4J5J6012345rearfrontJ3J2J1J4J5J6012345rearfront初始狀態(tài)J4,J5,J6出隊(duì)J1,J2,J3入隊(duì)隊(duì)空：front==rear隊(duì)滿：front==rear解決方案：少用一個(gè)元素空間隊(duì)空：front==rear

隊(duì)滿：(rear+1)%M==front在循環(huán)隊(duì)列上實(shí)現(xiàn)的操作用C語(yǔ)言描述循環(huán)隊(duì)列：#definem100//隊(duì)列可能的最大長(zhǎng)度

#defineMAXSIZEm+1typedofstruct{elemtypev[MAXSIZE];intfront,rear;}cqueuetp;cqueuetp*initqueue(){cqueuetp*q；

q=(cqueuetp*)malloc(sizeof(cqueuetp))；

//將隊(duì)列頭尾指針置為零

q->front=q->rear=0；

returnq；}循環(huán)隊(duì)列初始化voidmain(){

cqueuetp*q;q=initqueue();……}#defineMAXSIZE101typedofstruct{elemtypev[MAXSIZE];intfront,rear;}cqueuetp;cqueuetp*initqueue()；入隊(duì)：向循環(huán)隊(duì)列的隊(duì)尾插入一個(gè)元素算法思想先判隊(duì)列是否滿

if((q->rear+1)%MAXSIZE)==q->front)入隊(duì)動(dòng)作q->rear=(q->rear+1)%MAXSIZE;q->v[q->rear]=x;循環(huán)隊(duì)列入隊(duì)操作intenqueue(cqueuetp*q,elemtypex)；intenqueue(cqueuetp*q,elemtypex){if((q->rear+1)％MAXSIZE==q->front)

{printf(“循環(huán)隊(duì)列滿!\n”);

return0;}

q->rear=(q->rear+1)%MAXSIZE;q->v[q->rear]=x；

return1;}voidmain(){cqueuetp*q;q=initqueue();enqueue(q,10);}循環(huán)隊(duì)列入隊(duì)操作循環(huán)隊(duì)列出隊(duì)操作算法刪除循環(huán)隊(duì)列的隊(duì)頭元素，返回其值x算法思想在出隊(duì)前判隊(duì)列是否為空if(q->front==q->rear)

出隊(duì)動(dòng)作:q->front=(q->front+1)%MAXSIZE;x=q->v[q->front];voidmain(){cqueuetp*q;q=initqueue();enqueue(q,10);printf(“%d”,dequeue(q));}elemtypedequeue(cqueuetp*q);elemtypedequeue(cqueuetp*q){elemtypex;

if(q->front==q->rear){ printf(“循環(huán)隊(duì)列空！\n”);return0;}

q->front=(q->front+1)％MAXSIZE；

x=q->elem[q->front]；

returnx；}循環(huán)隊(duì)列出隊(duì)操作隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)鏈隊(duì)列隊(duì)列的鏈?zhǔn)酱鎯?chǔ)是單鏈表,同時(shí)帶有頭指針和尾指針頭指針指向隊(duì)頭結(jié)點(diǎn)尾指針指向隊(duì)尾結(jié)點(diǎn)頭結(jié)點(diǎn)^…...front隊(duì)頭隊(duì)尾rear設(shè)隊(duì)首、隊(duì)尾指針front和rear,front指向隊(duì)頭，rear指向隊(duì)尾鏈隊(duì)列類型定義：

typedefstruct{QNODE*front;//隊(duì)頭指針

QNODE*rear;//隊(duì)尾指針

}linkqueue;

linkqueue*q;

//q指針,封裝了隊(duì)頭指針和隊(duì)尾指針

q=(linkqueue*)malloc(sizeof(linkqueue));

q->front=?q->rear=?鏈隊(duì)列結(jié)點(diǎn)類型定義：

typedefstructnode{datatypedata;structnode*next;}QNODE;

①鏈隊(duì)列為空的特征：q->front==q->rear②鏈隊(duì)列會(huì)滿嗎？修改rear指針q->front==q->rear修改頭結(jié)點(diǎn)的指針域鏈隊(duì)列的幾種狀態(tài)修改q->rearlinkqueue*initqueue()

{

linkqueue*q;//鏈隊(duì)列指針,封裝了隊(duì)頭和隊(duì)尾指針

QNODE*p;//p為指向鏈隊(duì)列結(jié)點(diǎn)的指針

q=(linkqueue*)malloc(sizeof(linkqueue));

p=(QNODE*)malloc(sizeof(QNODE));

//生成頭結(jié)點(diǎn)

p->next=NULL;//頭結(jié)點(diǎn)指針域?yàn)榭?，空?duì)列

q->front=q->rear=p;//隊(duì)頭隊(duì)尾指針都指向頭結(jié)點(diǎn)

returnq;//注意，指針q中封裝了隊(duì)頭和隊(duì)尾指針

}構(gòu)造一個(gè)帶頭結(jié)點(diǎn)的空鏈隊(duì)列voidmain(){linkqueue*q;q=initqueue();}voidenqueue(linkqueue*q，datatypex)

{

QNODE*p;

//p為指向鏈隊(duì)列結(jié)點(diǎn)的指針

p=(QNODE*)malloc(sizeof(QNODE))；

p->data=x；

p->next=NULL；

q->rear->next=p；

//修改隊(duì)尾指針

q->rear=p；

}鏈隊(duì)列的入隊(duì)操作voidmain(){linkqueue*q;q=initqueue();enqueue(q,10);}刪除隊(duì)頭元素，返回其值x算法思想出隊(duì)前判隊(duì)列是否為空？if(q->front==q->rear)出隊(duì)動(dòng)作如下:p=q->front->next;x=p->data;修改隊(duì)頭指針:q->front->next=p->next注意：如果隊(duì)列中只有一個(gè)結(jié)點(diǎn)，刪除后還要修改隊(duì)尾指針，令鏈表為空鏈隊(duì)列的出隊(duì)操作voidmain(){linkqueue*q;q=initqueue();enqueue(q,10);dequeue(q);}datatypedequeue(linkqueue*q){QNODE*p;

//p為指向鏈隊(duì)列結(jié)點(diǎn)的指針

datatypex;

if(q->front==q->rear){printf("隊(duì)列為空,無(wú)法刪除!");return0;}

else{p=q->front->next；//p指向隊(duì)頭結(jié)點(diǎn)

x=p->data；//將隊(duì)頭元素的值賦給x

q->front->next=p->next；

//出隊(duì)

if(p->next==NULL)q->rear=q->front；

//若出隊(duì)列后隊(duì)列為空，則修改隊(duì)尾指針

free(p)；

returnx;}}datatypegethead(linkqueue*q){if(q->front==q->rear){printf(“\n鏈隊(duì)列為空!”);return0;}else

return(q->front->next->data)；

}取鏈隊(duì)列的隊(duì)頭元素datatypegethead(linkqueue*q)；在鏈隊(duì)列上操作的注意事項(xiàng)是否需要考慮隊(duì)滿？出隊(duì)時(shí)，若原隊(duì)中只有一個(gè)結(jié)點(diǎn)，該結(jié)點(diǎn)既是隊(duì)頭也是隊(duì)尾則刪去此結(jié)點(diǎn)時(shí)還需修改尾指針刪去此結(jié)點(diǎn)后隊(duì)列變空隊(duì)列的長(zhǎng)度變化一般比較大多采用鏈?zhǔn)酱鎯?chǔ)隊(duì)列的應(yīng)用——舞伴問(wèn)題先入隊(duì)的男士或女士先出隊(duì)配成舞伴可用隊(duì)列作為算法的數(shù)據(jù)結(jié)構(gòu)算法中，假設(shè)男士和女士的記錄存放在一個(gè)數(shù)組中作為輸入，然后依次掃描該數(shù)組的各元素，并根據(jù)性別來(lái)決定是進(jìn)入男隊(duì)還是女隊(duì)。這兩個(gè)隊(duì)列構(gòu)造完成之后，依次將兩隊(duì)當(dāng)前的隊(duì)頭元素出隊(duì)來(lái)配成舞伴，直至某隊(duì)列變空為止。此時(shí)，若某隊(duì)仍有等待配對(duì)者，算法輸出此隊(duì)列中等待者的人數(shù)及排在隊(duì)頭的等待者的名字，他（或她）將是下一輪舞曲開(kāi)始時(shí)第一個(gè)可獲得舞伴的人。

隊(duì)列的應(yīng)用—門(mén)診看病問(wèn)題門(mén)診在醫(yī)院門(mén)診某診室看病的時(shí)候,護(hù)士給每位病人一個(gè)編號(hào)病人按編號(hào)進(jìn)行排隊(duì)一個(gè)病人看完后,護(hù)士安排下一個(gè)病人看病編程:對(duì)此過(guò)程進(jìn)行模擬隊(duì)列的應(yīng)用--劃分子集問(wèn)題問(wèn)題描述已知集合A={a1,a2,……an}，及集合上的關(guān)系R={(ai,aj)|ai,aj

A,ij}其中(ai,aj)表示ai與aj間存在沖突關(guān)系要求將A劃分成互不相交的子集A1,A2,……Ak,(kn)使任何子集中的元素均無(wú)沖突關(guān)系，同時(shí)要求分子集個(gè)數(shù)盡可能少隊(duì)列的應(yīng)用--劃分子集問(wèn)題A={1,2,3,4,5,6,7,8,9}R={(2,8),(9,4),(2,9),(2,1),(2,5),(6,2),(5,9),(5,6),(5,4),(7,5),(7,6),(3,7),(6,3)}可行的子集劃分為：

A1={1,3,4,8}A2={2,7}A3={5}A4={6,9}隊(duì)列的應(yīng)用--劃分子集問(wèn)題算法思想利用循環(huán)篩選從第一個(gè)元素開(kāi)始，凡與第一個(gè)元素?zé)o沖突的元素劃歸一組再將剩下的元素重新找出互不沖突的劃歸第二組直到所有元素進(jìn)組隊(duì)列的應(yīng)用--劃分子集問(wèn)題所用數(shù)據(jù)結(jié)構(gòu)沖突關(guān)系矩陣r[i][j]=1,i,j有沖突r[i][j]=0,i,j無(wú)沖突循環(huán)隊(duì)列cq[n]數(shù)組result[n]存放每個(gè)元素分組號(hào)工作數(shù)組newr[n]劃分子集問(wèn)題-算法描述初始狀態(tài)：A中元素放于cq中，result和newr數(shù)組清零，組號(hào)group=1第一個(gè)元素出隊(duì)，將r矩陣中第一行“1”拷入newr中對(duì)應(yīng)位置，這樣，凡與第一個(gè)元素有沖突的元素在newr中對(duì)應(yīng)位置處均為“1”下一個(gè)元素出隊(duì)若其在newr中對(duì)應(yīng)位置為“1”，有沖突，重新插入cq隊(duì)尾，參加下一次分組若其在newr中對(duì)應(yīng)位置為“0”,無(wú)沖突，可劃歸本組；再將r矩陣中該元素對(duì)應(yīng)行中的“1”拷入newr中如此反復(fù)，直到所有元素依次出隊(duì)由newr中為“0”的單元對(duì)應(yīng)的元素構(gòu)成第1組,將組號(hào)group值“1”寫(xiě)入result對(duì)應(yīng)單元中令group=2,newr清零，對(duì)cq中元素重復(fù)上述操作，直到cq中front==rear,即隊(duì)空，運(yùn)算結(jié)束劃分子集問(wèn)題-算法描述123456789012345678cqfr000000000012345678newr000000000012345678result初始R={(2,8),(9,4),(2,9),(2,1),(2,5),(6,2),(5,9),(5,6),(5,4),(7,5),(7,6),(3,7),(6,3)}010000000010110000000001100000010001010101101011010100001011000010000000100011011R=23456789012345678cqfr010000000012345678newr100000000012345678resultR={(2,8),(9,4),(2,9),(2,1),(2,5),(6,2),(5,9),(5,6),(5,4),(7,5),(7,6),(3,7),(6,3)}010000000010110000000001100000010001010101101011010100001011000010000000100011011R=

23456789012345678cqfr010000000012345678newr100000000012345678resultR={(2,8),(9,4),(2,9),(2,1),(2,5),(6,2),(5,9),(5,6),(5,4),(7,5),(7,6),(3,7),(6,3)}010000000010110000000001100000010001010101101011010100001011000010000000100011011R=

2456789012345678cqfr010001

100012345678newr101000000012345678resultR={(2,8),(9,4),(2,9),(2,1),(2,5),(6,2),(5,9),(5,6),(5,4),(7,5),(7,6),(3,7),(6,3)}010000000010110000000001100000010001010101101011010100001011000010000000100011011R=

256789012345678cqfr01001

1

101012345678newr101

100000012345678resultR={(2,8),(9,4),(2,9),(2,1),(2,5),(6,2),(5,9),(5,6),(5,4),(7,5),(7,6),(3,7),(6,3)}010000000010110000000001100000010001010101101011010100001011000010000000100011011R=

2

56789012345678cqfr01001

1

101012345678newr101

100000012345678resultR={(2,8),(9,4),(2,9),(2,1),(2,5),(6,2),(5,9),(5,6),(5,4),(7,5),(7,6),(3,7),(6,3)}010000000010110000000001100000010001010101101011010100001011000010000000100011011R=

2

5

6789012345678cqfr01001

1

101012345678newr101

100000012345678resultR={(2,8),(9,4),(2,9),(2,1),(2,5),(6,2),(5,9),(5,6),(5,4),(7,5),(7,6),(3,7),(6,3)}010000000010110000000001100000010001010101101011010100001011000010000000100011011R=

2

5

6

789012345678cqfr01001

1

101012345678newr101

100000012345678resultR={(2,8),(9,4),(2,9),(2,1),(2,5),(6,2),(5,9),(5,6),(5,4),(7,5),(7,6),(3,7),(6,3)}010000000010110000000001100000010001010101101011010100001011000010000000100011011R=

2

56

79012345678cqfr01001

1

101012345678newr101

100010012345678resultR={(2,8),(9,4),(2,9),(2,1),(2,5),(6,2),(5,9),(5,6),(5,4),(7,5),(7,6),(3,7),(6,3)}010000000010110000000001100000010001010101101011010100001011000010000000100011011R=

25679012345678cqfr01001

1

101012345678newr101

100010012345678resultR={(2,8),(9,4),(2,9),(2,1),(2,5),(6,2),(5,9),(5,6),(5,4),(7,5),(7,6),(3,7),(6,3)}010000000010110000000001100000010001010101101011010100001011000010000000100011011R=

5679012345678cqfr10001

101

1012345678newr1

2

1

100010012345678resultR={(2,8),(9,4),(2,9),(2,1),(2,5),(6,2),(5,9),(5,6),(5,4),(7,5),(7,6),(3,7),(6,3)}010000000010110000000001100000010001010101101011010100001011000010000000100011011R=

679

5012345678cqfr10001

101

1012345678newr1

2

1

100010012345678resultR={(2,8),(9,4),(2,9),(2,1),(2,5),(6,2),(5,9),(5,6),(5,4),(7,5),(7,6),(3,7),(6,3)}010000000010110000000001100000010001010101101011010100001011000010000000100011011R=

79

56012345678cqfr10001

101

1012345678newr1

2

1

100010012345678resultR={(2,8),(9,4),(2,9),(2,1),(2,5),(6,2),(5,9),(5,6),(5,4),(7,5),(7,6),(3,7),(6,3)}010000000010110000000001100000010001010101101011010100001011000010000000100011011R=

9

56012345678cqfr10101

101

1012345678newr1

2

1

1002

10012345678resultR={(2,8),(9,4),(2,9),(2,1),(2,5),(6,2),(5,9),(5,6),(5,4),(7,5),(7,6),(3,7),(6,3)}010000000010110000000001100000010001010101101011010100001011000010000000100011011R=

569012345678cqfr10101

101

1012345678newr1

2

1

1002

10012345678resultR={(2,8),(9,4),(2,9),(2,1),(2,5),(6,2),(5,9),(5,6),(5,4),(7,5),(7,6),(3,7),(6,3)}010000000010110000000001100000010001010101101011010100001011000010000000100011011R=

69012345678cqfr010101

101012345678newr1

2

1

1

302

10012345678resultR={(2,8),(9,4),(2,9),(2,1),(2,5),(6,2),(5,9),(5,6),(5,4),(7,5),(7,6),(3,7),(6,3)}010000000010110000000001100000010001010101101011010100001011000010000000100011011R=

96012345678cqfr010101

101012345678newr1

2

1

1

302

10012345678resultR={(2,8),(9,4),(2,9),(2,1),(2,5),(6,2),(5,9),(5,6),(5,4),(7,5),(7,6),(3,7),(6,3)}010000000010110000000001100000010001010101101011010100001011000010000000100011011R=

9

6012345678cqfr010101

101012345678newr1

2

1

1

302

100123