posts - 2,  comments - 8,  trackbacks - 0

题目描述: 
一个文件中存有空格分开的单词 
现在要将这个文件读入到另外一个文件,保存格式如下: 
live evil 
search casher 
.. 
就是含有相同字母的单词要放到一行。 
用c实现,可以使用fopen,fread,fwrite等 
接口: 
bool TransferDictionary(char * OriginalFile,char * NewFile);
  


网上一些大侠给出的解法的问题主要在于不能区分诸如ab,abb,babba等含有相同字母,但是字母出现次数不相同的情况

思路如下:
gHeadList是一个链表的头,其中的每一个HeadNode的child是一个指向同一类的word的链表(这些word含有相同的hashcode,即含有相同的字母种类并且各个字母的出现次数也相同),hashcode成员则保存该类word排序后的值;

具体解法如下:


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

bool    TransferDictionary(char * srcFile,char * destFile); 

//从源文件中读入数据
char*    ReadFile(const char* fname);

//将处理后的数据写到目的文件中
bool    WriteFile(const char* fname);

//得到一个word的hash码,实际就是返回word按字母排序后的字符串
char*    GetHashCode(char *word);

//将word插入到表中正确的位置
bool    InsertWord(char * word);

//释放空间
void    Free();


struct Node
{
    char *word;
    Node *next;
};
struct HeadNode
{
    char*        hashcode;
    Node*        child;
    HeadNode*    link;
};

HeadNode *gHeadList=NULL;

void Free()
{
    HeadNode *pHead=gHeadList,*pTmpHead=NULL;
    Node *pTmp=NULL;
    while(NULL != pHead)
    {    
        Node *pNode=pHead->child;
        while(NULL != pNode)
        {
            pTmp=pNode->next;
            free(pNode->word);
            free(pNode);
            pNode=pTmp;
        }
        
        pTmpHead=pHead->link;

        free(pHead->hashcode);
        free(pHead);
        pHead=pTmpHead;
    }
}

bool WriteFile(const char* fname)
{
    FILE *fp=NULL;
    fp = fopen(fname,"w");

    HeadNode* hTmp = gHeadList;
    Node *nTmp = NULL;

    while (hTmp != NULL)
    {
        nTmp = hTmp->child;

        if(nTmp == NULL )continue;

        fwrite(nTmp->word,sizeof(char),strlen(nTmp->word),fp);
        printf("\n%s",nTmp->word);

        nTmp=nTmp->next;
        while (nTmp!=NULL)
        {
            fwrite(" ",sizeof(char),1,fp);            
            fwrite(nTmp->word,sizeof(char),strlen(nTmp->word),fp);

            printf(" %s",nTmp->word);
            
            nTmp = nTmp->next;
        }
        fwrite("\n",sizeof(char),1,fp);

        hTmp = hTmp->link;
    }
    return true;
}

bool InsertWord(char * word)
{
    char *hashcode=GetHashCode(word);

    Node *pNode=(Node*)malloc(sizeof(Node));
    pNode->word=strdup(word);
    pNode->next=NULL;

    HeadNode *pHead=gHeadList;

    while(pHead != NULL)
    {
        if(0 == strcmp(pHead->hashcode,hashcode))
        {
            Node *pTmp=pHead->child;
            pHead->child=pNode;
            pNode->next=pTmp;
            return true;
        }

        pHead=pHead->link;
    }

    pHead=(HeadNode*)malloc(sizeof(HeadNode));    
    pHead->hashcode=strdup(hashcode);
    pHead->child=pNode;
    pHead->link=gHeadList;

    gHeadList=pHead;
    return true;
}

char* GetHashCode(char *word)
{
    char value[26]={0};
    int len=strlen(word);
    if(len<=0)return NULL;

    char *hashcode=(char*)malloc(len+1);
    int i=0;
    for(i=0;i<len;i++)
        value[word[i]-'a']+=1;

    int pos=-1;
    for(i=0;i<26;i++)
    {
        for(int j=0;j<value[i];j++)
            hashcode[++pos]='a'+i;
    }
    hashcode[len]='\0';

    return hashcode;
}

char* ReadFile(const char* fname)
{
    FILE *fp = fopen(fname,"r");
    if (fp == NULL)
    {
        perror("Open file failed!\n");
        exit(0);
    }

    fseek(fp,0L,SEEK_END);
    long fsize = ftell(fp);
    if (fsize==0L)
    {
        perror("The file is empty!\n");
        exit(0);
    }
    char *file_buf = (char*)malloc((size_t)fsize+1);
    rewind(fp);

    int Ret = fread(file_buf,sizeof(char),fsize,fp);

    if (Ret == 0)
    {
        return NULL;
    }

    file_buf[fsize] = '\0';

    return file_buf;
}


bool TransferDictionary(char * OriginalFile,char * NewFile)
{
    char * buf=ReadFile(OriginalFile);
    if(buf == NULL)return false;

    const char *delimer=" ";
    char * word=strtok(buf,delimer);
    while(word != NULL)
    {
        printf("Get a word:%s\n",word);

        InsertWord(strlwr(word));

        word=strtok(NULL,delimer);
    }

    WriteFile(NewFile);

    return true;
}


int main()
{
    char OriginalFile[100],TargetFile[100];

    memset(OriginalFile,0,100);
    memset(TargetFile,0,100);

    printf("Enter the original file name:");
    scanf("%s",OriginalFile);
    printf("Enter the target file name:");
    scanf("%s",TargetFile);

    TransferDictionary(OriginalFile,TargetFile);

    Free();

    return 0;
}
posted on 2007-06-28 21:24 Darkblue 阅读(1962) 评论(4)  编辑 收藏 引用

FeedBack:
# re: 一道微软的Mini-Test笔试题(一)
2007-06-29 09:44 | WarTalker
阁下的代码清晰明了,读后受益匪浅。  回复  更多评论
  
# re: 一道微软的Mini-Test笔试题(一)
2007-06-29 14:11 | SuperPlayeR
本来看到哗哗一长串代码就准备跳过的,看到1楼的评论说写的不错,又回头认真读了一遍,确实不虚此行,受教了~//bow //thanks  回复  更多评论
  
# re: 一道微软的Mini-Test笔试题(一)
2007-06-30 19:49 | 麦田守望者
强啊! 不知道题目在哪里获取的啊?  回复  更多评论
  
# re: 一道微软的Mini-Test笔试题(一)
2007-07-03 16:15 | Darkblue
@麦田守望者
题目也是在网上看见的,可能是以前参加mini-test的前辈带出来的吧
  回复  更多评论
  

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


<2022年9月>
28293031123
45678910
11121314151617
18192021222324
2526272829301
2345678

常用链接

留言簿(1)

随笔档案

最新评论

阅读排行榜

评论排行榜