自己感触，有错的还请大家指出
动态数组：
动态数组只写了三遍，发现一些问题总结如下。
设计的动态数组和之前的双向链表一样，也是浅拷贝的数据结构。
- 第一遍用malloc,free,memmove等函数来完成的(注：memcpy和memmove的区别是memcpy没有考虑内存重叠的情况)。
- 第二遍发现memmove的操作并不怎么直观，所移动的size每次都要写的比较长(sizeof(void *) * n)，于是实现了一个elem_move的函数，使用index进行移动。同时替换malloc和free所进行的内存扩展为realloc，在使用realloc的过程中没有仔细阅读realloc的函数原型，第一次使用时居然认为肯定原地扩展了，虽然运行起来没发现错误，还好被valgrind查出来了。在此严重推荐一下valgrind，检查内存泄漏的一个很不错的工具，帮我查出很多次错误了；
- 写第三遍是因为发现了浅拷贝的一个问题。如果get了其中一个elem然后set到不同的index下，那么原来在此index下的elem会发生内存泄漏，而被set过来的elem则会在销毁的时候被free两遍。为了改善这个这个问题，在数组内引入了reference count的概念。我在数组初始化的时候引入了ref_ch和ref_eq函数，调用者自己完成这些函数，并且在自己的数据结构里面加上reference count，根据自己的elem结构对reference count进行操作，并且在insert和set_by_index的时候进行reference count加一，elem_destroy的时候先减一，判断为0了再free。
最终结构是这样的：
数据部分：
struct _DArray{
void **data;//用来存放动态数组的首指针
size_t length;//数组当前长度
size_t size;//数组目前的可用大小
void *ctx;//进行free的上下文
DArrayFreeFunc free;//自己的free函数
DArrayVisitFunc ref_ch;//修改reference count的函数
DArrayCmpFunc ref_eq;//判断reference count是否等于一个数的函数
};
内部方法：
//销毁一个元素，data为所要销毁的elem的指针。具体操作为调用 //ref_ch((void *)-1, data)减少其ref count，然后检查是否为0， //是则free掉，否则只是减一 static void darray_elem_destroy(DArray *thiz, void *data) static size_t darray_get_size(DArray *thiz) static Ret darray_set_size(DArray *thiz, size_t size) static Ret darray_set_length(DArray *thiz, size_t length) //扩展当前数组，函数判断若inc+length>size了就扩展 static Ret darray_expand(DArray *thiz, int inc) //收缩，若数组长度已减少到一半又少了rand()，则缩减数组尺寸为一半 static Ret darray_shrink(DArray *thiz) //元素移动，用于中间的插入和删除。n为需要移动的元素个数。 static Ret darray_elem_move(DArray *thiz, size_t des_index, size_t src_index, size_t n)
外部方法：
//创建动态数组实例，返回此实例的指针，参数为该数组用的元素free函数， DArray *darray_create(DArrayFreeFunc free, DArrayVisitFunc ref_ch, DArrayCmpFunc ref_eq, void *ctx); //把data插入对应index，具体操作为调用expand(thiz, 1),elem_move, 设置值, //ref_count++, set_length Ret darray_insert(DArray *thiz, size_t index, void *data); Ret darray_append(DArray *thiz, void *data); Ret darray_prepend(DArray *thiz, void *data); //删除某个元素，具体操作为elem_destroy, elem_move, set_length, shrink Ret darray_delete(DArray *thiz, size_t index); //把某个元素的内容设置为data Ret darray_set_by_index(DArray *thiz, size_t index, void *data); //获取某个index对应的元素，将其指针赋到data上 Ret darray_get_by_index(DArray *thiz, size_t index, void **data); size_t darray_length(DArray *thiz); Ret darray_foreach(DArray *thiz, DArrayVisitFunc visit, void *ctx); //顺序调用elem_destroy， free掉所有元素，并把指针全部置为NULL void darray_destroy(DArray *thiz);
在这个过程中同时折腾了好多的东西，感觉也很有意思。
- 关于malloc来的内存没有初始化，原因是这样的：我原来认为malloc和free是c用来提供内存和释放内存的函数，其实更准确的说它们是管理内存的函数，它所做的事就是管理内存。malloc是找到一块没有其他人使用的内存，free是把这块内存标记为没有使用，至于内存中的内容？抱歉，这两个函数是不管里面的内容的，free掉的内存中甚至还可能有内存控制块的信息。这样的话所谓的“未初始化”的内存含义就是可能有人用过，可能没有人用过，至于里面的内容，谁知道是什么，可能刚刚有人拿它来存整数，也可能存指针了，也可能真就是空的。（此处提一嘴，强烈推荐K&R的C程序设计语言，这本书中居然还有malloc和free的实现！）
- 关于struct，猜测内存对齐的原因及结构体访问的方式。新建一个struct实例的操作很简单，malloc一块空间，地址赋给struct类型的指针。就这么简单，这是怎么回事呢？从刚才的说法可以了解malloc来的内存其实是未初始化的，里面什么东西都有可能，那么我们调用其成员的时候系统是如何知道什么是它的成员呢？猜测：其实系统不知道，系统做的只是访问某块内存，对其读取或者写入，系统所了解到的“成员”只不过是这个“成员”相对于结构体指针地址的偏移量，为了方便管理和计算偏移，在编译的时候把它们的偏移量都统一确定了。（暂时不好查阅资料，内存对齐的话题看来要留到以后学习了）。
排序算法
这章中重新写了三个排序算法，冒泡，快速，归并。事实证明，我对这三个算法的熟悉程度并没有到“技能”的程度，平均一个算法写了一个半小时。这里将三个排序算法的关键点记录一下。
- 冒泡排序：我采取了改进的冒泡法，即每次冒泡都进行到上次交换过的最后一个。此方法主要有三个变量，一个遍历用的变量，一个记录单轮冒泡过程中做交换的元素的位置，一个用来记录已经有序有序的元素的位置（它等于上一轮最后那做交换的元素的位置）。
- 快速排序：主要思想是每轮都把一个元素放到最终位置上，并且保证比它大的和比它小的元素分开两边。这个算法有两个特殊情况需要处理，选取的标准元素是这一堆中的最小值，或者是其中的最大值，写条件的时候主意这两种情况外加不要越过左右边界，快速排序就不会有什么问题了。
- 归并排序：它主要是两个动作，首先是递归，然后是合并有序数据。递归出口是函数参数包含的数据段合并完成，初始递归出口是数据段内只有一个元素。每个数据段都是闭区间，所以不要把某个元素包含到两个数据段中去。用来遍历的变量i超过边界是没有问题的，只要超过之后不会再次被使用。
