第10章結(jié)構(gòu)體與鏈表本章要點(diǎn)：結(jié)構(gòu)體類型與結(jié)構(gòu)體變量的定義結(jié)構(gòu)體變量的引用與初始化結(jié)構(gòu)體數(shù)組鏈表處理共用體類型和枚舉類型學(xué)習(xí)方法建議：結(jié)合第二章的數(shù)據(jù)類型，了解屬于構(gòu)造類型的結(jié)構(gòu)體類型、共用體類型、枚舉類型，比較它們的相同點(diǎn)和區(qū)別，通過(guò)例題掌握這些數(shù)據(jù)類型的定義和使用，并在此基礎(chǔ)上掌握鏈表的應(yīng)用。本章的難點(diǎn)是鏈表的應(yīng)用。1．問(wèn)題描述——構(gòu)建手機(jī)通訊錄眾所周知，手機(jī)中有一個(gè)簡(jiǎn)單的通訊錄工具，用于管理聯(lián)系人的基本信息，其基本功能包括對(duì)聯(lián)系人信息的新建、修改、刪除和查詢等。2．引例分析要想構(gòu)建手機(jī)通訊錄，應(yīng)創(chuàng)建聯(lián)系人的基本信息，而聯(lián)系人的基本信息應(yīng)該包括姓名、年齡和聯(lián)系電話等，假設(shè)通訊錄最多容納50名聯(lián)系人的信息，建立一個(gè)數(shù)組friends，數(shù)組的大小為50，每一個(gè)數(shù)組元素都應(yīng)存放姓名、年齡和聯(lián)系電話等信息。10.1引例

3．程序代碼#include<stdio.h>#include<string.h>structfriend_list/*手機(jī)通訊錄結(jié)構(gòu)體定義*/{charname[10];/*姓名*/intage;/*年齡*/chartelephone[13];/*聯(lián)系電話*/};main(){intchoice;charname[10];structfriend_listfriends[50];/*包含50個(gè)人的通訊錄*/do{printf("手機(jī)通訊錄功能選項(xiàng)：1:新建2:修改3:刪除4:查詢0:退出\n");printf("請(qǐng)選擇功能:");scanf("%d",&choice);switch(choice){case1:printf("新建聯(lián)系人姓名:");;/*new_friend(friends);*/break;case2:printf("請(qǐng)輸入要修改的聯(lián)系人姓名:");scanf("%s",name);;/*modify_friend(friends,name);*/break;case3:printf("請(qǐng)輸入要?jiǎng)h除的聯(lián)系人姓名:");scanf("%s",name);;/*delete_friend(friends,name);*/break;case4:printf("請(qǐng)輸入要查詢的聯(lián)系人姓名:");scanf("%s",name);;/*search_friend(friends,name);*/break;case0:break;}}while(choice!=0);printf("謝謝使用通信錄功能！\n");}10.2.1結(jié)構(gòu)體類型與結(jié)構(gòu)體變量的定義1.結(jié)構(gòu)體類型定義struct結(jié)構(gòu)體類型名 /*struct是結(jié)構(gòu)體類型關(guān)鍵字*/{數(shù)據(jù)類型數(shù)據(jù)項(xiàng)1;

數(shù)據(jù)類型數(shù)據(jù)項(xiàng)2;……

數(shù)據(jù)類型數(shù)據(jù)項(xiàng)ｎ;}; /*此行分號(hào)不能少！*/其中，struct是定義結(jié)構(gòu)體類型的關(guān)鍵字。結(jié)構(gòu)體類型名的命名規(guī)則，與變量名相同。成員的數(shù)據(jù)類型可以是基本數(shù)據(jù)類型。10.2結(jié)構(gòu)體類型及其變量

【例10.1】定義一個(gè)反映學(xué)生基本情況的結(jié)構(gòu)體類型，用以存儲(chǔ)學(xué)生的信息。structdate /*日期結(jié)構(gòu)體類型：由年、月、日共三項(xiàng)組成*/{intyear;intmonth;intday;};structstd_info/*學(xué)生結(jié)構(gòu)體類型：由學(xué)號(hào)、姓名、性別和生日共四項(xiàng)組成*/{charno[7];charname[9];charsex[3];structdatebirthday;};structscore /*成績(jī)結(jié)構(gòu)體類型：由學(xué)號(hào)和三門成績(jī)共四項(xiàng)組成*/{charno[7];intscore1;intscore2;intscore3;};

