《程序设计与C语言》课件第8章

第8章结构体、共用体及枚举类型8.1结构体类型8.2动态数据结构8.3共用体8.4位段8.5枚举类型习题88.1结构体类型8.1.1结构体变量的定义及初始化

1.结构体类型的定义要定义结构体变量，首先要定义结构体类型。结构体类型定义的一般形式是：

struct［〈结构名〉］

{〈成员表〉；

};〈成员表〉∷=〈分量1〉；［〈分量2〉；…］

〈分量〉∷=〈类型标识符〉〈分量名〉其中，符号“∷=”表示“定义为”，方括号中的内容是可选的。例如语句

structdate{intyear;intmonthintday;};就定义了一个表示日期的结构体类型，类型名为structdate。它的三个分量的类型均为整型。对结构体来说，分量的类型可以互不相同，这是它与数组的区别。数组也是构造类型，但它要求各元素具有相同的类型。再如

structstudent{ unsignednum; charname［10］；

intage; loatscore;};定义了一个学生的结构体类型，名字为structstudent，它有4个分量，类型各不相同。结构体类型可以嵌套定义，即结构体的分量类型是另一个结构体类型。以下两种情况都可以定义嵌套的结构体类型：

(1)两个结构体类型的定义是分离的，后者可以把前者作为其分量类型。比如上面已经定义了日期类型，则可以用它来定义学生类型：

structstudent{unsignednum;charname［10］;intage;floatscore;structdatebirthday;};

(2)还可以在一个结构体内部直接嵌套定义：

structstudent{unsignednum;charname［10］;intage;floatscore;struct{intyear;intmonth;intday;}birthday;}

注意：①结构体类型不能递归定义，即分量的类型不能是正在定义的结构体类型。如：

structwrong{inti;structwrongw;}；这样的定义是错误的。②定义结构体类型时，常犯的错误是忽略了最后的分号。

2.结构体变量的定义在定义了类型名之后，就可以定义该类型的变量了。定义结构体变量的方法有三种：

(1)如结构体类型已定义好，则可以用来定义变量。如：

structdatedate1,date2;structstudentstu1,stu2;

注意：在使用结构体类型名时，初学者往往会忽略保留字struct,其实structdate和structstudent都是一个统一的整体，二者缺一不可。

(2)定义结构类型的同时直接定义变量，如

structdate { intyear; intmonth; intday; } date1,date2;

(3)定义结构体类型的同时定义变量，但没有结构名。第(2)和(3)种的差别在于：第(2)种方法既定义了类型名又定义了变量，以后需要时还可以继续定义新的变量，而第(3)种就不能再定义新的变量了，因为它没有结构名。

3.结构体变量赋初值结构体变量可以在定义时赋初值，如语句

structstudentstu1,stu2={63001,″zhang″,18,642.5}；就对结构体变量stu2进行了初始化，实际上是用右边的值对stu2各分量进行初始化，因此提供的初值必须和相应分量的类型一致。两个相同类型的结构体变量之间可以进行赋值操作。如：

stu1=stu2;则使stu1的各分量具有了和stu2各分量一样的值。

4.结构体指针变量的定义除了定义结构体变量之外，还可定义结构体指针变量。如：

structstudentstu1,*p；定义了结构体类型指针p。像其他类型的指针一样，结构体指针只有和某个结构体变量发生了联系，即得到了结构体变量的首地址之后才能被使用。如：

p=&stu1;就把stu1的首地址，即第一个分量的地址赋给了p，p于是指向这个结构体变量，如下图所示。这之后对stu1和对*p的操作效果都是一样的。stu1pnumnameagescore

5.结构体变量的内存分配结构体变量由各分量组成。各分量分配内存的次序和规则与普通变量有所不同。如：structstudent{charname［7］;intage;charsex;floatscore;}stu,*p=&stu;则其内存分配情况如图8-1所示。图8-1结构体变量各分量的内存分配情况从图8-1中可以看出：

(1)结构体变量中各分量内存分配的情况是：按照各分量出现的先后次序，先出现的分量在上面，地址小；后出现的分量在下面，地址大。

(2)数组分量中，下标小的元素在上面，地址小；下标大的元素在下面，地址大。

(3)各分量之间的关系依系统的不同而有所不同。对TurboC来说，各分量之间没有空洞，即不要求各分量按整字边界存放，它们之间是紧凑的。因此，当用sizeof运算符求结构体变量的大小时，其值等于各分量实际字节数之和，此处有：sizeof(stu)=14。而对VisualC++而言，要求各分量按整字边界存放，这样在各分量之间就有可能存在空洞，因此在用sizeof运算符求结构体变量的大小时，必须将这些空洞计算进来，此处有：sizeof(stu)=20。由此可知，在求结构体变量的大小时，必须首先明确是在什么系统中进行的。8.1.2结构体数组及结构体分量的引用

1.结构体数组一个结构体变量可以处理一个对象，如果有多个对象，则需要多个结构体变量，这时应该用结构体数组来处理多个同类型的对象。例如，定义一个产品类型的数组prod：

structproduct{unsignedlongno;charname［15］;intnum;floatprice;}prod［3］；定义结构体变量的其他两种方法也可以用来定义结构体数组。对结构体数组可以初始化，例如

