《C语言程序设计》课件2第9章

第9章构造数据类型9.1结构体类型9.2共同体类型9.3位段结构类型9.4枚举类型9.5自定义类型9.6程序举例习题9

本章学习要求：

1.了解位段结构类型，了解自定义类型的定义方法，理解结构体、共同体类型的定义，掌握结构体变量的定义与使用。

2.掌握结构体数组的定义与使用，掌握结构体指针的定义与使用，掌握单链表的定义、单链表的建立及结点的插入、删除运算。

3.掌握枚举类型变量的定义与使用。

迄今为止，我们已经介绍了C语言中的基本数据类型(整型、实型、字符型)及派生类型(数组和指针)。但实际处理问题时，只有这些数据类型是不够的，故C语言给用户提供了自己声明数据类型的权利，这些类型称为构造类型。本章将介绍四种构造类型：结构体类型、共同体类型、枚举类型及自定义类型。

有时候我们需要将各种不同数据类型的变量、数组等组合成一个整体，使之相互之间具有一定的联系。比如每位学生个体都具有学号、姓名、年龄、成绩等属性，而一个班级的学生在学号上又具有一定联系。要想把这种数据结构描述出来，利用目前所学的知识是无法达到的，而本章介绍的结构体数据类型就可以解决这个问题。9.1结 构 体 类 型9.1.1结构体变量

大家非常清楚，定义一个变量必须指出确定的类型，这样系统才能为其分配确定大小的存储空间。而结构体类型是由用户自己声明的，所以定义结构体变量之前就必须声明结构体类型，或者可以在声明结构体类型的同时定义结构体变量。

1.结构体类型的声明

结构体类型声明的一般形式如下：

struct结构体名

{成员列表

};其中：

(1)“struct”是C语言的关键字，是结构体类型的标志。

(2)“结构体名”称为结构标记，即代表花括号内的声明，可以用它作为该声明的简写形式，书写要符合C语言标识符命名规则。

(3)“成员列表”可以是若干个不同类型的变量、数组。

(4)结构体类型的大小是其所有成员所占空间字节数相加之和。

(5)花括号外的分号必不可少。例如：

structdate

{intyear,month,day;};

也可以写成

structdate

{intyear;

intmonth;

intday;

};以上结构体类型的全称是structdate，我们用它来描述某一天的日期；它有三个成员项year、month、day，分别代表年、月、日；类型大小是三个整型变量的存储字节数相加之和：6B(字节)。

(6)

结构体类型的声明还允许嵌套，例如：

structstudent

{intnum;

charname[20];

structdatebirthday;

};

结构体structstudent可以用来描述某个学生的相关信息，其中第三个成员birthday本身也是一个结构体类型，称为嵌套。我们还可以把structdate的声明嵌套进来，形成如下形式：

structstudent

{intnum;

charname[20];

structdate

{intyear,month,day;

}birthday;

};注意，struct声明定义了一种数据类型，只是列出了该数据结构的各成员组成情况，即给出了一个数据结构的“模版”，系统并没有为其分配存储空间，只有用这种类型定义变量或数组时系统才会为变量或数组分配存储空间。对于这一点，大家可以这样理解，“structdate”、“structstudent”与int、float在语法上具有类似的意义，只不过int、float的类型声明是由系统完成的，对于int、float本身系统并不会为其分配空间。

2.结构体变量的定义

在C语言中，定义结构体变量存在三种方式。

1)在声明结构体类型之后定义结构体变量

此方式的定义形式如下：

struct结构体名结构体变量名；

若结构体类型的声明按照前文，则结构体变量的定义如下：

structdatesunday;

structstudentstu1;

这种定义变量的形式与前面我们学习过的定义变量的方式相同，并不陌生，因此不作过多阐述。但下面两种定义变量的形式却是以前没有过的。

2)在声明结构体类型的同时定义结构体变量

此方式的定义形式如下：

struct结构体名

{成员列表

}变量列表；

例如：

structdate

{intyear,month,day;

}sunday;

或

structstudent

{intnum;

charname[20];

structdatebirthday;

}stu1;

3)在声明一个无名结构体类型的同时定义结构体变量

此方式的定义形式如下：

struct

{成员列表

}变量列表；

例如：

struct

{intyear,month,day;

}sunday;

或

struct

{intnum;

charname[20];

structdatebirthday;

}stu1;

这种定义方式的主要特点是声明的结构体没有名称，但是关键字struct必不可少。另外说明一点，因为此结构体没有名称，所以不能利用这种结构体像第一种方式那样去定义变量。独立声明结构体类型的时候是不允许有这种方式的，否则将毫无意义。针对三种定义方式的说明：

(1)变量birthday所占存储空间为6个字节，变量stu1所占存储空间为2+20+6=28个字节，其结构如图9.1所示。

(2)不论哪一种定义方式，都可以同时定义若干个变量，变量名之间用逗号隔开。

图9.1结构体变量存储空间示意图

3.结构体变量的初始化

以上三种方式在定义结构体变量的同时都可以进行初始化。下面就以第一种定义结构体变量的方式为例来说明初始化问题。

初始化方法就是将所赋初值按顺序放在一对花括号内，例如：

structdatesunday={2005,6,5};

structstudentstu1={501,"ZhaoLin",1979,10,24};

其存储结构如图9.2所示。

图9.2结构体变量存储结构示意图从图中可以看出，系统是按照从左到右的顺序逐一将数值赋予每个成员的，嵌套结构体变量也是如此。

注意：