2.結(jié)構(gòu)體類型變量定義（1）間接定義法──先定義結(jié)構(gòu)體類型、再定義結(jié)構(gòu)體變量。定義一般格式為：struct結(jié)構(gòu)體類型名{…};/*定義結(jié)構(gòu)體類型*/struct結(jié)構(gòu)體類型名結(jié)構(gòu)體變量表;/*定義結(jié)構(gòu)體類型變量*/（2）直接定義法──在定義結(jié)構(gòu)體類型的同時(shí)定義結(jié)構(gòu)體變量。一般格式為：struct結(jié)構(gòu)體類型名{…}結(jié)構(gòu)體變量表;（3）一次性定義──先定義無(wú)名結(jié)構(gòu)體類型，緊接著定義結(jié)構(gòu)體類型變量。一般格式為：struct{…}結(jié)構(gòu)體變量表;1.結(jié)構(gòu)體變量的引用規(guī)則對(duì)于結(jié)構(gòu)體變量，要通過(guò)成員運(yùn)算符“.”，逐個(gè)引用其成員。結(jié)構(gòu)體變量的引用格式為：結(jié)構(gòu)體變量.成員/*其中的“.”是成員運(yùn)算符*/如果某成員本身又是一個(gè)結(jié)構(gòu)體類型，則只能通過(guò)多級(jí)的分量運(yùn)算，對(duì)最低一級(jí)的成員進(jìn)行引用。此時(shí)的引用格式可擴(kuò)展為：結(jié)構(gòu)體變量.成員.子成員.….最低1級(jí)子成員10.2.2結(jié)構(gòu)體變量的引用與初始化【例10.2】利用例10.1中定義的結(jié)構(gòu)體類型structstd_info，定義一個(gè)結(jié)構(gòu)體變量student，用于存儲(chǔ)和顯示一個(gè)學(xué)生的基本情況。#include"stdio.h"/*定義并初始化一個(gè)外部結(jié)構(gòu)體變量student*/structstd_infostudent={"000102","張三","男",{1980,9,20}};

main(){printf("No:%s\n",student.no);/*引用結(jié)構(gòu)體變量student中的no成員項(xiàng)*/printf("Name:%s\n",);/*引用結(jié)構(gòu)體變量student中的name成員項(xiàng)*/printf("Sex:%s\n",student.sex);/*引用結(jié)構(gòu)體變量student中的sex成員項(xiàng)*/printf("Birthday:");printf("%d-",student.birthday.year);/*引用student中birthday的year成員項(xiàng)*/printf("%d-",student.birthday.month);/*引用birthday的month成員項(xiàng)*/printf("%d\n",student.birthday.day);/*引用student中birthday的day成員項(xiàng)*/}2.結(jié)構(gòu)體變量的初始化與一維數(shù)組的初始化類似，結(jié)構(gòu)體變量初始化的一般格式為：結(jié)構(gòu)體變量={初值表};例如:structstudent{intnum;charname[20];floatscore;}st={1001,"gxl",98};結(jié)構(gòu)體數(shù)組初始化的格式為：結(jié)構(gòu)體數(shù)組[n]＝{{初值表1},{初值表2},...,{初值表n}};【例10.3】首先定義結(jié)構(gòu)體類型structstudent，然后定義一個(gè)結(jié)構(gòu)體數(shù)組st[3]，用于存儲(chǔ)和顯示三個(gè)學(xué)生的基本情況。#include"stdio.h"main(){structstudent{intnum;charname[20];floatscore;}st[3]={{1102,"張三",89},{1105,"李四",89},{1112,"王五",98}};inti;for(i=0;i<3;i++){printf("%6d",st[i].num);printf("%s",st[i].name);printf("%.0f\n",st[i].score);}}

10.3結(jié)構(gòu)體數(shù)組【例10.4】計(jì)算學(xué)生的某科平均成績(jī)和不及格學(xué)生的人數(shù)。#include"stdio.h"structstu{intnum;char*name; charsex;floatscore;}boy[5]={{101,"Liping",'M',45},{102,"Zhangping",'M',62.5},{103,"Hefang",'F',92.5},{104,"Chengling",'F',87},{105,"Wangming",'M',58}};main(){inti,c=0;floatave,s=0;for(i=0;i<5;i++){s+=boy[i].score;if(boy[i].score<60)c+=1;

}printf("s=%f\n",s);

