第8章74數(shù)據(jù)封裝結(jié)構(gòu)體

第8章數(shù)據(jù)封裝—結(jié)構(gòu)體結(jié)構(gòu)體的概述結(jié)構(gòu)體類型的定義結(jié)構(gòu)體類型的變量結(jié)構(gòu)體數(shù)組結(jié)構(gòu)體作為函數(shù)的參數(shù)鏈表結(jié)構(gòu)體的概念打印學(xué)生成績單，格式如下：學(xué)號(hào)姓名語文成績數(shù)學(xué)成績英語成績.00001張三96948800003李四89707600004王五908778如何在程序中表示這組學(xué)生信息？可選方案用二維的數(shù)組來表示該方案不可行，因?yàn)檫@些信息有不同的類型每一列用一個(gè)一維數(shù)組來表示，這種方法稱為并聯(lián)數(shù)組。要保證每位學(xué)生信息的正確性很難為什么要使用記錄當(dāng)我們考慮怎么邏輯地組織數(shù)據(jù)時(shí)，應(yīng)該將一個(gè)人的所有信息項(xiàng)放在一起，即保持相關(guān)性。學(xué)號(hào)姓名語文成績數(shù)學(xué)成績英語成績.00001張三96948800003李四89707600004王五908778我

們

希

望

的

結(jié)

構(gòu)學(xué)生一00001張三969488學(xué)生二00003李四897076學(xué)生三00004王五908778記錄在C++中稱為結(jié)構(gòu)體結(jié)構(gòu)體類型作用結(jié)構(gòu)體類型允許程序員把一些分量聚合成一個(gè)整體，用一個(gè)變量表示。一個(gè)結(jié)構(gòu)體的各個(gè)分量都有名字，把這些分量稱為成員(member)。由于結(jié)構(gòu)體的成員可以是各種類型的，程序員能創(chuàng)建適合于問題的數(shù)據(jù)聚合。結(jié)構(gòu)體的使用定義一個(gè)新的結(jié)構(gòu)體類型定義新類型的變量訪問結(jié)構(gòu)體變量第8章數(shù)據(jù)封裝—結(jié)構(gòu)體結(jié)構(gòu)體的概述結(jié)構(gòu)體類型的定義結(jié)構(gòu)體類型的變量結(jié)構(gòu)體數(shù)組結(jié)構(gòu)體作為函數(shù)的參數(shù)鏈表結(jié)構(gòu)體類型的定義定義結(jié)構(gòu)體類型中包括哪些分量格式：struct結(jié)構(gòu)體類型名{字段聲明；}；如：structstudentT{charno[10];charname[10];intchinese;intmath;intenglish;};注意字段名可與程序中的變量名相同在不同的結(jié)構(gòu)體中可以有相同的字段名結(jié)構(gòu)體成員的類型可以是任意類型，當(dāng)然也可以是結(jié)構(gòu)體類型structdateT{ intmonth; intday; intyear;};structstudentT{ ... dateTbirthday;};

第8章數(shù)據(jù)封裝—結(jié)構(gòu)體結(jié)構(gòu)體的概述結(jié)構(gòu)體類型的定義結(jié)構(gòu)體類型的變量結(jié)構(gòu)體數(shù)組結(jié)構(gòu)體作為函數(shù)的參數(shù)鏈表結(jié)構(gòu)體類型的變量結(jié)構(gòu)體變量的定義結(jié)構(gòu)體類型的引用指向結(jié)構(gòu)體的指針動(dòng)態(tài)分配結(jié)構(gòu)體的空間結(jié)構(gòu)體變量的定義結(jié)構(gòu)體變量的定義和普通的變量定義一樣。如定義了結(jié)構(gòu)體類型studentT，就可以定義結(jié)構(gòu)體變量：studentTstudent1;一旦定義了一個(gè)結(jié)構(gòu)體類型的變量，系統(tǒng)在分配內(nèi)存時(shí)就會(huì)分配一塊連續(xù)的空間，依次存放它的每一個(gè)分量。這塊空間總的名字就是結(jié)構(gòu)體變量的名字。內(nèi)部還有各自的名字

