第12章-結(jié)構(gòu)體和數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)

哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院蘇小紅

sxh@

第12章結(jié)構(gòu)體和數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)第12章學(xué)習(xí)內(nèi)容結(jié)構(gòu)體，共用體，枚舉類型結(jié)構(gòu)體變量、數(shù)組、指針的定義結(jié)構(gòu)體成員的引用向函數(shù)傳遞結(jié)構(gòu)體動態(tài)數(shù)據(jù)結(jié)構(gòu)：鏈表、棧、隊列、二叉樹2/65對計算機系統(tǒng)和硬件，類型的概念不存在因為在馮.諾依曼體系結(jié)構(gòu)中，程序中的數(shù)據(jù)和代碼都是以二進(jìn)制存儲的機器指令及匯編語言中，數(shù)據(jù)對象均用二進(jìn)制數(shù)表示內(nèi)存里存的內(nèi)容都是二進(jìn)制數(shù)，你將它解釋成什么，它就是什么12.1從基本數(shù)據(jù)類型到抽象數(shù)據(jù)類型3/65在高級語言引入基本數(shù)據(jù)類型的目的有效地組織數(shù)據(jù)，規(guī)范數(shù)據(jù)的使用，提高程序的可讀性不同語言會定義不同的基本類型高級語言中預(yù)先定義的類型是遠(yuǎn)遠(yuǎn)不夠的有些語言（如PL/1）中試圖規(guī)定較多的類型，如數(shù)組、樹、棧等，但實踐證明不是個好辦法12.1從基本數(shù)據(jù)類型到抽象數(shù)據(jù)類型4/65有沒有一種類型能很好地定義學(xué)生（包括姓名、學(xué)號、性別、年齡等信息）呢？有沒有一種類型能很好地定義紙牌（包括花色和牌面）呢？C語言允許用戶自定義數(shù)據(jù)類型典型的代表就是“結(jié)構(gòu)體”一種構(gòu)造數(shù)據(jù)類型12.1從基本數(shù)據(jù)類型到抽象數(shù)據(jù)類型5/65有沒有一種類型能定義車呢？除車的屬性，還包括對車的操作（啟動、加速、減速、剎車等）抽象數(shù)據(jù)類型（AbstractDataType,ADT）不單純是數(shù)據(jù)的集合，增加了對數(shù)據(jù)的操作類型的表示和操作的實現(xiàn)細(xì)節(jié)對外是不可見的能達(dá)到更好的信息隱藏效果12.1從基本數(shù)據(jù)類型到抽象數(shù)據(jù)類型6/65C++中的類(Class)結(jié)構(gòu)體可看成是所有成員都是public的類但不能將C++看成是帶類的C，是思考問題角度的轉(zhuǎn)變面向過程(ProcessOriented)分析問題的處理步驟，通過函數(shù)（過程）調(diào)用處理問題以功能為中心來設(shè)計功能模塊面向?qū)ο?ObjectOriented)將問題分解為對象，而不是步驟建立對象的目的不是為了完成一個步驟，數(shù)據(jù)為中心以對象為基礎(chǔ)，以事件或消息來驅(qū)動對象執(zhí)行操作12.1從基本數(shù)據(jù)類型到抽象數(shù)據(jù)類型7/6512.2.1為什么要定義結(jié)構(gòu)體類型在程序里表示一個人（姓名、性別、年齡…），怎么表示？想表示多個人呢？如何用計算機程序?qū)崿F(xiàn)下述表格的管理？8/65數(shù)組的解決方法12.2.1為什么要定義結(jié)構(gòu)體類型9/6512.2.1為什么要定義結(jié)構(gòu)體類型10/65數(shù)組的解決方法分配內(nèi)存不集中，尋址效率不高對數(shù)組賦初值時，易發(fā)生錯位結(jié)構(gòu)零散，內(nèi)存管理困難12.2.1為什么要定義結(jié)構(gòu)體類型11/65希望的內(nèi)存分配圖12.2.1為什么要定義結(jié)構(gòu)體類型12/65結(jié)構(gòu)體類型的聲明聲明了一個結(jié)構(gòu)體類型構(gòu)成結(jié)構(gòu)體的變量稱為結(jié)構(gòu)體的成員(StructureMember)結(jié)構(gòu)體的名字稱為結(jié)構(gòu)體標(biāo)簽(StructureTag)13/65結(jié)構(gòu)體類型的聲明結(jié)構(gòu)體模板(StructureTemplate)形成一個類型聲明的樣板用于生成結(jié)構(gòu)體變量但并未定義任何結(jié)構(gòu)體變量因而編譯器不為其分配內(nèi)存

