作者：黄建雄

下载源代码

简介
大量数据的管理是很多程序员的心病，很难找到一个速度快、效率高、支持超大规模数据的表，在1.0版本的基础上，启程花血本写下了这个强化了数据插入 与删除的修正版，启程动态数组是一个功能强大的列表形数据管理链表，利用它可以轻松实现超大数据量的随机插入、删除、修改等操作，它另外一个特点就是速度 极快，内存利用率高。
大量数据的管理必然需要占用大量的内存空间，如果这些数据占用的空间大小是随各种条件变化的，我们就不能使用数组来管理这些数据了（道理就不多说 了），这时我们需要一个动态数组。MFC提供了一个很好的动态数组类CArray，对于少量数据，使用CArray就足够好用了，但是对于大量数据 （10W级）它就力不从心了，因为它的本质就是一个数组，只不过对常用的插入、删除等操作进行了一个复杂的包装。为了解决这个问题，启程动态数组开创性地 将链表与数组巧妙的结合起来，既有数组的高速随机索引的优点，又有链表的数据量灵活多变的特点。

工作原理
启程动态数组的数据结构如图（这是1.0版本的示意图，2.0版在结点中增加了一个指示当前数据段中已经使用的空间变量）。为了解决大量数据的动态存 储问题，启程动态数组将数据分段存放在链表的节点中，每一段可以保存一定数量的数据，如果数据量增加，则在内存中分配一个新数据段，如果数据减少则释放空 闲的数据段，从而有效地解决了该问题。相对于1.0版，2.0版中引入了每个结点中已使用空间用和总空闲空间两个变量，经过这个处理，在进行数据的插入删 除时就不再需要对整个数组中的数据进行移动而只需要对目标数据段做一个简单的处理。

插入数据
如果目标数据段有空闲位置，那么只需要将该段进行曲整理并插入数据；如果目标段没有空闲空间，启程动态数据自动在内存中申请一段新的数据，并将该数据段链接到链表中。

删除数据
找到目标段后，从目标数据段中删除目标数据，如果目标段中只包含目标数据，启程动态数组自动删除目标段，并维护好链表的完整性。

添加数据
检查最后一个数据段，如果有空间就不再分配，没有就申请订报的数据段。

随机索引（数据定位）
相比较普通链表在随机索引方面的不足，启程动态数组在这方面可以说是趋于完美。由于启程动态数组在数据结构上的优势，它在数据定位的时候是段式跳跃的 搜索，因此它的速度得到了有力的保障。另一方面，为了加速索引速度它还经过了特别的优化，就是设置了一个当前位置的指针，这样不仅在普通的索引中可以成倍 的提高速度，特别是在遍历类的操作时甚至可以达到数组的速度。

数据压缩
如果细心的人一定会发现，按照上面的模式中可能存在很严重的空间滥废，事实上如果不作处理也是如此，因为在的插入数据时，我只需要插入一个数据，结果 却申请了一个完整的数据段，这在空间有限的计算机中将会造成很大的问题。还记得上面提到的新引入的用来记录空闲空间数量的变量吗？好了，有了它，我们就可 以把握有多少空间没有利用到，当这个值达到一个的范围时，启程动态数组自动对它占用的空间进行整理，经过整理后不再需要的空间自动回收。当然您可也可强制 整理，只需要调用一个简单的接口就好了。

参数设置
启动动态数组的性能很大程度上依赖于参数的设置，关键的参数有勇有2个，一是数据段的大小，一是空闲空间压缩阀，这两个参数应该也是比较好理解的。数 据段的大小主要应该根据目标数据的容量及计算机的内存来设置，压缩阀则要考虑你的机器的内存以及插入、删除操作的频率。对于10万级的数据量，数据段设成 100就差不多了，如果需要大量进行插入、删除压缩阀可适应加大，否则反之。

执行性能
代码的性能估计是大家最为关心的问题，同时也是它存在的根本。由于没有其实的代码做参考，这里只能与MFC的CArray进行比较。在10万级综合操 作测试中，启程动态数组耗时300MS左右，而CArray则需要3000MS，而且因为启程动态数组的耗时与数据量基本是线性关系，而CArray则基 本是指数关系，因此数据量越大启程动态数组的性能优势越明显。

测试程序
在开发这个程序时写了一个相应的测试工具，界面如下图：

