以{8,5,3,2,9,11,2}为叶子结点的权值构造哈夫曼树,并求其带权路径长度.
来源:学生作业帮助网 编辑:作业帮 时间:2024/07/17 05:12:40
![以{8,5,3,2,9,11,2}为叶子结点的权值构造哈夫曼树,并求其带权路径长度.](/uploads/image/z/8461571-59-1.jpg?t=%E4%BB%A5%7B8%2C5%2C3%2C2%2C9%2C11%2C2%7D%E4%B8%BA%E5%8F%B6%E5%AD%90%E7%BB%93%E7%82%B9%E7%9A%84%E6%9D%83%E5%80%BC%E6%9E%84%E9%80%A0%E5%93%88%E5%A4%AB%E6%9B%BC%E6%A0%91%2C%E5%B9%B6%E6%B1%82%E5%85%B6%E5%B8%A6%E6%9D%83%E8%B7%AF%E5%BE%84%E9%95%BF%E5%BA%A6.)
以{8,5,3,2,9,11,2}为叶子结点的权值构造哈夫曼树,并求其带权路径长度.
以{8,5,3,2,9,11,2}为叶子结点的权值构造哈夫曼树,并求其带权路径长度.
以{8,5,3,2,9,11,2}为叶子结点的权值构造哈夫曼树,并求其带权路径长度.
1.struct_tree.h
#include "stdio.h"
#include "conio.h"
#include "stdlib.h"
typedef struct tree
{
char data;
int weight;
struct tree *parent;
struct tree *Lchild;
struct tree *Rchild;
}bitnode,*bitree;
typedef struct node
{
char ch;
struct node *next;
}linknode,*linklist;
2.stack.h
typedef struct stack
{
bitree ch;
struct stack *next;
}linkstacknode,*linkstack;
linkstack initstack()
{
linkstack s;
s=(linkstack)malloc(sizeof(linkstacknode));
s->next=NULL;
return s;
}
linkstack clearstack(linkstack s)
{
s->next=NULL;
return s;
}
int isempty(linkstack s)
{
if(s->next==NULL)
return 1;
return 0;
}
int push(linkstack s,bitree ch)
{
linkstacknode *temp;
temp=(linkstacknode *)malloc(sizeof(linkstacknode));
if(temp==NULL)
return 0;
temp->ch=ch;
temp->next=s->next;
s->next=temp;
return 1;
}
int pop(linkstack s,bitree *ch)
{
linkstacknode *temp;
temp=s->next;
if(temp==NULL)
return 0;
s->next=temp->next;
*ch=temp->ch;
free(temp);
return 1;
}
int gettop(linkstack s,bitree *ch)
{
linkstacknode *temp;
temp=s->next;
if(temp==NULL)
return 0;
*ch=temp->ch;
return 1;
}
3.queue.h
typedef struct queue
{
bitree ch;
struct queue *next;
}linkqueuenode;
typedef struct
{
linkqueuenode *front;
linkqueuenode *rear;
}linkqueue;
linkqueue* initqueue()
{
linkqueue *q;
q=(linkqueue *)malloc(sizeof(linkqueue));
q->front=(linkqueuenode *)malloc(sizeof(linkqueuenode));
if(q->front!=NULL)
{
q->rear=q->front;
q->front->next=NULL;
return q;
}
return NULL;
}
int enterqueue(linkqueue *q,bitree ch)
{
linkqueuenode *newnode;
newnode=(linkqueuenode *)malloc(sizeof(linkqueuenode));
if(newnode!=NULL)
{
newnode->ch=ch;
newnode->next=NULL;
q->rear->next=newnode;
q->rear=newnode;
return 1;
}
return 0;
}
int deletequeue(linkqueue *q,bitree *ch)
{
linkqueuenode *temp;
if(q->front==q->rear)
return 0;
temp=q->front->next;
q->front->next=temp->next;
if(q->rear==temp)
q->rear=q->front;
*ch=temp->ch;
free(temp);
return 1;
}
int getqueue(linkqueue *q,bitree *ch)
{
linkqueuenode *temp;
if(q->front==q->rear)
return 0;
temp=q->front->next;
*ch=temp->ch;
return 1;
}
4.主程序
typedef struct queue
{
bitree ch;
struct queue *next;
}linkqueuenode;
typedef struct
{
linkqueuenode *front;
linkqueuenode *rear;
}linkqueue;
linkqueue* initqueue()
{
linkqueue *q;
q=(linkqueue *)malloc(sizeof(linkqueue));
q->front=(linkqueuenode *)malloc(sizeof(linkqueuenode));
if(q->front!=NULL)
{
q->rear=q->front;
q->front->next=NULL;
return q;
}
return NULL;
}
int enterqueue(linkqueue *q,bitree ch)
{
linkqueuenode *newnode;
newnode=(linkqueuenode *)malloc(sizeof(linkqueuenode));
if(newnode!=NULL)
{
newnode->ch=ch;
newnode->next=NULL;
q->rear->next=newnode;
q->rear=newnode;
return 1;
}
return 0;
}
int deletequeue(linkqueue *q,bitree *ch)
{
linkqueuenode *temp;
if(q->front==q->rear)
return 0;
temp=q->front->next;
q->front->next=temp->next;
if(q->rear==temp)
q->rear=q->front;
*ch=temp->ch;
free(temp);
return 1;
}
int getqueue(linkqueue *q,bitree *ch)
{
linkqueuenode *temp;
if(q->front==q->rear)
return 0;
temp=q->front->next;
*ch=temp->ch;
return 1;
}