CS50 2013-Week5 学习笔记
本以为这节课很难。但是课中讲的Array、Linked List、Stack、Queue、Binary search tree、Hash table，刚好以前都看到过。
Array
前面课程中提到过。
比如int a[8];语句。 定义一个能存储8个整型数据的数组a，系统会为数组a 分配一片连续的存储空间（例如，1201~1232），数组中元素按下标从小到大排列，每个元素占用相应的4个字节。
另外，数组名a是常量，代表数组占用存储空间的起始地址（这里1201）。
随后，可以对数组元素赋值，如a[1] = 2;，将2写到地址1205对应的存储空间里。
这时候输出列表，发现第二个元素为2，其他的没赋值元素好奇怪，暂时没有弄清楚。如下图：
Linked List
首先，需要有一个指针指向列表的第一个元素，知道链表从哪儿开始的。
然后，每个元素除了数据域存储数据，还有指针域指向下一个元素。
然后，不需要连续的存储空间，只要有指针存储下一个元素的地址就行。
链表的最后一个元素指针指向Null，标志这链表的结尾。
例如，如果要在上述链表中搜索一个元素02：
首先通过头指针查看头指针指向的元素值是否等于02，
发现不等于，查看指针指向的下一个元素值是否等于02
…
最后发现有个元素等于02，返回True。
如果直到指针指向Null，都没有发现搜索元素，返回False。
链表中增加元素（到链表开头），如下图：
复制头指针的地址，使要增加的元素同样指向第一个元素。
使头指针指向要增加的这个元素。
其余的链表操作还有增加元素到链表中间、删除元素等。
Stack
这个遇到好多次了，能说出一些：
last in，first out。
每次增加元素会放在栈顶，每次也只能取出栈顶的元素。
视频中有两个例子，
显示餐厅的托盘，一大堆托盘，放托盘时，只能放在最上面。拿托盘时，也只能拿最上面的。
还有叠衣服到箱子里，每次放衣服放在最上面，拿衣服也只能拿最上面的，一直只能穿一套衣服。
Queue
队列，first in, first out。
像正常的排队买东西一样，队列最前面的先买。最前面的买到了，第二个买。
然后，重要的一个概念：
假如队列只有8个位置。（Capacity）
现在8个位置都有人排队。（Size）
第一个人买完后，又来了一个人排队。
一般的做法是所有的人前移一个位置，留出最后一个位置给新来的人。
更巧妙的做法，可以新来的人直接站在第一个位置。只要第二个人的位置变成队列的开头就行了。
大致如下图：
Tree
树结构，看下边的 Binary Search Tree，每次比较搜索值与当前节点值，能确定下次往左搜索还是往右搜索。不用遍历所有数据了。
首先有一个指针指向tree结构的根节点，知道二叉树从哪儿开始的。
根节点有两个指针，左边的指针指向的子节点的值小于根节点的值，右边子节点的值大于根节点的值。
同样，下面的子节点一样会有一个或两个字节点。
例如，搜索66：
首先开始时指针指向的值为55, 66大于55，看55右边的指针。
55右边的指针指向77, 66小于77，看77左边的指针。
77左边的指针指向66，等于66，返回True，完成了搜索。
使用二叉树搜索，最重要的是二叉树的结构要平衡。
比如，下面的二叉树结构，符合搜索二叉树的定义。只是这样的二叉树和链表差不多，看不出二叉树搜索的优势了。
然后视频中最后了一些编码和hash tables。
标准ASCII码用7位二进制数表示128个可能的字符。
例如 65 代表A 等等。
所有的字母都占用一样的内存或许不太理想。
当然，可以自己按照字母出现的频率来编码。字母出现频率高，相应的编码也简单，方便使用和存储（Morse Code）。
比如 一段文字 AAAEEEBBCCCCDDDDDDDD。
A出现的频率为15%，B 10%，C 20%，D 40%，E 15%。
按照最小的两个数互相结合成一个新的数的原理。如下：
首先，五个数中最小的两个数是 10%和15%，结合后变成25%。
现在，四个数中最小的两个数是 15%和20%，结合后变成35%。
然后，三个数中最小的两个数是 25%和35%，结合后变成60%。
60%和40%结合成了1。
到了编码环节，按照节点左边编码为0，右边编码为1。
A的编码为001，B的编码为000，C的编码为011，D的编码为1，E的编码为010。
（暂时没看到多大的优势，3个二进制数能表示8个字符，这里只有E编码为一个二进制数，其他4个字符还是3个二进制数表示。如果需要编码的字符多了，会很明显的优势，出现频率高的字符编码也少，就不用占用那么多内存了。）
关于视频后面的 hash 表，暂时没去找更详细的介绍。
最后放上数据结构的定义：
Data structure
数据结构