“efficiency compare”部分是进行性能比较的，其它的都是进行程序正确性测试用的。做完测试后可以用刷新来显示内存中的数据。

版本历史

• 2.0：2004-6-3
• 增强插入删除
• 1.0：2003- 09-25

担保
本代码可以任意使用、修改、传播，但作者不对使用该链表造成的后果承担任何直接或间接责任。

写在最后
这是我以为写得最好的一段代码，拿出来共享只希望能够给大家带来一点点方便。如果大家觉得它有价值将是我最大的快乐！如果发现程序的bug请一定告诉我！希望大空用的开心。

联系方式

e-mail：　huangjianxiong@sina.com.cn

个人网站：http://setoutsoft.3322.net

作者：Hatem Mostafa
译者：happyparrot

下载源代码

介绍

本文描述在网上能够找到的最简单，最快速的哈夫曼编码。本方法不使用任何扩展动态库，比如STL或者组件。只使用简单的C函数，比如：memset，memmove，qsort，malloc，realloc和memcpy。

因此，大家都会发现，理解甚至修改这个编码都是很容易的。

背景

哈夫曼压缩是个无损的压缩算法，一般用来压缩文本和程序文件。哈夫曼压缩属于可变代码长度算法一族。意思是个体符号（例如，文本文件中的字符）用一个特定长度的位序列替代。因此，在文件中出现频率高的符号，使用短的位序列，而那些很少出现的符号，则用较长的位序列。

编码使用

我用简单的C函数写这个编码是为了让它在任何地方使用都会比较方便。你可以将他们放到类中，或者直接使用这个函数。并且我使用了简单的格式，仅仅输入输出缓冲区，而不象其它文章中那样，输入输出文件。

bool CompressHuffman(BYTE *pSrc, int nSrcLen, BYTE *&pDes, int &nDesLen);
bool DecompressHuffman(BYTE *pSrc, int nSrcLen, BYTE *&pDes, int &nDesLen);

要点说明

速度

为了让它(huffman.cpp)快速运行，我花了很长时间。同时，我没有使用任何动态库，比如STL或者MFC。它压缩1M数据少于100ms（P3处理器，主频1G）。

压缩

压缩代码非常简单，首先用ASCII值初始化511个哈夫曼节点：

CHuffmanNode nodes[511];

for(int nCount = 0; nCount < 256; nCount++)
    nodes[nCount].byAscii = nCount;

然后，计算在输入缓冲区数据中，每个ASCII码出现的频率：

for(nCount = 0; nCount < nSrcLen; nCount++)
    nodes[pSrc[nCount]].nFrequency++;

然后，根据频率进行排序：

qsort(nodes, 256, sizeof(CHuffmanNode), frequencyCompare);

现在，构造哈夫曼树，获取每个ASCII码对应的位序列：

int nNodeCount = GetHuffmanTree(nodes);

构造哈夫曼树非常简单，将所有的节点放到一个队列中，用一个节点替换两个频率最低的节点，新节点的频率就是这两个节点的频率之和。这样，新节点就是两个被替换节点的父节点了。如此循环，直到队列中只剩一个节点（树根）。

// parent node
pNode = &nodes[nParentNode++];

// pop first child
pNode->pLeft = PopNode(pNodes, nBackNode--, false);

// pop second child
pNode->pRight = PopNode(pNodes, nBackNode--, true);

// adjust parent of the two poped nodes
pNode->pLeft->pParent = pNode->pRight->pParent = pNode;

// adjust parent frequency
pNode->nFrequency = pNode->pLeft->nFrequency + pNode->pRight->nFrequency;

这里我用了一个好的诀窍来避免使用任何队列组件。我先前就直到ASCII码只有256个，但我分配了511个(CHuffmanNode nodes[511])，前255个记录ASCII码，而用后255个记录哈夫曼树中的父节点。并且在构造树的时候只使用一个指针数组 (ChuffmanNode *pNodes[256])来指向这些节点。同样使用两个变量来操作队列索引(int nParentNode = nNodeCount;nBackNode = nNodeCount –1)。

接着，压缩的最后一步是将每个ASCII编码写入输出缓冲区中：

int nDesIndex = 0;