structproductprod［3］={{112346,″football″,56,284.5},{112347,″basketball″,108,256},{112348,″valleyball″,35,96.4}};其逻辑结构如图8-2所示。图8-2结构体数组的逻辑结构这个结构像是二维数组，但它不是真正的数组，它没有行地址和列地址之说，因此对它用指针进行操作时也就没有所谓行指针和列指针的问题，只有一种指向结构体的指针。例如，若定义结构体指针变量p：

structproduct*p;则经过赋值运算“p=prod；”之后，就使p指向了prod数组的第1个元素prod［0］。p++后指向prod［１］，即沿垂直方向向下走一步，指向下一个结构体，而不能说指向下一行。并且它也只能沿着垂直方向前进，而不能沿水平方向前进。至于水平方向的引用则涉及到对结构体分量引用的问题。

2.对结构体分量的引用对结构体分量的引用有三种方法：用点运算符引用；用指向运算符引用；对数组元素的分量用下标加点或指向运算符引用。下面分别加以说明。

(1)用点运算符引用结构体变量的分量的方法，有两种引用形式：

〈结构体变量名〉.〈分量名〉 (*〈结构体指针〉).〈分量名〉即在结构体变量和其分量名之间加一个点运算符。例如：

structproductprod,*p=∏则

prod.num=35; /*等价于(*p).num=35;*/ strcpy(,″football″)；就是对结构体变量prod的分量进行赋值的运算。这时prod.num(或(*p).num)、作为一个独立的变量使用，可以直接进行输入/输出操作。

【例8-1】对结构体分量的引用。＃include<stdio.h>structproduct{unsignedlongno;charname［15］;intnum;floatprice;};main(){structproductprod;prod.no=117364;prod.num=46;prod.price=287.5scanf(″%s″,);printf(″%lu,%s,%d,%f＼n″,prod.no,,prod.num,prod.price);return0;}运行输出：

football↙

117364,football,46,287.5

注意：因为name分量是字符数组，所以不能用赋值语句直接赋值，只能用字符串处理函数strcpy或用scanf函数的控制符“%s”控制输入。

(2)用指向运算符引用结构体指针所指对象的分量的方法，是用结构体指针处理结构体的常用形式，其引用形式为：

〈结构体指针变量〉->〈分量名〉指向运算符由两个字符“-”和“>”组成，它是一个整体，中间没有空格。例如：

p->no=117368;strcpy(p->name,″basketball″);

【例8-2】用指针重做例8-1。＃include<stdio.h>structproduct{unsignedlongno;charname［15］;intnum;floatprice;};main(){structproductprod,*p;p=∏scanf(″%lu%s%d%f″,&p->no,p->name,&p->num,&p->price);printf(″%lu,%s,%d,%f＼n″,p->no,p->name,p->num,p->price);return0;}运行输出：

117364valleyball75197.6↙

117364valleyball75197.6输入时应注意，数字和后面的字符串之间可以不留空格，编译器会自动识别数字的终结，但字符串和后面的数字之间必须有空格，否则编译器会把数字也当作字符看待。

(3)用下标加点运算符引用结构体数组元素的分量的方法，其引用形式为：

〈数组名〉［〈下标〉］.〈分量名〉

注意：下标和数组名紧密相连，不可分离，不能把下标放在分量名后面。例如：

structproductprod［３］；则

prod［2］.price=78.5;是正确的引用，而prod.price［２］则是错误的写法。

【例8-3】建立和输出有3个元素的产品结构体数组，并输出价格最高的产品的所有信息。＃include<stdio.h>structproduct{unsignedlongno;charname［15］;intnum;floatprice;struct{intyear,month,day;}}outdate;}prod［３］；main(){inti,j;floatmax=0;structproduct*p=prod;puts(″Inputprod［3］:＼n″);for(i=0;i<=2;i++)scanf(″%lu%s%d%f%d%d%d″,&prod［i］.nu,prod［i］.name,&prod［i］.num,&prod［i］.price,&prod［i］.outdate.year,&prod［i］.outdate.month,&prod［i］.outdate.day);printf(″Theprod［３］arrayis:＼n″);for(i=0;i<=2;i++){print(″%lu,%s,%d,%.2f,&d/%d/%d＼n″,p->no,p->name,p->num,p->price,p->outdate.year,p->outdate.month,p->outdate.day);p++;printf(″＼n″);}for(i=0;i<=2;i++)if(prod［i］.price>max){max=prod［i］.price;j=i;}printf(″Elementhavinghighestprice:＼n″);printf(″%lu,%s,%d,%.2f,%d,%d,%d＼n″,prod［j］.no,prod［j］.name,prod［j］.num,prod［j］.price,prod

［i］.outdate.year,prod［j］.outdate.month,prod［j］,outdate.day);return0;}运行输出：

Inputprod［3］：

11111aaaaa8999.22001119↙

22222bbbbb76100.4200218↙33333ccccc96187200284Theprod［3］arrayis：

11111aaaaa8999.202001/11/922222bbbbb76100.402002/1/833333ccccc96187.002002/8/4Elementhavinghighestprice:33333ccccc96187.002002/8/4本例中prod［３］是一个嵌套的结构体类型数组，其中出厂日期分量outdate是一个结构体类型。在对嵌套的结构体分量进行引用时，必须连续使用点运算符，以达到分量的最底层，这时才可以对各分量进行输入/输出操作。比如第i个元素的出厂年份的表示为：prod［i］.outdate.year,这个序列是个整体，相当于一个整型变量，可以对它进行读/写。

