第三章 聚合数据类型与操作函数
在本章中，将进一步讨论C++中较为复杂的聚合与派生数据类型及操作函数。
本章目的：
·了解线性表结构数据处理及数组类型
·掌握指针类型变量及地址计算方法
·初步掌握函数定义与调用机制
·了解结构类型及链表结构数据处理
3．1 数组类型与简单线性表处理
3．1．1 线性表结构的C++处理方法线性表在内存中存放的形式有两种：
物理存储连续：各线性表元素在内存中是连续存放的。其中每个元素都包含相同的数据顶，即各线性表元素所占用的内存区域大小相同，在某一元素的内存地址上加上该内存区域的大小即可得到其下一个元素的内存地址。该线性表的结构如图３．1所示。
数据元素1 数据元素2 数据元素3 数据元素n
数据
1
数据
2
数据
3
数据
n
数据
1
数据
2
数据
3
数据
n
数据
1
数据
2
数据
3
数据
n
数据
1
数据
2
数据
3
数据
n
图3．１ 物理连续的线性表的一般结构该方法使用方便，存储经济，访问方便，缺点是要占用一块较大的连续内存区域，且数据的插入等操作较为困难。
2、逻辑上连续：在这种线性表中，各元素项都包含两个部分：一个数据项和一个指针项。
在数据项中，可以包含一个或多个相同或不同类型的数据，每个线性表元素中所包含数据的个数称为线性表的长度，但是在数据项中包含的数据的个数及相应的数据类型对线性表内的所有元素项都是相同的。
在指针项中，根据需要可以包含一个或多个指向线性表内其他元素的指针。一般的线性表的结构如图3．2
图3．２ 物理不连续线性表的一般结构
该方法为为编程处理带来较高的效率。
线性表可以用一个名称（标识符）进行标识，通常该标识符指向线性表的第一个元素项。线性表可以为空，则该标识符不指向任何元素项。
这种线性表可以方便地访问、插入、删除一个元素，也可以提供完善的查询、排序、显示等功能以及线性表状态监控函数等。最常见的线性结构是数组。
3．1．2 数组的定义与使用数组是具有相同数据类型的一组变量的集合，它具有有序性和均匀性的特点。一维数组在内存中是连续存放的，数组中的第一个元素存储在数组的最低地址，该地址即是数组的地址，用数组名来指示（指针）。在该线性表结构中，每个元素项只含有一个数据项，且性相同，即数据类型和数据长度相同。因此数组中的所有数据对象拥有共同的名字，其中每个特定的数据元素用相应的下标来进行确定。
一维数组的定义如下：
data_type varible[size];
注意：size必须大于等于1，用于定义范围大小的量必须是一个常量表达式。
在对数组中的对象进行访问时，使用如下形式：
varible[index]
其中varible是数组的标识符，index是对象所对应的下标。特别值得注意的是，在C++中数组元素的下标由0开始，而不是由1开始。C++是一种不进行下标越界检验的语言。因此在程序中使用了非法的数组下标来进行数据读写，编译系统将不认为是错误，而且也能进行读写操作。若进行读，读出的数据是无法预测的，若进行写，则有可能错误地修改其他数据，导致程序瘫痪。为避免这样的情况，程序员必须在程序的相应地方加上显式的数组范围检测。
通过数组名和下标组合来进行数据访问时，系统会根据在数组名中所保存的数组首元素地址值、该数组所保存数据的数据类型在内存中所占字节数以及下标的大小按如下公式计算。
数据地址=数组首地址+数据类型占用字节数*数组下标对数组进行初始化有两种方式。
（1）利用循环逐个给数据元素进行赋值。
（2）在定义数组时显示地用包括在大括号内，用逗号分割开的一组数值类进行初始化。
如：
int num[]={1,2,3,4};
float price[6]={1.2,2.3,3.4,4.5,5.6,6.7};
float height[20]={4.5,3.3,3.4};
注意：数组不能用另一个数组元素进行初始化或赋值，而必须依次拷贝数组的各元素。
3．1．2 多维数组在C++中，还可以定义多维数组。多维数组的定义与使用与一般数组相似。在进行定义时，每一维的范围大小都用一个中括号括起来。而在对数组元素的引用时，必须指明其在各维中的下标，且各维的下标也用中括号括起来。
二维数组的定义如下：
data_type varible[size1]size2] //size1为第一维注意：size1,size2必须大于等1，且用于定义数组各维范围大小的量必须是一个常量表达式。在定义了一个二维数组之后，可以用如下形式进行访问：
varible[index1][index2]
多维数组的初始化也可以按逐个给数组元素赋值和在数组定义时进行显示初始化两种进行。如：
int data[4][3]={1,2,3,4,5,6,7,8,9,10,11,12};
若按上例进行赋值，层次对应关系不清晰，而且在一些只进行部分赋值的情况下数值省略较为困难。为此，可以在外层的大括号内，再利用大括号将同属一行的各列元素的初值括起来，使层次关系更为清晰。如上例可改为：
int data[4][3]={{1,2,3},{4,5,6},{7,8,9},{10,11,12}};
int data[4][3]={{1},{2},{3},{4}};//给部分元素赋初值，其余元素则为零
int data[4][3]={1,2,3,4};
3．1．4 字符数组在C++中，没有提供字符串类型，对字符串的存储和标识是用字符数组（一维数组）来实现的。在字符数组中，除了字符串中的可打印字符外，编译器还要在字符串末尾加一个空（NULL）字符’\0’，标识字符串的结束。字符数组的长度为字符串的所有字符数加1。如果在定义字符数组时长度过小，则会在程序运行过程中引用到该字符数组时有可能导致死机。
C++中也支持字符串常量。字符串常量是由一对双引号括起来的字符序列。由于编译程序会自动的在字符串常量的末尾加上字符串结束符，因此不必人为地在字符串常量的末尾加上’\0’。
字符串常量初始化的形式如下：
char chr1[]={‘c’,’p’,’p’}; //只有3个元素，无结束符NULL
char chr2[]={“cpp”}; //编译程序自动加上NULL
char chr3[]={‘c’,’p’,’p’,’\0’}; //用户自己加上NULL
在本章中，将进一步讨论C++中较为复杂的聚合与派生数据类型及操作函数。
本章目的：
·了解线性表结构数据处理及数组类型
·掌握指针类型变量及地址计算方法
·初步掌握函数定义与调用机制
·了解结构类型及链表结构数据处理
3．1 数组类型与简单线性表处理
3．1．1 线性表结构的C++处理方法线性表在内存中存放的形式有两种：
物理存储连续：各线性表元素在内存中是连续存放的。其中每个元素都包含相同的数据顶，即各线性表元素所占用的内存区域大小相同，在某一元素的内存地址上加上该内存区域的大小即可得到其下一个元素的内存地址。该线性表的结构如图３．1所示。
数据元素1 数据元素2 数据元素3 数据元素n
数据
1
数据
2
数据
3
数据
n
数据
1
数据
2
数据
3
数据
n
数据
1
数据
2
数据
3
数据
n
数据
1
数据
2
数据
3
数据
n
图3．１ 物理连续的线性表的一般结构该方法使用方便，存储经济，访问方便，缺点是要占用一块较大的连续内存区域，且数据的插入等操作较为困难。
2、逻辑上连续：在这种线性表中，各元素项都包含两个部分：一个数据项和一个指针项。
在数据项中，可以包含一个或多个相同或不同类型的数据，每个线性表元素中所包含数据的个数称为线性表的长度，但是在数据项中包含的数据的个数及相应的数据类型对线性表内的所有元素项都是相同的。
在指针项中，根据需要可以包含一个或多个指向线性表内其他元素的指针。一般的线性表的结构如图3．2
图3．２ 物理不连续线性表的一般结构
该方法为为编程处理带来较高的效率。
线性表可以用一个名称（标识符）进行标识，通常该标识符指向线性表的第一个元素项。线性表可以为空，则该标识符不指向任何元素项。
这种线性表可以方便地访问、插入、删除一个元素，也可以提供完善的查询、排序、显示等功能以及线性表状态监控函数等。最常见的线性结构是数组。
3．1．2 数组的定义与使用数组是具有相同数据类型的一组变量的集合，它具有有序性和均匀性的特点。一维数组在内存中是连续存放的，数组中的第一个元素存储在数组的最低地址，该地址即是数组的地址，用数组名来指示（指针）。在该线性表结构中，每个元素项只含有一个数据项，且性相同，即数据类型和数据长度相同。因此数组中的所有数据对象拥有共同的名字，其中每个特定的数据元素用相应的下标来进行确定。
一维数组的定义如下：
data_type varible[size];
注意：size必须大于等于1，用于定义范围大小的量必须是一个常量表达式。
在对数组中的对象进行访问时，使用如下形式：
varible[index]
其中varible是数组的标识符，index是对象所对应的下标。特别值得注意的是，在C++中数组元素的下标由0开始，而不是由1开始。C++是一种不进行下标越界检验的语言。因此在程序中使用了非法的数组下标来进行数据读写，编译系统将不认为是错误，而且也能进行读写操作。若进行读，读出的数据是无法预测的，若进行写，则有可能错误地修改其他数据，导致程序瘫痪。为避免这样的情况，程序员必须在程序的相应地方加上显式的数组范围检测。
通过数组名和下标组合来进行数据访问时，系统会根据在数组名中所保存的数组首元素地址值、该数组所保存数据的数据类型在内存中所占字节数以及下标的大小按如下公式计算。
数据地址=数组首地址+数据类型占用字节数*数组下标对数组进行初始化有两种方式。
（1）利用循环逐个给数据元素进行赋值。
（2）在定义数组时显示地用包括在大括号内，用逗号分割开的一组数值类进行初始化。
如：
int num[]={1,2,3,4};
float price[6]={1.2,2.3,3.4,4.5,5.6,6.7};
float height[20]={4.5,3.3,3.4};
注意：数组不能用另一个数组元素进行初始化或赋值，而必须依次拷贝数组的各元素。
3．1．2 多维数组在C++中，还可以定义多维数组。多维数组的定义与使用与一般数组相似。在进行定义时，每一维的范围大小都用一个中括号括起来。而在对数组元素的引用时，必须指明其在各维中的下标，且各维的下标也用中括号括起来。
二维数组的定义如下：
data_type varible[size1]size2] //size1为第一维注意：size1,size2必须大于等1，且用于定义数组各维范围大小的量必须是一个常量表达式。在定义了一个二维数组之后，可以用如下形式进行访问：
varible[index1][index2]
多维数组的初始化也可以按逐个给数组元素赋值和在数组定义时进行显示初始化两种进行。如：
int data[4][3]={1,2,3,4,5,6,7,8,9,10,11,12};
若按上例进行赋值，层次对应关系不清晰，而且在一些只进行部分赋值的情况下数值省略较为困难。为此，可以在外层的大括号内，再利用大括号将同属一行的各列元素的初值括起来，使层次关系更为清晰。如上例可改为：
int data[4][3]={{1,2,3},{4,5,6},{7,8,9},{10,11,12}};
int data[4][3]={{1},{2},{3},{4}};//给部分元素赋初值，其余元素则为零
int data[4][3]={1,2,3,4};
3．1．4 字符数组在C++中，没有提供字符串类型，对字符串的存储和标识是用字符数组（一维数组）来实现的。在字符数组中，除了字符串中的可打印字符外，编译器还要在字符串末尾加一个空（NULL）字符’\0’，标识字符串的结束。字符数组的长度为字符串的所有字符数加1。如果在定义字符数组时长度过小，则会在程序运行过程中引用到该字符数组时有可能导致死机。
C++中也支持字符串常量。字符串常量是由一对双引号括起来的字符序列。由于编译程序会自动的在字符串常量的末尾加上字符串结束符，因此不必人为地在字符串常量的末尾加上’\0’。
字符串常量初始化的形式如下：
char chr1[]={‘c’,’p’,’p’}; //只有3个元素，无结束符NULL
char chr2[]={“cpp”}; //编译程序自动加上NULL
char chr3[]={‘c’,’p’,’p’,’\0’}; //用户自己加上NULL
