第8章自義數(shù)據(jù)類型ppt課件

1、1第8章 自定義數(shù)據(jù)類型2第8章 自定義數(shù)據(jù)類型數(shù)組是一種數(shù)據(jù)形式，其特點是多個相同類型元素集合起來；結(jié)構(gòu)體是另一種重要的數(shù)據(jù)形式，其特點是不同類型成員組合起來。38.1 結(jié)構(gòu)體類型結(jié)構(gòu)體允許將不同類型的數(shù)據(jù)元素組合在一起形成一種新的數(shù)據(jù)類型，其聲明形式為：struct 結(jié)構(gòu)體類型名結(jié)構(gòu)體類型名 成員列表成員列表;48.1 結(jié)構(gòu)體類型struct STUDENT /學(xué)生信息類型學(xué)生信息類型 int no; /聲明一個整型數(shù)據(jù)成員表示學(xué)號聲明一個整型數(shù)據(jù)成員表示學(xué)號 char name21; /聲明一個字符串?dāng)?shù)據(jù)成員表示姓名聲明一個字符串?dāng)?shù)據(jù)成員表示姓名 char sex; /聲明一個字符數(shù)據(jù)成

2、員表示性別聲明一個字符數(shù)據(jù)成員表示性別 int age; /聲明一個整型數(shù)據(jù)成員年齡聲明一個整型數(shù)據(jù)成員年齡 char 11; /聲明一個字符串?dāng)?shù)據(jù)成員表示聲明一個字符串?dāng)?shù)據(jù)成員表示QQ號號 double score; /聲明一個浮點型數(shù)據(jù)成員表示成績聲明一個浮點型數(shù)據(jù)成員表示成績;例如可以通過如下聲明建立能表示學(xué)生信息的數(shù)據(jù)類型。58.1 結(jié)構(gòu)體類型結(jié)構(gòu)體類型聲明一般放在程序文件開頭，此時這個聲明是全局的。在全局作用域內(nèi)，該聲明處處可見，因此同作用域內(nèi)的所有函數(shù)都可以使用它。結(jié)構(gòu)體類型聲明也可以放到函數(shù)內(nèi)部，此時這個聲明是局部的。若在函數(shù)內(nèi)部有同名的結(jié)構(gòu)體類型聲明，則全局聲明在該函數(shù)內(nèi)部是無

3、效的，有效的是局部聲明的。68.1 結(jié)構(gòu)體類型（1結(jié)構(gòu)體類型和普通數(shù)據(jù)類型如int、char、double等一樣是類型名稱，而不是該類型的一個實體，因此不會為結(jié)構(gòu)體類型分配存儲空間。（2結(jié)構(gòu)體類型聲明時成員可以又是是結(jié)構(gòu)體類型。struct DATA int year,month,day; ;78.1 結(jié)構(gòu)體類型（3C語言的結(jié)構(gòu)體類型只能用“struct 結(jié)構(gòu)體類型名表示，如“struct STUDENT”。C+兼容C語言的結(jié)構(gòu)體類型，既可以用C語言方式，又可以直接用“結(jié)構(gòu)體類型名表示，如“STUDENT”。建議C+程序員使用后一種方式。88.2 結(jié)構(gòu)體對象定義結(jié)構(gòu)體對象稱為結(jié)構(gòu)體類型實例化i

4、nstance），實例化會根據(jù)數(shù)據(jù)類型為結(jié)構(gòu)體對象分配內(nèi)存單元。98.2.1 結(jié)構(gòu)體對象的定義定義結(jié)構(gòu)體對象有三種形式。1先聲明結(jié)構(gòu)體類型再定義對象結(jié)構(gòu)體類型名 結(jié)構(gòu)體對象名列表; /C+方式struct 結(jié)構(gòu)體類型名 結(jié)構(gòu)體對象名列表; /兼容的C語言方式STUDENT a,b; /C+方式定義結(jié)構(gòu)體對象方式定義結(jié)構(gòu)體對象struct STUDENT x,y; /C語言方式定義結(jié)構(gòu)體對象語言方式定義結(jié)構(gòu)體對象108.2.1 結(jié)構(gòu)體對象的定義2聲明結(jié)構(gòu)體類型的同時定義對象一般形式為：struct 結(jié)構(gòu)體類型名結(jié)構(gòu)體類型名 成員列表成員列表 結(jié)構(gòu)體對象名列表結(jié)構(gòu)體對象名列表;struct DAT