(1)不允许对结构体变量独立进行整体赋值操作，如下形式是不合法的：

sunday={2005,6,5};

(2)所赋初值与各成员数据类型要匹配或兼容。

4.结构体变量的使用

老版本的C语言中不允许对结构体变量进行整体操作(一种情况例外，见说明第(3)点)，只能使用结构体变量的各成员项，因此所有的引用操作都必须具体到单个成员项。

1)结构体变量成员的引用

结构体变量成员的引用形式如下：

结构体变量名.成员名

其中，实心点“.”称为成员运算符。例如：

sunday.yearsunday.daystu1.num说明：

(1)成员运算符在C语言中优先级最高，与圆括号、下标运算符同级。

(2)引用内嵌结构体变量的成员时，要逐层使用成员运算符，例如：

stu1.birthday.monthstu1.birthday.day

(3)允许相同类型的结构体变量之间进行赋值运算，如下语句是合法的：

structdated1;

d1=sunday;

以上实现了将结构体变量sunday中各成员的值赋予变量d1种相应的成员项。

(4)新的ANSI

C标准允许对结构体变量整体进行各种操作。

2)结构体成员的操作

通过以上方法引用到了不可分割的成员项，这时每个成员项都属于确定的我们熟悉的数据类型，因此在使用结构体成员项时完全可以把它们当作普通的变量或数组来看待。例如，sunday.year可以看成普通整型变量来操作，可以看成字符数组来操作，stu1.birthday.day同样可以看成普通整型变量来操作。

(1)结构体成员的输入/输出如下：

scanf(“%d,%d,%s”,&sunday.year,&stu1.birthday.day,);

printf(“%d,%d,%s”,sunday.year,stu1.birthday.day,);

(2)结构体成员的赋值操作如下：

sunday.year=1982；

stu1.birthday.day=11；

类型相同或兼容的结构体成员之间可以相互赋值，例如：

sunday.month=stu1.birthday.day;

实际应用中要注意数值的合法范围，如用sunday.month代表月份，那它的取值范围就是1～12。

(3)结构体成员的一般运算如下：

相同类型的普通变量能够进行的运算，结构体成员也可以进行，例如：

sunday.year++；

sunday.month=stu1.birthday.day-2；

同样可以进行关系、逻辑等运算，例如：

(sunday.month>=1)&&(sunday.month<=12)

!(sunday.year)

3)结构体变量作函数参数

(1)结构体变量的成员作函数参数。结构体变量中的每个成员可以是普通变量、指针变量、数组等，它们既然可以参与上文所述的若干运算，当然也可以作为函数参数来传递。若实参是结构体变量成员，则形参可以是与成员子类型相同或兼容的普通变量。例如：

struct

{intyear,month,day;

}sunday;

intage(intx) /*定义子函数，整型变量作形参*/

{……}

main()

{…

age(sunday.year);

/*调用子函数，结构体变量成员作实参*/

…

}

(2)结构体变量作函数参数。结构体变量作函数参数传递的是所有成员的数据，因此实参与形参必须是相同类型的结构体变量。例如：

structdate

{intyear,month,day;

};

intage(structdatemy) /*定义子函数，结构体变量作形参*/

{……}

main()

{structdatefy;

…

age(fy); /*调用子函数，结构体变量作实参*/

…

}

则函数调用时实参结构体变量fy将其三个成员项的值传给了形参结构体变量my相应的三个成员项。

例9.1

编写程序，求解某一点在平面坐标中关于原点的对称点。

平面坐标系中一般用(x,y)来表示一个点，且x和y是有关联的，是一个整体。因此我们可以用具有两个成员项的结构体来表示这种结构，这里假设x、y的坐标值均为整数。而点(x,y)关于原点的对称点应该是(-x,-y)，程序如下：

#include<stdio.h>

structpoint

{intx;

inty;

};

main()

{inta,b;

structpointpi;

printf("Pleaseentertwonumbers:\n");

scanf("%d,%d",&pi.x,&pi.y);

a=-pi.x;

b=-pi.y;

printf("symmetricalpoint:%d,%d\n",a,b);

}

若利用函数实现，则程序如下：

#include<stdio.h>

structpoint

{intx;

inty;

};

voidspoint(inta,intb)

{a=-a;

b=-b;

printf("symmetricalpoint:%d,%d\n",a,b);

}

main()

{structpointpi;

printf("Pleaseentertwonumbers:\n");

scanf("%d,%d",&pi.x,&pi.y);

spoint(pi.x,pi.y);

}9.1.2结构体数组

一个结构体变量只能表示一个实体的信息，例如一个“structstudent”类型的结构体变量只能表示一个学生的信息，如果想把存在关联的一组学生信息存放在一起则需要使用结构体数组。

1.结构体数组的定义和初始化

通过第6章的学习，我们能够推出，结构体数组的含义就是它的每个元素都是结构体类型的，这也是它与一般数值型数组的唯一不同之处。

1)结构体数组的定义

结构体数组的定义方法与结构体变量的定义方法类似，存在三种形式，此处就不再一一详细讲解。下面给出第一种定义形式：

struct结构体名结构体数组名[整型表达式]；

例如：

structdatedt[4];

structstudentst[30];

2)结构体数组的初始化

结构体数组的初始化同第6章中其他类型数组的初始化类似。但由于结构体数组的每个元素都是包含若干成员的结构体，因此结构体数组初始化时，通常在每个元素的两边加一对花括号，以便区分清楚数组的各个元素，每对花括号之间用逗号隔开。例如：

