C语言程序设计基础（第二版）课件：用户可建立的数据类型-复杂数据的表示与处理

用户可建立的数据类型

—复杂数据的表示与处理9.1结构体9.2共用体9.3枚举类型9.4用户自定义数据类型名称9.5用结构体和指针处理链表实操训练课外练习

9.1结构体

描述一个客体属性的不同类型数据的集合如何表示与处理？结构体是把描述一个实体不同属性的相关数据组织在一起，构成一个数据对象进行存储和处理的一种构造型数据。这类数据在有些程序设计语言中称为记录，而在C语言中称为结构体。

结构体通常是由不同类型数据所组成的一个集合。一个结构体中的一个基本数据称为“成员”(也称“域”或“数据项”，或“元素”)。结构体的引入为处理复杂数据结构提供了有力手段，特别是为处理数据结构复杂的大型程序设计提供了方便。

9.1.1结构体类型与结构体变量的定义

在程序中如何使用结构体数据对象？

结构体属于一种用户自定义的数据类型。不同对象有不同的结构，可定义一种类型来表示一种结构。使用结构体类型数据，必须先定义结构体类型，然后定义该类型的变量，通过变量对其数据进行存储及引用。定义一个结构体类型和变量，可采用三种方式。

1．先定义结构体类型，再定义结构体变量

定义结构体类型的一般形式为

struct结构体类型名

{

类型成员名1；

类型成员名2；

…

类型成员名n；

}；

其中，“struct”为结构体类型定义关键字，是结构体类型的标识符。“结构体类型名”是所定义结构体的类型名称，这个名字由用户命名，其命名同变量名、数组名一样，要符合C语言的标识符命名规则。用户可以用该类型名来定义结构体变量。花括号中定义该结构体类型所包含的成员，即成员的类型、名称及其顺序关系。成员名的命名规则与标识符命名规则相同。成员类型可以是基本类型或者任何在该结构体类型之前已经定义过的自定义

类型。

结构体类型的定义仅是声明了一种数据对象的结构类型，仅表示一种抽象结构，并不代表具体的数据对象，编译系统也不分配存储空间，不能在程序中引用。要使所定义的结构体类型代表一个数据对象，需定义结构体类型变量。定义结构体类型变量的一般方式为

struct结构体类型名变量名；

其中，“struct结构体类型名”代表一种结构体类型，其后的变量名就被定义为可表示该结构体类型的变量，变量表示具有该结构体的实体对象，编译系统给结构体变量按结构体成员顺序与类型分配存储空间。

例如，定义表示日期的结构体类型：

structdate

{

intyear；

intmonth；

intday；

}；

date是结构体类型的名称，year、month和day分别是整型数据成员的名称，表示日期中的年、月、日。

定义了结构体类型之后，就可以用该类型来定义结构体变量。如：

structdatedate1;

date1是被定义为表示日期类型的结构体变量。其存储结构是连续分配3个整型数据的单元，一个整型数据占4个字节，共占12个字节的存储空间。

结构体类型定义中，成员类型可以是已经定义过的任何一种数据对象的类型。例如，在定义了日期结构体类型的基础上，可定义一个学生信息的结构体类型：

学生结构体类型定义中包含日期结构体成员birthday，即结构体类型可以嵌套定义。但是，结构体不允许递归定义，即结构体的成员不能为该结构体的变量。如，下面的定义是非法的：

在定义了student结构体类型的基础上，可以定义该结构体类型的变量：

structstudentstudent1，student2；

从上述可以看出，由一个结构体类型可以定义多个结构体变量。

2．在定义结构体类型的同时定义结构体变量

该方式定义的一般形式为

在定义结构体类型的花括号外直接定义变量，可以定义一个变量，也可以定义多个变量。定义多个变量时，变量之间要用逗号分隔。例如：

定义了人的基本信息的结构类型“structpeople”，同时定义了两个结构体变量person1、person2。

3．直接定义结构体类型变量

该方式定义的一般形式为

显然，这种定义方式是在第2种定义方式中去掉结构类型名，其他定义内容完全相同。

例如：

从上述可知，定义结构体类型的目的是定义结构体变量，只有结构体变量才能存储和处理结构体数据，前两种方式定义了结构体类型名称，可以使用这种结构体类型名称来定义新的结构体变量。第3种定义方式中，没有用结构体类型名，无法利用结构体类型名来定义新的结构体变量。

