プログラマ専用SNS ミクプラ

コード:

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<ctype.h>
#define MAXWORDLENGTH 80
#define NBRANCHES ('Z'-'A'+2)	//　27のこと, ASCII文字の時

typedef struct{
	int num;
	void *ptr[NBRANCHES];	//	子とデータの2種類指すため void 型
}branchnode;

typedef struct{
	int num;
	char *key;
}datanode;

typedef branchnode *brptr;
typedef datanode *dataptr;

void error(char *str)
{
	printf("\nError: %s\n", str);
	exit(1);
}

void printtrie(void *p)
{
	dataptr dp = (dataptr) p;

	void *q;
	int k;

	if(dp->num)					//	num > 0 のとき、pはデータノードを指す
		printf("%5d %s\n", dp->num, dp->key);
	else						//	num = 0 のときは、pは分岐ノードを指す
		for(k = 0; k < NBRANCHES; k++){
			if((q = ( ( brptr ) p)->ptr[k] ) != NULL )		//	(brptr) p で分岐ノードに変換
				printtrie(q);
		}
}

dataptr found(void *p, char *word)
{
	int i = 0, k;
	char ch;

	dataptr dp = (dataptr) p;	//	データノードの場合
	brptr bp = (brptr) p;		//	分岐ノードの場合

	while(p != NULL && bp->num == 0){
		ch = word[i++];
		k = (ch ? ch - 'A' + 1 : 0);			//	アルファベットが何番目か(ch = Aのときは1番目, Zのときは26番目e.t.c.)
		if(k < 0 || k >26)				//	アルファベット以外のとき
			return NULL;

		p = bp->ptr[k];						
		bp = (brptr) p;						
	}	

	dp = (dataptr) p;
	return (p == NULL ? NULL : strcmp(word, dp->key) == 0 ? dp : NULL);
	
}

brptr newbrnode(void)
{
	brptr bp;
	int k;

	bp = (brptr) malloc(sizeof(branchnode));
	if(bp == NULL)
		error("Not enough memory");

	bp->num = 0;
	for(k = 0; k < NBRANCHES; k++){
		bp->ptr[k] = NULL;
	}
	return bp;
}

dataptr newdatanode(char *word)
{
	char *pch;
	dataptr dp;

	dp = (dataptr) malloc(sizeof(datanode));
	pch = (char *) malloc(strlen(word) + 1);

	if(dp == NULL || pch == NULL)
		error("Not enough memory");
	
	strcpy(pch, word);
	dp->num = 1;
	dp->key = pch;

	return dp;
}

void insert(void **pp, char *word, int i)	//	wordをトライ木に挿入。引数ppはこのトライ木の根のアドレスを含んでいる。
{
	char ch, ch1;
	brptr bp, bp1;
	dataptr dp;
	int k, k1;

	for(;;){
		if(*pp == NULL){
			*pp = (void *)newdatanode(word);
			break;
		}	
		bp = *(brptr *) pp;		//	分岐ノードの場合
		dp = *(dataptr *) pp;		//	データノードの場合
		ch = word[i];
		k = (ch ? ch - 'A' + 1 : 0);
				
		if(bp->num == 0)		//	分岐ノード
			pp = &bp->ptr[k];
		else{				//	データノード
			if(strcmp(word, dp->key) == 0){
				dp->num++;
				break;
			}
			bp1 = newbrnode();
			*pp = (void *) bp1;
			ch1 = dp->key[i];	//	既存のデータノードの文字
			k1 = (ch1 ? ch1 - 'A' + 1 : 0);
			bp1->ptr[k1] = (void *) bp;
			pp = &bp1->ptr[k];
		}
		i++;
	}
}

int getword(FILE *fp, char *str)
{
	int ch, i=0;
	
	while(ch = getc(fp), ch != EOF && !isalpha(ch));	//	英字でない文字を読み飛ばす

	while(isalpha(ch)){					//	英字が続く限りstrに読み込む
		str[i++] = toupper(ch);
		ch = getc(fp);
		if(i > MAXWORDLENGTH)
			error("Word too long");
	}
	str[i] = '\0';
	return i;
}

int main(void)
{
	FILE *fp;
	char filename[51], word[MAXWORDLENGTH + 1];
	void *root;
	dataptr q;

	printf("Input file : ");
	scanf("%50s", filename);

	fp = fopen(filename, "r");
	if(fp == NULL)
		error("File not available");

	root = NULL;
	while(getword(fp, word) > 0)
		insert(&root, word, 0);
	fclose(fp);

	printf("\nContents of file:\n");
	
	if(root != NULL)
		printtrie(root);
	
	while( printf("\nEnter a word, or type STOPSEARCH to stop: "), getword(stdin, word), strcmp(word, "STOPSEARCH") ){
		q = found(root, word);
		if(q == NULL)
			printf("key not found\n");
		else
			printf("key found : count field = %d\n", q->num);
	}
				
	return 0;
}