structdatedt[4]={{1982,7,3},{1980,12,5},{1981,9,15},{1980,3,11}};

可以看到，数组dt有四个元素：dt[0]、dt[1]、dt[2]，dt[3]，每个元素都有三个成员项，每个元素都占6个字节，因此整个数组共占存储空间24个字节。又例如：

structworker

{intnum;

charname[20];

floatsalary;

}warr[3]={{9901,"Zhaolin",82.5},{9902,"Lifei",75},{9903,"Chenjun",91.5}};

可以看到，数组warr有三个元素：warr[0]、warr[1]、warr[2]，每个元素都有三个成员项，每个元素都占26个字节，因此系统共分配了78个字节的连续存储空间给数组warr。说明：

(1)当初始化元素个数与定义的数组长度相等时，可以省略数组长度。例如：

structdatedt[]={{1982,7,3},{1980,12,5},{1981,9,15},{1980,3,11}}；

(2)元素、元素内成员项均可以进行部分初始化，系统按照从左到右的顺序赋值。

例如：

structdatedt[4]={{1982},{1980,12,5},{1981,9,15}}；

该语句没有给元素dt[3]赋初值，它的三个成员项的值均为0，而给第一个元素dt[0]也只提供了一个数据，则后两个成员项的值也为0。

(3)除了初始化时可以对结构体数组整体赋初值，其他任何情况下都不能对结构体数组进行整体赋值，如下语句均是错误的：

warr[3]={{9901,"Zhaolin",82.5},{9902,"Lifei",75},{9903,"Chenjun",91.5}};

或

warr={{9901,"Zhaolin",82.5},{9902,"Lifei",75},{9903,"Chenjun",91.5}};

2.结构体数组的使用

在讲述结构体变量时，我们说过操作时要具体到单个成员项，对结构体数组的使用也同样要遵循这个原则(例外情况见说明)。

1)结构体数组的引用

结构体数组的引用形式如下：

结构体数组名[数组下标].成员名

若有定义语句structdatedt[4];和structwokerwarr[10];，则以下引用形式均是合法的：

dt[0].year,dt[0].month,dt[0].day,dt[3].day

warr[1].num,warr[2].name,warr[3].name,warr[8].salary

说明：相同结构体类型的数组元素之间可以相互赋值，例如：

dt[0]=dt[1];

warr[7]=warr[1];

这是结构体数组元素之间可以进行整体操作的唯一一种运算。

2)结构体数组的操作

同以前学过的数组操作类似，因为数组下标是有规律变化的，所以结构体数组的操作也通常是利用循环对各个元素逐一进行控制。但与其他类型数组的不同之处就是，每个元素还要细化到成员项。当细化到成员项之后就相当于使用相同类型的普通变量或数组，此处仅以输入和输出作为示例。

结构体数组的输入和输出：

(1)

for(i=0;i<4;i++)

scanf("%d,%d,%d",&dt[i].year,&dt[i].month,&dt[i].day);

for(i=0;i<4;i++)

printf("%d,%d,%d\n",dt[i].year,dt[i].month,dt[i].day);

(2)

for(i=0;i<10;i++)

scanf("%d,%s,%f",&warr[i].num,warr[i].name,&warr[i].salary);

for(i=0;i<10;i++)

printf("%d,%s,%f",warr[i].num,warr[i].name,warr[i].salary);

scanf()语句中，因为warr[i].name是数组，数组名代表数组起始地址，因此不应再加取地址"&"运算符。

3)结构体数组作函数参数

结构体数组作函数参数传递的是地址，若实参是结构体数组，则形参可以是结构体数组也可以是结构体指针，这部分内容在下一节中再详细讲解。

例9.2

假设描述个体的结构体如下，则编写程序求分数最高者。要求从键盘输入数据，然后输出得分最高者的相关信息。

#include<stdio.h>

structperson

{longsn;

charname[20];

floatscore;

}pe[50];

main()

{inti,j;

floatmax;

printf("Pleaseentername,snandscore:\n");

for(i=0;i<50;i++)

{gets(pe[i].name);

scanf("%ld,%f",&pe[i].sn,&pe[i].score);

}

max=pe[0].score;j=0;

for(i=1;i<50;i++)

if(pe[i].score>max)

{max=pe[i].score;

j=i;

}

printf("Theresultis:\n");

printf("%d,%f,%s",pe[j].sn,pe[j].score,pe[j].name);

}程序说明：

(1)用scanf()函数输入字符串遇空格即结束，不能满足实际要求，所以我们采用gets()函数输入字符串，它只遇换行符结束。

(2)此例题并不仅仅是统计分数最高者，还要求最后输出其相关信息，因此必须记录其位置才能解决问题，引入变量j即是为了记录具有最高分数元素的下标。9.1.3*结构体指针

通过第7章的学习，我们知道指针即是地址，而结构体的指针即是结构体的地址，包括结构体变量的指针和结构体数组的指针。

1.结构体指针变量的定义

与定义结构体变量、数组的方法类似，结构体指针变量的定义也有三种形式。

1)在声明结构体类型之后定义结构体指针变量

此方式的定义形式如下：

struct结构体名*指针变量名；

例如：

structdate*psd;

structworker*pwk;

这种定义与第7章中我们学习的定义指针变量的方式类似，注意变量名前的“*”号，它起标识的作用，但不包括在变量名之内。

2)在声明结构体类型的同时定义结构体指针变量

此方式的定义形式如下：

struct结构体名

