Chinaunix首页 | 论坛 | 博客
  • 博客访问: 557281
  • 博文数量: 104
  • 博客积分: 4131
  • 博客等级: 上校
  • 技术积分: 1137
  • 用 户 组: 普通用户
  • 注册时间: 2009-07-31 15:05
文章分类

全部博文(104)

文章存档

2011年(13)

2010年(23)

2009年(68)

我的朋友

分类: WINDOWS

2009-12-11 22:23:14

做了很长时间的调试,文本文件的读写让我搭进去了很多时间,比如文件大小n,然后读文件n个字节数据,但是在n-m(m>>1)处就没有数据了,很让人头疼,也许文本文件要发生字符转换问题吧,计算位置就发生混乱了。像fseek函数也不能用,简直就不是你想要的结果。上一个程序时花了很长时间才做完的,只能以读文件中字符方式,确定文件长度,用缓冲区复制来保留信息,很麻烦。以下是二进制的文件读写,很方便,要是早点用就节约时间了,而且适用广!
#include
#include
#include
#include
#include
#define MAXSIZE 102400
// 计算文件长度
long get_file_size(char *filename)
{
 
 struct stat f_stat;
 if( stat( filename, &f_stat ) == -1 )
  return -1;
    return f_stat.st_size;
}
//得到next值
void get_nextval(unsigned char pat[],int nextval[],int length)
{
 int i=1;
 int j=0;
 nextval[1]=0;
 while(i {
  if(j==0||pat[i-1]==pat[j-1])
  {
   ++i;
   ++j;
   if(pat[i-1]!=pat[j-1]) nextval[i]=j;
   else nextval[i]=nextval[j];
  }
  else j=nextval[j];
 }
}
//kmp算法搜索
int Index_KMP(unsigned char text[], unsigned char pat[],int nextval[],int t_len,int p_len)
{
 int i=0;
 int j=0;
 int count=0;
 while (i<=t_len&&j<=p_len)
 {
  if(j==0||text[i-1]==pat[j-1]){++i;++j;}
  else j=nextval[j];
  if (j>p_len)
  {
   count++;
   j=1;
  }
 }
 if (count>0) return count;
 else return -1;
}
//匹配处理
int Serach(char *file1,char *file2)
{
 int i=0;
 int count=0;
 int answer;
 long ReadSize;
 long tLen=0;//主串文件长度
 long pLen=0;//模式串文件长度
 int BlockNum=0;//分组大小
 long tlastlen=0;//
 unsigned char *tData;//为存放文件数据申请空间的起始位置
 unsigned char *pData;//为存放文件数据申请空间的起始位置
 int*  nextval;
 FILE* tFile=NULL;
 FILE* pFile=NULL;
 tLen=get_file_size(file1);
 pLen=get_file_size(file2);
 printf("主串长度为:%ld字节.\n",tLen);
 printf("模式串长度为:%ld字节.\n",pLen);
 if(tLen==0||tLen  return 0;
 BlockNum=tLen/MAXSIZE;
 tlastlen=tLen%MAXSIZE;
 BlockNum=tlastlen?(BlockNum+1):BlockNum;
 if((tFile= fopen(file1,"rb"))==NULL)
 { 
  printf("Open tFile Error!\n");//DEBUG
  return 0;//错误处理机制
 }
 if((pFile= fopen(file2,"rb"))==NULL)
 { 
  printf("Open pFile Error!\n");//DEBUG
  return 0;//错误处理机制
 }
 tData = (unsigned char*)malloc((unsigned int)(MAXSIZE+pLen-1+16)*sizeof(char));
 if(!tData) return -1;
 pData = (unsigned char*)malloc((unsigned int)(pLen+16)*sizeof(char));
 if(!pData) return -1;
 nextval = (int*)malloc((unsigned int)(pLen+16)*sizeof(int));
 if(!nextval) return -1;
 fread(pData, pLen, 1, pFile);
 get_nextval(pData,nextval,pLen);
 if(BlockNum==1)
 {
  ReadSize=(tlastlen)?tlastlen:BlockNum;
  fread(tData, ReadSize, 1, tFile);
  if((answer=Index_KMP(tData, pData,nextval,ReadSize,pLen))>=0)
   count+=answer;
 }
 else
 {
  fread(tData, MAXSIZE, 1, tFile);
  if((answer=Index_KMP(tData, pData,nextval,MAXSIZE,pLen))>=0)
   count+=answer;
  BlockNum=tlastlen?BlockNum:(BlockNum+1);
  for(i=0;i  {
   fseek(tFile,1-pLen,SEEK_CUR);
   fread(tData, MAXSIZE+pLen-1, 1, tFile);
   if((answer=Index_KMP(tData, pData,nextval,MAXSIZE+pLen-1,pLen))>=0)
    count+=answer;
  }
  if(tlastlen)
  {
   fseek(tFile,1-pLen,SEEK_CUR);
   fread(tData, tlastlen+pLen-1, 1, tFile);
   if((answer=Index_KMP(tData, pData,nextval,tlastlen+pLen-1,pLen))>=0)
    count+=answer;
  }
 }
 free(tData);
 free(pData);
 free(nextval);
 fclose(tFile);
 fclose(pFile);
 return count;
}
void main()
{
 clock_t start,end,total=0;
 double a;
 int all=0;
 char *p="p.txt";
 char *t="t.dat";
 printf("\nKMP String Searching Program");
 printf("\n====================================\n");
 start=clock();
 all=Serach(t,p);
 end=clock();
 total=end-start;
 a=(double)total/(double)CLOCKS_PER_SEC;
 printf("process time is %lf s\n",a);
 if(total==-1)
 {
  printf("alloc error!\n");
 }
 printf("find the number is %d .\n",all);
}
阅读(1643) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~