百度之星 2005年 初赛题目三

第三题（共四题 100 分）：字符串替换（ 30 分）

题目描述：请编写程序，根据指定的对应关系，把一个文本中的字符串替换成另外的字符串。

输入数据：程序读入已被命名为 text.txt 和 dict.txt 的两个输入数据文本文件， text.txt 为一个包含大量字符串（含中文）的文本，以 whitespace 为分隔符； dict.txt 为表示字符串（ s1 ）与字符串（ s2 ）的对应关系的另一个文本（含中文），大约在 1 万行左右，每行两个字符串（即 s1 和 s2 ），用一个 \t 或空格分隔。 dict.txt 中各行的 s1 没有排序，并有可能有重复，这时以最后出现的那次 s1 所对应的 s2 为准。 text.txt 和 dict.txt 中的每个字符串都可能包含除 whitespace 之外的任何字符。 text.txt 中的字符串必须和 dict.txt 中的某 s1 完全匹配才能被替换。（为便于调试，您可下载测试 text.txt 和 dict.txt 文件，实际运行时我们会使用不同内容的输入文件。）

输出数据：在标准输出上打印 text.txt 被 dict.txt 替换后了的整个文本。

评分标准：程序输出结果必须正确，内存使用越少越好，程序的执行时间越快越好。

 

思路：

    首先，读取dict.txt内容，构建HashTable。鉴于“并有可能有重复，这时以最后出现的那次 s1 所对应的 s2 为准”，在添加到HashTable中是，如果已经存在，则覆盖原有的Value值，即可。

   然后读取text.txt文件，使用strtok拆分

        对每一个字符串进行处理，然后在HashTable中寻找是否存在

        存在，则，替换输出到新的一个文件中

        不存在，则，不替换输出到新的一个文件中

   直至完成。

GHash.h

#ifndef __GHASH_H_
#define __GHASH_H_

#define HASHSIZE 512
typedef struct _Item
{
   char * key;
   char * value;
   struct Item * next;
} Item;

void GHashInit();
Item *  HashInSert(char * key,char * value);
int  HashRemove(char * key);
Item *  HashSearch(char * key);
void FreeGHash();
void PrintGHash();

#endif

 

 GHash.c

 

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

static struct Item *hashtab[HASHSIZE];

static void freeItem(Item * item);
static unsigned int _Hash(char *key);
static unsigned int _ELFHash(char *str);

void GHashInit()
{
 	 int i=0;
 	 for(i=0; i<HASHSIZE; i++)
 	 {
	  	hashtab[i]=NULL;
     }
}

Item *  HashInSert(char * key,char * value)
{
 	 Item * np;
 	 unsigned int hashval;
 	 if((np=HashSearch(key))==NULL)
 	 {
         np=(Item *)malloc(sizeof(Item));
         if(NULL==np || NULL ==(np->key = strdup(key))
		       || NULL ==(np->value = strdup(value)) )
         {
             return NULL;
         }
         hashval = _Hash(key);
         np->next = (Item *)hashtab[hashval];
         hashtab[hashval] = np;
     }
     else
     {
	  	 free(np->value);
	  	 if((np->value=strdup(value))== NULL)
	  	 {
		    return NULL;
         }
 	 }
 	 return np;
}
int  HashRemove(char * key)
{
}

Item *  HashSearch(char * key)
{
    Item  *np;

    for(np = (Item *)hashtab[_Hash(key)];
        np != NULL;
        np = np->next)
      if(strcmp(key,np->key) == 0)
           return np;
    return NULL;
}

void FreeGHash()
{
 	 int i=0;
 	 for(i=0; i<HASHSIZE; i++)
 	 {
	     if(hashtab[i]!=NULL)
	     {
		    Item * tmp;
		    Item * deln;
		    for(tmp=hashtab[i]; tmp!=NULL; tmp=hashtab[i])
		    {
			     hashtab[i]=tmp->next;
			     freeItem(tmp);
			}
		 }
     }
}
void PrintGHash()
{
 	 printf("Print Hash:\n");
 	 int i=0;
 	 for(i=0; i<HASHSIZE; i++)
 	 {
	     if(hashtab[i] !=NULL )
	     {
		    printf("%d---",i);
		    Item * tmp;
		    for(tmp=hashtab[i]; tmp!=NULL; tmp=tmp->next)
		    {
			     printf("%s:%s;",tmp->key,tmp->value);
			}
			printf("\n");
		 }
     }
}

static unsigned int _Hash(char *key)
{
    return _ELFHash(key)%HASHSIZE;
}

