`

百度之星 2005年 初赛题目四

 
阅读更多

第四题（共四题 100 分）：低频词过滤（ 40 分）

题目描述：请编写程序，从包含大量单词的文本中删除出现次数最少的单词。如果有多
个单词都出现最少的次数，则将这些单词都删除。

输入数据：程序读入已被命名为 corpus.txt 的一个大数据量的文本文件，该文件包含英
文单词和中文单词，词与词之间以一个或多个 whitespace 分隔。（为便于调试，您可下载
测试 corpus.txt 文件，实际运行时我们会使用不同内容的输入文件。）

输出数据：在标准输出上打印删除了 corpus.txt 中出现次数最少的单词之后的文本（
词与词保持原来的顺序，仍以空格分隔）。

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

 

思路：因为词汇的频率是一个未知数，在统计的过程中无法探知到哪些多哪些少，必须把所有的词汇进行统计才能统计出哪些词汇词频最低。故1、构造Hash表，对出现的词汇进行统计，统计词频。2、然后获取到词频最低的列表。3、对原文进行处理，剔除低频词汇。

 

 

GHash.h

#ifndef __GHASH_H_
#define __GHASH_H_
#include "GList.h"
#define HASHSIZE 512
typedef struct _Item
{
   char * key;
   char * value;
   unsigned int count;
   struct Item * next;
} Item;

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

#endif

 

GHash.c

 

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include "GHash.h"
#include "4lib.h"
//#include "GList.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 = (char*)strdup(key))
		       || NULL ==(np->value = (char*)strdup(value)) )
         {
             return NULL;
         }
         hashval = _Hash(key);
         np->next = (struct Item *)hashtab[hashval];
         hashtab[hashval] = (struct Item *)np;
     }
     else
     {
	  	 free(np->value);
	  	 if((np->value=(char *)strdup(value))== NULL)
	  	 {
		    return NULL;
         }
 	 }
 	 return np;
}

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;
}


int  HashIncrease(char * key)
{
 	 Item * np;
 	 unsigned int hashval;
 	 if((np=HashSearch(key))==NULL)
 	 {
         np=(Item *)malloc(sizeof(Item));
         if(NULL==np || NULL ==(np->key = (char *)strdup(key))
		    )
         {
             return -1;
         }
         hashval = _Hash(key);
         np->value=NULL;
         np->count=1;
         np->next = (struct Item *)hashtab[hashval];
         hashtab[hashval] = (struct Item *)np;
         return 1;
     }
     else
     {
	  	 np->count=np->count+1;
	  	 //free(np->value);
	  	 //if((np->value=strdup(value))== NULL)
	  	 //{
		 //   return NULL;
         //}
         return np->count;
 	 }
 	 return np->count;
}

int  HashRemove(char * key)
{
}



void GetMinList(List* glist)
{
 	 GListInit(glist);
 	 GListEmptyList(glist);
 	 int curmin=100;
 	 int i=0;
 	 for(i=0; i<HASHSIZE; i++)
 	 {
	     if(hashtab[i]!=NULL)
	     {
		    Item * tmp=hashtab[i];
		    while(tmp!=NULL)
		    {
			 	if(tmp->count==curmin)
			 	{
				 	GListAddNode(tmp->key,glist);		  
		        }
		        else if(tmp->count<curmin)
		        {
				 	 GListEmptyList(glist);
				 	 GListAddNode(tmp->key,glist);	
				 	 curmin=tmp->count;
	            }
	            tmp=tmp->next;
	        }
		 }
     }
}

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]=(struct Item *)(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:%d;",tmp->key,tmp->value,tmp->count);
			}
			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);
   item=NULL;
}

 

 

 GLish.h

 

#ifndef __GLIST_H_
#define __GLIST_H_
typedef struct _Node 
{
    char* data;
    struct _Node * next; 
} Node;
typedef struct _List
{
   int count; 
   Node * header;
} List;

void GListInit(List* glist);
void GListAddNode(char* data,List* glist);
void GListEmptyList(List * glist);
int GListGetCount(List* glist);
void GListPrint(List * glist);
#endif

 

 

   GLish.c

   

#include <stdio.h>
#include <stdlib.h>
#include "GList.h"
#include "4lib.h"
//static List glist ;
void GListInit(List* glist)
{
 	 glist->count=0;
 	 glist->header=NULL;
}
void GListAddNode(char* data,List* glist)
{
 	Node * node = (Node *)malloc(sizeof(Node));
 	//node->data=data;
 	node->data=(char *)strdup(data);
 	node->next=glist->header;
 	glist->header=node;
 	glist->count=glist->count+1;
}
int GetCount(List* glist)
{
 	return glist->count;
}
void FreeNode(Node * node)
{
 	 free(node->data);
 	 free(node);
 	 node=NULL;
}
void GListEmptyList(List * glist)
{
 	 Node* tmp;
 	 while(glist->header!=NULL)
 	 {
        tmp=glist->header;
        glist->header=tmp->next;
        //free(tmp);
        FreeNode(tmp);
     }
     glist->count=0;
     glist->header=NULL;
}

void GListPrint(List * glist)
{
 	 printf("GList:\n");
 	 Node* tmp=glist->header;
 	 while(tmp!=NULL)
 	 {
        printf("%s ",tmp->data);
        tmp=tmp->next;
     }
     printf("\n");
}

int GListSearch(char * data,List* glist)
{
 	Node* tmp=glist->header;
 	 while(tmp!=NULL)
 	 {
	    if(strcmp(data,tmp->data)==0)
     	    return TRUE;
	    else
            tmp=tmp->next;
     }
     return FALSE;
}

 

  4lib.h

  

#ifndef __4LIB_H_
#define __4LIB_H
#define TRUE 1
#define FALSE 0
char *strdup(const char *str);

#endif

4lib.c

char *strdup(const char *str)
{
    int n = strlen(str) + 1;
    char *dup = malloc(n);
    if(dup)
    {
        strcpy(dup, str);
    }
    return dup;
}

 

 

   main.c

  

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "GList.h"
#include "GHash.h"
#include "4lib.h"
#define INPUT "4.input.txt"
#define READBUFSIZE 513
#define FREADSIZE ((READBUFSIZE-1))
#define KEEPBUFSIZE (READBUFSIZE*2)
char keepbuf[KEEPBUFSIZE];
extern int  HashIncrease(char * key);
void HandlerItem(const char *item)
{
 	//printf(" %s\n",item);
 	HashIncrease(item);
}

void HanlderBuf(const char * buf)
{
 	 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);
	   	  }
          tmp=next;
          
     }
}

void HandlerItemout(char *item,List * glist)
{
    if(GListSearch(item,glist)==FALSE)
		  printf(" %s ",item);
 	//HashIncrease(item);
}

void HanlderBufout(char * buf,List * glist)
{
 	 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
	      {
		   	  HandlerItemout(tmp,glist);
	   	  }
          tmp=next;
          
     }
}


int main(int argc, char *argv[])
{
  FILE * f=fopen(INPUT,"r+");
  if(NULL==f)
  {
	 perror("Open file:");
  }
  
  GHashInit();
  
  char readbuf[READBUFSIZE];
  memset(keepbuf,'\0',KEEPBUFSIZE);
  memset(readbuf,'\0',READBUFSIZE);
  int readnum;
  while((readnum=fread(readbuf,sizeof(char),FREADSIZE,f))>0)
  {
      readbuf[readnum]='\0';
      //printf("%d\n",readnum);
      if(readnum<FREADSIZE)
      {
	      if(feof(f)!=0)//end file
	      {
	         HanlderBuf(readbuf);
	         break;
	      }
          else
          {
		   	  perror("Error!");
	   	  }
	  }
	  else if(readnum==FREADSIZE)
	  {
	   	   HanlderBuf(readbuf);
      }
  }
  
  if(strlen(keepbuf)>0)
    HandlerItem(keepbuf);
  fclose(f);
  PrintGHash();

  List glist;
  GetMinList(&glist);
  printf("list count:%d\n",GetCount(&glist));
  GListPrint(&glist);
  
  FreeGHash();
  
  //hanlde the input
  f=fopen(INPUT,"r+");
  if(NULL==f)
  {
	 perror("Open file:");
  }
  memset(keepbuf,'\0',KEEPBUFSIZE);
  memset(readbuf,'\0',READBUFSIZE);
  readnum;
  while((readnum=fread(readbuf,sizeof(char),FREADSIZE,f))>0)
  {
      readbuf[readnum]='\0';
      //printf("%d\n",readnum);
      if(readnum<FREADSIZE)
      {
	      if(feof(f)!=0)//end file
	      {
	         HanlderBufout(readbuf,&glist);
	         break;
	      }
          else
          {
		   	  perror("Error!");
	   	  }
	  }
	  else if(readnum==FREADSIZE)
	  {
	   	   HanlderBufout(readbuf,&glist);
      }
  }
  
  if(strlen(keepbuf)>0)
    HandlerItemout(keepbuf,&glist);
  fclose(f);
  
  GListEmptyList(&glist);
  system("PAUSE");	
  return 0;
}

 

 

   该解决方案不包含的内容：

   1、 在对词汇进行统计的时，未记录词汇的位置，造成在提出低频词汇时需要再次比对，可以提升

   2、 仅适用于最低频的，无法针对词频范围。如果需要则可以修改为HashTable的冲突列表为顺序列表

   3、 无法获得每个低频词汇的出现的顺序

   4、 替换低频词汇效率不高

 

 

 

 

 

 

 

 

 

 

0
顶
0
踩
分享到：
| conflicting types for
评论
发表评论

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

相关推荐

    百度之星题目（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