14/65結(jié)構(gòu)體類型的聲明定義為何種類型更好？15/65（1）先定義結(jié)構(gòu)體類型再定義變量名（2）在定義結(jié)構(gòu)體類型的同時定義變量（3）直接定義結(jié)構(gòu)體變量（不指定結(jié)構(gòu)體標(biāo)簽）12.2.2結(jié)構(gòu)體變量的定義16/6512.2.3用typedef定義數(shù)據(jù)類型名structstudentstu1,stu2;/*Itworks*/STUDENT

stu1,stu2;

/*Itworks!*/student

stu1,stu2;/*Canthiswork?*/struct

stu1,stu2;/*Canthiswork?*/關(guān)鍵字typedef為一種已存在的類型定義一個別名，并未定義新類型structstudent與STUDENT類型是同義詞17/65等價于12.2.4結(jié)構(gòu)體變量的初始化18/65結(jié)構(gòu)體定義可嵌套——嵌套的結(jié)構(gòu)體（NestedStructure）在一個結(jié)構(gòu)體內(nèi)包含了另一個結(jié)構(gòu)體作為其成員12.2.5嵌套的結(jié)構(gòu)體19/65訪問結(jié)構(gòu)體變量的成員成員選擇運算符（也稱圓點運算符）12.2.6結(jié)構(gòu)體變量的引用對嵌套的結(jié)構(gòu)體成員，必須以級聯(lián)方式訪問STUDENT

stu1;

20/65等價于注意！12.2.6結(jié)構(gòu)體變量的引用21/65【例12.1】演示結(jié)構(gòu)體變量的賦值和引用方法按結(jié)構(gòu)體的成員順序逐一對相應(yīng)成員進(jìn)行賦值格式符%02d中2d前面的前導(dǎo)符0表示輸出數(shù)據(jù)時，若左邊有多余位，則補012.2.6結(jié)構(gòu)體變量的引用22/65

若不用初始化的方法，而用從鍵盤輸入的方法輸入結(jié)構(gòu)體變量stu1的內(nèi)容，那么程序如何修改？兩個地址有何不同？23/65結(jié)構(gòu)體成員的地址與該成員在結(jié)構(gòu)體中所處的位置及其所占內(nèi)存的字節(jié)數(shù)相關(guān)結(jié)構(gòu)體變量的地址&stu2是該變量所占內(nèi)存空間的首地址24/6512.2.7結(jié)構(gòu)體所占內(nèi)存的字節(jié)數(shù)struct

