博文
数据结构学习（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有什么变化。与其这样，重载“+”还......
数据结构学习（C++）——循环链表(2007-04-02 06:17:00)
摘要：原书对循环链表的介绍很简略，实现部分也不完整（当然了，如果完整就又是重复建设）。而我也没觉得循环链表有什么别的用，他更应该是为了一个特殊的问题而产生的，这只是个人的看法。我从链表类派生出了循环链表，这需要注意几个细节。
1. 构造函数：派生类实例化时，先调用基类的构造函数；因此，初始化循环链表的工作就是将带表头的空链表的表头节点的link指向表头节点，从而构成一个圈。
2. 析构函数：释放对象时，先调用派生类的析构函数，然后调用基类的析构函数。因此，释放循环链表只需要将循环链表变成普通的单链表，然后这个单链表会被基类的析构函数释放。这里假定不使用这种语句Base *p = new Drived;delete p;因为我在~List()前面没有加virtual。你可以参阅各种C++书籍搞清这类问题。
3. 判空函数：条件不是检测头节点的link是否为空，而是是否指向头节点。
4. 置空函数：原来的显然不能工作了，实际上只要从表头位置不断后删直到表空就可以了。
5. Next()：遇到表头节点要跳过去。
6. Remove()：当前节点是表头节点时不能删，删了表头节点的后果自己想吧（因为在循环链表中prior指针不一定为空——其实应该是一定不空，但是由于继承部分List函数，所以就是不一定了，以至于原来的Remove()检查可能无效）；如果删除的是表尾节点，删除后当前指针将指向表头节点，要跳过去指向下一个。总之，使用Next()和Remove()时，不能让外界觉察到表头节点的存在，否则，当你循环计数时，表头节点就被算进去了。
7. “<<”必须重写，否则，当你执行co......
数据结构学习（C++）——序言(2007-04-02 06:16:00)
摘要：题外话：先前有一篇文章叫《用C++模板描述的链表、栈、队列（声明与实现）》，当时是第一次发表文章（我才注册没几天），很不成熟，改了又改不说，还弄的老长，不利于阅读。于是我重写了一下，并且想做成一个系列，这从我的标题可以看出来。好，言归正传。
本篇为后面一系列文章的序言，旨在说明写作的目的，以及写作的风格；或者说是为自己可能的错误，预先给个托词。如果您不想听我在这废话，请跳过本篇，直接阅读后面的文章。但是这样，我不能保证，您在阅读的同时，不会骂我白痴。
为什么写这些文章
这些文章可以说是《数据结构（用面向对象方法与C++描述）》这本书的读书笔记，但也不完全是。数据结构是计算机专业必修课——几乎每个计算机专业的学生都会推崇他的重要；同时，也是其他专业转修计算机专业的一个难点。
从学习的角度来说，严蔚敏的《数据结构（C语言版）》是本不错的书。但是，C语言不是描述的理想工具。《数据结构（C语言版）》的前言里是这样说的：“虽然C语言不是抽象数据类型的理想描述工具，但鉴于目前和近一、二年内，……并增添了C++语言的引用调用参数传递方式等，构成了一个类C描述语言。”
从抽象数据类型的定义——一个数学模型以及定义在该模型上的一组操作——可以看出，面向对象语言中类的概念和这个定义很接近，加之C语言的普及，用C++来描述于是就成了顺理成章的事情。
于是，清华在2002年的考研参考书目中对《数据结构》的参考书做了改变，使用《数据结构（用面向对象方法与C++描述）》（殷人昆等编著，ISBN 7-302-03405-2/TP1845）作为参考书，而实际上考的也是（废话，不是那叫误导）。坦白的讲，原书把教学目的和提供实例的目的搞混了，结果是个四不象：作为教科书，条理不清晰；提供各个方法的实现，也不是很实用，相反，重复建设太多。至于错误，可能有些是笔误，比如少个友元声明了，不是继承而使用别的类的成员函数没有指明了；还有一些，就是考虑不够周全。
不管怎么说，现在不是挑书的时候，你想考清华的计算机专业研究生吗，这本书是你不二的选择。我发现读懂此书淖詈梅椒ǎ褪亲约喊凑帐樯系乃悸罚约笆导视τ玫姆治觯约褐匦率迪指髦殖橄笫堇嘈汀Ｕ庋龌褂幸桓龊么Γ约航椿垡坏悴聘弧?/SPAN>
我的写作风格
编译器我选用的是VC6，因此，我不保证我提供的代码在别的编译器也能通过——从......
数据结构学习（C++）——单链表（定义与实现）(2007-04-02 06:16:00)
摘要：
节点类
#ifndef Node_H
#define Node_H
template <class Type> class Node //单链节点类
{
public:
Type data;
Node<Type> *link;
Node() : data(Type()), link(NULL) {}
Node(const Type &item) : data(item), link(NULL) {}
Node(const Type &item, Node<Type> *p) : data(item), link(p) {}
};
#endif
【说明】因为数据结构里用到这个结构的地方太多了，如果用原书那种声明友元的做法，那声明不知道要比这个类的本身长多少。不如开放成员，事实上，这种结构只是C中的struct，除了为了方便初始化一下，不需要任何的方法，原书那是画蛇添足。下面可以看到，链表的public部分没有返回Node或者Node*的函数，所以，别的类不可能用这个开放的接口对链表中的节点操作。
【重要修改】原书的缺省构造函数是这样的Node() : data(NULL), link(NULL) {} 。我原来也是照着写的，结果当我做扩充时发现这样是不对的。当Type为结构而不是简单类型（int、……），不能简单赋NULL值。这样做使得定义的模板只能用于很少的简单类型。显然，这里应该调用Type的缺省构造函数。 这也要求，用在这里的类一定要有缺省构造函数。在下面可以看到构造链表时，使用了这个缺省构造函数。当然，这里是约定带表头节点的链表，不带头节点的情况请大家自己思考。
【闲话】请不要对int *p......