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
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
【Codility Lesson3】FrogJmpA small frog wants to get to the other side of the road. The frog is currently located at position X and wants to get to...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.