第三题(共四题 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;
}
该程序只是一个实现版本,很多东西还可以做出修改的
比如读取文件时,可以采用内存映射,尤其对于大文件的读写来说更为合适
分享到:
相关推荐
Astar2007百度之星程序设计大赛网络资格赛(初赛) 题。 Astar2007百度之星程序设计大赛网络资格赛(初赛) 题 。
百度之星 2011 初赛 算法设计题 百度之星
Astar2006百度之星程序设计大赛题目参考源程序
百度之星程序设计大赛从2005到2010的初赛、复赛、决赛题目。
2012年百度之星初赛题目,仅供参考。有兴趣可以看看
2007年百度之星程序设计大赛复赛题目,应该可以帮助大家多了解一些大赛的出题规律
2005年百度之星程序设计大赛试题初赛题 ,适合热爱Java人士
对于2014年百度之星程序设计大赛迷宫问题的较为详尽的分析
百度之星-编程大赛初赛练习题 题目描述: 一个正整数有可能可以被表示为n(n>=2)个连续正整数之和,如:
2011微软校园之星初赛题目(原题),ATA合作院校参赛题。
2011年百度之星程序设计大赛初赛B,经典的题目,挑战的趣味,还在等什么?
2011百度之星试题合集,包括初赛A、B,复赛以及决赛,不含答案。
原理很简单:取max1,max2 然后分别存到2个不同的数组,之后对这2个数组进行排序后比大小就可以了;
2011年百度之星程序设计大赛初赛A试题,有难度,有挑战性!!!
百度之星2005-2007以及2011年的初赛复赛试题,文件为pdf文字版。
2019年 百度之星大赛资料 包含初赛 复赛 题解答案 问题解答 .rar
百度之星试题,我也忘记是哪年的了。
百度之星2009程序设计大赛 初赛第一场试题
初赛题目.zip