englishmathchinesenamenostudent1結(jié)構(gòu)體變量的初始化studentTstudent1={“00001”，“張三”，87，90，77}；

定義結(jié)構(gòu)體類型的同時(shí)定義變量struct結(jié)構(gòu)體類型名{字段聲明；}結(jié)構(gòu)體變量；struct{字段聲明；}結(jié)構(gòu)體變量；區(qū)別：前者可以繼續(xù)用結(jié)構(gòu)體類型名定義變量結(jié)構(gòu)體類型的變量結(jié)構(gòu)體變量的定義結(jié)構(gòu)體類型的引用指向結(jié)構(gòu)體的指針動(dòng)態(tài)分配結(jié)構(gòu)體的空間結(jié)構(gòu)體變量的訪問成員的表示：

結(jié)構(gòu)變量名.成員名

如:

如結(jié)構(gòu)中還有結(jié)構(gòu)，則一級(jí)一級(jí)用”.”分開，如如：student1.birthday.year對結(jié)構(gòu)體類型變量的引用一般為引用他的成員結(jié)構(gòu)變量的賦值結(jié)構(gòu)體是一個(gè)統(tǒng)稱。每個(gè)結(jié)構(gòu)體類型在使用前都要先定義自己有哪些分量。系統(tǒng)事先無法知道如何處理他。因此，結(jié)構(gòu)體變量的賦值通常是通過對它的每一個(gè)成員的賦值而實(shí)現(xiàn)。如：輸入student1的內(nèi)容可用：cin>>student1.no>>>>student1.chinese>>student1.math>>student1.english>>student1.birthday.year>>student1.birthday.month>>student1.birthday.day;同類型的結(jié)構(gòu)變量之間可以相互賦值，如Student1=student2;將student2的成員對應(yīng)賦給student1的成員結(jié)構(gòu)變量的輸出結(jié)構(gòu)體變量的輸出通常是通過輸出它的每一個(gè)成員而實(shí)現(xiàn)。如：輸出student1的內(nèi)容可用：cout<<student1.no<<<<student1.chinese<<student1.math<<student1.english<<student1.birthday.year<<student1.birthday.month<<student1.birthday.day;結(jié)構(gòu)體類型的變量結(jié)構(gòu)體變量的定義結(jié)構(gòu)體類型的引用指向結(jié)構(gòu)體的指針動(dòng)態(tài)分配結(jié)構(gòu)體的空間指向記錄的指針直接定義指針變量studentT*sp;也可以在定義結(jié)構(gòu)體類型的同時(shí)定義指向結(jié)構(gòu)體的指針struct結(jié)構(gòu)體類型名{字段聲明；}*結(jié)構(gòu)體指針；通過指針操作記錄給結(jié)構(gòu)體指針賦值，如：sp=&student1;結(jié)構(gòu)體指針的引用：(*指針).成員

如：(*sp).name指針->成員如：sp->namestudent1.成員

->是所有運(yùn)算符中優(yōu)先級(jí)最高的

通常程序員習(xí)慣使用第二種方法結(jié)構(gòu)體類型的變量結(jié)構(gòu)體變量的定義結(jié)構(gòu)體類型的引用指向結(jié)構(gòu)體的指針動(dòng)態(tài)分配結(jié)構(gòu)體的空間動(dòng)態(tài)分配結(jié)構(gòu)體的空間指向結(jié)構(gòu)體指針的另一種用法是存儲(chǔ)動(dòng)態(tài)申請到的內(nèi)存的首地址。用法和申請普通的動(dòng)態(tài)變量一樣。如：studentT*sp;sp=newstudentT;第8章數(shù)據(jù)封裝—結(jié)構(gòu)體結(jié)構(gòu)體的概述結(jié)構(gòu)體類型的定義結(jié)構(gòu)體類型的變量結(jié)構(gòu)體數(shù)組結(jié)構(gòu)體作為函數(shù)的參數(shù)鏈表