(4)用指向运算符也可以引用结构体数组元素的分量，因为对结构体数组可以用指针进行处理。例如有定义：

structproductprod［3］,*p;令p=prod，则p指向数组prod的第1个元素，p++指向下一个元素，每个元素又是结构体,仍要用“->”运算符求其分量,如图8-3所示。用指针来引用结构体分量时，要注意“->”运算符的优先级最高，它把前后两部分连成一个不可分割的整体，因此，p->num++等价于(p->num)++，即先取出p所指结构体的num分量的当前值，然后对它加1；++p->num等价于++(p->num)，即对num分量加1；(++p)->num是先把p移向数组的下一个元素，再求该元素的num分量；(p++)->num是先把p所指结构的num分量取出，再把p向下移一个元素。为了加深对结构体指针和结构体数组的理解，我们可以分析下面的程序。图8-3结构体数组的指针处理

【例8-4】分析下面程序的输出结果。＃include<stdio.h>structsinl{char*s;inti;structsinl*slp;};main(){staticstructsinla［］= {{″abcd″,1,a+1}, {″efgh″,2,a+2}, {″ijkl″,3,a}};structsinl*p=a;inti; printf(″a［0］.s=%s＼tp->s=%s＼ta［2］.slp->s=%s＼n＼n″,a［0］.s,p->s,a［2］.slp->s);for(i=0;i<2;i++)printf(″--a［%d］.i=%d＼t++a［%d］.s［3］=%c＼n″,i,--a［i］.i,i,++a［i］.s［3］)；

printf(″++(p->s)=%s＼ta［(++p)->i］.s=%s＼t″″a［--(p->slp->i)］.s=%s＼n″,++(p->s)，

a［(++p)->i］.s,a［--(p->slp->i)］.s);return0;}运行输出：

a［０］.s=abcdp->s=abcda［2］.slp->s=abcd--a［0］.i=0++a［0］.s［3］=e--a［1］.i=1++a［１］.s［3］=i++(p->s)=fgia[(++p)->i].s=abcea[--(p->slp->i)].s=abce程序中定义了一个结构体数组a并初始化。从初始化的数据看有三个结构体。图8-4画出了这三个结构体中指针的指向。图8-4结构体中指针的指向在定义的结构体中，分量slp是指向自身结构的指针，这种结构称为自引用结构。slp又称为“链接”，它能够把一个structsinl结构体与另一个同样的结构体链接在一起。因为slp是指针，所以这不是递归定义。结构体中有一个分量的名字为i，而在主函数中，i又被定义成一个新的整型变量，两者是否会冲突?答案是不会，因为它们所处的地方不同，作用也不同。①由图8-3可知，a［０］的s分量是指向字符串的指针；p->s为p所指对象的s分量，即a［0］的s分量，是一个指针；a［2］.slp->s为a［２］的slp分量所指对象的s分量，也即a［０］的s分量。这三种表示是等价的，因而输出也相同，为“abcd”。②因为--a［i］.i等价于--(a［i］.i)，即以a［i］的i分量的值减1作为输出结果，所以--a［0］.i=0,--a［1］.i=1，于是a［0］.i=0,a［i］.i=1。③因为++a［i］.s［3］=++(a［i］.s［3］)，s是指向字符串中第一个字符的指针，s+3为指向该串第3+1个字符的指针，又因为s［3］=*(s+3)，即s［3］为该串第3+1个字符，所以++a［i］.s［3］表示a［i］的s分量指向的字符串中的第3+1个字符加1(即其后继字符)，所以++a［0］.s［3］=e,++a［1］.s［3］=i，于是a［0］.s指向“abce”，a［1］.s指向“efgi”。在下面的输出中，以TurboC对函数参数由右向左进行求值的顺序，先计算并输出a［--(p->slp->i)］.s,然后是a［(++p)->i］.s，最后是++(p->s)，且左边的求值受右边求值的影响。④求a［--(p->slp->i)］.s：这时p指向a［0］,p->slp->i，即a［1］.i,它的值已变为1，再对它进行自减运算得a［1］.i=0,于是a［0］.s指向“abce”。⑤求a［(++p)->i］.s：因p指向a［0］,则++p使p指向a［1］，而a［1］的i分量的值已变为0，则a［(++p)->i］.s仍是求a［0］.s所指字符串，即“abce”。⑥求++(p->s)：因此时p已指向a［1］,p->s即为a［1］的s分量，它指向字符串“efgi”的第1个字符e，则++(p->s)指向“efgi”的第2个字符f，故输出为“fgi”。

注意：在循环语句中，a［i］.i中的两个i代表不同的对象，方括号中的i是循环控制变量，代表数组元素的下标，而小数点后面的i则是结构体的分量名。

