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

typedef struct sWORD {
	char *spelling;		 // the word spelling
	int count;			 // number of times the word has been used
	struct sWORD *next;
} WORD;

void read(WORD **txt);					// read the data	
int search(WORD *txt, char *oneword);	// search a word in the linked list

int main () {
/*
	txt : the main linked list to store words.
	reg : register
	i	; looping index
*/
	WORD *txt=NULL, *reg;
	int i;
	read(&txt);
	// show the times which every word appears.
	for (reg = txt, i=0; reg; reg = reg->next) {
		if (i>0 && i%4 == 0)
			printf("\n");
		printf("%-20s %3d  ", reg->spelling, reg->count);
		i++;
	}
	printf("\n");
	return 0;
}

void read(WORD **txt) {
	/*
		head	: the head of linked list
		tail	: the tail of linked list
		reg		: register
		pre		: the preveious node
		oneword	: store one word temporarily in array
		ch		: store one char temporarily in character
		i, j	: looping index
	*/
	WORD *head = NULL, *tail, *reg, *pre, *newnode = NULL;
	char oneword[50], ch;
	int i = 0;
	// read the data untill the end of file
	while ((ch = getchar()) != EOF ) {
		/*	I store the data word by word, but the word only can be
			composed by alphebat or number or '\'' or '-', by the way,
			the prefix only can be alphebat or number.
		*/
		if (((ch >= 'a' && ch <= 'z') || (ch >= 'A' && ch <= 'Z') 
		|| (ch >= '0' && ch <= '9') || ch == '\'' || ch == '-')) {
			if (!(i==0 && (ch == '\'' || ch == '-')))
			oneword[i++] = ch;
		}
		else {
			oneword[i] = '\0';
			/*	If one word has been made, test whether this word has
				appeared in the list.
			*/
			if (i) {	//	if oneword is made
				if(search(head, oneword)){	// If search success.
					// make the word's count plus one.	
					for (reg = head; reg; reg=reg->next)
						if (strcmp(reg->spelling, oneword) == 0)
							reg->count++;				
				}
				else {// If search fail, make one newnode to store word

					if(strcmp("a",oneword)==0) {	// debug
						printf("before:\n");
						for (reg = head, i=0; reg; reg = reg->next) {
							if (i>0 && i%4 == 0)
							printf("\n");
						printf("%-20s %3d  ", reg->spelling, reg->count);
						i++;
						}
						printf("----------------------------\n\n");
					}
					newnode = (WORD*)malloc(sizeof(WORD));
					if (newnode==NULL) {
						printf("memory unenough\n");
						return;
					}
					newnode->spelling=malloc(sizeof(strlen(oneword)+1));
					strcpy(newnode->spelling, oneword);
					newnode->next = NULL;
					newnode->count = 1;	
					/* to arrange data in order, I insert the node in order
						while I make it.
					*/
					if (head == NULL) {// If the list has'nt made
						head = newnode;
						tail = newnode;
					}
					else {// if the list has made.
					//	lexicographically sorting here
						for(reg=head, pre=NULL;
							reg && strcmp(oneword, reg->spelling) > 0;
							pre=reg, reg=reg->next);
						// If the newnode has to be inserted front the head
						if (reg == head) {
							newnode->next = head;
							head = newnode;
						}
						// If the newnode has to be inserted after the tail
						else if (reg == tail) {
							tail->next = newnode;
							tail = newnode;
						}
						// If the newnode has to be insert in the middle
						else {
							pre->next = newnode;
							newnode->next = reg;
						}
						if(strcmp("a",oneword)==0) {	//debug
							printf("after:\n");
							for (reg = head, i=0; reg; reg = reg->next) {
								if (i>0 && i%4 == 0)
									printf("\n");
							printf("%-20s %3d  ", reg->spelling, reg->count);
							i++;
							}
							printf("++++++++++++++++++++++++++++++\n\n");
						}
					}
				}
			}

			// reset
			for (i=0; i<50; i++)
				oneword[i] = '\0';
			i = 0;
		}
	}
	//	reconnect linked list
	*txt = head;
}
// This function will search a word in the linked list.
int search(WORD *txt, char *oneword) {
	WORD *reg; // register
	if (txt == NULL){	// If the list is nothing
		return 0;
	}
	for (reg = txt; reg; reg = reg->next) {
		if (strcmp(reg->spelling, oneword) == 0) {	// find the word.
			return 1;
		}
	}
	return 0;		// doesn't find the word.
}