博文
数据结构学习（C++）——图【1】（基本储存方法）(2007-04-02 06:10:00)
摘要：首先告诉大家一个好消息，数据结构到这里就要结束了！然后再来一个坏消息，这里是数据结构中“最没有意义”的部分和最难的部分。图的应用恐怕是所有结构中最宽泛的了，但这也注定了在讲“数据结构的图”的时候没什么好讲的——关于图的最重要的是算法，而且相当的一部分都是很专业的，一般的人几乎不会接触到；相对而言，结构就显得分量很轻。你可以看到关于图中元素的操作很少，远没有单链表那里列出的一大堆“接口”。——一个结构如果复杂，那么能确切定义的操作就很有限。
不管怎么说，还是先得把图存起来。不要看书上列出了好多方法，根本只有一个——邻接矩阵。如果矩阵是稀疏的，那就可以用十字链表来储存矩阵（见前面的《稀疏矩阵（十字链表）》）。如果我们只关系行的关系，那么就是邻接表（出边表）；反之，只关心列的关系，就是逆邻接表（入边表）。
下面给出两种储存方法的实现。
#ifndef Graphmem_H
#define Graphmem_H
#include <vector>
#include <list>
using namespace std;
template <class name, class dist, class mem> class Network;
const int maxV = 20;//最大节点数
template <class name, class dist>
class AdjMatrix
{
friend class Network<name, dist, AdjMatrix<name, dist> >;
public:
AdjMatrix() : vNum(0), eNum(0)
{
vertex = new name[maxV]; edge = new dist*[maxV];
......
数据结构学习（C++）——图【2】（DFS和BFS(2007-04-02 06:09:00)
摘要：对于非线性的结构，遍历都会首先成为一个问题。和二叉树的遍历一样，图也有深度优先搜索（DFS）和广度优先搜索（BFS）两种。不同的是，图中每个顶点没有了祖先和子孙的关系，因此，前序、中序、后序不再有意义了。仿照二叉树的遍历，很容易就能完成DFS和BFS，只是要注意图中可能有回路，因此，必须对访问过的顶点做标记。
最基本的有向带权网
#ifndef Graph_H
#define Graph_H
#include <iostream>
#include <queue>
using namespace std;
#include "Graphmem.h"
template <class name, class dist, class mem>
class Network
{
public:
Network() {}
Network(dist maxdist) { data.NoEdge = maxdist; }
~Network() {}
bool insertV(name v) { return data.insertV(v); }
bool insertE(name v1, name v2, dist cost) { return data.insertE(v1, v2, cost); }
name& getV(int n) { return data.getV(n); }
int nextV(int m, int n = -1) { return data.nextV(m, n); }
......
数据结构学习（C++）——树（总结）(2007-04-02 06:08:00)
摘要：才刚开了个头，就要说再见了——在树这里，除了二叉树，别的都还没有讲。为什么可以总结了呢？因为前面已经涉及到了树的两个基本用途，而如果再讲B＋、B－，就不能不提到搜索，如果是胜者树就不能不提到排序。为此，把这部分放到后面。我前面所做的努力，只是让你有个基本概念，什么时候记得用树。
树的两个基本用途，可以用物质和精神来比喻。
一个用途是做为数据储存，储存具有树结构的数据——目录、族谱等等。为了在实际上是线性的储存载体上（内存、磁盘）储存非线性的树结构，必须有标志指示出树的结构。因此，只要能区分根和子树，树可以采取各种方法来储存——多叉链表、左子女－右兄弟二叉链表、广义表、多维数组。由于操作的需求，储存方法并不是随意选取的。比如，在并查集的实现上，选取的是双亲链表。
一个用途是做为逻辑判断，此时会常常听到一个名词——判定树。最常用的结构是二叉树，一个孩子代表true，一个孩子代表false。关于多叉判定树，有个例子是求8皇后的全部解——这个连高斯都算错了（一共是92组解，高斯最开始说76组解），我们比不上高斯，但是我们会让computer代劳。
就像哲学界到现在还纠缠于物质和精神本源问题，实际上在树这里也是如此。有些情况下，并不能区分是做为储存来用还是做为判断来用，比如搜索树，既储存了数据，还蕴涵着判断。
和后面的图相比，树更基本，也更常用。你可以不知道最短路径怎么求，却每时每刻都在和树打交道——看看你电脑里的文件夹吧。
最后，附带一个求N皇后的全部解的程序。
#include <stdio.h>
#define N 8
int layout[N];//布局
int key = 0;
int judge(int row, int col)//判断能否在（row，col）放下
{
int i;
for (i = 0; i < row; i++)
{
i......
数据结构学习（C++）——图【3】（无向图）（下）(2007-04-02 06:08:00)
摘要：最小生成树
说人是最难伺候的，真是一点不假。上面刚刚为了“提高可靠性”添加了几条多余的边，这会儿又来想办法怎么能以最小的代价把所有的顶点都连起来。可能正是人的这种精神才使得人类能够进步吧——看着现在3GHz的CPU真是眼红啊，我还在受500MHz的煎熬，然后再想想8086……
正如图的基本元素是顶点和边，从这两个方向出发，就能得到两个算法——Kruskal算法（从边出发）、Prim算法（从顶点出发）。据说还有别的方法，恕我参考资料有限，不能详查。
最小生成树的储存
显然用常用的树的储存方法来储存没有必要，虽然名曰“树”，实际上，这里谁是谁的“祖先”、“子孙”并不重要。因此，用如下的MSTedge结构数组来储存就可以了。
template <class dist>
class MSTedge
{
public:
MSTedge() {}
MSTedge(int v1, int v2, dist cost) : v1(v1), v2(v2), cost(cost) {}
int v1, v2;
dist cost;
bool operator > (const MSTedge& v2) { return (cost > v2.cost); }
bool operator < (const MSTedge& v2) { return (cost < v2.cost); }
bool operator == (const MSTedge& v2) { return (cost == v2.cost); }
};
Kruskal算法
最小生成树直白的讲就是，挑选N－1条不产......
数据结构学习（C++）——图【3】（无向图）（上）(2007-04-02 06:07:00)
摘要：要是在纸上随便画画，或者只是对图做点示范性的说明，大多数人都会选择无向图。然而在计算机中，无向图却是按照有向图的方法来储存的——存两条有向边。实际上，当我们说到无向的时候，只是忽略方向——在纸上画一条线，难不成那线“嗖”的就出现了，不是从一头到另一头画出来的？
无向图有几个特有的概念，连通分量、关节点、最小生成树。下面将分别介绍，在此之前，先完成无向图类的基本操作。
无向图类
template <class name, class dist, class mem>
class Graph : public Network<name, dist, mem>
{
public:
Graph() {}
Graph(dist maxdist) : Network<name, dist, mem> (maxdist) {}
bool insertE(name v1, name v2, dist cost)
{
if (Network<name, dist, mem>::insertE(v1, v2, cost))
return Network<name, dist, mem>::insertE(v2, v1, cost);
return false;
}
};......
数据结构学习（C++）——二叉树【1】(2007-04-02 06:06:00)
摘要：这些天参与了CSDN论坛的讨论，改变了我以前的一些看法。回头看我以前的东西，我虽对这本书很不满，但我还是按照它的安排在一点点的写；这样就导致了，我过多的在意书中的偏漏，我写的更多是说“这本书怎样”，而偏离了我写这些的初衷——给正在学习数据结构的人一些帮助。正像我在前面所说的，虽然现有的教科书都不是很合理，但如果仅仅是抱怨这点，那无异于泼妇骂街。虽然本人的水平连初级都够不上，但至少先从我做一点尝试，以后这门课的教授方法必将一点点趋于合理。
因此，后面不在按照书上的次序，将本着“实际应用（算法）决定数据结构”的思想来讲解，常见教科书上有的，基本不再重点叙述（除了重点，例如AVL树的平衡旋转），——因此，在看本文的同时，一定要有一本教科书。这只是一个尝试，希望大家多提宝贵意见。
树
因为现实世界中存在这“树”这种结构——族谱、等级制度、目录分类等等，而为了研究这类问题，必须能够将树储存，而如何储存将取决于所需要的操作。这里有个问题，是否允许存在空树。有些书认为树都是非空的，因为树表示的是一种现实结构，而0不是自然数；我用过的教科书都是说可以有空树，当然是为了和二叉树统一。这个没有什么原则上的差别，反正就是一种习惯。
二叉树
二叉树可以凳侨嗣羌傧氲囊桓瞿Ｐ停虼耍市碛锌盏亩媸魇俏拚榈摹６媸魇怯行虻模蟊哂幸桓龊⒆雍陀冶哂幸桓龅亩媸魇遣煌牧娇檬鳌Ｗ稣飧龉娑ǎ且蛭嗣歉秤枇俗蠛⒆雍陀液⒆硬煌囊庖澹诙媸鞯母髦钟τ弥校憬崆宄目吹健Ｏ旅嬷唤步饬词浇峁埂？锤髦纸彩萁峁沟氖椋慊岱⑾忠桓鲇腥さ南窒螅涸诙媸髡饫铮静僮饔屑扑闶鞲摺⒏髦直槔褪敲挥胁迦搿⑸境鞘魇窃趺唇⑵鹄吹模科涫嫡夂芎美斫猓杂诜窍咝缘氖鹘峁梗迦肷境僮鞑辉谝欢ǖ姆ㄔ蚬娑ㄏ拢呛廖抟庖宓摹Ｒ虼耍挥性诰咛宓挠τ弥校呕嵊胁迦肷境僮鳌?SPAN lang=EN-US>
节点结构
数据域、左指针、右指针肯定是必须的。除非很少用到节点的双亲，或者是资源紧张，建议附加一个双亲指针，这将会给很多算法带来方便，尤其是在这个“空间换时间”的时代。
template <class T>
struct BTNode
{
BTNode(T data = T(), BTNode<T>* left = NULL, ......
数据结构学习（C++）——图（总结）(2007-04-02 06:04:00)
摘要：以上就是现在的教科书里面，图的全部内容了。写完之后，茫茫然，不知道学完之后有什么用……就像我在开篇写的，图的应用太广泛了，以至于现在觉得图“没什么用”——很奇怪的逻辑，只有仔细体味才能觉察到写教科书的人的无奈。
不同于前面的链表和树，在图这里，储存方法不是重点，我们更多的注意力放在了算法上。我在写程序的时候，也尽量做到了算法和储存方法无关。然而算法实际上就是现实问题的抽象，如果我们的常识所不及，我们也就没有办法来介绍算法，反过来说，几乎遇不到的问题，我们也不会对它的算法感兴趣。
因此，在图的算法里面，由铺设管道引出了最小生成树，由提高通信、交通网络可靠性引出了关节点和重连通分量，由地图寻径引出了最短路径，由工程预算引出了关键路径。这些恐怕是我们能够理解的全部了，如果再来一个电气网络计算，没点物理知识恐怕是要完。
但即使这样，上面的各个算法仍然离我们很远，我们大多数人恐怕永远都不会知道管道是怎么铺的。我想，这里面除了最短路径能引起大多数人的兴趣之外，其他的就只能走马观花的看看罢了。这也使得图的学习很像“聋子的耳朵”，真正接触到图的用途的人不多，并且即使用到图，也仅仅是个别的算法。
正像数据结构教学的通病一样，学无所用常常导致学无所成，前面的链表、树好歹还能做点什么东西出来，到了图这里，除了做个导游系统，我们也做不出别的什么了。写到这里很无奈，但我也只能是无奈……
那么，学完了图，我们应该掌握什么呢，是上面零散的算法吗？我的看法是，不是。我觉得我们更应该知道那些算法是怎么“创造”出来的，如果遇到了类似的问题，能不能“派生”出新的算法。因此，我觉得《数据结构算法与应用-C++语言描述》这本书，将图的最小生成树、最短路径、拓扑排序算法放到了贪婪算法里讲解，是一种更为合理的安排。
最后对在学习图时像我一样茫然的人深表同情。......
数据结构学习（C++）——后记(2007-04-02 06:03:00)
摘要：这回真的是后记了，也就是到了这些文章结束的时候了。虽然还有排序和查找两大算法系没有讲，但是对于“数据结构”而言，上面应该是全部了。并且这些文章加在一起已经很长了，每次打开WORD来编辑，跳到末页总是不那么顺畅，是到了结束的时候了。对于那两大算法系，我准备另外再开一个系列，姑且就叫做《数据结构学习（C++）续》吧。突然发现，在安排文章结构上不知不觉的受了《计算机编程艺术》的影响了。
我的参考书主要是三本，《数据结构（用面向对象方法与C++描述）》（殷人昆等），《数据结构（C语言版）》（严蔚敏、吴伟民），《数据结构算法与应用-C++语言描述》（中译名，详细信息可查china-pub）。
能写完这些文章，首先要感谢C++语言，如果让我拿C来写，没准中途就放弃了。前不久还看到有人争论数据结构用什么语言描述最合适，有人还在坚持用C最好，按照他的看法，汇编没准是最好的（有兴趣可以看看《计算机编程艺术》是拿什么语言写的）。从ADT的思想来看，C是不合适的，因为C要把数据和数据上的操作封装在一起非常的麻烦，并且只有利用文件来组织这种关系，而对于初学者来说，多模块编译链接本身就是一个很玄的事，当年学C语言的时候这部分都没敢看。而C++的类能非常完美的表达ADT的思想，并且模板⒅卦亍⒓坛心芨逦谋硎鍪萁峁怪涞牧怠９赜?/SPAN>C++在解决问题上比C的优势，可以看看《C++沉思录》，有非常有说服力的例子，当然，从运行效率来说，C要强于C++。
然而当选用了C++之后，有件事就非常尴尬了，就是STL。常用的数据结构、算法都已经作为C++标准的一部分了，我就看到一本书是用STL来描述数据结构的（只看到了书名，没看到内容）。前面的三部分，线性表在STL里全部都有现成的（变长数组、链表、队列、栈），二叉搜索树在SGI－STL里有红黑树的实现，只有图标准库没有提供，但是图最重要的是一堆算法。排序、查找在STL里也有现成的。
这让我想起了“程序员＝民工”的论调，的确，现在的语言、开发工具在给程序员提供了便利的同时，也限制了程序员的思维，养成了他们的惰性。现在编程就是在Framework里面改写若干的函数，在我们感到这种方式的便利的同时，也越来越感到自己力量的渺小。也许人就是种奇怪的动物。
或许数据结构这门课程根本就不是让你掌握那些链表、树是如何实现的。开设这门课第一个目的......
数据结构学习（C++）续——排序【2】插入排序(2007-04-02 06:03:00)
摘要：基本思想是，每步将一个待排序的记录，按其关键码大小，插入到前面已经排好序的记录的适当位置，从头做到尾就可以了。
直接插入排序
template <class T>
void InsertSort(T a[], int N, int& KCN, int& RMN)
{
KCN = 0; RMN = 0;
for (int i = 1; i < N; i++)
{
T temp = a[i]; RMN++;
for (int j = i; j > 0 && ++KCN && temp < a[j - 1]; j--) { a[j] = a[j - 1]; RMN++; }
a[j] = temp; RMN++;
}
}
精简之后就是这样：
template<class T> void InsertSort(T a[], int N)
{
for (int i = 1; i < N; i++)
{
T tem......
数据结构学习（C++）续——排序【5】归并排序(2007-04-02 06:01:00)
摘要：【5】归并排序当初学习链表的时候，我们都曾经做过将两个有序链表合成一个有序链表的练习。那时我们就知道了归并的特点就是，将分段有序的序列合成整体有序的序列。在内部排序中，归并的地位并不十分重要，主要是因为附加的O(n)的储存空间；但是，归并却是外部排序的不二法门——我们只能用内排得到分段有序的序列，为了得到最后的有序序列，必须使用归并的方法。
迭代的2路归并排序2路归并是最简单的，并且单纯对内存中数据操作2路的往往是最好的（比如平衡树，AVL树经常优于m叉的平衡树）。所谓的迭代就是先归并len＝1的N个序列，然后是len＝2的N/2个序列，len＝4的N/4个序列……最后归并2个序列就完成了。实际写的时候，需要一个和原来序列一样大小的临时数组。执行偶数次“一趟归并”能够使得最后的结果保存在原来的数组中。
//迭代2路归并排序及其所需的子程序
template <class T>
void Merge(T S[], T D[], int l, int m, int n, int& KCN, int& RMN)
{
//S[]源表，D[]归并后的表，l源表第一个段的起始序号，m源表第二个段的起始序号，n源表的长度
int i = l, j = m, k = l;//i第一段的指针，j第二段的指针，k目的表指针
for (; i < m && j < n; RMN++, k++)
if (++KCN && S[i] > S[j]) { D[k] = S[j]; j++; } else { D[k] = S[i]; i++; }
if (i < m)
&n......