结构体成员可以与程序中的其他变量同名，两者代表不同对象，互不影响。结构体的定义可以放在函数内，也可以放在函数外。在函数内定义的结构体只能在函数内使用(即局部数据对象)。在函数外定义的结构体可以在定义点之后的所有函数内使用(全局数据对象)。

9.1.2结构体变量的初始化

如何给结构体变量提供初始数据？

定义了结构体变量后，系统按成员的顺序和类型给其分配存储空间，但成员没有指定的数据。对结构体提供数据是针对成员来进行的，也就是说，不能对结构体整体进行，这与数组类似。对结构体成员提供数据有两种方式，一种是在定义结构体变量时提供初始值，称为初始化；还有一种是在程序运行中，通过赋值操作给成员提供值。一般在定义结构体变量时，需进行初始化。结构体变量初始化的方式是：按结构体成员的顺序和类型分别提供初始数据。

例如，对前面定义的学生结构体变量初始化如下：

structstudentstudent1={0103208，"liuxiqiao"，'w'，{1983，9，17}}；

给结构体变量赋初值要用花括号将所有成员数据括起来。在花括号中要按成员顺序提供初始数据，数据类型要与定义的成员类型一致。例如“姓名”成员是字符数组，可以通过字符串提供初值，也可以按字符数组元素的方式提供初值。“出生日期”成员是一个结构体类型，要按定义的日期结构体来提供初值，其年、月、日数据用花括号括起来。

9.1.3结构体成员的引用

如何引用结构体变量中的数据？

系统把结构体变量看作一个数据对象，给其分配数据空间，按成员的顺序和类型连续存储数据，但对结构体变量的数据不能整体引用，只能按成员来引用。结构体数据的引用方式与数组数据的引用方式类似。

结构体成员引用的形式为

结构体变量名.成员名

其中，“.”是C语言中的一种运算符，称为“取成员运算符”。“.”的优先级是C语言中优先级最高的运算符，具有左结合性(参见附录C)。

例如，前面定义的一个学生信息的结构体变量，student1.num表示学号成员数据项。

如果成员又是一个结构体类型，则要分层用成员运算符，一级一级地找到最基本的成员。例如，要引用一个学生信息的结构体变量中的出生日期数据，要分别采用如下的引用

形式：

不能用student1.birthday来引用出生日期数据。

可以对结构体变量中的成员进行输入、输出、赋值、运算等操作。

对结构体成员输入数据，要取成员地址。例如：

scanf("%ld",&student1.num);

一个成员变量可以像基本类型变量一样进行相应的运算。例如：

sum=student1.age+student2.age;

student1.age++;

例9.1定义一个学生成绩表的数据结构，学生信息包含学号、姓名、出生日期，有5门课成绩，从键盘输入数据，求出学生总分，输出学生数据和总分。

编程思路：学生成绩表包含许多学生数据，每个学生具有相同的数据结构，属于典型的结构体类型数据。先定义学生数据结构，再定义学生数据结构的变量。学生信息的输入和处理要针对成员数据来进行。

分析：在程序中定义两个结构体类型，学生结构中嵌套了日期结构，形成了嵌套结构。定义了结构体变量s来表示具体学生的结构数据。从程序及其运行结果可以看出，结构体成员的输入/输出只能按基本类型数据元素来进行。例如，输入成员数组元素采用语句“scanf("%f",&s.score[i]);”，输出成员数组元素采用语句“printf("Score%d:%-6.1f",i,s.score[i]);”。

9.1.4结构体数组

批量结构体类型数据如何表示与处理？

在实际应用中，经常遇到结构体类型的批量数据，如一个班级的学生信息。一个学生的基本信息是一个结构体类型数据，一个班级的学生基本信息就是一个结构体数组。C语言允许定义结构体数组。

结构体数组是复合型构造数据类型，即结构体数组中所有元素是同一类型的结构体数据对象，一个元素是一个结构体数据对象。所以，结构体数组的定义、初始化和元素引用方法都是数组和结构体中方法的类推。

因为结构体数组元素是用户自定义的结构体类型，所以定义结构体数组应先定义元素的结构体类型，再按已定义的结构体类型定义数组。其定义方式与结构体变量的定义方式相仿。只要在结构体变量定义中的变量名位置写上数组定义符号即可。结构体数组定义也有与结构体变量定义对应的3种方式。若已定义了结构体类型(具有结构体类型名)，则一维结构体数组定义的一般形式为

