Chinaunix首页 | 论坛 | 博客
  • 博客访问: 1879366
  • 博文数量: 333
  • 博客积分: 10791
  • 博客等级: 上将
  • 技术积分: 4314
  • 用 户 组: 普通用户
  • 注册时间: 2007-08-08 07:39
文章分类

全部博文(333)

文章存档

2015年(1)

2011年(116)

2010年(187)

2009年(25)

2008年(3)

2007年(1)

分类: C/C++

2011-07-05 17:31:19

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

#define MAX_SYMBOLS 255
#define MAX_LEN 10

struct tnode {
    struct tnode *left;    /*used when in tree */
    struct tnode *right;    /*used when in tree */
    int isleaf;
    char symbol;
};

struct code {
    int symbol;
    char strcode[MAX_LEN];
};

/*global variables*/
struct tnode *root = NULL;    /*tree of symbols */

/*
    @function talloc
    @desc allocates new node
*/

struct tnode *talloc()
{
    struct tnode *p = (struct tnode *) malloc(sizeof(struct tnode));
    if (p != NULL) {
        p->left = p->right = NULL;
        p->symbol = 0;
        p->isleaf = 0;
    }
    return p;
}

/*
    @function build_tree
    @desc builds the symbol tree given the list of symbols and code.h
    NOTE: alters the global variable root that has already been allocated in main
*/

void build_tree(FILE * fp)
{
    char symbol;
    char strcode[MAX_LEN];
    int items_read;
    int i, len;
    struct tnode *curr = NULL;

    while (!feof(fp)) {
        items_read = fscanf(fp, "%c %s\n", &symbol, strcode);
        if (items_read != 2)
            break;
        curr = root;
        len = strlen(strcode);
        for (i = 0; i < len; i++) {
            /*TODO: create the tree as you go */

            if('1' == strcode[i]){
                if(NULL == curr->right){
                    struct tnode *tmp_node = talloc();
                    curr->right = tmp_node;
                }

                curr = curr->right;
            }
            else{
                if(NULL == curr->left){
                    struct tnode *tmp_node = talloc();
                    curr->left = tmp_node;
                }

                curr = curr->left;
            }
            
        }
        /*assign code */
        curr->isleaf = 1;
        curr->symbol = symbol;
        printf("inserted symbol:%c\n", symbol);
    }
}

/*
    function decode
*/

void decode(FILE * fin, FILE * fout)
{
    char c;
    struct tnode *curr = root;
    while ((c = getc(fin)) != EOF) {
        /*TODO:
         traverse the tree
         print the symbols only if you encounter a leaf node
         */

        
        if('1' == c)
                curr = curr->right;
        else if('0' == c)
                curr = curr->left;
            
        if(NULL == curr->left && NULL == curr->right){ // isleaf

            putc(curr->symbol, fout);
            curr = root;
        }
        
    }
}

/*
    @function freetree
    @desc     cleans up resources for tree
*/


void freetree(struct tnode *root)
{
    if (root == NULL)
        return;
    freetree(root->right);
    freetree(root->left);
    free(root);
}

int main()
{
    const char *IN_FILE = "encoded.txt";
    const char *CODE_FILE = "code.txt";
    const char *OUT_FILE = "decoded.txt";
    FILE *fout;
    FILE *fin;
    /*allocate root */
    root = talloc();
    fin = fopen(CODE_FILE, "r");
    /*build tree */
    build_tree(fin);
    fclose(fin);

    /*decode */
    fin = fopen(IN_FILE, "r");
    fout = fopen(OUT_FILE, "w");
    decode(fin, fout);
    fclose(fin);
    fclose(fout);
    /*cleanup */
    freetree(root);
    //getchar();

    return 0;
}


阅读(1025) | 评论(0) | 转发(0) |
0

上一篇:[MIT C]lifegame总结

下一篇:sizeof实现

给主人留下些什么吧!~~