第12章 結(jié)構(gòu)設(shè)計(jì)之美

第11章算法和數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)——結(jié)構(gòu)設(shè)計(jì)之美哈爾濱工業(yè)大學(xué)12.1從定長(zhǎng)數(shù)組到動(dòng)態(tài)數(shù)組本節(jié)主要討論如下問題：（1）什么是動(dòng)態(tài)內(nèi)存分配？如何進(jìn)行動(dòng)態(tài)內(nèi)存分配？（2）常見的內(nèi)存錯(cuò)誤有哪些？如何避免這些內(nèi)存錯(cuò)誤？12.1.1動(dòng)態(tài)內(nèi)存分配C程序中變量的內(nèi)存分配方式有以下3種：（1）從靜態(tài)存儲(chǔ)區(qū)分配（2）在棧上分配（3）從堆上分配1.函數(shù)malloc()函數(shù)malloc()的原型為：void*malloc(unsignedintsize);2.函數(shù)calloc()函數(shù)calloc()的函數(shù)原型為：void*calloc(unsignedintnum,unsignedintsize);3.函數(shù)free()函數(shù)free()的函數(shù)原型為：voidfree(void*p);4.函數(shù)realloc()函數(shù)realloc()的函數(shù)原型為：void*realloc(void*p,unsignedintsize);12.1.1動(dòng)態(tài)內(nèi)存分配void*型指針不指定其指向變量的類型，可指向任意類型的變量是一種generic（通用）或typeless（無類型）的指針

使用時(shí)，需強(qiáng)轉(zhuǎn)(Type*)為其他類型12.1.1動(dòng)態(tài)內(nèi)存分配void*

malloc(unsignedintsize);向系統(tǒng)申請(qǐng)size字節(jié)的連續(xù)內(nèi)存塊，系統(tǒng)找到一塊未占用的內(nèi)存，將其標(biāo)記為已占用，把首地址返回p=(float*)malloc(n*sizeof(float));free(p);//釋放p指向的內(nèi)存頻繁申請(qǐng)/釋放，速度慢，易造成內(nèi)存碎片程序員不釋放內(nèi)存泄漏釋放仍繼續(xù)使用野指針空指針的用途

定義指針時(shí)進(jìn)行初始化在程序中常用作狀態(tài)比較指針不能與非指針類型變量進(jìn)行比較但可與NULL（即0值）進(jìn)行相等或不等的關(guān)系運(yùn)算

p=(int*)malloc(n*sizeof(int));if(p==NULL)//判斷內(nèi)存申請(qǐng)是否成功{printf("Noenoughmemory!\n");exit(0);}int*p;Heap（堆區(qū)）若申請(qǐng)不成功則返回NULL12.1.1動(dòng)態(tài)內(nèi)存分配【例12.1】請(qǐng)編寫一個(gè)點(diǎn)名神器，從文件中讀取學(xué)生名單，每按一次回車鍵，就從學(xué)生名單中隨機(jī)抽取1個(gè)學(xué)生，直到按ESC鍵或者學(xué)生名單中的學(xué)生全部抽完為止，要求每個(gè)學(xué)生最多只能被抽中一次，即不能被重復(fù)點(diǎn)到名字。#include<stdio.h>#include<conio.h>#include<stdlib.h>#include<time.h>#defineNO120#defineSIZE30typedefstruct{charname[SIZE];

shortflag;//標(biāo)記是否被點(diǎn)過名}ROLL;intReadFromFile(charfileName[],ROLLmsg[]);voidMakeRollCall(ROLLmsg[],inttotal);intmain(void){ROLLmsg[NO];//定長(zhǎng)數(shù)組

char*fileName="student.txt";inttotal=ReadFromFile(fileName,msg);printf("總計(jì)%d名學(xué)生\n現(xiàn)在開始隨機(jī)點(diǎn)名\n",total);MakeRollCall(msg,total);//隨機(jī)點(diǎn)名

return0;}12.1.2動(dòng)態(tài)數(shù)組實(shí)例——隨機(jī)點(diǎn)名使用定長(zhǎng)的結(jié)構(gòu)體數(shù)組來實(shí)現(xiàn)點(diǎn)名神器【例12.1】請(qǐng)編寫一個(gè)點(diǎn)名神器，從文件中讀取學(xué)生名單，每按一次回車鍵，就從學(xué)生名單中隨機(jī)抽取1個(gè)學(xué)生，直到按ESC鍵或者學(xué)生名單中的學(xué)生全部抽完為止，要求每個(gè)學(xué)生最多只能被抽中一次，即不能被重復(fù)點(diǎn)到名字。12.1.2動(dòng)態(tài)數(shù)組實(shí)例——隨機(jī)點(diǎn)名//函數(shù)功能：從文件filename中讀取名單存入數(shù)組msgintReadFromFile(charfileName[],ROLLmsg[]){FILE*fp=fopen(fileName,"r");if(fp==NULL){printf("cannotopenfile%s\n",fileName);return1;}inti=0;while(fgets(msg[i].name,sizeof(msg[i].name),fp)){i++;}fclose(fp);returni;}【例12.1】請(qǐng)編寫一個(gè)點(diǎn)名神器，從文件中讀取學(xué)生名單，每按一次回車鍵，就從學(xué)生名單中隨機(jī)抽取1個(gè)學(xué)生，直到按ESC鍵或者學(xué)生名單中的學(xué)生全部抽完為止，要求每個(gè)學(xué)生最多只能被抽中一次，即不能被重復(fù)點(diǎn)到名字。12.1.2動(dòng)態(tài)數(shù)組實(shí)例——隨機(jī)點(diǎn)名//函數(shù)功能：隨機(jī)點(diǎn)名，總計(jì)名單中有total個(gè)學(xué)生voidMakeRollCall(ROLLmsg[],inttotal){srand(time(NULL));for(inti=0;i<total;i++){msg[i].flag=0;//標(biāo)記都沒有被點(diǎn)過

}charch='';inti=0;do{intk=rand()%total;//隨機(jī)確定被點(diǎn)名學(xué)生的下標(biāo)

if(kbhit()&&msg[k].flag==0)//當(dāng)有按鍵，并且第k個(gè)人也沒有被點(diǎn)過

{ch=getch();//等待用戶按任意鍵，以回車符結(jié)束輸入

if(ch!=27){i++;printf("請(qǐng)第%d位同學(xué)回答問題：%s\n",i,msg[k].name);msg[k].flag=1;//標(biāo)記其已經(jīng)被點(diǎn)過

}}}while(ch!=27&&i<total);if(ch==27){printf("點(diǎn)名結(jié)束\n");}else{printf("所有同學(xué)均已點(diǎn)名完畢\n");}}【例12.1】請(qǐng)編寫一個(gè)點(diǎn)名神器，從文件中讀取學(xué)生名單，每按一次回車鍵，就從學(xué)生名單中隨機(jī)抽取1個(gè)學(xué)生，直到按ESC鍵或者學(xué)生名單中的學(xué)生全部抽完為止，要求每個(gè)學(xué)生最多只能被抽中一次，即不能被重復(fù)點(diǎn)到名字。intmain(void){intn;printf("Howmanystudents?");scanf("%d",&n);//輸入學(xué)生人數(shù)

ROLL*msg=(ROLL*)malloc(n*sizeof(ROLL));//向系統(tǒng)申請(qǐng)內(nèi)存

if(msg==NULL)//確保指針使用前是非空指針，為空指針時(shí)結(jié)束程序運(yùn)行

{ printf("Noenoughmemory!\n"); exit(1);}char*fileName="student.txt";inttotal=ReadFromFile(fileName,msg,n);printf("總計(jì)%d名學(xué)生\n現(xiàn)在開始隨機(jī)點(diǎn)名\n",total);MakeRollCall(msg,total);//隨機(jī)點(diǎn)名

free(msg);//釋放向系統(tǒng)申請(qǐng)的內(nèi)存

return0;}12.1.2動(dòng)態(tài)數(shù)組實(shí)例——隨機(jī)點(diǎn)名使用一維動(dòng)態(tài)數(shù)組來實(shí)現(xiàn)點(diǎn)名神器【例12.1】請(qǐng)編寫一個(gè)點(diǎn)名神器，從文件中讀取學(xué)生名單，每按一次回車鍵，就從學(xué)生名單中隨機(jī)抽取1個(gè)學(xué)生，直到按ESC鍵或者學(xué)生名單中的學(xué)生全部抽完為止，要求每個(gè)學(xué)生最多只能被抽中一次，即不能被重復(fù)點(diǎn)到名字。//函數(shù)功能：從文件filename中讀取名單存入數(shù)組msg，返回名單中的實(shí)際人數(shù)intReadFromFile(charfileName[],ROLL*msg,intn){FILE*fp=fopen(fileName,"r");if(fp==NULL){printf("cannotopenfile%s\n",fileName);return1;}inti;for(i=0;i<n;i++)//讀取你條記錄，若已經(jīng)讀到文件尾，則結(jié)束循環(huán)

