Huff man (하프 만 인 코딩) 및 디 코딩 을 어떻게 실현 합 니까?

5188 단어 알고리즘
코드
[제목 설명]
통신 에 사용 할 영문 전문 을 지정 하고 이 전문 에 있 는 모든 문자 가 나타 나 는 빈 도 를 통계 하 며 주파수 왼쪽 작은 오른쪽 큰 방법 으로 이 문자 들 에 하 프 만 (Huffamn) 트 리 를 만 들 고 모든 문자 의 하 프 만 트 리 코드 를 만들어 이 전문 에 있 는 하 프 만 코드 번역문 을 출력 합 니 다.
 
【 입력 】
입력 파일 허 프 맨. in 은 통신 에 사용 되 는 영문 전문 입 니 다.
【 출력 】
출력 파일 허 프 맨. out 에서 이 전문 을 출력 하 는 하 프 만 코드 번역문.
 
[입 출력 예시 1]
huffman.in                             
huffman.out
aaccdddbacbcddddddd
011011000011101001100010001111111
【 데이터 제한 】
2 < = 영문 전문 문자 수 < = 10000000
이상 abcd 에 나타 난 개 수 를 통계 합 니 다.
a:3   b:2    c:4    d:10
하프 만 나 무 를 만들다
a:011         b:010     c  :00          d:1
다음은 주로 두 개의 구조 체 배열 을 통 해 이 루어 진다.
struct node1 { int w, lch, rch, parent; }ht[2*N0-1+1];
배열 아래 표시
1
2
3
4
5
6
7
부모 노드 의 배열 아래 parent 를 표시 합 니 다.
0
0
0
0
 
 
 
왼쪽 아이 노드 의 배열 아래 lch 를 표시 합 니 다.
0
0
0
0
 
 
 
오른쪽 아이 노드 의 배열 아래 표 시 된 rch
0
0
0
0
 
 
 
가중치
3
2
4
10
 
 
 
-》
배열 아래 표시
1
2
3
4
5
6
7
부모 노드 의 배열 아래 parent 를 표시 합 니 다.
5
5
0
0
0
 
 
왼쪽 아이 노드 의 배열 아래 lch 를 표시 합 니 다.
0
0
0
0
2
 
 
오른쪽 아이 노드 의 배열 아래 표 시 된 rch
0
0
0
0
1
 
 
가중치
3
2
4
10
5
 
 
-》.。。。。。。。。
배열 아래 표시
1
2
3
4
5
6
7
부모 노드 의 배열 아래 parent 를 표시 합 니 다.
5
5
6
7
6
7
0
왼쪽 아이 노드 의 배열 아래 lch 를 표시 합 니 다.
0
0
0
0
2
5
6
오른쪽 아이 노드 의 배열 아래 표 시 된 rch
0
0
0
0
1
3
4
가중치
3
2
4
10
5
9
19
 
struct node2 { char ch; / 대응 하 는 문자 abcd int start; / 인 코딩 의 시작 위 치 는 이 인 코딩 이 거꾸로 되 어 있 기 때문에 여 기 는 start 를 사용 합 니 다. int code [N0]; / / 이것 은 인 코딩 배열} hc [N0 + 1];
대략 그림 은 아래 와 같다.
아르 바 이 트 를 잘 못 해 요. 대충 봤 을 거 예요.
여러분 이 원 하 시 는 프로그램 을 알려 드 리 겠 습 니 다.
//#include "stdio.h"
//#include   "string.h " 
#include 
#include 
const int N0=10;
const int N=100;
const int INF=1000000;
struct node1 
{ int w, lch, rch, parent;
}ht[2*N0-1+1];
struct node2
{ char ch;
 int start;
 int code[N0];
}hc[N0+1];
int n,root;//n      
void readData()
{ char ch;
int num[256]={ 0 };
 n=0;
 freopen( "huffman.in", "r", stdin);//     
 while( (ch=getchar()) != EOF )
  num[ch]++;
 for( int i=0; i<=255; i++ )
 { if( num[i] )
  { n++;
   ht[n].w=num[i];
   hc[n].ch=i;
  }
 }
}
void select1( int t, int *s1, int *s2)//                   ,        。
{ int w1,w2;
 w1=w2=INF;
 for( int i=1; i<=t; i++ )
  if( ht[i].parent==0 )
   if( ht[i].w=0; m--)
   printf("%d", hc[j].code[m]);
  j=1;
 }
}


int main()
{ 
 readData();
 createHufTreeHuCode();
 freopen("huffman.out", "w", stdout);
 txt2code();
 return 0;
}


디 코딩
[제목 설명]
2 개의 입력 파일 을 지정 합 니 다. 첫 번 째 입력 파일 은 통신 에 사용 되 는 영문 전문 입 니 다. 이 전문 에 있 는 모든 문자 가 나타 나 는 빈 도 를 통계 하고 주파수 왼쪽 작은 오른쪽 큰 방법 으로 이 문자 들 에 하 프 만 (Huffamn) 트 리 를 만 들 고 모든 문자 의 하 프 만 트 리 코드 를 만 듭 니 다.두 번 째 입력 파일 은 첫 번 째 입력 파일 의 영문 전문 에 따라 편 성 된 하프 만 코드 로 이 하프 만 코드 에 대응 하 는 영문 전문 을 출력 한다.
 
【 입력 】
첫 번 째 입력 파일 은 Huff man. in 으로 통신 에 사용 되 는 영문 전문 이 며, 두 번 째 입력 파일 codeToTxt. in 은 첫 번 째 입력 파일 로 편 성 된 하프 만 코드 입 니 다.
【 출력 】
출력 파일 codeToTxt. out 에서 codeToTxt. in 파일 내용 의 영문 전문 을 출력 합 니 다.
 
[입 출력 예시 1]
huffman.in                            
codeToTxt.in
codeToTxt.out
aaccdddbacbcddddddd
011111011000011101001100010001111
adddaccdddbacbcdddd
【 데이터 제한 】
2 < = 영문 전문 문자 수 < = 10000000
 
#include 
#include 
const int N0=10;
const int N=100;
const int INF=1000000;
struct node1 
{ int w, lch, rch, parent;
}ht[2*N0-1+1];
struct node2
{ char ch;
 int start;
 int code[N0];
}hc[N0+1];
int n,root,num[256];
void readData()
{ char ch;

 n=0;
 freopen( "huffman.in", "r", stdin);
 while( (ch=getchar()) != EOF )
  num[ch]++;//         ,     ,     
 for( int i=0; i<=255; i++ )
 { if( num[i] )
  { n++;
   ht[n].w=num[i];//  
   hc[n].ch=i;//  
  }
 }
}
void select1( int t, int *s1, int *s2)
{ int w1,w2;
 w1=w2=INF;
 for( int i=1; i<=t; i++ )
  if( ht[i].parent==0 )
   if( ht[i].w

좋은 웹페이지 즐겨찾기