第11章 用结构封装数据

第11章算法和数据结构基础——用结构封装数据哈尔滨工业大学11.1结构体类型及其应用

——变形金刚之组合金刚本节主要讨论如下问题：（1）如何声明一个结构体类型？如何为数据类型定义一个别名？（2）如何定义一个结构体变量、数组或指针？如何通过它们访问结构体的成员？（3）可以对结构体执行哪些操作？不能执行哪些操作？（4）如何计算结构体在内存中占用的字节数？11.1.1结构体类型的声明和结构体变量的定义如何表示多个学生的信息呢？11.1.1结构体类型的声明和结构体变量的定义内存分配不集中，结构零散，内存管理困难，寻址效率不高对数组赋初值时，易发生错位相同类型的数据单独放在一起存储逻辑相关但类型不同的数据放在一起存储structstudent{

longID;

charname[10];

chargender;

intbirthyear;

intscore[4];};structstudent{

longID;

charname[10];

chargender;

intbirthyear;

intscore[4];};结构体成员(StructureMember)结构体标签(StructureTag)，可省略结构体模板(StructureTemplate)编译器不为其分配内存

关键字typedef为已存在的类型定义一个别名structstudent{

longID;

charname[10];

chargender;

intbirthyear;

intscore[4];

};typedef

structstudentSTUDENT;typedefstructstudent{

longID;

charname[10];

chargender;

intbirthyear;

intscore[4];

}STUDENT;11.1.1结构体类型的声明和结构体变量的定义（1）先定义结构体类型

再定义变量名structstudentstu1;structstudent{ longID; charname[10]; chargender; intbirthyear; intscore[4];};（2）在定义结构体类型

的同时定义变量structstudent{ longID; charname[10]; chargender; intbirthyear; intscore[4];}stu1;11.1.1结构体类型的声明和结构体变量的定义结构体变量的定义（3）直接定义结构体变量（不指定结构体标签）struct{ longID; charname[10]; chargender; intbirthyear; intscore[4];}stu1;在定义结构体变量的同时对其进行初始化STUDENT

stu1={100310121,"王刚",'M',1991,{72,83,90,82}};structstudent

stu1={100310121,"王刚",'M',1991,{72,83,90,82}};初始化列表中成员的顺序必须和结构体类型定义的顺序一致11.1.2结构体成员的初始化和访问typedefstructstudent{longID;charname[10];chargender;intbirthyear;intscore[4];}STUDENT;结构体数组的定义和初始化typedefstructstudent{longID;charname[10];chargender;intbirthyear;intscore[4];}STUDENT;typedefstructdate{ intyear;

intmonth; intday;}DATE;11.1.2结构体成员的初始化和访问结构体指针的定义和初始化

STUDENT

stu1;

STUDENT

*pt;pt=&stu1;如何定义指向结构体变量的指针？

STUDENT

*pt=&stu1;等价于11.1.2结构体成员的初始化和访问typedefstructstudent{longID;charname[10];chargender;intbirthyear;intscore[4];}STUDENT;typedefstructdate{ intyear; intmonth; intday;}DATE;inta[5];访问数组的元素通过下标（位置）选择数组元素访问结构体变量的成员通过名字访问结构体的成员typedefstructstudent{longID;charname[10];chargender;intbirthyear;intscore[4];}STUDENT;STUDENTstu;11.1.2结构体成员的初始化和访问访问结构体变量的成员成员选择运算符（圆点运算符）对嵌套的结构体成员，必须以级联方式访问stu1.studentID=100310121;stu1.studentName="王刚";//errorstrcpy(stu1.studentName,"王刚");stu1.studentSex='M';stu1.birthday.year=1991;stu1.birthday.month=5;stu1.birthday.day=19;11.1.2结构体成员的初始化和访问typedefstructstudent{longID;charname[10];chargender;intbirthyear;intscore[4];}STUDENT;STUDENTstu;如何访问结构体指针变量指向的结构体成员呢？ptstu1成员1成员2成员3成员4成员5通过成员选择运算符访问stu1.studentID=1;(*pt).studentID=1;

通过指向运算符访问pt->studentID=1;通过结构体指针访问结构体成员

STUDENT

stu1;

STUDENT

*pt=&stu1;如何定义指向结构体变量的指针？

11.1.1结构体类型的声明和结构体变量的定义typedefstructstudent{longID;charname[10];chargender;intbirthyear;intscore[4];}STUDENT;typedefstructdate{ intyear; intmonth; intday;}DATE;当结构体嵌套时，如何访问结构体指针变量指向的结构体成员？

stu1.

birthday.

year=1999;(*pt).