ave=s/5;printf("average=%f\ncount=%d\n",ave,c);}10.4.1指向結(jié)構(gòu)體變量的指針一般來(lái)說(shuō)，如果指針變量pointer已指向結(jié)構(gòu)體變量var，則用指針變量pointer引用結(jié)構(gòu)體變量var成員項(xiàng)可用以下形式：pointer->成員或(*pointer).成員一般地說(shuō)，以下三種形式等價(jià)。var.成員pointer->成員(*pointer).成員

10.4指向結(jié)構(gòu)體類型數(shù)據(jù)的指針【例10.5】使用指向結(jié)構(gòu)體變量的指針來(lái)訪問(wèn)結(jié)構(gòu)體變量的各個(gè)成員。#include"stdio.h"main(){structstudent{intnum;charname[20];floatscore;}st={1102,"張三",89},*p=&st;printf("%6d",p->num);printf("%s",p->name);printf("%.0f\n",p->score);}10.4.2指向結(jié)構(gòu)體數(shù)組的指針如果指針變量p已指向某結(jié)構(gòu)體數(shù)組，則p+1指向結(jié)構(gòu)體數(shù)組的下一個(gè)元素，而不是當(dāng)前元素的下一個(gè)成員?！纠?0.6】使用指向結(jié)構(gòu)體數(shù)組的指針來(lái)訪問(wèn)結(jié)構(gòu)體數(shù)組。#include"stdio.h"main(){structstudent{intnum;charname[20];floatscore;}st[3]={{1102,"張三",89},{1105,"李四",89},{1112,"王五",98}},*p=st;inti;for(i=0;i<3;i++,p++){printf("%6d",p->num);printf("%s",p->name);printf("%.0f\n",p->score);}}10.5.1鏈表結(jié)構(gòu)1．鏈表的概念鏈表是用指針把各個(gè)結(jié)點(diǎn)鏈接在一起，其一般形式如圖所示。10.5鏈表處理