struct结构体类型名数组名[数组长度]；

其中，“struct结构体类型名”是已经定义过的结构体类型，其他和数组定义一样。另外两种定义方式在后面的例子中说明。同样也可定义二维结构体数组。二维结构体数组不太常用，不再细述。

结构体数组的初始化是先按元素顺序，再按元素的结构体成员顺序与类型来提供初始数据。所以就形成了按元素顺序依次对结构体成员初始化的过程。

对结构体数组元素的引用也是先引用数组元素(结构体对象)，再引用该元素中的结构体成员。

例9.2构造一个班一门课程成绩表的数据结构，初始化成绩表信息，查找出不及格学生，并输出该学生的全部信息。成绩表信息包括学号、姓名、课程、成绩。

编程思路：学生基本信息包含不同类型数据，应是一个结构体类型。一个班成绩表应是结构体数组。所以，采用结构体数组进行处理。为简化数据，说明处理方法，程序中只对5个学生信息进行处理。

分析：

(1)在程序开头定义了一个结构体类型，同时定义了结构体数组st[5]，又对数组进行了初始化。内层一个花括号对应一个数组元素，花括号内的数据对应一个结构体成员的数据。可以看出，数据类型与所定义的成员类型一一对应。如果去掉结构体类型名“student”，或者把结构体数组定义放在主函数中，用“structstudentst[5];”定义，程序都能正确运行。请读者自行验证。

(2)在程序中求总分和输出不及格学生的信息中都采用了“数组名[i].成员名”的引用形式，表示引用数组第i个元素中指定的成员数据。如“st[2].score”是引用结构体数组第2个元素的结构体成员score的值(即对应数组中的第2个学生的成绩)。

从上例可以看出，只要掌握结构体数组复合层次关系，类推数组元素的引用到结构体成员的引用上，对结构体数组的引用就不难理解。最终都类推到对基本变量的引用上。

9.1.5结构体指针

何谓结构体指针？如何通过结构体指针引用其数据？

定义了结构体类型与结构体变量后，系统给结构体数据分配一个存储空间，按照成员顺序连续存储，按成员类型分别占据不同字节的存储长度，每个成员都有确定的存储地址，结构体数据对象的首地址就是结构体的指针。对结构体数据也有两种访问方式：直接访问和间接访问。前面讲的“结构体变量名.成员名”访问方式就是直接访问，也可以通过指向结构类型的指针变量来间接访问结构体数据。

结构体数组存储结构也同样保持结构的复合关系，先按元素顺序连续存储，再按成员顺序和类型分配存储空间。每一个结构体元素及其成员都有确定的存储地址。对结构体数组数据也有两种访问方式。“数组名[下标].成员名”是直接访问。同样，也可以通过指向结构体数组的指针变量来间接访问。

掌握了指针及指针变量的实质，通过指针变量来访问结构体及结构体数组就不难理解了。指向结构体对象的指针变量可指向结构体数据，也可指向结构体数组中的元素。

指向结构体的指针变量定义、赋初值及通过指针变量引用数据的方法同普通指针变量相仿。只需用自定义的结构体类型来定义指针变量，取结构体类型变量地址赋给指针变量，即可建立指向。例如：

通过指针变量对结构体数据的引用有两种方式：

这两种方式是等价的，可以相互取代。注意：指针变量名两侧的括号是不能缺省的。

1．通过结构体指针变量来引用结构体成员值或结构体数组中的成员值

下面通过两个例子来说明通过指针变量来引用结构体数据和结构体数组元素。

例9.3通过指向结构体变量的指针变量输出结构体变量中成员的信息。

编程思路：为了便于对比，仍以学生信息表数据为例。

分析：在主函数中定义学生信息结构体类型的同时定义了结构体变量st，并进行了初始化。接着定义了指向结构体类型的指针变量p，&st赋给p，使其指向结构体变量st。两个printf函数调用中，分别采用结构体变量名引用法和指针变量引用法，输出结果完全一样，但意义有所不同，结构体变量名表示结构体数据的地址是固定的，指针变量的指向是可以变化的。

例9.4通过指向结构体数组的指针变量实现例9.2所要求的功能。

分析：程序中定义了指向结构体类型的指针变量ps，把数组名表示的数组首地址赋给ps。在for循环中，“ps=st”使ps指向数组首元素，“ps++”是数组逻辑指针的调整，即使ps指向下一个元素(结构体成员)，“ps<st+5”中的st+5仍是一个逻辑指针，表示ps指向最末一个元素后结束，最末一个元素的指针是st+4。

