结构体与共用体课件

结构体与共用体

11.1结构体类型定义10.1

结构体类型的定义与变量说明

我们所处理的数据并非总是一个简单的整型、实型或字符型数据。如我们要处理的对象是学生，不可能孤立地考虑学生的成绩，而割裂学生成绩与学生其它属性之间的内在联系。学生的成绩、姓名、学号等是一组逻辑相关的数据，孤立地考虑这些属性，将导致操作的不便或逻辑错误。

解决以上问题的方法就是引入结构体类型，将逻辑相关的数据有机组合在一起，称之为结构体。一.结构体类型的定义struct

结构体类型名

{

数据成员列表；

}；结构体类型的一般定义形式为：定义结构体类型的标识符用户命名的标识符结构体类型定义的结束符10.1

结构体类型定义

例10-1，一个学生的数据信息包含有学号、姓名、性别、年龄、成绩、住址，可将其定义为一个结构体类型：

structstudent{longID；/*学生学号*/charname[10]；/*学生姓名*/charsex；/*学生性别*/

intage；/*学生年龄*/floatscore；/*学生成绩*/charaddr[30]；/*学生住址*/}；结构体类型定义仅仅是定义了一个特定的复合数据类型，描述了这一类型数据的公共属性，为了在程序中使用该结构体类型的具体对象，还需要说明这种类型的变量。10.1

结构体类型定义二.结构体类型变量的定义结构体类型变量定义的一般形式：struct

结构体类型名结构体变量名；1.先定义结构体类型再定义结构体变量structstudentstu1，stu2；ID(4字节)stu1namesex(1字节)age(2字节)score(4字节)addr…………共10个字节共30个字节IDstu2……图11-1结构体变量的存储结构共51个字节10.1

结构体类型定义2.定义结构体类型的同时定义变量structstudent{longID；

charname[10]；

charsex；

intage；

floatscore；

charaddr[30]；}stu1，stu2；

10.1

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

{longID；

charname[10]；

charsex；

intage；

floatscore；

charaddr[30]；}stu1，stu2；结构体变量的三种形式可以任意选用。但在不同函数中定义说明同一类型的结构体变量时，用第三种方法不太方便，一般用第一种和第二种定义形式。10.1

结构体类型定义三.结构体类型的嵌套结构体类型的嵌套是指结构体的成员是一个结构体类型若定义学生信息为结构体，其成员分别为：学号、姓名、性别、出生年月、成绩。其中出生年月包括出生的年、月、日三个数据，这些数据可以用另一个结构体类型表示。例如，定义student结构体。（1）先定义date结构体：structdate{intyear;

intmonth;

intday；

}；（2）再定义student结构体：structstudent{longID；

charname[10]；

charsex；

structdatebirthday；

floatscore；}；10.1

结构体类型定义10.2结构体类型变量的引用与初始化一.结构体类型变量的引用

对一个结构体类型变量的引用是通过引用它的每一个成员来实现的。引用运算符有两个：.->其中，“->”为结构体指针运算符，引用一个结构体变量的成员有两种方法：结构体变量名、指向结构体的指针变量结构体成员运算符“.”在所有运算符中优先级最高.结构体变量不能作为一个整体进行输入输出,只能对其成员分别输出。

10.2

结构体变量引用用结构体变量名引用其成员的一般形式： 结构体变量名.成员名其中，“.”称为结构体成员运算符，将结构体变量名与成员名连接起来，它具有最高级别的优先级。结构体变量可以单独引用其成员，也可作为一个整体引用，还可以引用结构体变量或成员的地址。1.单独引用结构体变量的成员structclock{inthour,minute,second；}；structdate{intyear,month,day；

structclocktime；

}；

structdatetoday；

today.year=2004；

today.month=4；

today.day=12；

today.time.hour=16；

today.time.minute=47；

today.time.second=15；

10.2

结构体变量引用2.结构体变量作为一个整体引用

结构体变量不可以作为整体进行输入输出，但可以作为函数的参数或返回值而被整体引用，也可以将一个结构体变量作为一个整体赋给另一个具有相同类型的结构体变量。structdate