5、E /日期類型日期類型 int year,month,day; /年，月，日年，月，日 整型整型 d1,d2; /定義結(jié)構(gòu)體對象定義結(jié)構(gòu)體對象118.2.1 結(jié)構(gòu)體對象的定義3結(jié)構(gòu)體對象的內(nèi)存形式實例化結(jié)構(gòu)體對象后，對象會得到存儲空間。128.2.1 結(jié)構(gòu)體對象的定義圖8.1 結(jié)構(gòu)體對象的內(nèi)存結(jié)構(gòu)struct STUDENT /學(xué)生信息類型學(xué)生信息類型 int no; /聲明一個整型數(shù)據(jù)成員表示學(xué)號聲明一個整型數(shù)據(jù)成員表示學(xué)號 char name21; /聲明一個字符串?dāng)?shù)據(jù)成員表示姓名聲明一個字符串?dāng)?shù)據(jù)成員表示姓名 char sex; /聲明一個字符數(shù)據(jù)成員表示性別聲明一個字符數(shù)據(jù)成員表示性別

6、 int age; /聲明一個整型數(shù)據(jù)成員年齡聲明一個整型數(shù)據(jù)成員年齡 char 11; /聲明一個字符串?dāng)?shù)據(jù)成員表示聲明一個字符串?dāng)?shù)據(jù)成員表示QQ號號 double score; /聲明一個浮點型數(shù)據(jù)成員表示成績聲明一個浮點型數(shù)據(jù)成員表示成績;138.2.2 結(jié)構(gòu)體對象的初始化STAFF s1=1001,“Li Min”,M,1980,10,6,2700.0;STAFF s2=1002,Ma Gang,M,1978,3,22,3100.0;struct STAFF /職員信息類型職員信息類型 int no; /工號，整型工號，整型 char name21; /姓名，字符串姓名，字符串 cha

7、r sex; /性別，字符型性別，字符型 DATA birthday; /出生日期，結(jié)構(gòu)體類型出生日期，結(jié)構(gòu)體類型 double salary; /薪水，浮點型薪水，浮點型;可以在結(jié)構(gòu)體對象定義時進(jìn)行初始化。148.2.3 結(jié)構(gòu)體對象的使用1結(jié)構(gòu)體對象成員引用使用結(jié)構(gòu)體對象主要是引用它的成員，其一般形式為：結(jié)構(gòu)體對象名結(jié)構(gòu)體對象名.成員名成員名158.2.3 結(jié)構(gòu)體對象的使用表8-1 對象成員引用運算符運算符運算符功能功能目目結(jié)合性結(jié)合性用法用法對象成員引用運算對象成員引用運算 雙目雙目自左向右自左向右object.memberSTAFF a,b;a.no=10002; /將將10002賦值給

8、賦值給a對象中的對象中的no成員成員b.salary=a.salary+500.0; /在表達(dá)式中可以引用對象成員在表達(dá)式中可以引用對象成員a.no+; /按優(yōu)先級等價于按優(yōu)先級等價于(a.no)+168.2.3 結(jié)構(gòu)體對象的使用如果成員本身又是一個結(jié)構(gòu)體對象，就要用成員引用運算符，一級一級地引用。例如：STAFF x;x.birthday.year=1990,x.birthday.month=5,x.birthday.day=12; /逐級引用成員逐級引用成員178.2.3 結(jié)構(gòu)體對象的使用2結(jié)構(gòu)體對象輸入與輸出不能將一個結(jié)構(gòu)體對象作為整體進(jìn)行輸入或輸出，只能對結(jié)構(gòu)體對象中的成員逐個進(jìn)行輸入