birthday.

year=1999;

pt->

birthday.

year=1999;通过结构体指针访问结构体成员typedefstructstudent{longID;charname[10];chargender;intbirthyear;intscore[4];}STUDENT;typedefstructdate{ intyear; intmonth; intday;}DATE;11.1.1结构体类型的声明和结构体变量的定义在一个结构体内包含了另一个结构体作为其成员11.1.3结构体与数组的嵌套typedefstructstudent{longID;charname[10];chargender;intbirthyear;intscore[4];}STUDENT;typedefstructdate{ intyear;

intmonth; intday;}DATE;typedefstructdate{ intyear;

charmonth[10]; intday;}DATE;STUDENT

stu1={100310121,"王刚",'M',{1991,5,19},{72,83,90,82}};STUDENT

stu1={100310121,"王刚",'M',{1991,"May",19},{72,83,90,82}};

STUDENT

stu[30];

STUDENT

*pt;pt=stu;

如何定义指向结构体数组的指针？

STUDENT

*pt=stu;等价于STUDENT

*pt=&stu[0];等价于ptstu[30]stu[0]stu[1]stu[2]stu[3]stu[4]......stu[29]typedefstructstudent{longID;charname[10];chargender;intbirthyear;intscore[4];}STUDENT;typedefstructdate{ intyear; intmonth; intday;}DATE;11.1.3结构体与数组的嵌套pt->studentID等价于(*pt).studentIDstu[0].studentID如何访问结构体指针指向的结构体数组成员？stu[30]ptstu[0]stu[1]stu[2]stu[3]stu[4]......stu[29]pt++是什么意思？

STUDENT

stu[30];

STUDENT

*pt=stu;pt=&stu[0];

typedefstructstudent{longID;charname[10];chargender;intbirthyear;intscore[4];}STUDENT;typedefstructdate{ intyear; intmonth; intday;}DATE;11.1.3结构体与数组的嵌套11.1.4结构体占内存的字节数结构体类型占用内存字节数是所有成员占内存的总和吗？【例11.1】下面程序用于演示结构体所占内存字节数的计算方法。#include<stdio.h>typedefstructsample{charm1;intm2;charm3;}SAMPLE;//定义结构体类型SAMPLEintmain(void){SAMPLEs={'a',2,'b'}; //定义结构体变量s并对其进行初始化

printf("bytes=%d\n",sizeof(s));//打印结构体变量s所占内存字节数

return0;}内存对齐（Memory-alignment）对于大多数计算机，数据项要求从某个数量字节的倍数开始存放short型数据从偶数地址开始存放，而int型数据则被对齐在4字节地址边界为了满足内存地址对齐的要求，需要在较小的成员后加入补位结构体在内存中所占的字节数不仅与所定义的结构体类型有关，还与计算机系统本身有关11.1.4结构体占内存的字节数1.结构体变量的赋值操作typedefstructstudent{longID;charname[10];chargender;intbirthyear;intscore[4];}STUDENT;STUDENT

