数据和C
数据类型关键字
基本数据类型使用11个关键字:int、long、short、unsigned、char、float、double、signed
、_Bool
、_Complex
和_Imaginary
。
有符号整数:
这种类型可以取正值和负值。
- int:系统的基本整数类型。C保证int类型至少有16位长。
- short或short int:最大的short整数不大于最大的int整数值。C保证short类型至少有16位长。
- long或long int:这种类型的整数不小于最大的int整数值。C保证long至少有32位长。
- long long或long long int:这种数据类型的整数不小于最大的long整数值。long long类型至少是64位长。
无符号整数:
无符号整数只有0和正值,这使得无符号数可以表达的比有符号数更大的正值。使用unsigned关键字表示无符号数,例如:unsigned int、unsigned long和unsigned short。
字符:
字符包括印刷字符,如A、&和+。在定义中,char类型使用1个字节的存储空间表示一个字符。出于历史原因,字符字节通常为8位,但出于表示基本字符的需要,它也可以为16位或者更长。
char
: 字符类型的关键字。一些实现使用有符号的cha
r,另外一些则使用无符号char。C允许使用signed
和unsigned
关键字标记char的符号属性。
布尔值:
布尔值表示true
和false
;C使用1代表true
,0代表false
。
_Bool
:此类型的关键字。布尔值是一个无符号整数,其存储只需要能够表示1和0的空间。
实浮点数:
实浮点数可以有正值或负值。
float
:系统的基本浮点类型。至少能表示6位有效数字。double
:范围可能更大的浮点类型。能表示比float类型更多的有效数字(至少10位,通常会更多)以及更大的指数。
long double
:范围再大的浮点类型。
位、字节和字
最小的存储单位称为位(bit)。它可以容纳两个值(0或1)之一。位是计算机存储的基本单位。
字节(byte)是常用的计算机存储单位。几乎对于所有的机器,一个字节均为8位。由于每个位或0或1,所以一个8位的字节包含256种可能的0、1组合。这些组合可用于表示0到255的整数或者一组字符。
小结
计算机中,浮点数和整数有很大的不同,它们的存储和运算都有很大区别。
计算机内存中用数值编码来表示字符。美国最常用的数值编码是ASCII码,C也支持其他编码的使用,字符常量是计算机系统所使用的数值编码的符号表示,它表示为单引号中的一个字符。
数组和指针
声明一些数组的例子:
1 | float candy[365]; |
方括号[]表示candy和其他两个标识符均为数组,方括号内的数字指明了数组包含的元素数目。
数组的初始化
int powers[8] = {1, 2, 4, 8, 16, 32, 64};
有时候需要只读数组,在这种情况下,建议使用关键字const。
const int days[] = {31, 28, 31, 30, 31, 30, 31, 31, 31, 31, 30, 31};
- 当使用空的方括号对数组进行初始化时,编译器会根据列表中的数值数目来确定数组大小。
- 运算符sizeof给出其后的对象或类型的大小。因此sizeof days是整个数组的大小,sizeof days[0]是一个元素的大小。整个数组的大小除以单个元素的大小就是数组中元素的数目。
为数组赋值
声明完数组后,可以借助数组的索引对数组成员进行赋值。例如:
1 | int counter, evens[50]; |
C不允许把数组作为一个整体来进行赋值,也不支持用花括号括起来的列表形式进行赋值(初始化的时候除外)。下面这段代码展示了一些不允许的赋值方式:
1 | int oxen [5] = {5, 3, 2, 8}; //这里是允许的,下面的都是不合法的 |
数组和指针的关联
数组名也是该数组的首元素的地址。也就是说,如果flizny是一个数组,下面的代码是正确的:
flizny == &flizny[0];
&
是地址运算符
在C中,对一个指针加一的结果是对该指针增加一个存储单元。对于数组而言,地址会增加到下一个元素的地址,而不是下一个字节。这就是为什么声明一个数组时必须声明它所指向对象的类型。
- 指针的数值就是它所指向的对象的地址。
- 在指针前运用运算符*就可以得到该指针所指向的对象的数值。
- 对指针加1,等价于对指针的值加上它指向的对象的字节大小。
下面的等式体现了C的优点:
1 | dates + 2 == &dates[2];//相同的地址 |
函数、数组和指针
如果实现这样一个对一个int类型的数组求和的函数,可以使用一个指针参量来确定数组的开始点,使用一个整数参量来指明数组的元素个数。但这并不是向函数传递数组信息的唯一方法。另一种方法是传递两个指针,第一个指针指明数组的起始地址,第二个指针指明数组的结束地址。如下:
1 | int sump(int *start, int *end); |
指针操作
下面的列表描述了可对指针变量执行的基本操作:
- 赋值
- 求值
- 取指针地址
- 增加指针的值
- 从指针中减去一个整数
- 求差值
- 比较
小结
C把数组名解释为该数组首元素的地址,也就是说,数组名和指向首元素的指针是等价的。通常,数组和指针是紧密联系的。如果ar是数组,那么表达式ar[i]和*(ar+i)是等价的。
C不支持把整个数组作为函数参数来传递,但是可以传递数组的地址。然后函数可以利用该地址来处理原始数组。如果函数功能不需要修改原始数组,那么在声明相应的形式参量时,需要加上关键字const。
对指针加上一个整数或进行增量运算时,指针值的改变都是以所指向对象的字节大小为单位的。也就是说,如果pd指向数组内的一个8字节长的double数值,则对pd加1就相当于对它的值加上数值8.这样,该指针就会指向数组的下一个元素。
存储类
在分析存储类之前,我们需要理解一些术语的意义:作用域、链接以及存储时期。
- 作用域:作用域描述了程序中可以访问一个标识符的一个或多个区域。一个C变量的作用域可以是代码块作用域、函数原型作用域和文件作用域。
- 代码块作用域:在代码块中定义的变量具有代码块作用域。
- 函数原型作用域:函数原型作用域从变量定义处一直到原型声明的末尾。
- 文件作用域:一个在所有函数之外定义的变量具有文件作用域。
- 链接:C中一共有三种链接类型,外部链接、内部链接和空链接。一个C变量具有三种链接之一。
- 空链接:具有代码块作用域或者函数原型作用域的变量属于空链接。
- 内部链接:具有代码块作用域的并且用static修饰的变量为内部链接。
- 外部链接:和内部链接一样具有代码块作用域且被关键字extern或者没有被关键字修饰(属于文件作用域的变量如没有关键字修饰C默认为extern修饰)的具有外部链接。
- 存储时期:一个C变量具有静态存储时期或自动存储时期之一。
C使用作用域、链接和存储时期来定义了5种存储类:自动、寄存器、具有代码块作用域的静态、具有外部链接的静态和具有内部链接的静态。
自动变量:属于自动存储类的变量具有自动存储时期、代码块作用域和空链接的特点。
寄存器变量:通常变量存储在内存中。如果幸运的话,寄存器变量可以被存储在CPU寄存器中(速度更快的可用内存中),从而可以比普通变量更快地访问和操作。由于寄存器变量多是存储在一个寄存器中而非内存中,所以无法获得寄存器变量的地址。自动变量与寄存器变量都有代码块作用域、空链接和自动存储时期。通常使用存储类标识符register可以声明寄存器变量:
1
2
3int main(void){
register int quick;
}我们说幸运是因为声明一个寄存器类变量仅是一个请求,而非一条指令。编译器必须在您的请求和可用寄存器的个数之间权衡,所以您可能达成不了自己的愿望。这种情况下,变量成为一个普通的自动变量;然而,您依然不能对它使用地址运算符。
具有代码块作用域的静态变量:静态是指变量的位置固定不动,不是值不可改变的意思。代码块作用域的静态变量具有代码块作用域、空链接和静态存储时期。
具有外部链接的静态变量:外部链接的静态变量具有文件作用域、外部链接和静态存储时期。
具有内部链接的静态变量:内部链接的静态变量具有文件作用域、内部链接和静态存储时期。
存储类说明符:auto、register、static、extern和typedef。
- auto:表明一个变量具有自动存储时期。
- register:请求变量存储在寄存器内。
- static:表明一个变量具有静态存储时期。
- extern:表明您在声明一个已经在别处定义了的变量。
前五种存储类有一个共同的特点:在决定了哪一个存储类之后就自动决定了作用域和存储时期。您的选择服从预先制定的内存管理规则。然而还有另外一种选择给您更多灵活性。这一选择就是使用库函数来分配和管理内存。
这种方式主要工具是函数malloc(),它接收一个参数:所需的内存字节数。然后malloc()找到可用内存中一个大小合适的块。内存是匿名的。然而,它却可以返回那块内存的地址。因此,您可以把那个地址赋值个一个指针变量,并使用该指针来访问那块内存。函数malloc()可以用来返回数组指针、结构指针等,因此一般需要把返回的类型指派为适当的类型。但将void指针赋值给其他类型的指针并不构成冲突。如果malloc()找不到所需的空间,它将返回空指针。
1 | double *ptd; |
一般的,对应每个malloc()
调用,应该调用一次free()
。函数free()的参数是先前malloc()
返回的地址,它释放先前分配的内存。
这种方式被称为动态内存分配,动态分配的内存在调用malloc()
或calloc()
时产生,在调用free()时释放。由程序员而不是一系列固定的规则控制内存持续时间,因此内存块可以在一个函数中创建,而在另一个函数中释放。由于这点,动态内存分配所有的内存部分可能变成碎片状,也就是说,在活动的内存块之间散布着未使用的字节片。不管怎样,使用动态内存往往导致进程比使用堆栈内存慢。
结构和其他数据形式
结构体
声明一个结构体,首先使用关键字struct
,它表示接下来是一个结构。后面是一个可选的标记,它是用来引用该结构的快速标记。声明就像下面这样:
1 | struct book{ |
1 | struct book library, panshin, *ptbook; |
结构变量library和panshin均包含title、author和value部分。指针ptbook可以指向library、panshin,或任何其他book结构变量。
struct book library
是以下声明的简化:
1 | struct book{ |
换句话说声明结构的过程和定义结构变量的过程可以被合并成一步。
初始化一个结构可以使用与初始化数组相似的语法:
1 | struct book library = { |
如要访问一个结构的成员用结构成员运算符点.
就可以。例如library.value
。
声明一个结构数组和声明其他任何类型的数组一样。例如:
1 | struct book library[10]; |
这条语句声明一个library为一个具有10个元素的数组,数组的每个元素都是book类型的结构。因此,library[0]是一个book结构。
- 指向结构的指针
1 | struct names{ |
若要使用结构指针访问结构成员,可以有两种方式:
使用一个新运算符:->。下面的例子可以清楚的表达这个意思:
him ->income is fellow[0].income if him == &fellow[0]
如果
him = &fellow[0]
,那么*him = fellow[0]
,因为&和 * 是一对互逆的运算符。因此可以做以下替代:1
fellow[0].income == (*him).income;
枚举类型
可以使用枚举类型声明代表整数常量的符号名称。通过使用关键字enum
,可以创建一个新类型并指定它可以具有的值。枚举类型的目的是提高程序的可读性。它的语法与结构的语法相同。例如:
1 | enum spectrum { |
第一个声明设置spectrum为标记名,从而允许您把enum spectrum作为一个类型名使用。第二个声明使得color成为该类型的一个变量。
1 | int c; |
typedef简介
typedef
工具是一种高级数据特性,它是您能够为某一类型创建您自己的名字。在这个方面,它和#define
相似,但是它们具有三个不同之处:- 与
#define
不同,typedef
给出的符号名称仅限于类型,而不对值。 typedef
的解释由编译器,而不是预处理器执行。- 虽然它的范围有限,但在其受限范围内,
typedef比#define
更灵活。
举个简单的typedef的例子,假如要对1字节的数值使用术语BYTE,您只须像定义一个char变量来定义BYTE,然后在这个定义前面加上关键字typedef,如:
1
typedef unsigned char BYTE;
随后就可以使用BYTE来定义变量了:
1
BYTE x, y[10], *z;
- 与
函数指针
声明指向函数的指针是可以的。典型的用法是,一个函数指针可以作为另一个函数的参数,告诉第二个函数使用哪个函数。 函数也有地址,这是因为函数的机器语言实现是由载入到内存中的代码组成。指向函数的指针中保存着函数代码起始处的地址。
当声明一个函数指针时,必须声明它指向的函数类型。要指定函数类型,就要指出函数的返回类型以及函数的参量类型。例如:
1 | void ToUpper (char *); |
要声明指向上述函数的指针,可以这样做:
1 | void (*pt) (char *);//pt是一个指向函数的指针 |
下面举个简单的例子来阐述函数指针的用法:
1 | void ToUpper (char *); |
历史上,贝尔实验室的C和UNIX的开发者采用第一种观点,而Berkeley的UNIX的扩展者采用第二种观点。为了保持与现有代码的兼容性,ANSIC把这二者作为等价形式全部接受。
位操作
通常向硬件设备发送一两个字节来控制该设备,其中每一位都有特定的含义。同样的,通常使用代表特定项目的特定位来存储操作系统关于文件的信息。许多压缩和加密操作都对单独的位进行操作。高级语言一般不处理这一级别的细节;C在提供高级语言便利的同时,也能够在典型的为汇编语言所保留的级别上工作,这是其成为编写设备驱动程序和嵌入式代码的首选语言。
二进制、位和字节
一个十进制的数2157
,我们可以写成如下形式:
1 | 2*1000 + 1*100 + 5*10 + 7*1 |
计算机的位只有两种选择0或1(关闭或打开),因此,以2为基数的系统适用于计算机。它用2的幂代替10的幂。以2为基数表示的数字成为二进制数。例如,二进制1101可以表示为以下形式:
1 | 1*2^3 + 1*2^2 + 0*2^1 + 1*2^0 |
以十进制表示为
1 | 1*8 + 1*4 + 0*2 + 1*1 = 13 |
一个字节通常有八位,128是2的7次幂,以此类推。该字节可以保存的最大数据是把所有的位都设置为1:1111 1111
,该二进制数的值如下:
1 | 128 + 64 + 32 + 16 +8 + 4 + 2 + 1 = 255 |
其他基数
计算机世界通常使用基于八和十六的数制系统。因为8和16都是2的幂,所以这些系统比十进制系统更接近于计算机的二进制系统。
十六进制指以16为基数的进制系统。该系统使用16的幂,使用的数字是0到15。10到15用A到F来表示。例如,十六进制数A3F代表:
1 | 10*16^2 + 3*16^1 + 15*16^0 = 2623(以十位基数) |
每个十六进制位对应于一个4位的二进制数,因此两个十六进制位恰好对应于一个8位字节。第一个十六进制位位表示高4位,第二个表示低4位。这使得十六进制适用于表示字节。下表显示了这个对应关系:
十进制数 | 十六进制数 | 二进制数 | 十进制数 | 十六进制数 | 二进制数 |
---|---|---|---|---|---|
0 | 0 | 0000 | 8 | 8 | 1000 |
1 | 1 | 0001 | 9 | 9 | 1001 |
2 | 2 | 0010 | 10 | A | 1010 |
3 | 3 | 0011 | 11 | B | 1011 |
4 | 4 | 0100 | 12 | C | 1100 |
5 | 5 | 0101 | 13 | D | 1101 |
6 | 6 | 0110 | 14 | E | 1110 |
7 | 7 | 0111 | 15 | F | 1111 |
C的运算符
C提供位的逻辑运算符和位移运算符。4个位运算符用于整型数据,包括char。将这些运算符称为位运算符的原因是它们对每位进行操作,而不影响左右两侧的位。
二进制反码或按位取反:~
一元运算符~将每个1变为0,将每个0变为1,如下所示:
1 | ~(1001 1010) |
位与(AND):&
二进制运算符&通过对两个操作数逐位进行比较产生一个新值。对于每个位,只有两个操作数的对应为都为1时结果才为1。如下:
1 | (1001 0011)&(0011 1101) |
C也有一个组合的位与赋值运算符:&=
。下面两个语句产生相同的结果:
1 | val &= 0377; |
位或(OR):|
二进制运算符|通过对两个操作数逐位进行比较产生一个新值。对于每个位,如果其中任意操作数中对应的位为1,那么结果位就为1。如下所示:
1 | (1001 0011) | (0011 1101) |
位异或:^
二进制运算符^对两个操作数逐位进行比较。对于每个位,如果操作数中的对于位有一个位1(但是不都为1),那么结果为1。如下所示:
1 | (1001 0011) ^ (0011 1101) |
用法:掩码
位与
运算符通常跟掩码一起使用。掩码是某些位设为开而某些位设置为关的位组合。掩码中的零覆盖了另一个数中相应的位,所以该过程称为使用掩码
,例如:
1 | ch &= 0xff; |
值0xff的二进制形式为11111111,十进制形式为0377。该掩码留下ch的最后8位,将其余位设为0。无论最初的ch是8位、16位或是更多,都将最终的值修整到一个字节中。
用法:打开关闭位
打开一个值中特定的位,同时保持其他位不变。可以使用位或
运算符来实现。例如:
考虑MASK,其位1设为1。下面的语句将flags中的位1设为1,并保留其他位不变:
1 | flags |= MASK; |
若想关闭flags中的位1,可以使用如下表达:
1 | flags &= ~MASK; |
用法:转置位
转置一个位表示如果该位打开,则关闭该位;如果该位关闭,则打开该位。您可以使用位异或运算符来转置一个位。例如:
1 | flags ^= MASK; |
用法:查看一位的值
如果你想查看flags的位1是否为1,不应该简单的比较flags与MASK。即使flags中的位1被设为1,flags中的其他位也会使比较结果为非真。必须屏蔽flags中其他位,以便只把flags中的位1和MASK相比较:
if((flags & MASK) == MASK)
移位运算符
移位运算符用<< 、>>表示左移和右移。左移运算符将其左侧操作数的值的每位向左移动,移动的位数由其右侧操作数指定。空出的位用0填充。例如:
1 | (1000 1010) << 2 |
位移运算符能欧提供快捷、高效的对2的幂的乘法和除法。
number << n | number乘以2的n次幂 |
---|---|
number >> n | 如果number为非负,number除以2的n次幂 |
位字段
对位进行操作的第二种方法是使用位字段。位字段由一个结构申明建立,该结构申明为每个字段提供标签,并决定字段宽度。例如:
1 | struct{ |
该定义使prnt包含四个一位字段。现在,可以使用普通的结构成员运算符将值赋值给单独的字段:
1 | prnt.itals = 0; |
总结
使C区别于许多高级语言的特性之一是访问整数中个别位的能力。该特性通常是程序与硬件设备和操作系统相连接的关键。
C有两个主要访问位的工具。一个是位运算符,另一个是在结构中创建位字段的能力。
典型地,使用这些特性的程序仅限于特定的硬件平台或操作系统,并且被设计为不可移植的。
C预处理器和C库
C预处理器和C库是C语言的两个重要的附件。执行预处理指令的C预处理器可以在编译源代码前对源代码进行调整。C库提供了许多有助于完成各种任务的函数,这些任务包括:输入、输出、文件处理、内存管理、排序与搜索、数学计算、字符串处理等等。
C预处理器
- 明显常量
预处理器指令从#开始,到其后第一个换行符为止。也就是说,指令的长度限于一行代码。在预处理开始前,系统会删除反斜线和换行符的组合。因此可以把指令扩展到几个物理行,由这些物理行组成单个逻辑行。
1 |
每个#define行由三部分组成。第一部分为指令#define自身。第二部分为所选择的缩略语,这些缩略语称为宏。第三部分称为替换列表或主体。预处理器在程序中发现了宏的实例后,总会用实体代替该宏。
- 在#define中使用参数
在#define中使用参数,可以创建外形和作用都与函数相似的类函数宏。类函数宏的定义中,用圆括号括起一个或多个参数,随后这些参数出现在替换部分。
1 |
函数调用与宏调用之间有着许多重要的差异,如下:
1 | int x = 2; |
得到的结果出乎你的意料,结果为8。这是因为预处理器不进行计算,而只进行字符串的替换。替换后的表达式为x+2*x+2
。
解决这种问题的方法是只需在定义时使用足够多的圆括号,如下:
1 | #define SQUARE(X) (X)*(X) |
从中得到的经验是使用必须的足够多的圆括号来保证以正确的顺序进行运算和结合。
- 利用宏参数创建字符串:#运算符
1 |
|
注意,引号中的字符串中的X被看作普通文本,而不是被看作一个可被替换的语言符号。C具有如下特点:如果X是一个宏参量,那么#X可以把参数名转化为相应的字符串。该过程称为字符串化。
1 | #define PSQR (X) pintf("The square of #X is %d",X); |
- 预处理的粘合剂:##运算符
和#运算符一样,##运算符可以用于类函数宏的替换部分。另外,##还可以用于类对象宏的替换部分。例如:
1 | #define XNAME(n) x##n |
- 可变宏:
...和_ _VA_ARGS_ _
有些函数(如printf())接收可变数量的参数。实现思想就是宏定义中参数列表的最后一个参数为省略号。这样,预定义宏_ _VA_ARGS_ _
就可以被用在替换部分中,以表明省略号代表什么。例如:
1 |
|
- 宏还是函数
宏于函数的选择实际上是时间与空间的权衡。宏产生内联代码;也就是说,在程序中产生语句。如果使用宏20次,则会把20行代码插入程序中。如果使用函数20次,那么程序中只有一份函数语句的拷贝,因此节省了空间。另一方面,程序的控制必须转移到函数中并随后返回调试程序,因此这比内联代码花费的时间更长。
其他指令
#undef
指令:#undef
指令取消定义一个给定的#define。例如:1
2#define LIMIT 400
#undef LIMIT现在就可以重新定义LIMIT,以使它有一个新的值。即使开始没有定义LIMIT,取消LIMIT的定义也是合法的。
#ifdef、#else和#endif
#ifndef
指令:使用这些指令告诉编译器根据编译时的条件接收或忽略信息块。例如:1
2
3
4
5
6
7#ifdef MAVIS
# include "hurse.h"
# define STABLES 5
#else
# include "cow.h"
# define STABLES 15
#endif类似于
#ifdef
指令,#ifndef
指令可以与#else
、#endif指令一起使用。#ifndef
判断后面的标识符是否为未定义的,#ifndef的反义词为#ifdef
。#ifndef通常用来定义此前未定义的常量。#if和#elif
指令:#if指令更像常规的C中的if;#if后跟常量整数表达式。如果表达式为非零值,则表达式为真。例如:1
2
3
4
5
6
7
8
9
内联函数
通常函数调用需要一定的时间开销。这意味着执行调用时花费了时间用于建立调用、传递参数、跳转到函数代码段并返回。使用类函数宏的一个原因就是可以减少执行时间。C99还提供另一种方法:内联函数,“把函数变为内联函数将建议编译器尽可能快速地调用该函数。上述建议的效果由实现来定义”。因此,使函数变为内联函数可能会简化函数的调用机制,但也可能不起作用。
创建内联函数的方法是在函数声明中使用函数说明符inline。通常首次使用内联函数前在文件中对该函数进行定义。例如:
1
2
3
4
5
6
7
8
9
inline void eatline(){
while (getchar() != '\n')
continue;
}
int main(){
eatline();
}内联函数应该比较短小。对于很长的函数,调用函数的时间少于执行函数主体的时间;此时,使用内联函数不会节省多少时间。
C库
最初并没有官方的C库,后来,基于UNIX的C实现变成了事实上的标准。于是ANSIC委员会主要以这个标准为基础开发了一个官方标准库。
数学库
数学库包含许多有用的数学函数。头文件math.h提供这些函数声明或原型。
通用工具库
通用工具库包含各种函数,其中包括随机数产生函数、搜索和排序函数、转换函数和内存管理函数。这些函数的原型在头文件stdlib.h中。
诊断库
由头文件assert.h支持的诊断库是设计用于辅助调试程序的小型库。它又宏assert()构成。
高级数据表示
数组与链表
结构本身不能含有同类型的结构,但是它可以含有指向同类型结构的指针。这样的定义是定义一个链表的基础。链表是一个列表,其中的每一项都包含描述何处能找到下一项的信息。下面给出一段链表的实现:
1 |
|
很多编程问题,比如创建一个列表或队列,可以用链表(一种动态分配的结构序列链)或数组来处理。每种形式都有其优势和缺点,下表总结了链表和数组的性质:
数据形式 | 优点 | 缺点 |
---|---|---|
数组 | C对其直接支持,提供随机访问 | 编译时决定其大小;插入和删除元素很费时 |
链表 | 运行时决定其大小快速插入和删除元素 | 不能随机访问用户;必须提供编程支持 |
向数组中插入一个元素,必须移动其他元素以便安插新元素,新元素离数组头越近,要移动的元素越多。而向链表插入一个节点,只需分配两个指针值。类似的,从数组中删除一个要重新安置大量元素,而从链表中删除一个节点只需重新设置一个指针并释放被删除节点使用的内存。
其次,考虑如何访问列表中的成员,对数组来说,可用数组索引直接访问任意元素。这被称为随机访问。对链表来说,必须从列表头开始,逐个节点的移动到所需的节点处,这叫做顺序访问。数组也可以顺序访问。
选择何种数据类型是取决于具体问题的。如果列表需要频繁地插入和删除元素因而不断地调整大小,并且不需要经常搜索,链表是更好的选择。而如果列表基本稳定只是偶尔插入或删除一些元素,但却经常搜索,则数组是更好的选择。
如果需要一种既支持频繁地插入和删除又支持频繁搜索的数据类型,链表和数组都不是针对这个目标的理想选择。另一种形式,二叉搜索树。我们会在下文详细介绍。
抽象数据类型(ADT)
计算机科学已经研究出一种定义新类型的成功方法。这种方法使用三个步骤来完成从抽象到具体的过程:
- 为类型的属性和可对类型执行的操作提供一个抽象的描述。这个描述不应受任何特定实现的约束,甚至不应受到任何特定编程语言的约束。这样一种正式的抽象描述被称为抽象数据类型(ADT);
- 开发一个实现该ADT的编程接口。即说明如何存储数据并描述用于执行所需操作的函数集合。比如在C中,可能同时提供一个结构的定义和用来操作该结构的函数原型。这些函数对用户自定义类型的作用和C内置运算符对C基本类型的作用相同。想要使用这种新类型的人可以使用这个接口来进行编程。
- 编写代码来实现这个接口。当然,这一步至关重要,但是使用这种新类型的程序员无须了解实现的细节。
队列(ADT)
队列是具有两个特殊属性的列表。第一,新的项目只能被添加到列表结尾处。第二,项目只能从列表开始处被移出。可以将队列看成是一队买电影票的人。您在队尾加入队列,在买完票后从队首离开。队列是一种“先进先出(FIFO)”的数据形式。
下面我们将队列的代码实现用ADT来表现:
1 |
|
二叉搜索树
二叉搜索树是一种结合了折半搜索策略的链接结构。树中的每一个节点都包含一个项目和两个指向其他节点的指针。这种构思是每一个节点都有两个子节点,左节点和右节点。在左节点中的项目是父节点中项目的前序项,而在右节点中的项目是父节点中项目的后序项。这种关系存在于每一个有子节点的节点中。
二叉树ADT:
1 |
|