第十三章 文件输入输出

与文件通信

文件的含义

file指的是在磁盘或者固态硬盘上的一段已命名的存储区。C把文件看做是一系列连续的字节，每个字节都被单独读取，这与UNIX环境的文件结构相对应。由于其他环境中可能无法完全对应这个模型，C提供两种文件模式：文本模式和二进制模式。

所有文件的内容都以二进制形式（0或1）存储。但是，如果文件最初使用二进制编码的字符（例如ASCII或Unicode）表示文本（就像C字符串一样），该文件就是文本文件，其中包含文本内容。如果文件中的二进制值表示机器语言代码或者数值数据或图片或音乐编码，该文件就是二进制内容。
为了规范文本文件的处理，C提供两种访问文件的途径：二进制和文本模式。

• 文本模式：
  在文本模式中，程序所见的内容和文件的实际内容不同，程序以文本模式读取文件时，把本地环境表示的行末尾或文件结尾映射为C模式。例如C文本模式程序在MS-DOS平台读取文件时，把\r\n转换为\n；写入文件时再把\n转换为\r\n，在其他环境中编写的文本模式程序也会做类似的转换。
• 二进制模式：
  除了以文本模式读写文本文件，还能以二进制模式读写文本文件，如果要编写旧式Mac格式、MS-DOS格式或UNIX/Linux格式的文件模式程序，应该使用二进制，这样程序才能确定实际的文件内容并执行相应的动作。

二进制与文本模式

虽然C提供了二进制模式和文本模式，但是这两种模式的实现可以相同。因为UNIX使用一种文件格式，所以这两种模式对于UNIX实现而言完全相同，Linux也是如此。

I/O级别

除了选择文件模式，还可以选择I/O的两个级别（即处理文件访问的两个级别）。底层I/O（low-level I/O）使用操作系统提供的基本I/O服务，标准高级I/O（standard high-level I/O）使用C库的标准包和stdio.h头文件定义。

因为无法保证所有的操作系统都使用相同的底层I/O模式，C标准只支持标准I/O包。这也是我们主要讨论的I/O。

标准文件

C程序会自动打开三个文件：

• 标准输入standard input：一般情况下是系统的普通输入设备，通常为键盘
• 标准输出standard output和标准错误输出standard error output：系统的普通输出设备，通常为显示屏

通常，标准输入为程序提供输入，它是getchar()和scanf()使用的文件。程序通常输出到标准输出，它是putchar()、puts()和printf()使用的文件。

标准I/O

与底层I/O相比，标准I/O除了可移植性外还有两个好处：

• 标准I/O有很多函数简化了处理不同I/O的问题
• 输入和输出都是缓冲的

缓冲：一次转移大一块信息而非一字节信息（通常至少为512字节），程序读取文件时先将一块数据拷贝到缓冲区（一块中介存储区域），这种缓存极大地提高了数据传输效率。

fopen函数

该函数声明在stdio.h中，它的第一个参数是待打开文件的名称（确切的说是一个包含该文件名的字符串地址），第二个参数是一个字符串，指定待打开文件的模式：

程序成功打开文件后，fopen()将返回文件指针file pointer，其他I/O函数可以使用这个指针指向该文件。

文件指针fp并不指向实际的文件，它指向一个包含文件信息的数据对象，其中包含操作文件的I/O函数所用的缓冲区信息。因为标准库中的I/O函数使用缓冲区，所以它们不仅要知道缓冲区的位置，还需要知道缓冲区被填充的程序以及使用哪一个文件。标准I/O函数根据这些信息在必要时决定再次填充或者清空缓冲区。

getc()和putc()函数

这两个函数与getchar()和putchar()类似，但是要告诉这两个函数使用哪一个文件。

ch = getc(fp);

文件结尾

int ch;           // 用int类型的变量EOF
FILE * fp;
fp = fopen("wacky.txt", "r");
ch = getc(fp);    // 获取初始输入
while (ch != EOF)
{
    putchar(ch);  // 处理输入
    ch = getc(fp);// 获取下一个输入
}

