C語言-第7章結(jié)構(gòu)體(成).ppt

1、第7章 結(jié)構(gòu)體與共用體,Contents,7.1 結(jié)構(gòu)體,7.2 結(jié)構(gòu)體數(shù)組,7.3 指向結(jié)構(gòu)體類型數(shù)據(jù)的指針,7.4 結(jié)構(gòu)體與鏈表,7.5 共用體,7.6 枚舉,7.7 用typedef定義類型,7.1 結(jié)構(gòu)體,前面已介紹過數(shù)組，它存儲的是一組相同類型的數(shù)據(jù)。但在實(shí)際問題中，一組數(shù)據(jù)往往具有不同的數(shù)據(jù)類型。例如，一個(gè)學(xué)生的信息包括學(xué)號、姓名、性別、年齡和成績等。這些數(shù)據(jù)的類型各不相同：姓名為字符型，學(xué)號為整型或字符型，性別為字符型，年齡為整型，成績?yōu)閷?shí)型，這顯然不能用一個(gè)數(shù)組存放。為了解決這一問題，C語言提供了一種構(gòu)造數(shù)據(jù)類型結(jié)構(gòu)體，它能將不同類型的數(shù)據(jù)存放在一起。,一、結(jié)構(gòu)體類型的定義 s

2、truct 結(jié)構(gòu)體名 成員列表 ； 例如，表示學(xué)生基本信息的結(jié)構(gòu)體類型可定義如下： struct student int num; char name20; char sex; int age; float score; ;,7.1 結(jié)構(gòu)體,二、結(jié)構(gòu)體類型變量的定義 1、先定義結(jié)構(gòu)體再定義變量 struct student ; struct student stu1, stu2; 為了使用方便，可以通過宏定義用一個(gè)符號常量來表示一個(gè)結(jié)構(gòu)體類型，還可以用typedef來自定義數(shù)據(jù)類型。 #define STUDENT struct student STUDENT int num; ; STUDE

3、NT stu1, stu2;,7.1 結(jié)構(gòu)體,typedef 已有類型名 新類型名； 如：typedef int INTEGER; 則 INTEGER i; 等價(jià)于 如：typedef int NUM10; 則 NUM a; 等價(jià)于 如：typedef char *STRING; 則 STRING p; 等價(jià)于 如：typedef struct int num; STUDENT; STUDENT stu1, stu2;,int i;,int a10;,char *p;,7.1 結(jié)構(gòu)體,由此可見，一個(gè)C程序結(jié)構(gòu)一般為： #include /*文件包含處理*/ #define /*宏定義*/ ty

4、pedef struct /*定義結(jié)構(gòu)體類型*/ STUDENT; int max(int x, int y); /*函數(shù)說明*/ main() /*主函數(shù)*/ int max(int x, int y) /*子函數(shù)*/ ,7.1 結(jié)構(gòu)體,注意： （1）結(jié)構(gòu)體類型所占字節(jié)數(shù)=各成員所占字節(jié)數(shù)之和。 （2）如何求結(jié)構(gòu)體類型所占字節(jié)數(shù)？ 運(yùn)算符sizeof求某種數(shù)據(jù)類型所占字節(jié)數(shù)。 如：sizeof(int)=2 sizeof(float)=4 sizeof(struct student)= 2、定義類型同時(shí)定義變量 struct student stu1, stu2;,2+20+1+2+4=29

5、,7.1 結(jié)構(gòu)體,3、直接定義結(jié)構(gòu)體類型變量（無結(jié)構(gòu)體名） struct stu1, stu2; 說明： （1）一般采用“先定義類型再定義變量”。 （2）成員名可與程序中的變量同名，但表示的是兩個(gè)不同的量。 （3）成員也可以為一個(gè)結(jié)構(gòu)體。如： struct date int year; int month; int day; ;,struct student struct date birthday; ;,7.1 結(jié)構(gòu)體,三、結(jié)構(gòu)體變量的初始化 （按順序依次給各成員賦初值） 如：struct student stu=100, “Liu”, M, 19, 95.5; 不能寫成： struct s