【例10.7】建立一個(gè)簡(jiǎn)單的鏈表，它由3個(gè)存放學(xué)生數(shù)據(jù)（包括學(xué)號(hào)和成績(jī)）的結(jié)點(diǎn)組成，然后輸出各結(jié)點(diǎn)的數(shù)據(jù)。#include"stdio.h"structnode/*定義結(jié)構(gòu)體類型*/{intnum;/*學(xué)號(hào)*/floatscore;/*成績(jī)*/structnode*next;/*指向structnode類型的指針變量*/}main(){structnodea,b,c,*head,*p;a.num=101;a.score=85.4;b.num=103;b.score=96.1;c.num=105;c.score=77.5;head=&a;a.next=&b;b.next=&c;c.next=NULL;p=head;do{printf("學(xué)號(hào)：%d成績(jī)：%5.2f\n",p->num,p->score);p=p->next;}while(p!=NULL);}2．動(dòng)態(tài)存儲(chǔ)分配函數(shù)（1）分配內(nèi)存空間函數(shù)malloc()調(diào)用形式：(類型說(shuō)明符*)malloc(size)；功能：在內(nèi)存的動(dòng)態(tài)存儲(chǔ)區(qū)中分配一塊長(zhǎng)度為“size”字節(jié)的連續(xù)區(qū)域。函數(shù)的返回值為該區(qū)域的首地址。例如：pc=(char*)malloc(sizeof(char));表示分配1個(gè)字節(jié)的內(nèi)存空間，并強(qiáng)制轉(zhuǎn)換為字符類型，函數(shù)的返回值為指向該字節(jié)的指針，把該指針賦予指針變量pc。（2）分配內(nèi)存空間函數(shù)calloc()調(diào)用形式：(類型說(shuō)明符*)calloc(n,size)；功能：在內(nèi)存動(dòng)態(tài)存儲(chǔ)區(qū)中分配n塊長(zhǎng)度為“size”字節(jié)的連續(xù)區(qū)域。函數(shù)的返回值為該區(qū)域的首地址。說(shuō)明：“（類型說(shuō)明符*）”用于強(qiáng)制類型轉(zhuǎn)換。calloc()函數(shù)與malloc()函數(shù)的區(qū)別僅在于一次可以分配n塊區(qū)域。例如：ps=(struetstu*)calloc(2,sizeof(structstu));其中的sizeof(structstu)是求stu的結(jié)構(gòu)體長(zhǎng)度。因此該語(yǔ)句的意思是：按stu的長(zhǎng)度分配2塊連續(xù)區(qū)域，強(qiáng)制轉(zhuǎn)換為stu類型，并把其首地址賦予指針變量ps。（3）釋放內(nèi)存空間函數(shù)free()調(diào)用形式：free(void*ptr)；功能：釋放ptr所指向的一塊內(nèi)存空間，ptr是一個(gè)任意類型的指針變量，它指向被釋放區(qū)域的首地址。被釋放區(qū)應(yīng)是由malloc()或calloc()函數(shù)所分配的區(qū)域?！纠?0.8】分配一塊區(qū)域，輸入一個(gè)學(xué)生數(shù)據(jù)。#include"stdlib.h"#include"stdio.h"main(){structstu{intnum;char*name;charsex;floatscore;}*ps;ps=(structstu*)malloc(sizeof(structstu));ps->num=102;ps->name="Zhangping";ps->sex='M';ps->score=62.5;printf("Number=%d\nName=%s\n",ps->num,ps->name);printf("Sex=%c\nScore=%f\n",ps->sex,ps->score);free(ps);}對(duì)鏈表的常用的操作主要包括創(chuàng)建、插入、刪除和輸出等基本操作。創(chuàng)建鏈表【例10.9】編寫一個(gè)create()函數(shù)，按照規(guī)定的結(jié)點(diǎn)結(jié)構(gòu)，創(chuàng)建一個(gè)單鏈表?；舅悸罚菏紫认蛳到y(tǒng)申請(qǐng)一個(gè)結(jié)點(diǎn)的空間，然后輸入結(jié)點(diǎn)數(shù)據(jù)域中的數(shù)據(jù)項(xiàng)，并將指針域置為空（鏈尾標(biāo)志），最后將新結(jié)點(diǎn)插入到鏈表尾。對(duì)于鏈表的第一個(gè)結(jié)點(diǎn)，還要設(shè)置頭指針變量。本題中設(shè)3個(gè)指針變量head、new1和tail，分別說(shuō)明如下：head：頭指針變量，指向鏈表的第一個(gè)結(jié)點(diǎn)，用作函數(shù)返回值。new1：指向新申請(qǐng)的結(jié)點(diǎn)。tail：指向鏈表的尾結(jié)點(diǎn)，用tail->next=new1，實(shí)現(xiàn)將新申請(qǐng)的結(jié)點(diǎn)，插入到鏈表尾，使之成為新的尾結(jié)點(diǎn)。10.5.2對(duì)鏈表的基本操作#include"stdio.h"#include"malloc.h"#defineNULL0#defineLENsizeof(structstudent) /*定義結(jié)點(diǎn)長(zhǎng)度*/structstudent/*定義結(jié)點(diǎn)結(jié)構(gòu)*/{intnum; /*學(xué)號(hào)*/floatscore; /*成績(jī)*/structstudent*next; /*指針域*/};structstudent*create()/*create()函數(shù):創(chuàng)建單鏈表*/{structstudent*head=NULL,*new1,*tail;intcount=0;/*鏈表中的結(jié)點(diǎn)個(gè)數(shù)(初值為0)*/new1=tail=(structstudent*)malloc(LEN);/*向系統(tǒng)申請(qǐng)一新結(jié)點(diǎn)空間*/scanf("%d%f",&new1->num,&new1->score);while((new1->num)!=0)/*如果學(xué)號(hào)0，則退出*/{count++;/*結(jié)點(diǎn)個(gè)數(shù)加1*/if(count==1)head=new1;/*將新結(jié)點(diǎn)插入到鏈表尾，并設(shè)置新的尾指針*/elsetail->next=new1;/*非首結(jié)點(diǎn),將新結(jié)點(diǎn)插入到鏈表尾*/tail=new1; /*設(shè)置新的尾結(jié)點(diǎn)*/new1=(structstudent*)malloc(LEN);scanf("%d%f",&new1->num,&new1->score);}tail->next=NULL;return(head);/*返回單鏈表的頭指針*/}3.插入操作在結(jié)點(diǎn)a與b之間插入一個(gè)新的結(jié)點(diǎn)x。插入前，結(jié)點(diǎn)a是結(jié)點(diǎn)b的前驅(qū)結(jié)點(diǎn)，結(jié)點(diǎn)b是結(jié)點(diǎn)a的后繼結(jié)點(diǎn)；插入后，新插入的結(jié)點(diǎn)x成為結(jié)點(diǎn)a的后繼結(jié)點(diǎn)、結(jié)點(diǎn)b的前驅(qū)結(jié)點(diǎn)。結(jié)點(diǎn)插入前的鏈表結(jié)點(diǎn)插入后的鏈表算法如下：s=p->next;p->next=s;【例10.10】編寫insert()函數(shù)，完成在單鏈表的第i個(gè)結(jié)點(diǎn)后插入1個(gè)新結(jié)點(diǎn)的操作。structstudent*insert(structstudent*head,structstudent*stu,inti){structstudent*pointer;if(head==NULL)/*若為空鏈表*/head=stu,stu->next=NULL;/*將新結(jié)點(diǎn)插入到空鏈表中*/else /*非空鏈表*/if(i==0)stu->next=head,head=stu;/*使新結(jié)點(diǎn)成為鏈表新的首結(jié)點(diǎn)*/else /*其他位置*/{pointer=head;/*查找單鏈表的第i個(gè)結(jié)點(diǎn)(pointer指向它)*/for(;pointer!=NULL&&i>1;pointer=pointer->next,i--)if(pointer==NULL) /*越界錯(cuò)*/printf("Outoftherange,can'tinsertnewnode!\n");else /*一般情況：pointer指向第i個(gè)結(jié)點(diǎn)*/stu->next=pointer->next,pointer->next=stu;}return(head);}