{if(!fgets(msg[i].name,sizeof(msg[i].name),fp))break;}fclose(fp);returni;//返回名單中的實(shí)際人數(shù)}12.1.2動(dòng)態(tài)數(shù)組實(shí)例——隨機(jī)點(diǎn)名【例12.1】請(qǐng)編寫一個(gè)點(diǎn)名神器，從文件中讀取學(xué)生名單，每按一次回車鍵，就從學(xué)生名單中隨機(jī)抽取1個(gè)學(xué)生，直到按ESC鍵或者學(xué)生名單中的學(xué)生全部抽完為止，要求每個(gè)學(xué)生最多只能被抽中一次，即不能被重復(fù)點(diǎn)到名字。//函數(shù)功能：隨機(jī)點(diǎn)名，總計(jì)名單中有total個(gè)學(xué)生voidMakeRollCall(ROLL*msg,inttotal){srand(time(NULL));for(inti=0;i<total;i++){msg[i].flag=0;//標(biāo)記都沒有被點(diǎn)過

}charch='';inti=0;do{intk=rand()%total;//隨機(jī)確定被點(diǎn)名學(xué)生的下標(biāo)

if(kbhit()&&msg[k].flag==0)//當(dāng)有按鍵，并且第k個(gè)人也沒有被點(diǎn)過

{ch=getch();//等待用戶按任意鍵，以回車符結(jié)束輸入

if(ch!=27){i++;printf("請(qǐng)第%d位同學(xué)回答問題：%s\n",i,msg[k].name);msg[k].flag=1;//標(biāo)記其已經(jīng)被點(diǎn)過

}}}while(ch!=27&&i<total);if(ch==27){printf("點(diǎn)名結(jié)束\n");}else{printf("所有同學(xué)均已點(diǎn)名完畢\n");}}12.1.2動(dòng)態(tài)數(shù)組實(shí)例——隨機(jī)點(diǎn)名12.2從靜態(tài)數(shù)據(jù)結(jié)構(gòu)到動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)本節(jié)主要討論如下問題：（1）何為單向鏈表？何為單向循環(huán)鏈表？（2）如何對(duì)鏈表進(jìn)行遍歷以及增、刪節(jié)點(diǎn)的操作？在C語言中，指針之所以重要，原因主要有以下幾點(diǎn)：（1）指針作函數(shù)參數(shù)，提供了一種從函數(shù)返回修改的變量值的手段。（2）利用指針的增1和減1運(yùn)算來尋址數(shù)組元素，可以提高程序的執(zhí)行效率。（3）指針為動(dòng)態(tài)內(nèi)存分配系統(tǒng)提供了支持。（4）利用指針和動(dòng)態(tài)內(nèi)存分配實(shí)現(xiàn)動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)（如鏈表、隊(duì)列、二叉樹等）。12.2.1線性表的鏈?zhǔn)酱鎯?chǔ)數(shù)組（包括結(jié)構(gòu)體數(shù)組）實(shí)際上是一種線性表的順序存儲(chǔ)方式，像這種用一組地址連續(xù)的存儲(chǔ)單元存放一個(gè)線性表，稱為順序表。優(yōu)點(diǎn)表中的數(shù)據(jù)元素在邏輯上和物理上都是相鄰的，使用直觀，便于實(shí)現(xiàn)線性表中任一元素的快速隨機(jī)存取。缺點(diǎn)插入和刪除操作時(shí)需要移動(dòng)大量的數(shù)組元素?cái)?shù)組屬于靜態(tài)數(shù)據(jù)結(jié)構(gòu)，數(shù)組的長(zhǎng)度不能在程序運(yùn)行時(shí)改變數(shù)組的長(zhǎng)度，實(shí)際使用的數(shù)組元素個(gè)數(shù)不能超過定義數(shù)組時(shí)指定的數(shù)組長(zhǎng)度的限制，否則就會(huì)發(fā)生下標(biāo)越界錯(cuò)誤，而低于所設(shè)定的最大長(zhǎng)度時(shí)，又會(huì)造成系統(tǒng)資源的浪費(fèi)，因而空間效率差CB下的錯(cuò)誤提示：field'next'hasincompletetypeVC下的錯(cuò)誤提示：'next'usesundefinedstruct'link'不能包含本結(jié)構(gòu)體類型的成員系統(tǒng)無法預(yù)知占據(jù)多少內(nèi)存