6、tudent stu; stu=100, “Liu”, M, 19, 95.5; 說明：C允許對結(jié)構(gòu)體變量進(jìn)行初始化，但不允許將一組常量通過賦值語句直接賦給一個(gè)結(jié)構(gòu)體變量。,7.1 結(jié)構(gòu)體,四、結(jié)構(gòu)體變量的引用 相同類型的結(jié)構(gòu)體變量可相互整體賦值，但一般情況下，不能整體引用，只能對各個(gè)成員分別引用。 如： struct student stu1, stu2=100, “Liu”, M, 19, 95.5; stu1=stu2; 如：printf(“ “, stu1); 引用成員方式：結(jié)構(gòu)體變量名成員名 如：printf(“ “, stu1.num, , ); 正確。 注意：若

7、成員本身為一個(gè)結(jié)構(gòu)體，則需一級一級展開，只能對最低級的成員進(jìn)行引用。 如：printf(“ “, stu1.birthday);,正確,錯(cuò)誤,錯(cuò)誤,7.1 結(jié)構(gòu)體,printf(“ “, stu1.birthday.year, stu1.birthday.month, stu1.birthday.day); 正確。 【例7-1】設(shè)計(jì)一個(gè)程序，輸入一個(gè)學(xué)生的信息并顯示。 【程序分析】 假設(shè)學(xué)生信息包括：學(xué)號、姓名、性別、年齡和成績，則定義一個(gè)結(jié)構(gòu)體類型struct student表示學(xué)生信息。,7.1 結(jié)構(gòu)體,struct student int num; char name20; char s

8、ex; int age; float score; ;,【程序源代碼】 #include stdio.h #include string.h struct student int num; char name20; char sex; int age; float score; main() struct student student1; char ch;float x; printf( input sutdent1 information:n); printf(num name age sex scoren); scanf(%d,7.1 結(jié)構(gòu)體,ch=getchar(); scanf(%c

9、, ,7.1 結(jié)構(gòu)體,結(jié)構(gòu)體數(shù)組是指每個(gè)元素為同一結(jié)構(gòu)體類型的數(shù)組。 一、結(jié)構(gòu)體數(shù)組的定義 struct student int num; char name20; char sex; int age; float score; ; struct student stu3; 定義了一個(gè)數(shù)組stu，該數(shù)組有3個(gè)元素，均為struct student類型，包含5個(gè)成員（如圖7-2所示）。,7.2 結(jié)構(gòu)體數(shù)組,7.2 結(jié)構(gòu)體數(shù)組,二、結(jié)構(gòu)體數(shù)組的初始化 如：struct student stu3=100, “Li”, F, 20, 80, 101, “Xiao”, M, 19, 90, 102, “

10、Chen”, M, 18, 95;,【例7-2】求四個(gè)學(xué)生的五門課的平均成績并輸出。 【程序分析】 假設(shè)學(xué)生信息包括：學(xué)號、姓名、5門課成績、平均分，則定義一個(gè)結(jié)構(gòu)體類型struct chengji表示學(xué)生信息。 struct chengji int num; char name10; float s5; float aver; ; 該題要對4個(gè)學(xué)生的信息進(jìn)行處理，故需定義一個(gè)結(jié)構(gòu)體數(shù)組stud4，將4個(gè)學(xué)生信息存入。 struct chengji stud = ,；,三、結(jié)構(gòu)體數(shù)組的應(yīng)用,7.2 結(jié)構(gòu)體數(shù)組,求第i個(gè)學(xué)生5門課成績（studi.s0,studi.s4）的平均分，賦給studi

11、.aver。 studi.aver=0; for(j=0;j5;j+) studi.aver+=studi.sj; studi.aver/=5.0; 【程序源代碼】 #include”stdio.h” struct chengji int num; char name10; float s5; float aver; ; /*結(jié)構(gòu)體類型定義*/,7.2 結(jié)構(gòu)體數(shù)組,main() int i ,j; struct chengji stud =111, “zhang san”,67,89,76, 54,86,0,105, “l(fā)i si”,87,73,88,75,78,0,109, “wang wu