9、或輸出。例如：STAFF x;cinx.nox.sexx.salary; cinx.birthday.yearx.birthday.monthx.birthday.day;; 188.2.3 結(jié)構(gòu)體對象的使用3結(jié)構(gòu)體對象的運算結(jié)構(gòu)體對象可以進(jìn)行賦值運算，但不能對進(jìn)行算術(shù)運算、關(guān)系運算等，例如：COMPLEX m,n,k;m=n; /正確，結(jié)構(gòu)體對象允許賦值正確，結(jié)構(gòu)體對象允許賦值k=m+n; /錯誤，結(jié)構(gòu)體對象不能做算術(shù)運算錯誤，結(jié)構(gòu)體對象不能做算術(shù)運算mn; /錯誤，結(jié)構(gòu)體對象不能做關(guān)系運算錯誤，結(jié)構(gòu)體對象不能做關(guān)系運算回憶：19struct STAFF int no; c

10、har name21; char sex; DATA birthday; double salary; ;STAFF a,b;a.no=1101;b.birthdat.year=1988;a=b;sum=a.salary+b.salary;struct DATE int year,month,day; ; 定義結(jié)構(gòu)體類型定義結(jié)構(gòu)體對象結(jié)構(gòu)體對象的內(nèi)存形式結(jié)構(gòu)體對象成員的引用結(jié)構(gòu)體對象的輸入輸出結(jié)構(gòu)體對象的運算208.3 結(jié)構(gòu)體與數(shù)組數(shù)組元素可以是結(jié)構(gòu)體對象。218.3.1 結(jié)構(gòu)體數(shù)組數(shù)組元素可以是結(jié)構(gòu)體類型，稱為結(jié)構(gòu)體數(shù)組，如一維結(jié)構(gòu)體數(shù)組定義形式為：struct 結(jié)構(gòu)體類型名結(jié)構(gòu)體類型名 結(jié)

11、構(gòu)體數(shù)組名結(jié)構(gòu)體數(shù)組名常量表達(dá)式常量表達(dá)式;例如表示平面上若干個點的數(shù)據(jù)對象，可以這樣定義：struct POINT /點類型點類型 int x,y; /平面上點的平面上點的x、y坐標(biāo)坐標(biāo);POINT points100; /表示表示100個點的數(shù)據(jù)對象個點的數(shù)據(jù)對象228.3.1 結(jié)構(gòu)體數(shù)組一維結(jié)構(gòu)體數(shù)組初始化形式為：其中初值序列必須按內(nèi)存形式做到類型、次序一一對應(yīng)。struct 結(jié)構(gòu)體類型名結(jié)構(gòu)體類型名 結(jié)構(gòu)體數(shù)組名結(jié)構(gòu)體數(shù)組名常量表達(dá)式常量表達(dá)式 =初初值序列值序列;238.3.1 結(jié)構(gòu)體數(shù)組例如：初值寫法中除最外面的一對大括號外，其他大括號可以省略。例如：struct RECT /矩形

12、框類型矩形框類型 int left,top,right,bottom;RECT rects3=1,1,10,10, 5,5,25,32,100,100,105,200;RECT _rect3=1,1,10,10,5,5,25,32, 100,100,105,200;248.3.1 結(jié)構(gòu)體數(shù)組引用結(jié)構(gòu)體數(shù)組成員需要將數(shù)組下標(biāo)運算、對象成員引用運算結(jié)合起來操作，其一般形式為：數(shù)組對象數(shù)組對象下標(biāo)表達(dá)式下標(biāo)表達(dá)式.成員名成員名r0.left=10;/數(shù)組對象數(shù)組對象下標(biāo)表達(dá)式下標(biāo)表達(dá)式是結(jié)構(gòu)體對象是結(jié)構(gòu)體對象258.3.2 結(jié)構(gòu)體數(shù)組成員結(jié)構(gòu)體類型中可以包含數(shù)組成員，數(shù)組成員類型既可以是基本數(shù)據(jù)類型