12.2.1線性表的鏈?zhǔn)酱鎯?chǔ)可以包含指向本結(jié)構(gòu)體類型的指針變量structlink

{

intdata;

structlink*next;

};//遞歸數(shù)據(jù)結(jié)構(gòu)structlink

{

int data;

structlinknext;

};structlink{

int

data;//數(shù)據(jù)域：存儲(chǔ)節(jié)點(diǎn)的數(shù)據(jù)信息

structlink*next;//指針域：存儲(chǔ)其直接后繼信息};典型代表——單向鏈表（LinkedTable）用一組任意的存儲(chǔ)單元（不一定連續(xù)）鏈?zhǔn)酱鎯?chǔ)線性表數(shù)據(jù)12.2.1線性表的鏈?zhǔn)酱鎯?chǔ)只包含一個(gè)指針域，又稱線性鏈表或單向鏈表12.2.2單向鏈表的基本操作向單向鏈表中添加節(jié)點(diǎn)分兩種情況：原鏈表為空表、非空表若原鏈表為空表(head==NULL)，則將新建節(jié)點(diǎn)p置為頭節(jié)點(diǎn)若原鏈表為非空，則將新建節(jié)點(diǎn)newP添加到表尾if(head==NULL)//若鏈表為空表

{ head=newP; }else { p=head; while(pr->next!=NULL)//若未到表尾 { p=p->next;//pr指向下一節(jié)點(diǎn) } p->next=newP;//末節(jié)點(diǎn)指針指向新建節(jié)點(diǎn)}newP=(structlink*)malloc(sizeof(structlink));newP->data=nodeData;newP->next=NULL;12.2.2單向鏈表的基本操作刪除節(jié)點(diǎn)分兩種情況：空表、非空表（待刪節(jié)點(diǎn)為頭節(jié)點(diǎn)、非頭節(jié)點(diǎn)）datanextheaddatanextpr//找待刪除節(jié)點(diǎn)while(p->data!=nodeData&&p->next!=NULL)//未找到且未到表尾{

pr=p;//在pr中保存當(dāng)前節(jié)點(diǎn)的指針

p=p->next;//p指向當(dāng)前節(jié)點(diǎn)的下一節(jié)點(diǎn)}pp待刪除節(jié)點(diǎn)12.2.2單向鏈表的基本操作分兩種情況：空表、非空表（待刪節(jié)點(diǎn)為頭節(jié)點(diǎn)、非頭節(jié)點(diǎn)）若原鏈表為空表，則退出程序若待刪節(jié)點(diǎn)p是頭節(jié)點(diǎn)，則將head指向當(dāng)前節(jié)點(diǎn)的后繼節(jié)點(diǎn)即可datanexthead待刪除節(jié)點(diǎn)datanextp頭節(jié)點(diǎn)if(p->data==nodeData)//找到待刪節(jié)點(diǎn){

if(p==head)//若待刪節(jié)點(diǎn)p為頭節(jié)點(diǎn){ head=p->next;//head指向待刪除節(jié)點(diǎn)p的后繼節(jié)點(diǎn)}

else//若待刪節(jié)點(diǎn)不是頭節(jié)點(diǎn){ pr->next=p->next;//前驅(qū)節(jié)點(diǎn)指向待刪節(jié)點(diǎn)的后繼} free(p); //釋放為已刪除節(jié)點(diǎn)分配的內(nèi)存}12.2.2單向鏈表的基本操作若待刪節(jié)點(diǎn)不是頭節(jié)點(diǎn)，則前驅(qū)節(jié)點(diǎn)指向后繼節(jié)點(diǎn)datanextdatanext待刪除節(jié)點(diǎn)datanextp中間節(jié)點(diǎn)datanext若已搜到表尾（p->next==NULL）仍未找到待刪除節(jié)點(diǎn)，則顯示“未找到”prif(p->data==nodeData)//找到待刪節(jié)點(diǎn){ if(p==head)//若待刪節(jié)點(diǎn)p為頭節(jié)點(diǎn){ head=p->next;//head指向待刪除節(jié)點(diǎn)p的后繼節(jié)點(diǎn)} else//若待刪節(jié)點(diǎn)不是頭節(jié)點(diǎn){ pr->next=p->next;//前驅(qū)節(jié)點(diǎn)指向待刪節(jié)點(diǎn)的后繼} free(p); //釋放為已刪除節(jié)點(diǎn)分配的內(nèi)存}else//找到表尾仍未找到{printf("Notfound!\n");}12.2.2單向鏈表的基本操作在升序的鏈表中插入節(jié)點(diǎn)分兩種情況：空表、非空有序表非空表分三種情況：在頭節(jié)點(diǎn)前、中間節(jié)點(diǎn)、表尾節(jié)點(diǎn)后插入新節(jié)點(diǎn)若原鏈表為空表，則將新節(jié)點(diǎn)p作為頭節(jié)點(diǎn)，讓head指向新節(jié)點(diǎn)phead待插入節(jié)點(diǎn)datap∧if(head==NULL)//若原鏈表為空表{ head=p;//待插入節(jié)點(diǎn)作為頭節(jié)點(diǎn)}else//若原鏈表為非空{(diào)//找待插入位置while(nodeData>pr->data&&pr->next!=NULL){ temp=pr;//在temp中保存當(dāng)前節(jié)點(diǎn)的指針 pr=pr->next;//pr指向當(dāng)前節(jié)點(diǎn)的后繼節(jié)點(diǎn)

} ……}p=(structlink*)malloc(sizeof(structlink));p->data=nodeData;p->next=NULL;head12.2.2單向鏈表的基本操作待插入節(jié)點(diǎn)nodeDatanextpdatanextdata∧prprtemp待插入位置p=(structlink*)malloc(sizeof(structlink));p->data=nodeData;p->next=NULL;pr=head;if(head==NULL)//若原鏈表為空表{ head=p;//待插入節(jié)點(diǎn)作為頭節(jié)點(diǎn)}else//若原鏈表為非空{(diào)

//找待插入位置

while(nodeData>pr->data&&pr->next!=NULL)

