`

百度之星 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;
}

 

 

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

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

 

 

 

 

 

 

分享到：
| HashTable简单实现，使用ELFHash 哈希
评论
发表评论

您还没有登录,请您登录后再发表评论

相关推荐

    百度之星题目（2005-2010）

    自2005年起，百度公司主办的"百度之星"程序设计大赛成为每年一度的IT界盛事，吸引了无数编程爱好者和专业选手参与。该比赛不仅检验了参赛者的编程技巧，也推动了国内计算机科学教育的发展。以下将对2005年至2010年间...

    百度之星2005预赛决赛题目及源程序

    1. **初赛2005.doc**：这是2005年百度之星初赛的题目文档，通常包括多个问题，涉及数据结构、算法、逻辑推理等多个方面。通过分析这些题目，我们可以了解当时比赛的难度水平和常见题型，比如排序、搜索、图论等经典...

    历年百度之星程序设计大赛试题题目

    这些压缩包中的文件名称表明，我们拥有从2005年至2007年连续三年的百度之星程序设计大赛的初赛、复赛以及总决赛的题目文档。这些文档通常包含了详细的题目描述、输入输出格式、样例测试数据以及评分标准，是了解比赛...

    百度之星 题目分析.doc

    2014年的百度之星程序设计大赛中有一道名为“迷宫问题”的题目，该题目要求参赛者帮助一只名为“度度熊”的角色探索一个由m×n矩阵构成的迷宫。迷宫的规则如下： - 度度熊从迷宫的左上角出发； - 只能向上、向下或...

    2005年百度之星程序设计大赛试题初赛题.doc

    本文档是2005年百度之星程序设计大赛初赛试题，共四题，总分为100分。每题的描述、输入数据、输出数据和评分标准如下： 第一题：连续正整数 题目描述：一个正整数可以被表示为n(n&gt;=2)个连续正整数之和，例如15=1+2+...

    百度之星十年试题集

    - **背景介绍**：“百度之星”是由百度公司主办的一项面向全国大学生的程序设计竞赛，自2005年起至今已成功举办多届。该比赛旨在通过算法挑战激发学生的编程兴趣和创新能力，同时选拔出优秀的人才加入百度。 - **...

    百度之星历年试题

    【百度之星历年试题】是关于中国著名互联网巨头百度举办的一项技术竞赛——百度之星的历年考试题目集合。这个压缩包包含了2005年至2007年以及2011年的初赛和复赛试题，格式为PDF，方便学习者进行查阅和练习。 百度...

    百度编程大赛初赛练习题

    ### 百度编程大赛初赛练习题解析 #### 题目一：连续整数之和 **题目描述**： 本题考查的是如何判断一个正整数是否能表示为至少两个连续正整数之和，并找出所有可能的组合方式。 **示例**： - 例如数字15可以...

    百度之星历年预决赛试题（包括2009年）

    "百度之星历年预决赛试题（包括2009年）"这一资源包含了自2005年以来百度举办的“百度之星”编程竞赛的所有题目，旨在帮助参赛者或编程爱好者提升编程技能和解决问题的能力。这些试题涵盖了从初级到高级的各类编程...

    poj-ACM.zip_ 1706 References_ACM_ACM习题

    2. **2005年百度之星程序设计大赛试题初赛题目.doc**：这份文档包含了2005年百度主办的程序设计大赛初赛的题目，对于了解历年的竞赛题型和难度，以及学习如何解决实际问题具有很高的价值。 3. **poj题目**：POJ是...

Magicbox
Global site tag (gtag.js) - Google Analytics