13、又可以是指針類型或結(jié)構(gòu)體類型，例如表示平面三角形的數(shù)據(jù)對象，可以這樣定義：struct TRIANGLE /三角形類型三角形類型 POINT p3;/由由3個平面上的點描述三角形個平面上的點描述三角形;268.3.2 結(jié)構(gòu)體數(shù)組成員引用結(jié)構(gòu)體數(shù)組成員需要將對象成員引用運算、數(shù)組下標(biāo)運算結(jié)合起來操作，其一般形式為：結(jié)構(gòu)體對象結(jié)構(gòu)體對象.數(shù)組成員數(shù)組成員下標(biāo)表達(dá)式下標(biāo)表達(dá)式struct TRIANGLE tri;tri.p0.x=10,tri.p0.y=10;/結(jié)構(gòu)體對象結(jié)構(gòu)體對象.數(shù)組成員數(shù)組成員下標(biāo)表達(dá)式下標(biāo)表達(dá)式.成員名成員名278.3.2 結(jié)構(gòu)體數(shù)組成員例8.1 輸入20個學(xué)生信息，按成績

14、遞減排序；成績相同時，按學(xué)號遞增排序。 1 #include 2 using namespace std; 3 #define N 20 4 struct tagSTUDENT /學(xué)生信息類型 5 int no; /學(xué)號 6 char name21; /姓名 7 double score; /成果 8 ;288.3.2 結(jié)構(gòu)體數(shù)組成員例8.1 9 int main() 10 11 struct tagSTUDENT AN , t; 12 int i , j=2.0; /消除浮點型bug 13 for (i=0; iAi.noAAi.score; 15 for (i=0; iN-1;

15、 i+) /排序 16 for (j=i; jN; j+) 17 if (Ai.scoreAj.no) 19 t=Ai, Ai=Aj, Aj=t; 298.3.2 結(jié)構(gòu)體數(shù)組成員例8.1 20 for (i=0; iN; i+) /輸出學(xué)生信息 21 coutAi.no,A ,Ai.score成員名。348.4.1 指向結(jié)構(gòu)體的指針表8-2 指針成員引用運算符運算符運算符功能功能目目結(jié)合性結(jié)合性用法用法-指針成員引指針成員引用運算用運算雙目雙目 自左向右自左向右pointer-memberp-no=10002; /將將10002賦值給對象中的賦值給對象中的no成員，指針成成員，指針

16、成員引用運算結(jié)果是左值即成員本身）員引用運算結(jié)果是左值即成員本身）p-salary=p-salary+500.0; /在表達(dá)式中引用指針指向的在表達(dá)式中引用指針指向的成員成員p-no+; /按優(yōu)先級等價于按優(yōu)先級等價于(p-no)+358.4.1 指向結(jié)構(gòu)體的指針（1指針成員引用運算符（-）左邊運算對象必須是指向結(jié)構(gòu)體對象的指針，右邊member必須是結(jié)構(gòu)體對象中的成員名。其引用形式為：結(jié)構(gòu)體指針結(jié)構(gòu)體指針-成員名成員名368.4.1 指向結(jié)構(gòu)體的指針（2如果成員本身又是一個結(jié)構(gòu)體對象指針，就要用指針成員引用運算符一級一級地引用成員。例如：DATE d=1981,1,1;TEACHER /教師

17、信息類型教師信息類型 int no; /工號工號 char name21; /姓名姓名 DATE *pbirthday; /出生日期出生日期 a=1001,Li Min,&d, *p=&a;p-no=10001; /通過指針通過指針p引用引用a的的no成員成員p-pbirthday-year=2019; /通過指針通過指針p-pbirthday引引用用d的的year成員成員378.5 結(jié)構(gòu)體與函數(shù)將結(jié)構(gòu)體對象作為函數(shù)實參傳遞到函數(shù)中，采用值傳遞方式。例如：struct DATA int data; /整型成員整型成員 char name10; /數(shù)組成員數(shù)組成員;void fu