{ temp=pr;//在temp中保存當(dāng)前節(jié)點(diǎn)的指針 pr=pr->next;//pr指向當(dāng)前節(jié)點(diǎn)的后繼節(jié)點(diǎn)

} ……}若原鏈表非空，則按節(jié)點(diǎn)值大?。僭O(shè)升序）確定插入新節(jié)點(diǎn)的位置12.2.2單向鏈表的基本操作head待插入節(jié)點(diǎn)datanextpdatanextdatanextdata∧if(nodeData<=pr->data)//不在表尾插入{

if(pr==head)//若在頭節(jié)點(diǎn)前插入新節(jié)點(diǎn) { p->next=head;//將新節(jié)點(diǎn)指向鏈頭

head=p;//head指向新節(jié)點(diǎn) } else//若在鏈表中間插入新節(jié)點(diǎn) { pr=temp; p->next=pr->next;//新節(jié)點(diǎn)指向后繼節(jié)點(diǎn)

pr->next=p;//前驅(qū)節(jié)點(diǎn)指向新節(jié)點(diǎn) }}若在頭節(jié)點(diǎn)前插入節(jié)點(diǎn)，則將新節(jié)點(diǎn)的指針域指向原鏈表的頭節(jié)點(diǎn)，且讓head指向新節(jié)點(diǎn)p=(structlink*)malloc(sizeof(structlink));p->data=nodeData;p->next=NULL;prdatanext12.2.2單向鏈表的基本操作若在鏈表中間插入新節(jié)點(diǎn)，則將新節(jié)點(diǎn)的指針域指向下一節(jié)點(diǎn)且讓前一節(jié)點(diǎn)的指針域指向新節(jié)點(diǎn)待插入節(jié)點(diǎn)datanextpdatanextdatanextdata∧prtemp待插入位置if(nodeData<=pr->data)//不在表尾插入{ if(pr==head)//若在頭節(jié)點(diǎn)前插入新節(jié)點(diǎn) { p->next=head;//將新節(jié)點(diǎn)指向鏈頭

head=p;//head指向新節(jié)點(diǎn) }

else//若在鏈表中間插入新節(jié)點(diǎn) { pr=temp; p->next=pr->next;//新節(jié)點(diǎn)指向后繼節(jié)點(diǎn)

pr->next=p;//前驅(qū)節(jié)點(diǎn)指向新節(jié)點(diǎn) }}p=(structlink*)malloc(sizeof(structlink));p->data=nodeData;p->next=NULL;prdatanext12.2.2單向鏈表的基本操作若在表尾插入新節(jié)點(diǎn)，則末節(jié)點(diǎn)指針域指向新節(jié)點(diǎn)待插入節(jié)點(diǎn)datanextpprdata∧原末節(jié)點(diǎn)next∧//找待插入節(jié)點(diǎn)while(nodeData>pr->data&&pr->next!=NULL){ temp=pr; pr=pr->next; } if(nodeData<=pr->data)

//不在表尾插入{……}else//即pr->next==NULL，表示若在表尾插入新節(jié)點(diǎn){ pr->next=p;//末節(jié)點(diǎn)指向新節(jié)點(diǎn)}p=(structlink*)malloc(sizeof(structlink));p->data=nodeData;p->next=NULL;除尾節(jié)點(diǎn)的后繼指針指向首節(jié)點(diǎn)外，均與單鏈表一致每個(gè)節(jié)點(diǎn)只包含一個(gè)指針，即后繼指針//單向鏈表structlink{

int data;

structlink*next;};//雙向鏈表structDNode{

int data;

structDNode*prev;//指向前驅(qū)structDNode*next;//指向后繼

};12.2.3單向循環(huán)鏈表應(yīng)用實(shí)例——循環(huán)報(bào)數(shù)問題12.2.3單向循環(huán)鏈表應(yīng)用實(shí)例——循環(huán)報(bào)數(shù)問題【例12.2】據(jù)說，魯智深一天中午匆匆來到開封府大相國(guó)寺，想蹭頓飯吃，當(dāng)時(shí)大相國(guó)寺有99個(gè)和尚，只做了99個(gè)饅頭，智清長(zhǎng)老不愿得罪魯智深，便把他安排在一個(gè)特定位置，之后對(duì)所有人說：從我開始報(bào)數(shù)（圍成一圈），第5個(gè)人可以吃到饅頭（并退下），按此方法，所有和尚都吃到了饅頭，唯獨(dú)魯智深沒有吃上，請(qǐng)問他在哪個(gè)位置？方法1：用一維數(shù)組實(shí)現(xiàn)//函數(shù)功能：用數(shù)組求解循環(huán)報(bào)數(shù)問題//函數(shù)參數(shù)：n為參與報(bào)數(shù)的總?cè)藬?shù)，m表示每隔m人有一人退出圈子//函數(shù)返回值：返回剩下的最后一個(gè)人的編號(hào)intNumberOff(intn,intm){inti,c=0,counter=0,a[N];for(i=1;i<=n;++i)//按從1到n的順序給每個(gè)人編號(hào)

{

a[i]=i;}do{for(i=1;i<=n;++i){if(a[i]!=0){c++;//元素不為0,則c加1,記錄報(bào)數(shù)的人數(shù)

if(c%m==0)//c除以m的余數(shù)為0,說明此位置為第m個(gè)報(bào)數(shù)的人

{

a[i]=0;//將退出圈子的人的編號(hào)標(biāo)記為0

counter++;//記錄退出的人數(shù)

}}}}while(counter!=n-1);//當(dāng)退出圈子的人數(shù)達(dá)到n-1人時(shí)結(jié)束循環(huán)，否則繼續(xù)循環(huán)

