<The practice of Programming>markov链.keywords: hash table

random_file.c

/*
#include <stdio.h>
#define FILEPATH "/Users/tinylamb/Documents/coding/santi.txt"
int main(){
    FILE *fp;
    fp=fopen(FILEPATH,"r");
    char c;
    while((c=fgetc(fp))!=EOF)
        printf("%c",c);
    fclose(fp);
    return 0;
}*/

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>
#define FILEPATH "/Users/tinylamb/Documents/coding/ba.txt"

enum{
    NPRE=2,
    NHASH=4093,
    MAXGEN=140,
    SUFINIT=1000,
    INCRE=1000,
    MULTI=31
};
typedef struct State State;
struct State{
    char pref[NPRE];
    char *suf;
    unsigned count;
    unsigned size;
    State *next;
};
State *statetab[NHASH];

unsigned hash(char prefix[NPRE]);
void build(char prefix[NPRE],FILE *fp);
void add(char prefix[NPRE],char c);
State *lookup(char prefix[NPRE],int create);
void addsuffix(State *sp,char c);
void generate(char prefix[NPRE],int nwords);

char NONWORD='\n';
int main(){
    int i,nwords=MAXGEN;
    char prefix[NPRE];
    
    long seed;
    seed=time(NULL);
    srand(seed);

    for (i = 0; i < NPRE; i++)	/* set up initial prefix */
        prefix[i] = NONWORD;
    FILE *fp=fopen(FILEPATH,"r");
    build(prefix, fp);
    add(prefix, NONWORD);

    printf("input two words:\n");
    for(i=0;i<NPRE;i++)
        scanf("%c",prefix+i);
    generate(prefix,nwords);
    fclose(fp);
    return 0;


}


unsigned hash(char prefix[NPRE]){
    unsigned h;
    char c;
    int i;
    for(i=0,h=0;i<NPRE;i++){
        c=prefix[i];
        h=MULTI*h+c;
    }
    return h % NHASH;
}

void build(char prefix[NPRE],FILE *fp){
    char c;
    while((c=fgetc(fp))!=EOF)
        if(c!=' '|| c!='\n')
            add(prefix,c);
}

void add(char prefix[NPRE],char c){
    State *sp;
    sp=lookup(prefix,1);
    addsuffix(sp,c);
    memmove(prefix,prefix+1,(NPRE-1)*sizeof(prefix[0]));
    prefix[NPRE-1]=c;
}

State *lookup(char prefix[NPRE],int create){
    int i;
    unsigned h;
    State *sp;
    h=hash(prefix);
    for(sp=statetab[h];sp!=NULL;sp=sp->next){
        for(i=0;i<NPRE;i++)
            if(prefix[i]!= sp->pref[i])
                break;
        if(i==NPRE)
            return sp;
    }
    if(create){
        sp=malloc(sizeof(State));
        for(i=0;i<NPRE;i++)
            sp->pref[i]=prefix[i];
        sp->size=SUFINIT;
        sp->suf=malloc(sp->size *sizeof(char));
        sp->count=0;
        sp->next=statetab[h];
        statetab[h]=sp;
    }
    return sp;
}

void addsuffix(State *sp,char c){
    sp->suf[sp->count++]=c;
    if(sp->count==sp->size){
        char *s;
        sp->size+=INCRE;
        s=realloc(sp->suf,sp->size *sizeof(char));
        if(s)
            sp->suf=s;
        else
            printf("realloc failed.\n");
    }
}

void generate(char prefix[NPRE],int nwords){
    State *sp;
    char w;
    int i,match;
    for(i=0;i<nwords;i++){
        sp=lookup(prefix,0);
        if(sp==NULL){
            printf("look up failed\n");
            break;
        }
        match=sp->count;
        if(match==0){
            printf("no suffix\n");
            break;
        }
        w=sp->suf[rand()%match];
        printf("%c",w);
        memmove(prefix,prefix+1,(NPRE-1)*sizeof(prefix[0]));
        prefix[NPRE-1]=w;
    }
}

https://www.clear.rice.edu/comp200/13spring/notes/18/shaney.shtml
Mark V Shaney