데이터 구조 Huffman 인 코딩 디 코딩
5400 단어 프로그램 소스 코드
1.1 문제 설명
• 문제 설명: 하프 만 인 코딩 을 이용 하여 통신 을 하면 채널 이 용 률 을 크게 높 일 수 있 고 정보 전송 시간 을 단축 시 켜 전송 원 가 를 낮 출 수 있다.그러나 이 는 송신 단 에서 하나의 인 코딩 시스템 을 통 해 전 송 된 데 이 터 를 미리 인 코딩 하고 수신 단 에서 전 송 된 데 이 터 를 디 코딩 (디 코딩) 해 야 한다.양 방향 채널 (즉, 양 방향 으로 정 보 를 전송 할 수 있 는 채널) 에 대해 모든 엔 드 는 완전한 편집 / 디 코딩 시스템 이 필요 하 다.이러한 정보 송 수신 소 를 위해 하 프 만 컴 파일 코드 시스템 을 설계 해 보 세 요.
1.2 기본 요구 사항
(1) 입력 의 형식 과 입력 값 의 범위;
(2) 출력 형식;
(3) 프로그램 이 달성 할 수 있 는 기능.
1. 기본 요구
(1) 초기 화 (Initialzation).데이터 파일 DataFile. data 에서 문자 와 모든 문자 의 가중치 를 읽 고 하프 만 트 리 HuffTree 를 만 듭 니 다.
(2) 인 코딩 (EnCoding).만들어 진 하프 만 트 리 로 파일 ToBeTran. data 의 텍스트 를 인 코딩 하여 메 시 지 를 만 들 고 메 시 지 를 파일 Code. txt 에 쓰기;
(3) 디 코딩 (Decoding).만들어 진 하프 만 트 리 를 이용 하여 파일 CodeFile. data 의 코드 를 디 코딩 하여 원문 을 만 든 결과 파일 Textfile. txt 에 저장 합 니 다.
(4) 출력 (Output).DataFile. data 에 나타 난 문자 와 각 문자 가 나타 나 는 빈도 (또는 확률) 를 출력 합 니 다.ToBeTran. data 와 그 메시지 Code. txt 를 출력 합 니 다.CodeFile. data 와 그 원문 Textfile. txt 를 출력 합 니 다.
2. 개요 설계
이 프로그램 에서 사용 하 는 모든 추상 적 인 데이터 형식의 정 의 를 설명 합 니 다.주 프로그램의 절차 와 각 프로그램 모듈 간 의 차원 (호출) 관계.
(1) 데이터 구조
하프 만 나무의 노드
struct huff
{
intweight;
intparent;
intl;
intr;
};
하프 만 인 코딩 저장 소
struct huff *hufftree;
(2) 프로그램 모듈
1 부터 i - 1 까지 parent 가 0 이 고 가중치 가 가장 작은 두 개의 하 표를 선택 하 십시오.
void Select(struct huff *HT, int n, int&s1, int &s2)
하프 만 트 리 구축:
void huffmancoding(struct huff *ht,int *w,intn)
원문 인 코딩:
void code(char *c)
메시지 에 따라 원문 찾기:
void decoding(char *zifu)
3. 상세 설계
핵심 기술 분석:
1: 하프 만 트 리 구축 및 하프 만 인 코딩 생 성:
모든 문자 의 가중치 에 따라 최 적 화 된 이 진 트 리 의 구축 방법 에 따라 하 프 만 트 리 를 재 귀적 으로 생 성하 고 하 프 만 트 리 를 배열 로 저장 합 니 다.
모든 잎 노드 에서 나무 뿌리 를 옮 겨 다 니 며 인 코딩 을 구하 십시오.
예 를 들 면:
그림 에서 보 듯 이 네 개의 노드 v1, v2, v3, v4 는 그들의 가중치 가 각각 7, 11, 4, 5 이다.
7 11 4 5
첫 번 째 단계: 두 개의 가중치 가 가장 작은 노드 를 좌우 자식 으로 선택 하고 이 진 트 리 를 만 듭 니 다. 부모 의 가중치 는 두 아이의 합 입 니 다. 그림 과 같 습 니 다.
7 11 9
첫 번 째 단계 반복:
11 16
27
첫 번 째 단계 반복:
16
이때 만들어 진 것 은 이 진 트 리 입 니 다. 왼쪽 트 리 의 인 코딩 을 1 로 정 하고 오른쪽 트 리 의 인 코딩 을 0 으로 정 하면 이 진 트 리 를 인 코딩 할 수 있 습 니 다. 그림 과 같 습 니 다.
1 0
1 0
1 0
각 정점 의 인 코딩 은:
V1 01
V2 1
V3 001
V4 000
2: 원문 인 코딩:
파일 에서 문 자 를 하나씩 읽 고 만들어 진 하 프 만 트 리 에 따라 모든 문자 에 해당 하 는 인 코딩 을 찾 습 니 다.
3: 메시지 디 코딩:
단계 1:
일치 하 는 문자열 을 먼저 읽 고 저장 합 니 다.
단계 2:
일치 하 는 문자열 에 따라 모든 하프 만 인 코딩 을 찾 습 니 다. 해당 하 는 인 코딩 을 찾 으 면 해당 하 는 문 자 를 입력 하 십시오. 찾 지 못 하면 두 문 자 를 읽 고 일치 하 는 문자열 에 저장 하고 두 번 째 단 계 를 반복 합 니 다. 찾 을 때 까지.
단계 3:
나머지 문 자 를 반복 합 니 다. 하나, 둘.
#include
#include
#include
struct huff
{
int weight;
int parent;
int l;
int r;
};
int mm;/* */
struct huff *hufftree;
char **huffmancode;
void Select(struct huff *HT, int n, int &s1, int &s2)// ， parent ，
{
int min1=100;
int min2=100;
int i;
for(i=1;i<=n;i++)
if((min1>HT[i].weight)&&(HT[i].parent==0))
min1=HT[i].weight;
for(i=1;i<=n;i++)
if((min1==HT[i].weight)&&(HT[i].parent==0))
{
s1=i;
break;
}
for(i=1;i<=n;i++)
if((min2>HT[i].weight)&&(HT[i].parent==0)&&(i!=s1))
min2=HT[i].weight;
for(i=1;i<=n;i++)
if((min2==HT[i].weight)&&(HT[i].parent==0)&&(i!=s1))
{
s2=i;
break;
}
}
int pipei(char *c)/* huffmancode */
{
int i;
for(i=1;iweight=*w;
p->parent=0;
p->l=0;
p->r=0;
}
for(;i<=m;i++,p++)
{
p->l=0;
p->weight=0;
p->parent=0;
p->r=0;
}
for(i=1;i<=4;i++)
for(i=n+1;i<=m;i++)
{
int s1,s2;
Select(ht,i-1,s1,s2);
ht[s1].parent=i;
ht[s2].parent=i;
ht[i].l=s1;
ht[i].r=s2;
ht[i].weight=ht[s1].weight+ht[s2].weight;
}
char *cd;
cd=(char *)malloc(n*sizeof(char));
cd[n-1]='\0';
int start,c,f;
for(i=1;i<=n;++i)
{
start=n-1;
for(c=i,f=ht[i].parent;f!=0;c=f,f=ht[f].parent)
if(ht[f].l==c)
cd[--start]='0';
else
cd[--start]='1';
huffmancode[i]=(char *)malloc((n-start)*sizeof(char));
strcpy(huffmancode[i],&cd[start]);
}
free(cd);
}
좋은 웹페이지 즐겨찾기
