浙江大学刘加海C语言课件6.doc

个人收集整理 勿做商业用途
第6章 结构体与共用体
u 本章重点
1. 结构体类型的定义及结构体变量的定义。
2. 结构体变量占用的内存空间。
3. 结构体变量对结构体成员的引用方法。
4. 结构体指针变量对结构体变量、结构体数组的应用.
5. 结构体变量作为函数的参数。
6. 链表：堆栈与队列。
7. 共用体的应用。
u 本章难点
1。 正确理解结构体类型与结构体变量的关系.
2。 结构体数组变量对结构体成员的引用，指向结构体变量的指针对结构体成员的不同引用方法。
3. 结构体变量的输入输出。
4. 结构体变量作为函数的参数。
5。 结构体的嵌套,堆栈与队列的应用。

结构体（struct)和共用体（union）是C语言中程序员自定义的数据类型，它是一种常用的数据类型。结构体能把若干不同类型的变量组织到统一的名字之下，也称聚合数据类型，而通过共用体允许把同一片内存定义成多种不同类型的变量。
6.1 结构体的基本概念
以前各章所讨论的数据是单一的数据类型，而在实际应用中所涉及到变量的属性是各种基本数据类型的组合，因而在C语言程序设计中引入了结构体类型的概念.结构体类型是C语言的一种构造数据类型，它用于描述具有多个数据成员且每个数据成员具有不同数据类型的数据对象。例如描写一个学生的基本情况，涉及到学号、姓名、性别、两门课的成绩，分别用int num；char name[8]；char sex；float score［2］表示，要描写这样一个由不同数据类型构成的对象，需要定义一个结构体类型.
1．结构体类型定义
结构体类型的定义格式为：
struct 结构体类型名
{ 类型 数据类型成员名 1；
类型 数据类型成员名 2；
类型 数据类型成员名 3;
………………
类型 数据类型成员名 n；
｝；
例如要描写上述学生的基本情况，需定义的结构体类型为：
struct student
｛
int num ；
char name［8];
char sex；
float score[2］；
｝；
注意
（1）此定义仅仅是结构体类型的定义，它说明了结构体类型的构成情况，C语言并没有为之分配存储空间。
（2)结构体中的每个数据成员称为分量或域，它们并不是变量,在实际应用中还需定义结构变量。
2．结构体变量的定义
定义了结构体类型以后，可以进行结构体变量的定义，其形式为：
struct 结构体类型名 结构体变量表;
结构体的变量也可以是数组或指针。
定义结构体变量时，C语言会为每个变量分配存储空间。结构体变量的定义的方法可以与结构体类型同时定义或分开定义，分开定义是指先定义结构体类型，再定义结构体变量.
定义结构体时，我们实际上声明了一种复杂的数据类型，并未生成任何变量。声明该变量之前，不存在任何此种类型的变量。为了声明student类型的变量stu,可写成如下形式：
struct student stu；
这样就定义了struct student类型的结构体变量stu。student描述结构体类型，称为结构体类型。stu是结构体类型的实例或对象，称为结构体类型变量或结构体变量.
定义了结构体变量（stu）之后，C编译程序自动为结构体变量的所有成员分配足够的内存，如图6.1所示。
num name sex score［0］ score[1]
4Byte
8Byte
1B
8Byte
8Byte
低地址 高地址
图6.1 在Visual C++环境下结构体变量stu占用内存情况
定义结构体的同时可定义一个或多个结构体变量。例如：
struct student
｛
int num ;
char name[8]；
char sex；
float score［2]；
}stu1,stu2，stu3；
定义结构体类型student，同时声明该类型变量stu1，stu2，stu3。每个结构体变量都包含各自的结构体成员的副本.例如,stu1中的sex成员和stu2中的sex成员是彼此独立的,改变stu1中的sex，不会影响stu2中的sex。
如在定义结构体类型与结构体变量时,结构体标记还可省略。例如：
struct
｛
int num ；
char name［8]；
char sex;
float score[2];
};
这里直接按结构体类型说明了结构体变量.
3．结构体变量对结构体成员的引用
通过圆点（。）操作符可访问结构体中的成员。访问一个结构体成员的一般形式为：
结构体变量名。成员名;
它表示结构体变量对具体成员的引用，以下代码把2001赋给结构体变量stu1的成员num：
stu1.num=2001；
在屏幕上显示stu的成员num所含的学号值,应写为：
printf("％d",stu。num）；
同理，从键盘读入的语句是：
scanf(“%d”，＆stu。num）；
4．结构体变量的赋值
（1）结构体变量可在声明时直接进行初始化。初始化数据应放在大括号中，并根据成员变量的声明次序排列,同时数据之间的类型应一致。例如：
struct student stu1={2001，"张华”,’M’，86.00，92.2｝;
或：
struct student
{
int num ；
char name[8]；
char sex;
float score［2］；
｝stu1=｛2001,"张华”,’M',86.00，92。2};
例6。1 结构体变量初始化的实例。
＃include〈stdio.h〉
struct student
{
int num ；
char name[8];
char sex;
float score［2]；
｝stu1={2001,”张华”，’M’,86.00,92。2｝；

void main( )
{
printf（”%d\t％s\t%c\t%f\t%f\n”，stu1。num,stu1.name,stu1.sex，stu1。score[0]，stu1。score［1]）；
}
(2）对结构体变量的数据成员成员进行逐个赋值
例6。2 结构体变量的数据成员进行逐个赋值。
#include〈stdio.h>
＃includename［8];
char sex;
float score[2]；
}stu1；

void main( )
{
stu1.num=2001;
strcpy(stu1。name，”张华”)；
stu1。sex=’M’;
stu1。score[0］=86.00;
stu1.score[1］=92.2；
printf（"％d\t％s\t%c\t％f\t％f\n"，stu1。num,stu1.name，stu1。sex,stu1.score［0］，stu1.score[1］)；
｝
（3）可用单赋值语句把一个结构体变量的全部内容赋给另一个同类结构体变量，而不必逐个成员地多次赋值。
以下程序描述结构体赋值:
例6。3 结构体变量之间的赋值。
#include〈stdio。h>
struct student
{
int num ;
char name［8］；
char sex；
float score［2］;
｝stu1=｛2001,"张华”,’M’,86.00,92。2｝;
；
void main(void）
｛
struct student stu2;
stu2=stu1；
printf("％d\t%s\t%c\t%f\t%f\n”，stu2.num，stu2。name，stu2.sex，stu2。score[0]，stu2。score［1])；
｝
(4）从键盘中逐个读入结构体数据成员。
例6.4从键盘中逐个读入结构体数据成员的实例。
#included\t%s\t%c\t%f\t％f\n"，stu1。num,stu1。name,stu1。sex，stu1.score［0],stu1.score[1］);
}
6。2 结构体数组
6.2。1 结构体数组的定义
结构体的最常见用法就是结构体数组(array of structures）。例如，描述一个班级的学生。用结构体类型中不同类型的成员变量描述学生的具体属性，用数组类型描述拥有相同属性的一个班级的学生，以便使用循环对数组元素进行统一处理，优化算法。
定义结构体数组时,必须先定义结构体，然后再定义该类结构体的数组。例如，定义前述结构体的数组时，可写成：
struct student stu［40］;
或：
struct student
｛
int num ；
char name[8］;
char sex;
float score[2];
}stu[40]；
6。2。2 结构体数组初始化
结构体数组的初始化与其他类型的数组类似.如：
struct student
｛
int num ;
char name[8］；
char sex；
float score[2］；
｝stu［2]={｛4001,”Liu”，’M’,86.5,97。3},
｛4002,”Zheng",'F’,78。4,86。5}}；
下面用一个简单例子来说明结构体数组的定义、初始化及引用.
例6.3 候选人得票统计程序。设有3个候选人,每次输入一个得票候选人的名字,共10张选票，不考虑弃权情况，要求最后输出各人得票结果。
程序定义一个全局结构体类型person,它有二个成员name（姓名）和count（得票数）。结构体数组在main函数中定义并初始化。字符数组l_name代表每次输入的被选人的姓名，在每次输入后，与候选人的名字相比,相同则相应候选人的得票数加1。输入统计结束后，输出3个候选人及相应的得票数。
程序如下：
#include〈stdio。h〉
＃include 〈string。h>
struct person
｛
char name[20];
int count；
｝;
int main(void)
{
int k,t;
char l_name［20];
struct person leader[3］={"AA”,0, ”BBB”，0， "AABBB”，0｝;
for(k=1;k<=10;k++)
{
scanf（”%s",l_name）；
for(t=0；t<3；t++)
if(strcmp（l_name,leader[t]。name）==0) leader[t]。count++;
｝
printf("\nNow the results is:\n”);
for（t=0；t<3；t++）
printf（"%10s：\t％5d”,leader［t].name,leader［t］.count);
printf(”\n"）;
return 0;
}

6.3 结构体变量的指针
指向结构体变量的指针叫结构体指针，它保持着结构体变量的存储首地址。例如：
struct student
{
int num ;
char name［8］；
char sex；
float score[2]；
｝stu1，＊p；
指针变量p是struct student类型的，它只能指向结构体变量的地址，如：
p=&stu1 ；
通过该赋值语句便建立了指向关系。如图6。2所示。
num name sex score[0］ score[1］
2001
张华
‘M’
86。00
92。2

stu1
p

图6。2 结构体变量的指针变量示意图
2．用结构体变量的指针引用结构体变量的成员
利用结构体变量的指针引用所指向的结构体变量的成员可使用下面两种方法：
（1)（＊指针变量名）.成员名
例如图6。2中：(＊p)。num、（＊p）.name、（＊p)。sex、(＊p）。score［0］、（＊p)。score[1］等。
（2）指针变量名—〉成员名
例如在图6.2中:p->num、p->name、p—>sex、p—>score[0]、p-〉score[1］等。
符号—>由减号和大于号拼接而成。
例如有一结构体及结构体变量的定义如下：
struct student
｛
char *name;
int age；
int *m;
char sex［2］;
float salary；
char address［30]；
}stu［3]， ＊ p； p = stu ；
指针变量对成员age、name的引用表示为：p－〉age、p－>name 或（*p）.age、（*p).name
应注意以下式子的含义:
(1）p－>age++和++p－〉age 都使结构体成员age加1。
（2）（++p）－〉age、(——p)－〉age使指针p下移或上移，然后再访问age。
（3）p－〉name为指针p所指的name地址,*（p－〉m)++相当于*p－〉m++，表示先访问m所指地址上的内容,然后此内容再增加1。
例：有数据及结构定义如下：
N0. Name sex age
1010 LiLin M 18
10102 ZhangFun M 19
10104 WangMin F 20
struct student
{ int num;
char name[20］;
char sex ；
int age；
}stu［3］,＊p；
p=stu;
在TC中,p+1意味着向下移25个字节，而在VC中此结构体占用空间为29个字节,p+1意味着向下移29个字节。
（++p）－>num指转向p的下一结构变量的起始地址，然后取得成员num的值。
（p++）－〉num先得到p－〉num的值，然后p指向下一结构变量的起始地址。
（4）p只能指向一个结构体类型数据，即地址类型应相同。
p=malloc(sizeof（struct student）)是错的。应该把申请到的地址强制转换成结构类型，所以应写成：p=（struct student ＊)malloc(sizeof（struct student)）
例6。5 请输入学生学号和3门课成绩，学号为0时表示数据输入结束，程序设计如下：
#include 〈stdio。h〉
#include 〈stdlib.h〉
struct student
{
int num；
float score［3］;
｝；
void main( ）
{
int i=0，n=0；
struct student ＊ptr[200]；
printf(”请输入学生学号和3门课成绩,学号为0表示数据输入结束\n"）;
do
｛ptr［i］=(struct student *）malloc(sizeof(struct student））;
scanf(”％d%f%f%f”，＆ptr[i]->num，＆ptr［i]-〉score［0］，&ptr［i]—>score［1]，
＆ptr［i］—〉score[2]）；
if（ptr[i］—>num==0）break;
i++；
n++;
｝while(1)；
free(ptr[i]）；

for（i=0；iscore［0］,
ptr[i］->score[1]， ptr［i］—>score[2])；
｝
6.4 结构体变量作为函数的参数
结构体变量可以作为函数的参数.
6.4。1 向函数传递结构体变量
结构体变量用作函数的参数时，把结构体变量的所有成员传递给被调用函数。此时实际参数为结构体变量的地址或指向结构体变量的指针，形式参数最好为结构体类型的指针变量。例如有一结构体变量定义：
struct student *p ， stu , s[10]；
p=&stu ;或p=s;
函数调用语句为：
函数名（p）；或: 函数名（＆stu）； 或：函数名(s)；
函数定义为：
返回值类型 函数名(struct student *p)
｛ ……
}
通过以下简单程序，可以了解结构体变量作为函数参数的用法。
例6.6 结构体变量作为函数参数的例子。
＃include
struct pen
｛
int i;
double j；
｝;
void count(struct pen *p）
｛
double x；
x=p->i
x＊=p-〉j；
printf（”x=％f\n”，x）；
｝
void main（ ）
｛ static struct pen d={3，1。23};
count(&d）；
}
例6.7 有4个学生,包括学号、姓名、成绩。要求找出成绩最高者的姓名和成绩。
#include〈stdio.h>
struct student
{ int num ;
char name[20];
int score;
}；
void input(struct student *stu )
{ int i；
for（i=0;i〈4；i++)
scanf"%d %s％d”,＆stu[i]。num， ＆stu［i].name,＆stu[i］.score)；
｝
void findmax(struct student ＊stu）
｛ struct student *p;
int i，temp=0；
float max;
for（max=stu［0]。score,i=0；i〈4；i++）
if（stu［i].score〉max）
｛ max=stu[i］.score;temp=i;｝
p=stu+temp;
printf（”\nThe maximum score：\n")；
printf（"No:％d name:%s score %4d\n”,p—>num， p-〉name,p-〉score）；
｝
void main（ ）
{
struct student stu[4],＊p=stu;
input（stu);
findmax(p）；
}
程序执行时调用函数input（stu）及findmax(p)，函数的参数为结构体变量的地址及指向结构体变量的指针，程序在执行时如输入：
101 Lu 91
102 Tan 88
103 Liu 98
104 Fun 87
则程序输出为:
The maximum score:
No：103 name：Liu score 98
65 结构体的嵌套
结构体的成员可以是简单的变量,例如:int、float等，也可以是复合类型.若结构体的成员包括结构体，即结构体中又有结构体，则称结构体的嵌套，或嵌套结构体（nested structure)。在下面的例子中，结构体date内嵌在结构体student中：
#include
struct date
{
int year；
int month;
int day；
｝;
struct student
{
char num[10］；
char name［20］；
char sex;
struct date birthday;
float score;
char addr［40］；
｝;
void main()
{
struct student comp_stu ={”78202"，”Dennis”,’M’, ｛1986，4，20｝, 576。00，”123 BinHong Road”}；
printf(”\nTheBirthdayof%sis:%d—%d-％d”,comp_stu.name，
comp_stu.birthday。year，comp_stu.birthday。month，comp_stu。birthday。day)；
}
6.6 共用体
共用体是另一种构造型数据类型,是多种变量共享的一片内存。直观地讲，共用体可以把所在存储单元中相同的数据部分当作不同的数据类型来处理，或用不同的变量名来引用相同的数据部分。共用体常用于需要频繁进行类型转换的场合，及压缩数据字节或程序移植等方面。
共用体类型的定义、变量的说明、成员的引用与结构体类型十分相似。共用体变量和结构体变量的本质差别在于两者的存储方式不同:结构体的成员变量存储时各占不同起始地址的存储单元，在内存中呈连续分配,所占内存为各成员所占内存的总和；而共用体的成员变量存储时共用同一起始地址的存储单元，所占内存为最大内存需求的成员所占内存。如图6。3所示。
ch

高字节
低字节
t
图6.3 共用体
1．共用体和共用体变量
共用体的定义类似于结构体的定义，一般形式如下:
union 共用体类型名
｛
共用体成员表列；
}共用体变量名表列；
其中，共用体类型名或共用体变量名表列之一可省略，但两者必留其一.例如，在共用体中有一整型成员al和字符型成员ch,共用体变量reg，以下三种定义方式都可.
（1)定义共用体类型p_type的同时声明共用体变量reg
union p_type{
int al；
char ch；
}reg
(2）省略共用体类型名而直接声明共用体变量reg
union
｛
int al;
char ch;
}reg；
(3）先定义共用体类型p_type，再声明共用体变量reg
union p_type
｛
int al;
char ch;
};
union p_type reg；
2．共用体变量的引用方式
在通常使用中，只引用共用体的成员变量，引用方式与结构体变量的引用类似.可通过变量名直接引用，也可通过指向共用体类型的指针变量来间接引用。引用的操作符为‘。’、‘－〉’。例如:
union p_type reg，＊pu； 　 /* 声明了共用体变量reg和指向共用体的指针变量pu */
pu=＆cvnt； 　　　　　　　 /* 使共用体指针变量pu指向共用体变量reg ＊/
reg。al 和pu－〉al 　　　　 /*对成员al用共用体变量直接引用和指针的间接引用 ＊/
reg.ch 和pu－>ch 　　 /*对成员ch用共用体变量直接引用和指针的间接引用*/
3．共用体变量的存储方式举例
例6.9 分析程序的的执行结果
union data
{
int a；
char b;
}x;
void main（ ）
｛
x.a=16384;
x.b=’a’;
printf("％d\n"，x。a）；
}

高位
低位
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0

分析：成员a占用2字节，成员b占用1字节。当给x。a赋值后，在内存空间存储情况如下所示.

当给x.b赋值时,由于x。b与x.a在低字节共用一个存储单元,赋值后的存储情况如下所示.
0
1
0
0
0
0
0
0
0
1
1
0
0
0
0
1
因而当最后输出x.a时的值为16481。答案：16481。
例6。10 数组的第0个元素在低位，以下程序输出的是（ ）.
(A) 39 （B）9 (C）38 （D）0
＃includei［0]=0x39; s—>i［1]=0x38；
printf("％x\n"，s—〉c［0]）;
｝
分析：存储空间的结构示意图如下:
r。c［3］ r.c[2］ r.c[1］ r.c［0］
00000000
00111000
00000000
00111001
r。i［1](0x38） r.i［0］（0x39）
s－>c［0］即r。c［0］,因而其值为16进制的39，答案为A.
4．共用体与结构的嵌套使用
共用体与结构的可以嵌套使用。
例6。11 下列程序的输出结果为（　　）。
＃include〈stdio。h〉
void main（ )
{
union EXAMPLE
{ struct
｛ int x；
int y;
} in ;
int a ;
int b ；
}e;
e。a = 1；
e.b = 2 ；
e。in .x = e。a ＊ e。b ；
e.in 。y = e。a + e。b ;
printf("％d ％d\n" , e.in。x ，e。in。y ） ;
}
分析：如图所示共用体有3个成员in、a、b，以占用最大空间的成员in为准，在Visual C++环境中占用内存空间为8字节，其中e。a、e.b、e.in.x占用同一个内存空间，当执行语句e。a=1;时，e。b、e.in.x的值都为1，当执行语句e。a=2;时,e。b、e.in.x的值都为2，e。a＊e.b的值赋给e.in.x，e.in.x的值为4，而此时e.a、e。b的值都为4，所以执行语句e.in .y = e。a + e.b；后,e.in。y的值为8.
e.in.x
e。a
e。b
e.in。y
低位 高位
图6。4 共用体EXAMPLE的空间占用情况

程序输出为：4，8。
5．程序举例
通过一个简单程序，更清楚共用体类型的使用。
例6。13 两类实体大致属性相同,个别属性不同。现把两类实体（如学生和教师)放置于一个表格中，表格可通过结构体数组来实现,如表6.1所示。要求输入人员数据，然后再输出(简化考虑，测试数据可采用一类实体一例）。
若‘number’含‘s’则第四项为class，即John为comput001班的学生；若‘number’含‘t’则第四项为department,即Dennis为comput系的教师。Class和department两个属性对于任何一个实体而言,只能拥有一个，因此它们可通过共用体共用一段内存单元。number属性的值约束暂时简化为s或t开头,除此之外为非法。
表6。1 两类实体
number
Name
sex
Class(班）/Department(系)
s02001
John
m
comp001
t0007
Dennis
m
comput
程序如下：
＃include〈stdio。h>
＃define N 2
struct
{
char num[8］；
char name[20］；
char sex；
union
｛
char class1[8]；
char department[10]；
｝dep;
｝memb［N];

int main(void）
{
int n；
for（n=0;nb[n］.num［0］=='s’)
scanf(”%s”,memb[n].dep。class1）;
else if(memb[n]。num［0］=='t')
scanf("%s”，memb[n]。dep。department）；
else
printf("input error！”)；
｝
printf（”\n”);
for(n=0;n〈N;n++）
{
if(memb[n]。num［0]=='s’）
printf（”％-8s％—10s％-3c％—10s”，memb［n]。num， memb[n］.name， memb［n].sex，
memb［n]。dep。class1）;
else
printf（"％—8s%-10s％—3c%-10s",memb［n]。num， memb[n].name， memb［n]。sex，
memb［n］。dep。department)；
}
return 0；
}
在该例程中,整个数据模型由结构体数组memb实现，各属性由结构体成员实现，其中两类实体非共性部分由共用体实现,这样简化了算法,提高了运行效率。
6.7 动态链表的基本操作
在这一节将学习如何建立动态数据结构。什么叫动态数据结构呢？动态数据结构是指在程序的运行时,根据程序的数据存储的需要而扩充或缩小数据结点.它与数组不同，数组存储固定数目元素的存储空间，而动态数据是在程序的执行时，根据程序的数据的存储需要而扩充或缩小数据结点。
6．7．1 动态链表的概念
在实际应用中,一个程序在每次运行时要处理数据的数目通常并不确定，根据需要随时开辟存储单元,不再需要时随时释放，就能比较合理地使用存储空间。但各次动态分配的存储单元,其地址不可能是连续的，在这种链表的每个结点中，除了要有存放数据本身的数据域外,至少还需要有一个指针域,用它来存放下一个结点元素的地址，以便通过这些指针把各结点连接起来，从而形成如图6．4所示的链表.在这种动态链表中，每个结点元素没有自己的名字,只能靠指针维系结点元素之间的接续关系。一旦某个元素的指针"断开”,后续元素就再也无法找寻。
head
头指针 i

next NULL
头结点
图6．4单向链表

每个链表都用一个”头指针"来指向链表的开始，如上图中的head。在head中存放了链表第一个结点的地址，链表最后一个结点的指针域不再指向其它结点，就置成'\0’( NULL）值，标志着链表的结束。上述链表的每个结点只有一个指针域,每个指针域存放着下一个结点的地址,因此，这种链表只能从当前结点找到后继结点，故称为”单向链表"。为构成如图中所示的单向链表,假定结构体结点的类型定义如下：
struct node
｛
int i；
struct node ＊next;
｝；
其中一个成员为整型数，另一个是指向自身结构体的指针类型的成员。
单向链表通常可分为队与堆栈，下面将以图6.4所示的链表结构体为例，介绍与单向链表有关的基本算法，包括链表的建立、结点数据域的输出、结点的插入和删除。在单向链表的建立及操作中需要用到的常函数：
① void ＊malloc(unsigned size )
在具体应用中为：
p=(struct node ＊)malloc（sizeof(struct node)）
② void free（void ＊ptr）
关于这些函数更为详细的问题,可查阅C语言函数库.
6．7．2 堆栈的建立
所谓堆栈是指一组能存储和取出数据的暂时存储单元,数据从堆栈中的取出过程与入栈过程是以相反的次序进行的，通常称为“后进先出"堆栈.
（a）链表未建立时：结点数为0，头指针为空。即：
n=0,head=NULL;

head= NULL；
∧

（b）产生第一个存储单元,读入数据；
p

next

（c）将第一个数据读入，并将数据存入第一个存储单元，即p->i=x1 ; 将第一个存储单元链入链表p—>next=head ；head=p；
head p
x1
NULL

（d）产生第二个存储单元,读入数据并赋值,p—〉i=x2 ;将第二个数据连到链表前面，完成语句p—〉next=head;head=p；读入第三个数据。
p head head p x2 x1
x2 x1
next NULL NULL
（a)第二个结点连入前