4.刪除操作刪除結(jié)點(diǎn)x。刪除前，結(jié)點(diǎn)x是結(jié)點(diǎn)b的前驅(qū)結(jié)點(diǎn)、結(jié)點(diǎn)a的后繼結(jié)點(diǎn)；刪除后，結(jié)點(diǎn)a成為結(jié)點(diǎn)b的前驅(qū)結(jié)點(diǎn)，結(jié)點(diǎn)b成為結(jié)點(diǎn)a的后繼結(jié)點(diǎn)。

結(jié)點(diǎn)刪除前的鏈表結(jié)點(diǎn)刪除后的鏈表pa->next=px->next;free(px);【例10.11】編寫一個(gè)dele()函數(shù)，刪除鏈表中學(xué)號(hào)為num的指定結(jié)點(diǎn)。structstudent*dele(structstudent*head,intnum){structstudent*pf,*pb;if(head==NULL)/*若為空表，輸出提示信息*/{printf("\nemptylist!\n");returnhead;}pb=head;while(pb->num!=num&&pb->next!=NULL)/*當(dāng)前結(jié)果不是要?jiǎng)h除的結(jié)點(diǎn)，而且也不是最后一個(gè)結(jié)點(diǎn)時(shí)，繼續(xù)循環(huán)*/{pf=pb;pb=pb->next;}/*pf指向當(dāng)前結(jié)點(diǎn)，pb指向下一結(jié)點(diǎn)*/if(pb->num==num){if(pb==head)head=pb->next;/*找到被刪結(jié)點(diǎn)，且為第一結(jié)點(diǎn)，則使head指向第二個(gè)結(jié)點(diǎn)，否則使pf所指結(jié)點(diǎn)的指針指向下一結(jié)點(diǎn)的后續(xù)*/elsepf->next=pb->next;free(pb);printf("Thenodeisdeleted\n");}elseprintf("Thenodenotbeenfoud!\n");returnhead;}

5.輸出鏈表首先知道head頭指針的值，設(shè)一個(gè)指針變量p，先指向第一個(gè)結(jié)點(diǎn)，輸出p所指的結(jié)點(diǎn)，然后使p后移一個(gè)結(jié)點(diǎn)，再輸出，直到鏈表的尾結(jié)點(diǎn)。【例10.12】輸出鏈表。voidoutput(structstudent*head){structstudent*p;p=head;if(head!=NULL)do{printf("%d%5.1f\n",p->num,p->score);p=p->next;}while(p!=NULL);}