結(jié)構(gòu)體數(shù)組用于描述個(gè)體的集合定義格式：studentTstudentArray[SIZE];結(jié)構(gòu)體數(shù)組的引用引用數(shù)組的某一成員的成員studentArray[3].name數(shù)組成員之間相互賦值studentArray[4]=studentArray[2]結(jié)構(gòu)數(shù)組的初始化studentTstudentArray[5]={{“00001”,張三“,80,90,98},{…},{…},{…}};統(tǒng)計(jì)候選人得票。設(shè)有三個(gè)候選人，每次輸入一個(gè)得票的候選人名字，要求最后輸出各人得票結(jié)果。

structpersonT{intid;intcount;}leader[3]={0,0,1,0,2,0};

intmain(){inti,j,inputID;for(i=1;i<=10;++i){cin>>inputID;if(inputID<0||inputID>2){cout<<“廢票”；continue；}leader[inputID].count+=1;}cout<<endl;for(i=0;i<3;++i)cout<<leader[i].id<<““<<leader[i].count);return0;}

指針與結(jié)構(gòu)體數(shù)組與普通的指針一樣，指向結(jié)構(gòu)體的指針也能夠用來指向一個(gè)結(jié)構(gòu)體數(shù)組。此時(shí)，對指針加1就是加了該結(jié)構(gòu)體的大小。第8章數(shù)據(jù)封裝—結(jié)構(gòu)體結(jié)構(gòu)體的概述結(jié)構(gòu)體類型的定義結(jié)構(gòu)體類型的變量結(jié)構(gòu)體數(shù)組結(jié)構(gòu)體作為函數(shù)的參數(shù)鏈表結(jié)構(gòu)體作為參數(shù)傳遞盡管結(jié)構(gòu)體和數(shù)組一樣也有許多分量組成，但結(jié)構(gòu)體的傳遞和普通內(nèi)置類型是一樣的。它是將實(shí)際參數(shù)中的每個(gè)分量復(fù)制到形式參數(shù)的每個(gè)分量中。結(jié)構(gòu)體的傳遞VoidprintPerson(PersonTp)指向結(jié)構(gòu)體的指針作為參數(shù)因?yàn)榻Y(jié)構(gòu)體是值傳遞，當(dāng)希望把函數(shù)內(nèi)部對結(jié)構(gòu)體的修改返回給主調(diào)函數(shù)時(shí)，可以用指針傳遞或引用傳遞由于結(jié)構(gòu)體一般占用的內(nèi)存量都比較大，值傳遞既浪費(fèi)空間又浪費(fèi)時(shí)間。因此可用指針傳遞或引用傳遞指針傳遞形式比較繁瑣，所以C++通常用引用傳遞引用傳遞的問題是函數(shù)中可以修改實(shí)際參數(shù)，要控制函數(shù)中不能修改實(shí)際參數(shù)，可以加const限定指向結(jié)構(gòu)體的指針作為參數(shù)和普通的指針傳遞一樣，函數(shù)中可以通過指針訪問主調(diào)函數(shù)的記錄減少函數(shù)調(diào)用時(shí)的數(shù)據(jù)傳遞量VoidPrintPerson(personT&p);VoidPrintPerson(constpersonT&p);結(jié)構(gòu)體傳遞的實(shí)例設(shè)計(jì)一函數(shù)，打印學(xué)生信息設(shè)計(jì)一：值傳遞VoidPrintStudent(studentTs){cout<<s.no<<‘\t’<<<<‘\t’<<s.chinese<<‘\t’<<s.math<<‘\t’<<s.english<<endl;}缺點(diǎn)：浪費(fèi)時(shí)間空間設(shè)計(jì)二：指針傳遞或引用傳遞VoidPrintStudent(studentT*s){cout<<s->no<<‘\t’<<s->name<<‘\t’<<s->chinese<<‘\t’<<s->math<<‘\t’<<s->english<<endl;}VoidPrintStudent(studentT&s){cout<<s.no<<‘\t’<<<<‘\t’<<s.chinese<<‘\t’<<s.math<<‘\t’<<s.english<<endl;}缺點(diǎn)：不安全設(shè)計(jì)三：C++的常規(guī)做法VoidPrintStudent(conststudentT&s){cout<<s.no<<‘\t’<<<<‘\t’<<s.chinese<<‘\t’<<s.math<<‘\t’<<s.english<<endl;}特點(diǎn)：節(jié)約內(nèi)存，提高函數(shù)調(diào)用速度，可靠返回結(jié)構(gòu)體類型的函數(shù)一個(gè)函數(shù)返回一個(gè)結(jié)構(gòu)體。如：personTGetPersonData(void){personTperson;…….Return(person);}返回的是一個(gè)結(jié)構(gòu)體的復(fù)制。在主調(diào)函數(shù)中必須有這樣的程序段：Main(){personTp1,p2;p1=GetPersonData();}返回結(jié)構(gòu)體引用的函數(shù)函數(shù)返回一個(gè)結(jié)構(gòu)體的引用。如：personT&GetPersonData(void){personT*person=newpersonT;…….Return(*person);}本質(zhì)上返回的是結(jié)構(gòu)體的地址。在主調(diào)函數(shù)中可以有這樣的程序段：Main(){personT&p1=GetPersonData();…}

