C 언어 로 호 프 만 트 리 데이터 구 조 를 자세히 설명 합 니 다.
a.경로 와 경로 길이
한 나무 에 하나의 결점 서열 k1,k2,...,kj 가 존재 한다 면 ki 는 ki+1 의 부모(1<=i
b.노드 의 권리 와 밴드 경로 의 길이
많은 응용 에서 나무의 결점 을 특정한 의 미 를 가 진 실 수 를 부여 한다.우 리 는 이 실 수 를 이 결점 의 권 이 라 고 부른다.(예 를 들 어 다음 나무의 파란색 숫자 는 결점 의 권 리 를 나타 낸다)
결점 의 대 권 경로 길 이 는 나무 뿌리 결점 에서 이 결점 사이 의 경로 길이 와 이 결점 상권 의 곱셈 으로 규정 된다.
c.나무의 대역 권 경로 길이
나무의 대역 권 경로 길 이 는 나무의 모든 잎 결점 의 대역 권 경로 길이 의 합 으로 정의 되 고 공식 은 다음 과 같다.
그 중에서 n 은 잎 결점 의 수 를 나타 내 고 wi 와 li 는 잎 결점 ki 의 가중치 와 나무 뿌리 결점 에서 ki 사이 의 경로 길 이 를 나타 낸다.
아래 그림 에서 트 리 의 대역 권 경로 길이 WPL=9 x 2+12 x 2+15 x 2+6 x 3+3 x 4+5 x 4 = 122
d.하프 만 나무
하프 만 나 무 는 가장 좋 은 이 진 트 리 라 고도 부른다.이것 은 n 개의 잎 사 귀 결점 으로 구 성 된 모든 이 진 트 리 중 권한 경로 길이 가 WPL 에서 가장 작은 이 진 트 리 입 니 다.
아래 그림 과 같이 하프 만 나무 설명도 입 니 다.
2.구조 하프 만 나무
n 개의 가중치 가 있다 고 가정 하면 구 조 된 하 프 만 나 무 는 n 개의 잎 결점 이 있다.n 개의 가중치 가 각각 w1,w2,...,wn 으로 설정 되면 하 프 만 나무의 구조 규칙 은 다음 과 같다.
(1)w1,w2,...,wn 을 n 그루 의 나무 가 있 는 숲 으로 본다.
(2)숲 에서 두 개의 노드 의 가중치 가 가장 작은 나 무 를 선택 하여 합 쳐 새 나무의 왼쪽,오른쪽 나무 로 하고 새 나무의 뿌리 결산 점 의 가중치 는 왼쪽,오른쪽 나무 뿌리 결산 점 의 가중치 의 합 이다.
(3)숲 에서 선택 한 나무 두 그루 를 삭제 하고 새 나 무 를 숲 에 넣는다.
(4)반복(2),(3)보 는 숲 속 에 나무 한 그루 만 남 을 때 까지 이 나 무 는 바로 구 하 는 하프 만 나무 이다.
예 를 들 어 다음 그림 의 여섯 개의 대 권 엽 결점 에 대해 하프 만 나 무 를 구성 하 는데 절 차 는 다음 과 같다.
주의:얻 은 하프 만 나무의 구 조 를 가능 한 한 유일 하 게 하기 위해 일반적으로 규정된 하프 만 나무의 각 결점 의 왼쪽 뿌리 결점 의 권 리 는 오른쪽 뿌리 결점 과 같은 권 리 를 가진다.
구체 적 인 알고리즘 은 다음 과 같다.
//2、 a n ，
struct BTreeNode* CreateHuffman(ElemType a[], int n)
{
int i, j;
struct BTreeNode **b, *q;
b = malloc(n*sizeof(struct BTreeNode));
for (i = 0; i < n; i++) // b ， a
{
b[i] = malloc(sizeof(struct BTreeNode));
b[i]->data = a[i];
b[i]->left = b[i]->right = NULL;
}
for (i = 1; i < n; i++)// n-1
{
//k1 ，k2
int k1 = -1, k2;
for (j = 0; j < n; j++)// k1 ，k2
{
if (b[j] != NULL && k1 == -1)
{
k1 = j;
continue;
}
if (b[j] != NULL)
{
k2 = j;
break;
}
}
for (j = k2; j < n; j++)//
{
if (b[j] != NULL)
{
if (b[j]->data < b[k1]->data)
{
k2 = k1;
k1 = j;
}
else if (b[j]->data < b[k2]->data)
k2 = j;
}
}
// ，q
q = malloc(sizeof(struct BTreeNode));
q->data = b[k1]->data + b[k2]->data;
q->left = b[k1];
q->right = b[k2];
b[k1] = q;// b k1
b[k2] = NULL;//k2
}
free(b); // b
return q; //
}
전신 통신 에서 전문 은 2 진법 의 0,1 서열 로 전송 되 고 모든 문 자 는 2 진법 인 코딩 에 대응 하 며 전문 의 총 길 이 를 단축 시 키 기 위해 부 등장 인 코딩 방식 으로 하프 만 트 리 를 구성한다.
각 문자 의 출현 빈 도 를 문자 결점 의 값 으로 잎 결점 을 부여 하고,각 지점 의 좌우 지점 은 각각 0 과 1 로 인 코딩 하여,나무 뿌리 결점 에서 각 잎 결점 의 경로 로 한다.
분기 의 0,1 인 코딩 서열 은 이 잎 결점 의 바 이 너 리 인 코딩 과 같다.위의 글 에서 보 듯 이 하 프 만 인 코딩 은 다음 과 같다.
a 의 인 코딩:00
b 의 인 코딩:01
c 인 코딩:100
d 인 코딩:1010
e 의 인 코딩:1011
f 의 인 코딩:11
4.하 프 만 나무의 조작 연산
위의 하 프 만 트 리 를 구체 적 인 사례 로 하여 하 프 만 트 리 의 조작 연산 을 상세 한 프로그램 으로 보 여 줍 니 다.
#include<stdio.h>
#include<stdlib.h>
typedef int ElemType;
struct BTreeNode
{
ElemType data;
struct BTreeNode* left;
struct BTreeNode* right;
};
//1、 ， 。 ， int
void PrintBTree_int(struct BTreeNode* BT)
{
if (BT != NULL)
{
printf("%d", BT->data); //
if (BT->left != NULL || BT->right != NULL)
{
printf("(");
PrintBTree_int(BT->left); //
if (BT->right != NULL)
printf(",");
PrintBTree_int(BT->right); //
printf(")");
}
}
}
//2、 a n ，
struct BTreeNode* CreateHuffman(ElemType a[], int n)
{
int i, j;
struct BTreeNode **b, *q;
b = malloc(n*sizeof(struct BTreeNode));
for (i = 0; i < n; i++) // b ， a
{
b[i] = malloc(sizeof(struct BTreeNode));
b[i]->data = a[i];
b[i]->left = b[i]->right = NULL;
}
for (i = 1; i < n; i++)// n-1
{
//k1 ，k2
int k1 = -1, k2;
for (j = 0; j < n; j++)// k1 ，k2
{
if (b[j] != NULL && k1 == -1)
{
k1 = j;
continue;
}
if (b[j] != NULL)
{
k2 = j;
break;
}
}
for (j = k2; j < n; j++)//
{
if (b[j] != NULL)
{
if (b[j]->data < b[k1]->data)
{
k2 = k1;
k1 = j;
}
else if (b[j]->data < b[k2]->data)
k2 = j;
}
}
// ，q
q = malloc(sizeof(struct BTreeNode));
q->data = b[k1]->data + b[k2]->data;
q->left = b[k1];
q->right = b[k2];
b[k1] = q;// b k1
b[k2] = NULL;//k2
}
free(b); // b
return q; //
}
//3、
ElemType WeightPathLength(struct BTreeNode* FBT, int len)//len 0
{
if (FBT == NULL) // 0
return 0;
else
{
if (FBT->left == NULL && FBT->right == NULL)//
return FBT->data * len;
else // ， ， ，len
return WeightPathLength(FBT->left,len+1)+WeightPathLength(FBT->right,len+1);
}
}
//4、 （ ）
void HuffManCoding(struct BTreeNode* FBT, int len)//len 0
{
static int a[10];// a， ，
if (FBT != NULL)// a 0 1
{
if (FBT->left == NULL && FBT->right == NULL)
{
int i;
printf(" %d ：", FBT->data);
for (i = 0; i < len; i++)
printf("%d", a[i]);
printf("
");
}
else// ， 0、1 a
{ // ， len 1
a[len] = 0;
HuffManCoding(FBT->left, len + 1);
a[len] = 1;
HuffManCoding(FBT->right, len + 1);
}
}
}
//
void main()
{
int n, i;
ElemType* a;
struct BTreeNode* fbt;
printf(" n：");
while(1)
{
scanf("%d", &n);
if (n > 1)
break;
else
printf(" n ：");
}
a = malloc(n*sizeof(ElemType));
printf(" %d ：", n);
for (i = 0; i < n; i++)
scanf(" %d", &a[i]);
fbt = CreateHuffman(a, n);
printf(" ：");
PrintBTree_int(fbt);
printf("
");
printf(" ：");
printf("%d
", WeightPathLength(fbt, 0));
printf(" ：
");
HuffManCoding(fbt, 0);
}
다음은 ACM 문 제 를 보도 록 하 겠 습 니 다.
제목 설명:
하프 만 트 리,첫 줄 에 n 을 입력 하여 잎 결점 의 개 수 를 표시 합 니 다.이 잎 결점 으로 하프 만 나 무 를 생 성 해 야 한다.하프 만 나무의 개념 에 따 르 면 이 결점 들 은 권한 이 있다.즉,weight 이다.제목 은 모든 결점 의 값 과 권한 의 곱셈 의 합 을 출력 해 야 한다.
입력:
여러 그룹의 데 이 터 를 입력 하 십시오.
각 조 의 첫 번 째 줄 에 n 개의 수 를 입력 한 다음 에 n 개의 잎 노드(잎 노드 의 가중치 가 100 을 초과 하지 않 고 2<=n<=1000)를 입력 합 니 다.
출력:
출력 값.
샘플 입력:
5
1 2 2 5 9
샘플 출력:
37
ac 코드
링크 구축 하프 만 트 리(정렬 삽입)
#include <stdio.h>
#include <stdlib.h>
#define max 1001
struct htree
{
int weight;
struct htree *lchild;
struct htree *rchild;
struct htree *next;
};
void addNode(struct htree *, struct htree *);
struct htree* createHfmtree(int *, int);
int getWpl(struct htree *, int);
int main()
{
int w[max];
int i, n, wpl;
struct htree *ht;
while(scanf("%d", &n) != EOF)
{
for(i = 0; i < n; i ++)
{
scanf("%d", &w[i]);
}
ht = createHfmtree(w, n);
wpl = getWpl(ht, 0);
printf("%d
", wpl);
}
return 0;
}
struct htree* createHfmtree(int *w, int n)
{
int i;
struct htree *head, *pl, *pr, *proot;
head = (struct htree *)malloc(sizeof(struct htree));
head->next = NULL;
for(i = 0; i < n; i ++)
{
struct htree *pnode = malloc(sizeof(struct htree));
pnode->weight = *(w + i);
pnode->lchild = pnode->rchild = pnode->next = NULL;
addNode(head, pnode);
}
while(head->next)
{
if(head->next->next == NULL)
break;
pl = head->next;
pr = pl->next;
head->next = pr->next;
proot = (struct htree *)malloc(sizeof(struct htree));
proot->weight = pl->weight + pr->weight;
proot->lchild = pl;
proot->rchild = pr;
addNode(head, proot);
}
return head->next;
}
void addNode(struct htree *head, struct htree *pnode)
{
struct htree *t = head;
while(t->next && t->next->weight < pnode->weight)
t = t->next;
pnode->next = t->next;
t->next = pnode;
}
int getWpl(struct htree *ht, int level)
{
if(ht == NULL)
return 0;
if(!ht->lchild && !ht->rchild)
{
return ht->weight * level;
}
return getWpl(ht->lchild, level + 1) + getWpl(ht->rchild, level + 1);
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
C 언어 구현 천둥 제거 게임 상세 정보먼저 작은 메뉴를 표시하고 게임을 할지 여부를 선택하십시오.사용자가 종료를 선택하면 프로그램 실행이 끝나고, 사용자가 게임을 선택하면 지뢰 제거 위치 좌표를 입력하라는 메시지가 표시됩니다.사용자가 입력한 좌표가 바둑...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