{成员列表

}*指针变量名；

例如：

structdate

{intyear,month,day;

}*psd;

或

structworker

{intnum;

charname[20];

floatsalary;

}*pwk;

3)在声明一个无名结构体类型的同时定义结构体变量

此方式的定义形式如下：

struct

{成员列表

}*指针变量名；

例如：

struct

{intyear,month,day;

}*psd;

或

struct

{intnum;

charname[20];

floatsalary;

}*pwk;

以上定义的结构体指针psd、pwk均可以指向结构体类型相同的结构体变量或结构体数组。

2.指向结构体变量的指针

若有以下语句：

structworker

{intnum;

charname[20];

floatsalary;

}wk,*pwk;

pwk=&wk;

则这时指针pwk是指向变量wk的，即通过pwk可以实现操作wk的目的。我们知道，引用指针所指向的变量的方法是利用指针运算符“*”号，但在结构体中还必须具体到单个成员项，用到成员运算符“.”号。因此通过指针引用结构体变量中的成员有如下两种方式：

(*指针变量名).成员名

指针变量名->成员名

其中出现了新的运算符“->”，称为指向运算符，它由减号“-”和大于号“>”两部分组成，中间不得有空格，它的优先级同圆括号、成员运算符一样也是最高级。

另外，第一种方式中的圆括号必不可省，否则会产生错误，因为成员运算符的优先级高于指针运算符。

例如，利用指针对结构体变量输入和输出：

gets((*pwk).name)；

scanf("%d%f",&(*pwk).num,&(*pwk).salary);

printf("%d,%f,%s",pwk->num,pwk->salary,pwk->name);

因为指向运算符“->”方便、直观，所以使用较多

3.指向结构体数组的指针

若有以下语句：

structworker

{intnum;

charname[20];

floatsalary;

}warr[20],*pwa;

pwa=warr;/*或，pwa=&warr[0];*/则这时指针pwa指向数组warr的起始位置，即通过pwa可以实现操作数组warr元素的目的。利用指针运算符“*”号可以引用数组元素，但每个结构体数组元素还包含若干成员，因此也必须具体到单个成员项。而每个结构体数组元素就相当于同类型的变量，所以通过指针引用结构体数组元素中的成员也存在如下两种方式：

(*指针变量名).成员名

指针变量名->成员名

例如，(*pwa).num和pwa->num，即是warr[0].num。

通过前面第7章的学习，我们知道可以使用指针通过循环来引用数组的每个元素，在结构体数组中也同样可以。例如：

for(pwa=warr;pwa<warr+20;pwa++)

{gets(pwa->name)；

scanf("%d%f",&pwa->num,&pwa->salary)；

}

for(pwa=warr;pwa<warr+20;pwa++)

printf("%d,%f,%s",pwa->num,pwa->salary,pwa->name);说明：

(1)对指针进行“++”运算是使指针指向下一个数组元素，而绝不是指向下一个存储单元。例如，“pwa++”表示指针移动了26个存储单元而指向下一结构体数组元素。

(2)编译系统不会做越界检查，所以要注意终止条件。

(3)表达式++pwa->num等价于++(pwa->num)，所以是使得num加1，因为指向运算符的优先级高于自加运算；若想使pwa加1，应写成(++pwa)->num，则pwa先自加指向下一数组元素，然后再取num成员；另外，(pwa++)->num与pwa++->num等价，在访问pwa所指的num成员之后再自加指向下一元素。

4.结构体指针作函数参数

1)结构体变量指针作函数参数

若结构体变量指针作函数形参，则实参可以是结构体变量指针，也可以是结构体变量地址。

例9.3编写函数，利用指针给结构体变量输入数据。

#include<stdio.h>

structworker

{intnum;

charname[20];

floatsalary;

};

voidgetdata(structworker*pwk)

{printf("Pleaseentername,snandscore:\n");

gets(pwk->name)；

scanf("%d%f",&pwk->num,&pwk->salary)；

}

main()

{structworkerwk;

getdata(&wk); /*结构体变量地址作函数实参*/

printf("%d,%f,%s",wk.num,wk.salary,);

}若采用结构体指针作函数实参，则主函数修改如下：

main()

{structworkerwk，*p;

p=&wk;

getdata(p); /*结构体变量指针作函数实参*/

printf("%d,%f,%s",p->num,p->salary,p->name);

}

注意，这种情况下定义一个结构体变量是必须的，否则指针的内容是空的，它无法作为实参来使用。

2)结构体数组指针作函数参数

若结构体数组指针作函数参数，则实参与形参应该都是地址。又因为数组名本身就代表数组的起始地址，所以实参与形参可以出现的组合有四种，如表9.1所示。

表9.1结构体数组作函数时的形参与实参的四种组合下面我们以第三种情况为例进行说明。

例9.4

编写函数，利用指针给结构体数组输入数据。

#include<stdio.h>

structworker

{intnum;

charname[20];

floatsalary;

};

voidgetdata(structworker*pak)

{structworker*p;

for(p=pak;p<pak+20;p++)

{gets(p->name)；

scanf("%d%f",&p->num,&p->salary)；

}

}

main()

{structworkerwarr[20],*q=warr;

getdata(warr);/*还可以是，getdata(q)*/

for(;q<warr+20;q++)

printf("%d,%f,%s",q->num,q->salary,q->name);

}9.1.4*单链表

1.单链表的概念及结构