{

intyear，month，day；}；structdatenextday(day)

structdateday；

{structdatetemp；

... return(temp)；

}函数nextday的形参day为结构体类型，它将整体接受同类型实参的值10.2

结构体变量引用3.引用结构体变量的地址或成员的地址引用结构体变量的成员地址，要在结构体成员引用的前面再加“&”运算符.结构体变量a的成员t赋值：scanf(”%d”，&a.t)；引用结构体变量的地址,在结构体变量的前面直接加“&”:printf("%X"，&a)；

10.2

结构体变量引用二.结构体类型变量的初始化结构体变量可以在说明的同时初始化。structclock{inthour，minute，second；}；

structdate{intyear，month，day；

structclocktime；

}；

structdatetoday={2004，4，12，17，4，30}；structdatetoday={2004，4，12，{17，4，30}}；

10.2

结构体变量引用10.3

结构体类型与数组一.结构体数组的定义1.先定义结构体类型，后定义结构体数组structstudentstudents[100]；2.结构体数组与结构体类型同时定义structstudent{longID；

charname[10]；

intage；

floatscore[3]；

}students[100]；3.不定义结构体类型名，直接定义结构体数组struct

{longID；

charname[10]；

intage；

floatscore[3]；

}students[100]；

10.3

结构体与数组二.结构体数组的初始化与结构体数组元素的引用1.结构体数组的初始化structperson {longID；

charname[10]；

charsex；

structdatebirthdate；

chardepartment[30]；

floatsalary；

charaddress[30]；

}employee[3]={{1001，”张山”，’M’，1990，3，5，”计算中心”，545，”长沙”}，

{1002，”李红”，’F’，1989，10，1，”信息学院”，643，”武汉”}，

{1003，”王武”，’M’，1987，4，15，”人事处”，745，”广州”}}；

10.3

结构体与数组图11-2结构体数组的存储结构employee[1]1002ID（4字节）"李红"name（10字节）10sex（1字节）1birthdate(date类型，6字节)"信息学院"salary（4字节）643address（30个字节）'F'1989"武汉"department（30个字节）共85个字节employee[2]1003ID（4字节）"王武"name（10字节）4sex（1字节）15birthdate(date类型，6字节)"人事处"salary（4字节）745address（30个字节）'M'1987"广州"department（30个字节）共85个字节employee[0]1001ID（4字节）"张山"name（10字节）3sex（1字节）5birthdate(date类型，6字节)"计算中心"salary（4字节）545address（30个字节）'M'1990"长沙"department（30个字节）共85个字节10.3

结构体与数组2.结构体数组元素的引用

一个结构体数组元素相当于一个结构体变量，元素成员的访问使用数组元素的下标来实现。 结构体数组元素成员的访问形式：结构体数组名[元素下标].结构体成员名

可以将一个结构体数组元素整体赋给同一结构体数组的另一个元素，或赋给同一结构体类型变量。employee[0].ID=1001;employee[1]=employee[2]；与结构体变量一样，结构体数组元素也不能作为一个整体进行输入输出，只能以单个成员的形式实现。

10.3

结构体与数组10.4

结构体类型与指针

当结构体很大时，结构体变量的整体赋值效率是相当低的。

结构体变量名就是分配给该变量的内存空间的起始地址，我们可以利用指向结构体变量的指针，实现在不同程序段对同一内存区域的结构体变量的数据成员执行各种操作。10.4

结构体与指针一.指向结构体变量的指针

指向结构体变量的指针也称为结构体指针，它保存了结构体变量的存储首地址。

1.结构体指针的定义形式：

struct

结构体类型名*指针变量名；structstudentstu，*p；p=&stu；10.4

结构体与指针2.结构体变量成员的三种访问方法（1）结构体变量.成员名

stu.ID（2）(*结构体指针).成员名

(*p).ID

（3）结构体指针->成员名

p->ID

结构体指针->结构体成员结构体指针运算符“->”10.4

结构体与指针二.指向结构体数组的指针structperson{charname[10]；

intage；

}；

