e bị xuất kí tự thì bị mất 1 kí tự cuối có bác nào chỉ e fix được ko ạ
Source Code :
#include <stdio.h>
#include <windows.h>
#pragma GCC diagnostic ignored "-Wwrite-strings"
struct NODE {
unsigned char c ;
int freq ;
bool used ;
int nLeft ;
int nRight ;
} ;
struct MABIT {
char * bits ;
int soBit ;
} ;
const int MAX_NODE = 256*9 ;
const int MAX_BIT_LEN = 10000 ;
NODE huffTree [MAX_NODE] ;
MABIT bangMaBit [256] ;
void KhoiTao ( ){
for (int i = 0 ; i < MAX_NODE; i++) {
huffTree[i].c = i ;
huffTree [i].freq = 0 ;
huffTree[i].used = false;
huffTree[i].nLeft = - 1 ;
huffTree[i].nRight = - 1 ;
}
}
void ThongKeTanSoXuatHien(char*tenFile){
FILE*fi = fopen (tenFile ,"rt") ;
unsigned char c ;
while (1){
fscanf (fi,"%c",&c );
if (feof(fi)){
break ;
}
huffTree[c].freq++;
}
fclose(fi);
}
void XuatBangThongKe( ){
printf("Bang thong ke tan suat: \n") ;
for(int i = 0; i < 256; i++){
if(huffTree[i].freq > 0){
printf("%c:%d\n",i,huffTree[i].freq);
}
}
}
void XuatBanThongKe(){
printf("Bang thong ke tan suat: \n");
for (int i = 0; i < 256; i++){
if (huffTree[i].freq > 0){
printf("%c: %d\n",i, huffTree[i].freq);
}
}
}
bool Tim2PhanTuMin(int &i, int &j, int nNode) {
i = -1;
j = -1;
for (int k = 0; k < nNode; k++)
if (huffTree[k].used == false && huffTree[k].freq >0){
if (i == -1){
i = k;
}
else if (j == -1){
j = k;
}
else{
if (huffTree[i].freq > huffTree[j].freq){
if (huffTree[k].freq < huffTree[i].freq){
i = k;
}
}
else{
if (huffTree[k].freq < huffTree[j].freq){
j = k;
}
}
}
}
if (i!= -1 && j!= -1){
if ((huffTree[i].freq > huffTree[j].freq) || ((huffTree[i].freq > huffTree[j].freq) && (huffTree[i].c > huffTree[j].c))){
int t = i;
i = j;
j = t;
}
return true;
}
else {
return false;
}
}
int TaoCayHuffman( ) {https://daynhauhoc.s3-ap-southeast-1.amazonaws.com/original/3X/a/2/a2a6804ec37562e063d7b13a85dd608a016663b9.png
int nNODE = 256 ;
int i , j ;
bool timthay = false ;
while ( true ) {
timthay = Tim2PhanTuMin( i , j , nNODE ) ;
if (!timthay) {
break ;
}
huffTree[nNODE].c = (huffTree[i].c < huffTree[j].c) ? huffTree[i].c : huffTree [j].c ;
huffTree[nNODE].freq = huffTree[i].freq + huffTree[j].freq ;
huffTree[nNODE]. nLeft = i ;
huffTree[nNODE]. nRight = j ;
huffTree[i].used = true ;
huffTree[j].used = true ;
huffTree[nNODE].used = false ;
nNODE++;
}
return nNODE -1 ;
}
void XuatCayHuffman ( int node , int tab ) {
if ( node == -1 ) {
return ;
}
for ( int i = 0 ; i<tab;i++ ) {
printf ("\t") ;
}
if (huffTree[node].nLeft == - 1 && huffTree[node].nRight == -1 ) {
printf("%c\n" , huffTree[node].c)
;
}
else {
printf("%c..\n", huffTree[node].c ) ;
XuatCayHuffman(huffTree[node].nLeft, tab + 1 ) ;
XuatCayHuffman(huffTree[node].nRight, tab + 1 ) ;
}
}
void DuyetCayHuffman (int node, char maBit [ ] , int nMaBit ) {
if (node == -1 ) {
return ;
}
if (huffTree[node].nLeft == -1 && huffTree[node].nRight == -1 ) {
bangMaBit [node].soBit = nMaBit;
bangMaBit [node].bits = new char [nMaBit] ;
for ( int i = 0 ; i < nMaBit; i++) {
bangMaBit[node].bits[i]= maBit[i] ;
}
return ;
}
else {
maBit[nMaBit] = 0 ;
DuyetCayHuffman(huffTree[node].nLeft, maBit , nMaBit + 1) ;
maBit [ nMaBit ] = 1 ;
DuyetCayHuffman(huffTree[node].nRight, maBit , nMaBit + 1 ) ;
}
}
void PhatSinhMaBit( int nRoot ) {
for ( int i = 0 ; i < 256 ; i++ ) {
bangMaBit[i].soBit=0 ;
bangMaBit[i].bits =NULL ;
} ;
char maBit[MAX_BIT_LEN/8] ;
int nMaBit = 0 ;
DuyetCayHuffman(nRoot, maBit, nMaBit) ;
}
void XuatBangMaBit () {
for (int i = 0 ; i < 256 ; i++ )
if (bangMaBit[i].soBit>0 ) {
printf("%c:", i ) ;
for (int j = 0; j < bangMaBit[i].soBit;j ++ )
printf("%d", bangMaBit[i].bits[j]);
printf("\n" );
}
}
void XuatByte ( unsigned char out , int soBitCoNghia ) {
for (int i = 7; i > 7 - soBitCoNghia +1 ; i--) {
if ( ( out >> i ) & 1 ) {
printf ( "1" ) ;
}
else {
printf( "0" ) ;
}
}
printf ( "" ) ;
}
```
void MaHoa1KyTu ( unsigned char c , unsigned char & out , unsigned char & viTriBit) {
for (int i = 0 ; i < bangMaBit[c].soBit; i++ ) {
if ( bangMaBit[c].bits[i] == 1 ) {
out = out | ( 1 << viTriBit ) ;
}
if (viTriBit == 0 ) {
viTriBit = 7 ;
XuatByte( out, 8 ) ;
out = 0 ;
}
else {
viTriBit -- ;
}
}
}
void NenHuffman( char*inputFile ) {
//buoc 1: thong ke tuan so xuat hien
KhoiTao ( ) ;
ThongKeTanSoXuatHien (inputFile ) ;
XuatBangThongKe ( ) ;
//buoc 2: tao cay huffman
int nRoot = TaoCayHuffman () ;
XuatCayHuffman(nRoot, 0 ) ;
//buoc 3 : phat sinh mabit
PhatSinhMaBit( nRoot ) ;
XuatBangMaBit ( ) ;
//buoc 4: thay ki tu bang mabit
unsigned char out = 0 ;
unsigned char soBitCoNghia = 0 ;
unsigned char c ;
unsigned char viTriBit = 7 ;
FILE*fi = fopen(inputFile," rt " ) ;
while ( true ) {
fscanf ( fi , " %c " , & c ) ;
if (feof ( fi ) ) {
break ;
}
MaHoa1KyTu( c , out , viTriBit ) ;
}
soBitCoNghia = 7 - viTriBit ;
if ( soBitCoNghia == 0 ) {
soBitCoNghia = 8 ;
}
else {
XuatByte ( out , soBitCoNghia ) ;
}
fclose (fi) ;
}
```
int main (){
NenHuffman ("input.txt");
}