到目前为止，大家知道要存储一组有关联的数据需利用数组，比如一个班的学生、一个教研室的老师、一个车间的工人等等。通过第8章函数的学习可知，对于常用算法，我们通常把它做成一个模块(函数)以便反复调用，而每次调用时数据的个数及大小通常都会发生变化，如果采用数组来存储数据，则定义时我们必须按照最大可能的情况来确定数组长度，所以很多空间就会浪费。另外，数组中的插入、删除等操作也非常麻烦，通常需要移动较多元素。

而链表就可以解决以上两个问题，它的结构图如图9.3和图9.4所示。

图9.3单链表示意图

图9.4空链表示意图由图9.3可以看出，链表由一个头指针及若干结点组成。每个结点由数据域和指针域两部分组成，数据域存放描述个体的相关信息，指针域存放的是下一个结点的地址。头指针指向链表的第一个结点，链表可以没有头结点(见图9.4(b))，头结点中不存放数据。尾结点是最后一个结点，它不指向任何地方，所以指针域的地址是空值，在C语言中用'\0'(NULL)表示。结点的空间是在程序执行过程中根据需要随时向系统申请开辟的存储单元，不需要时又能随时释放结点、释放存储空间，如此按需分配则不存在空间浪费的问题。各个结点在内存中的位置也不是连续的，对空间的要求也相应降低，它们之间是通过指针建立起来的前后次序关系，因此插入、删除等操作只要改变个别指针的指向即可，无需移动任何结点。由于这种链表中每个结点都没有名称，只能从头指针开始由前往后逐个查找访问，即只存在一种访问链表的次序(或方向)，因此称为“单向链表”，也称“单链表”。

既然一个结点实体至少需要两个部分：数据域和指针域，因此描述它的类型应该是结构体类型，又因为这种指针指向的仍是相同类型的结点，所以指针的基类型应是自身结构体类型。链表结构体类型声明如下：

structlink

{intdata;

structlink*next; /*引用自身的结构体指针变量*/

};

2.静态链表

在以上介绍的单链表中我们说过，结点的申请和释放都是在程序执行过程中动态进行的，所以又称为动态链表。其实，还存在一些简单的链表，它具有链表的结构特征，但它的结点是定义好的静态结构体变量，结点的个数在程序执行前也都是确定的，总之链表是通过固定语句“手工”搭建起来的，因此称为静态链表。例9.5

建立静态链表。

#include<stdio.h>

structslink

{intdata;

structslink*next;

};

main()

{structslinkx,y,z,*head,*q;

x.data=10;y.data=11;z.data=12; /*给数据域赋值*/

head=&x;

x.next=&y;

y.next=&z;

z.next=’\0’;

}

如此建立的链表结构如图9.5所示。

图9.5静态链表结构

3.动态单链表

本节重点学习动态单链表，以下简称单链表。学习内容包括单链表的建立、访问、插入、删除等基本操作。

1)处理动态链表所需的函数

(1)

malloc()函数。

函数原型如下：

void*malloc(unsignedintsize);

函数功能：在内存的动态存储区中分配一个长度为size的连续空间。

函数值：如果成功，返回的是分配存储区的起始地址；如果不成功，返回的是空地址(NULL)。因此我们通常把函数值赋予一个指针变量。说明：

①由于链表结构体类型中存在指针变量成员，其类型大小很难确定，因此我们通常是采用系统提供的运算符sizeof()来求解链表结构体类型长度。例如：

sizeof(structlink)

②函数返回值的基类型是void，而实际应用中均会有确定类型，因此需利用强制类型转换运算符“()”进行类型转换。例如：

structlink

{intdata;

structlink*next;

}*q;

q=(structlink*)malloc(sizeof(structlink));

以上语句的功能就是向系统申请了一块structlink类型大小的区域，并将起始地址赋予了指针变量q，其实在单链表中这块区域就是一个结点，称为结点q。

(2)

free()函数。

函数原型如下：

voidfree(void*p);

函数功能：释放由指针变量p所指向的内存区域，将区域使用权交还给系统。

说明：

①此函数无返回值。

②

p必须是调用malloc函数返回的值，不能妄图用此函数释放所有指针指向的地址。

2)单链表的建立

建立动态链表的过程就是，在程序执行过程中一个一个地开辟空间，生成新结点，然后再将结点一个个连接起来。大致步骤如下：

(1)读取数据，判断是否有效，若是有效数据则执行步骤(2)，若无效则不再读取数据。

(2)申请新结点。

(3)将数据存入结点的成员变量中。

(4)将新结点插入到链表末尾。

(5)重复步骤(1)～(4)。

例9.6

编一函数，建立带头结点的单链表，要求数据从键盘输入直至遇-1结束。

说明：本程序中，h是头指针，指向头结点；new用来指向新生成的结点；而rear则始终指向当前链表的尾结点。

#include<stdio.h>

#defineLENsizeof(structlink)

structlink

{intdata;

structlink*next;

};

structlink*creat_link()

{inta;

structlink*h,*new,*rear;

h=(structlink*)malloc(LEN); /*生成头结点*/

rear=h;

scanf("%d",&a); /*读入数据*/

while(a!=-1)

{new=(structlink*)malloc(LEN); /*申请新结点*/

new->data=a; /*存放数据*/

rear->next=new; /*将新结点连接到表尾*/

rear=new; /*使rear指向当前表尾*/

scanf("%d",&a); /*读入数据*/

}

rear->next='\0'; /*置最终的表尾结点指针域为空*/

returnh； /*返回头指针*/

}

main()

