하프 만 트 리

시간 제한: 1000 MS 코드 길이 제한: 10KB
문제 유형: 프로 그래 밍 문제 언어: G +;GCC Description 정적 링크 를 이용 하여 헤 프 만 트 리 를 만 듭 니 다. 트 리 를 만 드 는 과정 에서 왼쪽 트 리 의 가중치 가 오른쪽 트 리 의 가중치 보다 적 고 각 노드 의 인 코딩 을 구 해 야 합 니 다.요구: 잎 결점 의 개수 n 및 결점 값 은 키보드 로 입력 합 니 다.이 문 제 는 테스트 요 구 를 충족 시 키 기 위해 프로그램 코드 를 보 여 줍 니 다. \ # include "stdio. h" \ # include "malloc. h" \ # include "string. h" typedef struct {unsigned int weight; unsigned int parent, lchild, rchild;} HTNode, * HuffmanTree;typedef char **HuffmanCode; void Select (HuffmanTree & HT, int n, int & s1, int & s2) / / HT [1... n] 에서 parent 를 0 으로 선택 하고 weight 가 가장 작은 두 개의 결점 을 선택 하 십시오. / / 그 번 호 는 각각 s1 과 s2 입 니 다.int i; s1 = - 1; s2 = - 1; for (i = 1; i < = n; i + + +) {if (HTi]. parent = 0) if (s1= = - 1) s1= - 1; i; i = 1; i = i = 1; i < = n; i + + + +) {if (HT[i]. parent = 0) if (s1= - 1) s1= - i; elsif (s2 = = = = - 1) = - i; elsif (s2 = = - 1) if (HTTP = i = - 1). if (HTi]. weight 0), 구조 하프 만 트 리 HT, / / / n 문자 의 하프 만 인 코딩 HC int i, j, m, m, s1, s1, s1, s1, s1, s2, s2, start; char * (HuffmanTree) malloc (m + 1) * size of (HTNode); / / / 0 번 셀 이 사용 되 지 않 았 습 니 다 (i = 1; i < = n; i + + +) {/ / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # printf ("HT 초기 상태: 결점 weight parent lchild rchild"); for(i = 1; i < = m; i + +) printf ("% 4d% 8d% 8d% 8d% 8d% 8d% 8d% 8d% 8d% 8d% 8d% 8d", i, i, i < < < = m; i + + +) printf ("임의의 키 를 누 르 고 계속..."); getch (); for (i = n + 1; i < < = m; i + + +) {/ / / / 하프 만 트 리 만 들 기 / / / / / / / / /..... i - 1] 에서 parent 가 0 이 고, weight 가 가장 작은 두 노드 를 선택 하 십시오. / / / / / / 번 호 는 각각 s11 과 s1 과 s2 입 니 다. Select 를 선택 하 십시오. Select 2. Select 2. Select(HT, i - 1, s1, s2); HT [s1]. parent = i; HT [s2]. parent = i; HT[i]. lchild = s1; HTi]. rchild = s2; HT[]. weight = HTTP [s1]. weight + HT[s2]. weight + HTML [s2]. weight; printf ("select: s1=% d s2 =% d s2 =% d =% d", s1, s2); printf ("결산 점 weint lchild rchild"); for (j = 1; j < < = i; j < = i; j + + + +) printf ("% 4d% 8d% 8d% 8d% 8d% 8d% 8d", j, HTML [j]. weight]. weight, HT[j]. parent, HT. parent. parent.. parent...... [j]. lchild, HT [j]. rchild); printf ("임의의 키 를 누 르 고 계속..."); getch ();}/ - 잎 에서 뿌리 까지 모든 문자 의 하프 만 인 코딩 - cd = (char) malloc (nsizeof (char); / 인 코딩 을 위 한 작업 공간 cd [n - 1] = '\ 0'; / 인 코딩 끝 문자. for (i = 1; i < = n; + i) {/ / 한 글자 씩 하프 만 인 코딩 start = n - 1; / 인 코딩 끝 문자 위치 for (c = i, f = HT [f]. parent)/ / 잎 에서 뿌리 까지 역방향 으로 인 코딩 if (HT [f]. lchild = = c) cd [– start] = '0', else cd [– start] = '1', HC [i] = (char *) malloc ((n - start) * sizeof (char)), / / i 번 째 문자 인 코딩 에 공간 strcpy (HC [i], & cd [start]), / cd 복사 인 코딩 (꼬치) 에서 HC 까지
} free (cd); / / 작업 공간 방출} / HuffmanCoding
void main () {int i, n; int * w; HuffmanTree HT; HuffmanCode HC; printf ("Node Number:"); scanf ("% d", & n); / / 가중치 개수 w = (int) malloc (nsizeof (int)); printf ("입력 가중치:"); for (i = 0; i scanf ("% d", & w [i]);
HC = (char * *) malloc (n + 1) sizeof (char); / 0 공간 은 HT = (HuffmanTree) malloc ((2 * n + 1 + 1) * sizeof (HTNode) 를 사용 하지 않 습 니 다. / 0 공간 은 HuffmanCoding (HT, HC, w, n) 을 사용 하지 않 습 니 다. printf ("); for (i = 1; i puts (HC [i]); / 출력 하프 만 인 코딩 free (HC [i]); / / / 방출 공간} free (HC); free (HT);} / main
입력 형식 첫 줄: 가중치 개수 두 번 째 줄: n 개의 가중치 를 입력 하고 빈 칸 으로 구분 합 니 다.
출력 형식 출력 n 줄 마다 가중치 에 대응 하 는 하프 만 인 코딩 을 표시 합 니 다.
입력 샘플 8 5 29 7 8 14 23 11
출력 샘플 0001 10 1110 1111 110 01 0000 001
문제 풀이 방향: 구조 하프 만 트 리 --- 하프 만 코딩
코드 는 다음 과 같 습 니 다. (새 교재 표지)

#include 
#include 
using namespace std;
typedef struct //     
{
     
	int weight;
	int parent,lchild,rchild;
}HTNode,*HuffmanTree;

typedef char **HuffmanCode;
void Selete(HuffmanTree HT,int len,int &s1,int &s2);

void CreateHuffmanTree(HuffmanTree &HT,int n)
{
     //       
	int i,s1,s2;
	if(n<=1) return;
	int m=2*n-1;
	HT=new HTNode[m+1];
	for(i=1;i<=m;i++)
	{
     
		HT[i].parent=0;
		HT[i].lchild=0;
		HT[i].rchild=0;
	}
	for(i=1;i<=n;i++)
	{
     
		cin>>HT[i].weight;
	}
	for(i=n+1;i<=m;i++)
	{
     
		Selete(HT,i-1,s1,s2);
		HT[s1].parent=i;
		HT[s2].parent=i;
		HT[i].lchild=s1;
		HT[i].rchild=s2;
		HT[i].weight=HT[s1].weight+HT[s2].weight;
	}
}

void Selete(HuffmanTree HT,int len,int &s1,int &s2)
{
     
	int i,min1=0x3f3f3f3f,min2=0x3f3f3f3f;//      
	for(i=1;i<=len;i++)
	{
     
		if(HT[i].weight<min1&&HT[i].parent==0)
		{
     
			min1=HT[i].weight;
			s1=i;
		}
	}
	int temp=HT[s1].weight;//       ，       ，  s1      
	HT[s1].weight=0x3f3f3f3f;
	for(i=1;i<=len;i++)
	{
     
		if(HT[i].weight<min2&&HT[i].parent==0)
		{
     
			min2=HT[i].weight;
			s2=i;
		}
	}
	HT[s1].weight=temp;
}

void CreateHuffmanCode(HuffmanTree HT,HuffmanCode &HC,int n)
{
     
	int i,start,c,f; 
	char *cd;
	HC=new char *[n+1];//    n            
	cd=new char[n];//                   
	cd[n-1]='\0';//     
	for(i=1;i<=n;i++)//           
	{
     
		start=n-1;//start       ，         
		c=i;
		f=HT[i].parent;//f  c      
		while(f!=0)
		{
     
			--start;
			if(HT[f].lchild==c) cd[start]='0';
			else cd[start]='1';
			c=f;
			f=HT[f].parent;
		}
		HC[i]=new char[n-start];//  i          
		strcpy(HC[i],&cd[start]);
	}
	delete cd;
}

int main()
{
     
	int n,i;
	HuffmanTree HT;
	HuffmanCode HC;
	cin>>n;
	CreateHuffmanTree(HT,n);
	CreateHuffmanCode(HT,HC,n);
	for(i=1;i<=n;i++) cout<<HC[i]<<endl;
}