12、”,79,82,56,64,77,0,107, “zhang na”,60,53,91,75, 65,0; /*結(jié)構(gòu)體數(shù)組定義及初始化*/ for(i=0;i4;i+) for(j=0;j5;j+) studi.aver+=studi.sj; studi.aver/=5.0; printf(“%d % -10s %3.0f %3.0f %3.0f %3.0f %3.0f %5.1f n”,studi.num,, studi.s0, studi.s1, studi.s2, studi.s3,studi.s4, studi.aver); ,7.2 結(jié)構(gòu)體數(shù)組,【例7-3】有三個(gè)

13、候選人，10個(gè)人投票，每人只能投一個(gè)候選人的票，統(tǒng)計(jì)三個(gè)候選人的總票數(shù)。 【程序分析】 定義一個(gè)結(jié)構(gòu)體類型struct person表示候選人信息（包括姓名、票數(shù)）。 struct person char name8; int count; ; 定義一個(gè)結(jié)構(gòu)體數(shù)組leader3存放3個(gè)候選人信息，并進(jìn)行初始化，首先使票數(shù)都置零。 struct person leader3= ZHANG,0, WANG,0, LI,0;,7.2 結(jié)構(gòu)體數(shù)組,如何統(tǒng)計(jì)票數(shù)？ 輸入一個(gè)被選人的名字（用字符數(shù)組lead_name存放），然后將該名字與3個(gè)候選人的名字進(jìn)行比較，若與某候選人名字（即leaderj.nam

14、e）相同，則該候選人的票數(shù)加1（即leaderj.count+），直至10個(gè)人投完票。 【程序源代碼】 #include stdio.h #include string.h struct person char name8; int count; ; main() int i,j; struct person leader3= ZHANG,0, WANG,0, LI,0; char lead_name8;,7.2 結(jié)構(gòu)體數(shù)組,for(i=1;i=10;i+) /*統(tǒng)計(jì)票數(shù)*/ scanf(%s,lead_name); for(j=0;j3;j+) if(strcmp(lead_name,lea

15、)=0) leaderj.count+; for(j=0;j3;j+) printf(%8s: %dn,,leaderj.count); ,練習(xí)：有3個(gè)學(xué)生，每個(gè)學(xué)生信息包括：學(xué)號、姓名、三門課成績，請輸入3個(gè)學(xué)生的信息并輸出。,7.2 結(jié)構(gòu)體數(shù)組,一、指向結(jié)構(gòu)體變量的指針 如：struct student int num; ; struct student stu=100, “Liu”, M, 98; struct student *p; p=,(*p).num,p-num,7.3 指向結(jié)構(gòu)體類型數(shù)據(jù)的指針,由此可見：結(jié)構(gòu)體成員的引用方式（3種）:

16、結(jié)構(gòu)體變量名成員名 (*p)成員名 p-成員名 注意： (*p).num及p-num表示：p所指結(jié)構(gòu)體變量中的成員num 區(qū)分：p-n, p-n+, +p-n,7.3 指向結(jié)構(gòu)體類型數(shù)據(jù)的指針,二、指向結(jié)構(gòu)體數(shù)組的指針 如： struct student int num; char name20; char sex; float score; ; struct student stu3=100, “Li”, F, 80, 101, “Xiao”, M, 90, 102, “Chen”, M, 95; struct student *p=stu;（則p+1指向下一個(gè)元素stu1） 通過指針p輸出

17、3個(gè)學(xué)生的信息，如何實(shí)現(xiàn)？ for(; pnum, p-name, p-sex, p-score);,7.3 指向結(jié)構(gòu)體類型數(shù)據(jù)的指針,三、結(jié)構(gòu)體變量作函數(shù)參數(shù) 采取 “值傳遞” ，將實(shí)參（各成員）的值傳遞給形參，形參也必須是同類型的結(jié)構(gòu)體變量。 【例7-6】有一個(gè)結(jié)構(gòu)體變量stu，內(nèi)含學(xué)生學(xué)號、姓名和3門課程的成績。編程輸出該結(jié)構(gòu)體變量各成員的值。要求定義一個(gè)函數(shù)list輸出一個(gè)結(jié)構(gòu)體變量的值。 【程序源代碼】 #include stdio.h struct student int num; char name20; float score3; void list(struct studen