函數(shù)中返回的結(jié)構(gòu)體不能是局部變量第8章數(shù)據(jù)封裝—結(jié)構(gòu)體結(jié)構(gòu)體的概述結(jié)構(gòu)體類型的定義結(jié)構(gòu)體類型的變量結(jié)構(gòu)體數(shù)組結(jié)構(gòu)體作為函數(shù)的參數(shù)鏈表單鏈表鏈表的概念鏈表的存儲(chǔ)鏈表的操作循環(huán)鏈表單鏈表nilhead頭結(jié)點(diǎn)只指出后繼關(guān)系的鏈表雙鏈表

head循環(huán)鏈表

head同時(shí)存儲(chǔ)前趨和后繼單鏈表鏈表的概念鏈表的存儲(chǔ)鏈表的操作循環(huán)鏈表單鏈表的存儲(chǔ)structlinkRec{datatypedata;linkRec*next;}

存儲(chǔ)鏈表就是存儲(chǔ)鏈表中的一個(gè)節(jié)點(diǎn)的地址，因此需要定義一個(gè)節(jié)點(diǎn)類型單鏈表鏈表的概念鏈表的存儲(chǔ)鏈表的操作循環(huán)鏈表單鏈表操作—插入申請空間輸入數(shù)據(jù)放入申請到的空間鏈入p后在結(jié)點(diǎn)p后插入一個(gè)結(jié)點(diǎn)

headptmptmp=newLinkRec;//創(chuàng)建一個(gè)新節(jié)點(diǎn)tmp->data=x;//把x放入新節(jié)點(diǎn)的數(shù)據(jù)成員中tmp->next=p->next;//把新節(jié)點(diǎn)和p的下一成員相連p->next=tmp;//把p和新節(jié)點(diǎn)連接起來

單鏈表操作—?jiǎng)h除把結(jié)點(diǎn)p后的結(jié)點(diǎn)刪除headpdelPtrdelPtr=p->next;p->next=delPtr->next;deletedelPtr;

單鏈表操作--建立定義頭指針：linkRec*head;建立頭結(jié)點(diǎn)申請空間設(shè)為頭結(jié)點(diǎn)head單鏈表操作--建立（續(xù)）逐個(gè)從鍵盤輸入數(shù)據(jù)，存入鏈表

接受輸入申請空間輸入數(shù)據(jù)放入申請到的空間鏈入鏈表尾置鏈表結(jié)束標(biāo)志headabcd^head=newlinkRec;rear=head;Cin>>in_data;while(輸入未結(jié)束){p=newlinkRec;p->data=in_data;rear->next=p;rear=p;cin>>in_data;}rear->next=NULL;

單鏈表操作—輸出headabcd^p=head->next;while(p!=NULL){cout<<p->data;p=p->next;}

創(chuàng)建并訪問一個(gè)帶頭結(jié)點(diǎn)的、存儲(chǔ)整型數(shù)據(jù)的單鏈表，數(shù)據(jù)從鍵盤輸入，0為輸入結(jié)束標(biāo)志。#include<iostream>usingnamespacestd;

