公开课学习笔记-[哈佛]计算机科学CS50（六）

第13课 typedef声明，队列，位操作 -2011.11.1

利用图像隐藏信息方法：图形的某些像素颜色进行转换后，可以看到隐藏的文字或图像信息。对于图像文件，例如bmp文件，开始的字节有特殊的含义和格式，也就是container的格式，例如2-5字节是bfsize。通过查找这些特殊的字节，可以恢复损坏flash卡的图像文件。又例如JPEG文件，开头的四个字节为0A0B0C0D，可以检索这个特殊的标记。扫描时需要注意系统是Big-endian（0A0B0C0D）还是little-endian（0D0C0B0A）。

介绍typedef的用法，例如typdef uini8_t BYTE,通过这种方式，可以统一32bit和64bit计算机的内存放置方式。

链表的一个问题是不能似数组海洋随机访问元素。介绍LIFO的stack和FIFO的queue。下面是queue的一个例子。

struct queue{
	int member[100];
	int head;
	int size;
}

int pop(queue *q){
	...
	q->head = (q->head+1)%100;  //越界处理方式
	...
}

对于C语言，防止内存泄漏很重要，可以利用工具valgrind来进行检查，使用方式为：

valgrind -v --leak-check=full a.out

介绍位操作。移位操作，空出的位置会补0。例如1 << i 不同i（31-0），可以获取每个位的mask。对于大小写的差别是32，即0010 0000中第5bit不同而已，ASCII的设计还是很有考究。A（01000001）a（01100001），这样在大小写转换时可高效处理。

第14课 位操作符号、stack、Hash表和树结构 -2011.11.2

位操作有&、|、^、>> 、<<其中^是XOR，即1^0 = 1，0^1 =1, 0^0 = 0, 1^1 =0，是个很方便的位操作，例如有三块RAID（硬盘），其中第三块的数据是第一块^第二块，无论第一块或者第二块硬盘出现损坏，均可以通过第三块来进行恢复。记得以前有个pw传输的加密算法，将keyMD5之后和pw进行XOR操作，传输对对方，可进行pw的恢复。

stack（堆栈）是FILO。

对于大量数据的处理，hash是比较常用的方式。在数组中，可以达到O（logN）的效率，但是插入和删除，需要进行大量的copy，效率低下，而链表方式查询效率低。如果有存储有足够的空间，为元素计算一个hash key，可以在数组中立即定位，由于hash key会出现一样，则采用链表方式，效率为O(n/k)。例如整数，可以直接返回num的值，String的值可以是首字母（或者前几个字母）组成的int值，在Java中，提供hashCode的计算方式。

介绍树结构，root和leave的概念，二叉树结构，通过二叉树进行查询和添加元素。树结构很适合使用递归（recursion）方式。有一个字典的例子，采用树结合hash的方式，如图所示，其查询效率为O(m)，m为strlen(word)。

相关链接：我的与编程思想相关的文章