類型用內(nèi)存字節(jié)數(shù)=?是所有成員占內(nèi)存的總和嗎？printf("%d\n",sizeof(struct

sample));用sizeof獲得結(jié)構(gòu)體大小sizeof(變量或表達(dá)式)sizeof(類型)12Why?printf("%d\n",sizeof(SAMPLE));【例12.2】typedefstructsample{charm1;intm2;charm3;}SAMPLE;25/65結(jié)構(gòu)體實際所占的內(nèi)存空間一般是按照機器字長對齊的不同的系統(tǒng)和編譯器，內(nèi)存對齊(Memory-alignment)方式不同為了滿足處理器的對齊要求，可能會在較小的成員后加入補位非所有成員變量的內(nèi)存總和m1m2m3結(jié)構(gòu)體變量的成員的內(nèi)存對齊方式是與機器相關(guān)的所以結(jié)構(gòu)體在內(nèi)存中所占的字節(jié)數(shù)也是與機器相關(guān)的m1m3m212.2.7結(jié)構(gòu)體所占內(nèi)存的字節(jié)數(shù)26/6532位體系結(jié)構(gòu)中，int值被對齊在4字節(jié)地址邊界，保證了一個int型數(shù)總能通過一次內(nèi)存操作被訪問到，每次內(nèi)存訪問是在4字節(jié)對齊的地址處讀取或存入32位整數(shù)讀取存儲在沒有對齊的地址處的32位整數(shù)，需兩次內(nèi)存訪問，且從取到的64位中提取相關(guān)的32位需額外的操作，性能下降m1m3m2m1m2m312.2.7結(jié)構(gòu)體所占內(nèi)存的字節(jié)數(shù)為什么要滿足內(nèi)存對齊的要求呢?27/65typedefstructsample{

charm1;

intm2;

charm3;}SAMPLE;typedefstructsample{

charm1;

charm3;

intm2;

}SAMPLE;m1m3m2printf("%d\n",sizeof(SAMPLE));？m1m3m212.2.7結(jié)構(gòu)體所占內(nèi)存的字節(jié)數(shù)28/6512.3結(jié)構(gòu)體數(shù)組的定義和初始化29/65建立了數(shù)據(jù)庫中的多條記錄，每條對應(yīng)一個學(xué)生信息12.3結(jié)構(gòu)體數(shù)組的定義和初始化30/65

【例12.3】利用結(jié)構(gòu)體數(shù)組，計算每個學(xué)生的平均分31/6512.4結(jié)構(gòu)體指針的定義和初始化ptstu1

STUDENT

stu1;

STUDENT

*pt;pt=&stu1;成員1成員2成員3成員4成員5如何定義指向結(jié)構(gòu)體變量的指針？

STUDENT

*pt=&stu1;等價于32/65如何訪問結(jié)構(gòu)體指針變量指向的結(jié)構(gòu)體成員呢？ptstu1成員1成員2成員3成員4成員5通過成員選擇運算符訪問(*pt).studentID=1;

stu1.studentID=1;通過指向運算符訪問pt->studentID=1;12.4結(jié)構(gòu)體指針的定義和初始化33/65ptstu1成員1成員2成員3成員4成員5當(dāng)結(jié)構(gòu)體嵌套時，如何訪問結(jié)構(gòu)體指針變量所指向的結(jié)構(gòu)體成員？

stu1.

birthday.

year=1999;(*pt).

birthday.

year=1999;

pt->

birthday.

year=1999;12.4結(jié)構(gòu)體指針的定義和初始化34/65

STUDENT

stu[30];

STUDENT

*pt;pt=stu;

如何定義指向結(jié)構(gòu)體數(shù)組的指針？

STUDENT

*pt=stu;等價于STUDENT

*pt=&stu[0];等價于ptstu[30]stu[0]stu[1]stu[2]stu[3]stu[4]stu[5]......stu[29]12.4結(jié)構(gòu)體指針的定義和初始化35/65使用pt++，使pt指向stu[1]pt->studentID等價于

stu[1].studentIDpt如何訪問結(jié)構(gòu)體指針指向的結(jié)構(gòu)體數(shù)組成員？stu[30]stu[0]stu[1]stu[2]stu[3]stu[4]stu[5]......stu[29]12.4結(jié)構(gòu)體指針的定義和初始化36/6512.5向函數(shù)傳遞結(jié)構(gòu)體向函數(shù)傳遞結(jié)構(gòu)體的單個成員復(fù)制單個成員的內(nèi)容向函數(shù)傳遞結(jié)構(gòu)體的完整結(jié)構(gòu)復(fù)制結(jié)構(gòu)體的所有成員向函數(shù)傳遞結(jié)構(gòu)體的首地址僅復(fù)制一個地址值37/65Beforefunctioncall:1999/04/23Afterfunctioncall:1999/04/23結(jié)構(gòu)體變量作函數(shù)參數(shù)intmain(void){

structdated;d.year=1999;d.month=4;d.day=23;printf("Beforefunctioncall:%d/%02d/%02d\n",d.year,d.month,d.day);

Func(d);/*結(jié)構(gòu)體變量作函數(shù)實參，傳值調(diào)用*/printf("Afterfunctioncall:%d/%02d/%02d\n",d.year,d.month,d.day);return0;}structdate{

intyear;

intmonth;

intday;};voidFunc(struct

datep){

p.year=2000;

p.month=5;

p.day=22;}