for(i=1;i<=n;++i){if(a[i]!=0)returni;}return0;}方法1：用一維數(shù)組實(shí)現(xiàn)#include<stdio.h>#defineN150typedefstructperson{intnum;//自己的編號(hào)intnextp;//下一個(gè)人的編號(hào)}LINK;voidCreatQueue(LINKlink[],intn);voidCountsOff(LINKlink[],intn,intm);voidPrtLastNum(LINKlink[],intn);intmain(void){intm,n;LINKlink[N+1];printf("Inputn,m(n>m):");scanf("%d,%d",&n,&m);CreatQueue(link,n);//n個(gè)人循環(huán)報(bào)數(shù)，報(bào)到m出隊(duì)，只留最后一個(gè)last=CountsOff(link,n,m);printf("\n最后的成員是：%d\n",last);return0;}linklink[0]link[1]link[2]link[3]......link[N]12.2.3單向循環(huán)鏈表應(yīng)用實(shí)例——循環(huán)報(bào)數(shù)問題方法2：用結(jié)構(gòu)體數(shù)組實(shí)現(xiàn)靜態(tài)循環(huán)鏈表voidCreatQueue(LINKlink[],intn){inti;for(i=1;i<=n;i++){link[i].num=i;//從1開始編號(hào)if(i==n)//尾指向頭{link[i].nextp=1;}else{link[i].nextp=i+1;}}}intCountsOff(LINKlink[],intn,intm){inth=n,i,j,last;printf("出圈成員及順序：");for(j=1;j<n;j++)//出隊(duì)n-1人{(lán)i=0;while(i!=m)//沒有報(bào)到m{h=link[h].nextp;//報(bào)下一個(gè)if(link[h].num!=0)//越過0元素{i++;//報(bào)數(shù)計(jì)數(shù)}}printf("%3d",link[h].num);link[h].num=0;//出隊(duì)元素標(biāo)記為0}for(i=1;i<=n;i++)//查找最后成員的編號(hào){if(link[i].num!=0){last=link[i].num;}}returnlast;}12.2.3單向循環(huán)鏈表應(yīng)用實(shí)例——循環(huán)報(bào)數(shù)問題方法2：用結(jié)構(gòu)體數(shù)組實(shí)現(xiàn)靜態(tài)循環(huán)鏈表intmain(void){LINK*head;//循環(huán)鏈表的頭指針intm,n,last;printf("Inputn,m(n>m):");scanf("%d,%d",&n,&m);head=CreateLink(n);last=CountsOff(head,n,m);printf("最后的成員是：%d\n",last);DeleteMemory(head,n);return0;}12.2.3單向循環(huán)鏈表應(yīng)用實(shí)例——循環(huán)報(bào)數(shù)問題方法3：用單向鏈表實(shí)現(xiàn)動(dòng)態(tài)循環(huán)鏈表LINK*CreateLink(intn)//加入了節(jié)點(diǎn)內(nèi)存申請(qǐng)是否成功的判斷{inti;LINK*p1,*p2,*head=NULL;for(i=1;i<=n;i++){p1=(LINK*)malloc(sizeof(LINK));if(p1==NULL){printf("Noenoughmemorytoallocate!\n");if(i==1)free(p1);elseDeleteMemory(head,i);exit(0);}if(i==1)head=p2=p1;elsep2->next=p1;p1->num=i;p2=p1;}p2->next=head;

returnhead;}voidDeleteMemory(LINK*head,intn){LINK*p=head,*pr=NULL;inti;for(i=1;i<=n;i++){

pr=p;p=p->next;

free(pr);}}方法3：用單向鏈表實(shí)現(xiàn)動(dòng)態(tài)循環(huán)鏈表12.2.3單向循環(huán)鏈表應(yīng)用實(shí)例——循環(huán)報(bào)數(shù)問題intCountsOff(LINK*head,intn,intm)//循環(huán)報(bào)數(shù){inti,j;LINK*p1=head,*p2=p1;if(n==1||m==1){return1;}for(i=1;i<n;i++)//刪掉n-1個(gè)節(jié)點(diǎn)

{for(j=1;j<m-1;j++)//移動(dòng)m-2次，找到第m個(gè)即待刪除節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn){p1=p1->next;}p2=p1;//p2指向第m個(gè)節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)p1=p1->next;//p1指向待刪除的節(jié)點(diǎn)p1=p1->next;//p1指向待刪除節(jié)點(diǎn)的后繼節(jié)點(diǎn)free(p2->next);//釋放p2的后繼節(jié)點(diǎn)（即待刪除節(jié)點(diǎn)）p2->next=p1;//讓p1成為p2的后繼節(jié)點(diǎn)，即刪掉第m個(gè)節(jié)點(diǎn)

}returnp1->num;}方法3：用單向鏈表實(shí)現(xiàn)動(dòng)態(tài)循環(huán)鏈表12.2.3單向循環(huán)鏈表應(yīng)用實(shí)例——循環(huán)報(bào)數(shù)問題小結(jié)定長(zhǎng)數(shù)組動(dòng)態(tài)數(shù)組動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)優(yōu)點(diǎn)連續(xù)存儲(chǔ)，隨機(jī)訪問使用直觀方便數(shù)據(jù)訪問效率高連續(xù)存儲(chǔ)，隨機(jī)訪問，空間不浪費(fèi)，可像數(shù)組一樣使用節(jié)省空間，無浪費(fèi)數(shù)據(jù)插入和刪除效率高適用于存儲(chǔ)長(zhǎng)度固定的數(shù)據(jù)集合適用于長(zhǎng)度在程序運(yùn)行時(shí)才能確切知道的集合適用于長(zhǎng)度在程序運(yùn)行過程中動(dòng)態(tài)變化的集合缺點(diǎn)插入、刪除操作效率低屬于靜態(tài)內(nèi)存分配，程序一旦運(yùn)行長(zhǎng)度不能改變，若想改變，只能修改程序，按最大需求定義數(shù)組，浪費(fèi)空間，還容易發(fā)生下標(biāo)越界程序員自己負(fù)責(zé)內(nèi)存的分配和釋放頻繁申請(qǐng)/釋放，速度慢運(yùn)行時(shí)間稍長(zhǎng)后，還會(huì)造成內(nèi)存空間碎片化分散存儲(chǔ)順序訪問，不可隨機(jī)訪問，數(shù)據(jù)訪問效率低操作較為復(fù)雜靜態(tài)數(shù)據(jù)結(jié)構(gòu)和動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)的區(qū)別12.3限定性線性表之棧和隊(duì)列本節(jié)主要討論如下問題：（1）棧和隊(duì)列兩種數(shù)據(jù)結(jié)構(gòu)各有什么不同的特點(diǎn)？（2）如何實(shí)現(xiàn)棧和隊(duì)列的順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)？數(shù)組是一種“連續(xù)存儲(chǔ)、隨機(jī)訪問”的線性表鏈表則屬于“分散存儲(chǔ)、連續(xù)訪問”的線性表它們的每個(gè)數(shù)據(jù)都有其相對(duì)位置，有至多一個(gè)直接前驅(qū)和至多一個(gè)直接后繼棧和隊(duì)列也屬于線性表，但它們都是運(yùn)算受限的線性表，也稱限定性線性表。棧限定數(shù)據(jù)只能在棧頂執(zhí)行插入（入棧）和刪除（出棧）操作。隊(duì)列限定只能隊(duì)頭執(zhí)行刪除操作（出隊(duì)），在隊(duì)尾執(zhí)行插入操作（入隊(duì)）。12.3.1棧的應(yīng)用實(shí)例——再談回文詩棧是一種特殊的線性表，只允許在線性表的頂端執(zhí)行數(shù)據(jù)的增刪操作，對(duì)棧進(jìn)行運(yùn)算的一端稱為棧頂（top），棧頂?shù)牡谝粋€(gè)元素稱為棧頂元素常用的堆棧運(yùn)算包括：（1）壓入堆棧（Push），簡(jiǎn)稱壓棧，即向一個(gè)棧中插入新元素，即把該元素放到棧頂元素的上面，使其成為新的棧頂元素；（2）彈出堆棧（Pop），簡(jiǎn)稱彈棧，即從一個(gè)棧中刪除元素，使原棧頂元素下方的相鄰元素成為新的棧頂元素。//函數(shù)功能：判斷回文字符串intIsPlalindrome(constcharstr[]){charrev[N];Reverse(str,rev);//計(jì)算字符串str的逆序字符串revreturnstrcmp(str,rev)==0?1:0;}//函數(shù)功能：采用字符數(shù)組做函數(shù)參數(shù)實(shí)現(xiàn)字符串逆序voidReverse(constcharstr[],charrev[]){inti;intlen=strlen(str);STACKs;InitStack(&s);//初始化棧top為-1for(i=0;i<len;i++){Push(&s,str[i]);//字符依次壓棧

}for(i=0;i<len;i++){Pop(&s,&rev[i]);//字符依次彈棧

}rev[i]='\0';//彈棧后的字符加上結(jié)束標(biāo)識(shí)符}12.3.1棧的應(yīng)用實(shí)例——再談回文詩【例12.3】采用棧這種數(shù)據(jù)結(jié)構(gòu)，重新編寫例10.5的判斷回文字符串的程序。采用順序存儲(chǔ)的數(shù)組實(shí)現(xiàn)//函數(shù)功能：將data壓入堆棧stackintPush(STACK*s,chardata){if(FullStack(s))//判斷棧是否已滿