// loop to write codes
for(nCount = 0; nCount < nSrcLen; nCount++)
{
        *(DWORD*)(pDesPtr+(nDesIndex>>3)) |= 
                  nodes[pSrc[nCount]].dwCode << (nDesIndex&7);
        nDesIndex += nodes[pSrc[nCount]].nCodeLength;
}

• (nDesIndex>>3): >>3 以8位为界限右移后到达右边字节的前面
• (nDesIndex&7): &7 得到最高位.

注意：在压缩缓冲区中，我们必须保存哈夫曼树的节点以及位序列，这样我们才能在解压缩时重新构造哈夫曼树（只需保存ASCII值和对应的位序列）。

解压缩

解压缩比构造哈夫曼树要简单的多，将输入缓冲区中的每个编码用对应的ASCII码逐个替换就可以了。只要记住，这里的输入缓冲区是一个包含每个ASCII 值的编码的位流。因此，为了用ASCII值替换编码，我们必须用位流搜索哈夫曼树，直到发现一个叶节点，然后将它的ASCII值添加到输出缓冲区中：

int nDesIndex = 0;
DWORD nCode;
while(nDesIndex < nDesLen)
{
        nCode = (*(DWORD*)(pSrc+(nSrcIndex>>3)))>>(nSrcIndex&7);
        pNode = pRoot;
        while(pNode->pLeft)
        {
            pNode = (nCode&1) ? pNode->pRight : pNode->pLeft;
            nCode >>= 1;
            nSrcIndex++;
        }
        pDes[nDesIndex++] = pNode->byAscii;
}

• (nDesIndex>>3): >>3 以8位为界限右移后到达右边字节的前面
• (nDesIndex&7): &7 得到最高位.

源文件： Huffman.cpp Huffman.h 请见本文提供的源代码压缩包。

作者： Chandrasekhar Vuppalapati
翻译：eastvc

下载源代码

本文的目的是设计一个完成URL编码的C++类。在我曾经的项目中，我需要从VC++ 6.0应用程序中POST数据，而这些数据需要进行URL编码。我在MSDN中查找能根据提供的字符串生成URL编码的相关类或API，但我没有找到，因 此我必须设计一个自己的URLEncode C++类。

URLEncoder.exe是一个使用URLEncode类的MFC对话框程序。

如何处理

一些特殊字符在Internet上传送是件棘手的事情, 经URL编码特殊处理，可以使所有字符安全地从Internet传送。

例如，回车的ASCII值是13，在发送FORM数据时候这就认为是一行数据的结束。

通常，所有应用程序采用HTTP或HTTPS协议在客户端和服务器端传送数据。服务器端从客户端接收数据有两种基本方法：

1、数据可以从HTTP头传送（COOKIES或作为FORM数据发送）
2、可以包含在URL中的查询部分

当数据包含在URL，它必须遵循URL语法进行编码。在WEB服务器端，数据自动解码。考虑一下下面的URL，哪个数据是作为查询参数。

例如：http://WebSite/ResourceName?Data=Data

WebSite是URL名称
ResourceName可以是ASP或Servlet名称
Data是需要发送的数据。如果MIME类型是Content-Type: application/x-www-form-urlencoded，则要求进行编码。

RFC 1738

RFC 1738指明了统一资源定位(URLs)中的字符应该是US-ASCII字符集的子集。这是受HTML的限制，另一方面，允许在文档中使用所有ISO- 8859-1(ISO-Latin)字符集。这将意味着在HTML FORM里POST的数据（或作为查询字串的一部分），所有HTML编码必须被编码。

ISO-8859-1 (ISO-Latin)字符集

在下表中，包含了完整的ISO-8859-1 (ISO-Latin)字符集，表格提供了每个字符范围（10进制），描述，实际值，十六进制值，HTML结果。某个范围中的字符是否安全。

