C語言基礎課件1第3章隊列

上傳人：1*** IP屬地：廣東上傳時間：2023-11-17 格式：PPT 頁數(shù)：52 大小：1.57MB 積分：15 舉報 版權申訴

已閱讀5頁，還剩47頁未讀，繼續(xù)免費閱讀

版權說明：本文檔由用戶提供并上傳，收益歸屬內容提供方，若內容存在侵權，請進行舉報或認領

文檔簡介

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

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

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

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

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

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

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

//將隊列頭尾指針置為零

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

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

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

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

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

return0;}

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

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

出隊動作: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)隊列空！\n”);return0;}

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

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

returnx；}循環(huán)隊列出隊操作隊列的鏈式存儲結構鏈隊列隊列的鏈式存儲是單鏈表,同時帶有頭指針和尾指針頭指針指向隊頭結點尾指針指向隊尾結點頭結點^…...front隊頭隊尾rear設隊首、隊尾指針front和rear,front指向隊頭，rear指向隊尾鏈隊列類型定義：

typedefstruct{QNODE*front;//隊頭指針

QNODE*rear;//隊尾指針

}linkqueue;

linkqueue*q;

//q指針,封裝了隊頭指針和隊尾指針

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

q->front=?q->rear=?鏈隊列結點類型定義：

typedefstructnode{datatypedata;structnode*next;}QNODE;

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

{

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

QNODE*p;//p為指向鏈隊列結點的指針

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

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

//生成頭結點

p->next=NULL;//頭結點指針域為空，空隊列

q->front=q->rear=p;//隊頭隊尾指針都指向頭結點

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

}構造一個帶頭結點的空鏈隊列voidmain(){linkqueue*q;q=initqueue();}voidenqueue(linkqueue*q，datatypex)

{

QNODE*p;

//p為指向鏈隊列結點的指針

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

p->data=x；

p->next=NULL；

q->rear->next=p；

//修改隊尾指針

q->rear=p；

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

//p為指向鏈隊列結點的指針

datatypex;

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

else{p=q->front->next；//p指向隊頭結點

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

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

//出隊

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

//若出隊列后隊列為空，則修改隊尾指針

free(p)；

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

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

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

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

A,ij}其中(ai,aj)表示ai與aj間存在沖突關系要求將A劃分成互不相交的子集A1,A2,……Ak,(kn)使任何子集中的元素均無沖突關系，同時要求分子集個數(shù)盡可能少隊列的應用--劃分子集問題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}隊列的應用--劃分子集問題算法思想利用循環(huán)篩選從第一個元素開始，凡與第一個元素無沖突的元素劃歸一組再將剩下的元素重新找出互不沖突的劃歸第二組直到所有元素進組隊列的應用--劃分子集問題所用數(shù)據(jù)結構沖突關系矩陣r[i][j]=1,i,j有沖突r[i][j]=0,i,j無沖突循環(huán)隊列cq[n]數(shù)組result[n]存放每個元素分組號工作數(shù)組newr[n]劃分子集問題-算法描述初始狀態(tài)：A中元素放于cq中，result和newr數(shù)組清零，組號group=1第一個元素出隊，將r矩陣中第一行“1”拷入newr中對應位置，這樣，凡與第一個元素有沖突的元素在newr中對應位置處均為“1”下一個元素出隊若其在newr中對應位置為“1”，有沖突，重新插入cq隊尾，參加下一次分組若其在newr中對應位置為“0”,無沖突，可劃歸本組；再將r矩陣中該元素對應行中的“1”拷入newr中如此反復，直到所有元素依次出隊由newr中為“0”的單元對應的元素構成第1組,將組號group值“1”寫入result對應單元中令group=2,newr清零，對cq中元素重復上述操作，直到cq中front==rear,即隊空，運算結束劃分子集問題-算法描述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

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=

56789012345678cqfr01001

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=

6789012345678cqfr01001

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=

789012345678cqfr01001

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=

79012345678cqfr01001

101012345678newr101