【例12.4】函數(shù)對結(jié)構(gòu)體內(nèi)容的修改不影響原結(jié)構(gòu)體38/65intmain(void){

structdated;d.year=1999;d.month=4;d.day=23;printf("Beforefunctioncall:%d/%02d/%02d\n",d.year,d.month,d.day);

Func(&d);/*結(jié)構(gòu)體變量的地址作函數(shù)實參，傳地址調(diào)用*/printf("Afterfunctioncall:%d/%02d/%02d\n",d.year,d.month,d.day);return0;}Beforefunctioncall:1999/04/23Afterfunctioncall:2000/05/22結(jié)構(gòu)體指針

作函數(shù)參數(shù)

【例12.5】結(jié)構(gòu)體指針作函數(shù)形參實參必須為地址值structdate{

intyear;

intmonth;

intday;};voidFunc(struct

date*p){

p->year=2000;

p->month=5;

p->day=22;}39/65結(jié)構(gòu)體變量

做函數(shù)返回值intmain(void){

structdated;d.year=1999;d.month=4;d.day=23;printf("Beforefunctioncall:%d/%02d/%02d\n",d.year,d.month,d.day);

d=Func(d);/*結(jié)構(gòu)體變量作函數(shù)實參，傳值調(diào)用*/printf("Afterfunctioncall:%d/%02d/%02d\n",d.year,d.month,d.day);return0;}structdate{

intyear;

intmonth;

intday;};structdateFunc(struct

datep){

p.year=2000;

p.month=5;

p.day=22;returnp;}

【例12.6】返回結(jié)構(gòu)體變量的值也可以得到修改的結(jié)構(gòu)體內(nèi)容，但效率低40/65

【例12.7】修改例12.3程序，用結(jié)構(gòu)體數(shù)組作函數(shù)參數(shù)編程計算并輸出學(xué)生的平均分aver放到結(jié)構(gòu)體成員中精簡參數(shù)傳遞個數(shù)使函數(shù)接口更簡潔結(jié)構(gòu)體作函數(shù)參數(shù)的好處？typedefstructstudent{longstudentID; charstudentName[10];charstudentSex; DATEbirthday; int score[4];

floataver; }STUDENT;41/65用戶自定義的數(shù)據(jù)類型結(jié)構(gòu)體（struct）把關(guān)系緊密且邏輯相關(guān)的多種不同類型的變量，組織到統(tǒng)一的名字之下共用體，也稱聯(lián)合（union）把情形互斥但邏輯相關(guān)的多種不同類型的變量，組織到統(tǒng)一的名字之下42/6512.6共用體structsample{

shorti;

charch;

floatf;};0x0037b00unionsample{

shorti;

charch;

floatf;};printf("%d\n",sizeof(structsample));8個字節(jié)ichf4個字節(jié)printf("%d\n",sizeof(unionsample));ichf

【例12.8】43/65sizeof(unionnumber)取決于占空間最多的那個成員變量0x0037b00同一內(nèi)存在每一瞬時只能存放其中一種類型的成員起作用的成員是最后一次存放的成員f4個字節(jié)12.6共用體44/6512.6共用體45/6512.6共用體46/6512.7枚舉數(shù)據(jù)類型枚舉（Enumeration）數(shù)據(jù)類型描述一組有限個數(shù)據(jù)值組成的整型值的集合基本數(shù)據(jù)類型

enumweeks{SUN,MON,TUE,WED,THU,FRI,SAT};

enumweekstoday; today=TUE;//值為2

enumresponse{no,yes,none};

enumresponseanswer;

answer=no;

//值為0

enumresponse{no=-1,yes=1,none=0};

47/65下面的結(jié)構(gòu)是什么意思？

structtemp

