5、程序设计实践读书笔记

1、对于字符串，最常见的散列算法之一就是：逐个把字节加到已经构造的部分散列值的一个倍数上。乘法能把新字节在已有的值中散开来。这样，最后结果将是所有输入字节的一种彻底混合。根据经验，在对ASCII串的散列函数中，选择31和37作为乘数是很好的。P45

如下所示：

enum {MULTIPLIER = 31};
unsigned int hash(char *str)
{
	unsigned int h;
	unsigned char *p;
	h = 0;
	for(p = (unsigned int*)str; *p != '\0'; p++)
		h = MULTIPLIER * h + *p;
	return h % NHASH; //NHASH为表的大小
}

2、一旦数据结构安排好之后，代码将会自然地随之而来。首先是选择简单算法和数据结构的重要性，应该选择那些能在合理时间内解决具有预期规模的问题的最简单的东西。

3、几个经典句子：

sprintf(fmt, "%%%s", sizeof(buf) - 1);

******

int strcmp(char *s1, char *s2)
{
	while(*s1 == *s2)
	{
		if(*s1 == '\0') 
			return 0;
		s1++;
		s2++;
	}
	if(*s1 > *s2)
		return 1;
	else 
		return -1;
}

******

p = malloc(strlen(buf)+1);

******

struct Namval
{
	char *name;
	int value;
};

Namval htmlchars[] = {
	"zhou", 12,
	"hello", 13,
	"ftmd", 15,
};

4、map,vector。

5、在进行程序设计时，必须考虑的问题包括：

•界面：应提供哪些服务和访问？在这里要做的是提供一种统一而方便的服务，使用方便，有足够丰富的功能，而又不过多过滥以至无法控制。

•信息隐藏：哪些信息应该是可见的，哪些应该是私有的？一个界面必须提供对有关部件的方便访问方式，而同时又隐蔽其实现的细节。

•资源管理：谁负责管理内存或者其他有限的资源？这里的主要问题是存储的分配和释放，以及管理共享信息的拷贝等。

•错误处理：谁检查错误？谁报告？如何报告？如果检查中发现了错误，那么应该设法做哪些恢复性操作？

6、在低层检查错误，在高层处理它们。一般由调用程序决定如何处理错误，而不是由被调函数。

NaN:Not a Number

7、如果能把各种各样的异常值(如文件结束、可能的错误状态)进一步区分开，而不是用单个返回值把它们堆在一起，那当然就更好了。如果无法立刻区分出这些值，另一个可能的方法是返回一个单一的“异常”值，但是另外提供一个函数，它能返回关于最近出现的错误的更详细信息。

这也是在Unix和C标准库里采用的方法。在那里许多系统调用或库函数都在返回-1(表示错误)的同时给名为errno的变量设一个针对特定错误的编码值，随后用strerror就可以返回与各个错误编码关联的字符串。

异常最好是保留给那些真正无法预期的事件。

示例如下

#include <stdio.h>
#include <string.h>
#include <error.h>
#include <math.h>
//只有在C语言中才行
int main()
{
	double f;
	errno = 0;
	f = log(-1.23);
	printf("%f %d %s\n", f, errno, strerror(errno));
	return 0;
}

8、对减少排错时间能有所帮助的技术包括：好的设计、好的风格、边界条件测试、代码中的断言和合理性检查、防御性程序设计、设计良好的界面、限制全局数据结构以及检查工具等。

9、返回局部变量的地址可以说是延迟灾难的一个秘方。对于某些malloc和free的实现，两次释放同一块存储将会破坏内部的数据结构。

10、马尔可夫链。P48

由已知的文字序列生成新的序列。

该算法把每个短语分割为两个部分：一部分是由多个词构成的前缀，另一部分是只包含一个词的后缀。马尔可夫链算法能够生成输出短语的序列，其方法是依据(在我们的情况下)原文本的统计性质，随机性地选择跟在前缀后面的特定后缀。采用三个词的短语就能够工作得很好——利用连续两个词构成的前缀来选择作为后缀的一个词：

