第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)體的概念打印學生成績單，格式如下：學號姓名語文成績數(shù)學成績英語成績.00001張三96948800003李四89707600004王五908778如何在程序中表示這組學生信息？可選方案用二維的數(shù)組來表示該方案不可行，因為這些信息有不同的類型每一列用一個一維數(shù)組來表示，這種方法稱為并聯(lián)數(shù)組。要保證每位學生信息的正確性很難為什么要使用記錄當我們考慮怎么邏輯地組織數(shù)據(jù)時，應該將一個人的所有信息項放在一起，即保持相關(guān)性。學號姓名語文成績數(shù)學成績英語成績.00001張三96948800003李四89707600004王五908778我

們

希

望

的

結(jié)

構(gòu)學生一00001張三969488學生二00003李四897076學生三00004王五908778記錄在C++中稱為結(jié)構(gòu)體結(jié)構(gòu)體類型作用結(jié)構(gòu)體類型允許程序員把一些分量聚合成一個整體，用一個變量表示。一個結(jié)構(gòu)體的各個分量都有名字，把這些分量稱為成員(member)。由于結(jié)構(gòu)體的成員可以是各種類型的，程序員能創(chuàng)建適合于問題的數(shù)據(jù)聚合。結(jié)構(gòu)體的使用定義一個新的結(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)體成員的類型可以是任意類型，當然也可以是結(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)體的指針動態(tài)分配結(jié)構(gòu)體的空間結(jié)構(gòu)體變量的定義結(jié)構(gòu)體變量的定義和普通的變量定義一樣。如定義了結(jié)構(gòu)體類型studentT，就可以定義結(jié)構(gòu)體變量：studentTstudent1;一旦定義了一個結(jié)構(gòu)體類型的變量，系統(tǒng)在分配內(nèi)存時就會分配一塊連續(xù)的空間，依次存放它的每一個分量。這塊空間總的名字就是結(jié)構(gòu)體變量的名字。內(nèi)部還有各自的名字

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

定義結(jié)構(gòu)體類型的同時定義變量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)體的指針動態(tài)分配結(jié)構(gòu)體的空間結(jié)構(gòu)體變量的訪問成員的表示：

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

如:

如結(jié)構(gòu)中還有結(jié)構(gòu)，則一級一級用”.”分開，如如：student1.birthday.year對結(jié)構(gòu)體類型變量的引用一般為引用他的成員結(jié)構(gòu)變量的賦值結(jié)構(gòu)體是一個統(tǒng)稱。每個結(jié)構(gòu)體類型在使用前都要先定義自己有哪些分量。系統(tǒng)事先無法知道如何處理他。因此，結(jié)構(gòu)體變量的賦值通常是通過對它的每一個成員的賦值而實現(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的成員對應賦給student1的成員結(jié)構(gòu)變量的輸出結(jié)構(gòu)體變量的輸出通常是通過輸出它的每一個成員而實現(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)體的指針動態(tài)分配結(jié)構(gòu)體的空間指向記錄的指針直接定義指針變量studentT*sp;也可以在定義結(jié)構(gòu)體類型的同時定義指向結(jié)構(gòu)體的指針struct結(jié)構(gòu)體類型名{字段聲明；}*結(jié)構(gòu)體指針；通過指針操作記錄給結(jié)構(gòu)體指針賦值，如：sp=&student1;結(jié)構(gòu)體指針的引用：(*指針).成員

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

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

通常程序員習慣使用第二種方法結(jié)構(gòu)體類型的變量結(jié)構(gòu)體變量的定義結(jié)構(gòu)體類型的引用指向結(jié)構(gòu)體的指針動態(tài)分配結(jié)構(gòu)體的空間動態(tài)分配結(jié)構(gòu)體的空間指向結(jié)構(gòu)體指針的另一種用法是存儲動態(tài)申請到的內(nèi)存的首地址。用法和申請普通的動態(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ù)組用于描述個體的集合定義格式：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)計候選人得票。設有三個候選人，每次輸入一個得票的候選人名字，要求最后輸出各人得票結(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)體的指針也能夠用來指向一個結(jié)構(gòu)體數(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ù)的每個分量中。結(jié)構(gòu)體的傳遞VoidprintPerson(PersonTp)指向結(jié)構(gòu)體的指針作為參數(shù)因為結(jié)構(gòu)體是值傳遞，當希望把函數(shù)內(nèi)部對結(jié)構(gòu)體的修改返回給主調(diào)函數(shù)時，可以用指針傳遞或引用傳遞由于結(jié)構(gòu)體一般占用的內(nèi)存量都比較大，值傳遞既浪費空間又浪費時間。因此可用指針傳遞或引用傳遞指針傳遞形式比較繁瑣，所以C++通常用引用傳遞引用傳遞的問題是函數(shù)中可以修改實際參數(shù)，要控制函數(shù)中不能修改實際參數(shù)，可以加const限定指向結(jié)構(gòu)體的指針作為參數(shù)和普通的指針傳遞一樣，函數(shù)中可以通過指針訪問主調(diào)函數(shù)的記錄減少函數(shù)調(diào)用時的數(shù)據(jù)傳遞量VoidPrintPerson(personT&p);VoidPrintPerson(constpersonT&p);結(jié)構(gòu)體傳遞的實例設計一函數(shù)，打印學生信息設計一：值傳遞VoidPrintStudent(studentTs){cout<<s.no<<‘\t’<<<<‘\t’<<s.chinese<<‘\t’<<s.math<<‘\t’<<s.english<<endl;}缺點：浪費時間空間設計二：指針傳遞或引用傳遞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;}缺點：不安全設計三：C++的常規(guī)做法VoidPrintStudent(conststudentT&s){cout<<s.no<<‘\t’<<<<‘\t’<<s.chinese<<‘\t’<<s.math<<‘\t’<<s.english<<endl;}特點：節(jié)約內(nèi)存，提高函數(shù)調(diào)用速度，可靠返回結(jié)構(gòu)體類型的函數(shù)一個函數(shù)返回一個結(jié)構(gòu)體。如：personTGetPersonData(void){personTperson;…….Return(person);}返回的是一個結(jié)構(gòu)體的復制。在主調(diào)函數(shù)中必須有這樣的程序段：Main(){personTp1,p2;p1=GetPersonData();}返回結(jié)構(gòu)體引用的函數(shù)函數(shù)返回一個結(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ù)鏈表單鏈表鏈表的概念鏈表的存儲鏈表的操作循環(huán)鏈表單鏈表nilhead頭結(jié)點只指出后繼關(guān)系的鏈表雙鏈表

head循環(huán)鏈表

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

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

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

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

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

接受輸入申請空間輸入數(shù)據(jù)放入申請到的空間鏈入鏈表尾置鏈表結(jié)束標志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)建并訪問一個帶頭結(jié)點的、存儲整型數(shù)據(jù)的單鏈表，數(shù)據(jù)從鍵盤輸入，0為輸入結(jié)束標志。#include<iostream>usingnamespacestd;

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

head=rear=newlinkRec;

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

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

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

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

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

01243head當n=5時，其刪除的節(jié)點的順序為2，0，4，1，最后剩下的節(jié)點為3。

循環(huán)鏈表的應用—約瑟夫環(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為當前正在創(chuàng)建的節(jié)點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)//報數(shù)，{p=q;q=p->next;}p->next=q->next;//繞過節(jié)點qcout<<q->data<<'\t';//顯示被刪者的編號deleteq; //回收被刪者的空間q=p->next;//讓q指向報1的節(jié)點}//打印結(jié)果cout<<"\n最后剩下："<<q->data<<endl;return0;}

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