數(shù)據(jù)封裝結(jié)構(gòu)體.pptVIP

第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é)生成績(jī)單 ，格式如下：,如何在程序中表示這組學(xué)生信息？,可選方案,用二維的數(shù)組來(lái)表示 該方案不可行，因?yàn)檫@些信息有不同的類型 每一列用一個(gè)一維數(shù)組來(lái)表示，這種方法稱為并聯(lián)數(shù)組。 要保證每位學(xué)生信息的正確性很難,為什么要使用記錄,當(dāng)我們考慮怎么邏輯地組織數(shù)據(jù)時(shí)，應(yīng)該將一個(gè)人的所有信息項(xiàng)放在一起，即保持相關(guān)性。,我 們 希 望 的 結(jié) 構(gòu),記錄 在C+中稱為結(jié)構(gòu)體,結(jié)構(gòu)體類型作用,結(jié)構(gòu)體類型允許程序員把一些分量聚合成一個(gè)整體，用一個(gè)變量表示。 一個(gè)結(jié)構(gòu)體的各個(gè)分量都有名字，把這些分量稱為成員(member)。 由于結(jié)構(gòu)體的成員可以是各種類型的，程序員能創(chuàng)建適合于問(wèn)題的數(shù)據(jù)聚合。,結(jié)構(gòu)體的使用,定義一個(gè)新的結(jié)構(gòu)體類型 定義新類型的變量 訪問(wèn)結(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)體類型名 字段聲明； ；,如： struct studentT char no10; char name10; int chinese; int math; int english; ;,注意,字段名可與程序中的變量名相同 在不同的結(jié)構(gòu)體中可以有相同的字段名 結(jié)構(gòu)體成員的類型可以是任意類型，當(dāng)然也可以是結(jié)構(gòu)體類型,struct dateT int month; int day; int year; ; struct studentT . dateT birthday; ;,第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)體變量： studentT student1; 一旦定義了一個(gè)結(jié)構(gòu)體類型的變量，系統(tǒng)在分配內(nèi)存時(shí)就會(huì)分配一塊連續(xù)的空間，依次存放它的每一個(gè)分量。這塊空間總的名字就是結(jié)構(gòu)體變量的名字。內(nèi)部還有各自的名字,結(jié)構(gòu)體變量的初始化,studentT student1= “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)體變量的訪問(wèn),成員的表示：,結(jié)構(gòu)變量名.成員名,如: ,如結(jié)構(gòu)中還有結(jié)構(gòu)，則一級(jí)一級(jí)用”.”分開(kāi) ，如,如：student1.birthday.year,對(duì)結(jié)構(gòu)體類型變量的引用一般為引用他的成員,結(jié)構(gòu)變量的賦值,結(jié)構(gòu)體是一個(gè)統(tǒng)稱。每個(gè)結(jié)構(gòu)體類型在使用前都要先定義自己有哪些分量。系統(tǒng)事先無(wú)法知道如何處理他。 因此，結(jié)構(gòu)體變量的賦值通常是通過(guò)對(duì)它的每一個(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的成員對(duì)應(yīng)賦給student1的成員,結(jié)構(gòu)變量的輸出,結(jié)構(gòu)體變量的輸出通常是通過(guò)輸出它的每一個(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)體指針；,通過(guò)指針操作記錄,給結(jié)構(gòu)體指針賦值，如： sp = 結(jié)構(gòu)體指針的引用：,(*指針).成員 如：(*sp).name,指針-成員 如：sp-name,student1.成員, -是所有運(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)申請(qǐng)到的內(nèi)存的首地址。用法和申請(qǐng)普通的動(dòng)態(tài)變量一樣。如： studentT *sp; sp = new studentT;,第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è)體的集合 定義格式： studentT studentArraySIZE;,結(jié)構(gòu)體數(shù)組的引用,引用數(shù)組的某一成員的成員 studentA 數(shù)組成員之間相互賦值 studentArray4 = studentArray2 結(jié)構(gòu)數(shù)組的初始化 studentT studentArray5 = “00001”, 張三“, 80, 90,98 , , , ;,統(tǒng)計(jì)候選人得票。設(shè)有三個(gè)候選人，每次輸入一個(gè) 得票的候選人名字，要求最后輸出各人得票結(jié)果。,struct personT int id; int count; leader3= 0, 0, 1, 0, 2, 0;,int main() int i, j, inputID; for (i=1; i inputID; if (inputID 2) cout “廢票”；continue； leaderinputID.count += 1; cout endl; for (i=0; i3; +i) cout leaderi.id “ “ leaderi.count); return 0; ,指針與結(jié)構(gòu)體數(shù)組,與普通的指針一樣，指向結(jié)構(gòu)體的指針也能夠用來(lái)指向一個(gè)結(jié)構(gòu)體數(shù)組。此時(shí)，對(duì)指針加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)體的傳遞,Void printPerson(PersonT p),指向結(jié)構(gòu)體的指針作為參數(shù),因?yàn)榻Y(jié)構(gòu)體是值傳遞，當(dāng)希望把函數(shù)內(nèi)部對(duì)結(jié)構(gòu)體的修改返回給主調(diào)函數(shù)時(shí)，可以用指針傳遞或引用傳遞 由于結(jié)構(gòu)體一般占用的內(nèi)存量都比較大，值傳遞既浪費(fèi)空間又浪費(fèi)時(shí)間。因此可用指針傳遞或引用傳遞 指針傳遞形式比較繁瑣，所以C+通常用引用傳遞 引用傳遞的問(wèn)題是函數(shù)中可以修改實(shí)際參數(shù)，要控制函數(shù)中不能修改實(shí)際參數(shù)，可以加const限定,指向結(jié)構(gòu)體的指針作為參數(shù),和普通的指針傳遞一樣，函數(shù)中可以通過(guò)指針訪問(wèn)主調(diào)函數(shù)的記錄 減少函數(shù)調(diào)用時(shí)的數(shù)據(jù)傳遞量,Void PrintPerson(personT ,結(jié)構(gòu)體傳遞的實(shí)例,設(shè)計(jì)一函數(shù)，打印學(xué)生信息,設(shè)計(jì)一：值傳遞,Void PrintStudent(studentT s) cout s.no t t s.chinese t s.math t s.english endl; 缺點(diǎn)：浪費(fèi)時(shí)間空間,設(shè)計(jì)二：指針傳遞或引用傳遞,Void PrintStudent(studentT *s) cout no name chinese math english endl; Void PrintStudent(studentT 缺點(diǎn)：不安全,設(shè)計(jì)三：C+的常規(guī)做法,Void PrintStudent(const studentT 特點(diǎn)：節(jié)約內(nèi)存，提高函數(shù)調(diào)用速度，可靠,返回結(jié)構(gòu)體類型的函數(shù),一個(gè)函數(shù)返回一個(gè)結(jié)構(gòu)體。如： personT GetPersonData(void) personT person; . Return(person); 返回的是一個(gè)結(jié)構(gòu)體的復(fù)制。 在主調(diào)函數(shù)中必須有這樣的程序段： Main() personT p1,p2; p1=GetPersonData();,返回結(jié)構(gòu)體引用的函數(shù),函數(shù)返回一個(gè)結(jié)構(gòu)體的引用。如： personT 函數(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)鏈表,單鏈表,頭結(jié)點(diǎn),只指出后繼關(guān)系的鏈表,雙鏈表,循環(huán)鏈表,同時(shí)存儲(chǔ)前趨和后繼,單鏈表,鏈表的概念 鏈表的存儲(chǔ) 鏈表的操作 循環(huán)鏈表,單鏈表的存儲(chǔ),struct linkRec datatype data; linkRec *next; ,存儲(chǔ)鏈表就是存儲(chǔ)鏈表中的一個(gè)節(jié)點(diǎn)的地址，因此需要定義一個(gè)節(jié)點(diǎn)類型,單鏈表,鏈表的概念 鏈表的存儲(chǔ) 鏈表的操作 循環(huán)鏈表,單鏈表操作插入,申請(qǐng)空間 輸入數(shù)據(jù)放入申請(qǐng)到的空間 鏈入p后,在結(jié)點(diǎn)p后插入一個(gè)結(jié)點(diǎn),tmp = new LinkRec; / 創(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)連接起來(lái),單鏈表操作刪除,把結(jié)點(diǎn)p后的結(jié)點(diǎn)刪除,delPtr=p-next; p-next=delPtr-next; delete delPtr;,單鏈表操作-建立,定義頭指針：linkRec *head; 建立頭結(jié)點(diǎn) 申請(qǐng)空間 設(shè)為頭結(jié)點(diǎn),head,單鏈表操作-建立（續(xù)）,逐個(gè)從鍵盤(pán)輸入數(shù)據(jù)，存入鏈表 接受輸入 申請(qǐng)空間 輸入數(shù)據(jù)放入申請(qǐng)到的空間 鏈入鏈表尾 置鏈表結(jié)束標(biāo)志,a,b,c,d,head = new linkRec; rear = head; Cin in_data; while(輸入未結(jié)束) p= new linkRec; p-data = in_data; rear-next = p; rear=p; cin in_data; rear-next = NULL;,單鏈表操作輸出,p = head-next; while ( p != NULL) cout data; p = p-next; ,創(chuàng)建并訪問(wèn)一個(gè)帶頭結(jié)點(diǎn)的、存儲(chǔ)整型數(shù)據(jù)的單鏈表，數(shù)據(jù)從鍵盤(pán)輸入，0為輸入結(jié)束標(biāo)志。,#include using namespace std; struct linkRec int data; linkRec *next; ;,int main() int x; /存放輸入的值 linkRec *head, *p, *rear; head = rear = new linkRec; while (true) /創(chuàng)建鏈表的其他結(jié)點(diǎn) cin x; if (x = 0) break; p = new linkRec; p-data = x; rear-next = p; rear = p; rear-next = NULL; /設(shè)置rear為表尾，其后沒(méi)有結(jié)點(diǎn)了 /讀鏈表 cout next; while (p != NULL) cout data next; cout endl; return 0; ,單鏈表,鏈表的概念 鏈表的存儲(chǔ) 鏈表的操作 循環(huán)鏈表,例：n個(gè)人圍成一圈，從第一個(gè)人開(kāi)始報(bào)數(shù)1、2、3。凡報(bào)到 3者退出圈子。找出最后留在圈子中的人的序號(hào)。,解。用循環(huán)鏈表,當(dāng)n = 5時(shí)，其刪除的節(jié)點(diǎn)的順序?yàn)?，0，4，1，最后剩下的節(jié)點(diǎn)為3。,循環(huán)鏈表的應(yīng)用約瑟夫環(huán),struct node int data; node *next; ; int main() node *head, *p, *q; / head為鏈表頭 int n, i; /輸入n cout n; /建立鏈表 head = p = new node; p-data = 0; /p指向表尾 for (i=1; idata =i; p-nex