3．4 结构类型及链表处理
3．4．1 结构变量定义及使用
C++提供了结构这一聚合数据类型，它是将具有一定联系的一组数据类型相同或不同的数据组织起来，进行统一管理，并赋予一个统一的名字。
结构可以是由不同数据类型的数据成员组成，面向对象的结构类型还可以包含函数说明和定义，从而可以定义一个类，用标识符struct 定义的类与用标识符class定义的类，其主要区别在于其成员的缺省访问属性不同。组成结构的每个数据称为该结构的成员。在使用结构之前，必须对该结构进行定义，以告诉编译器该结构的成员个数及其数据类型。本栉首先介绍非面向对象的结构，它属于一种聚合数据类型。
结构定义的语法形式如下：
struct variable
{
data_type1 name1;
data_type2 name2;
.
.
.
data_typen namen;
};
注意：结构的定义是一条语句，在其结尾处需要加一个语句结束符“；”。
例如：下面是一个通信录记录结构定义的一个例子：
struct addr
{
char name[30];
char street[40];
char city[20];
char state[2];
unsigned long zip;
};
在对结构进行定义后，就可以用来指明使用该结构的具体对象，这就称为结构的实例化，其一般形式如下：
struct variable name; 或 variable name;（常用形式）
其中struct是结构的标识符，variable是已经定义过的结构名称，name是结构变量名称。
在定义了结构的变量之后，可以用操作符“．”来访问结构中的成员数据。访问结构数据成员的形式如下所示：
name.member;//name是结构变量的名字，member是其某一成员数据的变量名。
3．4．2 结构数组最常用的结构对象是结构数组，而结构数组最主要的用途便是构造链表。
为了定义一个结构数组，必须首先定义一个结构类型，然后利用该结构类型来说明一个数组。为了访问数组中某一元素的某成员数据，必须指明该元素在数组中的下标及该成员数据的名称。如以下是使用上一节中定义过的通信记录结构定义结构数组并访问其成员数据的例子：
addr binfo[100];
binfo[0].zip=1234;
3．4．3 结构指针结构作为一种聚合数据类型，其变量是在内存中进行存放的，也有一定的内存地址，因而也就存在结构变量指针。结构指针可以用来指向任何统一结构类型的结构变量，可以通过结构指针来访问结构的成员数据。
定义结构指针的一般语法结构如下：
struct variable *name; 或 variable *name;
同样，对结构指针必须初始化或赋值，使其指向结构变量。对结构指针进行赋值时，需要将一个结构变量的地址赋给它，即对结构变量进行取址操作或利用其他结构指针对某个类型匹配的结构指针进行赋值。利用结构指针来对结构的成员数据进行访问的一般形式如下所示：
structure_variable->member_name;
其中structure_variable是结构变量的名字，而member_name是成员数据的变量名。
[例3．6] 使用结构指针的例子。(EX3_6.CPP)
3．4．4 结构的嵌套结构的嵌套指的是结构的成员数据中包含其他结构，形成复杂的数据结构在C++中，结构可以作为其他结构的成员数据。只要在编译器或计算机支持的范围内，结构可以多级地嵌套。
注意：程序中出现的所有结构，在结构中都必须的定义。
对于结构嵌套的情况，要访问作为某一结构的成员的结构的成员数据，需要进行多级逐层引用。
[例3．7] 结构嵌套的应用。EX3_7.CPP
3．4．5 链表类数据处理链表是计算机数据处理中常用的一种数据结构。在链表中，各元素具有相似的结构，且各元素之间依次链接形成民链状的表单结构，且链表的线性顺序连续是逻辑上的，而不是依赖分配连续存储空间来维持的，因而在物理结构上是灵活的，属于线性动态结构。结构是实现链表类数据处理的强有力的工具，有很多衫的链表结构都是用结构构造出来的。
为了实现通过链表结构中某一元素访问其他元素，即结构变量提供可以指向其他结构变量的机制，需要使用递归结构类型。在递归结构类型中，结构的成员数据中包含指向该结构类型本身的结构指针，利用该指针，可以实现对同类型的结构变量的访问。
例如，一个集邮爱好者想为他的收藏品建立一个卡片式档案。每张卡片记录一张邮票的情况，包括邮票名称，尺寸、发行日期、描述信息等内容。以这些要包含的内容作为成员函数，构成一个结构类型，每张卡片作为一个结构变量来处理，但这些卡片如何组织起来需要好好考虑一下。如建立结构数组或链表结构，比较而言，链表结构在处理记录增加、删除等方面要好于数组结构。因而选用链表结构。
先根据卡片的内容定义一个结构类型，该结构类型应该是弟归结构，以获得从一个结构变量访问同类型的另一个结构变量的能力。该结构的定义如下：
struct stamprecord
{
char name[20];
float size[2];
unsigned int data;
char *description;
struct stamrecord *next;
}
每个记录的结构确定之后，便要考虑如何将各个记录连接起来，组合成完整的记录集。在此不得不讨论动态内存分配的问题。
一般情况下，变量的存储空间的分配是在编译时便完成了，但是每个程序都拥有一块可以在运行时再进行分配的内存空间，称为动态内存分配空间。在程序中，可以通过“new”操作符为指针或变量获得动态内存空间，并一直将该空间保持到程序员显式地将该空间收回。例如：
char *copystr(const char *s)
{
char *ps=new char[strlen(s)+1];
strcpy(ps,s);
return ps;
}
显式地收回动态分配的内存空间的方法是用“delete”操作符施加在指向动态对象的指针上。如上例中要释放动态分配内存：
delete ps;
注意：整个系统的动态分配内存空间是有限的，它将有可能被耗尽。因此对于已经无用的动态分配内存空间，应该及时地进行释放。
简单介绍一下链表结构中添加、删除、插入、遍历、修改一个记录的过程。
3．4．6 联合在C++中，允许不同数据类型的数据使用共同的内存区域，这种数据构造类型称为联合，或称为联合体。联合在定义、说明和使用的形式上与结构很相似，但两者在本质上有着根本的区别，使用时应该引起重视。
定义联合的一般语法结构如下：
union variable
{
data_type1 variable1;
data_type2 variable2;
.
.
.
data_typen variablen;
};
联合的定义也只确定了形式，并不分配具体的内存空间。联合的n个成员在内存中具有相同的存储空间首地址。为了满足存放任意一个成员数据的目的，联合在内存是所占用的内存空间大小总是由成员中数据长度最长的成员项所占用的内存空间决定。
联合一经定义，便可以用它来说明使用这种数据构造类型的具体对象，其形式与结构对象的定义相同，如：
union utype
{
int in;
double do;
char ch;
};
utype data,*pt,gdata[20];
由于联合中的各个成员使用同一内存区域，所以在程序运行的任一时刻，联合对象所占有的内存单元中只能保持某个成员的数据。联合的引入是为了节约内存空间，将不会在同一时刻出现的某些变量结合起来，定义为联合类型，这样使变量定义所占用的内存区域达到最少。
对于联合的成员访问，与结构成员的访问相同，即采用“．”或“->”来进行访问。如上例中的定义，可以按以下方式进行访问：
data.in=99;
pt->ch=’A’;
gdata[1].do=3.3;
3．4．7 位域在对外部设备接口硬件进行控制和管理时，经常使用的控制方式是向接口发送方式字或命令字,以及从接口读取状态字等。它们通常是以二进制为单位的字段组成的数据，称为位字段数据。
位域是一种结构的变体，它允许访问一个字节的各个位。位域的所有成员只占一个或几个二进制位，它用来表示被压缩在一个字节内的各种信息。虽然对位的操作可以按位运算来实现，但运用位域将更有效，更具有通用性。
定义位域的一般语法形式如下所示：
struct variable
{
data_type1 name1:lenght1;
data_type2 name2:lenght2;
.
.
.
data_typen namen:lenghtn;
}
从上述语法形式可以看出，位域结构的说明方法与普通结构的说明方法基本相同，只不过是在成员名后加上冒号和长度说明。data_type只能是int、unsigned、signed中选择一种，且由于单个位不可能具有符号位，因此长度为1的类型只能是unsigned类型。
对于位域的访问及其他内容，与结构的相应内容十分相似。
在位域的所有成员进行存储时，使用的内存大小与int型数据相同。当成员的总位长超过int 型时，它将占用下一个连续的int 型数据位长空间。但是，位域中的任何一个成员不会跨越两个int型字长空间的边界。
对位域变量还有一些规定：不可以取位域变量位成员的地址；位域变量成员不能是数组。不同机型表示位域的顺序有可能不同。
3．4．8 枚举类型枚举类型是一种用户自定义的数据类型，它为一组整型数值提供便于记忆的标识符。枚举类型必须先定义后使用，定义枚举类型的形式如下：
enum 枚举名{枚举成员列表}；
其中包含在花括号中的枚举成员列表是一组用逗号分隔的表示整型数值的标识符。
例如：
enum weekday
{Sunday,Monday,Tuesday,Wednesday,Thursday,Friday,Saturday};
枚举常量是符号常量，其值为int、char或unsigned中的一种。一般情况下，枚举成员列表中的第一个枚举常量的值是0，其余各枚举常量的值依次为1，2，3，4，．．．．．。也可以由用户指定。如：
enum color
{
white=1;
red=3;
blue;
grey=white+6
};
枚举常量被定义后，其值在程序中不可以改变。
可以用枚举名来说明枚举变量，其说明方法与结构变量的说明相似，其形式如下：
枚举名 枚举变量名；
例如：weekday days;
在对枚举进行定义并对枚举变量进行说明之后，可以将枚举常量赋给枚举变量和整型变量，或将枚举变量赋给整型变量，在经过强制类型转换后，也可以将整型变量的值或整型常数赋给枚举变量。
例如：
days=Sunday;
days=(weekday)1;
int i=Wednesday;
可以将枚举常量和枚举变量作为表达式的成员、函数的实参等，并且还可以说明枚举类型的指针。
3．4．1 结构变量定义及使用
C++提供了结构这一聚合数据类型，它是将具有一定联系的一组数据类型相同或不同的数据组织起来，进行统一管理，并赋予一个统一的名字。
结构可以是由不同数据类型的数据成员组成，面向对象的结构类型还可以包含函数说明和定义，从而可以定义一个类，用标识符struct 定义的类与用标识符class定义的类，其主要区别在于其成员的缺省访问属性不同。组成结构的每个数据称为该结构的成员。在使用结构之前，必须对该结构进行定义，以告诉编译器该结构的成员个数及其数据类型。本栉首先介绍非面向对象的结构，它属于一种聚合数据类型。
结构定义的语法形式如下：
struct variable
{
data_type1 name1;
data_type2 name2;
.
.
.
data_typen namen;
};
注意：结构的定义是一条语句，在其结尾处需要加一个语句结束符“；”。
例如：下面是一个通信录记录结构定义的一个例子：
struct addr
{
char name[30];
char street[40];
char city[20];
char state[2];
unsigned long zip;
};
在对结构进行定义后，就可以用来指明使用该结构的具体对象，这就称为结构的实例化，其一般形式如下：
struct variable name; 或 variable name;（常用形式）
其中struct是结构的标识符，variable是已经定义过的结构名称，name是结构变量名称。
在定义了结构的变量之后，可以用操作符“．”来访问结构中的成员数据。访问结构数据成员的形式如下所示：
name.member;//name是结构变量的名字，member是其某一成员数据的变量名。
3．4．2 结构数组最常用的结构对象是结构数组，而结构数组最主要的用途便是构造链表。
为了定义一个结构数组，必须首先定义一个结构类型，然后利用该结构类型来说明一个数组。为了访问数组中某一元素的某成员数据，必须指明该元素在数组中的下标及该成员数据的名称。如以下是使用上一节中定义过的通信记录结构定义结构数组并访问其成员数据的例子：
addr binfo[100];
binfo[0].zip=1234;
3．4．3 结构指针结构作为一种聚合数据类型，其变量是在内存中进行存放的，也有一定的内存地址，因而也就存在结构变量指针。结构指针可以用来指向任何统一结构类型的结构变量，可以通过结构指针来访问结构的成员数据。
定义结构指针的一般语法结构如下：
struct variable *name; 或 variable *name;
同样，对结构指针必须初始化或赋值，使其指向结构变量。对结构指针进行赋值时，需要将一个结构变量的地址赋给它，即对结构变量进行取址操作或利用其他结构指针对某个类型匹配的结构指针进行赋值。利用结构指针来对结构的成员数据进行访问的一般形式如下所示：
structure_variable->member_name;
其中structure_variable是结构变量的名字，而member_name是成员数据的变量名。
[例3．6] 使用结构指针的例子。(EX3_6.CPP)
3．4．4 结构的嵌套结构的嵌套指的是结构的成员数据中包含其他结构，形成复杂的数据结构在C++中，结构可以作为其他结构的成员数据。只要在编译器或计算机支持的范围内，结构可以多级地嵌套。
注意：程序中出现的所有结构，在结构中都必须的定义。
对于结构嵌套的情况，要访问作为某一结构的成员的结构的成员数据，需要进行多级逐层引用。
[例3．7] 结构嵌套的应用。EX3_7.CPP
3．4．5 链表类数据处理链表是计算机数据处理中常用的一种数据结构。在链表中，各元素具有相似的结构，且各元素之间依次链接形成民链状的表单结构，且链表的线性顺序连续是逻辑上的，而不是依赖分配连续存储空间来维持的，因而在物理结构上是灵活的，属于线性动态结构。结构是实现链表类数据处理的强有力的工具，有很多衫的链表结构都是用结构构造出来的。
为了实现通过链表结构中某一元素访问其他元素，即结构变量提供可以指向其他结构变量的机制，需要使用递归结构类型。在递归结构类型中，结构的成员数据中包含指向该结构类型本身的结构指针，利用该指针，可以实现对同类型的结构变量的访问。
例如，一个集邮爱好者想为他的收藏品建立一个卡片式档案。每张卡片记录一张邮票的情况，包括邮票名称，尺寸、发行日期、描述信息等内容。以这些要包含的内容作为成员函数，构成一个结构类型，每张卡片作为一个结构变量来处理，但这些卡片如何组织起来需要好好考虑一下。如建立结构数组或链表结构，比较而言，链表结构在处理记录增加、删除等方面要好于数组结构。因而选用链表结构。
先根据卡片的内容定义一个结构类型，该结构类型应该是弟归结构，以获得从一个结构变量访问同类型的另一个结构变量的能力。该结构的定义如下：
struct stamprecord
{
char name[20];
float size[2];
unsigned int data;
char *description;
struct stamrecord *next;
}
每个记录的结构确定之后，便要考虑如何将各个记录连接起来，组合成完整的记录集。在此不得不讨论动态内存分配的问题。
一般情况下，变量的存储空间的分配是在编译时便完成了，但是每个程序都拥有一块可以在运行时再进行分配的内存空间，称为动态内存分配空间。在程序中，可以通过“new”操作符为指针或变量获得动态内存空间，并一直将该空间保持到程序员显式地将该空间收回。例如：
char *copystr(const char *s)
{
char *ps=new char[strlen(s)+1];
strcpy(ps,s);
return ps;
}
显式地收回动态分配的内存空间的方法是用“delete”操作符施加在指向动态对象的指针上。如上例中要释放动态分配内存：
delete ps;
注意：整个系统的动态分配内存空间是有限的，它将有可能被耗尽。因此对于已经无用的动态分配内存空间，应该及时地进行释放。
简单介绍一下链表结构中添加、删除、插入、遍历、修改一个记录的过程。
3．4．6 联合在C++中，允许不同数据类型的数据使用共同的内存区域，这种数据构造类型称为联合，或称为联合体。联合在定义、说明和使用的形式上与结构很相似，但两者在本质上有着根本的区别，使用时应该引起重视。
定义联合的一般语法结构如下：
union variable
{
data_type1 variable1;
data_type2 variable2;
.
.
.
data_typen variablen;
};
联合的定义也只确定了形式，并不分配具体的内存空间。联合的n个成员在内存中具有相同的存储空间首地址。为了满足存放任意一个成员数据的目的，联合在内存是所占用的内存空间大小总是由成员中数据长度最长的成员项所占用的内存空间决定。
联合一经定义，便可以用它来说明使用这种数据构造类型的具体对象，其形式与结构对象的定义相同，如：
union utype
{
int in;
double do;
char ch;
};
utype data,*pt,gdata[20];
由于联合中的各个成员使用同一内存区域，所以在程序运行的任一时刻，联合对象所占有的内存单元中只能保持某个成员的数据。联合的引入是为了节约内存空间，将不会在同一时刻出现的某些变量结合起来，定义为联合类型，这样使变量定义所占用的内存区域达到最少。
对于联合的成员访问，与结构成员的访问相同，即采用“．”或“->”来进行访问。如上例中的定义，可以按以下方式进行访问：
data.in=99;
pt->ch=’A’;
gdata[1].do=3.3;
3．4．7 位域在对外部设备接口硬件进行控制和管理时，经常使用的控制方式是向接口发送方式字或命令字,以及从接口读取状态字等。它们通常是以二进制为单位的字段组成的数据，称为位字段数据。
位域是一种结构的变体，它允许访问一个字节的各个位。位域的所有成员只占一个或几个二进制位，它用来表示被压缩在一个字节内的各种信息。虽然对位的操作可以按位运算来实现，但运用位域将更有效，更具有通用性。
定义位域的一般语法形式如下所示：
struct variable
{
data_type1 name1:lenght1;
data_type2 name2:lenght2;
.
.
.
data_typen namen:lenghtn;
}
从上述语法形式可以看出，位域结构的说明方法与普通结构的说明方法基本相同，只不过是在成员名后加上冒号和长度说明。data_type只能是int、unsigned、signed中选择一种，且由于单个位不可能具有符号位，因此长度为1的类型只能是unsigned类型。
对于位域的访问及其他内容，与结构的相应内容十分相似。
在位域的所有成员进行存储时，使用的内存大小与int型数据相同。当成员的总位长超过int 型时，它将占用下一个连续的int 型数据位长空间。但是，位域中的任何一个成员不会跨越两个int型字长空间的边界。
对位域变量还有一些规定：不可以取位域变量位成员的地址；位域变量成员不能是数组。不同机型表示位域的顺序有可能不同。
3．4．8 枚举类型枚举类型是一种用户自定义的数据类型，它为一组整型数值提供便于记忆的标识符。枚举类型必须先定义后使用，定义枚举类型的形式如下：
enum 枚举名{枚举成员列表}；
其中包含在花括号中的枚举成员列表是一组用逗号分隔的表示整型数值的标识符。
例如：
enum weekday
{Sunday,Monday,Tuesday,Wednesday,Thursday,Friday,Saturday};
枚举常量是符号常量，其值为int、char或unsigned中的一种。一般情况下，枚举成员列表中的第一个枚举常量的值是0，其余各枚举常量的值依次为1，2，3，4，．．．．．。也可以由用户指定。如：
enum color
{
white=1;
red=3;
blue;
grey=white+6
};
枚举常量被定义后，其值在程序中不可以改变。
可以用枚举名来说明枚举变量，其说明方法与结构变量的说明相似，其形式如下：
枚举名 枚举变量名；
例如：weekday days;
在对枚举进行定义并对枚举变量进行说明之后，可以将枚举常量赋给枚举变量和整型变量，或将枚举变量赋给整型变量，在经过强制类型转换后，也可以将整型变量的值或整型常数赋给枚举变量。
例如：
days=Sunday;
days=(weekday)1;
int i=Wednesday;
可以将枚举常量和枚举变量作为表达式的成员、函数的实参等，并且还可以说明枚举类型的指针。
