Добро пожаловать, гость
:: алгоритмы  и методы :: :: олимпиадные задачи :: :: связь :: :: о сайте :: :: форум ::

Форум работает в режиме архива, только для чтения и поиска.
Архив 2004 Архив 2007 Архив 2013

 
 
Опции темы Поиск в этой теме Опции просмотра
  #1  
Старый 20.11.2009, 20:23
Новичок

Отправить личное сообщение для BaSoff Посмотреть профиль Найти все сообщения от BaSoff
 
Регистрация: 20.11.2009
Сообщений: 1

алгоритм Хаффмана
всё знаю насчет теории... реализовать не могу... деревья - не мое... если кто может... поделитесь полезной инфой...)
  #2  
Старый 20.11.2009, 23:58
гость

 
Сообщений: n/a

гугл и яндекс - твои лучшие друзья в этом деле!
  #3  
Старый 13.04.2010, 06:05
MBo MBo вне форума
Местный

Отправить личное сообщение для MBo Посмотреть профиль Найти все сообщения от MBo
 
Регистрация: 21.09.2006
Адрес: Новосибирск
Сообщений: 1,374

http://algolist.ru/compress/standard/huffman.php
  #4  
Старый 14.12.2010, 20:24
Lcrypto

 
Сообщений: n/a

Хаффман (статический вариант)
hf.h
#include <string.h>
#include <stdlib.h>
typedef struct node node;
typedef char type;
typedef node *tree;

struct node {
int w;
type val;
node *left, *right;
};

typedef struct qnode qnode;
typedef tree qtype;
typedef struct {
qnode *front;
qnode *rear;
} queue;

struct qnode {
qtype op;
qnode *next;
};

bool qEmpty( queue *q ) {
return (q->front == NULL);
}

void qPushBack( queue *q, qtype op ) {
/*
* pushes op at q.rear.
*/
qnode *ptr = (qnode *)malloc( sizeof(qnode) );
ptr->op = op;
ptr->next = NULL;
if( qEmpty(q) ) // first element in q.
q->front = ptr;
else
q->rear->next = ptr;
q->rear = ptr;
}

void qInsertSorted(queue *q, qtype op) {
/*
* inserts val in sorted q and keeps new q sorted.
*/
qnode *ptr = (qnode *)malloc(sizeof(qnode));
qnode *curr, *prev;
ptr->op = op;

for(prev=NULL, curr=q->front; curr && curr->op->w < op->w; prev=curr, curr=curr->next)
;
if(!curr && !prev) // q empty.
ptr->next = NULL, q->rear = q->front = ptr;
else if(!curr) // op is the max value.
ptr->next = NULL, prev->next = q->rear = ptr;
else if(!prev) // op is the min value.
ptr->next = curr, q->front = ptr;
else { // if prev and ptr both exist.
ptr->next = curr;
prev->next = ptr;
}
}

qtype qPopFront( queue *q ) {
/*
* pops op from q->front.
*/
qnode *ptr = q->front;
qtype op;

if( qEmpty(q) )
return (qtype)NULL;
q->front = q->front->next;
if( qEmpty(q) ) q->rear = NULL;

op = ptr->op;
free(ptr);
return op;
}

int compare(const void *e1, const void *e2) {
/*
* compare the two elements in e1 and e2.
* each element is a vector of two elements.
*/
return ((int *)e1)[1] > ((int *)e2)[1];
}

void printTree(tree t, char *outputstr) {
/*
* print the huffman codes for each element of t.
* outputstr contains huffman code for t (NOT parent of t).
* assumes t!=NULL.
*/
char str[2] = "1";

if(t->right) {
strcat(outputstr, str);
printTree(t->right, outputstr);
outputstr[strlen(outputstr)-1] = 0; // restore.
}
if(t->left) {
str[0] = '0';
strcat(outputstr, str);
printTree(t->left, outputstr);
outputstr[strlen(outputstr)-1] = 0; // restore.
}
else if(!t->right)
printf("Symbol: %c - Code: %s - Rates: %d.\n", t->val, outputstr, t->w );
}

tree buildTree(int a[][2], int n) {
/*
* build a huffman tree using frequency in a[i][1] where a[0][j] indicates
* the character
* for that sort a on frequency.
* n is the size of a.
*/
int i;
tree t = NULL;
queue sortedq = {NULL};

// sort a on frequency.
qsort(a, n, sizeof(a[0]), compare);

// insert each element in tree.
for(i=0; i<n; ++i) {
tree temp = (tree)calloc(1, sizeof(node));
temp->w = a[i][1];
temp->val = (type)a[i][0];
qPushBack(&sortedq, temp);
}
// assume n>0.
while(n>0) {
tree t2 = NULL,
t1 = qPopFront(&sortedq);
if(!qEmpty(&sortedq))
t2 = qPopFront(&sortedq);
else {
t = t1;
break;
}

t = (tree)malloc(sizeof(node));
t->w = t1->w + t2->w;
t->left = t1;
t->right = t2;
{
qnode *ptr;
//for(ptr=sortedq.front; ptr; ptr=ptr->next)
//printf("%d ", ptr->op->w);
//printf("\n");
}
//printf("insertsorted=%d.\n", t->w);
qInsertSorted(&sortedq, t);
}
return t;
}
______________________________________________
hf.c
______________________________________________
#include <stdlib.h>
#include "hf.h"
#define MAXLEN 80


int main() {
/*int n=0,x=0,i=0,ch=0;
printf("How many symbols you want to use:");
scanf("%d",&n);
int a[n][2];
for(i=0;i<n;i++)
{
printf("\nEnter symbol %d:",i+1);
scanf("%c",&ch);
a[i][0]=ch;
}
for(i=0;i<n;i++)
{
printf("\nEnter Rate for %s:",a[i][0]);
scanf("%d",&x);
a[i][1]=x;
}
*/
int a[][2] = { {'B', 2012},
{'C', 2213},
{'D', 142},
{'E', 563},
{'F', 354},
{'G', 259},
{'F', 568 }
};
char outputstr[MAXLEN] ="";
tree t = buildTree(a, sizeof(a)/2/sizeof(int));

if(t)
printTree(t, outputstr);

return 0;
}
Заполнить структуру правильно не сложно, код работает.
 


Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск
Опции просмотра


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Код Хаффмана гость Реализация, исходники, языки 13 09.10.2012 07:43
реализация алгоритма хаффмана на Php и си Саня Реализация, исходники, языки 5 19.05.2010 14:03
Алгоритм Хаффмана гость Реализация, исходники, языки 1 28.04.2009 15:14
Код Хаффмана гость Математические алгоритмы 0 12.09.2007 14:59