博文
数据结构学习（C++）续——排序【6】内部排序总结(2007-04-02 05:55:00)
摘要：基数排序本文后面将会提到，我觉得将其和前面的排序算法放在一起比较有些不伦不类。前面介绍了四类排序方法，每种都有基本型和改进型。对于内部排序，我们最关心的当然是速度，这也是为什么快排受欢迎的原因。考虑到快排的缺陷，有时候我们可能会用堆排或者希尔排序、归并排序。
上面可能是选择排序方法最直接的思路了（我们的选择范围也不算广，就那几个翻过来调过去的，好一点的，综合一下搞一个“杂牌”），出于“赌徒”的思维，我们大多数人可能用快排包打天下——出最坏情况？我没那么倒霉吧？大不了再加一个“三者取中”（或者随机选取）。但是，有时候速度并不是一切，我们还要考虑排序的稳定性。
前面没有涉及稳定性，主要是考虑每提到一种算法都要说一些本来并不是十分重要的“是否稳定”实在是干扰读者思路，并且前面的测试也无法反映稳定性。现在我们放在一起来说。排序的稳定性是指，对于相同的关键字，排序完成后他们的次序是否发生了改变，维持原状是稳定，否则就是不稳定的。实际上就是说，对一个多关键字序列，多次排序结果是否能够累积——多次排序能否最终达到预期的有序。打个比方，首先我们按学号对学生排序得到一个序列（在实际的应用中，初始序列总是这样的，我们根本不需要排序），然后按照成绩排序，对于成绩相同的学生，我们希望学号靠前的排在前边（预期的有序），如果排序是不稳定的，就会破坏前面按照学号排好的序列，从而导致得不到最终的预期序列。注意到是“预期有序”，在排成绩的例子中，如果我们不要求相同成绩的学号有序，排序是否稳定就无关紧要了。
什么排序算法是稳定的呢？首先看一下是什么导致了“不稳定”。注意到前边的四类方法都有稳定的算法（这是现有结论，不要问我是怎么来的，反正是就是是了，^_^），排序的思路应该不是不稳定的因素。排序肯定有记录的移动（或者指针的修改），移动方法有平移（直插排序）、交换（起泡排序）、重排（表插、归并）。仔细观察一下，就会发现，不相邻位置记录的交换是导致不稳定的因素。这样一来，凡是有这个隐患的排序算法都是不稳定的，对于原来稳定的算法，如果采用了这样的交换策略，也会导致不稳定，比如直接选择排序对于链表来说是稳定的，但对于数组来说就是不稳定的，然而，如果采用平移来代替原来的交换，那么对于数组也是稳定（估计没人愿意把本来的交换1次改成平移一堆）。
另外对于本来稳定的算法，当更改关键字判断条件后，比如大于变为大......
数据结构学习（C++）续——排序【4】选择排序(2007-04-02 05:55:00)
摘要：【4】选择排序
基本思想是：每次选出第i小的记录，放在第i个位置（i的起点是0，按此说法，第0小的记录实际上就是最小的，有点别扭，不管这么多了）。当i＝N－1时就排完了。
直接选择排序
直选排序简单的再现了选择排序的基本思想，第一次寻找最小元素的代价是O(n)，如果不做某种特殊处理，每次都使用最简单的寻找方法，自然的整个排序的时间复杂度就是O(n2)了。
template <class T>
void SelectSort(T a[], int N, int& KCN, int& RMN)
{
KCN = 0; RMN = 0;
for (int i = 0; i < N; i++)
{
for (int j = i + 1, k = i; j < N; j++) if (++KCN && a[j] < a[k]) k = j;//select min
if (k != i) { swap(a[k], a[i]); RMN += 3; }
}
}
测试结果：
Sort ascending N=10000 TimeSpared: 721ms
KCN=49995000 KCN/N=4999.5 KCN/N^2=0.49995 KCN/NlogN=376.25
RMN=0 &nb......
数据结构学习（C++）续——查找（搜索）【1】(2007-04-02 05:53:00)
摘要：相信每个人都曾感受过找东西的痛苦，大多数人也感受过计算机参与资料管理后所带来的便捷，而学过编程的也曾为了某个问题（比如实现“如果不存在则加入”这样的算法描述——排列组合算法的初级阶段）而实现过查找。在SGI-STL的stl_algo.h里面有这样一段代码：
template <class _InputIter, class _Tp>
inline _InputIter find(_InputIter __first, _InputIter __last,
const _Tp& __val,
input_iterator_tag)
{
while (__first != __last && !(*__first == __val))
++__first;
return __first;
}
这个应该能代表我们曾经写过的所有顺序查找代码，关于为什么写成了这个样子，《C++沉思录》第17章有详细的说明。或许VC6的STL代码更容易理解些：
template<class _II, class _Ty> inline
_II find(_II _F, _II _L, const _Ty& _V)
{for (; _F != _L; ++_F)
......
AVL树的实现（源码）(2007-04-02 05:52:00)
摘要：AVLTree
http://www.staroceans.com/AVLTree.htm
A. First Edition
This is first edition of my AVL Tree and I never expect it takes so long as almost one week to finish! Of course
it is partly because of Christmas when I was continually interrupt by the earthly issues such as visiting a
friend and wasting some meaningful time on meaningless matters.
B.The problem
To write AVL tree on template basis and try to keep as much as possible of original BST frame work
because the code by Mr. Shaffer is very concise and compact! And efficiency is also a very important
issue here. As AVLTree has to store extra information than a BST, it is expected that we need to
reduce as many "balancing operations" as possible.
C.The idea of program
By adding a little piece of code in "insert" method of BST, I actually try to do the keeping-balance
job along the "insert" operation from bottom-up which always keep each node up-to-date balanced. It
is believed by me the best solution to impleme......
迷宫寻路程序2(2007-04-02 05:49:00)
摘要：三，详细设计：
1.主程序文件1.cpp：
#include<stdlib.h>
#include <string.h>
#include <time.h>
#include<iostream.h>
#include"0.h"
#include"mg.h"
void main()
{
cout<<" ****************************************************************"<<endl;
cout<<" 2004数据结构课程设计之迷宫寻路"<<endl;
cout<<" 本程序根据你输入的行，列，复杂水平，生成一个矩阵图形迷宫。"<<endl;
cout<<" 0表示不可行走的障碍，1表示可以行走的路径。"<<endl;
cout<<" 程序自动寻路，用文字显示所有搜索的路径。"<<endl;
cout<<" 再用9标识最后走通的路径。"<<endl;
cout<<" ****************************************************************"<<endl;......
数据结构学习（C++）续——查找（搜索）【2】(2007-04-02 05:45:00)
摘要：树型查找
折半查找所需要的，有序的、可以随机存取的、顺序结构的限制，导致了排序的额外负担（如果是逐个添加，主要的负担是移动数据，此时是折半插入排序）。通过观察折半查找的过程，发现实际上mid是从判定树的根走到了叶子节点，而这棵判定树和有相同节点的完全二叉树的高度是相同的。链式结构的好处就是不用大量移动数据，自然的用链树来做查找结构应该是个好选择。
在前面我们曾经写过一个BSTree类，这个类大致上能满足我们的要求。而为了在不同的输入情况下，使得树的高度尽可能的小，平衡树的概念被提出来了，例如前面的AVLTree类。所谓的平衡，现在更多意义上是指和完全m叉树高度的比值是小于某个常数的树，也就是高度≤klogmn的树，k为一个定常数。注意到AVL树的定义实际上太苛刻，就很容易理解为什么要放宽要求。而实际能应用的平衡树，都是为了满足这个要求而自己定一套规则，比如B－树，这个后面会讲到。
索引
有些字典会提供一个目录，大部分情况是这样的A……xx；B……xx；……。这样就能迅速翻到开头字母对应的页数（实际上也知道了开头字母结束的地方），并且每个页的左右上角的单词也说明了本页的单词范围（可以判断所查单词在不在此页）。这些就是索引。
使用索引能够快速的定位查找范围，从我们查字典的经验看来，这也应该是能提高查找效率的方法。注意到目录的作用，它使得我们所需的字典空间分布，在一页（或者几页）的空间上迅速的被我们得到——类比来看，如果数据太多以至内存装不下，我们也可以弄个“目录”，使得可以将数据分块的读入内存查找。
B－树
当数据膨胀到一个可怕的程度时，连索引都不能被全部装入内存——见过印刷版的EI检索都有这个感觉，光一个检索目录都比我们用的字典厚。我们的办法就是索引再索引，显而易见的，每个索引块都应该尽可能的大，以帮助我们获得尽可能多的信息苊庠俅蔚牟樗饕ù耸币话愣蓟嵘婕巴獯娴拇嫒。?/SPAN>AVL树此时便力不从心了，我们需要一种新的结构。
相信每个学到这里的人都对B－树的定义深恶痛绝，这个的责任应该由写书的人来负，虽然定义、概念是人认知的重要工具和途径，但在这里是适得其反的。原因就是B－树根本不存在概念意义上的“概念”，它只是一个描述型的“概念”，是B－树能够运行从而表现出来的一种现象。不管怎么说，先看一下现有的书上的定义（省略了“或者为空树”这句话......
数据结构学习（C++）续——续篇后记(2007-04-02 05:43:00)
摘要：我觉得续篇的写作我很不负责任，越到后面越是如此，可能是我没有打算写的缘故，或者说是“心浮气躁”——写了几个月有点熬不住了，^_^。但也可能我只能写到这样，毕竟这部分离我们太远，至少和前边的“数据结构”相比是太远。
有人说，查找和排序的算法已经非常成熟了，大师们穷尽脑汁也不可能带来“质的飞跃”了，而像我们这些等着“吸收前人劳动果实”的人，能全盘吸收就甚为不易，更不要说“完成前人所未完成”了。因此，对于教科书上面的讲解，除非作者治学态度有问题（信口开河），否则没有什么好讲的。正像我前面所说的，我只是给大家读书的时候起个向导的作用，并不是想写本书，因此很多的地方都省略了。我所写的，如果使得书上枯燥的数学分析具体化，各种方法的提出不再显得突兀，我就心满意足了。
对于排序，我还显得有点耐性，除了锦标排序和基数排序、外部排序，其他的都给出了例程；对于查找，除了顺序查找和折半、插值查找，二叉搜索树，AVL树，其他的都是说说而已。造成这种结果，固然是我耐性有限，但这也是现状所致——什么东西要是不带个数据库什么的就显得不够专业，有了数据库，B－树什么的还要它作甚？说这话的时候，我常常显得很无奈，但确实是这种现状的受益者。
最后，说说怎样看待数据结构——谈这个话题就是找骂，但到了最后了，我也不怕了。数据结构现在的地位很尴尬，几乎每个有志于写程序的人都把数据结构摆在必须掌握的知识的第一位，但实际上，当必修课学的、计算机专业的学生学完之后，一半茫茫然；而非计算机专业的，甚至没学过数据结构的，程序员也干得好好的。
计算机的应用能到今天的地步，数据结构功不可没，没有串、表、树、图，计算机只能在数值计算里面打转转——现在掉过来了，真正的数值计算反倒没有多少人会写了，^_^。但，这和汇编（更有甚者是01代码，我光知道90是NOP，^_^）的处境一样，汇编也曾在计算机发展上的作用无可估量，而现在会的人真是寥寥无几，就连C的境域也是如此，虽然每所大学不管是不是计算机专业都开设C语言课程。
可以说，我们写的每个还算有点功能的程序，都离不开数据结构。比如我们当初学C的时候，都做过这样的练习：将一组输入的数据逆序输出。我们每个人几乎都能想到先拿数组存起来，然后倒着再输出。我们在这里其实就利用了线性表，只是我们没意识到。再比如我们需要一段排序的程序，而在我们没学过排序方法的时候，大多数人都会写出直接......
数据结构中关键路径算法的实现与应用(2007-04-02 05:42:00)
摘要：数据结构中关键路径算法的实现与应用
摘 要 介绍求关键路经的算法，对于给出的事件结点网络，要求求出从起点到终点的所有路径，经分析、比较后找出长读最大的路径，从而得出求关键路径的算法，并给出计算机上机实现的源程序。
关键词 关键路径 最少时间
1：引言
通常把计划、施工过程、生产流程、程序流程的都当成一个工程。除了很小的工程外、一般都把工程分为若干个叫做“活动”的子工程。完成了这些“活动”的子工程，这个工程就可以完成了。
通常我们用有向图表示一个工程。在这种有向图中，用顶点表示活动，用有向边
<Vi,Vj>表示活动Vi必须先于活动Vj进行。如果在无有向环的带权有向图中用有向边表示一个工程中的各项活动（ACTIVITY），用有向边上的权值表示活动的持续时间（DURATION），用顶点表示事件（EVENT），则这种的有向图叫做用边表示活动的网络，简称AOE（active on edges）网络。
AOE网络在某些工程估算方面非常有用。他可以使人们了解：
（1）：研究某个工程至少需要多少时间？
（2）：那些活动是影响工程进度的关键？
在AOE网络中，有些活动可以并行的进行。从源点到各个顶点，以至从源点到汇点的有向路径可能不止一条。这些路径的长度也可能不同。完成不同路径的活动所需的时间虽然不同，但只有各条路径上所有活动都完成了，这个工程才算完成。因此，完成整个工程所需的时间取决于从源点到汇点的最长路径长度，即在这条路径上所有活动的持续时间之和。这条路径长度就叫做关键路径（critical path）。
2：设计步骤：
1: 以某一工程为蓝本，采用图的结构表示实际的工程计划的时间。
2: 调查以分析和预测这个工程计划个阶段的时间。
3: 用调查的结果建立ＡＯE网（Activity On Edge Network），即边表示活动的网络，并用图的形式表示。
4: 用图来......
数据结构学习（C++）——图【5】活动网络（AOV、AOE）(2007-04-02 05:38:00)
摘要：这部分是和工程相关的，也就是说，当AOV、AOE很复杂的时候，才能显示出这部分的价值——简单的话，手工都要比程序快，输入数据那段时间手工结果就出来了。我也没什么例子好举，总给我一种没底气的感觉，勉为其难的把程序写完就算完事吧。和前边的相比，这部分专业了一点，换而言之，不是每个人都感兴趣，不想看就跳过去吧。
准备工作
活动网络主要有两个算法，拓扑排序和求关键路径，后者以前者为基础。仿照上篇，另外构造一个“算法类”，需要算法时，将图绑定到算法上。
#include "Network.h"
#define iterator list<Link<name, dist>::edge>::iterator
#define begin(i) G->data.vertices[i].e->begin()
#define end(i) G->data.vertices[i].e->end()
struct CriAct
{
CriAct() {}
CriAct(int source, int dest) : s(source), d(dest) {}
int s, d;
};
template <class name, class dist>
class ActivityNetwork
{
public:
ActivityNetwork(Network<name, dist, Link<name, dist> >* G) : G(G), N(G->vNum()), outCriAct(CA)
{
count = new int[N]; re......
闲谈C++算法封装：穷举法(2007-04-02 05:35:00)
摘要：闲谈C++算法封装：穷举法
将算法独立抽象出来，在C++中算不上新鲜：STL中就封装了不少高效、健壮、灵活的泛型组件及对应的基础算法，工艺之高、适用性之强，非寻常我辈所轻易能及。这里不打算（也暂没有能力打算）以STL这样的工业级要求来谈论算法封装，只因最近尝翻大师名著，阅者水平有限，仅嗅触至皮毛，理智薄弱，感情却蓬勃发展：也欲尝试“封装”的味道。选择了最简易的穷举算法，抽其骨架，炮制成class，套上一实际例子，观之run之，抽象程度颇低，效率损失弥彰；然却也自觉有可爱之处，遂作此文以记之。诚惶诚恐，便于名目之前加“闲谈”二字，倘果因技术问题招致痛骂，则试以此二字为护文符，聊且一挡。
众所周知，穷举法可视为最简单的搜索：即是在一个可能存在可行状态（可行解）的状态全集中依次遍历所有的元素，并判断是否为可行状态。例如，要设计一个“从一堆苹果中找出蓝色的苹果”这样的穷举算法，则定义：
(1) 状态全集：一堆苹果
(2) 可行状态：蓝色的苹果
噢，好，我们现在已经抽取了两个基本概念，迫不及待要开始穷举了，但……怎么做呢？穷举的关键是“依次遍历”，即做到不重、不漏。呃，我们可以让听话的苹果们排成一行，放在“苹果数组”中，然后呢，我们就可以按照0号苹果、1号苹果、2号苹果、...、n号苹果这样的顺序成功遍历。好，我们解决了遍历苹果的问题……慢，我们现在是设计一个算法的抽象模型，如果一切待穷举的对象都已经活生生地摆在那里，当然有可能把它们全部收集起来并排队，但如果开始的时候我们并不知道所有要穷举的对象，比如我们或许要通过一台安装在探测飞船内的计算机在全宇宙范围内穷举出除地球以外有生命的星球，那么我们的计算机可能是随着飞船的前行方能不断地得到新星球的信息，而不是停在地球的时候就获得全宇宙的星球信息（就算可能，内存或许也装不下如此大的数据量——哪怕宇宙真的是有限“大”的）。所以我们不应当要求穷举进行之前就能获得状态全集中的所有状态，这样一来，我们的“苹果数组”计划就宣告流产了。现在再看看我们激动人心的星球搜索计划：它并没有把所有星球收罗排队，那么它成功的关......