基礎(chǔ)課件-第8章用戶定義類型

程序設計基礎(chǔ)(The

Foundation

of

Programming)第8章用戶定義類型

(User-defined

Type)主講：嚴冬梅第8章用戶定義類型教學要求了解用戶定義數(shù)據(jù)類型的實質(zhì)；掌握結(jié)構(gòu)體、聯(lián)合體、枚舉類型和typedef的定義和使用，特別是結(jié)構(gòu)變量、結(jié)構(gòu)數(shù)組和結(jié)構(gòu)指針的使用；理解鏈表的結(jié)構(gòu)；初步掌握鏈表的基本操作并進行簡單的程序設計。第8章用戶定義類型重點結(jié)構(gòu)類型的定義；結(jié)構(gòu)變量；結(jié)構(gòu)數(shù)組；結(jié)構(gòu)指針；聯(lián)合體；類型定義。；類型定義的使用；難點結(jié)構(gòu)指針；聯(lián)合體的鏈表結(jié)構(gòu)；鏈表的實現(xiàn)。數(shù)據(jù)類型空值類型void字符型char數(shù)據(jù)類型整型int雙精度型double浮點型（單精度型）

float基本數(shù)據(jù)類型聯(lián)合體union構(gòu)造數(shù)據(jù)類型數(shù)組結(jié)構(gòu)體struct枚舉地址類型：指針特殊數(shù)據(jù)類型第8章用戶定義類型8.1

結(jié)構(gòu)體8.2

聯(lián)合體8.3

枚舉8.4

類型定義8.5

鏈表*8.1

結(jié)構(gòu)體假設現(xiàn)在開發(fā)一個系統(tǒng)，其中有學生、教師、教室等對象，而這些對象都具有

、名稱等屬性，若不使用結(jié)構(gòu)體，則必須使用studentNum、

teacherNum、classroomNum、

studentName、teacherName、

classroomName等等，

，太麻煩了?。。?.1.1

結(jié)構(gòu)類型結(jié)構(gòu)（類型）的定義是對結(jié)構(gòu)體的描述，結(jié)構(gòu)的定義并不引起系統(tǒng)為該結(jié)構(gòu)分配內(nèi)存空間，只是制定了結(jié)構(gòu)使用的內(nèi)存模式。定義形式struct

結(jié)構(gòu)類型名成員名n;{

數(shù)據(jù)類型 成員名1;數(shù)據(jù)類型

成員名2;……數(shù)據(jù)類型};struct

結(jié)構(gòu)類型名是一個完整的數(shù)據(jù)類型structstudent{intnum;char

name[10];int

age;float

score;char

address[30];};8.1.2

結(jié)構(gòu)變量定義[

類型]struct

結(jié)構(gòu)類型名結(jié)構(gòu)變量名;struct

student{intnum;char

name[10];intage;float

score;char

address[30];};struct

student

a;struct

[student]{intnum;char

name[10];intage;float

score;char

address[30];}a;8.1.2

結(jié)構(gòu)變量anumnameagescoreaddress4字節(jié)10字節(jié)4字節(jié)4字節(jié)30字節(jié)52字節(jié)&a=&a.num：結(jié)構(gòu)變量說明時分配內(nèi)存；結(jié)構(gòu)變量按成員定義的順序

在連續(xù)的內(nèi)存單元中。8.1.2

結(jié)構(gòu)變量成員的結(jié)構(gòu)變量名.成員名初始化struct

student

a={1,"Mary",20,90,"……"};輸入輸出不允許直接輸入輸出scanf("%d%s%d%f%s",&a.num,,&a.age,&a.score,a.address);printf("no:%d,name:%s,age:%d,score:%f,\naddress:%s",a.num,,a.age,a.score,a.address);8.1.2

結(jié)構(gòu)變量結(jié)構(gòu)的嵌套結(jié)構(gòu)體可以嵌套，即成員可以是另一結(jié)構(gòu)的變量結(jié)構(gòu)體嵌套，只能對最低一級成員進行賦值、輸入輸出等運算struct

date{intyear;int

month;int

day;}；Struct

student{intnum;struct

date

birthdate;......};8.1.2

結(jié)構(gòu)變量a.birthdate.yeara.birthdate.montha.birthdate.daya.scorea.address4字節(jié)10字節(jié)12字節(jié)4字節(jié)30字節(jié)60字節(jié)&a=&a.num8.1.2