// 简化一下
int ch;
FILE * fp;
fp = fopen("wacky.txt", "r");
while ((ch = getc(fp) != EOF)
{
    putchar(ch);  // 处理输入
}

fclose()函数

fclose(fp)函数关闭fp指定的文件，必要时刷新缓冲区。对于较正式的程序，应该检查是否成功关闭文件。如果成功关闭，fclose()函数返回0，否则返回EOF:

if (fclose(fp) != 0)
    printf("Error in closeing file %s\n", argv[1]);

如果磁盘已满、移动硬盘被移除或出现I/O错误，都会导致调用fclose()函数失败

指向标准文件的指针

stdio.h把三个文件指针和三个标准文件相关联：

文件I/O

fprintf()和fscanf()函数

fprintf(stdout, "%s\n", "Succ");
while (fscanf(fp, "%s", words) == 1)
rewind(fp);  /* 返回到文件开始处 */

fgets()和fputs()

fgets(buf, STLEN, fp);

这里，buf是char类型数组的名称，STLEN是字符串的大小，fp是指向FILE的指针。

fgets()函数读取输入直到第一个换行符的后面，或读到文件结尾，或者读取STLEN个字符，然后在末尾添加一个空字符使之成为一个字符串，字符串的大小是其字符数加上一个空字符。如果fgets()在读到字符上限之前已经读完一整行，它会把表示行结尾的换行符放在空字符前面。fgets()函数在遇到EOF时将会返回NULL值，可以利用这一机制检查是否已经到达文件结尾，如果未遇到EOF则之前返回传给它的地址。

fputs(buf, fp);

这里，buf是字符串的地址，fp用于指定目标文件。

随机访问：fseek()和ftell()

有了fseek()函数，就可以把文件看成数组，在fopen()打开的文件中直接移动到任意字节处。

/* reverse.c -- 倒序显示文件中的内容 */
#include <stdio.h>
#include <stdlib.h>
#define CNTL_Z '\032'   /* DOS文本文件中的文件结尾标记 */
#define SLEN 81
int main(void)
{
    char file[SLEN];
    char ch;
    FILE *fp;
    long count, last;
    
    puts("Enter the name of the file to be processed:");
    scanf("%80s", file);
    if ((fp = fopen(file, "rb")) == NULL)
    {
        printf("reverse can't open %s\n", file);
        exit(EXIR_FAILURE)
    }
    
    fseek(fp, 0L, SEEK_END);      /* 定位到文件末尾 */
    last = ftell(fp);
    for (count = 1L; cout <= last; count++)
    {
        fseek(fp, -count, SEEK_END); /* 回退 */
        ch = getc(fp);
        if (ch != CNTL_Z && ch != '\r') /* MS-DOS文件 */
            putchar(ch);
    }
    putchar('\n')；
    fclose(fp);
    return 0;
}

fseek()和ftell()的工作原理

fseek()的参数：

• FILE指针：指向待查找的文件，fopen()应该已经打开该文件
• offset偏移量：表示从起始点开始要移动的距离，必须是一个long类型的值，可以为正、负或者0（保持不动）
• model模式：该参数表示起始点，包括SEEK_SET文件开始处、SEEK_CUR当前位置、SEEK_END文件末尾

ftell()函数的返回类型是long，表示当前的位置。ftell()通过返回距文件开始处的字节数来确定文件的位置。

文件的第1个字节到文件开始处的距离是0

标准I/O的工作原理

第一步

使用标准I/O的第一步是调用fopen()打开文件（C程序会自动打开3中标准文件）。fopen()函数不仅打开一个文件，还创建了一个缓冲区（在读写模式下会创建两个缓冲区）以及一个包含文件和缓冲区数据的结构。另外，fopen()返回一个指向该结构的指针，以便其他函数直到如何找到该结构。

假如该指针赋给一个指针变量fp，我们说fopen()函数“打开一个流”。如果是文本模式打开该文件，就获得一个文本流，如果以二进制模式打开该文件，就获得一个二进制流。

这个结构通常包含一个指定流中当前位置的文件位置指示器，除此之外它还包含错误和文件结尾的指示器、一个指向缓冲区开始处的指针、一个文件标识符和一个计数（统计实际拷贝进缓冲区的字节数）。

第二步

以文件输入为例，使用标准I/O的第二步是调用一个定义在stdio.h中的输入函数，如fscanf()、getc()或者fgets()等。调用这些函数，文件中的数据块就被拷贝进缓冲区中。缓冲区的大小一般是512字节或者它的倍数。最初调用函数，除了填充缓冲区外，还需要设置fp所指向的结构中的值，尤其要设置流中的当前位置和拷贝进缓冲区的字节数。（通常，当前位置从字节0开始）

第三步

在初始化结构和缓冲区后，输入函数按要求从缓冲区中读取数据。在它读取数据时，文件位置指示器被设置为指向刚读取字符的下一个字符。==由于stdio.h系列的所有输入函数都使用相同的缓冲区，所以调用任何一个函数都将从上一次函数停止调用的位置开始。==

第四步

当输入函数发现已读完缓冲区内所有字符时，会请求把下一个缓冲大小的数据块从文件拷贝到该缓冲区中。以这种方式，输入函数可以读取文件中的所有内容，直到文件结尾。函数在读取缓冲区中的最后一个字符后，把结尾指示器设置为真。于是，下一次被调用的输入函数将返回EOF。

输入函数以类似的方式将数据写入缓冲区，当缓冲区被填满时，数据将被拷贝至文件中。

其他标准I/O函数

int ungetc(int c, FILE *fp)函数

int ungetc()函数将c指定的字符放回到输入流中，如果把一个字符放回输入流，那么下次调用标准输入时将读取该字符。

int fflush(FILE *fp)函数

调用fflush()函数会引起输出缓冲区中所有的未写入数据被发送到fp指定的输出文件，即刷新缓冲区。如果fp是空指针，那么所有的输出缓冲区都会被刷新。

int setvbuf()函数

函数原型：

int setvbuf(FILE * restric fp, char * restrict buf, int mode, size_t size);

该函数创建了一个供标准I/O函数替换使用的缓冲区，buf指向待使用的缓冲区。

二进制I/O: fread()和fwrite()函数

之前使用的标准I/O函数都是面向文本的，用于处理字符和字符串。

这种做法有一个劣势：举个例子如果需要存储double num = 1./3，使用%.2f转换说明将其存储为4个字符：0.33，用%.12f转换说明将其存储为14个字符0.333333333333。改变转换说明将改变存储该值所需的空间数量，也会导致存储不同的值。把num存储为0.33后，读取文件就无法将其恢复为更高的精度，这意味着一定的损失。

为保证数值在存储前后保持一致，最精确的做法应该是使用与计算机相同的位组合来存储。因此，double类型的值应存储在一个double大小的单元中，即以二进制形式存储数据。

实际上，所有的数据都是以二进制形式存储的，甚至连字符都以字符吗的二进制表示来存储。如果文件中的所有数据都被解释成字符码，则称该文件包含文本数据。如果部分或所有的数据都被解释成二进制形式的数值数据，则称该文件包含二进制数据。

image.png

int feof(FILE *fp)和int ferror(FILE *fp)函数

当标准输入函数读取错误或者函数到达文件末尾时都会返回EOF，feof()和ferror()函数用于区分这两种错误。

第十四章 结构和其他数据形式

建立结构声明

struct book{
    char title[MAXTITL];
    char author[MAXAUTL];
    float value;
};

定义结构变量

初始化结构

struct book library = {
    "The Pious Pirate and the Devious Damsel",
    "Renee Vivotte",
    1.95
}

访问结构成员

使用结构成员运算符——点.访问结构中的成员，例如：

library.value

结构的初始化器

例如，只初始化book结构的value成员：

struct book surprise = { .value = 10.99 };

结构数组

声明结构数组

struct book library[MAXBKS];

标识结构数组的成员

library[2].value

指向结构的指针

• 声明和初始化结构指针

struct guy * him;
him = &barney;

• 用指针访问成员
  第一种方法是使用->运算符，如果him == &barney，那么him->income等于braney.income；第二个方法是使用(*him).income

向函数传递结构的信息

传递结构成员

只要结构成员是一个具有单个值的数据类型，那么就可以把它作为参数传递给接收该特定类型的函数。

传递结构的地址

可以将结构体的地址传递给函数，当函数不能改变指针所指向值的内容时，需要把该结构体声明为一个指向const的指针。

传递结构

对于允许把结构作为参数的编译器，调用函数时编译器会根据结构模板创建一个自动结构变量，然后程序使用原来结构的副本进行计算。

其他结构特性

现在的C允许把一个结构赋值给另一个结构，但是数组不能这样做。

o_data = n_data; // 把一个结构赋值给另一个结构

结构和结构指针的选择

选择把结构体指针作为参数有两个优点：

• 兼容性好，无论是以前还是现在的C都能实现这个方法
• 执行速度快，只需要传递一个地址

缺点：
无法保护数据，但是使用const限定符可以解决这个问题。

选择结构作为参数传递的优点是函数处理的是原始数据的副本，保护了原始数据。但是这样做浪费时间和存储空间，尤其是把大型结构传递给函数但是只使用结构中的一两个成员时。

结构中的字符数组和字符指针

截至目前，我们都使用字符数组来储存字符串，我们也可以考虑用指向char型的指针来代替字符数组。

#define LEN 20
struct names {
    char first[LEN];
    char last[LEN];
};

结构声明可以这样写：

struct pnames {
  char * first;
  char * last;
};

差异：对于struct name类型的结构变量，字符串存储在结构体内部，结构总共要分配40字节存储姓名。对于struct pnames类型的结构变量，字符串存储在编译器存储常量的地方。结构本身只存储了两个地址，在我们系统中共占16字节，这个结构不用为字符串分配任何存储空间，它使用的是存储在别处的字符。总之，pnames结构变量中的指针应用只用来在程序中管理那些已分配和在别处分配的字符串。

// 有风险的代码
struct names accountant;
struct pnames attorney;
puts("Enter the last name of your accountant:");
scanf("%s", accountant.last);
puts("Enter the last name of your attorney:");
scanf("%s", attorney.last); /* 潜在危险 */

对于accountant，用户输入存储在accountant结构变量的last成员中。对于attorney，用户输入把字符串放到attorney.last表示的地址上。由于这是未经初始化的变量，地址可以是任何值，因此程序可以把名字存储在任何地方，这一操作可能导致程序崩溃

结构、指针和malloc()

在上一节中，如果使用malloc()分配内存并使用指针存储该地址，那么在结构中使用指针处理字符串就会比较合理。

struct namect{
    char * fname; //用指针替代数组
    char * lname; //
    int letters;
}

我们构造一个getinfo()函数把用户的输入读入临时数组，调用malloc()函数分配存储空间，并把字符串拷贝到新分配的存储空间中：

void  getinfo (struct namect * pst)
{
    char temp[SLEN];
    printf("Please enter your first name.\n");
    s_gets(temp, SLEN);
    // 分配内存储存名
    pst->fname = (char *) malloc(strlen(temp) + 1);
    // 把名字拷贝到已分配的内存
    strcpy(pst->fname, temp);
    printf("Please enter your last name.\n");
    s_gets(temp, SLEN);
    pst->lname = (char *)malloc(strlen(temp) + 1);
    strcpy(pst->lname, temp);
}

这两个字符串都存储在malloc()分配的内存块中，但是这种做法需要释放程序动态分配的内存，使用free()函数。

复合字面量和结构（C99）

如果只需要一个临时结构值，复合字面量很好用。例如，可以使用复合字面量创建一个数组作为函数的参数或者赋给另一个结构。例如struct book类型的复合字面量：

(struct book)("The Idiot", "Fyodor Dostoyevsky", 6.99)

伸缩型数组成员（C99）

声明一个伸缩型数组成员（flexible array member）具有如下规则：

• 伸缩性数组成员必须是结构的最后一个成员
• 结构中必须至少有一个成员
• 伸缩数组的声明类似于普通数组，只是方括号中是空的

struct flex
{
    int count;
    double average;
    double scores[]; //伸缩型数组成员
}

声明一个struct flex类型的结构变量时，不能用scores做任何事，因为没有给这个数组预留存储空间。C99的意图不是让你声明struct flex类型的变量，而是希望你声明一个指向struct flex类型的指针，然后用malloc()来分配足够的内存，以储存struct flex类型结构的常规内容和伸缩型数组所需要的额外空间，例如：

struct flex * pf;
// 请求为这一个结构和一个数组分配存储空间
pf = malloc(sizeof(struct flex) + 5 * sizeof(double));

// 访问成员
pf->count = 5;
pf->scores[2] = 18.5;

相关的限制：

• 不能用结构进行赋值或者拷贝，这样做只能拷贝伸缩型数组成员以外的其他成员，确实要进行拷贝的话应使用memcpy()函数

struct flex * pf1, *pf2; 
...
*pf2 = *pf1; // 不要这样做

• 不要按值方式把这种结构传递给结构，原因和前面相同，应该把结构的地址传递给函数
• 不要使用带伸缩型数组成员的结构作为树组成员或另一个结构的成员

匿名数组（C11）

struct person
{
    int id;
    struct(char first[20]; char last[20];); // 匿名结构
}

使用结构数组的函数

/* funds4.c -- 把结构数组传递给函数 */
#include <stdio.h>
#define FUNDLEN 50
#define N 2

struct funds {
    char bank[FUNDLEN];
    double bankfund;
    char save[FUNDLEN];
    double savefund;
};

double sum(const struct funds money[], int n);

int main(void)
{
    struct funds jones[N] = {
        {
          "Garlic-Melon Bank",
          4032.27,
          "Lucky's Savings and Loan",
          8543.94
        },
        {
            "Honest Jack's Bank",
            3620.88,
            "Party Time Savinds",
            3802.91
        }
    };
    
    printf("The Joneses have a total of $.2f.\n"), sum(jones, N);
    
    return 0;
}

double sum(const struct funds money[], int)
{
    double total;
    int i;
    
    for (i=0, total=0; i<n; i++)
        total += money[i]. bankfund + money[i].savefund;
    return (total);
}

注意点：

1. 可以把数组名作为数组中第一个结构的地址传递给函数
2. 然后可以用数组表示法访问数组中其他结构，比如sum(&jones[0], N)等价于sum(jones, N
3. 由于sum()函数不能改变原始数据，因此该函数使用const限定符

把结构内容保存到文件中

存储在一个结构中的整套信息被称为记录record，单独的项被称为字段field。

fprintf()

#define MAXTITL 40
#define MAXAUTL 40
struct book{
    char title[MAXTITL];
    char author[MAXAUTL];
    float value;
};

fprintf(pbooks, "%s %s %.2f\n", primer.title, primer.author, primer.value);

对于某些具有较多成员的结构，这种方法显得不够方便而又笨拙

fwrite()和fread()读写结构大小的单元

// 定位到primer结构变量开始的位置，并把结构中所有字节都拷贝到和pbooks相关的文件中
fwrite(&primer, sizeof(struct book), 1, pbooks);
// fread()函数从文件中拷贝一块结构大小的数据到&primer指向的位置

链式结构

队列、二叉树、堆、哈希表和图表都由链式结构linked structure组成，通常每个结构都包含一两个数据项和一两个指向其他同类型结构的指针。这些指针把一个结构和另一个结构链接起来

例如二叉树结构：

二叉树结构

联合

联合union也是一种数据类型，它能在同一个内存空间中存储不同的数据类型（并非同时存储）。典型用法是存储既无规律也不知道顺序的混合类型。

union hold {
    int digit;
    double bigf1;
    char letter;
};

枚举类型

枚举类型enumerated type主要是为了提高程序可读性，第一个声明创建了spetrum作为标记名，第二个声明使用color作为该类型的变量：

enum spectrum {red, orange, yellow, green, blue, violet};
enum spectrum color;

使用方法：

int c;
color = blue;
if (color == yellow)
    ...;
for (color = red; color <= violet; color++)
    ...;

typedef

使用typedef工具（一种高级数据特性）可以为某一类型自定义名称。

• 与#define不同，typedef创建的符号名只受限于类型，不能用于值
• typedef由编译器解释，不是预处理器
• 在其受限范围内，typedef比#define更加灵活

复杂声明

声明时可用的符号

复杂声明示例

int board[8][8];  // 声明一个内含int数组的数组
int ** ptr;       // 声明一个指向指针的指针，被指向的指针指向int
int * risks[10];  // 声明一个内含10个元素的数组，每个元素都是指向一个指向int的指针
int (* rusks)[10]; // 声明一个指向数组的指针，该数组含10个int类型的值
int * oof[3][4];   // 声明一个3*4的二维数组，每个数组都是指向int的指针
int (* uuf)[3][4]; // 声明一个指向3*4二维数组的指针，该数组中内含int类型值
int (* uof[3])[4]; // 声明一个内含3个指针元素的数组，其中每个指针都指向一个内含4个int类型元素的数组

函数和指针

函数本身也有地址，指向函数的指针中存储着函数代码的起始处的地址：

void ToUpper(char *);  // 把字符串中的字符转换为大写字符
void (*pf) (char *); // pf是一个指向函数的指针
void *pf(char *); // pf是一个返回字符指针的函数

第十五章 位操作

二进制数、位和字节

以2为基底表示的数字被称为二进制数binary number。

二进制整数

image.png

通常1字节包含8位，因此1字节最多可存储0~255范围内的数字，总共256个值。

unsigned char用1字节表示的范围是0~255，而signed char用1字节表示的范围是-128~127。

有符号整数

表示有符号最简单的方法是用1位存储符号，剩下7位表示数字本身表示数字本身，10000001表示-1，00000001表示1，因此其表示范围是-127~+127。这种做法的缺点是有两个0。
二进制补码two's-complement方法避免了这个问题，是当今最常用的系统。该方法用1字节的后7位表示0~127，高阶位设置为0。另外如果高阶位是1，表示的值为负。该方法可以表示-128~+127

这两种做法的区别在于如何确定负值，从一个9位组合100000000（256的二进制）减去一个负数的位组合就是该负数的值。

二进制浮点数

许多分数例如1/3都不能用十进制表示法精确地表示，于此类似，很多分数也不能用二进制表示法准确的表示。二进制表示法只能精确地表示多个1/2幂的和。
举个例子，十进制中一个普通的浮点数0.527表示为：

5/10 + 2/100 + 7/1000

在二进制中，.101表示：

1/2 + 0/4 + 1/8

转化为十进制即：

0.5 + 0.00 + 0.125 = 0.625

在这种局限下，3/4和7/8可以精确表示为二进制小数，但是1/3和2/5却不行。

浮点数

在计算机中表示一个浮点数，需要留出若干位存储二进制分数，其他位存储指数。举例而言，一个浮点数乘以4，那么二进制小数不变，其指数乘以2，二进制分数不变。如果一份浮点数乘以一个不是2的幂的数，会改变二进制小数部分，如有必要，也会改变指数部分。

C按位运算符

按位逻辑运算符

• 按位取反~：将1变为0，将0变为1
• 按位与&：两个运算对象中相应的位都为1时，结果才为1
• 按位或|：两个运算对象中相应位为1，则结果为1
• 按位异或^：两个运算对象相应位不同则为1

按位与用法：掩码

掩码mask，假设定义符号常量MASK为00000010，则：

flags = flags & MASK

掩码

把掩码中的0当做不透明，1当做透明，则相当于只有1的位才可见

按位或用法：打开位（设置位）

相当于只打开一个位，其他位保持不变。

flags = flags | MASK

按位与：关闭位（清空位）

任意位与0组合都为0

flags = flags & ~MASK

按位异或：切换位

使用^可以打开已关闭的位或关闭已打开的位，假设b为一个位（1或0），则0^b均为b；1^b均为~b

flags = flags ^ MASK

移位运算符

左移与右移

左移<<将其左侧运算对象每一位的值向左移动其右侧运算对象指定的位数，左侧运算对象移出左末端位的值丢失，用0填充空出的位置：

(10001010) << 2 
(00101000)

右移>>同理。

移位运算符的用法

位字段

操控位的第2种方法是位字段bit field，它是一个unsigned int类型变量中的一组相邻的位：

struct {
    unsigned int autfd : 1;
    unsigned int bldfc : 1;
    unsigned int undln : 1;
    unsigned int itals : 1;
} prnt;

prnt包含4个1位的字段，我们可以给其赋值：

prnt.itals = 0;
prnt.undln = 1;

变量prnt被存储在int大小的内存单元中，但是在本例中只使用了其中4位。

字段也不必限制为1位大小：

struct {
    unsigned int code1 : 2;
    unsigned int code2 : 2;
    unsigned int code3 : 8;
} prcode;
// 赋值方式
prcode.code1 = 0;
prcode.code2 = 3;
prcode.code3 = 102;

举个实际使用的例子，我们需要在屏幕上表示一个方框，假设方框具有如下属性：

• 方框是透明或者不透明的
• 方框的填充色：黑、红、绿、黄、蓝、紫、青、白
• 边框可见或隐藏
• 边框颜色与填充色使用相同的调色板
• 边框样式：实线、虚线或者点线

struct box_props {
    bool opaque                : 1;
    unsigned int fill_color    : 3;
    unsigned int               : 4;
    bool show_border           : 1;
    unsigned int border_color  : 3;
    unsigned int border_style  : 2;
    unsigned int               : 2;
};

对齐特性（C11）

在我们的系统中，double的对齐值是8，这意味着地址的类型对齐可以被8整除，以0或8结尾的十六进制地址可被8整除。因为char的对齐值是1，所以对于普通的char类型变量，编译器可以使用任何地址。

第十六章 C预处理器和C库

翻译程序的第一步

第一，编译器把源代码中出现的字符映射到源字符集，该过程处理多字节字符和三字节字符——字符扩展让C更加国际化。
第二，编译器定位每个反斜杠后面跟着换行符的实例，并删除它们，即把两个物理行physical lien转换为一个逻辑行logical line。
第三，编译器把文本划分为预处理记号序列、空白序列和注释序列。

执行完这些之后，程序已经准备好进入预处理阶段，预处理器查找一行中以#号开始的预处理指令。

明示常量：#define

#define预处理器指令和其他预处理器指令一样，以#号作为一行的开始：

#define TWO 2   /* 明示常量 */
#define FOUR TWO*TWO
#define PX printf("X is %d.\n", x)
#define FMT "X is %d.\n"

每行#define都由三部分组成：

• #define指令本身
• 选定的缩写（也叫做宏），有些宏代表值（类对象宏），还有些宏是类函数宏
• 替换列表/替换体

一旦预处理器在程序中找到宏的实例后，就会用替换体代替该宏，从宏变成最终替换文本的过程被称之为宏展开macro expansion。一般而言，预处理器在发现程序中的宏后，会用宏等待的替换文本进行替换，如果替换的字符串中还包含宏，会继续替换这些宏。唯一例外的是双引号中的宏。

字符串与字符常量

#define HAL 'Z' /* 定义字符常量 */
#define HAP "Z  /* 定义字符串(Z\0) */

记号

从技术角度来看，可以把宏的替换体看成是记号token型字符串，而不是字符型字符串。

#define FOUR 2*2 /* 一个记号: 2*2 */
#define SIX 2 * 3 /* 三个记号: 2、*、3 */

重定义常量

假设我们先把LIMIT定义为20，然后在该文件中又把它定义为25，这个过程称为重定义常量 ，除非新定义和旧定义相同，否则有些实现可能会将其视为错误。如果确实需要重定义常量，使用const关键字和作用域规则会更容易些。

在#define中使用参数

在#define中使用参数可以创建外形和作用与函数类似的类函数宏，类函数宏定义的圆括号中可以有一个或多个参数，随后这些参数出现在替换体中：

// 定义宏
#define SQUARE(X) X*X

// 使用宏
z = SQUARE(2);

宏定义的陷阱

以上面定义的SQUARE宏为例：

int x = 5;
printf("The result is %d.\n", SQUARE(x+2));

输出的结果是17，原因在于宏不做计算，只处理字符序列，因此实际的结果是x+2*x+2。

注意一般情况不要在宏中使用递增或递减运算符，但是++x可作为函数参数。

用宏参数创建字符串：#运算符

#define PSQR(x) printf("The square of " #x " is %d.\n", ((x)*(x))

预处理粘合符：##运算符

#define XNAME(n) x ## n
int XNAME(1) = 14; // 等价于int x1 = 14;

变参宏：...和__VA_ARGS__

#define PR(...) printf(__VA_ARGS__)

宏和函数的选择

有些编程任务既可以用带参数的宏完成，也可以用函数完成。使用宏的话比普通函数复杂，稍有不慎就会产生器官的副作用。

从本质上将，宏和函数的选择其实是时间和空间的权衡，宏会生成内联代码，即在程序中生成语句。如果调用20次宏，就会在程序中插入20行代码；如果调用函数20次，程序中只有一份函数语句的副本，因此节省了空间。不过程序的控制必须跳转至函数内，然后再返回主调函数，这显然比内联代码花费更多的时间。

宏有一个优点是不需要担心变量类型（因为宏处理的是字符串而非实际的值）。

C99提供了第3种可替换的方法——内联函数，对于简单的函数，程序员常使用宏，如：

#define MAX(X,Y) ((X) > (Y) ? (X) : (Y))
#define ABS(X) ((X) < 0 ? -(X) : (X))
#define ISSIGN(X) ((X) == '+' || (X) == '-' ? 1 : 0)

使用宏时需注意：

• 宏名不允许有空格，但是在替换字符串中可以有空格
• 用圆括号把宏的参数和整个替换体括起来，这样能确保被括起来的部分在传递给宏函数表达式时也能正确地展开
• 用大写字母表示宏函数和宏常量，这可以提醒程序员注意宏可能产生的副作用
• 如果打算用宏来加快程序的运行速度，那么首先要确定使用宏和使用函数是否会产生较大差异。在程序中只是用一次的宏无法明显减少程序的运行时间，在嵌套循环中使用宏更有助于提高效率

文件包含：#include

当预处理器发现#include指令时，会查看后面的文件名并把文件的内容包含到当前文件中，即替换源文件中的#include指令。

#include <stdio.h> // 文件名在尖括号中
#include "mystuff.h" // 文件名在双引号中

在UNIX系统中，尖括号告诉预处理器在标准系统目录中查找该文件，双引号告诉粗护理期首先在当前目录中
（或文件名中指定的其他目录）查找该文件，如果未找到再查找标准系统目录：

#include <stdio.h>       // 查找系统目录
#include "hot.h"         // 查找当前工作目录
#include "/usr/biff/p.h" // 查找/usr/biff/目录

头文件示例

• 头文件中一般包含：常量定义、结构声明、类型定义和函数原型等
• 通常需要使用#ifndef和#define来防止多重包含头文件
• 使用头文件时必须编译和链接对应的源代码文件

头文件一般包含的内容为：

• 明示常量：EOF、NULL和BUFSIZE等
• 宏函数
• 函数声明
• 结构模板定义
• 类型定义

其他指令

常用的宏指令

• #undef用于取消已定义的#define指令
• 条件编译：#ifdef、#else和#endif

#ifdef MAVIS
    #include "horse.h" // 如果已经用#define定义了MAVIS，则执行下面的指令
    #define STABLES 5
#else
    #include "cow.h" // 如果没有定义MAVIS，则执行下面的指令
    #define STABLES 15
#endif

• 条件编译#ifndef同#ifdef指令类似，也可以和#else、#endif一起使用，只不过逻辑相反
• #if和#elif

预定义宏

C99标准提供一个名为__func__的预定义标识符，它展开为一个代表函数名的字符串（该函数包含该标识符）。那么，__func__必须具有函数作用域，而从本质上看宏具有文件作用域，因此__func__是C语言的预定义标识符，而非预定义宏。

#line、#error和#pragma

#line指令重置__LINE__和__FILE__宏报告的行号和文件名。

#line 1000 //当前行号重置为1000
#line 10 "cool.c" //行号重置为10，文件名重置为cool.c

#error可以让预处理器发出一条错误指令，编译过程应该中断：

#if __STDC__VERSION != 201112L
#error Not C11
#endif

#pragma把编译器指令放入源代码中，例如在开发C99时，可以使用下面的编译指示pragma让编译器支持C9X：

#pragma c9x on

内联函数

通常函数调用都有一定的开销（因为函数的调用过程包括建立调用、传递参数、跳转到函数代码并返回）。使用宏使代码内联，可以避免这样的开销。创建内联函数的定义有多种方法，标准规定具有内部链接的函数可以成为内联函数，还规定了内联函数的定义与调用该函数的代码必须在同一个文件中。最简单的方法是使用函数说明符inline和存储类别说明符static，通常内联函数应定义在首次使用它的文件中。

#include <stdio.h>
inline static void eatline() // 内联函数定义/原型
{
    while (getchar() != '\n')
        continue;
}

int main()
{
    ...
    eatline();      //函数调用
    ...
}

C库

访问C库

• 自动访问：在一些系统中，只需要编译程序就可使用一些常用的库函数
• 文件包含：如果函数被定义为宏，那么可以通过#include指令包含定义宏函数的文件
• 库包含：在编译或链接程序的某些截断，可能需要指定库选项。即使在自动检查标准库的系统中，也会有不常用的函数库，必须通过编译时选项显式指定这些库。

头文件提供函数声明或原型，库选项告诉系统到哪里查找函数代码。

数学库

math.h头文件提供了很多有用的数学函数的原型。

类型变体

基本的浮点型数学函数接受double类型的参数，并返回double类型的值。当然也可以用float或long double类型的参数传递给这些函数，它们仍然能正常工作，因为这些类型的参数会被转换成double类型。

这种做法很方便但不是最好的处理方式，如果不需要双精度，那么用float类型的单精度值来计算会更快些，而且把long double类型的值传递给double类型的形参会损失精度，形参获得的值可能不是原来的值。

C标准专门为float类型和long double类型提供了标准函数，即在原函数名前加上f或l前缀。sqrtf()是sqrt()的float 版本，sqrtl()是sqrt()的long double版本。

tgmath.h库（C99）

C99标准提供的tgmath.h头文件中定义了泛型类型宏，如果在math.h中为一个函数定义了3中类型（float、double和long double）的版本，那么tgmath.h文件就创建一个范型类型宏，与原来double版本的函数名同名。
如果包含了tgmath.h，要调用sqrt()函数而不是sqrt()宏，可以用圆括号把调用的函数名括起来：

#incldue <tgmath.h>
...
float x = 44.0;
double y;
y = sqrt(x);   // 调用宏，所以是sqrtf(x)
y = (sqrt)(x); // 调用函数sqrt()

通用工具库

exit()和atexit()函数

main()函数返回系统时会自动调用exit()函数，ANSI标准新增了一些不错的功能，其中最重要的是可以指定在执行exit()时调用的特定函数。atexit()函数通过退出时注册被调用的函数提供这种功能，它接受一个函数指针作为参数。

同golang中的defer()函数类似，atexit()函数会在调用exit()时执行注册函数列表中的函数，在这个列表中至少可以放32个函数，执行顺序与列表中的函数顺序相反（最后添加的函数最先执行）。

qsort()函数

对较大型的数组而言，“快速排序”方法是最有效的排序算法之一，它把数组不断分成更小的数组，直到变成单元素数组。在C实现的名称是qsort()：

void qsort(void *base, size_t nmemb, size_t size, int (*compar)(const void *, const void *));

断言库

assert的用法

assert.h头文件支持的断言库是一个用于辅助调试程序的小型库，它由assert()宏组成，接收一个整形表达式作为参数。如果表达式求值为假（非零），assert()宏就在标准错误流stderr中写入一条错误信息，并调用abort()函数来终止程序。

• assert()函数可以自动标准文件和出问题的行号
• 有一种无需更改代码就能开启或关闭assert()的机制，如果认为已经排除了程序的bug，只需将#define NDEBUG写在包含assert.h的位置前面。

_Static_assert(C11)

C11新增了一个特性：_Static_assert声明，可以在编译时检查assert()表达式，因此assert()可以导致正在运行的程序中止，而_Static_assert()可以导致程序无法通过编译。

string.h库中的memcpy()和memmove()

不能把一个数组赋值给另外一个数组，所以需要通过循环把数组中每一个元素赋值给另一个数组相应的元素。**有一个例外是我们可以使用strcpy()和strncpy()函数来处理字符数组，memcpy()和memmove()函数提供类似的方法来处理任意类型的数组。

void *memcoy(void * restric s1, const void * restrict s2, size_t n);
void *memmove(void *s1, const void *s2, size_t n);

这两个函数都从s2指向的位置拷贝n字节到s1指向的位置，而且都返回s1的值。所不同的是，memcpy()的参数待关键字restrict，即memcpy()假设两个内存区域之间没有重叠；而memmove()不作这样的假设，所以拷贝过程类似于先把所有字节拷贝到一个临时缓冲区，然后再拷贝至最终目的地，如果使用memcpy()时两区域出现重叠则行为是未定义的。

可变参数stdarg.h

stdarg.h头文件为函数提供了一个接受可变数量参数的功能，必须按如下步骤进行：

• 提供一个使用省略号的函数原型
• 在函数定义中创建一个va_list类型的变量
• 用宏把该变量初始化为一个参数列表
• 用宏访问参数列表
• 用宏完成清理工作

// 函数原型
void f1(int n, ...);

// double sum(int lim,...)
{
    va_list ap;        //声明一个存储参数的对象
    va_start(ap, lim); //把ap初始化为参数列表
    
    //检索参数
    double tic;
    int toc;
    ...
    tic = va_arg(ap, double);
    toc = va_arg(ap, int);
    
    va_end(ap); //清理工作
}

第十七章 高级数据表示

从数组到链表

理想的情况是用户可以不确定地添加数据直到用完内存量，而不应该先指定要输入多少项，也不用让程序分配多余的空间。

这样我们会引入另外一个麻烦：每次添加数据时都需要调用一次malloc()，而且不同的数据分配到的内存块是不连续的，因此我们需要存储多个指针指向每一个单独存储的数据结构。

有一种较好的方法是每次使用malloc()为新结构分配空间，同时也为新指针分配空间（即我们需要另一个指针来跟踪新分配的指针）。我们可以重新定义结构来解决这个问题，即每个结构中包含指向next结构的指针，当创建新结构时，可以把该结构的地址存储在上一个结构中，以film数据结构为例：

#define TSIZE 45 /* 存储的电影名数组大小 */
struct film {
    char title[TSIZE];
    int rating;
    struct film * next;
}

虽然结构不能含有与本身类型相同的数据结构，但是可以含有指向同类型结构的指针，这种定义是定义链表linked list的基础，链表中的每一项都包含着在何处能找到下一项的信息。

链表

使用链表

下面的程序首先构建了一个链表，把用户输入的数据存储在链表中，其次显示链表。

/* film2.c -- 使用结构链表 */
#include <stdio.h>
#include <stdlib.h> /* malloc() */
#include <string.h> /* strcpy() */
#define TSIZE 45    /* 存储片名的数组带下 */

struct film {
    char title[TSIZE];
    int rating;
    struct film * next; /* 指向链表中下一个结构 */
};
char * s_gets(char * st, int n);

int main(void)
{
    struct film * head = NULL;
    struct film * prev, *current;
    char input[TSIZE];

/* 收集并存储信息 */
    puts("Enter first movie title:");
    while (s_gets(input, TSIZE) != NULL && input[0] != '\0') /* 如果用户通过键盘模拟EOF或输入一行空行，将退出循环 */
    {
        /* 如果用户进行输入，程序就分配一个结构的空间，并将其地址赋给指针变量current */
        current = (struct film *) malloc(sizeof(struct file));
        /* 链表中第1个结构的地址应该存储在指针变量head中，随后每个结构的地址应该存储在其前一个结构的next成员中 */
        if (head == NULL) /* 第一个结构 */
            head = current
        else 
            prev->next = current;
        current->next = NULL; /*  */
        strcpy(current->title, input);
        puts("Enter your rating <0-10>:");
        scanf("%d", &current->rating);
        while (getchar() != '\n')
            continue;
        puts("Enter next movie title(empty line to stop)");
        prev = current;
    }
    
    /* 显示电影列表 */
    if (head == NULL)    /* 访问指针前先确保它为非空指针 */
        printf("No data entered. ");
    else
        printf("Here is the movie list:\n");
    current = head;  /* current表示当前指向的film指针 */
    while (current != NULL)
    {
        printf("Movie: %s Rating: %d\n",
            current->title, current->rating);
        current = current->next;
    }
    /* 完成任务，释放已分配的内存 */
    current = head;
    while (current != NULL)
    {
        current = head;
        head = current->next;
        free(current);
    }
    printf("Bye!\n");
    
    return 0;
}

char * s_gets(char * st, int n)
{
    char * ret_val;
    char * find;
    
    ret_val = fgets(st, n, stdin);
    if (ret_val)
    {
        find = strchar(st, '\n');   // 查找换行符
        if (find)
            *find = '\0';           // 如果地址不是NULL，则在此处放置一个空字符
        else
            while (getchar() != '\n')
                continue;          // 处理剩余输入行
    }
    return ret_val;
}

创建链表包括下面三步：

• 使用malloc()为结构分配足够的空间
• 存储结构的地址
• 把当前信息拷贝到结构中

抽象数据类型ADT

“类型”特指两类信息：属性和操作。

计算机科学领域开发了一种定义新类型的好方法，用3个步骤完成从抽象到具体的过程：

1. 提供类型属性和相关操作的抽象描述。这些描述既不能依赖特定的实现，也不能依赖特定的编程语言。这种正式的抽象描述被称为抽象数据类型ADT。
2. 开发一个实现ADT的编程接口，即指明如何存储数据和执行所需操作的函数。例如在C中可以提供结构定义和操作该结构的函数原型，需要使用该新类型的程序员可以使用这个借口进行编程。
3. 编写代码实现接口。这一步至关重要，但是使用该新类型的程序员无须了解具体的实现细节。

1.建立抽象

对于链表而言，首先它应该能存储一系列的项，并且这些个项能以某种方式排列，其次它应该提供某些操作，如在链表中添加新项等：

• 初始化一个空链表
• 在链表末尾添加一个新项
• 确定链表是否为空
• 确定链表是否已满
• 确定链表中的项数
• 访问链表中的每一项执行某些操作，如显示该项

对于电影项目而言暂时不需要其他操作，但是一般的链表还应该包含如下操作：

• 在链表的任意位置插入一个项
• 移除链表中的一个项
• 在链表中检索一个项（不改变链表）
• 用另一个项替换链表中的一个项
• 在链表中搜索一个项

在电影项目中，我们采用一种简化的链表作为抽象数据类型，总结如下：

类型名：   简单链表
类型属性： 可以存储一系列项
类型操作： 
           -初始化链表为空
           -确定链表为空
           -确定链表已满
           -确定链表中的项数
           -在链表末尾添加项
           -在链表末尾添加项
           -遍历链表，处理链表中的项
           -请空链表

下面的工作就是为开发简单链表ADT开发一个C接口。

2.建立接口

接口设计应尽量与ADT的描述保持一致，因此应该使用某种通用的Item类型而非一些特殊类型比如int或者struct film，可以使用C的typedef来定义所需的Item类型。

这样做的好处在于，如果以后需要其他数据形式的链表，可以重新定义Item类型，不必更改其余的接口定义。

#define TSIZE 45 /* 存储电影名的数组大小 */
struct film
{
    char title[TSIZE];
    int rating;
};
typedef struct film Item;

接下来确定如何存储这种类型的项：

typedef struct node
{
    Item item;
    struct node * next;
} Ndoe;
typedef Node * List;

应该着重理解下面的声明创建了一个链表，而不是一个指向节点的指针或者一个结构：

List movies;

使用该类型的程序员只需要知道使用InitializeList()来初始化链表即可，不必了解背后的实现细节，接口设计人员可以在函数原型前面提供如下注释：

/* 操作：初始化一个链表 */
/* 前提条件：plist指向一个链表 */
/* 后置条件：该链表初始化为空 */
void InitiqalizeList(List * plist);

因此调用方式为：

InitializeList(&movies);

在设计接口的过程中，我们应该把类型定义和函数原型放在一个头文件中，该文件应该提供程序员使用该类型所需的所有信息。在头文件中把组成函数名的每个单词的首字母大写，以这种方式表明这些函数是接口包的一部分。

/* list.h--简单链表类型的头文件 */
#ifndef LIST_H_
#define LIST_H_
#include <stdbool.h>

/* 特定程序的声明 */

#define TSIZE    45 /* 存储电影名的数组大小 */
struct film
{
    char title[TSIZE;
    int rating;
};

/* 一般类型定义 */
typedef struct film Item;

typedef struct node
{
    Item item;
    struct node * next;
} Node;

typedef Node * List;

/* 函数原型 */

/* 操作：初始化一个链表 */
/* 前提条件：plist指向一个链表 */
/* 后置条件：该链表初始化为空 */
void InitiqalizeList(List * plist);

/* 操作：确定链表是否为空 */
/* 后置条件： 为空返回true */
bool ListIsEmpty(const List *plist);

/* 操作：确定链表是否已满 */
bool ListIsFull(const List *plist);

/* 操作：确定链表中的项数 */
unsigned int ListItemCount(const List *plist);

/* 操作：在链表的末尾添加项 */
bool AddItem(Item item, List * plist);

/* 操作：把函数作用域链表中的每一个项 */
void Traverse(const List *plist, void(*pfun)(Item item));

/* 操作：释放了为链表分配的内存，将链表设置为空 */
void EmptyTheList(List * plist);

#endif

注意：

• 只有InitializeList()、AddItem()和EmptyTheList()函数需要修改链表，从技术角度上看只有他们需要传递指针参数。为了提高易用性，减轻用户负担，所有函数都使用指针参数
• 我们可以通过const List * plist作为形参来防止函数修改链表

队列ADT

1.定义队列抽象数据类型

队列queue是具有两个特殊属性的链表：

• 新项只能添加到链表的末尾
• 只能从链表的开头移除项
  它本身是一种先进先出first in first out, FIFO的数据形式，下面我们给出非正式的抽象定义：

类型名：   队列
类型属性： 可以存储一系列项
类型操作： 
           -初始化队列为空
           -确定队列为空
           -确定队列已满
           -确定队列中的项数
           -在队列末尾添加项
           -在队列开头删除或者恢复项
           -请空队列

2.实现接口数据表示

一种可靠的方法是使用链表，相比于使用数组的好处是删除首项时不需要移动其余元素，只需重置头指针指向新的首元素即可：

# 整数队列
typedef int Item;

typedef struct node
{
    Item item;
    struct node * next;
} Node;

typedef struct queue
{
    Node * front;  /* 指向队列首项的指针 */
    Node * rear;   /* 指向队列尾项的指针 */
    int items;     /* 队列中的项数 */
} Queue;

注意Queue是一个内含3个成员的结构，因此用指向队列的指针作为参数比直接使用队列作为参数节省了时间和空间。

3.queue.h接口头文件

/* queue.h --Queue的接口 */
#ifndef _QUEUE_H_
#define _QUEUE_H_
#include <stdbool.h>

// Item类型的定义
typedef int Item;

# define MAXQUEUE 10 // 队列最大长度

typedef struct node
{
    Item item;
    struct node * next;
} Node;

typedef struct queue
{
    Node * front;  /* 指向队列首项的指针 */
    Node * rear;   /* 指向队列尾项的指针 */
    int items;     /* 队列中的项数 */
} Queue;

// 初始化队列
void InitializeQueue(Queue * pq);

// 检查队列是否已满
bool QueueIsFull(const Queue * pq);

// 检查队列是否为空
bool QueueIsEmpty(const Queue * pq);

// 确定队列中的项数
int QueueItemCount(const Queue * pq);

// 在队列末尾添加项
bool EnQueue(Item item, Queue * pq);

// 从队列开头添加项
bool DeQueue(Item *pitem, Queue * pq);

// 清空队列
void EmptyTheQueue(Queue * pq);

#endif

4.接口实现函数

void InitializeQueue(Queue * pq)
{
    pq->front = pq->read = NULL;
    pq->items = 0;
}

void QueueIsFull(const Queue * pq)
{
    return pq->items == MAXQUEUE;
}

bool QueueIsEmpty(const Queue * pq)
{
    return pq->items == 0;
}

int QueueItemCount(const Queue * pq)
{
    return pq->items;
}

// 把项添加到队列末尾
// 1) 创建一个新节点
// 2) 把项拷贝到节点中
// 3) 设置节点的next为NULL, 表明该节点是最后一个节点
// 4) 设置当前节点的next指向新节点，把新节点链接到队列中
// 5) 把rear指针指向新节点，以便找到最后的节点
// 6) 项数 + 1

bool EnQueue(Item item, Queue * pq)
{
    Node * pnew;
    
    if (QueueIsFull(pq))
        return false;
    pnew = (Node *)malloc(sizeof(Node));
    if (pnew==Null)
    {
        fprintf(stderr,"Unable to allocate memory!\n");
        exit(1);
    }
    CotyToNode(item, pnew);
    pnew->next = NULL;
    if (QueueIsEmpty(pq))
        pq->front = pnew;
    else 
        pq->real->next = pnew;
    pq->rear = pnew;
    pq->items++;
    
    return true;
}

static void CopyToNode(Item item, Node * pn)
{
    pn->item = item;
}

bool DeQueue(Item * pitem, Queue * pq)
{
    Node * pt;
    
    if (QueueIsEmpty(pq))
        return false;
    CopyToItem(pq->front, pitem);
    pt = pt->front
    pq-> front = pq->front->next;
    free(pt);
    pq->items--;
    if (pq->items == 0)
        pq->rear = NULL;
    return true;
}

void EmptyTheQueue(Queue * pq)
{
    Item dummy;
    while (!QueueIsEmpty(pq))
        DeQueue(&dummy, pq);
    
}

链表和数组

1.插入和删除元素

在数组中插入元素必须移动其他元素腾出空位插入新元素，新插入的元素离数组开头越近，要被移动的元素越多。然而在链表中插入节点，只需给两个指针赋值。类似的，从链表中删除节点只需要重新设置一个指针并释放被删除节点占用的内存即可。

2.如何访问元素

对于数组而言，可以使用数组下标直接访问该数组中的任意元素，这叫做随机访问random access。对于链表而言，必须从链表首节点开始，逐个节点移动到要访问的节点，这叫做顺序访问sequential access。
对于一个排序的列表，用二分查找binary search比顺序查找要好得多。首先把待查找的项称为目标项，而且假设列表中的各项按字母排序，然后比较列表的中间项和目标项，如果两者相等则查找结束；假设目标项在列表中且中间项排在目标项前面，则目标项一定在后半部分，反之同理。这种做法可以保证下次查找的范围只有列表的一般。

假设有127个项，但是二分查找最多只需要用7次比较。项数越多时越能体现二分查找的优势。

3.选择数据结构的思路

选择何种数据结构一般取决于具体的问题，如果因频繁地插入和删除项导致经常调整大小，而且不需要经常查找，选择链表更好。如果只是偶尔插入或删除项，但是经常进行查找，使用数组更好。如果需要一种既支持频繁插入和删除项又支持频繁查找的数据形式，应该选择二叉查找树。

二叉查找树

二叉查找树是一种结合了二分查找策略的链接结构。二叉树的每个节点都包含一个项和两个指向其他节点（子节点）的指针。

二叉查找树

如果需要在二叉树查找一个目标项，如果目标项在节点项的前面则只需要查找子树；如果目标项在节点项的后面则查找右子树，每次都能拍出掉一半可能的匹配项。

1.二叉树ADT

类型名：   二叉查找树
类型属性： 二叉树要么是空节点的集合（空树），要么是有一个根节点的节点集合
           每个节点都有两个子树，叫做左子树和右子树
           每个子树本身也是一个二叉树或者空树
           二叉查找树是一个有序的二叉树，每个节点包含一个项
           左子树的所有项都在根节点项的前面，右子树的所有项都在根节点项的后面
类型操作： 初始化数为空
           确定树是否为空
           确定树是否已满
           确定树中的项数
           在树中添加一个项
           在树中删除一个项
           在树中查找一个项
           在树中访问一个项
           清空树

2.接口

typedef SOMETHING Item;

typedef struct trnode
{
    Item item;
    struct trnode * left;
    struct trnode * right;
} Trn;

typedef struct tree
{
    Trnode * root;
    int size;
} Tree;

我们要开发一个维护Nerfville宠物俱乐部的花名册，每一项都包含宠物名和宠物的种类。

/* tree.h --二叉查找树 */
#ifndef _TREE_H_
#define _TREE_H_
#include <stdbool.h>

/* 根据具体情况重新定义 Item */
#define SLEN 20
typedef struct item
{
    char petname[SLEN];
    char petkind[SLEN];
} Item;

#define MAXITEMS 10

typedef struct trnode
{
    Item item;
    struct trnode * left;
    struct trnode * right;
} Trn;

typedef struct tree
{
    Trnode * root;
    int size;
} Tree;

void InitializeTree(Tree * ptree);

bool TreeIsEmpty(const Tree * ptree);

bool TreeIsFull(const Tree * ptree);

int TreeItemCount(const Tree * ptree);

bool AddItem(const Item * pi, Tree * ptree);

// 在树中查找一个项
bool InTree(const Item * pi, const Tree * ptree);

bool DeleteItem(cosnt Item * pi, Tree * ptree);

// 把函数应用于树中的每一项
void Traverse(const Tree * ptree, void(*pfun)(Item item));

void DeleteAll(Tree * ptree);

#endif

3.添加项

bool AddItem(const Item * pi, Tree * ptree)
{
    Trnode * new_node;
    if (TreeIsFull(ptree))
    {
        fprintf(stderr, "Tree is full\n");
        return false;
    }
    if (SeekItem(pi, ptree).child != NULL)
    {
        fprintf(stderr, "Attempted to add duplicate item\n");
        return false;
    }
    new_node = MakeNode(pi);  /* 指向新节点 */
    if (new_node == NULL)
    {
        fprintf(stderr, "Couldn't create node\n");
        return false;
    }
    /* 成功创建了一个新节点 */
    ptree->size++;
    if (ptree->root == NULL)
        ptree->root = new_node;
    else
        AddNode(new_node, ptree->root);
    return true;
}

SeekItem()、MakeNode()和AddNode()函数不是Tree类型公共接口的一部分，它们是隐藏在tree.c文件中的静态函数，处理实现的细节（如节点、指针和结构），不属于公共接口。

// 参数是指向新项的指针，返回值是指向新节点的指针
static Trnode * MakeNode(const Item * pi)
{
    Trnode * new_node;
    new_node = (Trnode *) malloc(sizeof(Trnode));
    if (new_node != NULL)
    {
        new_node->item = *pi;
        new_node->left = NULL;
        new_node->right = NULL;
    }
    return new_node;
}

// 确定新节点的位置，然后添加新节点
// 其中ToLeft()和ToRight()函数依赖于Item本身的性质，用于比较两个Item的顺序关系
static void AddNode(Trnode * new_node, Trnode * root)
{
    if (ToLeft(&new_node->item, &root->item))
    {
        if (root->left == NULL)
            root->left = new_node;
        else
            AddNode(new_node, root->left);
    } 
    else if (ToRight(&new_node->item, &root->item))
    {
        if (root->right == NULL)
            root->right = new_node;
        else 
            AddNode(new_node, root->right);
    }
    else
    {
        fprintf(stderr, "location error in AddNode()\n");
        exit(1);
    }
}

4.查找项

AddItem()、InItem()和DeleteItem()都需要使用SeekItem()函数进行查找，DeleteItem()函数需要直接待删除项的父节点，以便在删除子节点后更新父节点指向子节点的指针。设计SeekItem()函数返回的结构包含两个指针：一个指针包含项的节点；一个指针指向父节点：

typedef struct pair {
    Trnode * parent;
    Trnode * child;
} Pair;

static Pair SeekItem(const * pi, const Tree * ptree)
{
    // 从root节点开始查找
    Pair look;
    look.parent = NULL;
    look.child = ptree->root;
    
    if (look.child == NULL)
        return look;
    while (look.child != NULL)
    {
        if (ToLefe(pi, &(look.child->item)))
        {
            look.parent = look.child;
            look.child = look.child->left;
        }
        else if (ToRight(pi, &(look.child->item)))
        {
            look.parent = look.child;
            look.child = look.child->right;
        }
        else 
            break;  /* 如果前两种情况都不满足，则必定相等 */
    }
    return look;
}

有了SeekItem()函数后，编写InTree()公共接口就比较简单了：

bool InTree(const Item * pi, cosnt Tree * ptree)
{
    return (SeekItem(pi, ptree).child == NULL) ? false : true;
}

5.删除项

删除项是最复杂的任务，因为必须连接剩余的子树形成有效的树：

• 如果待删除的节点没有子节点（即叶子节点leaf）,这种情况下只需要将父节点中的指针重置为NULL
• 删除带有一个子节点的节点时需要把被删除节点父节点中存储该节点的地址更新为该节点子树的地址
• 删除有两个子树的节点时，需要牢记树的基本设计：左子树的所有项都在父节点前面

删除项

现在删除项可以分成两个任务：一个是把特定项与待删除节点关联；一个是删除节点。为了修改指针，代码必须把该指针的地址传递给执行删除函数的任务。

static void DeleteNode(Trnode **ptr)
/* ptr是指向目标节点的父节点指针成员的地址 */
{
    Trnode * temp;
    if ((*ptr)->left == NULL)
    {
        temp = *ptr;
        *ptr = (*ptr)->right;
        free(temp);
    }
    else if ((*ptr)->right == NULL)
    {
        temp = *ptr;
        *ptr = (*ptr)->left;
        free(temp);
    }
    else /* 被删除的节点有两个子节点 */
    {
        for (temp = (*ptr)->left; temp->right != NULL; temp = temp->right)
            continue;
        temp->right = (*ptr)->right;
        temp = *ptr;
        *ptr = (*ptr)->left;
        free(temp);
    }
}

该函数显式处理了3种情况：没有左子节点的节点、没有右子节点的节点。代码中用临时指针记录被删除节点的地址，被删除节点的父节点指针被重置后，程序会丢失被删除节点的地址。但是free()函数需要这个信息，所以先把指针的值存储在temp中。
有两个子节点时，先在for循环中通过temp指针从左子树的右半部分向下查找一个空位将右子树连接于此。然后再用temp保存被删除节点的位置。接下来，把左子树连接到被删除节点的父节点上，最后释放temp指向的节点。

bool DeleteItem(const Item * pi, Tree * ptree)
{
    pair look;
    look = SeekItem(pi, ptree);
    if (look.child == NULL)
        return false;
    if (look.parent == NULL) /* 删除根节点 */
        DeleteNode(&ptree->root);
    else if (look.parent->left ==look.child)
        DeleteNode(&look.parent->left);
    else 
        DeleteNode(&look.parent->right);
    ptree->size--;
    
    return true;
}

注意：公共接口函数DeleteItem()处理的是最终用户所关心的问题（项和树），而隐藏的DeleteNode()函数处理的是与指针相关的实质性任务。

6.遍历树

void Traverse(const Tree * ptree, void(*pfun)(Item item))
{
    if (ptree != NULL)
        InOrder(ptree->root, pfun);
}

static void InOrder(const Trnode * root, void(*pfun)(Item item))
{
    if (root != NULL)
    {
        InOrder(root->left, pfun);
        (*pfun)(root->item);
        InOrder(root->right, pfun);
    }
}

7.清空树

void DeleteAll(Tree * ptree)
{
    if (ptree != NULL)
        DeleteAllNodes(ptree->root);
    ptree-> root = NULL;
    ptree->size = 0;
}
static void DeleteAllNodes(Trnode * root)
{
    Trnode * pright;
    if (root != NULL)
    {
        pright = root->right;
        DeleteAllNodes(root->left);
        free(root);
        DeleteAllNodes(pright);
    }
}