{printf("stackisfull!\n");return0;}s->top=s->top+1;//更新棧頂s->data[s->top]=data;//給新棧頂元素賦值)return1;}12.3.1棧的應(yīng)用實(shí)例——再談回文詩【例12.3】采用棧這種數(shù)據(jù)結(jié)構(gòu)，重新編寫例10.5的判斷回文字符串的程序。//函數(shù)功能：從堆棧stack中彈出棧頂數(shù)據(jù)intPop(STACK*s,char*data){if(EmptyStack(s))//判斷棧是否為空

{printf("stackisempty!\n");return0;}*data=s->data[s->top];//彈出棧頂元素，對(duì)應(yīng)圖12-19(d)s->top=s->top-1;//更新棧頂，對(duì)應(yīng)圖12-19(e)return1;}12.3.1棧的應(yīng)用實(shí)例——再談回文詩【例12.3】采用棧這種數(shù)據(jù)結(jié)構(gòu)，重新編寫例10.5的判斷回文字符串的程序。//函數(shù)功能：判斷棧是否為空intEmptyStack(STACK*s){returns->top==-1?1:0;}//函數(shù)功能：判斷棧是否已滿intFullStack(STACK*s){returns->top==N-1?1:0;}//函數(shù)功能：初始化棧voidInitStack(STACK*s){s->top=-1;//初始化棧top為-1}12.3.1棧的應(yīng)用實(shí)例——再談回文詩【例12.3】采用棧這種數(shù)據(jù)結(jié)構(gòu)，重新編寫例10.5的判斷回文字符串的程序。typedefstructstack{chardata[N];//每個(gè)元素保存一個(gè)字符

inttop;//指示棧頂}STACK;intmain(void){chara[N];printf("Inputastring:");gets(a);if(IsPlalindrome(a))//判斷是否是回文

{printf("Yes\n");}else{printf("No\n");}return0;}//函數(shù)功能：判斷回文字符串intIsPlalindrome(constcharstr[]){charrev[N];Reverse(str,rev);//計(jì)算字符串str的逆序字符串revreturnstrcmp(str,rev)==0?1:0;}//函數(shù)功能：采用字符數(shù)組做函數(shù)參數(shù)實(shí)現(xiàn)字符串逆序voidReverse(constcharstr[],charrev[]){inti;intlen=strlen(str);STACK*top=InitStack(top);//初始化棧top指向NULLfor(i=0;i<len;i++){top=Push(top,str[i]);//字符依次壓棧

}for(i=0;i<len;i++){top=Pop(top,&rev[i]);//字符依次彈棧

}rev[i]='\0';//彈棧后的字符加上結(jié)束標(biāo)識(shí)符}12.3.1棧的應(yīng)用實(shí)例——再談回文詩【例12.3】采用棧這種數(shù)據(jù)結(jié)構(gòu)，重新編寫例10.5的判斷回文字符串的程序。采用鏈?zhǔn)酱鎯?chǔ)的單向鏈表實(shí)現(xiàn)//函數(shù)功能：將data壓入堆棧stackSTACK*Push(STACK*top,chardata){STACK*p=(STACK*)malloc(sizeof(STACK));//創(chuàng)建新節(jié)點(diǎn)

p->data=data;//給新節(jié)點(diǎn)賦值

p->next=top;//新節(jié)點(diǎn)鏈接到原棧頂指針，對(duì)應(yīng)圖12-20(b)top=p;//更新棧頂指針指向新節(jié)點(diǎn)，對(duì)應(yīng)圖12-20(c)returntop;//返回新的棧頂指針}12.3.1棧的應(yīng)用實(shí)例——再談回文詩【例12.3】采用棧這種數(shù)據(jù)結(jié)構(gòu)，重新編寫例10.5的判斷回文字符串的程序。//函數(shù)功能：從堆棧stack中彈出棧頂數(shù)據(jù)STACK*Pop(STACK*top,char*data){if(EmptyStack(top))//判斷棧是否為空

{printf("stackisempty!\n");returnNULL;}STACK*p=top;//讓p指向棧頂，對(duì)應(yīng)圖12-20(d)*data=p->data;//彈出棧頂數(shù)據(jù)

top=top->next;//更新棧頂指針，對(duì)應(yīng)圖12-20(e)free(p);//釋放刪除的節(jié)點(diǎn)，對(duì)應(yīng)圖12-20(f)returntop;//返回新的棧頂指針}12.3.1棧的應(yīng)用實(shí)例——再談回文詩【例12.3】采用棧這種數(shù)據(jù)結(jié)構(gòu)，重新編寫例10.5的判斷回文字符串的程序。//函數(shù)功能：判斷棧是否為空intEmptyStack(STACK*top){return(top==NULL)?1:0;}//函數(shù)功能：初始化棧STACK*InitStack(STACK*top){top=NULL;//初始化為空

