博文
lz77压缩算法(2008-07-08 10:36:00)
摘要：第五章 聪明的以色列人(上)：LZ77 第四章 第六章 全新的思路 我们在第三和第四章中讨论的压缩模型都是基于对信息中单个字符出现频率的统计 而设计的，直到 70 年代末期，这种思路在数据压缩领域一直占据着统治地位。在 我们今天看来，这种情形在某种程度上显得有些可笑，但事情就是这样，一旦某项 技术在某一领域形成了惯例，人们就很难创造出在思路上与其大相径庭的哪怕是更 简单更实用的技术来。 我们敬佩那两个在数据压缩领域做出了杰出贡献的以色列人，因为正是他们打破了 Huffman 编码一统天下的格局，带给了我们既高效又简便的“字典模型”。至今 ，几乎我们日常使用的所有通用压缩工具，象 ARJ，PKZip，WinZip，LHArc，RAR ，GZip，ACE，ZOO，TurboZip，Compress，JAR……甚至许多硬件如网络设备中内 置的压缩算法，无一例外，都可以最终归结为这两个以色列人的杰出贡献。 说起来，字典模型的思路相当简单，我们日常生活中就经常在使用这种压缩思想。 我们常常跟人说“奥运会”、“IBM”、“TCP”之类的词汇，说者和听者都明白它 们指的是“奥林匹克运动会”、“国际商业机器公司”和“传输控制协议”，这实 际就是信息的压缩。我们之所以可以顺利使用这种压缩方式而不产生语义上的误解 ，是因为在说者和听者的心中都有一个事先定义好的缩略语字典，我们在对信息进 行压缩（说）和解压缩（听）的过程中都对字典进行了查询操作。字典压缩模型正 是基于这一思路设计实现的。 最简单的情况是，我们拥有一本预先定义好的字典。例如，我们要对一篇中文文章 进行压缩，我们手中已经有一本《现代汉语词典》。那么，我们扫描要压缩的文章 ，并对其中的句子进行分词操作，对每一个独立的词语，我们在《现代汉语词典》 查找它的出现位置，如果找到，我们就输出页码和该词在该页中的序号，如果没有 找到，我们就输出一个新词。这就是静态字典模型......
GDB 调试(2008-07-03 15:10:00)
摘要：如何用GDB调试
2007年06月01日 星期五 下午 06:38
GDB概述GDB 是GNU开源组织发布的一个强大的UNIX下的程序调试工具。或许，各位比较喜欢那种图形界面方式的，像VC、BCB等IDE的调试，但如果你是在 UNIX平台下做软件，你会发现GDB这个调试工具有比VC、BCB的图形化调试器更强大的功能。所谓“寸有所长，尺有所短”就是这个道理。
一般来说，GDB主要帮忙你完成下面四个方面的功能：
1、启动你的程序，可以按照你的自定义的要求随心所欲的运行程序。2、可让被调试的程序在你所指定的调置的断点处停住。（断点可以是条件表达式）3、当程序被停住时，可以检查此时你的程序中所发生的事。4、动态的改变你程序的执行环境。
从上面看来，GDB和一般的调试工具没有什么两样，基本上也是完成这些功能，不过在细节上，你会发现GDB这个调试工具的强大，大家可能比较习惯了图形化的调试工具，但有时候，命令行的调试工具却有着图形化工具所不能完成的功能。梦颐且灰豢蠢础?/p>
一个调试示例源程序：tst.c1 #include <stdio.h>23 int func(int n)4 {5 int sum=0,i;6 for(i=0; i<n; i++)7 {8 sum+=i;9 }10 return sum;11 }121314 main()15 {16 int i;17 long result = 0;18 for(i=1; i<=100; i++)19 {20 result += i;21 }2223 printf("result[1-100] = %d \n", result );24 printf("result[1-250] = %d \n", func(250) );25 }
编译生成执行文件：（Linux下）hchen/test> cc -g tst.c -o tst
使用GDB调试：
hchen/test> gdb tst <---------- 启动GDBGNU gdb 5.1.1Copyright 2002 Free Software Foundation, Inc.GDB is free software, covered by the GNU General Publ......
范式哈夫曼编码(2008-07-03 10:43:00)
摘要：
范式哈夫曼编码
1 概念介绍
哈夫曼编码是一种最优的前缀编码技术，然而其存在的不足却制约了它的直接应用。首先，其解码时间为O(lavg), 其中lavg为码字的平均长度；其次，更为最重要的是，解码器需要知道哈夫曼编码树的结构，因而编码器必须为解码器保存或传输哈夫曼编码树。对于小量数据的压缩而言，这是很大的开销。因而，应用哈夫曼编码的关键是如何降低哈夫曼编码树的存储空间。Faller[1973]提出的自适应哈夫曼编码技术使哈夫曼编码树的存储空间降为零，即在使用某种约定的情况下，解码器能动态地重构出和编码器同步的哈夫曼编码树，而不需要任何附加数据。这样做的代价便是时间开销的增大。另一种技术是编码器和解码器使用事先约定的编码树，这种方法只能针对特定数据使用，不具备通用性。另外一种，也是最为常用的方法，便是范式哈夫曼编码。现在流行的很多压缩方法都使用了范式哈夫曼编码技术，如GZIB、ZLIB、PNG、JPEG、MPEG等。范式哈夫曼编码最早由Schwartz[1964]提出，它是哈夫曼编码的一个子集。其中心思想是：使用某些强制的约定，仅通过很少的数据便能重构出哈夫曼编码树的结构。其中一种很重要的约定是数字序列属性(numerical sequence property)，它要求相同长度的码字是连续整数的二进制描述。例如，假设码字长度为4的最小值为0010，那么其它长度为4的码字必为0011, 0100, 0101, ...；另一个约定：为了尽可能的利用编码空间，长度为i第一个码字f(i)能从长度为i-1的最后一个码字得出, 即: f(i) = 2(f(i-1)+1)。假定长度为4的最后一个码字为1001，那么长度为5的第一个码字便为10100。最后一个约定：码字长度最小的第一个编码从0开始。通过上述约定，解码器能根据每个码字的长度恢复出整棵哈夫曼编码树的结构。
2 码字构造
假设有如下的码长序列： 符号：a b c d e f g h i j k ... u 码长：3 4 4 4 4 4 4 4 4 5 5 ... 5使用count[i]表示长度为i的码字的数目，first[i]表示长度为i的第一个码字的整数值。根据约定3，即first[3] = 0可得到符号......
用 GDB 调试程序(2008-07-02 14:08:00)
摘要：用GDB调试程序
说明
从CSDN的网站上找到的GDB使用说明。 原文标题：用GDB调试程序
作者：haoel （QQ是：753640，MSN是： haoel@hotmail.com）
关键字：gdb 调试 c c++ gun
这篇文章非常好，所以转载了下来，作为收藏。
topGDB概述GDB 是GNU开源组织发布的一个强大的UNIX下的程序调试工具。或许
，各位比较喜欢那种图形界面方式的，像VC、BCB等IDE的调试，但如
果你是在 UNIX平台下做软件，你会发现GDB这个调试工具有比VC、
BCB的图形化调试器更强大的功能。所谓“寸有所长，尺有所短”就
是这个道理。
一般来说，GDB主要帮忙你完成下面四个方面的功能：
1、启动你的程序，可以按照你的自定义的要求随心所欲的运行程序。
2、可让被调试的程序在你所指定的调置的断点处停住。（断点可以是条件表达式）
3、当程序被停住时，可以检查此时你的程序中所发生的事。
4、动态的改变你程序的执行环境。
从上面看来，GDB和一般的调试工具没有什么两样，基本上也是完成
这些功能，不过在细节上，你会发现GDB这个调试工具的强大，大家
可能比较习惯了图形化的调试工具，但有时候，命令行的调试工具却
有着图形化工具所不能完成的功能。让我们一一看来。
top一个调试示例源程序：tst.c
1 #include <stdio.h>
2
3 int func(int n)
4 {
5 int sum=0,i;
6 for(i=0; i<n; i++)
7 {
8 sum+=i;
9 }
10 return sum;
11 }
12
13
14 main()
15 {
16 int i;
17 long result = 0;
18 for(i=1; i<=100; i++)
19 {
20 result += i;
21 }
22
23 printf("result[1-100] = %d \n", result );
24 printf("result[1-250] = %d \n", func(250) );
25 }
编译生成执行文件：（Linux下）
hchen/test> ......
VMware访问Windows宿主机的共享文件(2008-04-17 22:44:00)
摘要：VMware访问Windows宿主机的共享文件( 转载 )
虚拟机的使用，的确给Linux的学习者提供了很大的方便。不过在Linux学习过程中，当涉及到应用软件的使用时，虽然可以直接从网上下载程序包或源码，但用惯了迅雷，对Linux中的下载速度简直无法忍受，且原有的很多资源本应该可以直接使用，没有必要重新下载。因而在两个系统中共享信息成为亟待解决的问题。
在网上搜索了大量相关信息，介绍两个系统间信息共享的不少，但是提供虚拟机host-guest机不同系统之间资源共享解决方案的不多。在朋友的帮助下，经过多次尝试和摸索，终于有了一些搜获。现提供一套包括局域网配置在内的较为详细的解决方案，供初学者参考。
转载请注明本站版权：微品质工作室版权所有
FTP法
环境介绍： 虚拟机：VMware Workstation 5.5 Host机系统：Windows 2000 Server Guest机系统：Red Hat Enterprise Linux 4
其实作为两个系统而言，要进行资源的共享，方法很多，最初我尝试了使用mount命令挂载文件系统。从命令本身来看，想要挂载一个Windows下的文件系统或驱动盘似乎没有什么问题。
首先在Linux系统/mnt空目录下，建立挂载点：#mkdir /mnt/mystudy /mnt目录是专门用来当作挂载点的目录。mystudy是自定义的专用挂载点名称。
然后我们看一下mount命令的使用方法： ......
在VC中添加响应自定义的消息的代码步骤(2008-03-31 10:42:00)
摘要：1. 首先定义一个消息代码 #define WM_DEBUG WM_USER + 1999 2. 在窗口头文件中添加class CStreamServerDlg : public CDialog{// Generated message map functions//{{AFX_MSG(CStreamServerDlg)...//}}AFX_MSGafx_msg void OnDebug(WPARAM wParam, LPARAM lParam); ...} 3. 在窗口的cpp文件中添加BEGIN_MESSAGE_MAP(CStreamServerDlg, CDialog)...ON_MESSAGE(WM_DEBUG, OnDebug)END_MESSAGE_MAP()void CStreamServerDlg::OnDebug(WPARAM wParam, LPARAM lParam){} 4. 其他地方就可以发送消息pWnd->PostMessage(WM_DEBUG, (WPARAM)p, 0) )......
可重入函数与不可重入函数(2008-03-03 10:13:00)
摘要：可重入函数与不可重入函数
2008年01月05日 10:57
主要用于多任务环境中，一个可重入的函数简单来说就是可以被中断的函数，也就是说，可以在这个函数执行的任何时刻中断它，转入OS调度下去执行另外一段代码，而返回控制时不会出现什么错误；而不可重入的函数由于使用了一些系统资源，比如全局变量区，中断向量表等，所以它如果被中断的话，可能会出现问题，这类函数是不能运行在多任务环境下的。
也可以这样理解，重入即表示重复进入，首先它意味着这个函数可以被中断，其次意味着它除了使用自己栈上的变量以外不依赖于任何环境（包括static），这样的函数就是purecode（纯代码）可重入，可以允许有该函数的多个副本在运行，由于它们使用的是分离的栈，所以不会互相干扰。如果确实需要访问全局变量（包括static），一定要注意实施互斥手段。可重入函数在并行运行环境中非常重要，但是一般要为访问全局变量付出一些性能代价。
编写可重入函数时，若使用全局变量，则应通过关中断、信号量（即P、V操作）等手段对其加以保护。
说明：若对所使用的全局变量不加以保护，则此函数就不具有可重入性，即当多个进程调用此函数时，很有可能使有关全局变量变为不可知状态。
示例：假设Exam是int型全局变量，函数Squre_Exam返回Exam平方值。那么如下函数不具有可重入性。
unsigned int example( int para )
{
unsigned int temp; Exam = para; // （**） temp = Square_Exam( ); return temp; } 此函数若被多个进程调用的话，其结果可能是未知的，因为当（**）语句刚执行完后，另外一个使用本函数的进程可能正好被激活，那么当新激活的进程执行到此函数时，将使Exam赋与另一个不同的para值，所以当控制重新回到“temp = Square_Exam( )”......
红黑树(2008-03-02 21:24:00)
摘要：红黑树: 理论与实现(理论篇)
红黑树: 理论与实现(理论篇)[修订版]
原创：司徒彦南
2002年8月19日
红黑树是一种很有意思的平衡检索树。它的统计性能要好于平衡二叉树(有些书籍根据作者姓名，Adelson-Velskii和Landis，将其称为AVL-树)，因此，红黑树在很多地方都有应用。在C++ STL中，很多部分(目前包括set, multiset, map, multimap)应用了红黑树的变体(SGI STL中的红黑树有一些变化，这些修改提供了更好的性能，以及对set操作的支持)。
红黑树的定义如下：
满足下列条件的二叉搜索树是红黑树
每个结点要么是“红色”，要么是“黑色”(后面将说明)
所有的叶结点都是空结点，并且是“黑色”的
如果一个结点是“红色”的，那么它的两个子结点都是“黑色”的。
结点到其子孙结点的每条简单路径都包含相同数目的“黑色”结点
根结点永远是“黑色”的
之所以称为红黑树的原因就在于它的每个结点都被“着色”为红色或黑色。这些结点颜色被用来检测树的平衡性。但需要注意的是，红黑树并不是平衡二叉树，恰恰相反，红黑树放松了平衡二叉树的某些要求，由于一定限度的“不平衡”，红黑树的性能得到了提升。
从根结点到叶结点的黑色结点数被称为树的“黑色高度”(black-height)。前面关于红黑树的性质保证了从根结点到叶结点的路径长度不会超过任何其他路径的两倍。
我们来解释一下这个结论。考虑一棵黑色高度为3的红黑树：从根结点到叶结点的最短路径长度显然是2(黑-黑-黑)，最长路径为4(黑-红-黑-红-黑)。由于性质4，不可能在最长路经中加入更多的黑色结点，此外根据性质3，红色结点的子结点必须是黑色的，因此在同一简单路径中不允许有两个连续的红色结点。综上，我们能够建立的最长路经将是一个红黑交替的路径。
由此我们可以得出结论：对于给定的黑色高度为n的红黑树，从根到叶结点的简单路径的最短长度为n-1，最大长度为2(n-1)。
插入和删除操作中，结点可能被旋转以保持树的平衡。红黑树的平均和最差搜索时间都是O(log2 n)。Cormen [2001]给出了对于这一结论的证明。在实际应用中，红黑树的统计性能要好于平衡二叉树，但极端性能略差。
红黑树中结点......
树，二叉树，森林的转换(2008-03-02 21:23:00)
摘要：树 - 树和森林- 树、森林和二叉树的转换
http://www.educity.cn 作者：自考频道 来源：学赛网 2008年1月5日 发表评论 进入社区
树或森林与二叉树之间有一个自然的一一对应关系。任何一个森林或一棵树可惟一地对应到一棵二叉树;反之，任何一棵二叉树
也能惟一地对应到一个森林或一棵树。
1.树、森林到二叉树的转换
(1)将树转换为二叉树
树中每个结点最多只有一个最左边的孩子(长子)和一个右邻的兄弟。按照这种关系很自然地就能将树转换成相应的二叉树：
①在所有兄弟结点之间加一连线;
②对每个结点，除了保留与其长子的连线外，去掉该结点与其它孩子的连线。
【例1】下面(a)图所示的树可转换为(c)图所示的二叉树。具体转换过程可
注意：
由于树根没有兄弟，故树转化为二叉树后，二叉树的根结点的右子树必为空。
(2)将一个森林转换为二叉树
具体方法是：
① 将森林中的每棵树变为二叉树
② 因为转换所得的二叉树的根结点的右子树均为空，故可将各二叉树的根结点视为兄弟从左至右连在一起，就形成了一棵二叉
树。
【例2】下图中，左边包含三棵树的森林可转换为右边的二叉树。
具体转换过程可
2.二叉树到树、森林的转换
把二叉树转换到树和森林自然的方式是：若结点x是双亲y的左孩子，则把x的右孩子，右孩子的右孩子，…，都与y用连线连起来
，最后去掉所有双亲到右孩子的连线。
【例3】下图的森林就是由例2中二叉树转换成的。
具体转换过程可
......
C语言可变参数函数的实现(2008-03-02 21:19:00)
摘要：// 下文转自网络
C语言可变参数函数的实现
一、什么是可变参数
我们在C语言编程中有时会遇到一些参数个数可变的函数,例如printf()函数,其函数原型为:
int printf( const char* format, ...);
它除了有一个参数format固定以外,后面跟的参数的个数和类型是可变的（用三个点“…”做参数占位符）,实际调用时可以有以下的形式: printf("%d",i);
printf("%s",s);
printf("the number is %d ,string is:%s", i, s);
以上这些东西已为大家所熟悉。但是究竟如何写可变参数的C函数以及这些可变参数的函数编译器是如何实现，这个问题却一直困扰了我好久。本文就这个问题进行一些探讨,希望能对大家有些帮助.
二、写一个简单的可变参数的C函数
先看例子程序。该函数至少有一个整数参数,其后占位符…，表示后面参数的个数不定. 在这个例子里，所有的输入参数必须都是整数，函数的功能只是打印所有参数的值.
函数代码如下：
//示例代码1：可变参数函数的使用
＃i nclude "stdio.h"
＃i nclude "stdarg.h"
void simple_va_fun(int start, ...)
{
va_list arg_ptr;
int nArgValue =start;
int nArgCout=0; //可变参数的数目
va_start(arg_ptr,start); //以固定参数的地址为起点确定变参的内存起始地址。
do
{
++nArgCout;
printf("the %d th arg: % d\n",nArgCout,nArgValue......