Dragon 第一期开发日志
前言
花了一个星期准备构思，结果感觉还是回到原来的设想上，不过当然也收获了STL源码的20%，的确精妙，学不来了，先做吧。
要花点时间将模板和运算符重载的知识点整理总结一下。明晚 后晚 大后晚 争取三晚完成
-----------------------------------------------------------------------------------------------------------------------------------------------------------------------
1.25
time consume: around 1h
完成了线性表头文件的模板类定义，但不包含LinkedList的定义。
-------------------------------------------------------------------------------------------------------------------------------------------
1.26
有两个问题
1. 待验证
template<class T> class A {}
template<class T> class B:public A<T> {}
有函数func(A<T> a) 问类型为B<T>的实参能够传入这个函数呢？待验证
2. 第二个问题是获取cout
已经验证可以用函数来获取：
void print(std::ostream &o, int d){ o<<d;} 但是注意ostream的形参不能是const
但是如果用类来获取呢？
如class A
{
ostream mo;
A(ostream &o) { mo = o; }
}
报错：
error C2512: 'basic_ostream<char,struct std::char_traits<char> >' : no appropriate default constructor available
这里暂时还没弄清楚是怎么回事。请教各位老师同学了。
最后发泄一下：这里这个博客太烂了。没有及时保存功能，我是重写了3遍呀！！！！！！！！！！！！！！！！！！！！！
哈哈！好了。
明晚继续吧。
----------------------------------------------------------------------------------------------------------------------------------------------
1.27
转到csdn博客上面 这里的编辑器强大太多了。
解决昨晚的问题：
对于cout的问题：
事实上，ostream o = cout 是没问题的，问题存在于在一个模板类的构造函数中，能不能将一个ostream对象传入后赋值给o?
template<typename T>
struct Prdct_Output : public Unary_Function<T,void>
{
std::ostream m_oOutput;
Prdct_Output<T>(std::ostream o)
{
m_oOutput = o;
}
void operator()(T &e) {
m_oOutput<<"<"<<e<<">";
}
};
对于这段源码，编译报错是：
error C2512: 'basic_ostream<char,struct std::char_traits<char> >' : no appropriate default constructor available
还是没能解决。
*这里需要注意的一点是：对一些编译错误提示，深入理解是无意义的，因为很有可能这些奇奇怪怪的报错是由于其他的一些错误引起，而这些错误，编译器是检查不出来的，这就是使用高级编程机制时，编译器的智能化程度没跟上的结果。Maybe？
*另外需要注意的一点是，对于形参表中的const，不是可以随便用的，因为这些涉及到类型转换问题，所以特别是自定义类型传参时，用const很容易就是报错。关于这个方面还需要深入研究。
然而已经基本弄清楚了函数对象的用法，并且对这种遍历的机制有所了解，其实我想写的就是foreach，而其实foreach是一个模板函数～！
另外还领略了一下关于 绑定器， 成员函数适配器，函数指针适配器， 否定器等几种适配器，C++ PL果然是宝典。、
有点进展了：原来真正的问题出现在：std::ostream m_oOutput;
也就是说必须先弄清楚ostream的声明方法。
目前的理解是ostream o必须在定义的第一时间进行初始化，即ostream o=std::cout; o<<e; 是OK的，但是除此之外都不行。
那么上面的void print(std::ostream &o, int d){ o<<d;}可以 是为什么呢？可能是引用的关系？那些将&去掉，一样是OK的，那就表明对实参o也是在定义的时候就初始化了。
在网上看到这么一句，流是不能被赋值的，待正式确认。
---------------------------------------------------------------------------------------------------------------------------------------
1.28
今晚就是重新写了一篇几个排序算法。O(n)的都没写。
* 一个问题，抽象类，即里面有虚函数的类是不能实例化的。这个问题出自：
template<typename T>void _merge(LinearList<T> &dest, LinearList<T> src, int _s, int _m, int _t, int &t)
也就是说不能出现LinearList<T> src 解决方法是在函数中进行表的复制。
* 第二个遇到的问题 其实也不是第一次遇到了。经常会有些Access Violation的报错，在ctrl+F5运行时还报错，但是如果F11逐步调试是完全没有问题的，这样实在是太浪费时间。要知道有时逐步调试就要花上 10分钟。所以应该要注意：1,clear 2.要培养对迭代式正确性的敏感度
--------------------------------------------------------------------------------------------------------------------------
1.29
今晚写排列和组合 发现这些算法忘得真的很快
（1）组合
首先花了45分钟 包括调试写了组合 感觉比之前写的有进步 代码更简洁 而且思路清晰 不过还是花了许多时间调试
记录两个出错点：
1. _push_1_left方法， 其实思路有很多，比如说可以利用插入排序的思想，很明显，将1都排在前面，但是这样n平方，也可以利用partition的思路：用一个下标记录已经整理过的1的后一位的位置，遇到1则与之调换，这样可以在O(n)时间内完成。
2. 另一个出错点是：while (p=_find_10(tags, n) != -1) 属于运算符结合优先级的问题，这样最后p的结果是1，而不是_find_10函数的返回值。
（2）排列（字典）
终于发现#ifndef的用处了。由于同时：
#include "composition.h"
#include "permutation.h"
结果疯狂报错。
所以注意 每次include一个头文件，先问问，你定义它了吗？
如：
#ifndef _LINEAR_LIST
#include "..//data_structure//basic_data_structure//linear_list//linear_list.h"
#endif
结果组合的字典算法还是很快就写好调好了。不过算法还是完全不是自己的思路，这证明只是机械编码阶段，没有进入思考阶段。
（3）排列（递归）
递归方法也写好了。虽然速度还行，但是很没达到心里的标准。
这次犯的错误完全是算法上的错误，根本对算法没有完全的了解。才会出现这样的错误。
错误：
count++;
//get a result
std::cout<<"Permutation: ";
for (int i=0;i<list.length();i++)
std::cout<< "<" << list[i] << ">";
std::cout<<"/n";
if (_s==list.length()-1)
{
return ;
}
也就是没有意识到 输出结果的条件是_s到达序列尾部。
------------------------------------------------------------------------------------------------------------------------
1.30
今晚准备写两个算法，随机化的顺序统计，一个是平均情况下线性，一个是最坏情况下线性。（第二个牛B了）
今晚进展不是很顺利，脑袋有点发胀。第一个算法写了一个半小时，而问题居然出现在partition上面，证明对一些基础算法还是很生疏呀。。。。
对一个随机选择pivot的partition算法，正确的步骤应该是：
先将这个pivot跟列表头部元素交换，然后再利用：
int p = _s;
//start the loop from _s+1
for (int i=_s+1; i<=_t; i++ )
if (list[i] < pivot )
{
p++;
if (i!=p) util::Swap(list[i],list[p]);
}
util::Swap(list[p],list[_s]);
利用一个循环，在[_s+1,_t]的区间上作分区，最后交换保存在表头的pivot和list[p]。而我居然将最后一句写成list[p] = pivot。。。。。太错了！更重要的是，在前天写的sort里面，quicksort的partition也是有错误的。。。。。。但是我居然没有test出来，证明test也是太疏忽了。。。。还好发现得早。。。。
唉 最后没实现目标。。。。shit....第二个算法有点忘记了 重新看了下书 结果发现以前的理解很肤浅。。而且第一个程序占用时间太多了。
---------------------------------------------------------------------------------------------------------------------------
1.31
今天回家。晚上9点开始写程序。虽然感觉今晚思维还是比较清晰，但是还是不熟练 不熟练 不熟练。。。。。
今晚写的是算法导论中最坏情况下线性时间的选择算法Select。这个算法比较复杂，但是我昨晚已经作了一定思考，觉得应该可以用传入间距来实现，第二步中，对每组的中位数进行递归Select。
结果写了将近一个小时后，发现纯粹利用间距 是无法完成这样的工作的 因为有可能 最后一组是不足5个元素，于是其中位数就不符合 前一中位数下标+interval*5的规律。
其实之前有一个想法是，直接获取每组的中位数，产生一个新的线性表对象，而不是直接在原来的线性表上做查找，但是觉得这样会影响速度，就先放弃了。其实目前来看，只能是这样做了。而由于产生一个新的对象，花的时间是O(n) 应该有一个更紧致的上界，但是就不分析了， 这样也是不会影响这个算法的总体速度的，还是O(n)。
接下来就按这个思想再重新写一遍吧。
发现对算法的理解还是很不够 写代码的熟练程度也非常不足。居然连 select是需要_s _t参数都没有实现考虑到。。。。
partition使用另外一个算法：
http://zhidao.baidu.com/question/106465392.html
这也是数据结构那本书上面的算法，可以将pivot作为参数输入，而不需知道它的下标。
但是事实上，这个算法应该是错误的。
因为数据结构书上的partition算法的思路是，将列表第一个元素设为Pivot，然后通过迭代地对pivot元素进行调换，将其与尾部数起第一个比它小的
调换，再从头部数起第一个比它大的调换，如此迭代进行，最终能够得到一个low==high，此即为pivot的位置。
因此 这个算法也是需要首先确定pivot元素的位置，而且要放在列表的两端上。
因此，partition算法，还必须是要首先知道pre_pivot元素的位置，而不能只知道它的值，否则就要先通过find函数来获得pivot元素的位置。
另一个解决方法是将_select的返回值改为元素下标。（目前采用）
-----------------------------------------------------------------------------------------------------------------------------------------
2.1
今晚开始对select进行调试 第3天了。。。。
以下是出现的bugs:
(1) 插入排序有问题： 原来是比较条件写成
for (int j = i-1 ; j>= _s; j--)
if (list[i] < list[j]) list[j+1] = list[j];
else break;
其实是应该将list[i]写成tmp才对。。。不然的话后移就会将这个插入元素改掉了！！！！
(2) for (int j=_s;j<=_t;j+=NG)
{
_insertSort(list, j, ((j+NG-1<=_t)?(j+NG-1):(_t)) );
}
调用插入排序这里也有问题，对于最后剩下的几个元素没有考虑周到，当j迭代到最后一个位置时，此时的末尾并不等于j+NG-1,因为没凑齐
NG个元素，因此这里应该要改成_insertSort(list, j, ((j+NG-1<=_t)?(j+NG-1):(_t)) );
(3) 第三个错误更让我啼笑皆非。。。寻找中位数的算法，返回的结果值是0——因为我是采用了将_select函数的返回值改成数组下标。。。但是
事实上这样很错误的。因为查找中位数时，是传入一个新的mlist,它的下标怎么能跟原来的下标对应呢？而且很明显，最后会返回一个0，因为mlist
的大小不断缩小，最后变为一个元素，就是要找的中位数，而它的下标肯定是0
其实是有通过传入pivot的值来进行partition的算法，也就是说我昨晚看的算法是正确的：
http://zhidao.baidu.com/question/106465392.html
因此解决方法就是将partition换成这个算法应该就没有问题了
(4) 第四个错误是关于delete &mlist; 这句会弹出一个用户breakpoint...不知道是什么错误，也没有错误提示。估计是由于没有实现析构函数
我实现了一个虚析构函数，但是报错：
error LNK2001: unresolved external symbol "public: virtual __thiscall LinearList<int>::~LinearList<int>(void)" (??1?$LinearList@H@@UAE@XZ)
其实出现这个错误是因为。。。模板类是不能出现虚模板函数的，而析构函数必须得加上模板类型。所以。。。
还是回来原来的那个错误：user breakpoint called from code at （突然弹出的一个对话框）
当我将mlist的定义改为： LinearList<T> *pMlist = new SequenceList<T>((r!=0)?(g+1):g);
用new来呼应delete，但是结果还是报错，类似的错误：crtisvalidheappointer puserdata （google 关键字！！！）
(5)删除后，通过了，但是结果跟RandomSelect的结果不同。即有误。
最后调试结果显示：错误出现在partition函数中。。。我真的泪奔了。。。一个Partition起码花了我5个小时以上的调试时间。。。
错误写法：
int p = -1;
int q = list.length();
while(1)
{
while (p<q && list[--q]>pivot) ; //find the first element that smaller than or equal to pivot from the end of the list
while (p<q && list[++p]<pivot) ; //find the first element that larger than or equal to pivot from the head of the list
// *Note that pivot would be not exist in the list
// but still can partition the list by the nearest element of value to pivot
if (p<q) util::Swap(list[p],list[q]);
else return p;
}
正确写法：
int p = 0;
int q = list.length()-1;
while(1)
{
while (p<q && list[q]>pivot) q--; //find the first element that smaller than or equal to pivot from the end of the list
while (p<q && list[p]<pivot) p++; //find the first element that larger than or equal to pivot from the head of the list
// *Note that pivot would be not exist in the list
// but still can partition the list by the nearest element of value to pivot
if (p<q) util::Swap(list[p],list[q]);
else return p;
}
错误原因是每次寻找p和q的时候先进性自增或自减。而正确顺序是先检查在做操作。。。
(6)目前在计算一个n=2034的序列的第100个元素，结果显示后者的速度奇慢～！！！！！