結(jié)構(gòu)變量注意：結(jié)構(gòu)類型與結(jié)構(gòu)變量是不同的概念；結(jié)構(gòu)體成員的使用與普通變量相同，可單獨使用；成員名可以與程序變量名相同，但二者代表不同對象int

num;struct

student{

int

num;......};嵌套的數(shù)據(jù)成員，只有到最后一層才能進行各種操作8.1.3

結(jié)構(gòu)數(shù)組說明：類型struct

結(jié)構(gòu)類型名結(jié)構(gòu)數(shù)組名[元素個數(shù)]；struct

student

class1301[40];初始化：structstudent

class1301[40]={{…},{…},…{…}}；輸入輸出：for(i=0;

i<40;

i++)scanf("%d%s%d%f%s",&class1301[i].num,class1301[i].name,&class1301[i].age,&class1301[i].score,class1301[i].address);8.1.3

結(jié)構(gòu)數(shù)組class1301[0].numclass1301[0].nameclass1301[0].ageclass1301[0].scoreclass1301[0].addressclass1301[1]……class1301[39]52字節(jié)52字節(jié)52字節(jié)：class130152*40字節(jié)class1301=&class1301[0]=&class1301[0].num8.1.3

結(jié)構(gòu)數(shù)組int

main(){struct

c{int

x;int

y;}a[2]={2,4,6,8};printf("%d",

a[0].x*a[1].y);}162468a[0].xa[0].ya[1].xa[1].y8.1.4

結(jié)構(gòu)指針【例8.1】結(jié)構(gòu)數(shù)組輸入輸出#include

<stdio.h>int

main(){

struct{

int

num;

char

name[10];int

age;}a[3];int

i,

avgAge

=

0;for(i=0;

i<3;

i++){scanf("%d%s%d",

&a[i].num,

a[i].name,

&a[i].age);avgAge

+=

a[i].age;}avgAge

/=

3;for(i=0;

i<3;

i++)printf("Num:

%d,

Name:

%s,

Age:

%d\n",a[i].num,

a[i].name,

a[i].age);printf("Average

Age

:

%d\n",

avgAge);return

0;}8.1.4

結(jié)構(gòu)指針結(jié)構(gòu)指針—指向結(jié)構(gòu)體的指針，保存

區(qū)首地址說明形式：

[

類型]

struct

結(jié)構(gòu)名

*結(jié)構(gòu)指針名;struct

student

*pstu;賦值:struct

student

class1301[40],a,*pstu;pstu=class1301;

/*pstu=&a;*/:(*結(jié)構(gòu)指針名).成員名(*pstu).num結(jié)構(gòu)指針名->成員名.->同屬第一優(yōu)先級pstu->num*屬第二優(yōu)先級初始化

structstudent

*pstu=class1301;pstu++;

相當于加一個結(jié)構(gòu)類型的長度#include

<stdio.h>struct{

int

num;char

name[10];};int

main(){

structstructa[3]={{1,"aaa"},{2,"bbb"},{3,"ccc"}};*p;for(p=a;

p<a+3;

p++)printf("Num:

%d,

Name:

%s\n",

p->num,p->name);return

0;}8.1.4

結(jié)構(gòu)指針【例8.2】結(jié)構(gòu)指針結(jié)構(gòu)數(shù)組8.2

聯(lián)合體同結(jié)構(gòu)體一樣，聯(lián)合體也是由不同數(shù)據(jù)類型的數(shù)據(jù)元素（成員）組成，但其占有內(nèi)存的方式不同。結(jié)構(gòu)體變量所占內(nèi)存長度是各成員所占的長度之和，各成員分別占有自己的內(nèi)存單元。聯(lián)合體變量所占內(nèi)存長度等于最長的成員長度。聯(lián)合使用覆蓋技術(shù)，使不同成員占用同一段區(qū)域。8.2

聯(lián)合體8.2.1

聯(lián)合類型union