structperson*p，s，boy[3]={”Zhang”， 18，”Wang”，20，”Li”，17}； 对于已定义的结构体数组，若用一个变量来存放该结构体数组在内存中的首地址，则该变量为指向结构体数组的指针变量。例如，定义结构体类型person和结构体指针变量p。p=boy；定义了结构体数组boy和结构体指针变量p，且p指向数组boy的首地址。

10.4

结构体与指针

将结构体变量与结构体数组的首地址赋给结构体指针的不同之处：

p=&s ；

/*s为结构体变量*/ p=boy；

/*boy为结构体数组，boy为数组的首地址*/

结构体指针也可以指向结构体数组的一个元素，这时结构体指针变量的值是该结构数组元素的首地址。注意：

若要将结构体成员的地址赋给结构体指针p，则必须使用强制类型转换操作，转换形式为：p=(struct

结构体类型名*)&结构体数组元素.成员名

10.4

结构体与指针10.5

链表C语言中，变量存储空间的分配分为静态分配和动态分配。静态存储分配：先在程序说明部分进行变量的说明，然后在程序编译时分配适当的存储单元。这些存储单元一经分配，在它的生存期内是固定不变的。动态存储分配：在程序执行期间，通过“申请”分配指定的存储空间来存储数据，当有闲置不用的存储空间时，又可以随时将其释放。

10.5

链表ANSIC标准为动态分配系统定义了四个函数：malloc、calloc、free和realloc。

用户可以通过调用C语言的标准库函数来实现动态存储分配，从而得到或释放指定数目的内存空间。这些函数在头文件alloc.h及stdlib.h中声明。

10.5

链表一.链表概述数组顺序存储结构随机存取逻辑关系上相邻的两个元素在物理位置上也相邻1.数组的致命弱点：(1)在对数组进行插入或删除操作时，需移动大量数组元素(2)在数组的长度是固定的而且必须预先定义，数组的长度难以缩放，对长度变化较大的数据对象要预先按最大空间分配，使存储空间不能得到充分利用10.5

链表2.链表存储结构是一种动态数据结构特点:(1)它包含的数据对象的个数及其相互关系可以按需要改变.(2)存储空间是程序根据需要在程序运行过程中向系统申请获得.(3)不要求逻辑上相邻的元素在物理位置上也相邻.(4)没有顺序存储结构所具有的弱点.10.5

链表图11-3单向链表的逻辑状态QianSunLiZhouWuWangHead7131432537以上链表结构中只有一个方向的指针，因此又称为单链表，简称为链表。一般地，用户可根据链表存放的信息如存放学生信息就称为学生链表，存放职工信息就称为职工链表。10.5

链表

在单链表，通常称它的数据元素为结点，每个结点都是一个结构体，至少包括两个成员：存储数据元素信息的成员称为数据域；存储直接后继结点存储位置的成员称为指针域.

显然，链表结点的指针域存放的地址类型与它自身的类型是相同的。

这就是C语言中较为特殊的递归结构体或自引用结构体，这种结构体具指向自身结构体的指针，一般在实现链表、树等数据结构时会用到这种特殊的结构体。

10.5

链表每个链表都有一个“头指针”head，整个链表的访问必须从头指针开始进行，头指针指示链表中的第一个结点的存储位置，习惯上将“头指针”head指示的链表简称为链表head，下同。同时，由于最后一个数据元素没有直接后继结点，则链表中最后一个结点的指针为“空”（NULL，即空地址）。表11-1链表的存储地址与指针域的关系存储地址数据域指针域head

71Li437Qian1313Sun125Wu3737WangNULL43Zhou2510.5

链表

数据元素之间的逻辑关系是由结点中的指针指示的，逻辑上相邻的两个数据元素其存储的物理位置不要求紧邻，即链表中的数据元素在内存中不是顺序存放的，要访问其数据元素不能像数组一样按下标去查找。要找一个元素，必须先找到上一个元素，根据上一个元素的指针域才能找到下一个元素。

因此，链表的数据元素访问必须从头指针开始，逐个访问链表的每个结点，直到元素的指针域为空为止。10.5

链表