18、t stu2) printf(%d,%s,%5.1f,%5.1f,%5.1fn,stu2.num,,stu2.score0,stu2.score1,stu2.score2); ,7.3 指向結(jié)構(gòu)體類型數(shù)據(jù)的指針,main() struct student stu1=1001, LiLin,67.5,89,78; list(stu1);/*調(diào)用list函數(shù)*/ 四、結(jié)構(gòu)體指針作函數(shù)參數(shù) 如：struct student int num; char name20; char sex; float score; ; main() struct student stu3=100, “

19、Li”, F, 80, 101, “Xiao”, M, 90, 102, “Chen”, M, 95; output(stu, 3); ,7.3 指向結(jié)構(gòu)體類型數(shù)據(jù)的指針,void output(struct student *p, int n) /*輸出指針p所指結(jié)構(gòu)體數(shù)組中n個(gè)元素的各成員值*/ struct student *p_end=p+n; for(; pnum, p-name, p-sex, p-score); ,7.3 指向結(jié)構(gòu)體類型數(shù)據(jù)的指針,一、鏈表概述 假設(shè)定義這樣一個(gè)結(jié)構(gòu)體： struct node int data; struct node *next; /*next

20、是指向該類結(jié)構(gòu)體的指針*/ 再定義3個(gè)該類型的結(jié)構(gòu)體變量： NODE n1, n2, n3; 執(zhí)行下列語句： n1.data=10; n2.data=20; n3.data=30; n1.next= n3.next=NULL,typedef NODE;,7.4 結(jié)構(gòu)體與鏈表,通常在鏈表中設(shè)立一個(gè)指針head指向第一個(gè)結(jié)點(diǎn)，稱為“頭指針”。 當(dāng)head所指鏈表為空時(shí)head=NULL，則判鏈表非空的條件是？,使得n1, n2和n3“鏈接”起來（如下圖所示）：,我們將這樣的表（通過指針將若干個(gè)元素鏈接起來的表）稱為“鏈表”，表中的每一個(gè)結(jié)構(gòu)體稱為“結(jié)點(diǎn)”。n2稱為n1的“后繼”結(jié)點(diǎn)，n1稱為n2的

21、“前驅(qū)”結(jié)點(diǎn)。,由此可見，鏈表的每個(gè)結(jié)點(diǎn)由兩部分構(gòu)成：數(shù)據(jù)域(data)、指針域(next)。,7.4 結(jié)構(gòu)體與鏈表,二、鏈表的建立 【例7-9】編寫一個(gè)創(chuàng)建鏈表的函數(shù)：輸入若干學(xué)生的信息存入鏈表中，以學(xué)號為0作為結(jié)束標(biāo)志。 【程序分析】用什么存放這若干學(xué)生的信息？用“數(shù)組”？數(shù)組長度如何確定？可不可以根據(jù)輸入學(xué)生信息的個(gè)數(shù)來確定數(shù)組長度？若輸入10個(gè)學(xué)生信息，就定義為10，輸入20個(gè)，就定義為20？ struct student int num; int n=0; scanf(%d%f,7.4 結(jié)構(gòu)體與鏈表,不能。因?yàn)镃語言中，數(shù)組長度必須預(yù)先定義好，不能動(dòng)態(tài)定義。如果數(shù)組長度定義得過大則浪

22、費(fèi)內(nèi)存空間，若過小則不夠用。對于這一類問題（即：用戶所需的內(nèi)存空間取決于實(shí)際輸入的數(shù)據(jù)而無法預(yù)先確定），用數(shù)組很難解決。為此，C語言提供了一些動(dòng)態(tài)分配內(nèi)存空間的函數(shù)，稱為“動(dòng)態(tài)存儲分配函數(shù)”，可以按需要?jiǎng)討B(tài)地分配內(nèi)存空間，也可把不再使用的空間回收。,7.4 結(jié)構(gòu)體與鏈表,我們主要介紹2個(gè)動(dòng)態(tài)存儲分配函數(shù)： (類型說明符 *)malloc(size) 功能：分配一個(gè)長度為size字節(jié)的連續(xù)空間。函數(shù)返回值是一個(gè)指針，即該段空間的起始地址。如：char *pc; int *pi; pc=(char *)malloc(100); 或者 pi=(int *)malloc(100); 表示分配100個(gè)字

