存储分配管理

书中关于这方面举了两个例子，一个是从编译时就确定的固定大小的数组中采用栈的形式进行存储空间管理；另一个是举例库函数malloc的设计思想。关于使用栈的形式进行存储管理这里不赘述，详见Chapter 5.4，这里重点说一下malloc的设计思想。

 

尽管分配程序要为不同的对象分配存储空间，但程序中只会有一个存储分配程序，却要处理多种类型的请求，这样情况下有两个问题：1.如何在大多数机器上满足各种类型对象的对齐要求？2.使用什么样的声明可以使得分配程序能返回不同类型的指针，以此满足不同类型请求的处理？在这一方面，栈式存储管理的缺点立马就显现出来了。

 

malloc的设计思想很巧妙地解决了这两个问题。对齐方面，它使用联合（union）来满足对齐要求，代价是牺牲一些存储空间。第二个方 面，malloc的返回值的类型是void*，这样在调用malloc时显示进行类型转成所需要的指针类型即可，这样一来，malloc并不需要识别要申请的内存是什么类型，它只关心内存的总字节数。

 

另外，malloc不是从一个编译时就确定的固定大小的数组中分配空间，而是需要时向操作系统申请，并且是以空闲块链表的方式进行组织的。

 

    缓冲区

 

我现在感觉缓冲区的思想灰常重要，设计缓冲区可以减少和避免很多繁琐的操作，常见的就是频繁的IO操作。这一点我在写搜索引擎爬虫时将所爬取的网页写入网页库的时候体会尤其深刻，而本书的例程再一次加深了我对缓冲区的理解。

 

有时候，程序并不能确定已经读入的输入是否足够，除非超前多读一些输入。例如从输入行中读一些字符合成一个数字（可能是整型可能是浮点型）就是一例：首先 读取并去除前导空白，然后一个字符一个字符地读取，但是我们并不知道什么时候读取停止，例如输入字符“1314.521ahathinking”，我们必须读到字符‘a’才知道数字已经读取完毕。此时就导致最后有一个字符不属于当前所要读入的数，下回读取时就不能从字符a读取了，怎么办？这时，我们需要将其压回输入中，对代码其他部分而言就相当于没有读入该字符一样，如何压回输入？共享缓冲区便是一个好方法，即读取字符时先看缓冲区中是否有字符，如果有读取，如果没有再从输入中读取。实现见Chapter 4.3中getch和ungetch的实现。

 

类似的还有一例，就是Chapter 8.5中getc和putc的实现：从文件中读取或写入一个字符，源码中并不是每次都从文件中读写，这样的IO操作太频繁，而是每次读或写一大块内容放入缓冲区，每次先检查缓冲区剩余的字符个数，如果>0，则返回下一个字符指针，否则填充缓冲区。

 

值得一提的是，缓冲区的思想跟栈式的存储管理有点类似，栈式存储的那个大数组就相当于预先开辟的缓冲区。

 

    函数设计

 

关于函数设计，核心问题是如何分解要解决的问题，写出各个有独立功能的函数，通过练习该书中的例程（主要是Chapter 5与Chapter 6），你不但能体会到问题的合理分解会让程序看起来结构明朗，逻辑清晰；更能感到由此带来的模块独立的好处，只要接口设计良好，写每个函数都无需过多考虑其他东西，当所有分解的功能函数完成后，你会发现原本感觉一个复杂的问题就这样被Divide-and-Conquer了。

 

另外，对于每一个函数的设计都要认真思考。如getline函数的实现，读的过程中就该思考，如果这个函数让你来设计，你会如何设计？函数参数如何设计？ 返回类型如何定义？是像平常一样直接返回void类型还是跟据它将来可能的用途设计一个更为合理的返回类型？函数功能逻辑应如何实现？是上来就读取数据还是考虑去除输入行的前导空白？有没有意外情况？比如读到空行了怎么办？程序结构如何安排？是想来就写还是考虑程序结构可以更为简洁地表达？如何让程序更加 精炼？种种这些，其实都是需要我们用心去考虑的，不是就简单一个函数的问题，就像之前说的，虽然简单，但每个例子都很经典，值得我们去学习、更为重要的是 去思考！

 

    二叉树

 

在不知道单词表的情况下，统计输入中所有单词的出现次数，并分别按字母顺序和词频降序打印？你会如何设计？

 

Chapter 6.5例程让你感受到二叉树的强大，不但方便查找，而且单词本身就是放在正确的位置，而记录每个单词的节点位置指针使得按照词频的排序变得简单。干货，值得仔细揣摩。

 

    哈希

 

大家知道，宏是在预编译阶段进行文本扩展替换的，但你知道编译器是如何实现宏处理的吗？或者说宏处理器实现的核心机制是什么？类似地，编译器的符号表管理程序是如何实现的？

 

没错，就是哈希，Chapter 6.6的表查找例程给我们很好地启发，加深理解哈希的设计思想会有利于解决很多问题，不要不屑于，或许用到的时候就想不到，恰恰就是这样让我们感觉很简单的东西实现了一些让我们听起来是多么高深复杂的东西。

 

    可变参数列表的设计

 

这个本书在讲printf时候说到了可变参数列表是如何实现的，感觉这个应该了解下，现在用不到，或许将来工作就会用到了吧，有个概念先。

 

    位字段的妙用

 

