哈夫曼算法进行文件压缩和解压缩
本文首先简要阐述哈夫曼算法的基本思想，然后介绍了使用哈夫曼算法进行文件压缩和解压缩的
处理步骤，最后给出了C语言实现的文件压缩和解压缩的源代码。
哈夫曼算法的主要思想是：
①首先遍历要处理的字符串，得到每个字符的出现的次数；
②将每个字符（以其出现次数为权值）分别构造为二叉树（注意此时的二叉树只有一个节点）；
③取所有二叉树种种字符出现次数最小的二叉树合并为一颗新的二叉树，新二叉树根节点的权值等于两个子节点的权值之和，新节点中的字符忽略；
④重复过程③直到所有树被合并为同一棵二叉树
⑤遍历最后得到的二叉树，自顶向下按路径编号，指向左节点的边编号0，指向右节点的边编号1，从根到叶节点的所有边上的0和1链接起来，就是叶子节点中字符的哈夫曼编码。
下图展示了哈夫曼编码的基本思想。
基于哈夫曼算法的文件压缩和解压缩过程分别说明如下：
一、文件压缩：
①统计词频：读取文件的每个字节，使用整数数组int statistic[MAX_CHARS]统计每个字符出现的次数，
由于一个字节最多表示2^8-1个字符，所以MAX_CHARS=256就足够了。在统计字符数的时候，
对于每一个byte, 有statistic[(unsigned char)byte]++。
②构造哈夫曼树：根据statistic数组，基于哈夫曼树算法造哈夫曼树，由于构造的过程中每次都要取最小权值的字符，
所以需要用优先队列来维护每棵树的根节点。
③生成编码：深度优先遍历哈弗曼树，得到每个叶子节点中的字符的编码并存入字符串数组char *dictionary[MAX_CHARS];
④存储词频：新建存储压缩数据的文件，首先写入不同字符的个数，然后将每个字符及其对应的词频写入文件。
⑤存储压缩数据：再次读取待压缩文件的每个字节byte，由
dictionary[(unsigned int)byte]得到对应的编码（注意每个字符
编码的长度不一），使用位运算一次将编码中的每个位(BIT)设置到一个char 类型的位缓冲中，可能多个编码才能填满一个
位缓冲，每填满一次，将位缓冲区以单个字节的形式写入文件。当文件遍历完成的时候，文件的压缩也就完成了。
二、文件解压：
①读取词频：读取压缩文件，将每个字符的出现次数存入数组statistic
②构造哈夫曼编码树：根据statistic数组构造哈夫曼编码树
③继续读取压缩文件，对于每个字节，使用位运算得到每个位（BIT）。对于每个BIT，根据BIT从根开始遍历哈夫曼树，如果BIT是0就走左分支，如果BIT 是1就走有分支，走到叶子节点的时候，输出对应的字符。走到叶子节点后，重新从哈夫曼树根节点开始匹配每个位。当整个压缩文件读取完毕时，文件解压缩也完成了。
上文介绍了基于哈夫曼算法的文件压缩和解压缩，下面给出基于上述思想的C 语言源代码，一共有5个文件，其中pq.h和pq.c
是优先队列，compress.h和compress.c是压缩和解压缩的实现，main.c是测试文件。
pq.h和pq.c请参见《优先队列(priority_queue)的C语言实现》：
https://www.wendangku.net/doc/5612929195.html,/gropefor/blog/item/7d958eb68359cbe230add14e.html 另外三个文件内容如下：
* File: compress.h
* Purpose: To compress file using the Haffman algorithm
* Author: puresky
* Date: 2011/05/01
*/
#ifndef _FILE_COMPRESSION_H
#define _FILE_COMPRESSION_H
//Haffuman Tree Node
typedef struct HaffumanTreeNode HTN;
struct HaffumanTreeNode
{
char _ch; //character
int _count; //frequency
struct HaffumanTreeNode *_left; //left child
struct HaffumanTreeNode *_right;//rigth child
};
//FileCompress Struct
#define BITS_PER_CHAR 8 //the number of bits in a char
#define MAX_CHARS 256 //the max number of chars
#define FILE_BUF_SIZE 8192 //the size of Buffer for FILE I/O
typedef struct FileCompressStruct FCS;
struct FileCompressStruct
{
HTN *_haffuman; //A pointer to the root of hafumman tree unsigned int _charsCount; //To store the number of chars
unsigned int _total; //Total bytes in a file.
char *_dictionary[MAX_CHARS]; //to store the encoding of each character
int _statistic[MAX_CHARS]; //To store the number of each character };
FCS *fcs_new();
void fcs_compress(FCS *fcs, const char *inFileName, const char
*outFileName);
void fcs_decompress(FCS *fcs, const char *inFileName, const char
*outFileName);
void fcs_free(FCS *fcs);
#endif
* File: compress.c
* Purpose: To compress file using the Haffman algorithm * Author: puresky
* Date: 2011/05/01
*/
#include
#include
#include
#include "compress.h"
#include "pq.h"
static const unsigned char mask[8] =
{
0x80, /* 10000000 */
0x40, /* 01000000 */
0x20, /* 00100000 */
0x10, /* 00010000 */
0x08, /* 00001000 */
0x04, /* 00000100 */
0x02, /* 00000010 */
0x01 /* 00000001 */
};
//static functions of HTN
static HTN *htn_new(char ch, int count)
{
HTN *htn = (HTN *)malloc(sizeof(HTN));
htn->_left = NULL;
htn->_right = NULL;
htn->_ch = ch;
htn->_count = count;
return htn;
}
static void htn_print_recursive(HTN *htn, int depth) {
int i;
if(htn)
{
for(i = 0; i < depth; ++i)
printf(" ");
printf("%d:%d\n", htn->_ch, htn->_count); htn_print_recursive(htn->_left, depth + 1);
htn_print_recursive(htn->_right, depth + 1);
}
}
static void htn_print(HTN *htn)
{
htn_print_recursive(htn, 0);
}
static void htn_free(HTN *htn)
{
if(htn)
{
htn_free(htn->_left);
htn_free(htn->_right);
free(htn);
}
}
//static functions of FCS
static void fcs_generate_statistic(FCS *fcs, const char *inFileName) {
int ret, i;
unsigned char buf[FILE_BUF_SIZE];
FILE *pf = fopen(inFileName, "rb");
if(!pf)
{
fprintf(stderr, "can't open file:%s\n", inFileName);
return;
}
while((ret = fread(buf, 1, FILE_BUF_SIZE, pf)) > 0)
{
fcs->_total += ret;
for(i = 0; i < ret; ++i)
{
if(fcs->_statistic[buf[i]] == 0)
fcs->_charsCount++;
fcs->_statistic[buf[i]]++;
}
}
fclose(pf);
}
static void fcs_create_haffuman_tree(FCS *fcs)
{
int i, count;
HTN *htn, *parent, *left, *right;
KeyValue *kv, *kv1, *kv2;
PriorityQueue *pq;
pq = priority_queue_new(PRIORITY_MIN);
for(i = 0; i < MAX_CHARS; ++i)
{
if(fcs->_statistic[i])
{
htn = htn_new((char)i, fcs->_statistic[i]); kv = key_value_new(fcs->_statistic[i], htn); priority_queue_enqueue(pq, kv);
}
}
//fprintf(stdout, "the number of haffuman leaf is %d\n", priority_queue_size(pq));
while(!priority_queue_empty(pq))
{
//fprintf(stdout, "priority queue size:%d\n", priority_queue_size(pq));
kv1 = priority_queue_dequeue(pq);
kv2 = priority_queue_dequeue(pq);
if(kv2 == NULL)
{
fcs->_haffuman = kv1->_value;
key_value_free(kv1, NULL);
}
else
{
left = (HTN *)kv1->_value;
right = (HTN *)kv2->_value;
count = left->_count + right->_count;
key_value_free(kv1, NULL);
key_value_free(kv2, NULL);
parent = htn_new(0, count);
parent->_left = left;
parent->_right = right;
kv = key_value_new(count, parent);
priority_queue_enqueue(pq, kv);
}
}
priority_queue_free(pq, NULL);
//htn_print(fcs->_haffuman);
}
static void fcs_generate_dictionary_recursively(HTN *htn, char
*dictionary[], char path[], int depth)
{
char *code = NULL;
if(htn)
{
if(htn->_left == NULL && htn->_right == NULL)
{
code = (char *)malloc(sizeof(char) * (depth + 1)); memset(code, 0, sizeof(char) * (depth + 1));
memcpy(code, path, depth);
dictionary[(unsigned char)htn->_ch] = code;
}
if(htn->_left)
{
path[depth] = '0';
fcs_generate_dictionary_recursively(htn->_left, dictionary, path, depth + 1);
}
if(htn->_right)
{
path[depth] = '1';
fcs_generate_dictionary_recursively(htn->_right, dictionary, path, depth + 1);
}
}
}
static void fcs_generate_dictionary(FCS *fcs)
{
char path[32];
fcs_generate_dictionary_recursively(fcs->_haffuman,
fcs->_dictionary, path, 0);
//fcs_print_dictionary(fcs);
}
static void fcs_print_dictionary(FCS *fcs)
{
int i;
for(i = 0; i < MAX_CHARS; ++i)
if(fcs->_dictionary[i] != NULL)
fprintf(stdout, "%d:%s\n", i, fcs->_dictionary[i]); }
static void fcs_write_statistic(FCS *fcs, FILE *pf)
{
int i;
fprintf(pf, "%d\n", fcs->_charsCount);
for(i = 0; i < MAX_CHARS; ++i)
if(fcs->_statistic[i] != 0)
fprintf(pf, "%d %d\n", i, fcs->_statistic[i]);
}
static void fcs_do_compress(FCS *fcs, const char *inFileName, const char* outFileName)
{
int i, j, ret;
char *dictEntry, len;
unsigned int bytes;
char bitBuf;
int bitPos;
unsigned char inBuf[FILE_BUF_SIZE];
FILE *pfIn, *pfOut;
pfIn = fopen(inFileName, "rb");
if(!pfIn)
{
fprintf(stderr, "can't open file:%s\n", inFileName);
return;
}
pfOut = fopen(outFileName, "wb");
if(!pfOut)
{
fclose(pfIn);
fprintf(stderr, "can't open file:%s\n", outFileName);
return;
}
fcs_write_statistic(fcs, pfOut);
bitBuf = 0x00;
bitPos = 0;
bytes = 0;
while((ret = fread(inBuf, 1, FILE_BUF_SIZE, pfIn)) > 0)
{
for(i = 0; i < ret; ++i)
{
len = strlen(fcs->_dictionary[inBuf[i]]);
dictEntry = fcs->_dictionary[inBuf[i]];
//printf("%s\n", dictEntry);
for(j = 0; j < len; ++j)
{
if(dictEntry[j] == '1')
{
bitBuf |= mask[bitPos++];
}
else
{
bitPos++;
}
if(bitPos == BITS_PER_CHAR)
{
fwrite(&bitBuf, 1, sizeof(bitBuf), pfOut);
bitBuf = 0x00;
bitPos = 0;
bytes++;
}
}
}
}
if(bitPos != 0)
{
fwrite(&bitBuf, 1, sizeof(bitBuf), pfOut);
bytes++;
}
fclose(pfIn);
fclose(pfOut);
printf("The compression ratio is:%f%%\n",
(fcs->_total - bytes) * 100.0 / fcs->_total);
}
static void fcs_read_statistic(FCS *fcs, FILE *pf)
{
int i, charsCount = 0;
int ch;
int num;
fscanf(pf, "%d\n", &charsCount);
fcs->_charsCount = charsCount;
for(i = 0; i < charsCount; ++i)
{
fscanf(pf, "%d %d\n", &ch, &num);
fcs->_statistic[(unsigned int)ch] = num;
fcs->_total += num;
}
}
static void fcs_do_decompress(FCS *fcs, FILE *pfIn, const char
*outFileName)
{
int i, j, ret;
unsigned char ch;
HTN *htn;
unsigned char buf[FILE_BUF_SIZE];
unsigned char bitCode;
int bitPos;
FILE *pfOut;
pfOut = fopen(outFileName, "wb");
if(!pfOut)
{
fprintf(stderr, "can't open file:%s\n", outFileName); return;
}
htn = fcs->_haffuman;
bitCode = 0x00;
bitPos = 0;
while((ret = fread(buf, 1, FILE_BUF_SIZE, pfIn)) > 0)
{
for(i = 0; i < ret; ++i)
{
ch = buf[i];
for(j = 0; j < BITS_PER_CHAR; ++j)
{
if(ch & mask[j])
{
htn = htn->_right;
}
else
{
htn = htn->_left;
}
if(htn->_left == NULL && htn->_right == NULL) //leaf
{
if(fcs->_total > 0)
{
fwrite(&htn->_ch, 1, sizeof(char), pfOut);
fcs->_total--;
}
htn = fcs->_haffuman;
}
}
}
}
fclose(pfOut);
}
//FCS functions
FCS *fcs_new()
{
FCS *fcs = (FCS *)malloc(sizeof(FCS));
fcs->_charsCount = 0;
fcs->_total = 0;
memset(fcs->_statistic, 0, sizeof(fcs->_statistic));
memset(fcs->_dictionary, 0, sizeof(fcs->_dictionary));
fcs->_haffuman = NULL;
return fcs;
}
void fcs_free(FCS *fcs)
{
int i;
if(fcs)
{
if(fcs->_haffuman)
htn_free(fcs->_haffuman);
for(i = 0; i < MAX_CHARS; ++i)
free(fcs->_dictionary[i]);
free(fcs);
}
}
void fcs_compress(FCS *fcs, const char *inFileName, const char
*outFileName)
{
fprintf(stdout, "To compress file: %s ...\n", inFileName);
fcs_generate_statistic(fcs, inFileName);
fcs_create_haffuman_tree(fcs);
fcs_generate_dictionary(fcs);
fcs_do_compress(fcs, inFileName, outFileName);
fprintf(stdout, "The compressed data of file: %s stored at %s!\n", inFileName, outFileName);
}
void fcs_decompress(FCS *fcs, const char *inFileName, const char
*outFileName)
{
FILE *pfIn;
fprintf(stdout, "To decompress file: %s ...\n", inFileName);
pfIn= fopen(inFileName, "rb");
if(!pfIn)
{
fprintf(stderr, "can't open file: %s\n", inFileName);
return ;
}
fcs_read_statistic(fcs, pfIn);
fcs_create_haffuman_tree(fcs);
fcs_generate_dictionary(fcs);
fcs_do_decompress(fcs, pfIn, outFileName);
fclose(pfIn);
fprintf(stdout, "The decompressed data of file: %s stored at %s\n", inFileName, outFileName);
}
/*
* File: main.c
* Purpose: testing File Compression
* Author:puresky
* Date: 2011/05/01
*/
#include
#include "compress.h"
const int DO_COMPRESS = 1;
const int DO_DECOMPRESS = 1;
const char *InFile = "data.txt"; //The file to compress.
const char *CompressedFile = "data.hfm"; //Compressed data of the file. const char *OutFile = "data2.txt"; //The decompressed file of the data.
int main(int argc, char **argv)
{
//1. compress file
if(DO_COMPRESS)
{
FCS *fcs1;
fcs1 = fcs_new();
fcs_compress(fcs1, InFile, CompressedFile);
fcs_free(fcs1);
}
//2. decompress file
if(DO_DECOMPRESS)
{
FCS *fcs2;
fcs2 = fcs_new();
fcs_decompress(fcs2, CompressedFile, OutFile);
fcs_free(fcs2);
}
system("pause");
return 0;
}
优先队列（priority_queue)和一般队列(queue)的函数接口一致，不同的是，优先队列每次出列的是整个队列中
最小（或者最大）的元素。
本文简要介绍一种基于数组二叉堆实现的优先队列，定义的数据结构和实现的函数接口说明如下：
一、键值对结构体：KeyValue
// =============KeyValue Struct================================== typedef struct key_value_struct KeyValue;
struct key_value_struct
{
int _key;
void *_value;
};
KeyValue *key_value_new(int key, void *value);
void key_value_free(KeyValue *kv, void (*freevalue)(void *));
键值对作为优先队列的中数据的保存形式，其中key用于保存优先级，_value
用于指向实际的数据。
key_value_new用于创建一个KeyValue结构体；key_value_free用于释放一个KeyValue结构体的内存，
参数freevalue用于释放数据指针_value指向的内存。
二、优先队列结构体：PriorityQueue
// =============PriorityQueue Struct==============================
#define PRIORITY_MAX 1
#define PRIORITY_MIN 2
typedef struct priority_queue_struct PriorityQueue;
struct priority_queue_struct
{
KeyValue **_nodes;
int _size;
int _capacity;
int _priority;
};
PriorityQueue *priority_queue_new(int priority);
void priority_queue_free(PriorityQueue *pq, void (*freevalue)(void *)); const KeyValue *priority_queue_top(PriorityQueue *pq);
KeyValue *priority_queue_dequeue(PriorityQueue *pq);
void priority_queue_enqueue(PriorityQueue *pq, KeyValue *kv);
int priority_queue_size(PriorityQueue *pq);
int priority_queue_empty(PriorityQueue *pq);
void priority_queue_print(PriorityQueue *pq);
1) 其中nodes字段是二叉堆数组，_capacity是nodes指向的KeyValue*指针的个数，_size是nodes中实际存储的元素个数。
_priority可以是PRIORITY_MAX或PRIORITY_MIN，分别表示最大元素优先和最小元素优先。
2) priority_queue_new和priority_queue_free分别用于创建和释放优先队列。
3) priority_queue_top用于取得队列头部元素，
4）priority_queue_dequeue用于取得队列头部元素并将元素出列。
其实现的基本思路，以最大优先队列说明如下：
①将队列首部nodes[0]保存作为返回值
②将队列尾部nodes[_size-1]置于nodes[0]位置，并令_size=_size-1
③令当前父节点parent(nodes[i])等于新的队列首部(i=0)元素，parent
指向元素的儿子节点为left = nodes[2 * i + 1]和rigth = nodes[2 * i + 2]，比较left和right得到优先级高的儿子节点,设为nodes[j](j = 2 *i + 1或2 *i + 2)，
④如果当前父节点parent的优先级高于nodes[j]，交换nodes[i]和
nodes[j]，并更新当前父节点,即令i=j,并循环③；
如果当前父节点的优先级低于nodes[j],处理结束。
5）priority_queue_enqueue用于将KeyValue入列
其实现的基本思路，以最大优先队列说明如下：
①设置nodes[_size] 为新的KeyValue,并令_size++
②令当前儿子节点child(nodes[i])为新的队列尾部节点（i=_size-1)，child的父节点parent为nodes[j],其中j= (i - 1) / 2
③如果当前儿子节点child的优先级高于parent, 交换nodes[i]和
nodes[j]，并更新当前儿子节点即令i = j,并循环③;
如果当前儿子节点的优先级低于parent,处理结束。
6) priority_queue_size用于取得队列中元素个数，priority_queue_empty 用于判断队列是否为空。
7）priority_queue_print用于输出队列中的内容。
文件pq.h给出了数据结构和函数的声明，文件pq.c给出了具体实现，main.c 文件用于测试。虽然是使用
过程化编程的C语言，可以看到具体的编码中应用了基于对象的思想，我们对数据结构和相关函数做了一定程度的
聚集和封装。
/*
*File: pq.h
*purpose: declaration of priority queue in C
*Author:puresky
*Date:2011/04/27
*/
#ifndef _PRIORITY_QUEUE_H
#define _PRIORITY_QUEUE_H
// =============KeyValue Struct================================== typedef struct key_value_struct KeyValue;
struct key_value_struct
{
int _key;
void *_value;
};
KeyValue *key_value_new(int key, void *value);
void key_value_free(KeyValue *kv, void (*freevalue)(void *));
// =============PriorityQueue Struct==============================
#define PRIORITY_MAX 1
#define PRIORITY_MIN 2
typedef struct priority_queue_struct PriorityQueue;
struct priority_queue_struct
{
KeyValue **_nodes;
int _size;
int _capacity;
int _priority;
};
PriorityQueue *priority_queue_new(int priority);
void priority_queue_free(PriorityQueue *pq, void (*freevalue)(void *)); const KeyValue *priority_queue_top(PriorityQueue *pq);
KeyValue *priority_queue_dequeue(PriorityQueue *pq);
void priority_queue_enqueue(PriorityQueue *pq, KeyValue *kv);
int priority_queue_size(PriorityQueue *pq);
int priority_queue_empty(PriorityQueue *pq);
void priority_queue_print(PriorityQueue *pq);
#endif
/*
*File:pq.c
*purpose: definition of priority queue in C
*Author:puresky
*Date:2011/04/27
*/
#include
#include
#include
#include "pq.h"
//Private Functions
static void priority_queue_realloc(PriorityQueue *pq);
static void priority_queue_adjust_head(PriorityQueue *pq);
static void priority_queue_adjust_tail(PriorityQueue *pq);
static int priority_queue_compare(PriorityQueue *pq,
int pos1,
int pos2);
static void priority_queue_swap(KeyValue **nodes,
int pos1,
int pos2);
//Functions of KeyValue Struct
KeyValue *key_value_new(int key,
void *value)
{
KeyValue *pkv = (KeyValue *)malloc(sizeof(KeyValue));
pkv->_key = key;
pkv->_value = value;
return pkv;
}
void key_value_free(KeyValue *kv,
void (*freevalue)(void *))
{
if(kv)
{
if(freevalue)
{
freevalue(kv->_value);
}
free(kv);
}
}
//Functions of PriorityQueue Struct
PriorityQueue *priority_queue_new(int priority)
{
PriorityQueue *pq = (PriorityQueue
*)malloc(sizeof(PriorityQueue));
pq->_capacity = 11; //default initial value
pq->_size = 0;
pq->_priority = priority;
pq->_nodes = (KeyValue **)malloc(sizeof(KeyValue *) *
pq->_capacity);
return pq;
}
void priority_queue_free(PriorityQueue *pq,
void (*freevalue)(void *)) {
int i;
if(pq)
{
for(i = 0; i < pq->_size; ++i)
key_value_free(pq->_nodes[i], freevalue);
free(pq->_nodes);
free(pq);
}
}
const KeyValue *priority_queue_top(PriorityQueue *pq)
{
if(pq->_size > 0)
return pq->_nodes[0];
return NULL;
}
KeyValue *priority_queue_dequeue(PriorityQueue *pq) {
KeyValue *pkv = NULL;
if(pq->_size > 0)
{
pkv = pq->_nodes[0];
priority_queue_adjust_head(pq);
}
return pkv;
}
void priority_queue_enqueue(PriorityQueue *pq,
KeyValue *kv) {
printf("add key:%d\n", kv->_key);
pq->_nodes[pq->_size] = kv;
priority_queue_adjust_tail(pq);
if(pq->_size >= pq->_capacity)
priority_queue_realloc(pq);
}
int priority_queue_size(PriorityQueue *pq)
{
return pq->_size;
}
int priority_queue_empty(PriorityQueue *pq)
{
return pq->_size <= 0;
}
void priority_queue_print(PriorityQueue *pq)
{
int i;
KeyValue *kv;
printf("data in the pq->_nodes\n");
for(i = 0; i < pq->_size; ++i)
printf("%d ", pq->_nodes[i]->_key);
printf("\n");
printf("dequeue all data\n");
while(!priority_queue_empty(pq))
关于计算极限的几种方法
目录 摘要 (1) 引言 (2) 一．利用导数定义求极限 (2) 二．利用中值定理求极限 (2) 三．利用定积分定义求极限 (3) 四．利用施笃兹公式 (4)
五．利用泰勒公式 (5) 六．级数法 (5) 七．结论 (6) 参考文献 (6)
内容摘要
引言： 极限是分析数学中最基本的概念之一，用以描述变量在一定的变化过程中的终极状态。早在中国古代，极限的朴素思想和应用就已在文献中有记载。例如,3世纪中国数学家刘徽的割圆术，就是用圆内接正多边形周长的极限是圆周长这一思想来近似地计算圆周率 的。随着微积分学的诞生，极限作为数学中的一个概念也就明确提出。但最初提出的这一概念是含糊不清的，因此在数学界引起不少争论甚至怀疑。直到19世纪，由A.-L.柯西、K. (T.W.)外尔斯特拉斯等人的工作，才将其置于严密的理论基础之上，从而得到举世一致的公认。 数学分析中的基本概念的表述，都可以用极限来描述。如函数()x f y =在 0x x =处导数的定义，定积分的定义，偏导数的定义，二重积分，三重积分的定义，无穷级数收敛的定义，都是用极限来定义的。极限是研究数学分析的基本公具。极限是贯穿数学分析的一条主线。 一．利用导数定义求极限 据文[]1定理1导数的定义：函数)(x f 在0x 附近有定义，对于任意的x ?， 则)()(00x f x x f y -?+=? 如果x x f x x f x x ?-?+=→?→? ) ()(lim lim 000 0存在，则此极限值就 称函数)(x f 在点0x 的导数记为 )('0x f .即x x f x x f x f x ?-?+=→?) ()(lim )('0000在这 种方法的运用过程中。首先要选好)(x f ，然后把所求极限。表示成)(x f 在定点0x 的导数。 例1：求a x x a a x x a a a a x --→lim 解：原式0)(lim lim 1lim 0---?=---=-→→→a x x a a x a a x a x x a a a x x a a a a x a a a a a x x a x x ，令a x x a y -=， 当a x →时，0→y ，故原式a a a a a a a y y a ln |)'(0=?== 一般地，能直接运用导数定义求的极限就直接用导数定义来求，值得注意的是许
中衡算法分析与【设计明细】-实验二-哈夫曼编码
昆明理工大学信息工程与自动化学院学生实验报告 （201 —201 学年第一学期） 课程名称：算法设计与分析开课实验室：年月日 一、上机目的及内容 1.上机内容 设需要编码的字符集为{d1, d2, …, dn}，它们出现的频率为{w1, w2, …, wn}，应用哈夫曼树构造最短的不等长编码方案。 2.上机目的 （1）了解前缀编码的概念，理解数据压缩的基本方法； （2）掌握最优子结构性质的证明方法； （3）掌握贪心法的设计思想并能熟练运用。 二、实验原理及基本技术路线图（方框原理图或程序流程图） （1）证明哈夫曼树满足最优子结构性质； （2）设计贪心算法求解哈夫曼编码方案； （3）设计测试数据，写出程序文档。 数据结构与算法: typedef char *HuffmanCode; //动态分配数组，存储哈夫曼编码 typedef struct { unsigned int weight; //用来存放各个结点的权值 unsigned int parent,LChild,RChild; //指向双亲、孩子结点的指针 } HTNode, *HuffmanTree; //动态分配数组，存储哈夫曼树 程序流程图：
三、所用仪器、材料（设备名称、型号、规格等或使用软件） 1台PC及VISUAL C++6.0软件
四、实验方法、步骤（或：程序代码或操作过程） 程序代码： #include
常用图像压缩方法
常用图像压缩方法 概述了常用的图像压缩方法，包括行程长度压缩，霍夫曼编码压缩，LZW压缩方法，算术压缩方法，JPEG压缩等。 一、行程长度压缩 原理是将一扫描行中的颜色值相同的相邻像素用一个计数值和那些像素的颜色值来代替。例如:aaabccccccddeee，则可用3a1b6c2d3e来代替。对于拥有大面积，相同颜色区域的图像，用RLE压缩方法非常有效。由RLE原理派生出许多具体行程压缩方法: 1. PCX行程压缩方法 该算法实际上是位映射格式到压缩格式的转换算法，该算法对于连续出现1次的字节Ch，若Ch>0xc0则压缩时在该字节前加上0xc1，否则直接输出Ch，对于连续出现N次的字节Ch，则压缩成0xc0＋N，Ch这两个字节，因而N最大只能为ff－c0=3fh(十进制为63)，当N大于63时，则需分多次压缩。 2. BI_RLE8压缩方法 在WINDOWS3.0、3.1的位图文件中采用了这种压缩方法。该压缩方法编码也是以两个字节为基本单位。其中第一个字节规定了用第二个字节指定的颜色重复次数。如编码0504表示从当前位置开始连续显示5个颜色值为04的像素。当第二个字节为零时第二个字节有特殊含义:0表示行末;1 表示图末;2转义后面2个字节，这两个字节分别表示下一像素相对于当前位置的水平位移和垂直位移。这种压缩方法所能压缩的图像像素位数最大为8位(256色)图像。 3. BI_RLE压缩方法 该方法也用于WINDOWS3.0/3.1位图文件中，它与BI_RLE8编码类似，唯一不同是:BI_RLE4的一个字节包含了两个像素的颜色，因此，它只能压缩的颜色数不超过16的图像。因而这种压缩应用范围有限。 4. 紧缩位压缩方法(Packbits) 该方法是用于Apple公司的Macintosh机上的位图数据压缩方法，TIFF规范中使用了这种方法，这种压缩方法与BI_RLE8压缩方法相似，如 1c1c1c1c2132325648压缩为:831c2181325648，显而易见，这种压缩方法最好情况是每连续128个字节相同，这128个字节可压缩为一个数值7f。这种方法还是非常有效的。
贪心算法构造哈夫曼树
软件02 1311611006 张松彬利用贪心算法构造哈夫曼树及输出对应的哈夫曼编码 问题简述： 两路合并最佳模式的贪心算法主要思想如下： （1）设w={w0,w1,......wn-1}是一组权值，以每个权值作为根结点值，构造n棵只有根的二叉树 （2）选择两根结点权值最小的树，作为左右子树构造一棵新二叉树，新树根的权值是两棵子树根权值之和 （3）重复（2），直到合并成一颗二叉树为 一、实验目的 （1）了解贪心算法和哈夫曼树的定义（2）掌握贪心法的设计思想并能熟练运用（3）设计贪心算法求解哈夫曼树（4）设计测试数据，写出程序文档 二、实验内容 （1）设计二叉树结点数据结构，编程实现对用户输入的一组权值构造哈夫曼树（2）设计函数，先序遍历输出哈夫曼树各结点3)设计函数，按树形输出哈夫曼树 代码： #include