|
t->count; left=getHfmTreeNode(*hQueue); right=getHfmTreeNode(*hQueue); hfmTreeNode *newNode=(hfmTreeNode*)malloc(sizeof(hfmTreeNode)); newNode->left=left; newNode->right=right; addQueueNode(hQueue,newNode,count); } hHfmTreeNode* tree=(hHfmTreeNode*)malloc(sizeof(hHfmTreeNode)); tree->rootNode=getHfmTreeNode(*hQueue); return tree; } hHfmTreeNode* creatTree(void) { FILE *ifile; int *countArray; char c; int i; countArray=(int*)malloc(sizeof(int)*256);//分配空间用于存储各字符出现的次数,并初始化为零 for(i=0;i<256;i++) { countArray[i]=0; } ifile=fopen("D://1.txt","r"); if(!ifile) //检查文件是否打开成功 printf("Can't open the file\n"); else { while((c=getc(ifile))!=EOF) { countArray[(unsigned int)c]++; printf("%c", c); } fclose(ifile); } hQueueNode *hQueue; initQueue(&hQueue); for(i=0;i<256;i++) { if(countArray[i]) { //printf("%c %d\n",i, countArray[i] ); hfmTreeNode *hNode=(hfmTreeNode*)malloc(sizeof(hfmTreeNode));//创建一个树节点，并初始化（用来对应队列queueNode中的ptr） hNode->symbol=(char)i; hNode->left=NULL; hNode->right=NULL; addQueueNode(&hQueue,hNode,countArray[i]);//将该节点插入队列中的适当位置（按统计的结果，从小到大排列） } } free(countArray);//释放不用的内存 queueNode* q=hQueue->first; printf("\n"); do { printf("\n%c %d",q->ptr->symbol, q->count); q=q->next; } while(q!=NULL); //printf("%d",hQueue->size); hHfmTreeNode *tree=crtHfmTree(&hQueue); return tree; } void traverseTree( hdTableNode** table, hfmTreeNode* tree, char* code, int k) { if(tree->left==NULL && tree->right==NULL) //递归结束检查，即找到叶子节点 { code[k]='\0'; //添加字符串结束标记 tableNode *tNode=(tableNode*)malloc(sizeof(tableNode)); //创建一个节点，并将其添加到table链表中 tNode->code=(char*)malloc(sizeof(char)*256+1); strcpy(tNode->code,code); tNode->symbol=tree->symbol; tNode->next=NULL; if((*table)->first==NULL) //如果是第一个节点，直接添加即可， 否则添加到尾部即可 { (*table)->first=tNode; (*table)->last=tNode; } else { (*table)->last->next=tNode; (*table)->last=tNode; } } if(tree->left!=NULL) //向左边递归，并记录编码为0 { code[k]='0'; traverseTree(table,tree->left, code, k+1); } if(tree->right!=NULL) //向右边递归，并记录编码为1 { code[k]='1'; traverseTree(table, tree->right, code, k+1); } } hdTableNode* crtTable(hHfmTreeNode* hfmTree) { hdTableNode* hdTable=(hdTableNode*)malloc(sizeof(hdTableNode)); hdTable->first=NULL; hdTable->last=NULL; char code[code_Max]; int k=0; //记录树的层级 traverseTree(&hdTable, hfmTree->rootNode, code, k); return hdTable; } int main(void) { hHfmTreeNode* tree; hdTableNode* table; printf("%s\n\n\n",title); tree=creatTree(); table=crtTable(tree); int i=0, j=0; tableNode* t=table->first; char* s=t->code; printf("\n\n*************************************************************************************\n"); printf("The Huffman code is:\n"); while(t!=NULL) { for(i=0;i<257;i++) { if((*s)!='\0') { printf("%c",*s); s++; } } printf("%8c\n",t->symbol); t=t->next; if(t) s=t->code; } }
|