hash应用之字符串替换

1. 考虑一个字符串替换的过程，在一个文本文件中含有一些文本内容和一些需要替换的变量，变量的格式为“$Var$”，原来的“$”使用“$$”进行转义，原来的“$$”表示为“$$$”。我们将含有变量的文件称为模板(文件名为t)，文本文件的平均长度为100K。另外，还有一系列的变量文件，里面为变量名和变量值的对应关系(文件名为1.v , 2.v… n.v)，每个变量文件包含的变量数在百万数量级，且变量排列次序不定。现要求将，模板里的变量分别用变量文件里的变量替换，并将生成的文件写成 (1.r, 2.r… n.r)。
要求：从算法和实现上和实现技术上的细节对程序进行优化，尽量使程序高效。程序运行环境为2G内存，4CPU。阐明主要思路，给出伪码和说明，可以着重指出你使用的优化技术。
例子：模板文件为
This is an $FF$ $$. I like $FF$ and $FA$。
变量文件为
1.v
FF : banana
FA : apple
2.v
FA: 苹果
FF : 香蕉
则生成文件为
1.r
This is an banana $$. I like banana and apple。
2.r
This is an香蕉 $$. I like 香蕉and苹果。

 

我这里程序没有生成1.r,  2.r而是直接输出的

 

基本思路是先对变量文件做hash,然后遍历模板文件,遇到变量就替换...思路很简单,这种题就是写代码烦...

 

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

#define HASH_SIZE 13
#define MAX_KEY 10
#define MAX_LINE 100

typedef struct hash
{
  char str[MAX_KEY];
  char value[MAX_KEY];
  struct hash* next;
}HASH;

HASH* H[HASH_SIZE];
 
void init_hash()
{
 int i;
 for(i=0;i<HASH_SIZE;i++)
 {
  H[i] = (HASH*)malloc(sizeof(HASH));
  H[i]->next = NULL;
 }
}

void free_hash_node()
{
  int i;
  HASH* p;
  HASH* q;
  
  for(i=0;i<HASH_SIZE;i++)
   {
     p = H[i]->next;
     while(p!=NULL)
      {
        q = p;
        p = p->next;
        free(q);
      }
    H[i]->next = NULL;
   }
}

void free_hash()
{
  int i;
  HASH* p;
  HASH* q;
  
  for(i=0;i<HASH_SIZE;i++)
   {
     p = H[i]->next;
     while(p!=NULL)
      {
        q = p;
        p = p->next;
        free(q);
      }
     free(H[i]);
   }
}

unsigned int get_hash(char* str)
{
  unsigned int seed = 131;
  unsigned int hash = 0;
  
  while(*str)
     hash = hash * seed + *str++;
   
   return (hash&0x7FFFFFFF);
}

void add_hash(char* key,char* value)
{
   unsigned int hash_num = get_hash(key);
   hash_num %= HASH_SIZE;
   
   HASH* p = (HASH*)malloc(sizeof(HASH));
   sprintf(p->str,"%s",key);
   sprintf(p->value,"%s",value);
   
   p->next = H[hash_num]->next;
   H[hash_num]->next = p;
}
   
int process_v_file(FILE* fp)
{
  char key[MAX_KEY];
  char value[MAX_KEY];
  
  while(fscanf(fp, "%s : %s\n", key, value)!=EOF)
   {
    printf("key is %s, value is %s\n", key, value);
    add_hash(key,value);
   }
}
 
 
char* key_2_value(char* key)
{
   unsigned int hash_num = get_hash(key);
   hash_num %= HASH_SIZE;
   
   HASH* p = H[hash_num]->next;
   while(p!=NULL)
    {
     if(strcmp(p->str, key) == 0 )
       break;
     p = p->next;
    }
  
   if(p!=NULL)
   return p->value;
   
  return NULL;
}

int process_template()
{
  char line[MAX_LINE];
  char line_after[MAX_LINE];
  char* value;
  int i = 0;
  int j = 0;
  int k = 0;
  
  FILE* fp = fopen("template.txt","r");
  
  while(fgets(line, MAX_LINE, fp)!=NULL)
   {
     while(line[i]!='\0')
      {
        printf("!!!! %c\n", line[i]);
        if(line[i] == '$')
         {
           if(line[i+1] == '$')
            {
              line_after[j++] = line[i++];
              line_after[j++] = line[i++];
            }
           else
            {
              i++;
              k = i;
              while(line[i]!='$')
                i++;
               
              line[i] = '\0';
              printf("key is %s\n", line+k);
              value = key_2_value(line+k);
              printf("value is: %s\n", value);
              i++;
              while((line_after[j++] = *value++)!='\0')
               ;
              j--;
            }
         }
        else
         {
          line_after[j++] = line[i++];
         }
      }
     line_after[j] = '\0';
     printf("after the line is:\n%s", line_after);
   }
}

void print_hash()
{
  int i;
  HASH* p = NULL;
  for(i=0;i<HASH_SIZE;i++)
   {
     p = H[i]->next;
     while(p!=NULL)
      {
        printf("%d key is %s, value is %s\n", i, p->str, p->value);
        p = p->next;
       }
   }
}
    
int main(int argc, char *argv[])
{
  init_hash();
  
  FILE* fp = fopen("1.v.txt","r");
  process_v_file(fp);
  fclose(fp);
  
  printf("in hash\n");
  print_hash();
  
  process_template();
  free_hash_node();
  
  fp = fopen("2.v.txt","r");
  process_v_file(fp);
  fclose(fp);
  process_template();
  free_hash();
     
  system("PAUSE");    
  return 0;
}


 

调试信息没有delete，现在都是dev-c++写代码,都是printf debug的,gdb都忘的差不多了,惭愧惭愧