[聯(lián)合類型名]{成員列表；}[聯(lián)合變量名];8.2.2union聯(lián)合變量聯(lián)合類型名聯(lián)合變量名;8.2.3union聯(lián)合數(shù)組聯(lián)合類型名聯(lián)合數(shù)組名[元素個數(shù)];8.2.4union聯(lián)合指針聯(lián)合類型名*聯(lián)合指針名;cifd1448&a=&a.c17字節(jié)結(jié)構(gòu)與聯(lián)合模式的差異struct{

char

c;inti;float

f;double

d;}a;union{char

c;int

i;float

f;doubled;}b;abcifd14848字節(jié)&b=&b.c=&b.i=&b.f=

&b.d8.2

聯(lián)合體8.2.5

聯(lián)合體的特點每一時刻，只有一個成員起作用，只能保持某個成員項的數(shù)據(jù)聯(lián)合變量起作用的成員是最后一次存放的成員聯(lián)合變量的地址和其各成員地址是同一地址不能在定義聯(lián)合變量時初始化union

{char

c;int

i;float

f;}b={‘A’,10,1.5};不能把聯(lián)合變量作為函數(shù)參數(shù)和返回值，但可以使用聯(lián)合指針聯(lián)合可以嵌套，其成員亦可以是結(jié)構(gòu)或數(shù)組8.2

聯(lián)合體struct{

int

num;char

name[12];char

sex;union{

int

class;char

position[10];}category;}

;sizeof(

)==278.2

聯(lián)合體int

main(){

union{

int

a;int

b;int

c;}x;x.a=2;

x.b=3;

x.c=x.a*x.b;printf("x.a=%d\n",x.a);}x.a=98.2

聯(lián)合體int

main(){

union{

char

c[2];short

si;}x;x.c[0]='8';

x.c[1]='9';printf("x.si=%x\n",x.si);}x.si=3938xx.c[0]00111000x.six.c[1]001110018.3

枚舉8.3.1

枚舉功能枚舉---將變量的值一一列舉出來如果一個變量只有幾種可能的值，可以定義為枚舉類型。8.3.2

枚舉格式enum

枚舉類型名{枚舉元素列表}；

定義enum

枚舉類型名

枚舉變量；

說明8.3.3

枚舉示例enumenumweekday

{sun,mon,tue,wed,thu,fri,sat};weekday

workday，weekend;8.3

枚舉8.3.4

枚舉注意枚舉元素不是變量，不能賦值，按常量處理枚舉元素是有值的，按定義時順序值為0，1，2……可指定枚舉元素的值，其后為前值增1若enum

weekday{sun,mon,tue,wed,thu,fri,sat};則sun==0，mon==1,tue==2……若enum

weekday{sun=7,mon,tue,wed,thu,fri,sat};則sun==7，mon==8,tue==9……所以enumweekday{sun=7,mon=1,tue,wed,thu,fri,sat};則sun==7，mon==1,tue==2,wed==3……8.3

枚舉8.3.4

枚舉注意枚舉元素值可用來判斷if(workday>wed)

if(workday>3)一個整數(shù)不能直接賦值給枚舉變量workday

=

2;×workday

=

tue;

√workday

=

(enum

weekday)2;

√【例8.3】從5個顏色的小球任意取出2個的所有可能。int