stu1={100310121,"王刚", 'M',{1991,5,19},{72,83,90,82}};STUDENTstu2;stu2=stu1;只能在相同类型的结构体变量之间进行赋值stu2.ID=stu1.ID;strcpy(,);stu2.gender=stu1.gender;stu2.birthday.year=stu1.birthday.year;stu2.birthday.month=stu1.birthday.month;stu2.birthday.day=stu1.birthday.day;for(i=0;i<4;i++){ stu2.score[i]=stu1.score[i];}11.1.5结构体的相关计算和操作2.结构体变量的取地址值操作11.1.5结构体的相关计算和操作&stu1.ID是结构体变量stu1的ID成员即stu1.ID的地址。不是stu1的地址。虽然&stu1.ID与&stu1具有相同的地址值，但二者的实际内涵是不同的，前者是结构体成员的地址，后者是结构体变量的地址，这两个地址的基类型是不同的。11.2用结构体封装函数参数向函数传递结构体的单个成员复制单个成员的内容向函数传递结构体的完整结构复制结构体的所有成员Before:0,0,0After:0,0,0【例11.2】下面程序用于演示结构体变量作函数参数实现按值调用。intmain(){

POINTposition={0,0,0};printf("Before:%d,%d,%d\n",position.x,position.y,position.z);Func(position);printf("After:%d,%d,%d\n",position.x,position.y,position.z);return0;}typedefstructpoint{intx;inty;intz;}POINT;voidFunc(POINTp){

p.x=1;

p.y=1;

p.z=1;}复制结构体的所有成员给函数函数对结构体内容的修改不影响原结构体p=position;p.x=position.x;p.y=position.y;p.z=position.z;11.2.1在函数之间传递结构体数据intmain(){

POINTposition={0,0,0};printf("Before:%d,%d,%d\n",position.x,position.y,position.z);Func(&position);printf("After:%d,%d,%d\n",position.x,position.y,position.z);return0;}Before:0,0,0After:1,1,1向函数传递结构体变量的地址typedefstructpoint{intx;inty;intz;}POINT;voidFunc(POINT*pt){

pt->x=1;

pt->y=1;

pt->z=1;}函数对结构体的修改影响原结构体position.x=1;position.y=1;position.z=1;pt=&position;11.2.1在函数之间传递结构体数据【例11.3】修改例11.2程序，改用结构体指针变量作函数参数，观察和分析程序的运行结果有何变化。intmain(){

POINTposition={0,0,0};printf("Before:%d,%d,%d\n",position.x,position.y,position.z);

position=

Func(position);printf("After:%d,%d,%d\n",position.x,position.y,position.z);return0;}typedefstructpoint{intx;inty;intz;}POINT;POINTFunc(POINTp){

p.x=1;

p.y=1;

p.z=1;returnp;}返回结构体变量也可得到修改的结构体内容，但效率低Before:0,0,0After:1,1,111.2.1在函数之间传递结构体数据【例11.4】下面程序用于演示从函数返回结构体变量的值。intmain(){

POINTposition={0,0,0};POINTnewPosition;printf("Before:%d%d%d\n",position.x,position.y,position.z);

newPosition=*Func(&position);printf("After:%d%d%d\n",position.x,position.y,position.z);printf("After:%d,%d,%d\n",newPosition.x,newPosition.y,newPosition.z);return0;}typedefstructpoint{intx;inty;intz;}POINT;POINT*Func(POINT*pt){

pt->x=1;

pt->y=1;

pt->z=1;returnpt;}11.2.1在函数之间传递结构体数据【例11.5】下面程序用于演示从函数返回结构体变量的指针。Before:0,0,0After:1,1,1After:1,1,1精简参数个数使函数接口更简洁

用结构体类型封装函数参数的好处是什么？可扩展性好【例11.6】继2008年夏奥会之后，2022年冬奥会花落北京，北京成为世界上首座“双奥之城”。在2022年冬奥会上，中国冰雪健儿勇夺9金、4银、2铜，取得了我国参加冬奥会的历史最好成绩，为祖国和人民赢得了荣誉，实现了运动成绩和精神文明双丰收。现在请编程，输入n个国家的国名及获得的奖牌数，然后输出奥运奖牌排行榜。11.2.2结构体应用实例1：奥运奖牌排行榜intmain(void){intn;structcountrycountries[M];printf("Howmanycountries?");scanf("%d",&n);printf("Inputnamesandmedals:\n");for(inti=0;i<n;i++){scanf("%s%d",countries[i].name,&countries[i].medals);}SortString(countries,n);printf("Sortedresults:\n");for(inti=0;i<n;i++){printf("%s:%d\n",countries[i].name,countries[i].medals);}return0;}#include<stdio.h>#include<string.h>#defineM250//最多的字符串个数#defineN20//每个字符串的最大长度structcountry{charname[N];intmedals;};voidSortString(structcountryc[],intn);11.2.2结构体应用实例1：奥运奖牌排行榜//按奖牌数降序排序voidSortString(structcountryc[],intn){intt;chartemp[N];for(inti=0;i<n-1;i++){for(intj=i+1;j<n;j++){if(c[j].medals<c[i].medals){strcpy(temp,c[i].name);strcpy(c[i].name,c[j].name);strcpy(c[j].name,temp);t=c[i].medals;c[i].medals=c[j].medals;c[j].medals=t;}}}}11.2.2结构体应用实例1：奥运奖牌排行榜//按奖牌数降序排序voidSortString(structcountryc[],intn){for(inti=0;i<n-1;i++){for(intj=i+1;j<n;j++){if(c[j].medals>c[i].medals){SwapChar(c[i].name,c[j].name);SwapInt(&c[i].medals,&c[j].medals);}}}}voidSwapInt(int*x,int*y){intt;t=*x;*x=*y;*y=t;}voidSwapChar(char*x,char*y){chart[N];strcpy(t,x);strcpy(x,y);strcpy(y,t);}11.2.2结构体应用实例1：奥运奖牌排行榜//按奖牌数降序排序voidSortString(structcountryc[],intn){structcountrytemp;for(inti=0;i<n-1;i++){for(intj=i+1;j<n;j++){if(c[j].medals>c[i].medals){temp=c[i];c[i]=c[j];c[j]=temp;}}}}11.2.2结构体应用实例1：奥运奖牌排行榜//按奖牌数降序排序voidSortString(structcountryc[],intn){for(inti=0;i<n-1;i++){for(intj=i+1;j<n;j++){if(c[j].medals>c[i].medals){SwapStruct(&c[i],&c[j]);}}}}voidSwapStruct(structcountry*x,