{

int data;

structtemppt;

};CB下的錯誤提示：field'pt'hasincompletetypeVC下的錯誤提示：'pt'usesundefinedstruct'temp'結(jié)構(gòu)體聲明時不能包含本結(jié)構(gòu)體類型的成員系統(tǒng)無法預(yù)知這樣的結(jié)構(gòu)體需要占據(jù)多少內(nèi)存

12.8動態(tài)數(shù)據(jù)結(jié)構(gòu)——單向鏈表48/65下面的結(jié)構(gòu)是什么意思？

structtemp

{

intdata;

structtemppt;

};下面的結(jié)構(gòu)是什么意思呢？

structtemp

{

intdata;

structtemp*pt;

};這樣的結(jié)構(gòu)體類型有什么用呢？12.8動態(tài)數(shù)據(jù)結(jié)構(gòu)——單向鏈表可包含指向本結(jié)構(gòu)體類型的指針變量49/65structlink{

int data;

structlink*next;};動態(tài)數(shù)據(jù)結(jié)構(gòu)的典型代表——鏈表（LinkedTable）特點：用一組任意的存儲單元存儲線性表數(shù)據(jù)存儲單元可以是連續(xù)的，也可以是不連續(xù)的12.8動態(tài)數(shù)據(jù)結(jié)構(gòu)——單向鏈表data=Anodedata=Bnodedata=C∧nodehead空指針NULL表示鏈表結(jié)尾頭指針：訪問鏈表的關(guān)鍵數(shù)據(jù)域：存儲節(jié)點的數(shù)據(jù)信息指針域：存儲直接后繼信息n個節(jié)點鏈接成一個表——線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)因只包含一個指針域，故又稱線性鏈表或單向鏈表50/65向鏈表中添加節(jié)點若原鏈表為空表(head==NULL)，則將新建節(jié)點p置為頭節(jié)點head(1)head=pdatanextp新建節(jié)點(2)pr=p∧pr(3)pr->next=NULLp=(structlink*)malloc(sizeof(structlink));p->data=nodeData;51/65datanext新建節(jié)點p向鏈表中添加節(jié)點若原鏈表為非空，則將新建節(jié)點p添加到表尾(1)pr->next=p(2)pr=p∧headdata∧prpr(3)pr->next=NULLnext52/65鏈表的刪除操作若原鏈表為空表，則退出程序若待刪除節(jié)點p是頭節(jié)點，則將head指向當(dāng)前節(jié)點的下一個節(jié)點即可刪除當(dāng)前節(jié)點

datanext(1)head=p->nexthead待刪除節(jié)點datanextp頭節(jié)點(2)free(p)53/65鏈表的刪除操作若待刪除節(jié)點不是頭節(jié)點，則將前一節(jié)點的指針域指向當(dāng)前節(jié)點的下一節(jié)點(1)pr->next=p->nextdatanextdatanext待刪除節(jié)點datanextp中間節(jié)點datanext若已搜索到表尾（p->next==NULL）仍未找到待刪除節(jié)點，則顯示“未找到”(2)free(p)pr54/65鏈表的插入操作若原鏈表為空表，則將新節(jié)點p作為頭節(jié)點，讓head指向新節(jié)點p

head待插入節(jié)點data∧p(1)head=p(2)p->next=NULL55/65鏈表的插入操作若原鏈表為非空，則按節(jié)點值的大小（假設(shè)已升序排序）確定插入新節(jié)點的位置若在頭節(jié)點前插入節(jié)點，則將新節(jié)點的指針域指向原鏈表的頭節(jié)點，且讓head指向新節(jié)點head待插入節(jié)點datanextp(2)head=pdatanextdatanextdata∧(1)p->next=head56/65datanext鏈表的插入操作若在鏈表中間插入新節(jié)點，則將新節(jié)點的指針域指向下一節(jié)點且讓前一節(jié)點的指針域指向新節(jié)點待插入節(jié)點datanextp(2)pr->next=pdatanextdatanextdata∧(1)p->next=pr->nextpr57/65datanext鏈表的插入操作若在表尾插入新節(jié)點，則末節(jié)點指針域指向新節(jié)點待插入節(jié)點datanextp(1)pr->next=pprdata∧原末節(jié)點next∧(2)p->next=NULL58/65雙向鏈表structDNode{

int data;

structDNode*prior,*next;//分別指向前驅(qū)和后繼節(jié)點};structlink{

int data;

structlink*next;};3next2next1next4∧head3nextprior3next∧head3prior3nextprior∧單循環(huán)鏈表structlink{

int data;

structlink*next;};類型定義相似，但初始化和刪除后繼節(jié)點的操作實現(xiàn)不同3next2next1next4∧head12.9.1棧和隊列//隊列的鏈?zhǔn)酱鎯ypedefstructqueue{intdata;