要使用链表，首先应定义结点的类型，再定义相应的结构体变量。例如，前面链表中结点的结构类型可以定义为：

structstudent{charname[10]；

structstudent*next；

}；其中，next为指针变量，其类型为结构体类型student，它可存储一个student结构体类型变量的地址，即实现链表中指向下一个结点的指针域。

这是一个递归定义，它在结构体student的定义未完成时又引用它定义其它的变量（指针变量）。

10.5

链表

引入链表后，用户就可以根据需要在程序的运行过程中动态分配存储空间。动态存储分配需要利用以下C语言库函数。(1)函数malloc

函数功能：函数原型：void*malloc(unsigned

intsize)；

在内存的动态存储区中分配一个长度为size的连续存储空间。其中，形参size为无符号整数，是函数malloc要求分配存储空间的字节个数。函数返回值为一个指针，它指向所分配存储空间的起始地址。若函数返回值为0，则表示未能成功申请到内存空间。函数类型为void，表示返回的指针不指向任何具体的类型.10.5

链表int*p； long*lp；p=(int*)malloc(8)；lp=(long*)malloc(12)；head=(structstudent*)malloc(sizeof(struct student))；例如：malloc(8)；

通过函数malloc向系统申请8个字节的内存空间，其起始地址通过函数值返回。若要求用一个指针变量（具有某种类型）指向这个起始地址，则需要显式进行类型转换。例如：10.5

链表(2)函数calloc

函数原型：voidcalloc(unsigned

intn，unsignedint size)；函数功能：

在内存的动态存储区域中分配n个长度为size的连续存储空间。函数的返回值为分配域的起始地址；如果分配不成功，则返回值为0。例如：int*p；p=（int*）calloc(3，8)；分配3个8字节的的连续存储空间，并将其起始地址赋给整型指针p。10.5

链表(3)函数free函数原型：voidfree(void*ptr)；函数功能：

释放由指针变量ptr为所指示的内存区域。其中，ptr一个指针变量，指向最近一次调用函数malloc或calloc时所分配的连续存储空间的首地址。通过函数free将已分配的内存区域交还系统，使系统可以重新对其进行分配。例如：long*p；p=(long*)malloc(8)；...free(p)；

10.5

链表

将ptr所指向的存储空间重新分配大小为size的存储空间，并返回重新分配后的存储空间的首地址。其中，ptr指向原先用函数malloc分配的内存区域的起始地址。函数realloc将ptr指向的存储区的大小改为size个字节，可以使原先分配的存储区域扩大或缩小。其函数返回值是一个指针，即为新的存储区域的首地址。(4)函数realloc函数原型：void*realloc(void*ptr，unsignedintsize)；函数功能：注意：新的首地址不一定与原先定义的首地址相同，因为为了增加空间，存储区会进行必要的移动。10.5

链表二.建立链表1.尾插法建立单链表所谓尾插法，是指新插入的结点总是放在链表尾部。一般地，链表的建立过程是在一个空链表的基础上逐步插入新的结点而成的。所谓空链表，即链表没有一个结点，这时链表的头指针为空。

链表与数组不同，不是程序定义时就可建立，而是在程序运行过程中一个结点一个结点地建立起来的，并在结点之间形式链接关系。

建立单向链表的方法有尾插法与头插法两种。

因此，链表的建立是一个动态存储空间分配和形成链接关系的过程。

10.5

链表用尾插法建立链表的过程如下：（1）建立一个空链表，即head=NULL；这里head为头指针，它指向链表的第一个结点。为了操作的方便，还定义一个指向链表尾结点的指针last，显然last的初始值也为空（即NULL）。如图10-5（a）所示。为了描述的方便，将“指针head所指向的结点”简称为“head结点”，将“指针p所指向的结点”简称为“p结点”，下同。（2）生成新结点p，对新结点p的数据域和指针域赋值。由于新插入的结点总是尾结点，则它的后继为空，故“p->next=NULL；”。如图10-5（b）所示。（3）将p结点插入到链表：如果链表为空（即head=NUUL），则p结点为头结点，也是尾结点，即：