2．用结构体变量和结构体变量的指针作函数参数

从前述已经知道，变量作函数参数，实参向形参单向传递变量的值；指针作函数参数，实参向形参传递地址，使实参和形参共同指向一个存储单元或存储区，使主调函数和被调函数共享存储单元或存储区中的数据。同样，结构体变量作函数参数，实参向形参传递结构体变量中的成员值，即传递的是不同类型的多个数据；结构体变量的指针作函数的参数，实参向形参传递结构体数据对象的地址，使主调函数和被调函数能共享结构体存储空间的成员数据，即能实现结构体成员数据的双向传递。下面通过实例来说明，请认真理解。

例9.5设一个班有3门课程的成绩表，学生学号、姓名已存入系统，从键盘录入学生3门课成绩，求每个学生的平均成绩，并将平均成绩最高的学生信息输出。

编程思路：学生成绩表属于结构体数组结构。从功能上可由3个函数来实现，显示学生学号、姓名，录入3门课成绩，同时求平均成绩；找出最高平均成绩；输出平均成绩最高的学生信息。

分析：

(1)定义学生成绩结构体类型，同时定义结构体数组，只给学号、姓名成员赋初值。

(2)定义成绩录入并求平均分函数input，结构体数组名作参数，系统把数组名看作指针变量，接收实参传递的指针。屏幕上显示学号、姓名，只输入3门课成绩。外循环控制录入第i个学生成绩，内循环控制录入第j门课成绩。使用了结构体数组元素中成员元素的引用“st[i].score[j]”。

(3)定义找最高平均分函数，结构体数组名作形参。在循环中只比较数组元素的平均分成员项“st[i].aver>st[m].aver”。

(4)定义输出学生信息函数，结构体变量作形参，接收实参传递的结构体变量值(全部成员数据)。

(5)函数调用，“input(p);”把指针变量p的值(结构体数组首地址)传递给形参st，使p和st都指向结构体数组，函数中录入的成绩就存入结构体数组的成绩数组中，所求平均分存入平均分成员项中。因为结构体数组属于全局数据对象，所在函数中的操作结果可供其他函数使用。

(6)函数调用，“print(max(p));”先调用“max(p)”，把结构体数组首地址传递给形参，在函数中使用结构体数组的平均分成员数据进行比较，返回最高平均分结构体元素st[m]，再产生“print(st[m]);”调用，在函数中输出最高平均分学生的全部信息。

9.2共用体

何谓共用体？怎样表示与使用共用体？共用体是多个不同类型数据对象存储在一个单元或空间，即通过覆盖方式共同占用一个单元或空间。被定义为共用体中的数据对象，也称为“成员”。利用共用体，可以使数据处理的方法更加灵活，能提高程序的效率。

9.2.1共用体类型与共用体变量的定义

共用体是用户自定义的一种数据存储结构类型，必须先定义类型，再定义变量，通过变量来引用共用体中的成员。

共用体定义的一般形式为

其中，union是共用体类型定义关键字；共用体类型名是用户自定义的类型名称；花括号中可以是任一类型的数据对象，包括自定义类型；共用体变量名表是用户自定义的共用体类型变量，如果定义多个变量，变量之间要用逗号分隔。

共用体定义同结构体相仿，也有3种定义方式。在上述定义中可以不要“共用体类型名”，也可以在定义共用体类型之后，利用已定义的共用体类型来定义变量。其一般形式为

union共用体类型名共用体变量名表；

定义了共用体类型与变量后，编译系统按成员中占据存储字节数最多的成员分配一个存储单元或空间。

例如：

uniondata

{

inti;

charch;

floatf;

}a;

系统给i、ch、f按实型数据分配一个存储单元，通过变量a可引用3种数据之一。其存储结构如图9.1所示。为说明问题，假定整型数占2个字节，实型数占4个字节。图9.1共用体存储结构示意图

9.2.2共用体变量引用

同结构体数据引用相仿，共用体变量只能引用其中的成员，也有两种引用形式。

形式一：

共用体变量名.成员名

形式二：

共用体指针变量名->成员名

因为共用体成员通过覆盖方式共享一个存储单元或空间，一个变量的瞬时值只能是一个类型的成员值，所以对共用体赋值及引用，一个时刻只能对一个成员进行操作。这与结构体变量是截然不同的。

