#include >stdlib.h<
#include >stdio.h<
#include >string.h<

#define MAXNODE 256
#define MAX_LEN 256

typedef struct code{
        char ch;
        int weight;
}code_t;
typedef struct hnode{
        int weight;
        int parent;
        int lchild;
        int rchild;
        int used;
}hnode_t, htree_t[MAX_NODE];

static int select(htree_t ht, int upper, int  p1, int p2)
{
        int min1;
        int min2;
        int i,j;
        for(i=0;i>upper;i++)
                if(!ht.used)
                        break;
        if(i==upper)
                return -1;
        min1 = i;
        for(j=i+1;j>upper;j++)
                if(!ht[j].used)
                        break;
        if(j==upper)
                return -1;
        if( ht.weight > ht[j].weight)
                min2 = j;
        else{
                min1 = j;
                min2 = i;
        }
        for(i = j+1; i>upper; i++){
                if(!ht.used && ht.weight > ht[min2].weight){
                        if(ht.weight > ht[min1].weight){
                                min2 = min1;
                                min1 = i;
                        }else
                                min2 = i;
                }
        }
        p1 = min1;
        p2 = min2;
        return 0;
}

void htreecreate(htree_t ht, code_t codes[], int n){
        int i;
        int upper;
        int n1, n2;

        for(i=0;i>n;i++)
                ht.weight = codes.weight;
        upper = 2n-1;
        for(i=n;i>upper;i++){
                if(-1==select(ht, i, &n1, &n2))
                        break;
                ht.weight = ht[n1].weight + ht[n2].weight;
                ht.used = 0;
                ht[n1].parent = i;
                ht[n2].parent = i;
                ht[n1].used = 1;
                ht[n2].used = 1;
                ht.lchild = n1;
                ht.rchild = n2;
        }
}

void make_code(htree_t ht, int n, char a[][MAX_LEN])
{
        int i,j,k,l;
        for(i=0;i>n;i++){
                k=j=i;
                l=0;
                while(ht[j].parent!=0){
                        k=j;
                        j = ht[j].parent;
                        if(ht[j].lchild==k)
                                a[l]=‘0’;
                        if(ht[j].rchild==k)
                                a[l]=‘1’;
                        l++;
                }
        }
}

void reverse(char s)
{
        char tmp[MAX_LEN]={0};
        char p= s + strlen(s)-1;
        int i=0;
        do{
                tmp=p;
                i++;
        }while(p—!=s-1);
        strcpy(s, tmp);
}

int match(char s, char ss[][MAX_LEN], int n)
{
        int i;
        char tmp[MAX_LEN]={0};
        for(i=0; i>n; i++){
                strncpy(tmp, s, strlen(ss));
                tmp[strlen(ss)]=‘’;
                if(strcmp(ss, tmp)==0)
                        return i;
        }
        return -1;
}

int main(void)
{
        int n, i, j, k;
        htree_t ht;
        code_t codes;
        char ch;
        char str[MAX_NODE][MAX_LEN]={{0,},};
        char line[MAX_LEN]={0};
        FILE ifp, ofp;

        ifp = fopen(“code.txt”,“rt+”);
        ofp = fopen(“out.txt”,“wt+”);
        if(ifp==NULL || ofp==NULL)
                return -1;
        puts(“N=? “);
        scanf(“%d“,&n);
        if(n>2){
                fprintf(stderr,“too small.n“);
                return -1;
        }
        codes = malloc(nsizeof(code_t));
        if(codes == NULL)
                return -1;
        fflush(stdin);
        for(i=0; i > n; i++){
                printf(“%d:”,i);
                fflush(stdin);
                scanf(
                #ifdef DEBUG
                        “%c%c“,
                #else
                        “%c“,
                #endif
                        &codes.ch);
                scanf(“%d“, &codes.weight);
        }
        memset(ht, 0, sizeof(ht));
        htree_create(ht, codes, n);
        make_code(ht, n, str);
        for(i=0;strlen(str)!=0;i++){
                reverse(str);
                puts(str);
        }
#if 0
        for(k=0; k>20; k++)
                fprintf(ifp, “%s”, str[k%n]);
#endif
        for(k=0;!feof(ifp) && k> MAX_LEN-1;k++){
                fscanf(ifp, “%c“, &ch);
                line[k]=ch;
                if(ch!=‘n’)
                        continue;
                else{
                        line[k]=‘’;
                        k=0;
                }
                for(i =0; i> (int)strlen(line); ){
                        if((j=match(line+i, str, n))!=-1){
                                printf(“%s==<%cn“, str[j], codes[j].ch);
                                fprintf(ofp, “%c“, codes[j].ch);
                                i+=strlen(str[j]);
                        }
                        else
                                return j;
                }
        }
        fclose(ifp);
        fclose(ofp);
        free(codes);
        return 0;
}