{structlink*head;

head=creat_link(); /*调用建立子函数*/

}

运行程序时，若输入：

102030-1

则形成的链表如图9.6所示。

图9.6建成的单链表

3)单链表的访问

链表建立好之后，就会经常对其进行各种各样的访问。而链表与数组完全不同，它各个结点的存储是不连续的，因此就不能像数组那样通过下标的变化来控制访问。在链表中不管进行什么运算，包括插入和删除，都必须从头指针开始，通过每个结点的指针域一个一个向下访问，不能进行直接定位。

例9.7

编一函数，顺序输出带头结点的单链表各结点的数据域内容。

voidprint_link(structlink*head)

{structlink*q;

q=head->next; /*让q指向第一个有效数据结点*/

if(q=='\0') /*链表为空*/

printf("linklistisnull\n");

else

{do

{printf("%5d",q->data); /*输出结点数据*/

q=q->next; /*让q指向下一个结点*/

}while(q!='\0');

}

}

4)单链表的插入操作

很多时候需要将一个新结点插入到链表的某个位置。如果在某结点之前插入一个新结点，则称为“前插”法，如果在某结点之后插入一个新结点，则称为“后插”法。下面给出在结点q和m之间插入新结点new的示意图9.7。

图9.7单链表中结点插入示意图

例9.8

在带头结点的单链表中，编一函数，在值为x的结点之后插入值为y的结点，若值为x的结点不存在则插在表尾。

解决这个问题，我们首先要查找x结点，再进行插入操作。则可能出现的插入情况有如下三种，程序应该全面处理：

(1)链表非空，值为x的结点存在，新结点插在此结点之后。

(2)链表非空，值为x的结点不存在，新结点插在表尾。

(3)链表为空，则新结点应插入在头结点之后，成为第一个结点。程序如下：

structlink*insert_link(structlink*head,intx,inty)

{structlink*new,*q;

new=(structlink*)malloc(LEN); /*生成新结点*/

new->data=y; /*新结点中存入数据y*/

q=head;

while((q->next!='\0')&&(q->data!=x)) /*表非空且未到表尾，查找值为x的结点*/

q=q->next; /*q不断向后移动*/

new->next=q->next; /*让新结点指向q之后的结点*/

q->next=new; /*让q指向新结点*/

return(head);

}函数执行时，若是空表，则循环的第一个条件(q->next!='\0')不满足，循环不进行，此时q指向头结点，则执行语句“new->next=q->next;q->next=new;”，便会使new成为第一个结点；若不是空表且值为x的结点存在，则通过循环会使q指向值为x的结点，再执行语句“new->next=q->next;q->next=new;”，使new结点插入在q结点之后；若不是空表且值为x的结点不存在，则通过循环会使q指向尾结点，再执行语句“new->next=q->next;q->next=new;”，使new结点插入尾结点之后。

读者可以思考：如何实现在值为x的结点之前插入值为y的结点？

5)单链表的删除操作

有些时候需要将链表中的某个结点删除，主要操作就是让待删结点之前的结点指向其后的结点，这样再从head开始访问链表时就找不到了。上述过程称为“逻辑”删除，因为该结点所占的存储空间并没有释放掉；只有用free()函数将其空间释放，才是真正的删除，称为“物理”删除。

例9.9

在带头结点的单链表中，编一函数删除指定结点。

假定被删除结点是m，如图9.8所示，我们必须找到m之前的结点才能实现删除操作。

图9.8单链表中结点删除示意图

structlink*delete_link(structlink*head,intx)

{structlink*q,*m;

q=head;

m=head->next;

while((m!='\0')&&(m->data!=x)) /*寻找被删除结点m*/

{q=m; /*q始终指向m之前的结点*/

m=m->next;

}

if(m=='\0') /*不存在符合条件的结点*/

printf("cannotexit!\n");

else

{q->next=m->next; /*逻辑删除结点*/

free(m); /*物理删除结点*/

}

return(head);

}

因为本例题处理的链表是带头结点的，所以即使被删除结点是头结点之后的第一个结点也不需要作特殊处理。但如果链表不带头结点，则出现此种情况时就得考虑对head的修改问题。

共同体也是一种构造数据类型，它的主要特点是，共同体变量中的所有成员占用同一段存储空间，这段空间的大小就是所有成员中字节数最大的值。而我们学习的结构体变量中的成员各自占有自己的存储空间，这是两者的本质区别。另外，共同体类型说明及变量定义都与结构体类型说明及变量定义的方式类似。9.2共 同 体 类 型共同体类型说明的形式如下：

union共同体类型名

{成员列表；

}；

其中union是C语言的关键字，共同体类型名只要符合C语言标识符命名规则即可。

共同体变量的定义同结构体变量的定义类似，也有三种方式，本节以第二种方式为例：

unionun1

{inta;

charb;

floatc;

}x;

由此看出，共同体“unionun1”共有三个成员，而其中成员c所需的存储空间最大，是4个字节。所以共同体变量x共占用存储空间4个字节，它的三个成员共享此段空间。其存储空间结构如图9.9所示。

说明：

在某一时刻，这段空间中只能存储一个成员的数据，这个数据就是最后一次赋予的值。

(2)不能对共同体变量进行初始化，也不能进行整体赋值运算。

例如：

x.a=10;

x.b='e';

x.c=80.2;

则这段存储空间保存的值是最后一次赋予的数据80.2。

图9.9共同体存储空间示意图

例9.10

编一程序，实现输出一个int型数据的高字节和低字节两个数。

