博文
数据结构学习（C++）——递归【3】（2）(2007-04-02 06:22:00)
摘要：递归法和回溯法
有人说，回溯实际上是递归的展开，但实际上。两者的指导思想并不一致。
打个比方吧，递归法好比是一个军队要通过一个迷宫，到了第一个分岔口，有3条路，将军命令3个小队分别去探哪条路能到出口，3个小队沿着3条路分别前进，各自到达了路上的下一个分岔口，于是小队长再分派人手各自去探路——只要人手足够（对照而言，就是计算机的堆栈足够），最后必将有人找到出口，从这人开始只要层层上报直属领导，最后，将军将得到一条通路。所不同的是，计算机的递归法是把这个并行过程串行化了。
而回溯法则是一个人走迷宫的思维模拟——他只能寄希望于自己的记忆力，如果他没有办法在分岔口留下标记（电视里一演到什么迷宫寻宝，总有恶人去改好人的标记）。
想到这里突然有点明白为什么都喜欢递归了，他能够满足人心最底层的虚荣——难道你不觉得使用递归就象那个分派士兵的将军吗？想想汉诺塔的解法，也有这个倾向，“你们把上面的N－1个拿走，我就能把下面的挪过去，然后你们在把那N－1个搬过来”。笑谈，切勿当真。
这两种方法的例程，我不给出了，网上很多。我只想对书上的递归解法发表点看法，因为书上的解法有偷梁换柱的嫌疑——迷宫的储存不是用的二维数组，居然直接用岔路口之间的连接表示的——简直是人为的降低了问题的难度。实际上，如果把迷宫抽象成（岔路口）点的连接，迷宫就变成了一个“图”，求解入口到出口的路线，完全可以用图的遍历算法来解决，只要从入口DFS到出口就可以了；然而，从二维数组表示的迷宫转化为图是个很复杂的过程。并且这种转化，实际上就是没走迷宫之前就知道了迷宫的结构，显然是不合理的。对此，我只能说这是为了递归而递归，然后还自己给自己开绿灯。
但迷宫并不是只能用上面的方法来走，前提是，迷宫只要走出去就可以了，不需要找出一条可能上的最短路线——确实，迷宫只是前进中的障碍，一旦走通了，没人走第二遍。下面的方法是一位游戏玩家提出来的，既不需要递归，也不需要栈来回溯——玩游戏还是有收获的。
另一种解法
请注意我在迷宫中用粗线描出的路线，实际上，在迷宫中，只要从入口始终沿着一边的墙走，就一定能走到出口，那位玩家称之为“靠一边走”——如果你不把迷宫的通路看成一条线，而是一个有面积的图形，很快你就知道为什么。编程实现起来也很简单。
下面的程序在TC2中编译，不能在VC6中编译——为了动态的表现人的移动情况，使用了go......
数据结构学习（C++）——递归【3】（1）(2007-04-02 06:22:00)
摘要：迷宫
关于迷宫，有一个引人入胜的希腊神话，这也是为什么现今每当人们提到这个问题，总是兴致勃勃（对于年青人，估计是RPG玩多了），正如虽然九宫图连小学生都能做出来，我们总是自豪的说那叫“洛书”。这个神话我不复述了，有兴趣的可以在搜索引擎上输入“希腊神话 迷宫”，就能找到很多的介绍。
迷宫的神话讲述了一位英雄如何靠着“线团”杀死了牛头怪（玩过《英雄无敌》的朋友一定知道要想造牛头怪，就必须建迷宫，也是从这里来的），我看到的一本编程书上援引这段神话讲述迷宫算法的时候，不知是有意杜撰，还是考证不严，把这个过程叙述成：英雄靠着线团的帮助——在走过的路上铺线，每到分岔口向没铺线的方向前进，如果遇到死胡同，沿铺的线返回，并铺第二条线——走进了迷宫深处，杀死了牛头怪。然而，神话传说讲的是，英雄被当成贡品和其他的孩子送到了迷宫的深处，英雄杀死了牛头怪，靠着线团标识的路线退出了迷宫。实际上，这个线团只是个“栈”，远没有现代人赋予给它的“神奇作用”。我想作者也是RPG玩多了，总想着怎样“勇者斗恶龙”，然而，实际上却是“胜利大逃亡”。
迷宫问题实际上是一个心理测试，它反映了测试者控制心理稳定的能力——在一次次失败后，是否失去冷静最终陷在迷宫之中，也正体现了一句诗，“不识庐山真面目，只缘身在此山中”。换而言之，我们研究迷宫的计算机解法，并没有什么意义，迷宫就是为人设计的，而不是为机器设计的，它之所以称为“迷”宫，前提是人的记忆准确性不够高；假设人有机器那样的准确的记忆，只要他不傻，都能走出迷宫。现在可能有人用智能机器人的研究来反驳我，实际上，智能机器人是在更高的层面上模拟人的思考过程，只要它完全再现了人的寻路过程，它就能走出迷宫。但是，研究迷宫生成的计算机方法，却是有意义的，因为人们总是有虐待自己的倾向（不少人在RPG里的迷宫转了三天三夜也不知道疲倦），呵呵，笑谈。
不管怎么说，还是亲自研究一下计算机怎么走迷宫吧。
迷宫的存储
按照惯例，用一个二维数组来表示迷宫，0表示墙，1表示通路，以后我们的程序都走下面这个迷宫。
&nb......
数据结构学习（C++）——递归【2】（4）(2007-04-02 06:21:00)
摘要：include <iostream>
#include <vector>
using namespace std;
class Needle
{
public:
Needle() { a.push_back(100); }//每一个柱子都有一个底座
void push(int n) { a.push_back(n); }
int top() { return a.back(); }
int pop() { int n = a.back(); a.pop_back(); return n; }
int movenum(int n) { int i = 1;while (a[i] > n) i++; return a.size() - i; }
int size() { return a.size(); }
int operator [] (int n) { return a[n]; }
private:
vector<int> a;
};
void Hanoi(int n)
{
Needle needle[3], ns;//3个柱子，ns是转换柱子时的保存栈，借用了Needle的栈结构
int source = 0, target, target_m = 2, disk, m = n;
......
数据结构学习（C++）——递归【1】(2007-04-02 06:20:00)
摘要：照黄皮书的安排，到了该讲递归的时候了。上网查了查，关于“递归”的文章可以说“汗牛充栋”——请原谅我在这里犯酸，我的意思是，写别人都写臭的东西让大家看，只是浪费大家的时间，所以我下面的东西应该是一些至少我看起来是新的东西，如果觉得有什么不清楚的，请参阅相关的文章（太多了）。即使这样，这篇文章还是不能把我想说的写完，看来我这人真的有废话的习惯。
看过这样一道题，问，“程序结构化设计的三种基础结构，顺序、选择、循环是不是必须的？”当然，你知道这样一个论断，只要有这三种就足够了；但是能不能更少呢？答案是“可以”，原因就是递归能取代循环的作用，例如下面的对一个数组里面元素求和的函数：
float rsum (float a[], const int n)
{
if (n <= 0) return 0;
else return rsum(a, n – 1) + a[n – 1];
}
实际上就是：
sum = 0;
for (int i = 0; i < n; i++) sum += a[i];
但实际的情况是，任何的一种语言里面都有循环结构，但不是任何的语言都支持递归；套用一句话，递归是万能的，但没有递归不是万万不能的。然而，我看到现在的某些人，不管什么问题都要递归，明明循环是第一个想到的方法，偏偏费尽脑筋去寻找递归算法。对此，我真的不知道该说什么。
递归是算法吗
经常的看到“递归算法”、“非递归算法”，这种提法没有语义上的问题，并且我自己也这样用——递归的算法。但这也正说明了，递归不是算法，他是一种思想，正是因为某个算法的指导思想是递归的，所以才被称为递归算法；而一个有递归算法的问题，当你不使用递归作为指导思想，这样得到的算法就是非递归算法。——而对于循环能处理的问题，都有递归解法，在这个意义上说，循环算法都可以称为非递归算法。
我在这咬文嚼字没什么别的意思，只是想让大家知道，能写出什么样的算法，关键是看你编写算法时的指导思想。如果一开始就想到了循环、迭代的方法，你再费心耗神去找什么递归算法——即使找到了一种看似“简洁”的算法，由于他的低效实际上还是废物——你还在做这种无用功干什么？典型的学......
数据结构学习（C++）——递归【2】（1）(2007-04-02 06:19:00)
摘要：汉诺塔的非递归解法
（真的很抱歉，由于CSDN能贴的长度有限，所以分成了4部分，让您麻烦了。——我用表格拼成的盘子，导致HTML代码数量激增，虽然看起来不长，但是实际上相当的长。）
似乎这个问题的最佳解法就是递归，如果你想用栈来消解掉递归达到形式上的消除递归，你还是在使用递归的思想，因此，他本质上还是一个递归的算法。我们这本黄皮书在谈论到“什么情况使用递归”的时候，在“3.问题的解法是递归的”这里面，就这样说了“有些问题只能用递归的方法来解决，一个典型的例子就是汉诺塔”。
但我坚信，如果一个问题能用分析的办法解决——递归实际上就是一个分析解法，能将问题分解成－1规模的同等问题和移动一个盘子，如果这样分解下去一定会有解，最后分解到移动1号盘子，问题就解决了——那么我也应该能用综合的办法解决，就是从当前的状态来确定怎样移动，而不是逆推得到决定。这是对实际工作过程的一个模拟，试想如果让我们去搬盘子，我们肯定不会用递归来思考现在应该怎么搬——只要8个盘子，我们脑子里的“工作栈”恐怕就要溢出了——我们要立即决定怎么搬，而不是从多少步之后的情景来知道怎么搬。下面我们通过模拟人的正向思维来寻找这个解法。
假设如下搬7个盘子的初始状态（选用7个是因为我曾经写出了一个1～6结果正确的算法，而在7个的时候才发现一个条件的选择错误，具体大家自己尝试吧），我们唯一的选择就是搬动1号盘子，但是我们的问题是向B搬还是向C搬？
1
2
......
数据结构学习（C++）——双向链表(2007-04-02 06:18:00)
摘要：原书这部分内容很多，至少相对于循环链表是很多。相信当你把单链表的指针域搞清楚后，这部分应该难不倒你。现在我的问题是，能不能从单链表派生出双向链表？
你可以有几种做法：
一种就是先定义一个双链节点——但是，它的名字必须叫Node，这是没办法的事；不然你就只好拷贝一份单链表的实现文件，把其中的Node全都替换成你的双链节点名字，但是这就不叫继承了。
另一种做法就是先定义一种结构例如这样的：
template <class Type> class newtype
{
public:
Type data;
Node<newtype> *link;
}
当你派生双向链表时，这样写template <calss Type> class DblList : public List<newtype<Type> >，注意连续的两个“>”之间要有空格。或者根本不定义这样的结构，直接拿Node类型来做，例如我下面给出的。但是，请注意要完成“==”的重载，否则，你又要重写Find函数，并且其他的某些操作也不方便。
在开始完成你的从单链表派生出来的双向链表之前，要在单链表这个基类中添加修改当前指针和当前前驱指针的接口，如下所示：
protected:
void Put(Node<Type> *p)//尽量不用，双向链表将使用这个完成向前移动
{
current = p;
}
void PutPrior(Node<Type> *p)//尽量不用，原因同上
{
&......
数据结构学习（C++）——稀疏矩阵（十字链表【1】）(2007-04-02 06:18:00)
摘要：先说说什么叫稀疏矩阵。你说，这个问题很简单吗，那你一定不知道中国学术界的嘴皮子仗，对一个字眼的“抠”将会导致两种相反的结论。这是清华2000年的一道考研题：“表示一个有1000个顶点，1000条边的有向图的邻接矩阵有多少个矩阵元素？是否稀疏矩阵？”如果你是个喜欢研究出题者心理活动的人，你可以看出这里有两个陷阱，就是让明明会的人答错，我不想说出是什么，留给读者思考。姑且不论清华给的标准答案是什么，那年的参考书是严蔚敏的《数据结构（C语言版）》，书上对于稀疏矩阵的定义是这样的：“非零元较零元少（注：原书下文给出了大致的程度），且分布没有一定规律”，照这个说法，那题的答案应该是不一定是稀疏矩阵，因为可能是特殊矩阵（非零元分布有规律）。自从2002年换参考书后，很多概念都发生了变化，最明显的是从多少开始计数（0还是1），从而导致的是空树的高度变成了－1，只有一个根节点的树高度是0。很不幸的是树高的问题几乎年年都考，在你下笔的时候，总是犯点嘀咕，总不是一朝天子一朝臣吧，会不会答案是个兼容版本？然后，新参考书带的习题集里引用了那道考研题，答案是是稀疏矩阵。你也许会惊讶这年头咸鱼都会游泳了，但这个答案和书并不矛盾，因为在这本黄皮书里，根本就没有什么特殊矩阵，自然就一定是稀疏矩阵了。其实，这两本书在这个问题上也没什么原则上的问题，C版的是从数据结构实现区分出特殊矩阵和稀疏矩阵，毕竟他们实现起来很不相同；新书一股脑把非零元少的矩阵都当成稀疏矩阵，当你按照这种思路做的时候就会发现，各种结构特殊的非零元很少的矩阵，如果用十字链表来储存的话，比考虑到它的特殊结构得出的特有储存方法，仅仅是浪费了几个表头节点和一些指针域，再有就是一些运算效率的降低。从我个人角度讲，我更喜欢多一些统一，少一些特别，即使牺牲一点效率；所以在这一点上我赞同新参考书的做法。而在计数起点上，我更喜欢原来的做法；毕竟，研究数据结构要考虑人的思考习惯，而不是计算机喜欢什么；你非得说表中的第一个元素是第0个，空树的高是－1，怎么不让人心里起疙瘩。数据结构是人们构造算法时思维和计算机实现的桥梁、中介，它应该符合人的思考习惯，即使在它实现的时候内部做了某些转换。开始废话了这么多，希望没打消了你往下看的心情，好，言归正传。
这里的十字链表是这样构成的：用链表模拟矩阵的行（或者列，这可以根据个人喜好来定）......
数据结构学习（C++）——单链表应用（一元多项式【1】）(2007-04-02 06:17:00)
摘要：总算到了这里，这时，你会很得意的说，辛辛苦苦学的单链表总算知道能干点什么了。但是很不幸，如果你和我一样看的是那本书，到这里，你可能比学双向链表时还要痛苦。如果你是按照书上的介绍一步一步做到这里，你能把书上的多项式加法函数调试出来，我对你致以十二分的敬意。
说到这里，我想起来我发单链表的时候，有人给我建议说：最好把链表和链表位置这两个分开。没错，C++标准库是这么做的，而我也不是什么专家，也不能证明什么优劣；但是，对于初学者来说，一个类总比两个类好操作。我不清楚原书这部分的程序究竟调没调试，但这种语句我是绝对看不懂的：
ListNode<Term> *pa, *pb, *pc, *p;
ListIterator<Term> Aiter(ah.poly);
ListIterator<Term> Biter(ah.poly);
pa = pc = Aiter.First(); pb = p = Biter.First();
………………………..
pa->coef = pa->coef + pb->coef;
p = pb; pb = Biter.Next(); delete p;
如果你没有原书，我来解释一下。pa, pb, p 究竟指向什么？你说这很清楚，ListNode<Term>这样的节点呗。但按照原书的定义，ListIterator::First()等等函数返回是指向data域的指针，他们怎么能直接赋值？到了下面更乱了，pb指向的区域直接分解出了Term的数据成员，也就是说是指向Term结构的；然后让ListNode<Term>类型的指针p指向这个Term结构，最后，居然把这个结构delete了，天啊，ListNode<Term>这样的节点的data域被delete了！
如果从基本的节点操作入手，谁也不会弄的这么乱。但正因为又多了一个类，很多事就疏忽了。所以，我并不怀疑标准库的做法，只是对于初学者，同一时间最好只对一个类操作。我以我的定义为基础，重新完成了这段程序。我并不欣赏原位操作的多项式加法（＋），PolyA+PolyB，然后B就嗖的一下没了，A就多了一堆（也可能少了一堆）；你作intJ+intK的时候怎么没见J和K有什么变化。与其这样，重载“+”还......