3.二维结构体数组二维结构体数组和其他类型的二维数组一样，由行和列组成，只不过它的每个元素是一个结构体，每个结构体又有自己的分量，因此，在对二维结构体数组赋初值和进行存取的过程中，必须考虑到行、列及分量等特点。设有定义structcid{charch;inti;doublex;}a［3］［3］；则结构体类型cid有三个分量，二维数组a有3行，每行有3列，共有9个元素，即有9个结构体。它的组织形式如图8-5所示。图8-5二维结构体数组在对二维数组赋初值时，为了清晰起见，应适当地使用括号，以便于把每行、每个元素都清楚地表示出来。例如：structcida［3］［3］={{{′a′,1,1.1},{′b′,2,2.2},{′c′,3,3.3}},{{′d′,4,4.4},{′e′,5,5.5},{′f′,6,6.6}},{{′g′,7,7.7},{′h′,8,8.8},{′i′,9,9.9}},}在赋初值时应注意，每行之间、每列之间及结构体的分量之间都不能留有空洞，或简单地讲，不能连续地出现两个逗号，即在两个逗号之间必须有具体内容。但在每对括号内部，后面的部分可以省略，该处的变量自动具有初值：字符型数据的初值为空字符，数值型数据的初值为零。要引用二维数组中元素的分量，必须在数组名的后面带两个下标，后跟点运算符加分量名。比如要引用上述定义中的字符′f′，则其表示为a［1］［2］.ch，对其中元素2.2的引用是a［0］［1］.x。若数组名只带一个下标，如a［1］，则它表示第2行第1个元素的地址，此时对′f′的引用应表示成(*(a［1］+2)).ch。注意:点运算符的优先级高于间接引用运算符*，所以必须把*(a［1］+2)用括号括起来。

【例8-5】设有I个班，每班有J名学生，每个学生有N个成绩，请输入学生的姓名和4科成绩，并计算每个学生的平均分，所有学生全部成绩的平均分、最高分和最低分。

编程思路：一个学生的信息用一个结构体描述，所有班、所有学生可用二维数组加以组织，因此这是一个二维结构体数组，可用上面叙述的方法加以处理。程序如下：＃include<stdio.h>＃defineI2＃defineJ3＃defineN4structstudent{charname［10］;floatscore［N］;floatave;}a［I］［J］;main(){inti,j,n;floatmax,min,average,sum,sumi;max=average=sum=0;min=100;for(i=0;i<I;i++)for(j=0;j<J;j++){sumi=0;printf(″Inputaname:″);scanf(″%s″,&a［i］［j］.name);printf(″Input%dscores:″,N):for(n=0;n<N;n++){scanf(″%f″,&a［i］［j］.score［n］);if(a［i］［j］.score［n］>max)max=a［i］［j］.score［n］;if(a［i］［j］.score［n］<min)min=a［i］［j］.score［n］;sum+=a［i］［j］.score［n］;sumi+=a［i］［j］.score［n］;}a［i］［j］.ave=sumi/N;}for(i=0;i<I;i++){printf(″＼n＼nclass%d:＼n″,i+1);printf(″Namescore1score2score3score4average\n″);for(j=0;j<J;j++){printf(″%-5s″,(*(a［i］+j)).name);for(n=0;n<N;n++)printf(″%.1f″,(*(a［i］+j)).score［n］);printf(″%.1f＼n″,(*(a［i］+j)).ave);}}average=sum/(I*J*N);printf(″\nmax=%.1f\nmin=%.1f\ntotalaverage=%.1f\n\n″,max,min,average);return0;}运行输出：Inputaname:zhaoInput4scores:88898768Inputaname:qianInput4scores:78899786Inputaname:sunInput4scores:89978659Inputaname:liInput4scores:89979668Inputaname:zhouInput4scores:87766989Inputaname:wuInput4scores:85839691class1:Namescore1score2score3score4averagezhao88.089.087.068.083.0qian78.089.097.086.087.5sun89.097.086.059.082.8class2:Namescore1score2score3score4averageli89.097.096.068.087.5zhou87.076.069.089.080.3wu85.083.096.091.088.8max=97.0min=59.0totalaverage=85.08.1.3结构体变量和结构体指针作参数结构体变量和结构体指针都可以作为函数的参数及函数的返回值。若形参和实参均为结构体变量，则参数传递的是结构体的拷贝，属于函数的传值调用。但这样做既费时间又费空间。如果把形参定义成指针类型，就可以解决这两方面的问题。这时实参传递的是结构体变量的地址，函数中对形参的处理就是对实参的直接处理。下面的例子说明了这种情况。

【例8-6】求两个复数的和与积。

编程思路：复数相加的公式为：(a+bi)+(c+di)=(a+c)+(b+d)i即两个复数相加结果仍为一复数，结果的实部为两个复数的实部之和，结果的虚部为两个复数的虚部之和。复数相乘的公式为：(a+bi)*(c+di)=(ac-bd)+(bc+ad)i复数可以设计成一个结构体类型。复数相加与相乘用两个函数表示。复数结构体类型在各个函数中都要使用，因此把它放到所有函数之外，作为全局类型定义。

＃include<stdio.h>structcomplex{floatre,im;};structcomplex*cadd(structcomplex*,structcomplex*,structcomplex*);structcomplexcmul(structcomplex,structcomplex);main(){structcomplexa,b,c,d,*pa=&a,*pb=&b;*pc=&c;printf(″Inputa.re=?,a.im=?＼n″);scanf(″%f%f″,&a.re,&a.im);printf(″Inputb.re=?,b.im=?＼n″);scanf(″%f%f″,&b.re,&b.im);pc=cadd(pa,&b,&c);d=cmul(a,b);printf(″sumof2complexnumber:＼n″);printf(″c.re=%.1f,c.im=%.1f＼n″,c.re,(*pc).im);printf(″＼n＼nmultipleof2complexnumber:＼n″);printf(″d.re=%.1f,d.im=%.1f＼n″,d.re,d.im);return0;}}structcomplex*cadd(structcomplex*x,structcomplex*y,structcomplex*t){(*t).re=(*x).re+(*y).re;(*t).im=(*x).im+(*y).im;returnt;}structcomplexcmul(structcomplexx,structcomplexy){structcomplexc;c.re=x.re*y.re-x.im*y.im;c.im=x.im*y.re+x.re*y.im;returnc;}运行输出：