设置w1和w2为文本的前两个词

输出w1和w2

循环：

随机地选出w3，它是文本中w1w2的后缀中的一个

打印w3

把w1和w2分别换成w2和w3

重复循环

11、除法和求余数比乘法慢得多，如果可以用乘倒数的方法来代替除法，或者在除数是2的幂时用掩码操作代替求余，则确实可能得到性能改进。

12、一般地说，如果可以，尽可能以文件形式存储信息。

13、无论char的符号情况如何，必须把getchar的返回值存入一个int，以便和EOF作比较。

14、移位可以是算术的(符号位将在移位的过程中复制传播)，也可以是逻辑的(移位中空出的位被自动补0 )。

15、很少有机器允许int存储在奇数边界上，一般都要求占据n个字节的基本数据类型存放在n字节的边界上。例如，double一般是8个字节长，所以需要存储在8的倍数的地址上。

16、不要用char与EOF做比较。总使用sizeof计算类型和对象的值。决不右移带符号的值。你所用的数据类型应该足够大，足够存储你希望放在里面的值。位域对机器的依赖太强，无论如何都不应该用它。

17、我们更喜欢只使用那些对所有目标环境都是共同的特性。这样我们就能编译和测试所有代码。如果某些东西产生可移植性问题，我们不是增加条件性代码，而是设法重写代码，设法避免这些问题。

18、数据交换时用固定的字节序。如下所示，可以解决很多big_endian与little_endian的问题。

示例程序1

unsigned short x;
putchar(x >> 8);  //write high order
putchar(x & 0xFF); //write low order
//read back by byte
unsigned short y;
y = getchar() << 8; //Read high order
y |= getchar() & 0xFF; //Read low order

示例程序2

#include "stdio.h"
int main()
{
	unsigned long x;
	unsigned char *p;
	x = 0x11223344UL;
	p = (unsigned char *)&x;
	for (int i = 0; i < sizeof(unsigned long); i++)
	{
		printf("%x ", *p++);
	}
	printf("\n");
	return 0;
}

19、Unicode也带来了一个问题：字符不再能放进字节里。因此，Unicode文本也会遇到字节顺序问题的滋扰。为了避免这种状况，Unicode文档在程序间或者通过网络进行传递之前，通常都先行转换为一种称为UTF-8的字节流编码形式。每个16位字符被编码为1个、2个或3个字节的一个序列，专门用于传输。P166

20、追求可移植性的两种途径，即联合和交集。联合途径相当于为在每个目标系统上工作而写一个版本，利用条件编译一类的机制，把这些代码尽可能地汇集在一起。这种途径的缺点很多，它造成过多的代码，而且常常是很多非常复杂的代码。它很难更新，也很难测试。

交集途径是设法以一种形式写出尽量多的代码，使它能在每种系统上运行而不需要做任何修改。把无法逃避的系统依赖性封装在独立的源文件里，其作用就像是程序与基础系统之间的界面。交集方法也有缺点，包括可能存在性能方面，甚至特征方面的损失。但是从长远的观点看，这种途径的利大于弊。

21、一个正则表达式本身也是一个字符序列，它定义了一集能与之匹配的字符串。

22、快带排序的致使弱点：

    如果每次对基准值的选择都能将元素划分为数目差不多相等的两组，上面的分析就是正确的。但是，如果执行中经常出现不平均的划分，算法的运行时间就可能接近于按n2增长。

23、这里有一个基本原则：在错误发生的时候，库函数绝不能简单地死掉，而是应该把错误状态返回给调用程序，以便那里能采取适当的措施。另一方面，库函数也不应该输出错误信息，或者弹出一个会话框，因为这个程序将来可能运行在某种环境里，在那里这种信息可能干扰其他东西。

    总之，这本书写的深入浅出，浅入深出，非常值得一读。