《code reading》阅读笔记之三

第四章，C数据结构

1. 警惕for循环体内部对循环条件变量的操作；
2. 使用memset之类的函数时，对所操作内存的字节数最好不使用常量而使用sizeof;
3. 使用memcpy函数时，源和目的内存重叠或者源和目的内存的类型不符时，其结果未定义，使用前必须额外验证已避免此类情况；同时，结合第2点，sizeof的参数应该取目的地址
4. 尽量避免使用gets/strcpy/strcat/sprintf/vsprintf（容易导致缓存溢出的错误），用fgets/strncpy/strncat/snprintf/vsnprintf替换；
5. 在循环的实现中，对范围采用不对称边界的校验策略，即包括下限（＝），小于上限
6. c语言中指针的一种用法很是让我惊奇：用指针当数组用：struct vcol *pv = malloc(n*sizeof(struct vcol));cnt=pv[xx].cnt;除了在内存中的实际分配机理与数组不同之外，如果在栈中直接声明该结构的数组的话，cnt=pv[xx].cnt;这句在不同的情况下功能完全一样哦！而动态分配的情况下pv+=xx;cnt=pv->cnt;和上面那句话的作用也一样！换言之，动态分配的内存指针所指向的实际结构可以用数组形式来表征和操作（*就用一维数组来表征，**就用二维数组来表征,以此类推...）；
7. 栈，LIFO，经常用来处理语言中的括号匹配／undo命令／中断；
8. 抽象数据类型，ADT，通过提供一组接口将具体实现和使用隔离开来，对栈来说，重要的属性是栈指针：表明下一个要入栈或出栈（注意：二者是不同的！）的元素在栈中的位置，栈操作要注意的一个问题就是上溢出和下溢出；
9. 队列，FIFO，经常用来处理两个软件系统间的交互（如gui应用程序和window系统之间、操作系统和收到的网络数据包之间）以及软硬件系统间的交互（网卡、硬盘、打印机的请求和操作系统之间）；基本操作有两个：出队和入队；基本属性有两个：头指针（指向出队元素）和尾指针（指向入队元素）；出队和入队时需要防止两种溢出：入队时的上溢出（队列满状态，针对数组实现，即尾指针＋1＝头指针），出队时的下溢出（队列空，即头尾指针相同）
10. maps：在能预先确定内容和数量的前提下，map可以用基于下标的数组来实现，以追求高的存取效率；提到了表格驱动编程，来避免大量的if；如用包含key和函数指针的数据结构数组来作字典，通过key的匹配来调用不同的函数（简单一点的可以省略函数指针，但一样是流程化的操作）；另外，数组包含元素的数量可以用sizeof(x)/sizeof(x[0])来表示，这是一个编译时已经确定的常量；
11. hash:对一动态集合，要求支持三种操作：插入、删除和搜索；当集合内元素少时，可直接采用数组实现；当集合的可能元素数量相当巨大时，需要运用hash函数产生键，去确定相应值；这样做的目的是用经济的空间以较小的代价来存取元素；hash要避免或者解决的问题是碰撞：即两个元素产生同一个键；
12. C语言的隐喻：a>>3等同于a/8; a<<3等同于a*8;a & 7等同于a%8;
    
13. 对图而言，一直没有统一的实现，经常的实现方式有指针数组、链表等;鉴于在遍历图的元素时可能会出现循环，一个避免的手段时对已经访问过的节点置“已访问”的标志；