哈夫曼树实现文件解压缩

#include "Huffman.h" unsigned char input_buffer[16384];//2^14 int main(int argc,char* argv[]){ FILE* inFile; if((inFile=fopen("a.java","rb"))==NULL){ printf("Can't open file to read!\n"); exit(0); } if((outFile=fopen("Huff.a","wb"))==NULL){ printf("can't open file to write!\n"); exit(0); } initOutBuf(); initNodeAddress(); /*对每一个接收到的字符，进行编码，并随时更新树*/ /*接受第一个字符*/ int hc; hc=fgetc(inFile); if(hc==EOF)goto EXIT; /*设置根*/ root=zeroNode=createNode(); fputc((unsigned char)hc,outFile);//输出第一个字符 /*重新更新树*/ updateTree(hc); int nread;/*读的字节数*/ /*读更多的字符，主循环*/ while(1){ nread=fread(input_buffer,1,16384,inFile); if(nread==0)break; int i=0; /*对每一个字符做处理*/ while(i<nread){ hc=(unsigned char)input_buffer[i]; i++; if(nodeAddress[hc]!=NULL){//不是一个新字符 /*输出编码*/ Code(nodeAddress[hc]); } else{//是一个新字符 /*输出zeroNode的编码*/ Code(zeroNode); put_nbits(hc,8); } /*更新树*/ updateTree(hc); } } flushOutBuf(); EXIT: freeOutBuf(); fclose(inFile); fclose(outFile); return 0; } void initNodeAddress(){ int i; for(i=0;i<256;i++) nodeAddress[i]=NULL; } listNode* createNode(){ listNode* node; if(count<2*256+1){ node=&nodes[count]; count++; } else return NULL; node->index=0; node->ch=-1; node->frequency=0; node->leftChild=NULL; node->rightChild=NULL; node->parent=NULL; node->next=NULL; return node; } void createNewZeroNode(int c){ zeroNode->leftChild=createNode(); zeroNode->rightChild=createNode(); zeroNode->leftChild->parent=zeroNode; zeroNode->rightChild->parent=zeroNode; /*原来的zeroNode变成内部节点，左孩子变成新的zeroNode*/ zeroNode->ch=INTERNAL_NODE; nodeAddress[c]=zeroNode->rightChild; nodeAddress[c]->ch=c; zeroNode->index=hasNotAssign--; nodeAddress[c]->index=hasNotAssign--; /*把新的节点放入numbers链表中*/ numbers[zeroNode->index]=zeroNode; numbers[nodeAddress[c]->index]=nodeAddress[c]; zeroNode=zeroNode->leftChild; zeroNode->ch=ZERO_NODE; } void swap(listNode* a,listNode* b){ listNode* parent,*temp=NULL; if(a->parent==b->parent){ parent=a->parent; if(parent->leftChild==a){ parent->leftChild=b; parent->rightChild=a; } else{ parent->leftChild=a; parent->rightChild=b; } goto numbersSwap; } if(a->parent->leftChild==a) a->parent->leftChild=b; else a->parent->rightChild=b; if(b->parent->leftChild==b) b->parent->leftChild=a; else b->parent->rightChild=a; //a,b指向的parent交换 parent=a->parent; a->parent=b->parent; b->parent=parent; numbersSwap: temp=numbers[a->index]; numbers[a->index]=b; numbers[b->index]=temp; int i=a->index; a->index=b->index; b->index=i; } listNode* getHighestEqualLeaf(listNode* node){ listNode* highest=NULL; int i; /*从当前的后一个索引开始,链表是由出现次数的多少从小到大排列*/ for (i=node->index+1;i<256*2;i++ ) { if(node->frequency==numbers[i]->frequency) {//需要找到最远的节点，且必须是叶节点 if(numbers[i]->ch!=INTERNAL_NODE) highest = numbers[i]; } else break; } return highest; } listNode* getHighestEqualNode(listNode* node){ listNode* highest=NULL; int i; /*从当前的后一个索引开始,链表是由出现次数的多少从小到大排列*/ for (i=node->index+1;i<256*2;i++ ) { if(node->frequency==numbers[i]->frequency) //需要找到最远的节点 highest = numbers[i]; else break; } return highest; } void updateTree(int value){ listNode* highest=NULL,*node=nodeAddress[value]; if(node==NULL){ createNewZeroNode(value); node=nodeAddress[value];/*新节点已变成zeroNode的右孩子*/ } /*若是一个zeroNode的兄弟，必须找到和它频率出现次数相同的叶节点*/ if(node->parent==zeroNode->parent){ highest=getHighestEqualLeaf(node); if(highest)/*找到最远的相等的叶子节点，交换*/ swap(node,highest); node->frequency++; node=node->parent;/*一直遍历到上层*/ } while(node!=root){ highest=getHighestEqualNode(node); if(highest)/*找到最远的相等的节点，交换*/ swap(node,highest); node->frequency++; node=node->parent;/*一直遍历到上层*/ } } void Code(listNode* node){ int i=0; char code_value[256];/*存储编码的数组*/ if(!node) return; while(node->parent){ if(node==node->parent->leftChild){ code_value[i]=0; /*左0*/ } else if(node==node->parent->rightChild){ code_value[i]=1; /*右1*/ } i++; node=node->parent; } /*把编码输出*/ while(i--) { if(code_value[i]==1) { put_ONE();/*输出1*/ } else{ put_ZERO();/*输出0*/ } } } void initOutBuf(){ outBitPointer=0; outBufCount=0; nbytesOutput=0; outBufStartAdd=outBufPointer=(unsigned char*)malloc(sizeof(char)*outBufSize); memset(outBufPointer,0,outBufSize); } void freeOutBuf(){ outBufPointer=outBufStartAdd; free(outBufPointer); } void flushOutBuf(){ if(outBufCount||outBitPointer){ fwrite(outBufStartAdd,outBufCount+(outBitPointer?1:0),1,outFile); outBufPointer=outBufStartAdd; nbytesOutput=0; memset(outBufPointer,0,outBufSize); } } void test(){ if(++outBitPointer==8){//一个byte已经满 ++outBufPointer; if(++outBufCount==outBufSize){ outBufPointer=outBufStartAdd; fwrite(outBufStartAdd,outBufSize,1,outFile); memset(outBufPointer,0,outBufSize); outBufCount=0; nbytesOutput+=outBufSize; } outBitPointer=0; } } void put_ONE(){ *outBufPointer |=(1<<outBitPointer); test(); } void put_ZERO(){ test(); } /* 放入输出流多个bit */ void put_nbits( unsigned int k, int size) { k=(k<<(32-size))>>(32-size); *outBufPointer |= (k<<(outBitPointer)); if( size >= (8-outBitPointer) ) { size -= (8-outBitPointer); k >>= (8-outBitPointer); outBitPointer=0; if(++outBufCount==outBufSize){ outBufPointer=outBufStartAdd; fwrite(outBufStartAdd,outBufSize,1,outFile); memset(outBufPointer,0,outBufSize); outBufCount=0; nbytesOutput+=outBufSize; } else outBufPointer++; if ( size ) do { *outBufPointer |= k; if ( size >= 8 ) { size -= 8; k >>= 8; if(++outBufCount==outBufSize){ outBufPointer=outBufStartAdd; fwrite(outBufStartAdd,outBufSize,1,outFile); memset(outBufPointer,0,outBufSize); outBufCount=0; nbytesOutput+=outBufSize; } else outBufPointer++; } else break; } while( 1 ); } outBitPointer+= size; }