老师在课上偶然提到到CSI第三章的霍夫曼编码,于是自己琢磨了一番: 还有很多可以优化的地方,比如说可以用堆来优化队列,之后我在慢慢填坑吧 ~
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
typedef struct trnode
{
int key;
struct trnode *lchild;
struct trnode *rchild;
} Trnode;
typedef struct tree
{
int size;
Trnode *root;
} Tree;
void buildtree(Tree* tree,int *C);
Trnode* makeNode(int data);
Trnode* min_element(Trnode* array[]);
void insert(Trnode* x,Trnode* array[]);
bool isEmpty(Trnode* array[]);
void quicksort(int *base,int x,int y) //x y数组下标
{
int i=x,j=y;
if(x>y)
return;
int temp=base[x]; //temp储存基准数
while(i<j)
{
while(base[j]>=temp&&i<j)
j--;
while(base[i]<=temp&&i<j)
i++;
if(i<j)
{
int exc=base[i];
base[i]=base[j];
base[j]=exc;
}
}
base[x]=base[i];
base[i]=temp;
quicksort(base,x,i-1);
quicksort(base,i+1,y);
}
void Print(Trnode* root,int *base,int i)
{
if(root->lchild==NULL&&root->rchild==NULL)
{
for(int i=0;i<5&&base[i]!=-1;i++)
printf("%d",base[i]);
printf(" ");
}
else
{
base[i]=0;
Print(root->lchild,base,i+1);
base[i]=1;
Print(root->rchild,base,i+1);
base[i]=-1;
}
}
int main(void)
{
int A[5]={10,6,3,5,567};
int C[5];
for(int i=0;i<5;i++)
C[i]=A[i];
quicksort(C,0,4);
Tree *tree=(Tree*)malloc(sizeof(Tree));
tree->root=NULL;
buildtree(tree,C);
int base[5]={-1,-1,-1,-1,-1};
int floor=0;
Print(tree->root,base,floor);
return 0;
}
void buildtree(Tree *tree,int *C)
{
Trnode* array[5];
for(int i=0;i<5;i++)
{
array[i]=makeNode(C[i]);
}
while(!isEmpty(array))
{
Trnode *x=min_element(array);
if(isEmpty(array))
{
tree->root=x;
break;
}
Trnode *y=min_element(array);
Trnode *z=(Trnode*)malloc(sizeof(Trnode));
z->key=x->key+y->key;
z->lchild=y;
z->rchild=x;
if(isEmpty(array))
{
tree->root=z;
break;
}
insert(z,array);
}
}
Trnode* makeNode(int data)
{
Trnode* x=(Trnode*)malloc(sizeof(Trnode));
x->key=data;
x->lchild=NULL;
x->rchild=NULL;
return x;
}
Trnode* min_element(Trnode* array[])
{
Trnode *p=array[0];
int i;
for(i=1;i<5;i++)
{
if(array[i]->key!=0)
array[i-1]=array[i];
else
break;
}
array[i-1]=makeNode(0);
return p;
}
void insert(Trnode* x,Trnode* array[])
{
int i=4;
while(i>=0)
{
if(array[i-1]->key!=0)
array[i]=array[i-1];
if(array[i]->key!=0&&array[i]->key<x->key)
break;
i--;
}
array[i]=x;
}
bool isEmpty(Trnode* p[])
{
for(int i=0;i<5;i++)
{
if(p[i]->key!=0)
{
return false;
}
}
return true;
}
2017年10月16日更:
我来填坑啦~
这是用堆优化过的版本
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
typedef struct trnode
{
int key;
struct trnode *lchild;
struct trnode *rchild;
} Trnode;
typedef struct tree
{
Trnode *root;
} Tree;
typedef struct queue
{
Trnode *array[5];
int size;
} Queue;
void buildtree(Tree* tree,int *C);
Trnode* makeNode(int data);
Trnode* min_element(Queue *H);
void insert(Trnode* x,Queue *H);
bool isEmpty(Trnode* array[]);
void swap(Trnode *a,Trnode *b)
{
Trnode temp=*a;
*a=*b;
*b=temp;
}
void quicksort(int *base,int x,int y) //x y数组下标
{
int i=x,j=y;
if(x>y)
return;
int temp=base[x]; //temp储存基准数
while(i<j)
{
while(base[j]>=temp&&i<j)
j--;
while(base[i]<=temp&&i<j)
i++;
if(i<j)
{
int exc=base[i];
base[i]=base[j];
base[j]=exc;
}
}
base[x]=base[i];
base[i]=temp;
quicksort(base,x,i-1);
quicksort(base,i+1,y);
}
void Print(Trnode* root,int *base,int i)
{
if(root->lchild==NULL&&root->rchild==NULL)
{
for(int i=0;i<5&&base[i]!=-1;i++)
printf("%d",base[i]);
printf(" ");
}
else
{
base[i]=0;
Print(root->lchild,base,i+1);
base[i]=1;
Print(root->rchild,base,i+1);
base[i]=-1;
}
}
int main(void)
{
int A[5]={10,6,3,5,567};
int C[5];
for(int i=0;i<5;i++)
C[i]=A[i];
quicksort(C,0,4);
Tree *tree=(Tree*)malloc(sizeof(Tree));
tree->root=NULL;
buildtree(tree,C);
int base[5]={-1,-1,-1,-1,-1};
int floor=0;
Print(tree->root,base,floor);
return 0;
}
void buildtree(Tree *tree,int *C)
{
/*if(!isEmpty(C))
{
Trnode *x=makeNode(min_element(C));
if(tree->root==NULL)
tree->root=x;
Trnode *y=makeNode(min_element(C));
Trnode *z=(Trnode*)malloc(sizeof(Trnode));
tree->root=z;
z->key=x->key+y->key;
z->lchild=y;
z->rchild=x;
insert(z->key,C);
}*/
Queue *H=(Queue*)malloc(sizeof(Queue));
H->size=0;
for(int i=0;i<5;i++)
{
H->array[i]=makeNode(C[i]);
H->size++;
}
while(!isEmpty(H->array))
{
Trnode *x=min_element(H);
Trnode *y=min_element(H);
Trnode *z=(Trnode*)malloc(sizeof(Trnode));
z->key=x->key+y->key;
z->lchild=x;
z->rchild=y;
if(isEmpty(H->array))
{
tree->root=z;
break;
}
insert(z,H);
}
}
Trnode* makeNode(int data)
{
Trnode* x=(Trnode*)malloc(sizeof(Trnode));
x->key=data;
x->lchild=NULL;
x->rchild=NULL;
return x;
}
Trnode* min_element(Queue *H)
{
int dad=0;
int son=2*dad+1;
Trnode* p=H->array[0];
H->array[0]=makeNode(0);
while(son<=H->size-1)
{
if(son+1<=H->size-1&&H->array[son+1]->key<H->array[son]->key)
son++;
swap(H->array[dad],H->array[son]);
dad=son;
son=2*dad+1;
}
H->array[dad]=H->array[H->size-1];
H->array[H->size-1]=makeNode(0);
H->size--;
return p;
}
void insert(Trnode* x,Queue *H)
{
H->array[H->size]=x;
H->size++;
int son=H->size-1;
int dad=(son-1)/2;
while(dad>=0&&son!=0)
{
if(H->array[dad]->key<H->array[son]->key)
break;
swap(H->array[dad],H->array[son]);
son=dad;
dad=(son-1)/2;
}
}
bool isEmpty(Trnode* p[])
{
if(p[0]->key==0)
return true;
else
return false;
}