Inputa.re=?a.im=?23↙

Inputb.re=?b.im=?34↙sumof2complexnumber:c.re=5.0,c.im=7.0multipleof2complexnumber:d.re=-6.0，d.im=17.0对于cmul函数，两个参数都是结构体类型，实参也是两个结构体变量，返回值也是结构体类型。函数cadd有3个参数，全是结构体指针，实参有结构体指针，也有结构体变量的地址，它们都是等价形式。函数以一个形参t作为返回值，调用时把结构体变量c的地址赋给形参t，则在函数中对t的处理也就是对实参c的处理。函数返回的t也被指向c的指针pc所接收。

讨论：根据cadd函数的处理情况，能否去掉形参t,而把它作为函数体内定义的指针变量呢?这是不允许的，因为作为临时指针变量，在它和具体的结构体建立联系之前，它的指向是随机的，对它指向的内存空间的赋值有可能引起破坏性的后果。但是可以对cadd函数作如下变形：

voidcadd(structcomplex*x,structcomplex*y,structcomplex*t){(*t).re=(*x).re+(*y).re；(*t).im=(*x).im+(*y).im;}即函数中可以不要返回语句，因为对形参t的处理也是对实参的处理，所以这里可以用函数语句的形式对函数cadd进行调用。

cadd(pa,pb,pc)；思考：cadd函数能作如下定义吗?structcomplex*cadd(structcomplex*x,structcomplex*y){structcomplext,*p=&t;t.re=(*x).re+(*y).re;t.im=(*x).im+(*y).im;returnp;}

注意：函数中定义的变量都是内部变量或临时变量，它们只在函数内部起作用，一旦到了函数外部就失去了作用，临时为它开辟的内存也被收回。

【例8-7】日期倒计时。计算今天距北京2008年奥运会开幕还剩多少天。编程思路：日期由年、月、日组成，可用结构体表示。倒计时的计算由三部分组成：当年所余天数+下一年距开幕前一年的天数+开幕当年的天数。

(1)当年所余天数=当月所余天数+下个月至年底的天数。

·当月所余天数=当月总天数-当天号数；

·下月至年底天数=各个月份的天数累加。

(2)下一年距开幕前一年的天数=各年天数累加。累加时闰年为366天，非闰年为365天。

(3)开幕当年的天数=开幕那月前数月的天数+开幕那天的号数。设北京奥运会开幕时间为2008年8月8日，可用宏定义表示具体数值，若改为其他日期，只需修改宏值即可。对当前日期的输入，可以用一个函数实现，函数的参数为一个指向结构体的指针，函数调用时的实参为主调函数中定义的指针，在使用以前它已指向了一个结构体变量。所以函数中对形参指针的操作，也就是对结构体变量的操作。程序如下：＃include<stdio.h>＃include<dos.h>＃defineYEAR2008＃defineMON8＃defineDAY8intdays［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}};structdate{intda_year;intda_mon;intda_day;};main(){inti,l,sum=0;intleap(int);voidgetdate(structdate*);structdatetoday;structdate*p1=&today;getdate(p1);printf(″today:%d.%d.%d＼n″,p1->da_year,p1->da_mon,p1->da_day);for(i=p1->da_year+1;i<=YEAR-1;i++)if(leap(i))sum+=366;elsesum+=365;l=leap(YEAR);for(i=0;i<MON-1;i++)sum+=days［1］［i］;sum+=DAY;sum+=days［l］［p1->da_mon-1］-p1->da_day;for(i=p1->da_mon;i<=11;i++)sum+=days［leap(p1->da_year)］［i］;printf(″＼nToBeijingOlympic,i1rest%ddays!＼n＼n″,sum);return0;}intleap(intm){if(m%4==0&&m%100!=0||m%400==0)return1;elsereturn0;}voidgetdate(structdate*p){printf(″Inputcurrentyear:＼n″);scanf(″%d″,&p->da_year);printf(″Inputcurrentmonth:＼n″);scanf(″%d″,&p->da_mon);printf(″Inputcurrentday:＼n″);scanf(″%d″,&p->da_day);}运行输出：Inputcurrentyear:2006↙

Inputcurrentmonth:7↙Inputcurrentday:20↙today:2006.7.20ToBeijingOlympic,ilrest750days!8.1.4类型名定义typedef在上面的例子中，我们定义了一个复数类型structcomplex,这是个不能分开的整体，利用这个类型名可以定义变量、函数的返回值等。但这个类型名很长，稍不留心就会出错。如果程序中有很多的复数类型的变量和函数需要定义，书写起来更是不胜其烦。能不能简单一些呢?答案是肯定的。C语言提供了一种机制，利用保留字typedef就可以用一个简单的名字来代替像structcomplex这样的长序列。例如：