structqueue*front;//指向隊頭

structqueue*rear;//指向隊尾}QUEUE;//隊列的順序存儲typedefstructqueue{intdata[Max];intfront；//控制隊頭intrear;//控制隊尾}QUEUE;//棧的順序存儲typedefstructstack{intdata[Max];inttop;//控制棧頂}STACK;//棧的鏈?zhǔn)酱鎯ypedefstructstack{intdata;

structstack*next;//指向棧頂}STACK;棧的應(yīng)用實例：計算逆波蘭表達(dá)式中綴表示：二元運算符置于兩個運算對象之間a+b后綴表示：運算符置于其運算對象之后，逆波蘭表達(dá)式ab+

a+babc+d*+

a+(b+c)*dabcab+cab+cda(b+c)*da+(b+c)*d棧的應(yīng)用實例：計算逆波蘭表達(dá)式intmain(void){charword[N];NodeTyped1,d2,d3;STACKstack;stack.top=0;//初始化棧頂while(scanf("%s",word)==1&&word[0]!='#'){if(isdigit(word[0]))

{d1.ival=atoi(word);

Push(&stack,d1);}else

{d2=Pop(&stack);d1=Pop(&stack);d3=OpData(&d1,&d2,word[0]);Push(&stack,d3);}}d1=Pop(&stack);//彈出棧頂保存的最終計算結(jié)果

printf("%d\n",d1.ival);return0;}typedefstruct