18、n1(DATA x); /函數(shù)原型函數(shù)原型void fun2() DATA a=1,LiMin; fun1(a); /函數(shù)調(diào)用函數(shù)調(diào)用388.5.2 結(jié)構(gòu)體數(shù)組作為函數(shù)參數(shù)將結(jié)構(gòu)體數(shù)組作為函數(shù)參數(shù)，采用地址傳遞方式。函數(shù)調(diào)用實參是數(shù)組名，形參必須是同類型的結(jié)構(gòu)體數(shù)組。例如：采用地址傳遞方式，形參數(shù)組的首地址與實參數(shù)組完全相同。void fun3(DATA X); /函數(shù)原型函數(shù)原型void fun4() DATA A3=1,LiMin,2,MaGang,3,ZhangKun; fun3(A); /函數(shù)調(diào)用函數(shù)調(diào)用398.5.3 結(jié)構(gòu)體指針或引用作為函數(shù)參數(shù)將結(jié)構(gòu)體指針作為函數(shù)參數(shù)，采用地址傳遞

19、方式。例如：void fun5(DATA *p); /函數(shù)原型函數(shù)原型void fun6() DATA a=1,LiMin; fun3(&a); /函數(shù)調(diào)用函數(shù)調(diào)用408.5.4 函數(shù)返回結(jié)構(gòu)體對象、指針或引用函數(shù)的返回類型可以是結(jié)構(gòu)體類型，這時函數(shù)將返回一個結(jié)構(gòu)體對象。例如：DATA fun8() DATA a=1,LiMin; return a; /返回結(jié)構(gòu)體對象，復(fù)制到臨時對象中返回結(jié)構(gòu)體對象，復(fù)制到臨時對象中void fun9() DATA b; b=fun8(); /函數(shù)返回結(jié)構(gòu)體對象，并且賦值函數(shù)返回結(jié)構(gòu)體對象，并且賦值418.10 鏈表鏈表是一種存儲空間能動態(tài)進(jìn)行增長或縮

20、小的數(shù)據(jù)結(jié)構(gòu)。鏈表廣泛地運用于數(shù)據(jù)管理中。428.10.1 鏈表的概念首先設(shè)計一種稱為結(jié)點node的數(shù)據(jù)類型：這個結(jié)構(gòu)體類型中，data成員表示數(shù)據(jù)域，代表結(jié)點的數(shù)據(jù)信息。struct NODE /結(jié)點數(shù)據(jù)類型結(jié)點數(shù)據(jù)類型 ElemType data; /數(shù)據(jù)域數(shù)據(jù)域 NODE *link; /指針域指針域;438.10.1 鏈表的概念圖8.7 鏈表結(jié)構(gòu)link成員表示指針域，存放另一個結(jié)點的地址，是鏈表中的組織者。通常，鏈表包含創(chuàng)建、遍歷、插入、刪除等運算。448.10.2 單鏈表與雙鏈表1單鏈表單鏈表每個結(jié)點包含一個指向直接后繼結(jié)點的指針域，其形式為：next指向直接后繼結(jié)點，由它構(gòu)成了一

21、條鏈。struct LNode /單鏈表結(jié)點類型單鏈表結(jié)點類型 int data; /數(shù)據(jù)域數(shù)據(jù)域 LNode *next; /指針域：指向直接后繼結(jié)點指針域：指向直接后繼結(jié)點;typedef LNode* LinkList; /LNode為單鏈表結(jié)構(gòu)體類型，為單鏈表結(jié)構(gòu)體類型，LinkList為單鏈表指針類型為單鏈表指針類型458.10.2 單鏈表與雙鏈表圖8.8 單鏈表結(jié)構(gòu)指針L指向單鏈表頭結(jié)點，頭結(jié)點指向開始結(jié)點，開始結(jié)點又指向下一個結(jié)點，直到最后一個尾結(jié)點。尾結(jié)點的next為0，表示NULL指針，約定單鏈表的結(jié)點的next為0時表示尾結(jié)點。468.10.3 創(chuàng)建與銷毀鏈表通過第7章介紹