Character range(decimal)	Type	Values	Safe/Unsafe
0-31	ASCII Control Characters	These characters are not printable	Unsafe
32-47	Reserved Characters	” ”!?#$%&”()*+,-./	Unsafe
48-57	ASCII Characters and Numbers	0-9	Safe
58-64	Reserved Characters	:;<=>?@	Unsafe
65-90	ASCII Characters	A-Z	Safe
91-96	Reserved Characters	[]^_`	Unsafe
97-122	ASCII Characters	a-z	Safe
123-126	Reserved Characters	{|}~	Unsafe
127	Control Characters	” ”	Unsafe
128-255	Non-ASCII Characters	” ”	Unsafe

所有不安全的ASCII字符都需要编码，例如，范围(32-47, 58-64, 91-96, 123-126)。
下表描述了这些字符为什么不安全。

Character	Unsafe Reason	Character Encode
"<"	Delimiters around URLs in free text	%3C
>	Delimiters around URLs in free text	%3E
.	Delimits URLs in some systems	%22
#	It is used in the World Wide Web and in other systems to delimit a URL from a fragment/anchor identifier that might follow it.	%23
{	Gateways and other transport agents are known to sometimes modify such characters	%7B
}	Gateways and other transport agents are known to sometimes modify such characters	%7D
|	Gateways and other transport agents are known to sometimes modify such characters	%7C
	Gateways and other transport agents are known to sometimes modify such characters	%5C
^	Gateways and other transport agents are known to sometimes modify such characters	%5E
~	Gateways and other transport agents are known to sometimes modify such characters	%7E
[	Gateways and other transport agents are known to sometimes modify such characters	%5B
]	Gateways and other transport agents are known to sometimes modify such characters	%5D
`	Gateways and other transport agents are known to sometimes modify such characters	%60
+	Indicates a space (spaces cannot be used in a URL)	%20
/	Separates directories and subdirectories	%2F
?	Separates the actual URL and the parameters	%3F
&	Separator between parameters specified in the URL	%26

如何实现

字符的URL编码是将字符转换到8位16进制并在前面加上”%”前缀。例如，US-ASCII字符集中空格是10进制
的32或16进制的20，因此，URL编码是%20。

URLEncode: URLEncode是一个C++类，来实现字符串的URL编码。CURLEncode类包含如下函数：
isUnsafeString
decToHex
convert
URLEncode

URLEncode()函数完成编码过程，URLEncode检查每个字符，看是否安全。如果不安全将用%16进制值进行转换并添加
到原始字符串中。

代码片断:

class CURLEncode
{
private:
  static CString csUnsafeString;
  CString (char num, int radix);
  bool isUnsafe(char compareChar);
  CString convert(char val);

public:
  CURLEncode() { };
  virtual ~CURLEncode() { };
  CString (CString vData);
};

bool CURLEncode::isUnsafe(char compareChar)
{
  bool bcharfound = false;
  char tmpsafeChar;
  int m_strLen = 0;

  m_strLen = csUnsafeString.GetLength();
  for(int ichar_pos = 0; ichar_pos < m_strLen ;ichar_pos++)
  {
    tmpsafeChar = csUnsafeString.GetAt(ichar_pos);
    if(tmpsafeChar == compareChar)
    {
      bcharfound = true;
      break;
    }
  }
  int char_ascii_value = 0;
  //char_ascii_value = __toascii(compareChar);
  char_ascii_value = (int) compareChar;

  if(bcharfound == false &&  char_ascii_value > 32 &&
                             char_ascii_value < 123)
  {
    return false;
  }
  // found no unsafe chars, return false
  else
  {
    return true;
  }

  return true;
}

CString CURLEncode::decToHex(char num, int radix)
{
  int temp=0;
  CString csTmp;
  int num_char;

num_char = (int) num;
  if (num_char < 0)
    num_char = 256 + num_char;

  while (num_char >= radix)
    {
    temp = num_char % radix;
    num_char = (int)floor(num_char / radix);
    csTmp = hexVals[temp];
    }

  csTmp += hexVals[num_char];

  if(csTmp.GetLength() < 2)
  {
    csTmp += ''0'';
  }

  CString strdecToHex(csTmp);
  // Reverse the String
  strdecToHex.MakeReverse();

  return strdecToHex;
}

CString CURLEncode::convert(char val)
{
  CString csRet;
  csRet += "%";
  csRet += decToHex(val, 16);
  return  csRet;
}

参考：

URL编码: http://www.blooberry.com/indexdot/html/topics/urlencoding.htm.

RFC 1866: The HTML 2.0 规范 (纯文本). 附录包含了字符表: http://www.rfc-editor.org/rfc/rfc1866.txt.

Web HTML 2.0 版本(RFC 1866) : http://www.w3.org/MarkUp/html-spec/html-spec_13.html.

The HTML 3.2 (Wilbur) 建议: http://www.w3.org/MarkUp/Wilbur/.