data{inttype;//數(shù)據(jù)類型

union{intival;}dat;//數(shù)據(jù)的值}NodeType;typedefstructstack{NodeTypedata[N];inttop;//控制棧頂}STACK;//棧的順序存儲如何輸入逆波蘭表達(dá)式356+2*+棧的應(yīng)用實例：計算逆波蘭表達(dá)式//函數(shù)功能：彈出棧頂數(shù)據(jù)并返回NodeTypePop(STACK*stack){stack->top=stack->top-1;returnstack->data[stack->top];}1002003004005000*pPushPop//函數(shù)功能：將數(shù)據(jù)data壓入堆棧voidPush(STACK*stack,NodeTypedata){memcpy(&stack->data[stack->top],&data,sizeof(NodeType));stack->top=stack->top+1;}*pPush(&stack,d1);//入棧d2=Pop(&stack);//出棧棧的應(yīng)用實例：計算逆波蘭表達(dá)式//函數(shù)功能：對d1和d2執(zhí)行運算op，并返回計算結(jié)果NodeTypeOpData(NodeType*d1,NodeType*d2,intop){NodeTyperes;res=OpInt(d1->ival,d2->ival,op);returnres;}//函數(shù)功能：對整型的數(shù)據(jù)d1和d2執(zhí)行運算op，并返回計算結(jié)果NodeTypeOpInt(intd1,intd2,intop){NodeTyperes;switch(op){case'+':res.ival=d1+d2;break;case'-':res.ival=d1-d2;break;case'*':res.ival=d1*d2;break;case'/':res.ival=d1/d2;break;}returnres;}循環(huán)隊列的應(yīng)用實例：舞伴配對假設(shè)在大學(xué)生的周末舞會上，男、女學(xué)生各自排成一隊。舞會開始時，依次從男隊和女隊的隊頭各出一人配成舞伴。如果兩隊初始人數(shù)不等，則較長的那一隊中未配對者等待下一輪舞曲。要求男、女學(xué)生人數(shù)及其姓名以及舞會的輪數(shù)，由用戶從鍵盤輸入，屏幕輸出每一輪舞伴的配對名單，如果在該輪有未配對的，能夠從屏幕顯示下一輪第一個出場的未配對者的姓名。避免“假滿”問題循環(huán)隊列的應(yīng)用實例：舞伴配對//函數(shù)功能：創(chuàng)建一個隊列voidCreatQueue(QUEUE*Q){intn,i;Q->front=Q->rear=0;printf("請輸入跳舞人數(shù)：");scanf("%d",&n);Q->qSize=n+1;printf("請輸入各舞者人名：");for(i=0;i<n;i++){scanf("%s",Q->elem[i]);}Q->rear=n;}循環(huán)隊列的應(yīng)用實例：舞伴配對//函數(shù)功能：循環(huán)隊列出隊，即刪除隊首元素voidDeQueue(QUEUE*Q,char*str){strcpy(str,Q->elem[Q->front]);Q->front=(Q->front+1)%Q->qSize;}//函數(shù)功能：判斷循環(huán)隊列是否為空intQueueEmpty(constQUEUE*Q){if(Q->front==Q->rear)//隊列為空

return1;elsereturn0;}//函數(shù)功能：取出隊首元素，隊頭指針不改變voidGetQueue(constQUEUE*Q,char*str){strcpy(str,Q->elem[Q->front]);}循環(huán)隊列的應(yīng)用實例：舞伴配對intmain(void){QUEUEman,women;printf("男隊：\n");CreatQueue(&man);printf("女隊：\n");CreatQueue(&women);DancePartners(&man,&women);return0;}//函數(shù)功能：根據(jù)隊列長短確定如何調(diào)用舞伴配對函數(shù)voidDancePartners(QUEUE*man,QUEUE*women){if(man->qSize<women->qSize){Match(man,women);}else{Match(women,man);}}循環(huán)隊列的應(yīng)用實例：舞伴配對//函數(shù)功能：舞伴配對voidMatch(QUEUE*shortQ,QUEUE*longQ){intn;charstr1[N],str2[N];printf("請輸入舞會的輪數(shù)：");scanf("%d",&n);while(n--)//循環(huán)n輪次

{while(!QueueEmpty(shortQ))//短隊列不為空

{if(QueueEmpty(longQ)){longQ->front=(longQ->front+1)%longQ->qSize;}DeQueue(shortQ,str1);DeQueue(longQ,str2);printf("配對的舞者：%s%s\n",str1,str2);}shortQ->front=(shortQ->front+1)%shortQ->qSize;if(QueueEmpty(longQ)){longQ->front=(longQ->front+1)%longQ->qSize;}GetQueue(longQ,str1);printf("第一個出場的未配對者的姓名：%s\n",str1);}}12.9.2樹和圖結(jié)構(gòu)中數(shù)據(jù)元素（節(jié)點）之間存在一對多的層次關(guān)系typedefstructBiTNode{ intdata; structBiTNode*lchild;//左子樹 structBiTNode*rchild;//右子樹}BI_TREE;二叉樹二叉樹的特點1）每個結(jié)點最多有兩棵子樹。2）左子樹和右子樹是有序的。3）即使樹中某結(jié)點只有一棵子樹，也要區(qū)分它是左子樹還是右子樹。4）二叉樹有5種基本形態(tài)：空樹，只有一個根結(jié)點，根結(jié)點只有左子樹，根結(jié)點只有右子樹，根結(jié)點既有左子樹也有右子樹。典型的遞歸數(shù)據(jù)結(jié)構(gòu)要么為空要么由根結(jié)點、左右子樹組成，而左、右子樹分別是一棵二叉樹二叉樹的遍歷操作124536742516374526731typedefstructBiTNode{ intdata; structBiTNode*lchild;//左子樹 structBiTNode*rchild;//右子樹}BI_TREE;二叉樹的遍歷操作//函數(shù)功能：二叉樹先序遍歷intPreOrderTraverse(BI_TREE*root,void(*visit)(int)){ if(root==NULL) { return1; } (*visit)(root->data); if(PreOrderTraverse(root->lchild,visit)) {