关于共用体变量引用的几点说明：

(1)共用体变量初始化与赋值。可以对共用体变量初始化，在初始化表中只能有任一成员类型的常量，不能期望同时给各个成员提供初始数据。例如：

实际上是向共用体变量存入一个整型数。如初始化表为{230,'a',3.6}则是错误的。

可以在程序中给共用体变量的成员赋值，但不能给共用体变量赋值。例如：

都是正确的。但如果有a=3.6则是不正确的。

如果有多次赋值，共用体变量中只是最后一次所赋的值，即后面的赋值覆盖前面的赋值。如上面的赋值语句被执行，则引用3个成员的值都是230。

(2)共用体变量的地址和成员的地址是同一地址，即有&a==&a.i==&a.ch==&a.f，因为3个成员共享一个存储单元。

例9.6录入表9.1中的数据，并输出。

编程思路：从表中可以看出，教师和学生信息前四项都是相同的，只有最后一项不同。如果在一个实际应用系统中把学生和教师信息以单独表的结构来存储、处理，不但会重复占据存储空间，也给程序设计带来一定的麻烦。如果把最后一项作共用体数据对象，将会避免上述问题。为说明方法，只编写一位教师和学生的信息处理程序。

分析：程序中定义了全局结构体数组person[2]，存储两个人的信息。在结构体类型定义中嵌套定义了一个共用体变量category，其中有两个成员，company和charposition[10]，身份是学生，则存班级信息(整型数据)；身份是教师，则存职称信息(字符数组)。使用共用体变量，使两种人员信息统一在一个数据结构中。人员信息输出中，相同信息项作相同处理，只是对不同信息项作选择处理，简化了程序设计，也提高了程序效率。

9.3枚举类型

一些事物属性只能列举，不具有数值关系，这些数据对象怎样表示与处理？现实中存在一些可列举的数据对象，如一周有星期一到星期日，颜色有红、橙、黄、绿、青、蓝、紫，等等。这种数据对象只可列举，不具有数值关系，似乎难以在计算机中处理。C语言允许将这类数据定义为枚举类型，能方便地进行处理。

枚举类型与枚举变量的定义也同结构体相仿，定义的一般形式为

其中，enum为枚举类型定义的关键字；枚举类型名是用户自定义的表示所定义枚举类型的名称；“枚举元素列表”是用逗号分隔的列举的元素名称序列；枚举变量列表是定义枚举类型的同时定义的变量名。一个枚举类型可定义多个变量，变量间用逗号分隔，就是枚举变量列表。枚举类型与枚举变量定义也可有3种形式。在上面的定义中可以省略“枚举类型名”而直接定义枚举变量。也可以先定义枚举类型，然后用所定义的枚举类型来定义枚举变量。其定义的一般形式为

enum枚举类型名枚举变量列表

例如：

enumWeekday

{Sunday，Monday，Tuesday，Wednesday，Thursday，Friday，Saturday}weektime；

关于枚举数据的几点说明：

(1)枚举元素虽以标号列出，但C编译系统按常量处理，故称枚举常量。在程序中不能给枚举元素赋值，即枚举元素相当于一个符号常量。

(2) C编译系统对枚举元素按定义的顺序依次赋值0，1，2，3，4，5，…。在上面的定义中，Sunday的值为0，Monday的值为1，…，Saturday的值为6。也可在定义时，给枚举元素指定常量序列值。例如：

enumWeekday

{Sunday=7，Monday=1，Tuesday，Wednesday，Thursday，Friday，Saturday}weektime；

这时，从Tuesday开始依次在前面元素值上加1，形成该元素的值，即Tuesday为2，Wednesday为3，Thursday为4，Friday为5，Saturday为6。

(3)枚举变量的取值范围是列举元素值的范围。如Sunday只可能取0～7之间的一个整数。

(4)由于枚举型变量的值是整数，因此C99标准中也把枚举型作为整型数据，用整型变量来表示枚举型元素值。

例9.7一个盒子中有红、黄、蓝3种颜色的球若干，每次从盒子中先后取出3个球，编程求解取不同颜色球的排列数，并输出每种颜色排列。

编程思路：定义3种颜色的枚举类型，再定义3个枚举类型或整型变量i、j、k，分别表示3个球的颜色值，然后用枚举算法求取出3个球的颜色排列数。

