博文
数据结构学习（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......
前序，中序，后序，广度的非递归程序实现(2007-03-24 21:39:00)
摘要： 早学完了二叉树。也知道了前序，中序，后序，广度的非递归是怎么实现的。但是一直没有写出程序出来。今天周末就把他写出来了，我觉得这些程序都很容易理解。所有没写什么注释了，这是用C++实现的。在栈是用STL种的栈实现的。如果大家用C语言编写，就一定要记得把它的栈写出来才可以实现。在整个程序中比较难理解的就是找父亲结点的算法和后序非递归实现的A，B。仔细理解还是看的懂的。程序我在VC6.0中实现的。其他编译器就不能保证了。
程序如下：
// 二叉树的建立。//前序，中序，后序，广度的非递归程序实现。#include <iostream>#include <stack>#include <queue>
using namespace std;
enum Tags{Left,Right};
template <class Elem>class TreeNode{ public: TreeNode* left; TreeNode* right; Elem data; TreeNode(Elem dataval,TreeNode* leftval=NULL,TreeNode* rightval=NULL) { data=dataval; left=leftval; right=rightval; } TreeNode(TreeNode* l......
二叉树的前序递归建立的详解(2007-03-23 19:57:00)
摘要： 这个二叉树的创建方法清华那本书中有一个通过前序建立的二叉树。我根据那里写了一个算法。
void BinTree<Elem>::Create(BinTreeNodeT<Elem> *Troot){ char ch; cin>>ch; if(ch=='$') Troot=NULL; else { Troot=new BinTreeNodeT<Elem>(ch,NULL,NULL); Create(Troot->left); Create(Troot->right); }}
可以看出这个算法的创建二叉树。可以通过Troot返回根结点。就可以创建二叉树了，但是如果你真正去试过的话。就会发现你通过Troot作为根结点进行遍历打印的时候确不能打印。甚至什么都没有啊，你看自己的程序再去推感觉真的没有错啊，怎么会没有数据呢？这个问题当时也困住我了，但是后来我用VC调试的时候发现Troot从创建的函数出来Troot==NULL所有在打印时候根本就不可能的。为什么会这样呢？我再通过调试发现在函数最后递归出来时。Troot就变成NULL了，仔细看看函数递归的过程。你就能......
浅谈程序员的数学修养 (2007-03-16 14:51:00)
摘要：可能有很多朋友在网上看过google公司早几年的招聘广告，它的第一题如下了：{first 10-digit prime found in consecutive digits e}.com，e中出现的连续的第一个10个数字组成的质数。据说当时这个试题在美国很多地铁的出站口都有大幅广告，只要正确解答了这道题，在浏览器的地址栏中输入这个答案，就可以进入下一轮的测试，整个测试过程如同一个数学迷宫，直到你成为google的一员。又如Intel某年的一道面试题目：巴拿赫病故于1945年8月31日。他的出生年份恰好是他在世时某年年龄的平方，问：他是哪年出生的？这道看似很简单的数学问题，你能不能能快地解答呢？下面则是一道世界第一大软件公司微软的招聘测试题：中间只隔一个数字的两个素数被称为素数对，比如5和7，17和19，证明素数对之间的数字总能被6整除(假设这两个素数都大于6)，现在证明没有由三个素数组成的素数对。这样的试题还有很多很多，这些题目乍初看上去都是一些数学问题。但是世界上一些著名的公司都把它们用于招聘测试，可见它们对新员工数学基础的重视。数学试题与应用程序试题是许多大型软件公司面试中指向性最明显的一类试题，这些试题就是考察应聘者的数学能力与计算机能力。某咨询公司的一名高级顾问曾说：微软是一家电脑软件公司，当然要求其员工有一定的计算机和数学能力，面试中自然就会考察这类能力。微软的面试题目就考察了应聘人员对基础知识的掌握程度、对基础知识的应用能力，甚至暗含了对计算机基本原理的考察。所以，这样的面试题目的确很“毒辣”，足以筛选到合适的人。
四川大学数学学院的曹广福教授曾说过：“一个大学生将来的作为与他的数学修养有很大的关系”。大学计算机专业学生都有感触，计算机专业课程中最难的几门课程莫过于离散数学、编译原理、数据结构，当然像组合数学、密码学、计算机图形学等课程也令许多人学起来相当吃力，很多自认为数据库学得很好的学生在范式、函数依赖、传递依赖等数学性比较强的概念面前感到力不从心，这些都是因为数学基础或者说数学知识的缺乏所造成的。数学是计算机的基础，这也是为什么考计算机专业研究生数学都采用最难试题（数学一）的原因，当然这也能促使一些新的交叉学科如数学与应用软件、信息与计算科学专业等飞速发展。许多天才程序员本身就是数学尖子，众所周知，Bill Gates的数学成绩一直都很棒，他甚......
详解链表的转置问题。(2007-02-15 01:40:00)
摘要：//题目： ------------------链表的转置------------------------// 要求：// 将链表的就地转置。就是将链表的数据存储倒置//例：// 输入：12345678910// 输出：10987654321
// 算法分析：// 程序最主要的地方再于将头接点的后的每个接点都放再头接点的前面。直到头接点到达// 尾接点。记完成了链表的转置。// 算法复杂度分析：// 只是将每个接点前移所以复杂度就链表的长度。O（N）；// 程序分析：// 程序采用的时C++实现的方式；时用类实现每个接点。程序中用到了可利用空间表，从而加快了// 程序中要删除接点再生成接点的速度。采用C++的重载new和delete函数。也用到了静态的类成员// 数据成员用来实现可利用空间表。
#include <iostream>using namespace std;//数据接点的类的实现。template <class Elem>class List{ private: static Li......
约瑟夫环C++循环单链表实现程序(2007-02-02 18:22:00)
摘要：////////////////////////////////约瑟夫环程序C++循环单链表实现。///////////当中的new和delete采用了重载函数。//也采用了可利用空间表提高了系统分配和回收的速度。// 题目：// 编号为1，2，3。。。。N的N个人按顺时针方向坐成一圈。每个人有一个密码，一开始任选一个// 整数作为报数上限值M，从第一个人开始按顺时针方向自1开始顺序报数。报到M时停止报数，报M// 的人出列，将他的密码作为下一次报数的新值M，从他的顺时针方向上的下一个人开始重新从1// 开始报数。如此下去直到所有人都出列为止。
#include <iostream>using namespace std;//每个人的号码和密码。struct people{ int NO; int pass;}node;template <class Elem>class Link{private: static Link<Elem>* freelist;//静态数据成员的头接点。public: struct people element; Link* next; Link(people elemval,Link* nextval=NULL) { element.NO=elemval.NO; element.pass=elemval.pass; next=nextval; } Link(Link* nextval=NULL) { next=nextval; } void* operator new(size_t);// 重载new 函数。 void operator delete(void*);//重载delete函数。};
template <class Elem>class LList{private: Link<Elem> *head; Link<El......