22、的內(nèi)存動態(tài)分配技術(shù)可以產(chǎn)生新結(jié)點的內(nèi)存單元，例如：LinkList p; /鏈表指針鏈表指針p=new LNode;/分配分配LNode類型內(nèi)存單元且將地址保存到類型內(nèi)存單元且將地址保存到p中中478.10.3 創(chuàng)建與銷毀鏈表創(chuàng)建鏈表常用兩種方法：頭插法和尾插法。（1頭插法建立鏈表CreateLinkF(&L,n,input()步驟：創(chuàng)建頭結(jié)點*L，設(shè)置*L的next為0。動態(tài)分配一個結(jié)點s，輸入s的數(shù)據(jù)域。將s插入到開始結(jié)點之前，頭結(jié)點之后，即： s-next=p-next，p-next=s。反復(fù)步驟加入更多結(jié)點。488.10.3 創(chuàng)建與銷毀鏈表采用頭插法創(chuàng)建單鏈表的算法如下： 1

23、void CreateLinkF(LinkList *L,int n) 2 /頭插法創(chuàng)建單鏈表，調(diào)用input輸入函數(shù)輸入數(shù)據(jù) 3 LinkList s; 4 *L=new LNode;/創(chuàng)建頭結(jié)點 5 (*L)-next=NULL; /初始時為空表 6 for (; n0; n-) /創(chuàng)建n個結(jié)點鏈表 7 s=new LNode; /創(chuàng)建新結(jié)點 8 cins-data; 9 s-next=(*L)-next; 10 (*L)-next=s; /頭結(jié)點之后 11 12 498.10.3 創(chuàng)建與銷毀鏈表圖8.11 頭插法建立的單鏈表L運行時若輸入5個元素：1、2、3、4、5，則調(diào)用建立的單鏈表如

24、圖所示。LinkList L;CreateLinkF(&L,5); /創(chuàng)建單鏈表創(chuàng)建單鏈表L508.10.3 創(chuàng)建與銷毀鏈表（2銷毀鏈表DestroyList(&L)將鏈表所占用的所有內(nèi)存釋放掉，即銷毀鏈表。銷毀鏈表的步驟如下：假設(shè)*L為0，表示已到鏈尾，銷毀鏈表結(jié)束。令指針p指向結(jié)點*L的next，釋放內(nèi)存*L。*L置換為p，即*L指向直接后繼結(jié)點，反復(fù)步驟直至銷毀鏈表結(jié)束。518.10.3 創(chuàng)建與銷毀鏈表應(yīng)用遍歷算法銷毀鏈表的算法如下： 1 void DestroyList(LinkList *L) /銷毀單鏈表L 2 3 LinkList q,p=*L;/p指向頭結(jié)點 4

25、 while(p!=NULL) /若不是鏈尾繼續(xù) 5 q=p-next; /指向直接后繼結(jié)點 6 delete p; /釋放結(jié)點存儲空間 7 p=q; /直接后繼結(jié)點 8 9 *L=NULL;/置為空表 10 528.10.4 鏈表的運算（1鏈表遍歷鏈表的輸出、銷毀、查找和逆序等運算都需要遍歷鏈表。鏈表遍歷算法的實現(xiàn)步驟為：令指針p指向L的開始結(jié)點。若p為0，表示已到鏈尾，遍歷結(jié)束。令p指向直接后繼結(jié)點，即p=p-next。反復(fù)步驟直至遍歷結(jié)束。538.10.4 鏈表的運算鏈表遍歷的算法如下：其中visit是函數(shù)指針。當(dāng)調(diào)用ListTraverse遍歷結(jié)點時，通過調(diào)用visit()對每個結(jié)點完

26、成定制的操作。 1 void ListTraverse(LinkList L, void(*visit)(ElemType*) 2 /遍歷L中的每個元素且調(diào)用函數(shù)visit訪問它 3 LinkList p=L-next; /p指向開始結(jié)點 4 while(p!=NULL) /若不是鏈尾繼續(xù) 5 visit(&(p-data); 6 p=p-next; /p指向直接后繼結(jié)點 7 8 548.10.4 鏈表的運算（2輸出鏈表設(shè)計遍歷結(jié)點時的visit函數(shù)：調(diào)用ListTraverse(L,visit)時掃描鏈表中的每個結(jié)點，并調(diào)用visit()輸出結(jié)點的數(shù)據(jù)域。 1 void visit(ElemType *ep) /實現(xiàn)鏈表遍歷時結(jié)點訪問的定制函數(shù) 2 /在函數(shù)中對結(jié)點*ep實現(xiàn)定制的操作，例如輸出 3 cout*epne