// ELF Hash Function
static unsigned int _ELFHash(char *str)
{
       unsigned int hash = 0;
       unsigned int x = 0;

       while (*str)
      {
           hash = (hash << 4) + (*str++);//hash左移4位，当前字符ASCII存入hash
           if ((x = hash & 0xF0000000L) != 0)
           {//如果最高的四位不为0，则说明字符多余7个，如果不处理，再加第九个字符时，第一个字符会被移出，因此要有如下处理。

           //该处理，如果对于字符串(a-z 或者A-Z)就会仅仅影响5-8位，否则会影响5-31位，因为C语言使用的算数移位
           hash ^= (x >> 24);
           //清空28-31位。
           hash &= ~x;
           }
       }

      //返回一个符号位为0的数，即丢弃最高位，以免函数外产生影响。(我们可以考虑，如果只有字符，符号位不可能为负)
     return (hash & 0x7FFFFFFF);

}

static void freeItem(Item * item)
{
   free(item->key);
   free(item->value);
   free(item);
}

 

 main.c

 

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

#define INPUT "3.input.txt"
#define TXT "3.text.txt"
#define OUT "3.out.txt"
#define DICTBUFSIZE 100
#define READBUFSIZE 513
#define FREADSIZE ((READBUFSIZE-1))
#define KEEPBUFSIZE (READBUFSIZE*2)
char keepbuf[KEEPBUFSIZE];

int WriteToFile(char* str,const FILE* f)
{
 	if(f==NULL)
 	   return 0;
    return fwrite(str,sizeof(char),strlen(str),f);
}

void HandlerItem(char *item,const FILE* out)
{
 	 Item * np;
     if((np=HashSearch(item)) == NULL)
  	 {//no hanlder
	    WriteToFile(item,out);
	    WriteToFile(" ",out);
 	 }
 	 else
 	 {
		WriteToFile(np->value,out);
		WriteToFile(" ",out);
     }
}

void HanlderBuf(const char *buf,const FILE* out)
{
 	 if (buf==NULL)
 	     return;
 	 strncat(keepbuf,buf,strlen(buf));
 	 char *split=" \t\n";
 	 char *tmp,*next;
 	 char *first=strtok(keepbuf,split);
 	 //HandlerItem(first,out);
 	 tmp=first;
 	 while(tmp)
 	 {
          next=strtok(NULL,split);
          if(next==NULL)//end of string
          {
	          strncpy(keepbuf,tmp,strlen(tmp));
	          keepbuf[strlen(tmp)]='\0';
	          break;
	      }
	      else
	      {
		   	  HandlerItem(tmp,out);
	   	  }
          tmp=next;
          
     }
}



int main(int argc, char *argv[])
{
  	//filterepeat(INPUT)
 	//construct hashtable of key-value
 	
 	//memory maps 
 	//hander every word split by whitespace
  //keepbuf[0]='\0';
  
  char dictbuf[DICTBUFSIZE];
  FILE * fdict=fopen(INPUT,"r+");
  if (NULL == fdict)
  {
   	 perror("open dict file wrong!\n");
   	 return 1;
  }
  
  GHashInit();
  
  //begin init dict list
  while(fgets(dictbuf,DICTBUFSIZE,fdict)!=NULL)
  {
      char* key = (char *)malloc(sizeof(char)*20);
      char* value= (char *)malloc(sizeof(char)*20);
      sscanf(dictbuf,"%s  %s",key,value);
      Item * np;
      if((np=HashInSert(key,value))==NULL)
  	  {
          printf("Insert %s:%s wrong\n",key,value);
  	  }
      printf("%s-%s\n",key,value);
  }
  fclose(fdict);
  //end init dict list
  
  //
  FILE *txtf = fopen(TXT,"r+");
  FILE *outf = fopen(OUT,"a");
  if(txtf == NULL && outf ==NULL)    
  {       
  	 perror("txtfile not open ");  
  }
  char readbuf[READBUFSIZE];
  memset(keepbuf,'\0',KEEPBUFSIZE);
  memset(readbuf,'\0',READBUFSIZE);
  int readnum;
  printf("%d-%d\n",READBUFSIZE,FREADSIZE);
  while((readnum=fread(readbuf,sizeof(char),FREADSIZE,txtf))>0)
  {
      readbuf[readnum]='\0';
      printf("%d\n",readnum);
      if(readnum<FREADSIZE)
      {
	      if(feof(txtf)!=0)//end file
	      {
	         HanlderBuf(readbuf,outf);
	         break;
	      }
          else
          {
		   	  perror("Error!");
	   	  }
	  }
	  else if(readnum==FREADSIZE)
	  {
	   	   HanlderBuf(readbuf,outf);
      }
  }
  
  if(strlen(keepbuf)>0)
    HandlerItem(keepbuf,outf);
  
  fflush(outf);
  fclose(txtf);
  fclose(outf);
  PrintGHash();
  FreeGHash();

  
  getchar();
  return 0;
}

 

 

 该程序只是一个实现版本，很多东西还可以做出修改的

 比如读取文件时，可以采用内存映射，尤其对于大文件的读写来说更为合适