枚举算法：当取出的两个球颜色不同(i≠j)时，取第3个球。如果第3个球与前两个球颜色都不同(k≠i且k≠j)，则是一次有效排列取法，计数一次。如此，i、j、k依次取3种颜色值之一，进行判断，可得到求解结果。显然，应该用三重循环来实现。

分析：

(1)定义了3种颜色的枚举类型后，编译时，3种颜色标号依次具有值0、1、2。

(2)定义i、j、k、pri表示颜色取值变量，等价于枚举变量。

(3)三重循环实现3次取球的颜色排列。第3层内循环的if语句要执行27次，实现3次取球的颜色排列判断。当判断出3个球的颜色不同时，则计数变量n+1，将颜色值转换成颜色字符输出。

(4)将颜色值转换成颜色字符输出，由if语句中嵌套的for循环来实现。当判断3个球颜色不同时，由switch(loop)分别将i、j、k当前值赋给pri，再由switch(pri)输出颜色值对应的颜色字符。

(5)使用枚举类型，使枚举元素标号具有整型值，可以很方便地进行比较判断和相应的运算。

(6)只要在枚举类型中添加颜色元素，再于循环中更改最后一个颜色的取值，即可实现更多种颜色的取球模型求解。取球模型代表了随机抽样一类应用问题。

9.4用户自定义数据类型名称

用户可以根据自己的习惯改变C语言规定的数据类型的关键字符号吗？C语言提供了丰富的数据类型，每一种类型都有规定的关键字，自定义的结构体、共用体、枚举类型也要使用规定的关键字和格式来定义。有些关键字可能不符合一些人的记忆习惯。尤其是学习过其他编程语言的人，对一些关键字容易搞混。

例如FORTRAN语言中整型的关键字是Integer，实型的关键字是Real。C语言中，可以用typedef给已有的类型名重新定义名称。其实，满足人的记忆习惯仅是typedef的一个方面，其更重要的意义在于提高C程序的移植性。typedef有多种用途。

1．用新类型名代替原有类型名

其使用的一般形式为

typedef已有类型标识符新类型名；

其作用是用“新类型名”代替原有类型标识符，即为原有的一个数据类型重新命名，而不是定义一种新的数据类型。

例如：

typedefintInteger；

typedeffloatReal；

经此定义后，在程序中就能用Integer、Real来定义整型、实型变量了。例如：

Integeri，j；(与“inti，j;”等效)

Reala,b;(与“floata,b;”等效)

2．用一个简单类型名代替复杂的类型

诸如数组类型、结构体类型、共用体类型、枚举类型等，看起来比较复杂，可用typedef定义一个简单的类型名代替复杂的类型。

(1)用一个新类型名代表数组类型：

typedefintNum[100]; //定义Num为包含100个元素的整型数组类型名

Numa; //与inta[100];等效

(2)用一个新类型名代表指针类型：

typedefchar*String; //定义String为字符指针类型

Stringp,s[10] //与char*p,*s[10];等效

(3)用一个新类型名代表指向函数的指针类型：

typedefint(*Pointer)(); //定义Pointer为指向返回值为整型的函数的指针类型

Pointerp1,p2; //与int(*p1)(),(*p2)();等效

(4)用一个新类型名代表结构体类型：

定义了新类型名Data代表上面的一个结构体类型。可以用Data定义结构体变量。如：

Databirthday; //定义了结构体类型变量birthday

9.5用结构体和指针处理链表

9.5.1链表简介链表是动态地进行存储分配的一种数据结构，特别适合规模不确定的复杂数据结构的批量数据表示与处理问题。例如，在一个学生成绩管理系统中，需要处理多个班级的学生数据，每个班学生数是不固定的。采用数组可以表示成绩表数据，但在定义数组长度时就会产生困惑。按人数少的班级定义数组长度，人数多的班级数据不够用，按人数多的班级定义数组长度，则必然造成存储空间的浪费。采用链表来表示学生成绩表数据，可完全解除这种困惑。

链表是把一个学生的信息看作一个数据节点，成绩表数据在存储器中不连续存储，通过一个指针把一个班学生数据连接起来，动态地分配内存，即可根据学生数来开辟内存空间。链表也有多种结构，一种简单的单向链表结构如图9.2所示。图9.2一种简单的单向链表结构