当需要对某些信息进行编码时，例如对变量的状态进行编码（是否是关键字，是否是静态的等Chapter 6.9），对文件指针的状态进行编码（是读的状态还是写的状态，是否到达文件末，是否发生错误Chapter 8.5）等，我们往往会定义一个与相关位的位置对应的“屏蔽码”集合，或者利用位字段将几个属性集成到一个标识变量中来记录，从而节省存储空间（Chapter 6.9）。这样定义后，在程序中就可以使用位操作来验证相关的属性值了。

 

这类型的设计思想在库中用到的非常多，我们应该熟悉并学会使用。

 

    最后列举下几个经典问题

 

通过他们的实现来体会解答问题的算法设计思想，下面这几个题目在经典例程中都有对应。

 

可变长文本行排序（指针数组）、已知单词表统计词频（折半）、未知单词表统计词频并按字母顺序打印（二叉树）、未知单词表统计词频并按词频降序打印（二叉树、排序）、表查找程序（哈希、链表）

 

===================================================

 

编程风格

 

本节罗列一些个人感觉在读本书之后学到的一些小风格，小习惯，每一点举一个小例子。

 

程序中最好不要使用突兀的常量，此时应该使用宏定义，并给出注释，便于别人和自己阅读；另外宏定义中，如果是表达式，最好外围加括号（），如果是语句块，最好使用do { } while (0)。

#define MAXWORD 100 // 一行允许输入的最大字符数

#define BUFSIZE 1024

#define EOF (-1)

 

字符变量使用整型来表示，如int c; 因为字符变量存储时便是以整型存储的，使用整型表示也能避免不必要的问题。

int ch;

scanf("%c",&ch);

 

函数形参需传递数组时，可以直接将形参定义为指针类型；因为数组在作为参数传递时会由incomplete type转为pointer type。

void test(char s[], int n); // 将其直接定义如下

void test(char *s, int n);

 

集成数组、指针和地址的算术运算编写高效精炼的代码，如下例（可以尝试编写一些经典的库函数来练习，如字符串处理函数strcpy、strcmp等、内存 操作函数memset等），这方面的思想主要体现在对数组元素进行循环操作的时候。关于这方面有比较容易出错和被忽视的地方，详见博文：数组、指针和地址 运算：一个经典的小问题

char * strcpy(char * s1, const char * s2)

    {

        char * s = s1;

        while(*s1++ = *s2++);

        return s;

    }

 

如果使用动态申请，则申请后一定要判断是否申请成功，这是一个好习惯

char * ptr;

if((ptr = (char *)malloc(nbytes)) != NULL){...}

 

了解寄存器变量register与inline都属于“建议”性关键词，编译器未必这样做。注：只有局部自动变量和形参才可以定义为寄存器变量；对于循环控制变量及循环体内反复使用的变量均可定义为寄存器变量，循环计数是应用寄存器变量的最好候选者

 

活用位操作，例如在乘除法，取模操作中，见下面例子。关于这方面，详见文章二进制思考系列博文

i = 879 / 16; // 对比

i = 879 >> 4;

j = 562 % 32; // 对比

j = 562 & (0x1f);

 

编写递归函数时，static变量是个很有用的东西，能避免部分参数的传递。。这个就不举例了吧，编程的时候遇到递归稍微向这方面思考下就行

 

===================================================

 

经典例程

 

这里以中文版为参考，所罗列的例程只是个人认为比较经典的一部分，许多没有罗列的习题也是值得一做，有助于理解一些基础性东西（比如第一章的1-20有助于理解制表符，1-23有助于理解类似“ab\”cd”这样的特例字符串等）。

 

P21 读取一行字符串函数getline 以及书中后续的改进版本

 

P22 Exer-1-19 反正字符串reverse函数，这个函数很简单，但是它有一个不是那么简单的延伸版本（参见博文关于Reverse Words的思考及三种解法），当初在水木上看到有人推荐的K&R，也是因为这个延伸版本的一道面试题

 

P38 Exer-2-4 函数squeeze，详见博文三种方法实现的比较

 

P41 Exer-2-9求二进制1的个数，该题本博提供了三种方法作为对比，关键是做延伸，深入理解位操作的一些技巧以及由此衍生的重要数据结构bit-map的实现（见博文位索引），关于位操作我做了一个小总结：二进制思考系列文章

 

P51-P52 例程atoi和itoa函数，以及后续的改进版本，这两个函数需要考虑的细节比较多；shellsort函数的实现

 

P66函数getop函数以及用到的getch和ungetch函数，后两个函数很实用

 

P74 函数qsort的实现，达到拿来就能写的熟练不为过

 

P90 库函数strcpy，strcmp的实现及课后习题

 

P92 可变长文本行的排序实现，这个应该算很经典了，巧妙使用指针数组排序文本行

 

P102 函数指针的用途，根据排序的不同要求设计不同的函数接口

 

P119 已知单词表，统计关键词次数，采用指针方式实现的，干货，顺便复习折半查找

 

P121 自引用结构中例程，未知单词表，统计词频，按字母顺序打印，二叉树的巧用

 

P125 Exer-6-4未知单词表，统计词频，按词频降序打印，二叉树与排序的结合

 

P125 Chapter6.6表查找，体会链表、哈希的思想；宏处理器或编译器的符号表管理的实现机制

 

注：关于那些知识点方面（如声明与定义的区别。#define与const及typedef的区别等），本文就不罗列了，需要在编码过程中去体会。

 

欢迎批评补充。