|
#include <stdio.h>
#include <stdlib.h>
#define MAX_TERM 10
#define MAX_LEN 100
#define HASH_N 13
typedef struct term
{
char str[MAX_TERM];
int id;
struct term* next;
}TERM;
typedef struct set
{
TERM* term;
struct set* next;
}SET;
typedef struct hash
{
char* key;
struct hash* next;
}HASH;
HASH* H[HASH_N];
void init_term(TERM** T)
{
*T = (TERM*)malloc(sizeof(TERM));
memset((*T)->str, 0, MAX_TERM);
(*T)->id = 0;
(*T)->next = NULL;
}
void init_set(SET** S)
{
*S = (SET*)malloc(sizeof(SET));
(*S)->term = NULL;
(*S)->next = NULL;
}
void init_hash()
{
int i;
for(i=0;i<HASH_N;i++)
{
H[i] = (HASH*)malloc(sizeof(HASH));
H[i]->key = NULL;
H[i]->next = NULL;
}
}
int get_term_id(char* term_id, TERM* T)
{
char* tmp = term_id;
TERM* p = (TERM*)malloc(sizeof(TERM));
int i = 0;
while(tmp[i]!='\0')
{
i++;
if(tmp[i] == '_')
{
tmp[i] = '\0';
sprintf(p->str, "%s", tmp);
p->id = atoi(tmp+i+1);
}
}
p->next = T->next;
T->next = p;
return 0;
}
int process_line(char* line,SET* S)
{
int i = 0;
char* line_tmp = line;
TERM* T = NULL;
SET* p = (SET*)malloc(sizeof(SET));
init_term(&T);
char term[MAX_TERM];
while(line_tmp[i] != '\0')
{
i++;
if(line_tmp[i] == ' ')
{
snprintf(term, i, "%s", line_tmp);
term[i] = '\0';
get_term_id(line_tmp,T);
i++;
line_tmp += i;
i = 0;
}
if(line_tmp[i] == '\0')
{
//line_tmp[i-1]='\0';
get_term_id(line_tmp,T);
break;
}
}
p->term = T;
p->next = S->next;
S->next = p;
return 0;
}
void print_set(SET* S)
{
SET* p = S->next;
while(p!=NULL)
{
TERM* q = p->term->next;
while(q!=NULL)
{
printf("term:%s\tid:%d\n", q->str, q->id);
q = q->next;
}
p = p->next;
}
}
void print_hash()
{
int i;
for(i=0;i<HASH_N;i++)
{
HASH* p = H[i]->next;
while(p!=NULL)
{
printf("hash str is %s\n",p->key);
p = p->next;
}
}
}
unsigned int BKDRHash(char* str)
{
unsigned int seed = 131;
unsigned int hash = 0;
while(*str)
{
hash = hash*seed + *str++;
}
return hash&0x7FFFFFFF;
}
void add_hash(char* term)
{
//printf("term is %s\n", term);
unsigned int hash_num = BKDRHash(term);
HASH* p = (HASH*)malloc(sizeof(HASH));
p->key = term;
hash_num %= HASH_N;
p->next = H[hash_num]->next;
H[hash_num]->next = p;
}
void process_input(char* line)
{
char* tmp_line = line;
int i = 0;
while(tmp_line[i]!='\0')
{
i++;
if(tmp_line[i]==' ')
{
char* term = (char*)malloc(MAX_TERM);
snprintf(term, i, "%s", tmp_line);
term[i] = '\0';
add_hash(term);
i++;
tmp_line += i;
i = 0;
}
if(tmp_line[i]=='\0')
{
tmp_line[i-1]='\0';
add_hash(tmp_line);
break;
}
}
}
int exist(char* str)
{
unsigned int hash_num = BKDRHash(str);
hash_num %= HASH_N;
HASH* p = H[hash_num]->next;
while(p!=NULL)
{
if(strcmp(str,p->key) == 0)
return 1;
}
return 0;
}
int judge_terms(SET* S)
{
SET* p = S->next;
while(p!=NULL)
{
TERM* q = p->term->next;
while(q!=NULL)
{
if(exist(q->str))
{
if(q->next == NULL)
return q->id;
q = q->next;
}
else
break;
}
p = p->next;
}
return -1;
}
int main(int argc, char *argv[])
{
int ret = 0;
SET* S = NULL;
init_set(&S);
char line[MAX_LEN];
init_hash();
FILE* fp = fopen("term.txt","r");
while(fgets(line, MAX_LEN, fp))
{
process_line( line, S);
}
print_set(S);
printf("Please input the terms you want:\n");
fgets(line, MAX_LEN, stdin);
printf("you input is %s\n",line);
process_input(line);
print_hash();
ret = judge_terms(S);
printf("ret is %d\n",ret);
fclose(fp);
system("PAUSE");
return 0;
}
|