The HTML 4.0 建议: http://www.w3.org/TR/REC-html40/.

W3C HTML 国际化区域: http://www.w3.org/International/O-HTML.html.

在软件的开发过程中，有时需要控制一些程序使他们不能同时运行，也就是多个程序间互斥运行（还包括禁止同一程序运行多个实例）。针对这一问题，我们在Visual C++6.0中利用内存映射文件实现了多个程序间的互斥运行。内存映射文件可以创建一个没有和磁盘文件相联系的内存对象，将文件的信息映射到一个进程的地址空间上，我们可以访问该文件中的数据，就如同它位于内存中一样。同时，在程序设计中可以给内存映射文件对象起一个名字，这个名字在整个系统中是唯一的，这个名字可以在多个进程之间共享，通过名字共享能实现进行信息交换，进而实现多个程序间的互斥运行。

在讲述具体的编程方法之前，让我们先介绍和内存映射文件操作有关的几个重要的函

1. CreateFileMapping的函数为指定的文件创建一个文件映射对象，该函数的原形如下：

   HANDLE CreateFileMapping(HANDLE hFile,//用于映射的文件句柄 LPSECURITY?ATTRIBUTES FileMappingAttributes,//内存映射文件的安全描述符 DWORD Flprotect,//文件映射对象的最大长度的高32位 DWORD dwMaximumSizelow,//最大长度的低32位 LPCTSTR IPNAME//指定这个内存映射文件的名字)

   值得注意的是，参数如果是OXFFFFFFFF，将在操作系统虚拟内存页面替换文件中创建文件映射对象，而不是使用磁盘文件，同时必须给出这个映射对象的大小。

2. NAO VUEWIFFILE函数将文件的视图映射到一个进程地址空间上，返回LPVOID类型的内存指针。通过它，就可以直接访问文件视图中的信息。

LPVOID MAP VIEWLFFILE（HANDLE HFILEMAPPINGOBUCT，//映射文件对象句柄 DWORD DWDESIREDACCESS，//访问模式 DWORD DWFILEOFFSETHIGH，//文件偏移地址的高32位 DWORD DWFILEOFFSETHIGH，//文件偏移地址的低32位 DWORD DWNUMBEROFBYTESTOMAP//映射视图的大小）

在Visual c++6.0中我们用默认方式生成基于对话框的应用程序，在程序的初始化阶段，在CwinApp生类的Initln_stance函数的开始处，添加以下代码：

（//创建内存映射文件对象，mu_texRunning是其名字，所有需要互斥运行 //的程序都使用这个名字（这些代码对于需要互斥运行的程序是通用的）HANDLE hMap=CreateFileMapping((HANDLE)0Xffffffffnull,PAGE_READWRLTE,0,128,"Mu_texRunning") if(hMap==NULL)//如果创建失败 （AfxMessageBox("创建用于互斥运行的内存映文件对象失败！”，MB?OK MB??ICLNSTOP)；

return FALSE;//退出此程序）

//如果已经存在这个同名对象，说明已有需要互斥的其他程序运行了

else if(GetLastError( )==ER_ROR_ALREADY_EXISTS)

(LPVOID ipMen=MapViewOFFile(hMap,FILE_MAP_WRITE,0,0,0);

Cstring str=(char*)ipMem;//获得已在运行的程序的描述信息

UnmapViewofFile(lpMem);//解除映射图

CloseHandle(hMap);//关闭此对象

AfxMessageBox(str,MB_ok MB_ICONSTOP);显示有关的描述信息

Return FALSE;//退出此程序）

Else//经过上面的检查，说明这是第一个运行的互斥程序

（LPVOID ip_mem=MapViewofFile(hMap,FILE_MAP_WRITE,0,0,0);

//这里可写入该程序运行的描述信息，上面的错误提示就是这信信息

strcpy((char*)lpMem,"xxx程序正在运行！”)；

UnmapViewofFile(lpMem);//解除映射图）

//下面可以继续执行函数INITIN?STANCE原有的代码了

AfxEnableControl_comtainer();

//当程序运行结束了，要记住调用CHANDIE（HMAP）关闭这个对象句柄，//这里可以在Initinstance函数最后returnFALSE之前调用

CloseHandle(hMap);//关闭内存映文件对象句柄 RETURN false;)以上的程序在Visual C++6.中已调试通过。其他非对话框类型的程序可以在各自的初始化和终止阶段添加类似的代码，只是如果内存映射文件对象的句柄hMap可能在不同函数中使用，那就要将其定义成CwinApp生类的成员变量或是全局变量了。

   你也许会遇到到这样一个问题？当你有一个较大的软件，而无法用一张软盘将其全部拷下时，你也许会想到该将它分解开，分盘拷回去后，再将它们合并起来。现在的这种分割工具很多，你想自己动手做一个适合自己的分割工具么？下面就让我用以前用VC做的一个＜袖珍文件分割器＞的例程来告诉你吧！程序运行后界面如下图：

基本构成思想：文件分割的基本思想比我之前发表的另一篇文章＜如何将多个文件合并为一个可执行程序＞的构成思想简单多了，它主要也分为分割文件和合并分割后的文件二大部分。分割文件，将原文件按指定分割大小进行等分，然后顺序读取其指定分割大小数据后到写到各自的新建文件中。合并文件，将各分割后的文件顺序读取后，写入到一个文件中既可。

1、分割文件时：打开文件，读取指定的分割大小一段数据，写入到一新建文件中，接着再读同样大小的一段数据，再写入到一新建文件中……，直到读出文件最后一部分数据，写入到最后一个新建文件中。对每一个分割后的新建文件名，采用原文件名前加数字信息的方法，按分割的顺序，按个加上一数字标识信息，以便合并时使用。
分割文件的部分代码实现如下：
//文件分割涵数
int CFileSpltDlg::SplitMe()
{
…… (省略:此部分代码实现省略掉)
//分割文件
do {
//动态建立一个新建文件名的前的数字
name = _ltoa(l, buff, 10);
name += _T("_");
CString newpath;

//判断选择目录未尾是否已有""符
if(m_targetpath.Right(1)==’\’)
newpath = m_targetpath;
else
newpath = m_targetpath + _T("\");
if (!destFile.Open(newpath + name + m_SourceFile.GetFileName(),
CFile::modeWrite |
CFile::shareExclusive |
CFile::typeBinary |
CFile::modeCreate, &ex)) {
TCHAR szError[1024];
ex.GetErrorMessage(szError, 1024);
::AfxMessageBox(szError);
m_SourceFile.Close();
return 1;
}
do {
dwRead = m_SourceFile.Read(buffer, nCount);
destFile.Write(buffer, dwRead);
}//当文件小于指定要分割的大小时
while (dwRead > 0 && destFile.GetLength() < newlen);
destFile.Close();

l++;
UpdateWindow();
}while (dwRead > 0);
m_SourceFile.Close();
return 0;
｝

2、合并文件时：和上面分割所采用的方法相反，将各个分割后的小文件读出后，按其分割后文件名前数字大小的顺序，按个写入到新建的文件中，这一新建文件的名字，为去掉分割后文件前面数字部分后的文件名(既原文件名)。
合并文件的部分代码实现如下：
// 文件合并涵数
int CFileSpltDlg::MergeMe()
{
…… (省略:此部分代码实现省略掉)
//开始合并文件
do {
//自动定位分割文件名前的数字信息
pref = _ltoa(l, buff, 10);
pref += _T("_");
//打开新的分割文件
if (!m_SourceFile.Open(newpath + pref + m_filename,
CFile::modeRead |
CFile::shareExclusive |
CFile::typeBinary, &ex)) {
TCHAR szError[1024];
ex.GetErrorMessage(szError, 1024);
destFile.Close();
m_path = _T("");
m_filename = _T("");
newpath = _T("");
UpdateData(FALSE);
return 0;
}
else
//形成一个新的文件名
name = _T(newpath + pref + m_filename);
do {//写入到目标文件中
dwRead = m_SourceFile.Read(buffer, nCount);
destFile.Write(buffer, dwRead);
}while (dwRead > 0);

m_SourceFile.Close();

l++;
UpdateWindow();
}while (l < 500);//little bit dirty solution, but you can always improve it!…

return 0;
}

以上各部分代码的具体实现，请在下载例程后，参看源代码既可。

联系方式：
地址：陕西省西安市劳动路2号院六单元
邮编：710082
作者EMAIL：jingzhou_xu@163.net