structcountry*y){structcountryt;t=*x;*x=*y;*y=t;}//按奖牌数降序排序voidSortString(structcountry*p,intn){for(inti=0;i<n-1;i++){for(intj=i+1;j<n;j++){if((p+j)->medals>(p+i)->medals){SwapStruct(p+i,p+j);}}}}11.2.2结构体应用实例1：奥运奖牌排行榜【例11.7】请编程，输入n个国家的国名及获得的奖牌数，然后输入一个国名，查找其获得的奖牌数。intSearchString(structcountrycountries[],intn,charname[]){for(inti=0;i<n;i++){if(strcmp(name,countries[i].name)==0){returni;}}return-1;}intmain(void){intn;structcountrycountries[M];chars[N];printf("Howmanycountries?");scanf("%d",&n);printf("Inputnamesandmedals:\n");for(inti=0;i<n;i++){scanf("%s%d",countries[i].name,&countries[i].medals);}printf("Inputthesearchingcountry:");scanf("%s",s);intpos=SearchString(countries,n,s);if(pos!=-1)printf("%s:%d\n",s,countries[pos].medals);elseprintf("Notfound!\n");return0;}11.2.2结构体应用实例1：奥运奖牌排行榜【例11.7】请编程，输入n个国家的国名及获得的奖牌数，然后输入一个国名，查找其获得的奖牌数。intSearchString(structcountry*pCountries,intn,charname[]){structcountry*p=pCountries;for(;p<pCountries+n;p++){if(strcmp(name,p->name)==0){returnp-pCountries;}}return-1;}11.2.2结构体应用实例1：奥运奖牌排行榜【例11.8】“一万小时定律”是作家格拉德威尔在《异类》一书中指出的定律，“人们眼中的天才之所以卓越非凡，并非天资超人一等，而是付出了持续不断的努力。1万小时的锤炼是任何人从平凡变成世界级大师的必要条件”。他将此称为“一万小时定律”。简而言之，要成为某个领域的专家，需要10000小时，按比例计算就是：如果每天工作八个小时，一周工作五天，那么成为一个领域的专家至少需要五年。假设某人从1990年1月1日起开始每周工作五天，然后休息两天。请编写一个程序，计算这个人在以后的某一天中是在工作还是在休息。11.2.3结构体应用实例2：一万小时定律【例11.7】请编程，输入n个国家的国名及获得的奖牌数，然后输入一个国名，查找其获得的奖牌数。intmain(void){DATEtoday;intn;do{printf("Inputyear,month,day:");n=scanf("%d,%d,%d",&today.year,&today.month,&today.day);if(n!=3){while(getchar()!='\n');}}while(n!=3||!IsLegalDate(today));if(WorkORrest(today)==1){printf("Heisworking\n");}else{printf("Heishavingarest\n");}return0;}#include<stdio.h>#include<stdlib.h>typedefstructdate{intyear;intmonth;intday;}DATE;intWorkORrest(DATEd);intIsLeapYear(inty);intIsLegalDate(DATEd);11.2.3结构体应用实例2：一万小时定律intWorkORrest(DATEd){intdayofmonth[2][12]={{31,28,31,30,31,30,31,31,30,31,30,31},{31,29,31,30,31,30,31,31,30,31,30,31}};intsum=0;for(inti=1990;i<d.year;++i){sum=sum+(IsLeapYear(i)?366:365);}intleap=IsLeapYear(d.year)?1:0;for(inti=1;i<d.month;++i){sum=sum+dayofmonth[leap][i-1];}sum=sum+d.day;sum=sum%7;//以5天为一个周期，看余数是几，决定是在工作还是在休息

