博文
范式哈夫曼编码(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，即f......
用 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> ......
Picking Coins(2008-04-28 12:31:00)
摘要：
Picking Coins
Time Limit: 1000ms, Special Time Limit:2500ms, Memory Limit:32768KB
Problem description
A pack of coins have been divided into piles, each pile has some number Ni (1 <= Ni <= 25) of coins. All the piles have been placed in an area of R rows(1 <= R <= 100) and C columns (1 <= C <= 100).Given a starting location, you have to make your way out of the area and gather as many coins as you can. From the position (r,c) you can only move to (r-1,c+1), (r, c+1), or (r+1,c+1) and endup your way at any edge of the area. If there exist more than one path that can gather the maximum number of coins, make your path the shortest.
Input
There will be only one testcase in the input file, the first line contains Two space-separated integers, respectively R and C, then followed R lines, Each line contains C space-separated integers in the obvious order, the last few lines each contains two integer which indicate the starting loca......
练手题(2008-04-27 20:33:00)
摘要：
Don't ask woman about her age
Time Limit: 1000ms, Special Time Limit:2500ms, Memory Limit:32768KB
Problem description
Mrs Little likes digits most of all. Every year she tries to make the best number of the year. She tryes to become more and more intelligent and every year studies a new digit. And the number she makes is written in numeric system which base equals to her age. To make her life more beautiful she writes only numbers that are divisible by her age minus one. Mrs Little wants to hold her age in secret.
You are given a number consisting of digits 0, …, 9 and latin letters A, …, Z, where A equals 10, B equals 11 etc. Your task is to find the minimal number k satisfying the following condition: the given number, written in k-based system is divisible by k−1.
Input
Input consists of one string containing no more than 106 digits or uppercase latin letters.
Output
Output file should conta......
ati2avxx.exe 病毒清除(2008-04-19 09:00:00)
摘要：
今天帮一同学解决电脑故障, 之后知道是中了 ati2avxx.exe 病毒
以下是自己总结的一些资料, 为中了该毒的网友提供参考, 不保证
适合于所有版本的 ati2avxx.exe.
ati2avxx.exe 病毒是我所见比较厉害的病毒
症状: 中毒后隐藏文件完全不可见, 软件无法安装, 另外还有可能无法打开网页
杀毒软件无法运行, 系统缓慢, 无法进入安全模式等等.
以上症状不敢确定有没有,因为我自己没有中过该病毒,但是如果在进程管理器里
可以看到该病毒进程而且无法删除的话基本就是中了该病毒. 中过之后,即使重装系统
如果没有全盘格式化磁盘(估计谁都不想发这么大的代价)只要打开磁盘,在进程管理器
里就又会出现该病毒. 的确是一顽固的生命力强大的病毒, 目前的杀毒软件好像无法对付.
解决方法:
一, 全盘格式化后重装系统 (不推荐)
二, 这个方法是自己无意中发现的,不保证适合所有版本的 ati2avxx.exe
a, 打开任务管理器, 结束 explorer.exe 进程
b, 结束 ati2avxx.exe, 如果还没结束而 explorer.exe 进程又运行的话
转到 a, 总之先结束 explorer.exe 进程, 之后结束 ati2avxx.exe
c, 经过 a,b后 ati2avxx.exe 应该不会再运行了, 在任务管理器里点
文件->(新建任务)运行, 输入 cmd 打开命令提示符, 进入 system32 目录
输入 attrib -h -s -r -a ati2avxx.exe
d, 切换到任务管理器, 点 文件->(新建任务)运行, 点浏览进入 system32
这时我们可以看到 ati2avxx.exe 文件, ......
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是自定义的专用挂载点名称。
&nb......
在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_MSG
afx_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值，所以当控制重新回到“te......
红黑树(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中二叉树转换成的。
具体转换过程可
......