returntop;//返回棧頂指針}12.3.1棧的應(yīng)用實(shí)例——再談回文詩【例12.3】采用棧這種數(shù)據(jù)結(jié)構(gòu)，重新編寫例10.5的判斷回文字符串的程序。typedefstructstackNode{chardata;//每個(gè)節(jié)點(diǎn)保存一個(gè)字符

structstackNode*next;//指向后繼節(jié)點(diǎn)}STACK;intmain(void){chara[N];printf("Inputastring:");gets(a);if(IsPlalindrome(a))//判斷是否是回文

{printf("Yes\n");}else{printf("No\n");}return0;}12.3.2隊(duì)列的應(yīng)用實(shí)例——再談循環(huán)報(bào)數(shù)問題隊(duì)列也是一種特殊的線性表其工作方式與棧剛好相反，其主要特點(diǎn)是先入先出（FirstInFirstOut,FIFO）即最先放入隊(duì)列的數(shù)據(jù)最先被取走。常用的隊(duì)列運(yùn)算包括：（1）入隊(duì)（Enqueue），即將新的元素插入隊(duì)尾，新元素進(jìn)隊(duì)后將成為新的隊(duì)尾元素。（2）出隊(duì)（Dequeue）即從隊(duì)頭刪除元素，其后繼元素將成為新的對(duì)頭元素。因此，為了便于管理隊(duì)列中的元素，通常設(shè)置兩個(gè)指針head和tail，分別指向隊(duì)頭和隊(duì)尾。12.3.2隊(duì)列的應(yīng)用實(shí)例——再談循環(huán)報(bào)數(shù)問題假設(shè)隊(duì)列的最大容量QMAX為10，在隊(duì)列為空時(shí)，head與tail相等，均為0。對(duì)于普通隊(duì)列而言，當(dāng)tail==QMAX-1時(shí)會(huì)有數(shù)據(jù)搬移操作，影響入隊(duì)操作性能12.3.2隊(duì)列的應(yīng)用實(shí)例——再談循環(huán)報(bào)數(shù)問題當(dāng)隊(duì)列滿了以后，不斷執(zhí)行出隊(duì)操作，而沒有入隊(duì)操作，直到head和tail一樣都指向了隊(duì)尾此時(shí)既不能插入，也不能刪除，因?yàn)槿粢迦耄瑫?huì)被告知隊(duì)列已滿，若要?jiǎng)h除，會(huì)被告知隊(duì)列為空。這就是所謂的隊(duì)列“假滿”問題12.3.2隊(duì)列的應(yīng)用實(shí)例——再談循環(huán)報(bào)數(shù)問題解決隊(duì)列假滿問題的方法就是采用循環(huán)隊(duì)列。因?yàn)檠h(huán)隊(duì)列的插入和刪除操作是在一個(gè)模擬成環(huán)形的存儲(chǔ)空間中“兜圈子”在循環(huán)隊(duì)列中，tail并非指向隊(duì)尾元素，而是指向隊(duì)尾元素的后一個(gè)位置如何模擬成環(huán)形的存儲(chǔ)空間中“兜圈子”呢？在移動(dòng)指針head或tail（即對(duì)其值加1）后再將其對(duì)QMAX進(jìn)行取余的操作。例如，當(dāng)有數(shù)據(jù)入隊(duì)時(shí)，隊(duì)尾指針tail變?yōu)?tail+1)%QMAX，當(dāng)有數(shù)據(jù)出隊(duì)時(shí)，隊(duì)頭指針head變?yōu)?head+1)%QMAX。head==tail仍是隊(duì)列為空的標(biāo)志，隊(duì)列已滿的標(biāo)志是(tail+1)%QMAX==head，隊(duì)列中之所以保留了一個(gè)空的單元，主要目的是避免與隊(duì)空標(biāo)志相沖突，因此具有QMAX個(gè)元素的循環(huán)隊(duì)列最多只能存放QMAX-1個(gè)元素。//函數(shù)功能：初始化循環(huán)隊(duì)列voidInitQueue(QUEUE*q,intn){q->size=n+1;//初始化隊(duì)列長(zhǎng)度,空一個(gè)單元

q->head=q->tail=0;//初始化隊(duì)頭和隊(duì)尾標(biāo)記}//函數(shù)功能：判斷循環(huán)隊(duì)列是否為空intEmptyQueue(constQUEUE*q){returnq->head==q->tail?1:0;}//函數(shù)功能：判斷循環(huán)隊(duì)列是否隊(duì)滿intFullQueue(constQUEUE*q){return(q->tail+1)%q->size==q->head?1:0;//隊(duì)滿則返回1，否則返回0}12.3.2隊(duì)列的應(yīng)用實(shí)例——再談循環(huán)報(bào)數(shù)問題【例12.4】用循環(huán)隊(duì)列來編程求解循環(huán)報(bào)數(shù)問題。typedefstructqueue{intnum[N+1];//編號(hào)數(shù)組

intsize;//隊(duì)列長(zhǎng)度

inthead;//隊(duì)頭

inttail;//隊(duì)尾}QUEUE;intmain(void){intm,n;QUEUEq;printf("Inputn,m(n>m):");scanf("%d,%d",&n,&m);InitQueue(&q,n);

intlast=NumberOff(&q,n,m);

printf("%disleft\n",last);return0;}方法1：用順序存儲(chǔ)的循環(huán)隊(duì)列實(shí)現(xiàn)12.3.2隊(duì)列的應(yīng)用實(shí)例——再談循環(huán)報(bào)數(shù)問題【例12.4】用循環(huán)隊(duì)列來編程求解循環(huán)報(bào)數(shù)問題。//函數(shù)功能：循環(huán)隊(duì)列進(jìn)隊(duì)intEnQueue(QUEUE*q,inte){if(FullQueue(q))//隊(duì)滿，則返回0，否則入隊(duì)并返回1{return0;}q->num[q->tail]=e;//在隊(duì)尾放入新數(shù)據(jù)

q->tail=(q->tail+1)%q->size;//更新隊(duì)尾的標(biāo)記

return1;}//函數(shù)功能：循環(huán)隊(duì)列出隊(duì)，即刪除隊(duì)首元素intDeQueue(QUEUE*q,int*e){if(EmptyQueue(q))//隊(duì)空，則返回0，否則出隊(duì)并返回1{return0;}*e=q->num[q->head];//隊(duì)頭數(shù)據(jù)出隊(duì)

