博文
数据结构学习（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......
C++常用排序算法(2007-04-02 05:59:00)
摘要：//选择排序法SelectionSort(int arr[],int n)template <typename T>void SelectionSort(T arr[],int n){ int smallIndex; //表中最小元素的下标 int pass,j; //用来扫描子表的下标 T temp; //用来交换表元素的临时变量
//pass的范围是0~n-2 for (pass=0;pass<n-1;pass++) { //从下标pass开始扫描子表 smallIndex=pass; //j遍历整个子表arr[pass+1]到arr[n-1] for(j=pass+1;j<n;j++)
//如果找到更小的元素,则将该位置赋值给smallIndex if(arr[j]<arr[smallIndex]) smallIndex=j;
//如果smallIndex和pass不在相同的位置 //则将子表中的最小项与arr[pass]交换 if(smallIndex!=pass) { temp=arr[pass]; arr[pass]=arr[smallIndex]; arr[smallIndex]=temp; } }}
/************************************************************************双端选择排序算法:是上面选择排序算法的变种,可以定位每......
常用查找算法(2007-04-02 05:58:00)
摘要：//search.h包含了所有的常用查找算法
//使用顺序查找法的查找函数//seqSearch(const int arr[],int first,int last,int target)template <typename T>int seqSearch(const T arr[],int first,int last,const T& target){ int i=first;
//扫描下标范围first<=i<last; 测试是否有匹配 //或下标超出范围 while (!(i==last)&&!(arr[i]==target)) i++;
return i; //i是匹配值的下标,或者,如果没有匹配,则i=last}
//模板函数find_last_of()的实现template <typename T>int find_last_of(const T arr[],int first,int last,const T& target){ int i=last-1;
//描扫下标范围first<=i<last;测试是否有匹配 //或下标超出范围 while(i>=first&&target!=arr[i]) i--; if (i<first) return last; //没找到,则返回last return i;}
//二分查找算法函数binSearch()的实现template <typename T>int binSearch(const T arr[],int first,int last,const T& target){ int mid; //中间点的下标 T midVal......
数据结构学习（C++）续——排序【3】交换排序(2007-04-02 05:57:00)
摘要：交换排序
基本思想是：两两比较待排序记录的关键码，如果发生逆序，则交换之，直到所有对象都排好为止。
起泡排序
起泡排序是比较相邻的两个记录，逆序则交换。这样的做法导致小的关键码一层层的浮上来，因此得名。CSDN的论坛曾经讨论过“冒泡”和“起泡”是不是一个东西，看来这是翻译惹的祸，英文名都是Bubble Sort，具体写的时候可以正着排，也可以倒着排。（严版是从后往前排，殷版是从前往后排，好在两本书都翻译为“起泡排序”，不然就正像某些人得出的结论——一个是从后往前排，一个是从前往后排）
template <class T>
void BubbleSort(T a[], int N, int& KCN, int& RMN)
{
KCN = 0; RMN = 0; bool exchange = true;
for (int i = 1; i < N && exchange; i++)
for (int j = N - 1; j >= i; j--)
{
exchange = false;
if (++KCN && a[j - 1] > a[j]) { sw......