博文
Binary Search (2007-04-19 14:22:00)
摘要：Discuss this articleBinary Search
By lovroTopCoder Member
Binary search is one of the fundamental algorithms in computer science. In order to explore it, we'll first build up a theoretical backbone, then use that to implement the algorithm properly and avoid those nasty off-by-one errors everyone's been talking about. Finding a value in a sorted sequenceIn its simplest form, binary search is used to quickly find a value in a sorted sequence (consider a sequence an ordinary array for now). We'll call the sought value the target value for clarity. Binary search maintains a contiguous subsequence of the starting sequence where the target value is surely located. This is called the search space. The search space is initially the entire sequence. At each step, the algorithm compares the median value in the search space to the target value. Based on the comparison and because the sequence is sorted, it can then eliminate half of the search space. By doing this repeatedly, it will eve......
ACM上题的精确分类(2007-04-12 13:06:00)
摘要：这是PKU上的ACM题:
下面是一个列表，可以从简单的开始作
说明：递推算动归， 离散化算数据结构， 并查集算数据结构， 博弈算动归， 麻烦题一般都是不错的综合题， 最短路算图论，数据的有序化算排序
测试
麻烦题：1697, 1712, 1713, 1720, 1729, 1765, 1772, 1858, 1872, 1960, 1963, 2050, 2122, 2162, 2219, 2237,
简单题目：1000, 1003, 1004, 1005, 1007, 1046, 1207, 1226, 1401, 1504, 1552, 1607, 1657, 1658, 1674, 1799, 1862, 1906, 1922, 1929, 1931, 1969, 1976, 2000, 2005, 2017, 2027, 2070, 2101, 2105, 2109, 2116, 2136, 2160, 2190, 2232, 2234, 2275, 2301, 2350, 2363, 2389, 2393, 2413, 2419,推荐：1063, 1064, 1131, 1140, 1715, 2163,
杂题：1014, 1218, 1316, 1455, 1517, 1547, 1580, 1604, 1663, 1678, 1749, 1804, 2013, 2014, 2056, 2059, 2100, 2188, 2189, 2218, 2229, 2249, 2290, 2302, 2304, 2309, 2313, 2316, 2323, 2326, 2368, 2369, 2371, 2402, 2405, 2407,推荐：1146, 1147, 1148, 1171, 1389, 1433, 1468, 1519, 1631, 1646, 1672, 1681, 1700, 1701, 1705, 1728, 1735, 1736, 1752, 1754, 1755, 1769, 1781, 1787, 1796, 1797, 1833, 1844, 1882, 1933, 1941, 1978, 2128, 2166, 2328, 2383, 2420,
高精度：1001, 1220, 1405, 1503......
图算法的实现(2007-04-11 23:12:00)
摘要：#define UNVISITED 0#define VISITED 1#define INFINITY 9999999#define ROOT -1
#include <iostream.h>#include <fstream.h>#include "LList.h"#include "minheap.h"#include <queue>
//数据结构部分:
/**************** 图的边的定义 ***************/class Edge{public: int from,to,weight; //from是边的始点,to是边的终点,weight是边的权
Edge() //构造函数 { from=-1; to=-1; weight=0; } Edge(int f,int t,int w) //构造函数 { from=f; to=t; weight=w; }
bool operator >(Edge oneEdge) //定义比较运算符>,边的大小比较即为边的权的大小比较 { return weight>oneEdge.weight; }
bool operator <(Edge oneEdge) //定义比较运算符<,边的大小比较即为边的权的大小比较 { return weight<oneEdge.weight; }};
/**************** 图的定义 ******......
图的建立,深度搜索和广度搜索的实现(2007-04-10 17:45:00)
摘要：// 图的建立和深度搜索和广度搜索的实现#include <iostream>#include <queue>using namespace std;const int UNVISITED=1000;const int VISITED=100;
class Graph{public: virtual int n()=0; virtual int e()=0; virtual int first(int)=0; virtual int next(int,int)=0; virtual void setEdge(int, int, int)=0; virtual void delEdge(int, int)=0; virtual int weight(int, int)=0; virtual int getMark(int)=0; virtual void setMark(int,int)=0;};class Edge{public: int vertex,weight; Edge() { vertex=-1; weight=-1; } Edge(int v,int w) { vertex=v; weight=w; }};
class Graphm:public Graph{private: int numVertex,numEdge; int **matrix; int *mark;public: Graphm(int numVert) { int i,j; numVertex=numVert;&n......
用C++模板描述的链表、栈、队列（声明与实现(2007-04-02 06:46:00)
摘要：主要参考书是《数据结构（用面向对象方法与C++描述）》殷人昆等编著，清华大学出版社。原书看起来很费事，显而易见的把教学目的和提供实例的目的搞混了，结果是个四不象：作为教科书，条理不清晰；提供各个方法的实现，也不是很实用，相反，重复建设太多。但是，这是清华的考研参考书目，一定有许多人和我一样在研读此书。我把我重新定义的类和实现发表出来，就是希望和我一样的人，或者是打算学习数据结构而选择了这本书的人，能更好的理解和学习。当然，如果你想使用这些数据结构，又不想学STL，这些类也能帮你达成目的。
我照着原书的类名和对应的函数名，写下了如下的类的定义，部分代码采用了原书的。把成员函数的实现写在类定义里，完全是为了将就VC++6的ClassView，不然一双击一个成员函数，就蹦出来“我找不到它的实现”，而实际上，一般我们都看的是ClassView显示的类的接口，很少去看类的定义。这是第一部分，马上我会完成树等结构。我只测试了int类型各个成员函数的正确性，并且也没做什么“极端测试”，欢迎测试。另外，欢迎反映这样的定义是否好看些，容易懂些。
#ifndef Node_H#define Node_H
template <class Type> class Node //单链节点类{public: Type data; Node<Type> *link; Node() : data(Type()), link(NULL) {} Node(const Type &item) : data(item), link(NULL) {}};
#endif说明：因为数据结构里用到这个结构的地方太多了，如果用原书那种声明友元的做法，那声明不知道要比这个类的本身长多少。不如开放成员，事实上，这种结构只是C中的struct，除了为了方便初始化一下，不需要任何的方法，原书那是画蛇添足。
一点重要的修改：原书的缺省构造函数是这样的Node() : data(NULL), link(NULL) {} 。我原来也是照着写的，结果当我做扩充时发现这样是不对的。当Type为结构而不是简单类型（int、……），不能简单......
数据结构学习（C++）——线性链式结构总结（代后记）【2】(2007-04-02 06:23:00)
摘要：在开始写这些文章之前，我曾经有个想法，能不能以单链表为基础，完成所有的线性链式结构？实践证明，是可以的，就像你看到的这样。我做这个尝试的起因是，看不惯现在教科书凌乱的结构：罗列了一大堆ADT或者是templat class，好像这些都要你去记似的。殊不知，只有提取共性，突出个性，才能更明显的表现出各种数据结构的差异，显示数据结构的进化发展的过程，看出变化的内在需求。借用《C＋＋沉思录》作者的一句话，“避免重复”。在以后的应用中，你可能需要单独的写出一个class——打个比方，为了实现栈，你没有必要先写一个线性表，然后再继承得到栈；但假如你已经有了一个线性表了，你还需要另起炉灶再重写一个栈吗？对于一本书来说，本来就是假定读者在看后面的章节的时候，已经对前面的章节有所了解；即使象《C＋＋沉思录》这样的从以前发表在杂志上的文章整理出的书，也能看到循序渐进的影子。如果在后面的章节又把前面的东西重复一遍，我只能认为他是在骗稿费。
我把以前的代码总结一下，列表如下（因为我画不好图）：
单链表（List<Type>）
多项式节点
表达式节点
修改部分操作
添加向前指针域
限制操作
多项式
表达式
循环链表
双向链表
栈和队列
我们从单链表出发，通过对应的变化，得到了绿色的一行。突然之间我觉得自己很可悲，看了100多页书，最后得到竟然只是这么一个表。不管怎么说，这也是我看了这么多页书的结晶，让我们看看能从这表里得到什么。
首先，单链表是一个容器，他是为了存取数据而存在的。如果里面存的是多项式的节点，那么他就是一个多项式；如果里面存的是表达式节点，那么他就是一个表达式。这让我想起了以前曾经困扰我的语义问题：多项式究竟是一个存了多项式节点的单链表呢，还是包含了一个存了多项式节点的单链表？现在我的想法是，这并不重要，怎么理解都行。
其次，循环链表、双向链表、栈和队列也是容器，只是具体的操作实现或者对外的行为和单链表有所差别。但是内在的存取机制是相同的，或者还有更多的地方相同，我们应当最大限度的利用这些相同之处。
上面的提法好像很无聊——他们当然是容器，还用你小子废话吗——请注意我下面的问题：数组是容器吗？你做过仅针对数组里的元素操作的练习吗？你做过数组应用的练习吗？现在请你把数......
数据结构学习（c++）——二叉树(2007-04-02 06:23:00)
摘要：注：本文只是对学习清华殷人昆《数据结构（用面向对象方法与c++描述）》的人有些微帮助，其他人就没有必要浪费时间看了。因为老实说这本书里的代码实现的确不怎么样。
我的目的，就是努力实现和书里的代码相同的接口，尽最大可能和原代码一摸一样。因为这样的话，一则自己以后看起来比较方便，只要对着课本翻翻就行了；二则这样可能对别的学这本书的人有一定的好处。由于自己的习惯，我在原书的类名前加了_。
/* Name: _BinaryTree.h Copyright: Author: elmar Date: 19-07-03 23:43 Description: */
#ifndef _BinaryTree_H#define _BinaryTree_H
#include <iostream>#include <deque> //用于Insert中的层次遍历 using namespace std;
template <class Type> class _BinaryTree;template <class Type> class _BinTreeNode{ friend class _BinaryTree<Type>; public: _BinTreeNode():data(Type()), leftChild(NULL), rightChild(NULL){} _BinTreeNode(Type item, _BinTreeNode<Type>* left = NULL, &......
数据结构学习（C++）——递归【3】（2）(2007-04-02 06:22:00)
摘要：递归法和回溯法
有人说，回溯实际上是递归的展开，但实际上。两者的指导思想并不一致。
打个比方吧，递归法好比是一个军队要通过一个迷宫，到了第一个分岔口，有3条路，将军命令3个小队分别去探哪条路能到出口，3个小队沿着3条路分别前进，各自到达了路上的下一个分岔口，于是小队长再分派人手各自去探路——只要人手足够（对照而言，就是计算机的堆栈足够），最后必将有人找到出口，从这人开始只要层层上报直属领导，最后，将军将得到一条通路。所不同的是，计算机的递归法是把这个并行过程串行化了。
而回溯法则是一个人走迷宫的思维模拟——他只能寄希望于自己的记忆力，如果他没有办法在分岔口留下标记（电视里一演到什么迷宫寻宝，总有恶人去改好人的标记）。
想到这里突然有点明白为什么都喜欢递归了，他能够满足人心最底层的虚荣——难道你不觉得使用递归就象那个分派士兵的将军吗？想想汉诺塔的解法，也有这个倾向，“你们把上面的N－1个拿走，我就能把下面的挪过去，然后你们在把那N－1个搬过来”。笑谈，切勿当真。
这两种方法的例程，我不给出了，网上很多。我只想对书上的递归解法发表点看法，因为书上的解法有偷梁换柱的嫌疑——迷宫的储存不是用的二维数组，居然直接用岔路口之间的连接表示的——简直是人为的降低了问题的难度。实际上，如果把迷宫抽象成（岔路口）点的连接，迷宫就变成了一个“图”，求解入口到出口的路线，完全可以用图的遍历算法来解决，只要从入口DFS到出口就可以了；然而，从二维数组表示的迷宫转化为图是个很复杂的过程。并且这种转化，实际上就是没走迷宫之前就知道了迷宫的结构，显然是不合理的。对此，我只能说这是为了递归而递归，然后还自己给自己开绿灯。
但迷宫并不是只能用上面的方法来走，前提是，迷宫只要走出去就可以了，不需要找出一条可能上的最短路线——确实，迷宫只是前进中的障碍，一旦走通了，没人走第二遍。下面的方法是一位游戏玩家提出来的，既不需要递归，也不需要栈来回溯——玩游戏还是有收获的。
另一种解法
请注意我在迷宫中用粗线描出的路线，实际上，在迷宫中，只要从入口始终沿着一边的墙走，就一定能走到出口，那位玩家称之为“靠一边走”——如果你不把迷宫的通路看成一条线，而是一个有面积的图形，很快你就知道为什么。编程实现起来也很简单。
下面的程序在TC2中编译，不能在VC6中编译——为了动态的表现人的移动情况，使用了go......
数据结构学习（C++）——递归【3】（1）(2007-04-02 06:22:00)
摘要：迷宫
关于迷宫，有一个引人入胜的希腊神话，这也是为什么现今每当人们提到这个问题，总是兴致勃勃（对于年青人，估计是RPG玩多了），正如虽然九宫图连小学生都能做出来，我们总是自豪的说那叫“洛书”。这个神话我不复述了，有兴趣的可以在搜索引擎上输入“希腊神话 迷宫”，就能找到很多的介绍。
迷宫的神话讲述了一位英雄如何靠着“线团”杀死了牛头怪（玩过《英雄无敌》的朋友一定知道要想造牛头怪，就必须建迷宫，也是从这里来的），我看到的一本编程书上援引这段神话讲述迷宫算法的时候，不知是有意杜撰，还是考证不严，把这个过程叙述成：英雄靠着线团的帮助——在走过的路上铺线，每到分岔口向没铺线的方向前进，如果遇到死胡同，沿铺的线返回，并铺第二条线——走进了迷宫深处，杀死了牛头怪。然而，神话传说讲的是，英雄被当成贡品和其他的孩子送到了迷宫的深处，英雄杀死了牛头怪，靠着线团标识的路线退出了迷宫。实际上，这个线团只是个“栈”，远没有现代人赋予给它的“神奇作用”。我想作者也是RPG玩多了，总想着怎样“勇者斗恶龙”，然而，实际上却是“胜利大逃亡”。
迷宫问题实际上是一个心理测试，它反映了测试者控制心理稳定的能力——在一次次失败后，是否失去冷静最终陷在迷宫之中，也正体现了一句诗，“不识庐山真面目，只缘身在此山中”。换而言之，我们研究迷宫的计算机解法，并没有什么意义，迷宫就是为人设计的，而不是为机器设计的，它之所以称为“迷”宫，前提是人的记忆准确性不够高；假设人有机器那样的准确的记忆，只要他不傻，都能走出迷宫。现在可能有人用智能机器人的研究来反驳我，实际上，智能机器人是在更高的层面上模拟人的思考过程，只要它完全再现了人的寻路过程，它就能走出迷宫。但是，研究迷宫生成的计算机方法，却是有意义的，因为人们总是有虐待自己的倾向（不少人在RPG里的迷宫转了三天三夜也不知道疲倦），呵呵，笑谈。
不管怎么说，还是亲自研究一下计算机怎么走迷宫吧。
迷宫的存储
按照惯例，用一个二维数组来表示迷宫，0表示墙，1表示通路，以后我们的程序都走下面这个迷宫。
&nb......
数据结构学习（C++）——递归【2】（4）(2007-04-02 06:21:00)
摘要：include <iostream>
#include <vector>
using namespace std;
class Needle
{
public:
Needle() { a.push_back(100); }//每一个柱子都有一个底座
void push(int n) { a.push_back(n); }
int top() { return a.back(); }
int pop() { int n = a.back(); a.pop_back(); return n; }
int movenum(int n) { int i = 1;while (a[i] > n) i++; return a.size() - i; }
int size() { return a.size(); }
int operator [] (int n) { return a[n]; }
private:
vector<int> a;
};
void Hanoi(int n)
{
Needle needle[3], ns;//3个柱子，ns是转换柱子时的保存栈，借用了Needle的栈结构
int source = 0, target, target_m = 2, disk, m = n;
......