博文
不为人熟知的FreeBSD(2006-08-02 11:19:00)
摘要：
【导读】FreeBSD 操作系统在免费操作系统中是一个不为人熟知的巨人。从 386BSD 项目开始，FreeBSD 操作系统成为主要针对于 Intel 芯片及其克隆产品的、运行速度极快的、类似 UNIX® 的操作系统。FreeBSD 在许多方面替代了基于 GNU/Linux 的操作系统。它运行于过时的 Intel 机器和 64 位 AMD 芯片之上，在一些全球最大的文件服务器上，它每天可以处理数 TB 的文件。
Berkeley Software Distribution (BSD) 系列操作系统的历史向前可以追溯到 20 世纪 70 年代后期由加利福尼亚大学 Berkeley 创建和维护的 BSD UNIX 操作系统。今天，BSD 系列包括 5 个主要分支，就是那些热衷于 Linux 的激进主义者也会惊叹于不断涌现的各种 BSD 分支。自 2001 年起，当最后一个主要分支 DragonFly BSD 发布时，FreeBSD、OpenBSD、NetBSD 和 Mac OS X 代表了 UNIX 世界一次新的创新浪潮。所有这些操作系统分支都符合 POSIX，都为它们的用户呈现了一个类似的命令行界面，并且都使用了使编程模式与应用程序用法特征尽可能类似的内核和系统库。
从条文上讲，BSD 不能算做 UNIX 系统，但是，BSD 各个分支代表开源 UNIX 这一观点已被广泛接受。令人感到惊奇的是，在 20 世纪 80 年代未和 90 年代初，运行于 PC 或 Mac 上的免费操作系统还没有一个能够冠以该名称。UNIX 存在于大型机和可伸缩的处理器架构（Scalable Processor Architecture、SPARC）之上。各大私有 UNIX 公司已经瓜分了商业 UNIX 市场。
最初的 BSD 操作系统是 386BSD
1993 年发生的两件大事永远地改变了 UNIX：即成立了 NetBSD 小组和再次流行 386BSD 修补工具。在十年前，BSD UNIX 开发人员再次从加州大学伯克莱分校的各层工作人员中和哲学博士学生中进行招募，资金大部分来源于国防高级研究计划署（Defense Advanced Research Projects Agency、DARPA），但是募集资金的形式从此结束。386BSD 项目是在 1985 年作为让......
STL中list的使用(2006-07-31 10:41:00)
摘要：STL中list的使用：
STL中的list就是一双向链表，可高效地进行插入删除元素。现总结一下它的操作。
文中所用到两个list对象c1,c2分别有元素c1(10,20,30) c2(40,50,60)。还有一个list<int>::iterator citer用来指向c1或c2元素。
list对象的声明构造()：
A. list<int>c0; //空链表
B. list<int>c1(3); //建一个含三个默认值是0的元素的链表
C. list<int>c2(5,2); //建一个含五个元素的链表，值都是２
D. list<int>c4(c2); //建一个c2的copy链表
E. list<int>c5(c1.begin(),c1.end());
//c5含c1一个区域的元素[_First, _Last)。
1. assign()分配值，有两个重载：
c1.assign(++c2.begin(), c2.end()) //c1现在为(50,60)。
c......
Floyd算法应用(2006-07-27 20:48:00)
摘要：Floyd算法的变化应用：
大家应该都知道Floyd在图中的任意两点最短路径的算法中的应用吧。现在我们来看一个Floyd在其它方面的应用……
题目：
Sorting It All Out（zju1060）
问题描述：
若变量 A, B, C, D已排好序,意味着: A < B, B < C,C < D. 本问题中,将给出一组变量间的小于关系，请你判断它们是否能确定一个排好的序列。
输入：
4 6 //变量有４个(大写字母Ａ—xx)，下面紧跟６种关系
A<B
A<C
B<C
C<D
B<D
A<B
3 2 //又一ＴＥＳＴ
A<B
B<A
26 1
A<Z
0 0 //00结束
输出：
Sorted sequence determined after 4 relations: ABCD.
Inconsistency found after 2 relations.
Sorted sequence cannot be determined.
说明：
第一组：前4个关系式就能确定序列
第二组：前两个关系式中出现矛盾
第三组：不能确定
问题分析：
★ n个元素要是能确定一个全序，任意两个元素间必能比较大小，这样关系总数应该有n-1 + n-2 + n-3 + …+1 = n*(n-1)/2 个。
★ 当关系式能产生n*(n-1)/2 个关系时，序列可确定。(直接排序)
★ 由于关系只有小于，我们可以用邻接矩阵来表示元素之间的小于关系。
★ &......
深度优先搜索(DFS)基础(2006-07-27 20:43:00)
摘要：深度优先搜索(DFS)基础
深度优先搜索(Deep First Search)主要用在回溯，搜索剪枝等类的问题上。
DFS的基本算法思想是：从图中一顶点vi出发，访问它，并进行标记，然后依次搜索vi的每个邻接点vj；若vj没被访问过，则对vj进行访问标记，然后，依次搜索vj的每个邻接点；若vj的邻接点没被访问过，则访问vj 的邻接点，并进行标记……直到图中和vi有通路的所有顶点都被访问。
二叉树的先序遍历是DFS的一种小范围情况:
实线表调用，虚线表返回(回溯)。得到ABDEGCF.
void Preorder(BiTree root)
{
if (root==NULL) return;
else
{
访问根结点；
Preorder(root->Lchild);
Preorder(root->Rchild);
......
c++中的string用法(三)(2006-07-27 20:32:00)
摘要：basic_string::max_size
返回string 能放的最大元素个数。（不同于capacity）
size_type max_size( ) const;
basic_string <char>::size_type cap, max;
cap = s.capacity ( );
max = s.max_size ( ); // max=4294967294.
basic_string::rfind
寻找给定的string。返回找到的第一个string 下标值；如果没找到则返回npos。
与find 不同的是：rfind 默认从npos 开始找。其他相同。
basic_string::replace
将原string 中的元素或子串替换。返回替换后的string。
（1）用string 或C-string 代替操作string 中从_Pos1 开始的_Num1 个字符
basic_string& replace( size_type _Pos1,size_type _Num1, const value_type* _Ptr);
basic_string& replace(size_type _Pos1,size_type _Num1,const basic_string_Str);
string a,b;
string s ( "AAAAAAAA" );
string s1p ( "BBB" );
const char* cs1p = "CCC"；
a = s.replace ( 1 , 3 , s1p ); // s=”ABBBAAAA”
b = s.replace ( 5 , 3 , cs1p ); // s=”ABBBACCC”
（2）用string 中从_Pos2 开始的_Num2 个字符,代替操作string 中从_Pos1 开始的_Num1 个字符
用C-string 中的_Num2 个字符，代替操作string 中从_Pos1 开始的_Num1 个字符
basic_string& replace( size_type _Pos1, size_type _Num1, const basic_string& _Str,
size_type _Pos2, ......
c++中的string用法(二)(2006-07-27 20:31:00)
摘要：basic_string::compare
如果所比较的两个string 相等，则返回0； 操作string 大于参数string,返回
正数；操作string 小于参数string,返回负数。
(1)比较操作string 与_Str 或C-string_Ptr
int compare( const basic_string& _Str ) const;
int compare( const value_type* _Ptr ) const;
int com = s.compare ( sp );
(2)比较操作string 中_Pos1(下标)开始的_Num1 个字符 与 string_Str
比较操作string 中_Pos1(下标)开始的_Num1 个字符 与 C-string _Ptr
比较操作string 中Pos1(下标)开始的Num1 个字符 与Str 中Off(下标)开始Count 个字
符
int compare( size_type _Pos1, size_type _Num1, const basic_string& _Str );
int compare( size_type _Pos1, size_type _Num1, const value_type* _Ptr ) const;
int compare( size_type _Pos1, size_type _Num1, const basic_string& _Str,
size_type _Off, size_type _Count );
int com1 = s.compare ( 2 , 3 , sp );
int com2 = s.compare ( 2 , 3 , c );
int com3 = s.compare ( 1 , 3 , cs , 3 ,1 );
basic_string::erase
删除string 中的一个或几个元素。前两个成员函数，返回要被删除的子串的下
一个元素的iterator; 第三个函数，返回删除后的string 的引用。
(1)删除string 中从_First 到_Last 的字符
iterator erase( iterator _First, iterator _Las......
c++中的string用法(一)(2006-07-27 20:31:00)
摘要：
basic_string::append
向string 的后面加字符或字符串。(比+=, push_back 更灵活)
(1)向string 的后面加C-string
basic_string& append( const value_type* _Ptr );
string s ( "Hello " ); // s=”Hello ”
const char *c = "Out There ";
s.append ( c ); // s=”Hello Out There”
(2)向string 的后面加C-string 的一部分
basic_string& append( const value_type* _Ptr, size_type _Count );
string s ( "Hello " ); // s=”Hello ”
const char *c = "Out There ";
s.append ( c , 3 ); // s=”Hello Out”
(3)向string 的后面加string(有两种方法)
basic_string& append( const basic_string& _Str );
string s1 ( "Hello " ), s2 ( "Wide " ), s3( "World " );
s1.append ( s2 ); // s1=”Hello Wide”
s1 += s3; // s1=”Hello Wide World”
(4)向string 的后面加string 的一部分 ---A
basic_string& append( const basic_string& _Str, size_type _Off,
size_type _Count );
string s1 ( "Hello " ), s2 ( "Wide World " );
s1.append ( s2 , 5 , 5 ); // s1=”Hello World”
(5)向string 的后面加string 的一部分 ---B
template<class InputIterator> basic_string& append(
Inp......
等价类与并查集的原理和应用(2006-07-27 20:15:00)
摘要：等价类与并查集的原理和应用
并查集主要解决判断两个元素是否同属一个集合，和把两个不属同一集合的两个元素进行合并的问题。(想想最小生成树中的kruskal算法:关键是判别两个节点是否属同一连通分量，这里并查集可以以很好的时间复杂度解决它，几乎是线性时间！！)
首先要知道关于等价类（就相当于前面说的同属一个集合）的基本性质。
等价类三大性质：（用ＸºＹ表Ｘ与Ｙ等价）
自反性：如ＸºＸ则ＸºＸ；
对称性：如ＸºＹ则ＹºＸ；
传递性：如ＸºＹ且ＹºＺ则ＸºＺ；
等价类应用：
设初始有一集合s={0,1,2,3,4,5,6,7,8,9,10,11}
依次读若干事先定义的等价对
0º4,3º1,6º10,8º9,7º4,6º8,3º5,2º11,11º0.
我们想把每次读入一个等价对后，把等价集合合并起来。
则每读入一个等价对后的集合状态是：（用｛｝表示一个等价集合）
初始 {0},{1},{2},{3},{4},{5},{6},{7},{8},{9},{10},{11}
0 º 4 {0,4},{1},{2},{3},{5},{6},{7},{8},{9},{10},{11......
广度优先搜索(BFS)的原理和应用(2006-07-27 17:55:00)
摘要：广度优先搜索(BFS)的原理和应用
二叉树中的层序遍历就属于一种BFS(Board First Search)
层序遍历会得到ABCDEFG的层序优先序列(BFS序列)。在层序遍历过程中，可以注意到先访问的节点的孩子节点必然先被访问(如访问了Ａ后访问Ｂ和Ｃ，那么Ｂ的孩子结点一定在Ｃ的孩子结点前被访问――仅针对下一层的孩子而言)。据这个特性，可以用队列来实现这个遍历。
void Layer(bitree *p)
{
queue<node*> Q; //定义一个队列
node *N;
Q.push(*p); //起始点入队
while(!Q.empty())
{
N=Q.front();
Q.pop();
cout<<N->data<<endl;
if(N->lchild!=NULL) //将扩展子结点(仅一层)全都入队
Q.push(N->lchild);
if(N->rchild!=NULL)
Q.push(N->rchild);
}
}
BFS比它更进一步，可以针对图的结构进行BFS遍历
的BFS(从Ｖ１开始)路径是
广搜的一般结构如下：
定义一个队列;
起始点入队；
while(队列不空){
队头结点出队;
若它是所求的目标状态,跳出循环;
否则，将它扩展出的子结点,全都入队;
}
若循环中找到目标,输出结果;
否则输出无解;
它的主要特点是：
n &nb......
一个简单枚举例子(2006-07-27 17:34:00)
摘要：一个简单枚举例子：
题目：
Zero Sum (USACO 36)
问题描述：
给定一个整数N（3=<N<=9).在序列1…N中插入‘＋’，‘－’，‘ ’。按字典序输出所有使得表达式为0的情况。
Sample Input：
7
Sample Output
1+2-3+4-5-6+7
1+2-3-4+5+6-7
1-23+4+5+6+7
1-23-45+67
1-2+3+4-5+6-7
1-2-3-4-5+6+7
问题分析：
v 在1..N中插入‘＋’，‘－’，‘ ’一共有多少中插法？
考虑最坏情况N＝9 时有3^8＝6561 情况。这个解空间比较小，这就意味着我们可以列举所有情况看它是否满足“使得表达式为0”(枚举)。
构造一个变量：
string digital = "11223344556677889";
对变量的操作：
输入n后把digital中2*n – 1 后剔除并在奇数位置按字典序枚举各种插入情况。对每种情况如果表达式值为0。则输出。
源程序：
#include<iostream>
#include<string>
#include<sstream>
using namespace std;
string digital="11223344556677889"; //后面直接对它修改后做为表达式
int n; //规模
int check() //检查字符串表示的表达式是否为0
{
int i;
string tmp;
for(i=0;i<digital.size();i++)
if(digital[i]!=' ')
tmp+=digital[i];
istringst......