CSDN老博文迁移-用lzw算法编码一个字符串

  #include <stdio.h>
  #include <string.h>
  #define STR_LEN 100
  #define DIC_LEN 4096

  struct dict {
    char str[STR_LEN];
    int index;
  } Dict[DIC_LEN];

  int j = 256;

  int in_dict(char *s, struct dict *Dict); /* 判断一个字符串s是否在字典中 */
  int index_of(char *s, struct dict *Dict);/* 通过字符串在字典中查找编号 */
  void insert_into_dict(char *s, struct dict *Dict);/*把字符串添加到字典中 */
  void init(struct dict *Dict); /* 初始化字典 */
  void output(int code, char *s);/* 输出编码与相应的字符串 */

  int main(void) {
    int i, code;
    char ch;
    char *str = "hellohellohello";
    char old_string[STR_LEN], new_string[STR_LEN];
    old_string[0] = str[0];
    old_string[1] = '\0';

    init(Dict);

    for (i = 1; str[i] != '\0'; i++) {
      ch = str[i];
      strcpy(new_string, old_string);
      strncat(new_string, &ch, 1);
      if (in_dict(new_string, Dict)) {
        strcpy(old_string, new_string);/* 更新旧字符串 */
      } else {
        code = index_of(old_string, Dict); /* 找到编码 */
        output(code, old_string); /* 输出编码 */
        insert_into_dict(new_string, Dict); /* 更新字典 */
        j++;
        old_string[0] = ch;
        old_string[1] = '\0';
      }
    }
    code = index_of(old_string, Dict);
    output(code, old_string);
    printf("\n");

    return 0;
  }

  int in_dict(char *s, struct dict *Dict) {
    int i;
    for (i = 0; i < DIC_LEN; i++) {
      if (strcmp(s, Dict[i].str) == 0) {
        return 1;
      }
    }
    return 0;
  }

  int index_of(char *s, struct dict *Dict) {
    int i;
    for (i = 0; i < DIC_LEN; i++) {
      if (strcmp(s, Dict[i].str) == 0) {
        return Dict[i].index;
      }
    }
  }

  void insert_into_dict(char *s, struct dict *Dict) {
    Dict[j].index = j;
    strcpy(Dict[j].str, s);
  }

  void init(struct dict *Dict) {
    int i, j;
    for (i = 0; i < DIC_LEN; i++) {
      for (j = 0; j < STR_LEN; j++) {
        Dict[i].str[j] = '\0';
      }
      Dict[i].index = i;
    }
    for (i = 0; i < 256; i++) {
      Dict[i].str[0] = (char) i;
    }
  }

  void output(int code, char *s) {
    printf("%d (%s)\n", code, s);
  }