求C语言高手请进解决！！！！！

2025-02-26 05:56:16

推荐回答（1个）

回答1：

给你找到了：
/********************** huffman.h ************************/
#include

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;
}

/********************* huffman.c *************************/
#include

#define MAXLEN 80

typedef struct node node;
typedef char type;
typedef node *tree;
typedef enum {FALSE, TRUE} bool;

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

#include "huffman.q.h"

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("%c=%d=%s.\n", t->val, t->w, outputstr);
}

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; iw = a[i][1];
temp->val = (type)a[i][0];
qPushBack(&sortedq, temp);
}
// assume n>0.
while(TRUE) {
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;
}

int main() {
int a[][2] = { {'a', 20},
{'b', 23},
{'c', 14},
{'d', 56},
{'e', 35},
{'f', 29},
{'g', 5 }
};
char outputstr[MAXLEN] = "";
tree t = buildTree(a, sizeof(a)/2/sizeof(int));

if(t)
printTree(t, outputstr);

return 0;
}

最新问答

身体表皮无故痛是什么原因?

贵阳银行股份有限公司金城支行怎么样？

金木水火土五行我是哪行？请高人指点啊。。。

怎么解除中国移动合约机？

想好好学习，可是心又被很多东西占据着，实在是无法静下心来，我是真的很想全身心的投入到学习中，好好珍