可以利用共同体的特点解决这个问题，程序如下：

#include"stdio.h"

uniondisa

{intx;

charch[2];

};

main()

{uniondisanum;

printf("pleaseenterainteger:");

scanf("%d",&num.x);

printf("low:%d,%c\n",num.ch[0],num.ch[0]);

printf("high:%d,%c\n",num.ch[1],num.ch[1]);

}

共同体变量num中包含两个成员，两个成员都是2个字节，因此整个变量所占空间也是2个字节。

运行程序时如果输入16738，则系统会将整数16738以二进制(0100000101100010)的形式存入存储单元，如图9.10所示。

从图9.10中可以看出，低字节二进制“01100010”转换成十进制为“98”，是字符“b”的ASCII值；而高字节二进制“01000001”转换成十进制为“65”，是字符“A”的ASCII值。所以本程序的运行结果如下：

low:98,b

high:65,A

图9.10共同体变量

一般信息的存取都是以字节为单位的，但有时候因为数据较小等原因，不需要一个字节的空间，C语言也为我们提供了可以按位存取的方法，这就是位段。

在定义结构体时，以位为单位来声明成员所占的内存长度，这样的成员就称为位段或位域。例如：9.3位段结构类型

structbitdata

{unsigneda:3;

unsignedb:5;

unsignedc:4;

unsignedd:4;

}i;

此结构体中定义了4个位段a、b、c、d，分别占3位、5位、4位、4位，共2个字节。即变量i共占2个字节，如图9.11所示。

图9.11位段结构从图9.11中可看出，位段a和b正好组合成一个字节，而位段c和d也正好组合成一个字节。实际上，完全可以不必在意如此，C语言允许任意声明位段1～8范围内的任意位数。例如：

structbitdata

{unsigneda:2;

unsignedb:5;

unsignedc:3;

unsignedd:2;

}x;现在大家要特别注意，位段a和b共7位，不满一个字节，还剩1位，但紧接其后的位段c却需要3个字节，所以系统会另外起一个存储单元来存放位段c，同样，第二个存储单元也会出现3位空闲，如图9.12所示。

图9.12位段存储示意图此时变量x中的4个成员可以像前面章节中介绍的那样进行引用，也可以进行相应的数值运算及输入/输出，但注意不要超出数值范围，例如：

x.a=2; /*a位段只有2位，最大值为3，超出范围则结 果出错*/

x.b=x.a+10;

说明：

(1)位段成员的类型必须指定为unsigned或int类型。

(2)一个位段必须存储在一个单元内，不能跨单元，如图9.12中位段c所示。

(3)不能定义位段数组。

(4)可以使用如下形式，使某位段从另一字节开始存放：

structbitdata

{unsigneda:2;

unsignedb:3;

unsigned:0;

unsignedc:3;

};

虽然位段a、b、c可以存放在一个单元内，但我们使用“unsigned:0;”使位段c从下一个存储单元开始存放。

枚举类型是ANSIC新标准增加的类型。

“枚举”就是一一列举的意思，枚举类型就是一一列举出来变量的值，然后此变量就只能使用列举出来的值。9.4枚举类型

1.枚举类型

枚举类型的声明如下例：

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

其中，enum是C语言中的关键字。“sun,mon,tue,wed,thu,fri,sat”这六个枚举元素称为枚举常量，系统把它们当作常量来使用。既然是常量，那就代表着一定的数值，系统按顺序赋给它们的值分别是“0,1,2,3,4,5,6”。如果不希望得到系统默认的值，也可以在声明时指定数据，例如：

enumweek{sun=7,mon=1,tue=2,wed=3,thu=4,fri=5,sat=6};

不管哪种声明方式，枚举常量都具有确定的值，因此也可以参与合理的数值运算。例如：

mon-1

if(wed>sat)

2.枚举变量

枚举变量的定义同样也有三种方式，例如：

enumweekworkday,weekday;

或

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

或

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

以上定义的枚举变量workday,weekday的值只能是sun到sat其中之一，不能超出这个范围，如下赋值语句是正确的：

workday=thu;

weekday=sun;

C语言允许用typedef来声明一个新的类型名代替已有的类型名，这些已有的自定义类型名可以是整型、实型、字符型、结构体型等。

声明新类型名的形式如下：

typedef类型名新类型名；

其中，“类型名”是已经声明了的合法的类型，而“新类型名”只要是合法的C语言标识符即可。9.5自 定 义 类 型例如：

typedefintINTEGER;

typedefcharCHARACTER;

注意，typedef语句并未产生新的类型，只是同一种类型又多了一个名称，同时原有类型名也依然有效。如下两个语句是等价的，都是定义了两个整型变量a、b：

inta,b；

INTEGERa,b;

为了便于区别起见，新的类型名一般采用大写形式。另外，利用typedef也可以为构造类型声明一个新名称，例如：

typedefstruct

{intnum;

charname[20];

floatscore;

}STUDENT;这时候是对此结构体类型声明了一个名称STUDENT，而绝不是定义了结构体变量。下面我们可以用STUDENT来定义这种结构体类型的变量或数组等：

STUDENTstu1,stu2,stu[30];

变量stu1、stu2都具有三个成员项，数组stu每个元素也都具有三个成员。

9.6.1结构体的应用

例9.11

有一场比赛，其中参赛选手10名，编号为1～10，评委3位，选手的得分是三位评委打分的平均值，最后获胜的只有一位最高分获得者。请编写函数，利用结构体数组计算每位选手的得分，并求出最高分，要求在主函数中输入数据并输出各选手得分和优胜者的相关信息。9.6程序举例

