博文
数据结构中关键路径算法的实现与应用(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++）——单链表应用（一元多项式【2】）(2007-04-02 05:40:00)
摘要：按照原书的安排，对多项式的讲解到上一篇就应该结束了，但我还想做一些延伸。比如说，你很清楚多项式的系数肯定不总是整数，但为什么用整型呢？我看到原书用的是整型，我也有这个疑问。但是，一旦动起手来，就会发现改成浮点不仅仅只是在定义Term时把int coef;改成float coef;很多的细节都要考虑到（给个提示，你知道浮点零是多少吗）。我试了一下，最后放弃了；理由是，写这些只是为了学习，没必要搞的那么复杂，能说明问题就可以了。
在下面将会有些重载运算符的例子，我们的工作将是使多项式的运算看起来更符合书写习惯。完成这些是我觉得我擅自将原书的“＋”改成了PolyAdd()，总要给个交待吧。很快你就会看到原位运算的多项式加法在多项式运算中有多么重要，往下看之前，请确保弄懂了上一篇的内容。
准备工作
下面将完成单链表的赋值运算的重载，请把这部分加到List类的public部分。的确，这部分也可以放在多项式类里实现；但是，复制一个多项式实际上就是复制一个单链表，与其单单做一个多项式赋值，还不如完成单链表的赋值，让派生类都能共享。
operator = (const List<Type> &l)
{
MakeEmpty();
for (Node<Type> *p = l.first->link; p != NULL; p = p->link) LastInsert(p->data);
}
还记得List类的private里面的这个List(const List<Type> &l)吗？当初怕它惹祸，直接将它禁用了，既然现在=都能用了，为了这种语法List<Type> b = a;顺便也把它完成了吧。现在可以把它从private放到publ......
数据结构学习（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号苹果这样的顺序成功遍历。好，我们解决了遍历苹果的问题……慢，我们现在是设计一个算法的抽象模型，如果一切待穷举的对象都已经活生生地摆在那里，当然有可能把它们全部收集起来并排队，但如果开始的时候我们并不知道所有要穷举的对象，比如我们或许要通过一台安装在探测飞船内的计算机在全宇宙范围内穷举出除地球以外有生命的星球，那么我们的计算机可能是随着飞船的前行方能不断地得到新星球的信息，而不是停在地球的时候就获得全宇宙的星球信息（就算可能，内存或许也装不下如此大的数据量——哪怕宇宙真的是有限“大”的）。所以我们不应当要求穷举进行之前就能获得状态全集中的所有状态，这样一来，我们的“苹果数组”计划就宣告流产了。现在再看看我们激动人心的星球搜索计划：它并没有把所有星球收罗排队，那么它成功的关......
数据结构学习（C++）——线索化二叉树【2】(2007-04-02 05:33:00)
摘要： 线索化二叉树
这是数据结构课程里第一个碰到的难点，不知道你是不是这样看，反正我当初是费了不少脑细胞——当然，恼人的矩阵压缩和相关的加法乘法运算不在考虑之列。我费了不少脑细胞是因为思考：他们干什么呢？很欣喜的看到在这本黄皮书上，这章被打了*号，虽然我不确定作者是不是跟我一个想法——线索化二叉树在现在的PC上是毫无用处的！——不知我做了这个结论是不是会被人骂死，^_^。
为了证明这个结论，我们来看看线索化二叉树提出的缘由：第一，我们想用比较少的时间，寻找二叉树某一个遍历线性序列的前驱或者后继。当然，这样的操作很频繁的时候，做这方面的改善才是有意义的。第二，二叉树的叶子节点还有两个指针域没有用，可以节省内存。说真的，提出线索化二叉树这样的构思真的很精巧，完全做到了“废物利用”——这个人真应该投身环保事业。但在计算机这个死板的东西身上，人们的精巧构思往往都是不能实现的——为了速度，计算机的各个部件都是整齐划一的，而构思的精巧往往都是建立在组成的复杂上的。
我们来看看线索化二叉树究竟能不能达到上面的两个目标。
求遍历后的线性序列的前驱和后继。前序线索化能依次找到后继，但是前驱需要求双亲；中序线索化前驱和后继都不需要求双亲，但是都不很直接；后序线索化能依次找到前驱，但是后继需要求双亲。可以看出，线索化成中序是最佳的选择，基本上算是达到了要求。
节省内存。添加了两个标志位，问题是这两个位怎么储存？即使是在支持位存储的CPU上，也是不能拿位存储器来存的，第一是因为结构体成员的地址是在一起的，第二是位存储器的数目是有限的。因此，最少需要1个字节来储存这两个标志位。而为了速度和移植，一般来说，内存是要对齐的，实际上根本就没节省内存！然而，当这个空间用来储存双亲指针时，带来的方便绝对不是线索化所能比拟的，前面已经给出了无栈的非递归遍历。并且，在线索化二叉树上插入删除操作附加的代价太大。
综上，线索化最好是中序线索化（前序后序线索化后还得用栈，何必要线索化呢），附加的标志域空间至少1个字节，在32位的CPU会要求对齐到4字节，还不如存储一个双亲指针，同样能达到中序线索化的目的，并且能带来其他的好处。所以，线索化二叉树在现在的PC上是毫无用处的！
......
利用C++实现哈夫曼算法(2007-04-02 05:29:00)
摘要： 我想每个计算机专业的学生或多或少都接触过哈夫曼编码，数据结构中的老问题了。大体就是给出一些字符，和这些字符的出现频率，让你为这些字符设 计 一个二进制编码，要求频率最高的字符的编码最短。解决的方法是构造一棵哈夫曼树（二叉树），其基本思路是，每次从这些字符中挑出两个频率最低 的， 然后构造一个新的结点，使新结点的左右孩子指针分别指向那两个节点。我想这个大家都很清楚了，我就不多说了。主要讲下这次我用C++实现时遇到 的问 题。首先，我定义了一个哈夫曼树结点：
class hNode{ public: friend bool operator > (hNode n1,hNode n2); //定义了大于符号，供优先队列排列使用 hNode(string d="",int i=0,hNode* l = NULL,hNode* r =NULL):left(l),right(r),data(d),value(i){} hNode* left; hNode* right; string data; //储存的字符串 int value; //字符串出现的次数};bool operator >(hNode n1,hNode n2){ return n1.value > n2.value;} 因为只是算法课的小作业，所以我也不准备为hNode定义完整的二叉树操作，仅 仅只是存放数据的对象，所以只有一个构造函数，并且所有的data member都是公有的。 这此写这个算法会遇到大麻烦，主要因为是用了 std::priority_queue容器。当时考虑到在哈夫曼中要每次挑选两个频率最小（即出现次数最小，我那个hNode里的value是出现的次数），很自然的就想到了 std::priority_queue容器，优先队列每次都会弹出队列中权值最高的元素，这个特性无疑是实现哈夫曼算法的最佳选择。然而因为第一次用 std::priority_queue容器，结果出了不少问题，好在最后都一一解决，也学到了不少东西。 初步的设想是这样的，先把所有的hNo......
数据结构学习（C++）——图【4】（最短路径）(2007-04-02 05:26:00)
摘要：最短路径恐怕是图的各种算法中最能吸引初学者眼球的了——在地图上找一条最短的路或许每个人都曾经尝试过。下面我们用计算机来完成我们曾经的“愿望”。
在图的算法中有个有趣的现象，就是问题的规模越大，算法就越简单。图是个复杂的结构，对于一个特定问题，求解特定顶点的结果都会受到其他顶点的影响——就好比一堆互相碰撞的球体，要求解特定球体的状态，就必须考虑其他球体的状态。既然每个顶点都要扫描，如果对所有的顶点都求解，那么算法就非常的简单——无非是遍历吗。然而，当我们降低问题规模，那很自然的，我们希望算法的规模也降低——如果不降低，不是杀鸡用牛刀？但是，正是由于图的复杂性，使得这种降低不容易达到，因此，为了降低算法的规模，使得算法就复杂了。
在下面的介绍中，清楚了印证了上面的结论。人的认知过程是从简单到复杂，虽然表面看上去，求每对顶点之间的最短路径要比特定顶点到其他顶点之间的最短路径复杂，但是，就像上面说的，本质上，前者更为简单。下面的介绍没有考虑历史因素（就是指哪个算法先提出来），也没有考虑算法提出者的真实想法（究竟是谁参考了或是没参考谁），只是从算法本身之间的联系来做一个阐述，如有疏漏，敬请原谅。
准备工作
一路走下来，图类已经很“臃肿”了，为了更清晰的说明问题，需要“重起炉灶另开张”，同时也是为了使算法和储存方法分开，以便于复用。
首先要为基本图类添加几个接口。
template <class name, class dist, class mem>
class Network
{
public:
int find(const name& v) { int n; if (!data.find(v, n)) return -1; return n; }
dist& getE(int m, int n) { return data.getE(m, n); }
const dist& NoEdge() { return data.NoEdge; }
};
template <class name......
Huffman树的建立问题(2007-03-27 23:58:00)
摘要： 我今天写了个利用最小堆建立哈夫漫树。在最小堆每个单独的程序我都编译过没有问题了，但是在放在建立huffman树中就出现了，问题。哪位高手帮我解决一下。非常感谢！
一下是程序：
树结点类实现。
//“HuffmanTreeNode.h"
#if ! defined(_HUFFMANTREENODE_H)#define _HUFFMANTREENODE_H
template<class Elem>class HuffmanTreeNode{ private: HuffmanTreeNode* left; HuffmanTreeNode* right; HuffmanTreeNode* parent; Elem element; public: HuffmanTreeNode(Elem elementval,HuffmanTreeNode* leftval=NULL, HuffmanTreeNode* rightval=NULL, HuffmanTreeNode* parentval=NULL) { element=elementval; left=leftval; right=rightval; parent=parentval; } HuffmanTreeNode(HuffmanTreeNode* leftval=NULL,HuffmanTreeNode* rightval=NULL, HuffmanTree......
最小堆优先队列C++实现(2007-03-27 16:49:00)
摘要： 最小堆的优先队列实现。
在建立最小堆或最大堆时。最主要的就是理解。SiftDown和SiftUp算法的实现问题。其实我觉得自己在画一棵树。先比较左右再比较父点之间。是最大堆往上。最小堆往下。就很能理解了，
下面程序是最小堆。#include <iostream>using namespace std;
template<class Elem>class MinHeap{private: Elem* heapArray; int CurrentSize; int MaxSize;public: MinHeap(const int n); virtual~ MinHeap() { delete []heapArray; } void BuildHeap(); bool isLeaf(int pos) const; int leftChild(int pos) const; int rightChild(int pos) const; //return parent position int parent(int pos) const; //删除给定下标的元素。 bool Remove(int pos,Elem& node); void SiftDown(int left); void SiftUp(int position); bool Insert(const Elem& newNode); Elem& RemoveMin(); bool print() const;};template<class Elem>MinHeap<Elem>::MinHeap(const int n){ if(n<=0) return ;&n......
如何系统地学习Linux（转）(2007-03-24 22:33:00)
摘要：linux太难用了!(一通鼠标点击，进入/etc)学习linux,你忘记windows的思维方式了吗？怎么安装软件阿？那一堆文件是干什么的阿？学习linux,你还在浮躁吗？进入linux,随便按了几下.赶紧重启进入win学习linux,你用心了吗？.......你我共勉之linux太难用了!(一通鼠标点击，进入/etc)学习linux,你忘记windows的思维方式了吗？怎么安装软件阿？那一堆文件是干什么的阿？学习linux,你还在浮躁吗？进入linux,随便按了几下.赶紧重启进入win学习linux,你用心了吗？.......你我共勉之作者:GuCuiwen email:win2linux@163.com版权声明:本文档可以在网络上在非商业范围内自由转载,转载请注明出处如果转载版面包含商业广告,请向作者支付至少每千字100园的稿费以书面,书籍形式转载和出版请按至少每千字100园人民币的标准向作者支付稿费首先,我想引用一下别人说过的一句话:除非在过去的十年你一直生活在山洞里,否则你一定听说过linux.是的,现在听说过linux,会一点linux基本操作的人多如牛毛,然而真正能用linux做一点事情的确少之又少,这就造成了现在的状况:各大 linux论坛十分热闹,但我国linux人材却还十分紧缺.到底是什么原因造成了这样的状况? 纠其原因,只有两个字:浮燥!如果在论坛里来一次调查投票,看一下在论坛里的人到底有多少人手头有一本以上的正规linux教材.我想这个数字不会超过30%. 如果再问一下,有多少人完整的读过各发行版自带的入门文档,系统定制文档,系统管理文档和系统安全文档,恐怕这个数字不到10%. 如果进一步再调查一下究竟有多少人静下心来学习过操作系统和计算机网络等和linux学习十分密切的专业课程,那么恐怕只有3%的数字都不到了.这让我想到了98年前后IT泡沫时代的中关村.在中关村的大街小巷,到处是一个个意气分发牛哄哄的IT精英.他们戴着默镜,剔着小平头,张口闭口都是网络, 安全,信息,黑客,代码,产业.T恤背后写着三个字:别惹我! 然而最后IT泡沫一过,只有那些真正肯安安心心静心学习的人在IT界存活了下来.现在国人学习linux的状况也是这样,学linux的人个个都意气分发,以为学习linux会用linux是多么了不起.学了一点皮毛就认为很牛了.但是那些企业用......