typedefstructcomplexCOMPLEX;则COMPLEX即是和structcomplex等价的类型名，可以用它定义变量：

COMPLEXa,b,c,*pa；这样用起来就方便多了。用typedef说明类型名的一般形式如下：

typedef〈原类型名〉〈新类型名〉新类型名一般用大写表示，以便与原名在性质上区别开来，即它不是新创造的类型，而是原类型的代名词或化身，它代表了原类型。原类型名可以是构造类型，也可以是标准类型，如：

typedeffloatREAL;就为标准类型float起了个新名REAL。以后在程序中，原名和别名可以同时使用。如有语句

REALf1,f2;就定义了两个浮点型的变量f1和f2。说明新类型的方法十分简单，可按下列步骤进行：

(1)先定义原类型的变量。

(2)把变量名大写，以示它为新类型名。

(3)在前面加上typedef保留字。例如：

structstudentstu;structstudentSTU;typedefstructstudentSTU;于是STU即成为structstudent的新名字，可用来定义变量了，如

STUstud1,stud2;

注意：在用新类型名定义变量时，新类型说明中的附加部分不能写上，如

typedefintARRAY［10］；则新类型名为ARRAY，它代表有10个整型元素的数组，可以用它来这样定义数组：

ARRAYa,b;而不能写成：

ARRAY［10］a,b；说明：用typedef说明新类型名的目的是为了简化书写，便于阅读，这对简化结构体类型名尤为有用，应该学会使用。但不要把简单的问题复杂化，比如要定义有10个整型元素的数组，完全可以写成：

inta［10］,b［10］,c［10］；这样的定义相当直观明了，大可不必先去定义个ARRAY,再用ARRAY来定义有10个元素的数组，那样做既麻烦又违背了简化程序的初衷。用typedef定义的新类型名不一定要大写，小写也可以，大写是为了突出新类型名。8.2动态数据结构到目前为止我们所使用的数据结构如数组等，其大小是一开始就定义好的，在程序中不能改动，这对内存的合理使用及某些操作非常不便。而动态数据结构是一开始并不指定大小，可以随需要不断增加，不用时随时取消的结构，如链表、堆栈、队列、树等，这些动态结构在信息科学中非常有用。8.2.1动态分配内存建立和维护动态数据结构需要进行动态的内存分配，即在程序执行过程中可以动态地得到内存和回收内存。动态分配内存的极限是计算机中可用的物理内存空间。为实现动态分配内存，C语言提供了几个专用的函数和运算符，它们是函数malloc、calloc、free和运算符sizeof。

1.malloc函数该函数原型为：

void*malloc(unsignedsize);功能：在内存中开辟size个字节大小的连续空间。返回值为该空间的起始地址。若分配不成功，则返回0值。

2.calloc函数

calloc函数的原型为：

void*calloc(unsignedn,unsignedsize);功能：在内存中开辟n个大小为size个字节(共n×size字节)的连续空间。返回值为该段空间的起始地址。若分配不成功，则返回0值。这两个函数返回值的类型都是void*，称为空类型或抽象类型的指针。它具有某个内存空间的地址值，一般用作指针类型转换时的过渡形式。如果想让开辟的内存空间中存放某种类型的数据，就把void*强制转换成指向该类型的指针，以满足不同调用环境的需要。如

char*cp；

cp=(char*)malloc(100)；这里用malloc函数开辟出100个字节的空间，用于存放字符，返回值为指向第一个字符的指针。注意：不经过强制转换，则开辟的内存不可用。如定义：char*p;p=malloc(7);则编译时会给出错误提示：cannotconvertfrom′void*′to′char*′，而定义为p=(char*)malloc(7);就正确了。

double*dp=(double*)calloc(10,sizeof(double));则共开辟出10×sizeof(double)个(即10×8=80个)字节的空间，返回的指针指向第1个double单元，如图8-6所示。

注意：NULL和void*是不同的，NULL是空指针，即值为0的指针，它常用作某种标志。比如链表结尾处的结构体的链接指针值为NULL，表示该指针不指向其他结构体。图8-6返回指针的指向

3.free函数

free函数的原型为：

voidfree(void*p)；功能：释放p所指的内存空间，无返回值。以上三个函数的原型在<stdlib.h>头文件中，因此使用它们时应把该头文件包含进来。

【例8-8】编一函数strsave，它可接收一个字符串，然后动态地开辟一个能放得下这个字符串的内存空间，把接收到的字符串复制到其中，并返回该空间的起始地址。＃include<stdio.h>

＃include<stdlib.h>

＃include<string.h>char*strsave(char*);main(){char*str=″China″,*cp;cp=strsave(srt);printf(″str=%s,cp=%s＼n″,str,cp);return0;}charstrsave*(char*s){char*p;if((p=(char*)calloc(strlen(s)+1,1))!=NULL)strcpy(p,s);returnp;}运行输出：

str=China，cp=China标准函数calloc分配strlen(s)+1个大小为1的内存空间。因为strlen函数统计字符串长度时不包含′＼0′字符，但在复制字符串中还需要把′＼0′加进去，所以分配空间时要加1。原calloc函数返回的是空类型指针，现在把它强制转换成char型指针，再把该指针值赋给p，然后判断p是否为NULL(0)，若不为NULL，就调用字符串拷贝函数来完成拷贝工作。函数中开辟的内存空间不会随函数调用的结束而取消，因此p指针返回来的值是有意义的。相反，如果不开辟内存空间，则p无所指向，不可使用。