head=p；last=p；如图10-5（c）所示。否则应将p结点插入到last结点之后，并使p结点成为当前的尾结点，即：

last->next=p；last=p；如图10-5（d）所示。（4）重复（2）~（3），继续插入新结点直到结束。10.5

链表所谓头插法，是指新插入的结点总是作为链表的第一个结点。用头插法建立链表的过程如下：（1）建立一个空链表，即head=NULL；与尾插法不同的是这里不需定义尾指针。（2）生成新结点p，对新结点p的数据域赋值。由于新插入的结点成为头结点，其指针域不必赋值。（3）将p结点插入到链表： 先p结点的后继为当前的头结点，然后使p结点成为当前的头结点，即：

p->next=head；head=p；（4）重复（2）~（3），继续插入新结点直到结束。2.头插法建立单链表10.5

链表三.链表的访问1.输出链表结点将链表中各结点的数据依次输出。输出链表结点的操作过程如下：（1）取得链表头结点的地址

head；（2）用一个跟踪指针p指向头结点，即p=head；（3）输出p所指结点的成员值；（4）移动指针p，使它指向它的后继结点。即p=p->next；（5）重复（3）（4），直到指针p为空。10.5

链表2.统计链表结点的个数一般情况下，各个单链表中结点个数是随机的，要想知道表中结点数目，必须从表头开始访问到表尾，逐个统计出结点数目。3.查找链表的某个结点在链表上查找符合某个条件的结点，也必须从链表头开始访问链表。（1）查找链表中第n个结点，若找到，则返回它的地址，否则返回空指针。（2）在链表中查找指定值的结点，若找到，则返回它的地址，否则返回空指针。10.5

链表四.链表的插入操作

所谓链表的插入操作就是将一个结点插入到一个已有链表的某个位置上。1.在第n个结点之后插入1个新结点(x)（1）输入n和x（一般在调用函数中处理）；（2）申请一个新结点，q指针指向新结点，q的值为x（一般在调用函数中处理）；（3）p=head，r=NULL，r为p的前驱结点，i=0；（4）i++，r=p，p=p->next，p结点往前移动一个结点；（5）若i<n且p!=NULL，则重复（4）；（6）若i==0，则链表为空，没有结点，q结点作为链表的第1个结点插入：

q->next=head，head=q；（7）若i<n且p==NULL，则链表不足n个，将q结点插入到链表尾r结点之后：

r->next=q，q->next=NULL；（8）否则，将q结点插入到第n个结点之后，即插入到r结点与p结点之间：

r->next=q，q->next=p；（9）返回链表头head。10.5

链表2.指定值的结点之后插入一个新结点（1）q指针指向新结点；（2）p=head，r指向p结点的前一个结点；（3）若head==NULL，则链表为空，没有结点，q结点作为链表的第1个结点插入：

head=q；q->next=NULL；（4）r=p，p=p->next，p、r结点往前移动1个结点；（5）若p->score!=x且p!=NULL，则重复（4）；（6）若p==NULL，则未找到score为x的结点，将q结点插入到链表尾r结点之后：

r->next=q，q->next=NULL；（7）否则，将q结点插入到第n个结点之后，即插入到r结点与p结点之间：q->next=p->next，p->next=q；（8）返回链表头指针head。10.5

链表五.链表的删除操作

从一个链表中删除一个结点，并不是真正从内存中把它抹掉，而是把它从链表中分离出来，即改变链表的链接关系。1．删除第n个结点将以head为头的链表中的第n个结点从链表中移出，其后继的结点往前移，使之仍为一个链表，只是结点数目比原来少1。

10.5

链表例:编写函数，删除学生链表head中的第n个结点。分析：（1）p=head，q指针指向p所指结点的前1个结点；（2）i为访问过的结点数目；（3）i++，q=p，p=p->next，p、q移动1个结点；（4）若p!=NULL且i<n-1，重复（3）（5）若n==1，则删除第1个结点，将下一个结点作为链表头结点：head=head->next；（6）若head==NULL，链表为空，不能删除；（7）若p==NULL，第n个结点不存在，不能删除；（8）找到第n个结点，删除p结点：

q->next=p->next；