23、節(jié)的內(nèi)存空間，該空間用來存放字符型數(shù)據(jù)，函數(shù)返回值強(qiáng)制轉(zhuǎn)換為字符型指針，并將該指針賦給指針變量pc。簡言之，也就是分配一塊大小為100字節(jié)的內(nèi)存空間，用指針pc指向。 free(void *p) 功能：回收（釋放）p所指的內(nèi)存空間。,7.4 結(jié)構(gòu)體與鏈表,【例7-9】建立單鏈表的基本思想：先建立一個(gè)空表，再將各結(jié)點(diǎn)逐個(gè)插入到表尾。 設(shè)頭指針head，指針p指向當(dāng)前表尾結(jié)點(diǎn)，指針s指向創(chuàng)建的新結(jié)點(diǎn)。 建立一個(gè)空表。,p=head=NULL;,7.4 結(jié)構(gòu)體與鏈表,將第1個(gè)結(jié)點(diǎn)插入到表尾。 輸入第1個(gè)學(xué)生信息 scanf(%d%f,7.4 結(jié)構(gòu)體與鏈表,將其它各結(jié)點(diǎn)插入到表尾。 輸入下一個(gè)學(xué)生信息

24、 scanf(%d%f,7.4 結(jié)構(gòu)體與鏈表,將最后一個(gè)結(jié)點(diǎn)的next域置空。 p-next=NULL;,7.4 結(jié)構(gòu)體與鏈表,注：可合并在一塊 if(head=NULL) head=s; else p-next=s;,【程序源代碼】 struct student int num; /*學(xué)號*/ float score; /*成績*/ struct student *next; /*指向下一個(gè)結(jié)點(diǎn)的指針*/ ; struct student *create() /*創(chuàng)建一個(gè)鏈表，返回其頭指針*/ struct student *head,*p,*s; int num; float score;

25、 scanf(%d%f,7.4 結(jié)構(gòu)體與鏈表,while (num!=0) if (head=NULL) head=s; /*若插入第一個(gè)結(jié)點(diǎn)*/ else p-next=s; /*若插入其它結(jié)點(diǎn)*/ p=s; /*p指向新的表尾*/ scanf(%d%f, /*返回鏈表的頭指針*/ ,7.4 結(jié)構(gòu)體與鏈表,【例7-10】定義一個(gè)函數(shù)：輸出頭指針head所指單鏈表中各結(jié)點(diǎn)的值（簡稱為：輸出單鏈表head）。 void print(struct student *head) struct student *p; for(p=head; ; ) printf(%d,%3.1fn,p-num ,p-

26、score ); ,p=p-next,p!=NULL,思考/練習(xí)：編程：輸入若干學(xué)生的信息存入鏈表中并輸出，以學(xué)號為0作為結(jié)束標(biāo)志。,7.4 結(jié)構(gòu)體與鏈表,三、鏈表的插入 在*p后插入*s 設(shè)p指向鏈表中某結(jié)點(diǎn)，s指向待插入的新結(jié)點(diǎn)，將*s插入到*p的后面，插入操作如下圖所示。 注意：兩個(gè)指針的操作順序不能交換。,s-next=p-next; p-next=s;,7.4 結(jié)構(gòu)體與鏈表,在*p前插入*s 先找到*p的前驅(qū)*q，再插入。,設(shè)鏈表頭指針為head，操作如下： q=head; while ( ) q=q-next; /*找*p的直接前驅(qū)*/ s-next=q-next; q-next=

27、s;,q-next!=p,7.4 結(jié)構(gòu)體與鏈表,由此可見： 在鏈表上進(jìn)行插入操作，必須首先找到插入位置的前一個(gè)結(jié)點(diǎn)。 鏈表的插入，通常是先修改待插結(jié)點(diǎn)*s的next指針，再修改插入位置的前一個(gè)結(jié)點(diǎn)的next指針。,【例7-11】已有一個(gè)學(xué)生鏈表，各結(jié)點(diǎn)是按照學(xué)號（num）由小到大順序排列的。編寫一個(gè)插入函數(shù)insert，插入一個(gè)新生的結(jié)點(diǎn)，要求插入后的鏈表依然有序。 【程序分析】 設(shè)s指向待插入結(jié)點(diǎn)（即新生結(jié)點(diǎn)），p指向?qū)W生鏈表的第一個(gè)結(jié)點(diǎn)（即第一個(gè)學(xué)生），從第一個(gè)結(jié)點(diǎn)開始，不斷將p所指結(jié)點(diǎn)的成員num（學(xué)號）與s所指結(jié)點(diǎn)的成員num（學(xué)號）進(jìn)行比較，若s-num大于p-num，則移動(dòng)p指針，

28、指向下一個(gè)結(jié)點(diǎn)，繼續(xù)比較，直到s-nump-num為止或者p指向尾結(jié)點(diǎn)之后結(jié)束。這時(shí)找到了插入位置，將*s插入到*p的前面，而鏈表的插入需要找到插入位置的前一個(gè)結(jié)點(diǎn)，所以還需找到*p的前驅(qū)，用q指向。,7.4 結(jié)構(gòu)體與鏈表,注意兩種特殊情況：一是鏈表為空，二是s-num第一個(gè)結(jié)點(diǎn)的成員num，這兩種情況都需要修改頭指針。 【程序源代碼】 struct student *insert(struct student *head,struct student *s) /*將s所指新生的結(jié)點(diǎn)插入到head所指的學(xué)生鏈表中，插入后使得該鏈表仍然有序，函數(shù)返回插入后的鏈表頭指針*/ struct stud

29、ent *p,*q; if(head=NULL|s-numnum) /*表空或待插結(jié)點(diǎn)第一個(gè)結(jié)點(diǎn)時(shí)*/ s-next=head;head=s;return; q=head;p=q-next; /*q指向第一個(gè)結(jié)點(diǎn)，p指向第二個(gè)結(jié)點(diǎn)，即q指向*p的前驅(qū)*/,7.4 結(jié)構(gòu)體與鏈表,while(p!=NULL ,7.4 結(jié)構(gòu)體與鏈表,q=head; while (q-next!=p) q=q-next; /*找*p的直接前驅(qū)*/ q-next=p-next; free(p);,四、鏈表的刪除 設(shè)p指向鏈表中某結(jié)點(diǎn)，刪除*p，操作如下： 先找到*p的前驅(qū)*q，再刪除。,7.4 結(jié)構(gòu)體與鏈表,由此可見：

30、在鏈表上進(jìn)行刪除操作，必須先找到刪除位置的前一個(gè)結(jié)點(diǎn)。,【例7-12】編寫一個(gè)刪除函數(shù)del，刪除鏈表中指定學(xué)號所在的結(jié)點(diǎn)。 【程序分析】 設(shè)p指向?qū)W生鏈表的第一個(gè)結(jié)點(diǎn)，從第一個(gè)結(jié)點(diǎn)開始，不斷將p所指結(jié)點(diǎn)的成員num（學(xué)號）與指定學(xué)號num進(jìn)行比較，若p-num不等于num，則移動(dòng)p指針，指向下一個(gè)結(jié)點(diǎn)，繼續(xù)比較，直到p-num = num為止或者p指向尾結(jié)點(diǎn)之后結(jié)束。這時(shí)找到了待刪除結(jié)點(diǎn)，即*p，而鏈表的刪除需要找到刪除位置的前一個(gè)結(jié)點(diǎn)，所以還需找到*p的前驅(qū)，用q指向。 注意3種特殊情況：一是鏈表為空時(shí)不能刪除；二是找到的待刪結(jié)點(diǎn)是第一個(gè)結(jié)點(diǎn)，這時(shí)需要修改頭指針；三是待刪結(jié)點(diǎn)不存在。,7.

31、4 結(jié)構(gòu)體與鏈表,【程序源代碼】 struct student *del(struct student *head,int num) /*在head所指的學(xué)生鏈表中刪除其學(xué)號等于num的結(jié)點(diǎn)，返回刪除后的鏈表頭指針*/ struct student *p,*q; if (head=NULL) /*如果是空鏈表*/ printf(“List is nulln”);return(head); p=head; while(p!=NULL ,7.4 結(jié)構(gòu)體與鏈表,練習(xí)： 在一個(gè)單鏈表中，已知q所指結(jié)點(diǎn)是p所指結(jié)點(diǎn)的前驅(qū)，若在*q和*p之間插入s所指結(jié)點(diǎn)，則執(zhí)行_。 A. s-next=p-next;

32、p-next=s; B. p-next=s-next; s-next=p; C. q-next=s; s-next=p; D. p-next=s; s-next=q; 在一個(gè)單鏈表中，若刪除p所指結(jié)點(diǎn)的后繼結(jié)點(diǎn)，則執(zhí)行_。 A. p=p-next-next; B. p=p-next; p-next=p-next-next; C. p-next=p-next; D. p-next=p-next-next;,7.4 結(jié)構(gòu)體與鏈表,五、鏈表的應(yīng)用舉例 【例7-13】編寫一個(gè)函數(shù)：將鏈表L中的元素逆置，逆置前表中元素為（a1,a2,an），逆置后表中元素為（an,a2,a1）。要求用原有結(jié)點(diǎn)，不能重新

33、申請結(jié)點(diǎn)。,7.4 結(jié)構(gòu)體與鏈表,【程序分析】 設(shè)指針p指向表中各結(jié)點(diǎn)，設(shè)指針s指向待插入結(jié)點(diǎn)。首先讓p指向第一個(gè)結(jié)點(diǎn)，接著將表L置空，即L=NULL；然后讓s指向*p作為當(dāng)前待插入結(jié)點(diǎn)，p指向下一個(gè)結(jié)點(diǎn)，并將*s插入到,L的表頭，接著再讓s指向*p作為當(dāng)前待插入結(jié)點(diǎn)，直到p指向表尾之后，即p為空結(jié)束。此時(shí)得到的就是一個(gè)逆置的鏈表。 【程序源代碼】 struct node *invert(struct node *L) /*將鏈表L中的元素逆置，逆置后返回頭指針*/ struct node *p,*s; p=L; L=NULL; while(p!=NULL) s=p; p=p-next; /*

34、將*p作為當(dāng)前待插結(jié)點(diǎn)，用s指向，p指向下一個(gè)結(jié)點(diǎn)*/ s-next=L; L=s; /*將*s插入到表頭*/ return( L ); ,7.4 結(jié)構(gòu)體與鏈表,【例7-14】將兩個(gè)遞增有序的鏈表A、B，歸并成一個(gè)遞增有序的單鏈表C，要求用A、B中的原結(jié)點(diǎn)形成，不能重新申請結(jié)點(diǎn)。 如：A=(3,5,8,11) B=(2,6,9,15,20) 歸并后：C=(2,3,5,6,8,9,11,15,20) 【程序分析】 設(shè)指針t指向C表的表尾。先建立一個(gè)空表C，即C=t=NULL；再依次比較A、B表中的相應(yīng)元素，將較小者插入到C的表尾，得到的C表則為遞增有序的。 設(shè)三個(gè)指針變量p, q和s，其中p,

35、q分別指向A、B表中某個(gè)結(jié)點(diǎn)，s指向當(dāng)前待插結(jié)點(diǎn)。若p-datadata，則讓s指向p所,7.4 結(jié)構(gòu)體與鏈表,指結(jié)點(diǎn)作為當(dāng)前待插結(jié)點(diǎn)，并將p指向A的下一個(gè)結(jié)點(diǎn)；否則，讓s指向*q作為當(dāng)前待插結(jié)點(diǎn)，并將q指向B的下一個(gè)結(jié)點(diǎn)。接著將待插結(jié)點(diǎn)*s插入到C的表尾，然后繼續(xù)比較p-data與q-data，直到其中一個(gè)表歸并完。最后將另一個(gè)表的剩余部分鏈接到C的表尾。 【程序源代碼】 struct node *merge(struct node *A, struct node *B) /*將兩個(gè)遞增有序的鏈表A、B歸并成一個(gè)遞增有序的鏈表C，函數(shù)返回C表頭指針*/ struct node *C,*t,*

36、p,*q,*s; p=A; q=B;/*p,q分別指向A,B表中第一個(gè)結(jié)點(diǎn)*/ C=t=NULL;/*建立一個(gè)空表C*/,7.4 結(jié)構(gòu)體與鏈表,while(p!=NULL ,7.4 結(jié)構(gòu)體與鏈表,一、共用體類型的定義 如：union data int a; float b; char c6; ; 二、共用體變量的定義 1、定義（類似“結(jié)構(gòu)體”，也有3種） 如：union data ; union data udata;,7.5 共用體,2、共用體與結(jié)構(gòu)體的區(qū)別 （1）結(jié)構(gòu)體中各成員占用連續(xù)的不同的內(nèi)存單元，而共用體中各成員占用相同的內(nèi)存單元（故稱為“共用體”多個(gè)不同類型的數(shù)據(jù)共同占用同一內(nèi)存單

37、元）。 （2）結(jié)構(gòu)體類型的長度等于各成員長度之和，而共用體類型的長度等于最長成員的長度。如： struct data int a; float b; char c6; a;,union data int a; float b; char c6; b;,問： a占？字節(jié)，b占？字節(jié)。 12 6,7.5 共用體,三、共用體變量的引用 1、不能整體引用共用體變量，只能引用成員。 2、不允許對共用體變量進(jìn)行初始化，每次只能給一個(gè)成員賦值。 如： union data int a; float b; char c6; udata=10,85.5, “jsj”; 錯(cuò)誤。 如：udata.a=10; uda

38、ta.b=85.5; strcpy(udata.c, “jsj”);,如： union data udata; udata =10,85.5, “jsj”; 錯(cuò)誤。,正確。,7.5 共用體,共用體變量的特點(diǎn)： （1）共用體變量的地址和它各成員的地址相同。 （2）共用體變量不能整體賦值，不能整體輸入輸出。 （3）在共用體變量所占內(nèi)存空間中，任一時(shí)刻只能存放其中的一個(gè)成員，而不是同時(shí)存放所有成員。即任一時(shí)刻只有一個(gè)成員有效，也就是說共用體變量的所有成員不是同時(shí)都存在和有效。 如：union data int i; char ch; float fa; a.i=1; a.ch=A; a.f=3.5;

39、 則：printf(“%d, %c, %fn”, a.i, a.ch, a.f); printf(“%fn”, a.f);,問：此時(shí)，哪個(gè)成員有效？ a.f有效，a.i和a.ch均無意義。,錯(cuò)誤。,正確。,7.5 共用體,【例7-15】設(shè)有一個(gè)教師與學(xué)生通用的表格，教師數(shù)據(jù)有姓名，年齡，職業(yè)，教研室四項(xiàng)。學(xué)生有姓名，年齡，職業(yè)，班級四項(xiàng)。編程輸入人員數(shù)據(jù)，再以表格輸出。 【程序分析】 根據(jù)題意，每個(gè)人員信息包含4項(xiàng)，故定義一個(gè)結(jié)構(gòu)體類型struct person包含4個(gè)成員，其中，“職業(yè)”一項(xiàng)可用“t”表示教師，用“s”表示學(xué)生，故“職業(yè)”定義成字符型；而“單位”這一項(xiàng)學(xué)生應(yīng)填入班級編號，教師

40、應(yīng)填入教研室名，班級編號可用整型表示，教研室名只能用字符型數(shù)組存放。,7.5 共用體,也就是說，此時(shí)“單位”這一項(xiàng)中包含了兩種不同類型的數(shù)據(jù)，而且這兩種數(shù)據(jù)不可能同時(shí)存在，要么填入的是班級編號，要么填入的是教研室名，故需將其定義為共用體類型。類型定義如下： struct person char name10; int age; char job; /*職業(yè)*/ union int class; /*班級編號*/ char office10; /*教研室名*/ depa; /*單位*/ ;,7.5 共用體,struct person body2; /*定義結(jié)構(gòu)體數(shù)組存放兩個(gè)人員信息*/ 如果輸入（輸出）的人員是學(xué)生（即bodyi.job=s），則輸入班級編號存入bodyi.depa.class中；否則輸入教研室名存入bodyi.depa.office中。如下所示： if(bodyi.job=s) scanf(%d,7.5 共用體,main() struct person body2; int i; for(i=0;i2;i+) /*輸入*/ printf(input name,age,job and departmentn); scanf(%s %d %c, ,7.5 共用體,for(i=0;i2;i+) /*輸出*/ if(bodyi.job