Learn Algorithms with Arden
第一天 引子
和arden学算法，只是arden自己的算法读书笔记。因为自己也是在学习阶段，有错误之处不可避免，只是希望能给想学习算法的朋友一个共享感受的途径，也许有一天我的算法有点基础了，我可以把它修改为一个初级教程。
在学习时arden主要的参考教材是Robert Sedgewick 的《algorithms in c》的前两卷。（第三卷还没有到手）大致的算法书籍都是按照这样的一个次序来讲授，所以没有选用那本比较经典的Sedgewick老师Knuth的算法书，主要原因是，我去书店的时候没有看到那本。另外的参考主要是来自于google上的search了，来自哪里相对杂乱，如果真的是不知道谁所写就不记录了，也请作者如果看见我的对您的文章代码的引用，请联系我，许可或者拒绝我的引用。
于是我大概会一天一个章节这样子写笔记，那么，有重要的章节可以花费多些时间。
那其实刚开始看这本参考书的时候，受到一些打击。就在这个引子里。一个连通性问题：
Q：一个整数对，其中每个整数代表某种类型的对象，而且将p-q对解释成“p与q连通”。假定连通是可传递的：如果p与q连通，同时q与r连通，则p与r连通。
要求：编写一段程序，从集合中过滤额外连接对。当程序输入整数对p-q，仅当程序此时已经看到的对不能通过可传递性证明p-q连通时才输出该对。
还是有一些数据抽象概念的，大学时候的离散数学和数据结构告诉我，这是一个图的连通性问题，可是没头绪，我去为它定义一个图结构？现在还没有讲到ADT，以后再说。先从零开始。
想想：我们需要存储所有的输入对记录，有新的对以后，遍历（traverse）它们并判断。
下面是我最初的思路：
1、 保存整数对到数组ipair[m][n]（矩阵和图总是有很多的联系），1为连通，0为不同。
2、 接受新的输入对p-q，检查其对应位置ipair[p][q]是否为1，来判断连通性。
3、 如果不连通则ipair[p][q]=1。
自我感觉可行，于是，转过头来看看Sedgewick给我的建议：
这样一句话给我打击：没有简单的方法能根据所有的连通集合立即判断两个对象是否连通，即使我们将它们全部保存。什么意思？我认为的空间复杂度提高带来的时间复杂度的降低难道是错误的？我已经足够奢侈的使用输入N的N^2来提高效率了。
不管了，看看他给的程序：
>>并集-查找（quick-find）算法：
/* file name qufd.c
此算法基于一个一维数组id[N],此数组具有如下性质：当且仅当第p个和第q个数组项相等时，p与q连通。将第i个数组项初始化为i，其中0<i<N。为了对p与q实现并集运算，遍历数组，将所有具有相同名字p的项更改为具有相同名字q。
*/
#include< stdio.h> //我在< 后加了空格防止被html自作多情
#define N 10000
main ()
{
Int i,t,p,q,id[N];
for (i=0;i<N;i++) id[i]=I;
while (scanf(“%d %d\n”,&p,&q)==2)
{
if(id[p]==id[q]) continue;
for(t=id[p],i=0;i<N;i++)
if(id[i]==t) id[i]==id[q];
printf(“%d %d\n”,&p,&q);
}
}
然后还不过瘾，又给了快速并集、快速并集加权、对分路经压缩等一些方法。然后当时我就蒙了，这书我还看得下去么？来的这么晦涩，的多好的胃来消化？幸好坚持了下来，越往以后就越来越开阔了。
那学习c的实践虽然可以上溯到大学时代，可是我的c语言水平完全是看BaoBao的代码和学习socket时候得的老本，java水平就更一般到语法层面。还是操起cpp，按照自己的理解重写了这个程序（c和cpp基本上没有大区别哈）：
#include < iostream>
using namespace std;
const int N=10;
void main()
{
int i,p,q,t,d[N];
for(i=0;i<N;i++) {d[i]=i; }
while(cin>>p>>q){
if(d[p]==d[q])continue;
for(i=0,t=d[p];i<N;i++)
{
if(t==d[i])d[i]=d[q];
}
cout<<p<<" "<<q<<endl;
}
}
今天的主要目的在于引子，我们不去深究了，下面的篇幅我们来理解以下上面的程序：
先说这样一句话：算法是基于一定对象的操作。像不像屁话？我看也想。但真的是这样，你看看上面程序，最基本的实现其实在于那个id[i]。通过i和id[i]的关系，完全解决了问题。以后的篇章里总是会强调数据结构的重要性，一方面，数据结构决定了算法的使用。特定的数据结构下，某些算法就是无法实现！
程序已开始定义了一个id[N]，并给它初始化：for（…）id[i]=i; 理解了这句话以后，便理解了这个程序。一开始谁也不和谁连通，我们让每个id[i]和它自己连通。
然后我们输入对p、q；
每此接到输入对以后，对id[N]遍历。找到那个等于q的位置id[q]看看它的值是对少，给了t。那么数组中所有等于t的位置都将被q取代。为什么？p-q现在是连通的，这就是传递性的一个数据抽象。
现在应该理解了吧，不理解没关系，我这么愚的人看两边就理解了，你也行。
比如一个N为10的数组我们给它初始化后是：0123456789
输入一个整数对：3 4
程序显示：3 4
数组变为：0124456789
再输入一个4 5
程序显示4 5
数组变为：0125556789
输入3 5
程序就不显示了，3和5已经通过3-4及4-5的传递连通了即id[3]==id[5]。
结束第一天的学习，我们还有很长的路要走，先是数据结构、然后看排序和搜索。
