鏈?zhǔn)疥?duì)列及其應(yīng)用

數(shù)據(jù)結(jié)構(gòu)所有n只猴子站成一排，從排頭猴子開(kāi)始1,2,3報(bào)數(shù)。報(bào)數(shù)為1、2的猴子站回到排尾，報(bào)數(shù)為3的猴子退出，如此反復(fù)，直到剩下一個(gè)猴子為止，則剩下這個(gè)猴子即為猴王。猴子選大王

問(wèn)：假如猴子甲想當(dāng)猴王，它當(dāng)初應(yīng)站在什么位置？分析其實(shí)，猴子選大王的過(guò)程就是一個(gè)反復(fù)排隊(duì)的過(guò)程。本節(jié)，我們將定義一個(gè)新的數(shù)據(jù)結(jié)構(gòu)—隊(duì)列，來(lái)解決這個(gè)問(wèn)題。己欲立而立人，己欲達(dá)而達(dá)人——《論語(yǔ)》

3.4

鏈隊(duì)及其應(yīng)用我們可以抽象出排隊(duì)的數(shù)據(jù)特性——FIFO（firstinfirstout），(1)線性結(jié)構(gòu)，具有線性特征；(2)限制操作方式——只能從兩端進(jìn)行操作。具體表現(xiàn)如下：

把數(shù)據(jù)在數(shù)學(xué)邏輯上的先后相鄰關(guān)系用元素的存儲(chǔ)地址的指針(pointer)來(lái)指示，稱(chēng)之為鏈?zhǔn)酱鎯?chǔ)（linkedmapping）。鏈?zhǔn)酱鎯?chǔ)：S=(a1,a2,……,an)a1heada2/\an……限定只能在一端()進(jìn)行插入(入隊(duì))，而在另一端()進(jìn)行刪除(出隊(duì))的操作的線性表，稱(chēng)之為隊(duì)列(queue）。本節(jié)只討論鏈?zhǔn)疥?duì)列(簡(jiǎn)稱(chēng)鏈隊(duì))。a2a1headanai/\a1稱(chēng)為隊(duì)頭元素an稱(chēng)為隊(duì)尾元素頭結(jié)點(diǎn)結(jié)點(diǎn)3.4.1

鏈隊(duì)的定義隊(duì)尾隊(duì)頭……typedefstructnode

{intdata;structnode*next;}Qnode,*queueptr;typedefstruct{queueptrfront;

queueptrrear;}linkqueue;

結(jié)點(diǎn)定義鏈隊(duì)定義aifrontreara2a1headan…/\frontrear3.4.2

鏈隊(duì)的C語(yǔ)言描述入隊(duì)操作Q.frontQ.rearx元素入隊(duì)^xQ.rearQ.frontQ.rearx^yy元素入隊(duì)Q.rearPp->data=x;p->next=NULL;Q.rear->next=p;Q.rear=p;p->data=y;p->next=NULL;Q.rear->next=p;Q.rear=p;PLinkqueueQ;^^

3.4.3鏈隊(duì)的基本操作

queueptrP;linkqueueEnqueue(linkqueue&Q,QElemTypex){Queueptrp;p=(Queueptr)malloc(sizeof(queueNode));

if(!p)exit(OVERFLOW);p->data=x;p->next=NULL;

rear->next=p;rear=p;

return(ok);}入隊(duì)算法Q.frontQ.rearx^yx元素出隊(duì)

出隊(duì)操作Q.front->next=s->next;s=Q.front->next;Sfree(s);Q.frontQ.reary元素出隊(duì)^y^Q.rearQ.frontQ.rearx^ySQ.rear=Q.front;s=Q.front->next;free(s);Q.front->next=s->next;intdelqueue(linkqueue&Q,QElemTypee){QueueptrS;

if(front==rear)return(-1);

s=Q.front->next;e=p->data;

Q.

front->next=s->next;if(s->next==NULL)rear=front;

free(s);}出隊(duì)算法Q.frontQ.rear^Q.front==Q.rear(1)空鏈隊(duì)有何特征,如何描述？（2）鏈隊(duì)會(huì)滿(mǎn)嗎？答：一般不會(huì),因?yàn)閯h除時(shí)用free()函數(shù)釋放被刪除的結(jié)點(diǎn),除非內(nèi)存不足。思考針對(duì)本節(jié)剛開(kāi)始提出的問(wèn)題，設(shè)置一個(gè)鏈隊(duì)，算法分三步如下：

（1）將全體猴子編號(hào)排隊(duì)(編號(hào)入隊(duì));

（2）從隊(duì)頭開(kāi)始報(bào)數(shù)，報(bào)1,2的猴子出隊(duì)，重新從隊(duì)尾入隊(duì),報(bào)3的猴子出局;（3）重復(fù)（2),這樣隊(duì)列中的猴子越來(lái)越少，直至最后一個(gè)猴子即為所選猴王。3.4.4

鏈隊(duì)?wèi)?yīng)用舉例frontrear???123frontfrontrearrearfront如此反復(fù)出隊(duì)入隊(duì)，直到隊(duì)中剩余一個(gè)猴子為止,即為所選猴王。假如有20只猴子，則站在隊(duì)列中第8位的猴子為所選猴王。#include<stdio.h>#include<malloc.h>#defineMAXSIZE100typedefstruct

{intelem[MAXSIZE];intfront;intrear;}Quque;預(yù)處理voidinitQue(Quque**q)//初始化intisFull(Quque*q)//判斷隊(duì)滿(mǎn)intinsertQue(Quque**q,intelem)//入隊(duì)

intisEmpty(Quque*q)//判斷隊(duì)空intdeleteQue(Quque**q,int*pelem)//出隊(duì)

voidmain(){intk=1,elem=0;intn=8;inti=4;intm=1;intj=1;intA[8]={0};inte=2;intak=0;Quque*q=(Quque*)malloc(sizeof(Quque));initQue(&q);鏈隊(duì)的基本操作聲明

for(k=1;k<=n;k++)insertQue(&q,k);

for(k=1;k<=n;k++)

{deleteQue(&q,&elem);printf("%d",elem);insertQue(&q,elem);}for(k=0;k<i;k++){deleteQue(&q,&e);

insertQue(&q,e);}生成鏈隊(duì)

while(!isEmpty(q)){for(j=0;j<=m;j++)

{deleteQue(&q,&e);insertQue(&q,e);}deleteQue(&q,&e);A[ak++]=e;}for(k=0;k<n;k++)//輸出

{printf("%d",*(A+k));}開(kāi)始選舉得出結(jié)果《DataStructuresandAlgorithmAnalysisinC》

---MarkAllenWeiss

MarkAllenWeiss，1987年在普林斯頓大學(xué)獲得計(jì)算機(jī)科學(xué)博士學(xué)位，師從RobertSedgewick，現(xiàn)任美國(guó)佛羅里達(dá)國(guó)際大學(xué)計(jì)算與信息科學(xué)學(xué)院教授。曾經(jīng)擔(dān)任全美計(jì)算機(jī)學(xué)科考試委員會(huì)主席。所著書(shū)籍深入淺出，暢銷(xiāo)北美乃至世界。由古羅馬的史學(xué)家約瑟夫（Josephus）提出，他參加并記錄了公元66—70年猶太人反抗羅馬的起義。約瑟夫作為將軍，在城市淪陷之后，他的40名不屈的將士大義凜然的說(shuō)“要投降毋寧死”。但是又難以下手，約瑟夫建議用課前提出的辦法，報(bào)數(shù)殺人，報(bào)到約定數(shù)字的將士，