structlinkRec{intdata;linkRec*next;};intmain(){intx;//存放輸入的值linkRec*head,*p,*rear;

head=rear=newlinkRec;

while(true){//創(chuàng)建鏈表的其他結(jié)點(diǎn)cin>>x;if(x==0)break;p=newlinkRec; p->data=x;rear->next=p;rear=p; }

rear->next=NULL; //設(shè)置rear為表尾，其后沒有結(jié)點(diǎn)了

//讀鏈表cout<<"鏈表的內(nèi)容為：\n";p=head->next;while(p!=NULL){cout<<p->data<<'\t';p=p->next;}cout<<endl;

return0;}單鏈表鏈表的概念鏈表的存儲(chǔ)鏈表的操作循環(huán)鏈表例：n個(gè)人圍成一圈，從第一個(gè)人開始報(bào)數(shù)1、2、3。凡報(bào)到3者退出圈子。找出最后留在圈子中的人的序號(hào)。

解。用循環(huán)鏈表

01243head當(dāng)n=5時(shí)，其刪除的節(jié)點(diǎn)的順序?yàn)?，0，4，1，最后剩下的節(jié)點(diǎn)為3。

循環(huán)鏈表的應(yīng)用—約瑟夫環(huán)structnode{intdata;node*next;};intmain(){node*head,*p,*q;//head為鏈表頭intn,i;//輸入ncout<<"\ninputn:";cin>>n;//建立鏈表head=p=newnode;p->data=0;//p指向表尾for(i=1;i<n;++i){q=newnode;//q為當(dāng)前正在創(chuàng)建的節(jié)點(diǎn)q->data=i;p->next=q;p=q;//將q鏈入表尾}p->next=head;//頭尾相連

//刪除過程q=head;while(q->next!=q)//只要表非空{(diào)for(i=0;i<2;++i)//報(bào)數(shù)，{p=q;q=p->next;}p->next=q->next;//繞過節(jié)點(diǎn)qcout<<q->data<<'\t';//顯示被刪者的編號(hào)deleteq; //回收被刪者的空間q=p->next;//讓q指向報(bào)1的節(jié)點(diǎn)}//打印結(jié)果cout<<"\n最后剩下："<<q->data<<endl;return0;}

鏈表總結(jié)實(shí)現(xiàn)較復(fù)雜插入、刪除效率高，但查找第i個(gè)元素效率低無表滿的問題適合于動(dòng)態(tài)表總結(jié)本章介紹了結(jié)構(gòu)體作用：處理更復(fù)雜的數(shù)據(jù)使用：定義類型定義變量鏈表第9章模塊化開發(fā)自頂向下的分解模塊劃分庫的設(shè)計(jì)與實(shí)現(xiàn)庫的應(yīng)用猜硬幣的游戲功能：提供游戲指南；計(jì)算機(jī)隨機(jī)產(chǎn)生正反面，讓用戶猜，報(bào)告對錯(cuò)結(jié)果。重復(fù)此過程，直到用戶不想玩了為止。頂層分解程序要做兩件事：顯示程序指南；模擬玩游戲的過程。main(){顯示游戲介紹；玩游戲；}主程序的兩個(gè)步驟是相互獨(dú)立的兩個(gè)，沒有什么聯(lián)系，因此可設(shè)計(jì)成兩個(gè)函數(shù)：voidprn_instruction()voidplay(）intmain(){prn_instruction();play();return0;}prn_instruction的實(shí)現(xiàn)prn_instruction函數(shù)的實(shí)現(xiàn)非常簡單，只要一系列的輸出語句把程序指南顯示一下就可以了voidprn_instruction(){cout<<"這是一個(gè)猜硬幣正反面的游戲.\n";cout<<"我會(huì)扔一個(gè)硬幣，你來猜.\n";cout<<"如果猜對了，你贏，否則我贏。\n";}play函數(shù)的實(shí)現(xiàn)Play函數(shù)隨機(jī)產(chǎn)生正反面，讓用戶猜，報(bào)告對錯(cuò)結(jié)果，然后詢問是否要繼續(xù)玩voidplay(){charflag=‘y’;while(flag==‘Y’||flag==‘y’){coin=生成正反面;輸入用戶的猜測；if（用戶猜測==coin）報(bào)告本次猜測結(jié)果正確；else報(bào)告本次猜測結(jié)果錯(cuò)誤；}}play函數(shù)的細(xì)化生成正反面：如果用