链表中，与一个节点之前连接的节点称为该节点的前驱节点，与一个节点之后连接的节点称为该节点的后继节点。链表的中间节点包含两个域：一是数据域，存放学生实际数据；二是地址域，存放后继节点的地址。每一个链表都有一个头节点，只有地址域，存放指向链表首节点的地址。每一个链表也有一个尾节点，包含数据域，但地址域为空(NULL)，没有后继节点。每一个节点的地址都是由系统动态分配的。

可以看到，表中的元素节点由地址连接起来。访问表中节点数据，首先要提供头指针，由头节点指针连接表首元素节点，再由此节点连接下一元素节点，直到表尾节点。这样的链接方式，如同一个链条，一环扣一环，中间是不能断开的，所以称为链表。

链表中节点数据对象是一个结构体类型。学生成绩表链表节点的数据结构可定义如下：

其中，指针成员是指向所定义的结构体类型节点的指针，这就是建立链表的方法。在程序设计时，不需要知道各节点的具体地址，只要保证将下一节点的地址放到前一节点的成员next中即可。

9.5.2建立静态链表

下面通过一个简单例子来说明建立静态链表的方法。

例9.8建立由4个学生信息节点组成的链表，并输出各节点中的数据。

编程思路：定义节点数据对象为结构体类型，依照连接关系设置每个节点的指针成员，就可形成链表。

分析：建立链表要经历3个步骤：

①根据节点数据定义节点结构体，指针成员是不可缺少的；

②设置节点数据，只需将数据赋给结构体对应成员；

③建立连接关系，只需按节点顺序关系，取结构体变量地址赋值即可。链表节点数据输出，先使指针变量p指向头节点，输出头节点指针所指向的首节点数据，将本节点指针成员的值赋给p，即指向下一节点，一直到p为NULL。

9.5.3建立动态链表

在程序的执行过程中一个一个地开辟节点，输入数据，建立节点的连接关系，就是动态地建立链表。建立动态链表需用到第8章介绍过的动态分配内存的相关函数(malloc、calloc、realloc、free)。

建立动态链表需经过以下步骤：

(1)使用动态分配函数malloc或calloc申请节点空间，得到节点地址，第一次申请节点为head节点，地址赋给head。

(2)从第1节点开始，申请节点得到地址，录入数据存入节点对应成员中，将节点地址赋给前一节点指针成员。

(3)重复第(2)步操作，直到数据录入结束。置最后一个节点的成员指针为NULL。

为了实施上述步骤，需定义两个指针变量p1、p2，p1指向当前节点，p2指向当前节点的前驱节点。当前节点输入的数据，存放到p1所指向节点的成员中，将p1的值赋给p2，如此交替可建立动态链表。

例9.9仍以4个学生的成绩为例来说明动态链表的建立。

分析：定义creat函数实现动态链表的建立，返回值是链表头指针。定义了3个结构体类型指针，head用于指向链表头节点，p1用于指向当前节点，p2用于指向当前节点的前驱节点，在循环中交替变化，从而实现了指针的移动。“p1=(structnode*)malloc(LEN);”是按测定的结构体所占内存字节数申请节点空间，函数返回值是存储空间首地址，为匹配结构体类型指针p1，进行了强制类型转换。

实操训练

实训任务九学习复杂数据表示与处理的编程方法

实训项目设计程序，应用结构体类型及结构体数组，实现学生成绩表的存储与处理，具体实现以下功能：

(1)输入班级学生成绩表数据，存入学生结构体数组中。设成绩表中一个学生记录包含学号、姓名、4门课成绩、平均成绩。为避免繁琐的数据录入，可暂设5个学生。

(2)求出每个学生的平均成绩，存入结构体数组中。

(3)按姓名查询学生记录。从键盘输入需查询的学生姓名，输出该学生成绩单。

(4)查询包含不及格科目的学生，输出这些学生的成绩单。

(5)查询平均成绩最高的学生，输出该学生的成绩单。

屏幕界面可参照图9.3所示。

图9.3实训项目界面式样

实训指导

1.设计程序

(1)采用模块化设计方法，把成绩表输入、计算平均成绩、输出一个学生记录、按姓名查询学生记录、查询不及格科目学生、查询最高平均成绩分别设计为函数。

(2)成绩表输入函数的形参可设置为结构体数组，用双重循环依次输入结构体数组元素(学生记录)及结构体每一成员的数据。外循环中输入学号、姓名，嵌入内循环，依次输入课程成绩。

(3)计算平均成绩函数的形参可设置