#include"stdio.h"

#defineN10

typedefstruct

{intsn;

floatscore1,score2,score3;

floataver;

}MATCH;

intpeak(MATCHplayer[])

{inti,j,m;

floatsum;

for(i=0;i<N;i++)

{sum=player[i].score1+player[i].score2+player[i].score3;

player[i].aver=sum/3;

}

m=player[0].aver;

j=0;

for(i=1;i<N;i++)

if(player[i].aver>m)

{m=player[i].aver;

j=i;

}

returnj;

}

main()

{MATCHpy[N];

inti,max;

for(i=0;i<N;i++)

py[i].sn=i+1;

printf("请输入十个选手的得分:\n");

for(i=0;i<N;i++)

{printf("%d#:",py[i].sn);

scanf("%f,%f,%f",&py[i].score1,&py[i].score2,&py[i].score3);

}

max=peak(py);

printf("各选手的得分如下：\n");

for(i=0;i<N;i++)

printf("%8.2f",py[i].aver);

printf("优胜者是：\n");

printf("%d号%6.2f",py[max].sn,py[max].aver);

}

实际生活中一般比赛分数是这样统计的：去掉最高分和最低分，然后再求平均值；而且一般还会将得分排序输出。所以读者可以自己思考，对本程序进行修改完善。9.6.2*单链表的应用

例9.12(其中划线部分为要填空的空格。)设链表上每个结点的数据结构为

typedefstructnode

{intd;

structnode*next;

}NODE;

函数NODE*invert(NODE*head)的功能是：将head指向的单链表逆置，即将原链表最后一个结点变为第一个结点，原来倒数第二个结点变成第二个结点，依此类推。在逆置过程中不建立新的链表。请填写完成函数中的空格。算法提示：从前往后，逐个改变结点指针域的指向，如将第二个结点指向第一个结点，将第三个结点指向第二个结点，依此类推，直至尾结点。最后把原来第一个结点(逆置之后是最后一个)的next域置空，把原来最后一个结点(逆置之后是第一个)的地址赋予head。

NODE*invert(NODE*head)

{NODE*p,*q,*r;

if(head==0||head->next==0)

returnhead;

p=head;

q=p->next;

while(q!=0)

{r=[1];

q->next=p;p=q;q=r;

}

[2]=0;

head=p;

returnhead;

}

答案：[1]q->next[2]head->next

一、选择题

1.已知有结构类型定义：

typedefstructex{longintnum;

charsex;

structex*next;

}student;

下列叙述中错误的是()。

A.

structex是结构类型B.

student是结构类型的变量名

C.

ex可缺省 D.

student不可缺省习题9

2.已知有如下的结构类型定义和变量声明：

structstudent

{intnum;

charname[10];

}stu={1,"marry"},*p=&stu;

则下列语句中错误的是()。

A.

printf("%d",stu.num);B.

printf("%d",(&stu)->num);

C.

printf("%d",&stu->num);

D.

printf("%d",p->num);

3.已知结构类型定义和变量声明如下：

structsk

{inta;floatb;}data[2],*p;

若有p=data，则以下对data[0]中成员a的引用中错误的是()。

A.

data[0]->aB.

data->aC.

p->aD.

(*p).a

4.已有结构类型定义和变量声明如下：

structperson

{intnum;

charname[20],sex;

struct{intclass;charprof[20];}in;

}a={20,"lining",'M'{5,"computer"}},*p=&a;

下列语句中正确的是()。

A.

printf("%s",a->name);B.

printf("%s",p->f);

C.

printf("%s",*);

D.

printf("%c",p->in->prof);

二、阅读程序题

1.以下程序的输出结果为

。

#include<stdio.h>

structs

{inta;

structs*next;

};

main()

{inti;

staticstructsx[2]={5,&x[1],7,&x[0]},*ptr;

ptr=&x[0];

for(i=0;i<3;i++)

{printf("%d",ptr->a);ptr=ptr->next;}

}

2.以下程序在运行时，输出结果的第一行是

，第二行是

，第三行是

。

#include<stdio.h>

typedefstructs

{intindex;

intvalue;

}M;

main()

{staticinti,j,k,c[4][4];

Ma[10]={{0,1},{3,2},{5,3},{6,4},{9,5},{15,6},{-1,0}},*p=a,

b[10]={{1,1},{3,2},{4,3},{6,4},{10,5},{13,6},{-1,0}},*q=b;

while(p->index!=-1)

{i=p->index/4;

j=p->index%4;

c[i][j]=p->value;

p++;

}

while(q->index!=-1)

{i=q->index/4;

j=q->index%4;

c[i][j]=q->value;

q++;

}

for(i=0;i<4;i++)

{for(j=0;j<4;j++)

printf("%d",c[i][j])；

printf("\n");

}

}三、完善程序题

1.以下程序按结构成员grade的值从大到小对结构数组pu的全部元素进行排序，并输出经过排序后的pu数组全部元素的值。排序算法为选择法。

#include<stdio.h>

struct{

intid;

intgrade;

}STUD;

voidmain

{STUDpu[10]={{1,4},{2,9},{3,1},{4,5},{5,3},{6,2},{7,8},

{8,6},{9,5},{10,2}},*temp；

inti,j,k;

for(i=0;i<9;i++)

{k=

;

for(j=i+1;j<10;j++)

if(

)k=j;

if(k!=i)

{