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