returnsum==0||sum==6?-1:1;}11.2.3结构体应用实例2：一万小时定律//函数功能：判断y是否是闰年，若是，则返回1，否则返回0intIsLeapYear(inty){return((y%4==0&&y%100!=0)||(y%400==0))?1:0;}//函数功能：判断日期d是否合法，若合法，则返回1，否则返回0intIsLegalDate(DATEd){intdayofmonth[2][12]={{31,28,31,30,31,30,31,31,30,31,30,31},{31,29,31,30,31,30,31,31,30,31,30,31}};if(d.year<1||d.month<1||d.month>12||d.day<1){return0;}intleap=IsLeapYear(d.year)?1:0;returnd.day>dayofmonth[leap][d.month-1]?0:1;}11.2.3结构体应用实例2：一万小时定律每张牌分为4种花色(Suit)黑桃(Spades)、红桃(Hearts)、草花(Clubs)、方块(Diamonds)每种花色有13张牌面(Face)A，2，3，4，5，6，7，8，9，10，Jack，Queen，King第一种方法用二维数组deck[4][13];11.2.4结构体应用实例3：洗发牌模拟【例11.9】一副扑克有52张牌，分为4种花色（suit）：红桃（Hearts）、方块（Diamonds）、草花（Clubs）、黑桃（Spades）。每种花色又有13张牌面（face）：A，2，3，4，5，6，7，8，9，10，Jack，Queen，King。如何用一种较为直观和自然的方式来表示52张扑克牌呢？如何模拟洗发牌呢？请编写一个程序，模拟洗牌和发牌过程。第二种方法用结构体数组

问题：如何表示第1张牌的花色和牌面？card[0].suitcard[0].face

typedefstructcard{ charsuit[10];/*花色*/ charface[10];/*牌面*/}CARD;

CARDcard[52];

11.2.4结构体应用实例3：洗发牌模拟typedefstructcard{charsuit[10];charface[10];}CARD;intmain(void){char*suit[]={"Hearts","Diamonds","Clubs","Spades"};char*face[]={"A","2","3","4","5","6","7","8","9","10","Jack","Queen","King"};CARDcard[52];srand(time(NULL));FillCard(card,face,suit);Shuffle(card);Deal(card);return0;}voidFillCard(CARDwCard[],char*wFace[],char*wSuit[]){for(inti=0;i<52;++i){strcpy(wCard[i].suit,wSuit[i/13]);strcpy(wCard[i].face,wFace[i%13]);}}11.2.4结构体应用实例3：洗发牌模拟//函数功能：将52张牌的顺序打乱以模拟洗牌过程voidShuffle(CARD*wCard){CARDtemp;intj;for(inti=0;i<52;++i)//每次循环产生一个随机数，交换当前牌与随机数指示的牌

{j=rand()%52;//每次循环产生一个0~51的随机数

temp=wCard[i];wCard[i]=wCard[j];wCard[j]=temp;}}11.2.4结构体应用实例3：洗发牌模拟洗牌算法每次循环生成一个0~51之间的随机数j然后将result中的发牌序号result[i]与随机选出的result[j]进行交换//函数功能：输出每张牌的花色和面值以模拟发牌过程voidDeal(CARD*wCard){for(inti=0;i<52;++i){printf("%9s%9s%c",wCard[i].suit,wCard[i].face,i%2==0?'\t':'\n');}}11.3共用体类型和枚举类型用户自定义数据类型结构体，也称结构（struct）把关系紧密且逻辑相关的多种不同类型的的变量，组织到一个统一的名字之下共用体，也称联合（union）把情形互斥但逻辑相关的多种不同类型的变量，组织到一个统一的名字之下structperson

{charname[20];chargender;intage;

union

maritalStatemarital;intmarryFlag;};unionmaritalState{intsingle;/*未婚*/

structmarriedStatemarried;/*已婚*/

structdivorceStatedivorce;/*离婚*/};11.3共用体类型和枚举类型unionmaritalState{intsingle;/*未婚*/

structmarriedStatemarried;/*已婚*/

structdivorceStatedivorce;/*离婚*/};structmarriedState{

structdatemarryDay; charspouseName[20]; intchild;};structdivorceState{

structdatedivorceDay; intchild;};structdate{ intyear; intmonth; intday;};11.3共用体类型和枚举类型structperson{charname[20];charsex;intage;unionmaritalStatemarital;

intmarryFlag;//婚姻状态标记字段};structpersonp1;共用体的一个主要问题：如何标记共用体中当前起作用的成员是哪一个？if(p1.marryFlag==1){ //未婚}elseif(p1.marryFlag==2){ //已婚}else{//离婚}

每次对共用体的成员赋值时，程序负责改变标记字段的内容11.3共用体类型和枚举类型#include<stdio.h>typedefunionsample{ shorti; charch; floatf;}SAMPLE;intmain(void){ printf("bytes=%d\n",sizeof(SAMPLE));//打印共用体类型所占内存字节数

return0;}11.3共用体类型和枚举类型【例11.10】下面程序用于演示共用体所占内存字节数的计算方法。共用体的第1个应用——节省存储空间共用体的第二个应用——构造混合的数据结构typedefunion{

inti;

floatf;}NU