q->head=(q->head+1)%q->size;//更新隊(duì)頭的標(biāo)記

return1;}12.3.2隊(duì)列的應(yīng)用實(shí)例——再談循環(huán)報(bào)數(shù)問題【例12.4】用循環(huán)隊(duì)列來編程求解循環(huán)報(bào)數(shù)問題。//函數(shù)功能：循環(huán)報(bào)數(shù)intNumberOff(QUEUE*q,intn,intm){inti,j,e,num[N];for(i=0;i<n;i++)//將所有人編號(hào)并且排隊(duì)

{num[i]=i+1;//將所有人編號(hào)

EnQueue(q,num[i]); //將每個(gè)人依次入隊(duì)

}//排查報(bào)數(shù)為m的人

i=j=0;while(!EmptyQueue(q))//若循環(huán)隊(duì)列非空，則排查報(bào)數(shù)為m的人

{i++;//報(bào)數(shù)計(jì)數(shù)器

DeQueue(q,&e);//隊(duì)首元素e出隊(duì)不再入隊(duì)

if(i==m){num[j]=e;//報(bào)到m者出隊(duì)后保存到出隊(duì)數(shù)組，不再入隊(duì)

i=0;//報(bào)數(shù)計(jì)數(shù)器重新開始計(jì)數(shù)

j++;//出隊(duì)數(shù)組下標(biāo)計(jì)數(shù)

}else{EnQueue(q,e);//未報(bào)到m者，還要再入隊(duì)，e放到隊(duì)尾

}}returnnum[n-1];//但會(huì)最后一個(gè)出隊(duì)的人的編號(hào)}12.3.2隊(duì)列的應(yīng)用實(shí)例——再談循環(huán)報(bào)數(shù)問題【例12.4】用循環(huán)隊(duì)列來編程求解循環(huán)報(bào)數(shù)問題。typedefstructQueueNode{intnum;//每個(gè)節(jié)點(diǎn)保存一個(gè)人的編號(hào)

structQueueNode*next;//指向后繼節(jié)點(diǎn)的指針}QueueNode;typedefstructQueue{QueueNode*head;//隊(duì)頭的指針

QueueNode*tail;//隊(duì)尾的指針}QUEUE;方法2：用鏈?zhǔn)酱鎯?chǔ)的循環(huán)隊(duì)列實(shí)現(xiàn)intmain(void){intm,n,last;printf("Inputn,m(n>m):");scanf("%d,%d",&n,&m);QUEUE*q=InitQueue();//初始化循環(huán)隊(duì)列

last=NumberOff(q,n,m);//循環(huán)報(bào)數(shù)

printf("%disleft\n",last);}12.3.2隊(duì)列的應(yīng)用實(shí)例——再談循環(huán)報(bào)數(shù)問題【例12.4】用循環(huán)隊(duì)列來編程求解循環(huán)報(bào)數(shù)問題。QUEUE*InitQueue(void){QUEUE*q=(QUEUE*)malloc(sizeof(QUEUE));//新建一個(gè)節(jié)點(diǎn)pif(q==NULL)//若內(nèi)存分配失敗，則結(jié)束程序

{printf("Noenoughmemorytoallocate!\n");exit(0);}q->head=q->tail=NULL;//初始化隊(duì)列為空

returnq;}//函數(shù)功能：釋放所有節(jié)點(diǎn)的內(nèi)存voidDeleteMemory(QUEUE*q){QueueNode*p;while(q->head!=q->tail){p=q->head;q->head=q->head->next;free(p);}free(q->head);}12.3.2隊(duì)列的應(yīng)用實(shí)例——再談循環(huán)報(bào)數(shù)問題【例12.4】用循環(huán)隊(duì)列來編程求解循環(huán)報(bào)數(shù)問題。//函數(shù)功能：循環(huán)隊(duì)列入隊(duì)voidEnQueue(QUEUE*q,inte){QueueNode*p=(QueueNode*)malloc(sizeof(QueueNode));//新建一個(gè)節(jié)點(diǎn)

if(p==NULL)//若內(nèi)存分配失敗，則結(jié)束程序

{printf("Noenoughmemorytoallocate!\n");DeleteMemory(q);exit(0);}p->num=e;//新數(shù)據(jù)存入新建節(jié)點(diǎn)

if(q->head==NULL)//若為空隊(duì)列，則新建節(jié)點(diǎn)作為唯一節(jié)點(diǎn)入隊(duì)

{q->head=p;//設(shè)置頭指針指向新建節(jié)點(diǎn)，對(duì)應(yīng)圖12-28(a)q->tail=p;//設(shè)置尾指針指向新建節(jié)點(diǎn)，對(duì)應(yīng)圖12-28(a)}else//若隊(duì)列非空，則新建節(jié)點(diǎn)入隊(duì)到已有隊(duì)列的隊(duì)尾

{q->tail->next=p;//將新建節(jié)點(diǎn)鏈接到尾節(jié)點(diǎn)，對(duì)應(yīng)圖12-28(c)q->tail=p;//將尾指針指向新建節(jié)點(diǎn)，對(duì)應(yīng)圖12-28(d)}p->next=q->head;//新建節(jié)點(diǎn)指向隊(duì)頭節(jié)點(diǎn)，使其成為循環(huán)鏈表，對(duì)應(yīng)圖12-28(e)}12.3.2隊(duì)列的應(yīng)用實(shí)例——再談循環(huán)報(bào)數(shù)問題【例12.4】用循環(huán)隊(duì)列來編程求解循環(huán)報(bào)數(shù)問題。//函數(shù)功能：循環(huán)隊(duì)列出隊(duì)，即刪除隊(duì)首元素voidDeQueue(QUEUE*q,int*e){QueueNode*p=q->head;//將p指向隊(duì)頭節(jié)點(diǎn)，對(duì)應(yīng)圖12-28(f)if(q->head==NULL)//若為空隊(duì)列，則返回

{return;}*e=q->head->num;//取出隊(duì)首元素

if(q->head!=q->tail)//若隊(duì)列中剩余的節(jié)點(diǎn)不止一個(gè)

{q->head=q->head->next;//更新隊(duì)頭指針，對(duì)應(yīng)圖12-28(g)q->tail->next=q->head;//更新隊(duì)尾指針，對(duì)應(yīng)圖12-28(h)}free(p);//釋放頭節(jié)點(diǎn)p，對(duì)應(yīng)圖12-28(i)}12.3.2隊(duì)列的應(yīng)用實(shí)例——再談循環(huán)報(bào)數(shù)問題【例