10.6.1共用體共用體類型的定義與結(jié)構(gòu)體類型的定義類似，格式為：

union共用體類型名

{成員列表;};1.間接定義──先定義類型、再定義變量。例如：定義data共用體類型變量un1,un2,un3的語(yǔ)句如下：uniondata{inti;charch;floatf;};uniondataun1,un2,un3;2.直接定義──定義類型的同時(shí)定義變量。union[data]{inti;charch;floatf;}un1,un2,un3;

10.6共用體和枚舉類型枚舉類型的定義為：enum枚舉類型名{取值表};如：enumweekdays{Sun,Mon,Tue,Wed,Thu,Fri,Sat}；枚舉類型變量的定義與結(jié)構(gòu)體變量類似。例如：enumweekdays

{Sun,Mon,Tue,Wed,Thu,Fri,Sat}workday;10.6.2枚舉類型在C語(yǔ)言中，可以用typedef關(guān)鍵字來(lái)為系統(tǒng)已經(jīng)有的數(shù)據(jù)類型定義別名，該別名與標(biāo)準(zhǔn)類型名一樣，可以用來(lái)定義相應(yīng)的變量。例如：

typedefintINTEGER;/*指定別名INTEGER代表int*/typedeffloatREAL;/*指定別名REAL代表float*/INTEGERx,y;等價(jià)于intx,y;REALa,b;等價(jià)于floata,b;10.7定義已有類型的別名也可以聲明一個(gè)新的別名DATE代表一個(gè)結(jié)構(gòu)體類型。例如：typedefstructdate{intmonth;intday;intyear;}DATE;下面可以用DATE定義變量DATEbirthday;/*定義結(jié)構(gòu)體變量*/

上機(jī)實(shí)驗(yàn)1．掌握結(jié)構(gòu)體變量的引用與初始化；2．掌握結(jié)構(gòu)體數(shù)組的應(yīng)用；3．掌握指向結(jié)構(gòu)體類型的指針變量的應(yīng)用。一、實(shí)驗(yàn)?zāi)康?．驗(yàn)證性實(shí)驗(yàn)1）分析并運(yùn)行下面的程序，給出運(yùn)行結(jié)果。#include"stdio.h"structstudent{charname[10];intold;}main(){structstudentstudents[3]={{"wangming",18},{"liyang",19},{"liuping",20}};structstudentstu;inti;for(i=0;i<2;i++){if(students[i].old>students[i+1].old){stu=students[i];students[i]=students[i+1];students[i+1]=stu;}}printf("Theyoungestis%s\n",students[0].name);}二、實(shí)驗(yàn)內(nèi)容2）閱讀并分析下面的程序，上機(jī)運(yùn)行并給出運(yùn)行結(jié)果。voidmain(){structstu{intnum;char*name,sex;floatscore;}*ps;ps=(structstu*)malloc(sizeof(structstu));ps->num=102;ps->name="張海";ps->sex='M';ps->score=62.5;printf("Number=%dName=%s\n",ps->num,ps->name);if(ps->sex=='M')printf("sex:男");elseif(ps->sex=='F')printf("sex:女");printf("Score=%f\n",ps->score);free(ps);}1）學(xué)生的記錄由學(xué)號(hào)和成績(jī)組成，N名學(xué)生的數(shù)據(jù)已在主函數(shù)中放入結(jié)構(gòu)體數(shù)組s中，請(qǐng)將函數(shù)fun補(bǔ)充完整，函數(shù)功能按分?jǐn)?shù)的高低排列學(xué)生的記錄，高分在前。#include<stdio.h>#defineN16typedefstruct{charnum[10];ints;}STREC;intfun(STRECa[]){STRECtmp;inti,j;for(i=0;i<N;i++)for(j=i+1;j<N;j++)if(a[i].s<＿＿①＿＿){tmp=a[i];a[i]=a[j];

＿＿②＿;}}

2．設(shè)計(jì)性實(shí)驗(yàn)2）給定程序中，函數(shù)是將形參std所指結(jié)構(gòu)