数据结构实习报告

}

/***更新编码树**/

void updateTree(unsigned char newchar) {

int current; int max;

/***把findchar函数的返回值赋给current**/

/**当前节点标记为新加入的那个字符letter，若字符letter在编码树中出现过， current记录它的下标，max标记与此字符出现频率相同最大下标值的节点**/

/**如果新读入的这个字符在编码树中出现过**/ if ( ( current=findchar(newchar) ) >= 0 )// first appearance for symbol Go to symbol external node {

max = highestInBlock(tree[current].count); // Node number max in block? if (current != max && tree[current].parent != max)

/**判断当前节点(此时是包含出现过的字符的节点)的双亲节点的下标是否为同一个block (权值相同的所有节点)的最大下标，如果不是，就把当前节点与具有最大下表的节点交换 当前节点的下标更新为同一个block中的最大下标，然后将当前节点的权值加1；若果当前 节点的双亲节点的下表就是它所在的block中最大的下标，则就把当前节点的权值（即节点 所包含字符出现频率）加1**/ {

swap(current, max); // Switch node with highest node in block

current = max; }

tree[current].count++; // Increment node weight } /**如果新读入的字符在编码树中未出现过**/ else {

// Yes

current = spawn(newchar); /**当前节点更新为新的NYT节点**/ // NYT gives birth to new NYT and external node

/**NYT节点产生新的NYT节点和叶节点，同时原NYT节点的字符指向为空 左孩子为新的NYT节点(权值为0)，右孩子为新出现的字符**/

current = tree[current].parent; // Go to old NYT node /**当前节点更新为新的NYT节点的双亲节点（即原来的NYT节点）**/

tree[current].count++; // Increment count of old NYT node /**原NYT节点的权值加1，即原NYT节点的权值变为1**/ }

17

/**至此，总结：

（1）若新读入的字符在编码树中出现过，已经把包含本次读入字符的节点的权值加1 当前节点是包含本次读入字符的节点

（2）若新读入的字符在编码树中没有出现过，构造了子树后，原来的NYT节点权值加1 当前节点更新为原来的NYT节点**/

/**以下过程直到当前节点为根节点结束：

当前节点更新为当前节点的双亲节点，再把当前节点更新为与现在的当前节点 具有相同权值的最大编号的节点，以进行及节点权值加1操作**/

while (current != root) // Is this the root node? {

current = tree[current].parent; // Go to parent node max = highestInBlock(tree[current].count); // Node number max in block? if (current != max && tree[current].parent != max) {

swap(current, max); // Switch node with highest node in block current = max; }

tree[current].count++; // Increment node weight } }

/**对字符文本进行编码，返回编码后的字符串数组**/ unsigned char* encoding(unsigned char *tempString) { unsigned char *code;/**code用来指向输出的码字流**/ unsigned char hold,bin[10000]; int i ; // encoding for (i=0; i

是：n为字符letter在编码树数组中的下标，否：n=-1**/ if (n>=0) {/**n>0则found in the tree在编码数数组中找到了字符hold 则输出码字流：找到编码树数组中**/ code = char2code( hold ); // translated into the corresponding binary code

18

updateTree(hold); strcpy(bin,strcat(bin,code)); } else/**如果在编码树中没有找到字符，此字符的编码包括更新前NYT节点的编码 (按照哈弗曼编码的方式)和当前字符的原始表达**/ { //not found in the tree code = char2code(NYT); /**更新前NYT节点的编码**/ // translated into the corresponding binary code

updateTree(hold);/**加入字符hold后，更新编码树**/ strcat(bin,code);

code = char2binary(hold);/**得到当前字符的原始二进制表达*/ strcat(bin,code);

/**将两个步骤中得到的编码分别存入bin数组**/ } } return bin; /**返回更新后的bin数组**/ }

//文本压缩函数

//将码字流(字符流)以二进制形式(0/1)写入另一文本 //返回压缩内容字节数 void Compress() {

unsigned char g[1000],bin[10000];

char infile[20]=\ FILE *ifp,*ofp;

float rate=0.0; //压缩率

char code[256]; //二进制文本码字数组 int i,j,k=0,temp=0,p,w=0,n,s[10000]; printf(\请输入要压缩的文件名:\ //scanf(\ ifp=fopen(infile,\ if(ifp==NULL) {

printf(\文件名输入错误，文件不存在!\\n\ return; } printf(\请输入目标文件名:\ //scanf(\ ofp=fopen(outfile,\ if(ofp==NULL) {

printf(\文件名输入错误，文件不存在!\\n\ return;

19

}

fgets(g, 1000, ifp);

/**fgets函数fgets函数用来从文件中读入字符串。 fgets函数的调用形式如下：fgets（str，n，fp）

此处，fp是文件指针；str是存放在字符串的起始地址； n是一个int类型变量。

函数的功能是从fp所指文件中读入n-1个字符放入str为起始地址的空间内； 如果在未读满n-1个字符之时，已读到一个换行符或一个EOF（文件结束标志）， 则结束本次读操作，读入的字符串中最后包含读到的换行符。 因此，确切地说，调用fgets函数时，最多只能读入n-1个字符。 读入结束后，系统将自动在最后加'\\0'，并以str作为函数值返回。**/

printf(\文本内容\\n\

printf(\以字符串格式打印文本**/ initalCode();

/**构造编码数数组并初始化编码树数组元素 编码树的初始状态只包含一个根节点，包含符号NYT(not yet transmitted, 尚未传送)，权重值为0**/ strcpy(bin,encoding(g)); /**把对g(待编码的字符数组)编码后的结果 完全复制到数组bin中，连字符串结束标志也一起复制**/ printf(\编码内容\\n\ printf(\

n=strlen(bin); p=n%8;

/**求出数组bin中最后一个字节所占有效比特位数**/ for(i=0;i

if(bin[i]=='1')s[i]=1; if(bin[i]=='0')s[i]=0; }

/**把char型的bin数组转换成对应的int型数组s，char型数组存放的是字符的ASCII码值，

占1个字节，int型数组以数字的二进制形式存储**/ for(i=0;i

for(j=0;j<8;j++)

/**控制内层循环次数，8次，即在int型数组s中每次都连续取8个 整数**/ {

20