4.sizeof运算符

sizeof运算符在本书第3章的3.3.6节中已有介绍，这里不再赘述。

【例8-9】学生的信息包括姓名、所在系名及三科成绩。请输入多个系的学生的信息，打印输出指定系的学生的最高分和平均成绩。＃include<stdio.h>＃include<string.h>＃include<stdlib.h>typedefstruct{charname［20］;char*dep;intscore［3］;}STUTP;voidstuscore(STUTP*s,char*depart,int*max,float*ave,intm){intn,i;floatsum=0;n=0;while(m!=0){if(strcmp(s->dep,depart)==0){for(i=0;i<3;i++){ sum+=(*s).score［i］; if((*s).score［i］>*max) *max=(*s).score［i］;}n++;}s++;m--;}*ave=sum/(3*n);printf(″In＼′%s＼′department,thereis%dstudents.＼n″,depart,n);}voidmain(){STUTPx［50］;inti=0,max,j;floatave;chardep［20］,depbuf［20］;while(1){puts(″Inputname:″);//scanf(″%s″,x［i］.name);getchar();gets(x［i］.name);if(strcmp(x［i］.name,″***″)==0){printf(″Inputend!＼n″);break;}puts(″Inputdepartment:″);x［i］.dep=(char*)malloc(strlen(depbuf)+1);gets(x［i］.dep);printf(″Input3scoresinteger:＼n″);for(j=0;j<3;j++)scanf(″%d″,&x［i］.score［j］);getchar();i++;}printf(″Youinput%dstudent!＼n″,i);puts(″Inputdepartnametoconsider:″);gets(dep);max=0;ave=0.0;stuscore(x,dep,&max,&ave,i);printf(″max=%d,ave=%.1f＼n″,max,ave);}程序说明：①程序中求最高分及平均分的工作由一个函数完成，函数的形参为指针，实参为主程序中定义的变量的地址，用这种方式可以从函数调用中获取多个数值。②结构体类型中的系名分量是指向字符的指针，不是字符数组，因此不能直接向它拷贝字符串。因为指针尚未指向具体的内存空间，这就需要首先调用动态分配内存的函数malloc分配内存，并将此内存空间的起始地址赋给该指针分量，然后再用它进行字符串输入。③main函数中while循环的条件永远是真，它的循环控制是由输入的姓名字符串决定的，如果输入的姓名是三个*号，则循环终止。④程序中使用typedef定义了一个类型名STUPT，这样可以使程序简洁。⑤在用scanf函数输入姓名和分数之后，接着调用一个getchar函数，目的是为了接收前面输入操作中的回车符，为的是不影响下面的输入。如果不用getchar吃掉前面留下来的回车符，则下面的输入语句就会将此回车符作为输入的内容而出现错误。但是，如果用gets函数输入字符串，则不需要再用getchar去消除输入字符串时回车符的影响，因为gets会自动地将回车符变为字符串结束标志附加到输入字符串的末尾。运行输出：Inputname:aaaInputdepartment:xxxInput3scoresinteger:809070Inputname:bbbInputdepartment:xxxInput3scoresinteger:4510055Inputname:cccInputdepartment:jsjxInput3scoresinteger:889977Inputname:dddInputdepartment:xxxInput3scoresinteger:12080100Inputname:***Inputend!Youinput4student!Inputdepartnametoconsider:xxxIn′xxx′department,thereis3students.max=120,ave=82.28.2.2链表链表是用链表指针连在一起的自引用结构(称为“结点”)的线性集合，如图8-7所示。其中，head是指向链表第一个结点的指针，通过它来访问链表。后面的结点是通过它前面结点中的链接指针来访问的。链表的最后一个结点中的链接指针被置为NULL(画成反斜杠以表示链尾)。链表中的结点是在需要时建立的，链表中的数据是动态存储的。图8-7链表的结构我们可以把动态的链表和静态的数组作一对比，以说明它们的特点。

(1)在数据元素的个数不可预知时，使用链表是合适的，因为可在需要时增加或减少链表中结点的个数；数组是在编译时分配内存的，其大小是不可改变的。

(2)当数组定义得很大以备不时之需时会造成空间的浪费；链表随用随增，不会造成空间的浪费。

(3)对于插入和删除操作，使用数组费时费力，而使用链表却可以方便地在合适的位置插入和删除结点，只要把有关结点的链接指针修改一下即可。

(4)数组中的元素在内存中是连续存放的，根据相对于数组的起始位置可以计算出数组元素的地址，所以可以立即访问到任意位置的数组元素；链表中的结点不能被立即访问到，因为链表中的结点在逻辑上是连续的，但在内存中是不连续的。虽然从总体上说，动态分配内存能节省空间，但每个结点中的指针也要占用存储空间，并且动态分配内存也需要一些函数调用的开销。下面我们研究链表的建立、插入、删除及输出等操作。

1.建立链表首先定义链表中结点的类型，它应该是一个自引用的结构体。如

structnode{intdata;structnode*next;};typedefstructnodeNode;Node为新类型名。所定义的结构体中有两个分量，形成两个域：数值域和指针域。对链表进行操作，需要三个指针：指向链表头的指针head，指向当前结点的指针p1,指向当前结点前一结点的指针p2。先建立只有一个结点的链表，使head、p1、p2都指向它，如图8-8所示。其操作步骤如下：

(1)产生一个结点，用p1指向它：

p1=(Node*)malloc(sizeof(Node));

(2)把p1赋给head和p2:p2=head=p1。

(3)对新结点的数据域输入数据，而把其指针域置为NULL。图8-8链表的建立下面建立只有两个结点的链表，即把第二个结点连到第一个结点之后作为链表尾，如图8-9所示。要达到这样的格局，需要进行如图8-9所示的五步操作：①用p1指向新产生的结点：

p1=(Node*)malloc(sizeof(Node));②把新结点的指针域置空：

p1->next=NULL；③输入新结点的数值域：

scanf(″%d″,&p->data)；④把新结点连到链表尾部：

p2->next=p1;图8-9建立两个结点的链表⑤让p2也指向新结点：

p2=p1；以后再加入新结点时，操作与此类似，但没有必要每产生一个新结点都将其指针域置为NULL，而完全可以在最后一个结点中实行。可以把输入数值0作为链表建立的结束。数值域为0的结点不在链表内。于是可写出如下函数：

Node*create(){Node*h=NULL,*p1,*p2;printf(″Inputintegertocreatealist,0toend:＼n″);p1=(Node*)malloc(sizeof(Node));scanf(″%d″,&p1->data);if(p1->data!=0)h=p1;

while(p1->data!=0){p2=p1;p1=(Node*)malloc(sizeof(Node));scanf(″%d″,&p1->data);p2->next=p1;}p2->next=NULL;returnh;}循环体内的操作是在当前结点的数值域不为0时才让p2指向它。如当前结点的数值域为0，则不让p2指向它，那么p2所指的结点就是最后一个结点，因此把它的next域置为NULL。虽然在循环体中进行过p2->next=p1的操作，但在循环体之后通过p2->next=NULL又把数值部分为0的那个结点从表中摘除了。这个函数的参数为空，返回值为指向结构体的指针。

2.输出链表当链表的头指针为NULL时说明链表是空的，不采取行动。只有当链表非空时才从链表头部开始，输出一个结点的值，然后移动指针，再输出下一个结点的值……直至表尾结束。可用下面的函数完成此项功能：voidprintList(Node*h){Node*p;p=h;if(h==NULL)printf(″Listisempty!＼n＼n″);else{while(p!=NULL){printf(″%d->″,p->data);p=p->next;}printf(″Null＼n＼n″);}}在函数体内定义了一个工作指针p，起流动哨的作用，在输出它所指结点的数值域之后，它就再向后移一位以指向下一个结点。这是由指针传递操作p=p->next来完成的。这个函数以结构体指针作参数，不返回值。

3.插入结点在一个链表中插入结点，首先要确定插入的位置，这里要考虑几种情况：

(1)空表情况。

(2)插在表头。

(3)插在表中。

(4)插在表尾。完成该功能的函数中使用了三个工作指针：newp，指向要被插入的结点；p1，指向当前结点；p2，指向当前结点的前一结点。这里设该链表已经排序且按升序插入结点，则从链表的头部开始，只要指向当前结点的指针p1不空且要插入的结点的数值又比当前结点的数值大，就继续向后查找合适的位置，向后移动的方法是修改p1和p2的值。该函数如下：Node*insert(Node*h,intvalue){Node*newp,*p1,*p2;newp=(Node*)malloc(sizeof(Node));if(newp!=NULL){newp->data=value;newp->next=NULL;p2=Null;p1=h;while(p1!=Null&&value>p1->data){p2=p1； /*移到…*/p1=p1→next; /*下一结点*/}if(p2==NULL) /*插在表头*/{newp->next=h;h=newp;}else{p2->next=newp;newp->next=p1;}}elseprintf(″%dnotinserted,Nomemoryavailable＼n″,value);returnh;}该函数返回一个指向结构体的指针，其参数为一个链表的头指针和要插入的数值，最后返回的仍然是链表的头指针，但链表在函数调用的过程中发生了变化。我们以图示来说明插入结点的操作。

(1)结点插在表头。设原头结点数值为8，把数值为6的结点插入其前，如图8-10所示。图8-10结点插在表头

(2)结点插在表中间。在上面链表的基础上插入数值为9的结点，如图8-11所示。

(3)结点插在表尾。在上面链表的基础上在表尾插入数值为16的结点，如图8-12所示。插在表尾，意味着在while循环中以p1=NULL为条件而退出循环。图8-11结点插在表中间图8-12结点插在表尾

4.删除结点从一个链表中删除结点也应考虑以下几种情况：

(1)删除表头结点。

(2)删除表中或表尾结点。

(3)找不到要删的结点。完成该功能的函数中使用了三个工作指针：p1，指向当前考查结点；p2，指向当前结点的前一结点；temp，指向被删结点。函数如下：

Node*delete(Node*h,intvalue){Node*p1,*p2,*temp;if(value==h->data) /*删除表头结点*/{temp=h;h=h->next; /*解除表头与链表的连接*/free(temp); /*释放该结点的内存*/}else{p2=h;p1=h->next;while(p1!=NULL&&p1->data!=value){p2=p1; /*移到…*/p1=p1->next; /*…下一个结点*/}if(p1!=NULL) /*即p1->data==value*/{temp=p1;p2->next=p1->next;free(temp);