main(){

enum

color

{red,white,blue,green,black};enum

color

present;

int

i,j,n=0,loop;for(i=0;i<5;i++)for(j=0;j<5;j++)if(j!=i)

{n++;

printf("%-4d",n);for(loop=1;loop<=2;loop++)

{switch(loop)

{case

1:

present=(enum

color)i;break;case

2:

present=(enum

color)j;break;}//switchswitch(present)

{case

red:

printf("%-10s",

"red");break;case

white:

printf("%-10s","white");break;case

blue:

printf("%-10s",

"blue");break;case

green:

printf("%-10s",

"green");break;case

black:

printf("%-10s",

"black");break;}//switch}//forprintf("\n");}//ifreturn

0;}8.3

枚舉8.4

類型定義（typedef）8.4.1

功能定義新的類型名代替已有類型名8.4.2

類型定義的格式typedef

type

新類型名；新類型名

變量名；type——標準類型名或定義過的其他類型名類型定義并不能創(chuàng)造任何一種系統(tǒng)規(guī)定外的數(shù)據(jù)類型typedef

int

COUNT; COUNT

i,j;

一目了然typedef

int

ARR[10]; ARR

a,b,c;

方便typedef

struct

student

STUDENT;STUDENTclass9909[41];簡單typedeftypedefint

INTEGER;long

INTEGRER;便于移植8.4

類型定義（typedef）8.4.3

類型定義的步驟先按定義變量的方法寫出定義體；將變量名換成新類型名;在最前面加typedef用新類型名定義變量typedef

char

*STRING;STRING

p;8.4

類型定義（typedef）8.4.4

類型定義的注意用typedef只是對已經(jīng)存在的類型增加一個類型名，而沒有創(chuàng)造新類型；可用#define完成，但本質(zhì)不同，typedef是在編譯時處理；優(yōu)點：方便、簡單、一目了然、便于移植；#include

"user.h"8.4

類型定義（typedef）typedef

struct{}int

num;char

name[10];;struct{int

num;char

name[10];}S;、S是結(jié)構(gòu)變量還是結(jié)構(gòu)類型8.5

鏈表8.5.1

鏈表的引入8.5.2

鏈表的特點8.5.3

鏈表的結(jié)構(gòu)8.5.4

鏈表的主要操作8.5.5

單鏈表的實現(xiàn)8.5.6

循環(huán)單鏈表8.5.1

鏈表的引入算一算：假設每個學生信息有300個字節(jié)，現(xiàn)在有10000個學生，請問太好了！有這么多連

存嗎？8.5.2

鏈表的特點鏈表的特點是將數(shù)據(jù)在位置任意的結(jié)構(gòu)

塊中，用結(jié)構(gòu)指針將這些

塊連接在一起，從第一個

塊順著指針可以到所有的

塊。鏈表中的每一個存儲塊叫一個結(jié)點。實現(xiàn)鏈表需要使用結(jié)構(gòu)指針和動態(tài)

管理機制。8.5.3

鏈表的結(jié)構(gòu)自遞歸結(jié)構(gòu)：指向本結(jié)點類型的指針是實現(xiàn)鏈表的基礎(chǔ)。struct

LNode{

int

data;struct

LNode

*next;};a1LLa2…an^^struct

LNode

*L;datanext鏈表的數(shù)據(jù)類型定義typedef

in

emType;typedef

intStatus;const

int

FALSE

=

0,

TRUE

=

1;typedef

struct

LNode

{ElemType

data;//通用類型struct

LNode

*next;}LNode,

*LinkList;

//LinkListLNode*LNode

*

LinkListLNode

*p,*q,*s;//定義指向結(jié)點的指針LinkList

L,LA,LB;//定義鏈表8.5.4

鏈表的主要操作初始化鏈表建立鏈表遍歷鏈表求鏈表長度查詢鏈表元素結(jié)點刪除結(jié)點逆序鏈表初始化鏈表void

InitList_L(LNode**);建立鏈表

Status

Crea

ist_L(LNode**,ElemType[],int);判斷鏈表是否空

Status

ListEmpty_L(LNode*);遍歷鏈表void

ListTraverse_L(LNode*,void(*)(ElemType));void

ListTraverse_L(LNode*);求鏈表長度int

ListLength_L(LNode*);某元素

Status

Ge em_L(LNode*,

int,

ElemType

*);查詢鏈表元素

int

LocateElem_L(LNode*,ElemType);結(jié)點Status

ListInsert_L(LNode**,int,ElemType);刪除結(jié)點Status

ListDelete_L(LNode**,int,ElemType

*);銷毀鏈表void

DestoryList_L(LNode**);逆序鏈表void

InvertList_L(LNode**);單鏈表的實現(xiàn)（二級指針）初始化鏈表void

InitList_L(LinkList*);建立鏈表

Status

Crea

ist_L(LinkList*,ElemType[],int);判斷鏈表是否空

Status

ListEmpty_L(LinkList);遍歷鏈表void

ListTraverse_L(LinkList,void

(*)(ElemType));void

ListTraverse_L(LinkList);求鏈表長度int

ListLength_L(LinkList);某元素

Status

Ge em_L(LinkList,

int,

ElemType

*);查詢鏈表元素

int

LocateElem_L(LinkList,int);結(jié)點Status

ListInsert_L(LinkList*,int,ElemType);刪除結(jié)點Status

ListDelete_L(LinkList*,int,ElemType

*);銷毀鏈表void

DestoryList_L(LinkList*);逆序鏈表void

InvertList_L(LinkList*);單鏈表的實現(xiàn)（二級指針）初始化一個鏈表L（一級指針接收）×intmain(){……

LinkList

L;InitList_L(L);……}//調(diào)用InitList_Lvoid

InitList_L(LinkList

L){L

=NULL;

}main()InitList_L()L:L:

20000000*L:

-567578356^形參為一級指針，不能成功！初始化一個鏈表L（無頭結(jié)點）√int

main(){……

LinkList

L;InitList_L(&L);

//調(diào)用InitList_L……}void

InitList_L(LinkList

*L){

*L

=

NULL;

}main()InitList_L()&LL:L:

^*L:

-567578356形參必須為二級指針！第一個結(jié)點（一級指針接收）

×main()ListInsert_L()∧L:^e********L:形參為一級指針，不能成功！L=new

LNode;第一個結(jié)點（二級指針接收）

√main()ListInsert_L()&LL:^e形參為二級指針，成功！********L:*L

=

new

LNode;刪除第一個結(jié)點（一級指針接收）

×main()ListDelete_L()********L:########L:形參為一級指針，不能成功！a1a2…an^p=L;L

=

p->next;delete

p;p刪除第一個結(jié)點（二級指針接收）

√main()ListDelete_L()&LL:形參為二級指針，成功！a1a2…an^p=*L;*L

= p->next;delete

p;########L:p結(jié)點的鏈表為了方便鏈表操作，可以在單鏈表的第一個結(jié)點之前附設一個結(jié)點，稱為頭結(jié)點。頭結(jié)點的指針指向第一個結(jié)點，此時如果鏈表為空，則頭結(jié)點的指針域為空。^La1a2……anL8.5.5

單鏈表的實現(xiàn)（

結(jié)點）初始化鏈表Status

InitList_L(LinkList*);LNode*InitList_L();建立鏈表

Status

Crea ist_L(LinkList,

ElemType[],

int);判斷鏈表是否空

Status

ListEmpty_L(LinkList);遍歷鏈表void

ListTraverse_L(LinkList,void

(*)(ElemType));void

ListTraverse_L(LinkList);求鏈表長度int

ListLength_L(LinkList);某元素

Status

Ge em_L(LinkList,

int,

ElemType

*);查詢鏈表元素int

LocateElem_L(LinkList,int);LNode*

LocateElem_L(LinkList

L,

ElemType);結(jié)點Status

ListInsert_L(LinkList,int,ElemType);Status

ListDelete_L(LinkList,

int

m,

ElemType

*);刪除結(jié)點Status

ListDelete_L(LinkList,int,ElemType

*);Status

ListDelete_L(LinkList

L,

ElemTypee);銷毀鏈表void

DestoryList_L(LinkList*);逆序鏈表void

InvertList_L(LinkList);初始化一個鏈表L（結(jié)點）×LinkList

L;InitList_L(L);//調(diào)用InitList_Lvoid

InitList_L

(LinkList

L)main()InitList_L()L:L:

20000000*L:

-567578356********形參為一級指針，不能成功！{

L

=

newLNode;(*L)->next

=

NULL;}^初始化一個鏈表L（

結(jié)點）√LinkList

L;InitList_L(&L);//調(diào)用InitList_Lvoid

InitList_L

(LinkList*

L){main()InitList_L()&LL:L:

*********L:

-567578356形參必須為二級指針！^*L=

new

LNode;(*L)->next

=

NULL;}L:

********第一個結(jié)點（結(jié)點）

√main()ListInsert_L()LL:^e結(jié)點，一級指針，成功！L->next

=

new

LNode;刪除第一個結(jié)點（結(jié)點）

√main()ListDelete_L()L:

********LL:結(jié)點，一級指針，成功！a1a2…an^pp

=

L->next;L->next

=

p->next;delete

p;初始化鏈表(

結(jié)點)Status

InitList_L(LinkList

*L){*L

=(LinkList)malloc(sizeof(LNode));//*L=

new

LNode;if

(*L

==NULL){ErrorMessage("內(nèi)存不足!");return

FALSE;//return

OVERFLOW;}(*L)->next

=

NULL;return

TRUE;}初始化鏈表(

結(jié)點)LNode

*InitList_L(){LinkList

L

=

(LinkList)malloc(sizeof(LNode));if

(L

==

NULL){ErrorMessage("內(nèi)存不足!");return

NULL;}L->next

=

NULL;return

L;}逆序建立鏈表(

結(jié)點)StatusCrea ist_L(LinkList

L,

ElemType

a[],

int

n){LNode

*s;

int

i;if(n

==

0)

return

TRUE;for

(i=0;

i<n;

i++){s

=

(LNode*)malloc(sizeof(LNode));if

(s

==

NULL){return

FALSE;}s->data=a[i];//也可以輸入s->next=L->next;L->next=s;}return

TRUE;}正序建立鏈表(

結(jié)點)StatusCrea ist_L(LinkList

L,

ElemType

A[],

int

n){LNode

*p=L,*s;//p為尾指針if

(n

==

0)

return

TRUE;for

(int

i=0;

i<n;i++){s

=

(LNode*)malloc(sizeof(LNode));;if(s

==

NULL){return

FALSE;}s->data=A[i];p->next=s;p

=

s;}p->next=NULL;return

TRUE;}判斷鏈表是否空(

結(jié)點)Status

ListEmpty_L(LinkList

L){if

(L->next)

//L->next!=NULLreturn

FALSE;elsereturn

TRUE;}遍歷鏈表(

結(jié)點)void

ListTraverse_L(LinkList

L){LNode

*

p=

L->next;while(p){printf("%3d",

p->data);p=

p->next;}printf("\n");}遍歷鏈表(

結(jié)點)void

ListTraverse_L(LinkList

L,void

(*visit)(ElemType)){LNode*

p=

L->next;while(p){(*visit)(p->data);p=p->next;}}求鏈表長度

(

結(jié)點)int

ListLength_L(LinkList

L){LNode

*

p=

L->next;int

n=

0;while(p){n++;p=p->next;}return

n;}某元素(

結(jié)點)Status

Ge em_L(LinkList

L,

int

m,

ElemType

*e){//用e返回鏈表中位序為m的元素值if

(L==NULL)return

FALSE;LNode

*p=L->next;inti=1;while(p

&&

i<m){i++;p

=p->next;}if(p){*e

=

p->data;return

TRUE;}elsereturnFALSE;}查詢鏈表元素位序(

結(jié)點)int

LocateElem_L(LinkList

L,

ElemType

e){//找查找與e相等的元素位置，不存在返回0LNode

*p=L->next;inti=

1;while(p

&&

p->data!=

e){p

=

p->next;i++;}if(p)

return

i;else

return

0;}查詢鏈表元素位序(

結(jié)點)LNode*

LocateElem(LinkList

L,

int

e){

//查找與e相等的元素的地址，不存在返回NULL。LNode

*p=L->next;while(

p

&&p->data

!=e

)p=p->next;return

p;}結(jié)點(

結(jié)點)Status

ListInsert_L(LinkList

L,

int

m,

ElemType

e){

//將e前

第m個結(jié)點之前if(m<1

||

m

>ListLength_L(L)+1)

return

FALSE;LNode

*p

=

L->next;LNode

*s

=

(LNode*)malloc(sizeof(LNode));;if(s

==

NULL){

return

FALSE;

}s->data

=

e;if(m

==

1){s->next

=

L->next;

L->next

=

s;return

TRUE;}for

(int

i=1;i<m-1;i++)//找前驅(qū)p=

p->next;s->next=p->next;p->next=s;//

結(jié)點return

TRUE;}結(jié)點(

結(jié)點)Status

ListInsert_L(LinkList

L,

int

x,

ElemType

e){

//

將e前

元素x之前LNode

*p

=

L->next,

*q

=

L->next;while

(q

&&

q->data

!=

x)

{p=q;

//p是q的前驅(qū)q=

q->next;}if

(q==NULL)

return

FALSE;

//沒找到eLNode

*s=(LNode

*)malloc(sizeof(LNode));if

(s==NULL){return

FALSE;}s->data

=e;if

(p==q){//q是第一個結(jié)點L->next

=s;p->next

=s;s->next

=

L->next;}

else

{s->next

=

p->next;}return

TRUE;}刪除結(jié)點(

結(jié)點)Status

ListDelete_L(LinkList

L,

int

m,

ElemType

*e){

//刪除帶有頭結(jié)點的鏈表L的