searching_words_with_hashing.c

#include <stdio.h>
#include <stdlib.h>
#define SIZE 997					//Tablo Büyüklüğü.
#define WORD_BUFFER 50				//Alınan kelime için maks boyut.
#define HORNER_NUMBER 11			//Horner metodundaki kat sayı.

typedef struct node {
	char documentName[WORD_BUFFER]; //Doküman Adı
	struct node* next;				//Sonraki adres
}NODE;

typedef struct hash {
	char word[WORD_BUFFER];			//Kelime
	NODE* documentNameHead;			//Doküman adlarını tutan linked listin başı
}HASH;

typedef struct hashtable {
	HASH table[SIZE];				//Hash tablosu
	float loadfactor;				//doluYer/SIZE
	int indexCounter;				//doluYer
}HASHTABLE;

void prepareHashTable(HASHTABLE* hashTable);					//HashTablosunda alana tanımlamaları ve default değerler ayarlanır.
int hash1(long unsigned int key);								//1. hash fonksiyonu  h1(key) = key mod M	(index döner).
int hash2(long unsigned int key);								//2. hash fonksiyonu  h2(key) = 1 + (key mod MM)	(index döner).
void readFile(FILE* fp, HASHTABLE* hashTable, char filename[]);		//Kelimeleri okumak için.
int insertToHash(HASHTABLE* hashTable, long unsigned int key, char filename[WORD_BUFFER], char wrd[WORD_BUFFER]);		//Kelimelerei HashTablosuna almak için.	 (Tablonun dolup dolmadığı döner.)
long unsigned int horner(char word[WORD_BUFFER]);					//Kelimelerin indexini hesaplarken sayıya dönüşümü için.	(kelimenin sayı hali döner).
void printHashTable(HASHTABLE* hashTable);							//Debug için hash tablosu yazdırma.
void addDocumentName(NODE* head, char filename[WORD_BUFFER]);		//Hash tablosundaki kelimeye doküman adı ekleme.
void saveHashTable(HASHTABLE* hashTable);							//Hash tablosunu .txt olarak yazar.
HASHTABLE* readHashFile(FILE* hashFile);							//Dosyadan hash tablosu okuma.	(Hash tablosu döner.)
void findWord(HASHTABLE* hashTable, char wrd[WORD_BUFFER]);

int main() {

	int choice;		//Menü seçimleri için
	int quit = 0;	//Çıkış için
	char filename[WORD_BUFFER];		//Dosya adı
	HASHTABLE* hashTable;			//Hash tablosu
	FILE* fp;
	FILE * hashFile = fopen("17011033.txt", "r+");		//Hazır hash tablosu var mı kontrolü.
	if (hashFile != NULL) {
    	printf("Hazir HashTable bulundu. Yukleniyor.\n");
        hashTable = readHashFile(hashFile);				//Hash tablosu okunur.
        fclose(hashFile);
    }
    else{
    	printf("Hashtable bulunamadi olusturuluyor.\n");
    	hashTable = (HASHTABLE*)malloc(sizeof(HASHTABLE));	//Hash tablosu oluşturuldu.
		prepareHashTable(hashTable);					
	}
	while(!quit){		
		printf("\nLoadfactor : %f\n1.Dokuman ekleme.\n2.Kelime Arama.\n3.Cikis.\n", hashTable->loadfactor);
		scanf("%d", &choice);
		system("CLS");
		if (choice == 1) {
			printf("Dokumanda kelimeler arasinda tek bosluk olduguna ve ozel karakterlerin bulunmadigina dikkat ediniz.\nDosya adi giriniz (input.txt) : ");
			scanf("%s", filename);
			fp = fopen(filename, "r");					//Doküman açıldı.
			if (fp == NULL) {
				printf("Dosya bulunamadi.");
				return 0;
			}
			readFile(fp, hashTable, filename);			//Döküman okundu ve hashe eklendi.
			fclose(fp);									//Döküman kapatıldı.
			saveHashTable(hashTable);					//Hash dosyasına kaydedildi.
			printf("\nDokuman eklendi.\n");
			//printHashTable(hashTable);				//Debug için
		}
		else if (choice == 2) {
			char word[WORD_BUFFER];
			printf("Aranicak kelimeyi giriniz : ");
			scanf("%s", word);
			findWord(hashTable, word);					//Kelime arama
		}
		else {
			quit=1;										//Çıkış
		}
	}
	return 0;
}

void findWord(HASHTABLE* hashTable, char wrd[WORD_BUFFER]){
	int i = 0;
	int index;										//hash fonksiyonundan dönecek değeri tutucak.
	long unsigned int key = horner(wrd); 					//Kelimenin sayı karşılığı alındı.
	do {
		index = (hash1(key) + (i * hash2(key))) % SIZE;		//Hash fonksiyonlarıyla indexi bulundu.
		i++;
	} while (strcmp(hashTable->table[index].word, "-") && strcmp(hashTable->table[index].word, wrd) && i<SIZE);
	//Yukardaki döngü boş bir yer veya aynı kelimeyi bulana kadar döner.

	if(!strcmp(hashTable->table[index].word, wrd)){			//Aynı kelime tabloda varsa.
		NODE* current = hashTable->table[index].documentNameHead;
		printf("Bulundu %s iceren dokumanlar : ", wrd);		//Dökümanlar yazdırılır.
		while(current != NULL){
			printf(" %s ", current->documentName);
			current = current->next;
		}
	}
	else{
		printf("Bulunamadi.");
	}
	printf("\n");
}

HASHTABLE* readHashFile(FILE* hashFile){
	int i;
	char buffer[WORD_BUFFER];										//Dosyadan okunan kelimeleri tutan değişken.
	HASHTABLE* hashTable = (HASHTABLE*)malloc(sizeof(HASHTABLE));	//Hash tablosu için alan açılır.
	prepareHashTable(hashTable);									//Hash tablosu hazırlanır.
	fscanf(hashFile,"%f\n",&(hashTable->loadfactor));				//loadfactor okunur.
	fscanf(hashFile,"%d\n",&(hashTable->indexCounter));				//IndexCounter okunur.
	for(i=0;i<SIZE;i++){
		fscanf(hashFile, "%s", &buffer);							//Kelime okunur
		strcpy(hashTable->table[i].word, buffer);					//Tabloya alınır.
		fscanf(hashFile, "%s", &buffer);							//Boşluk geçilir.
		while(strcmp(buffer, ";")){									// ';' gelen kadar dosya isimlerini okur.
			addDocumentName(hashTable->table[i].documentNameHead, buffer);	// Dosya isimlerini ilgili kelimenin structına ekler. 
			fscanf(hashFile, "%s", &buffer);
		}
	}
	return hashTable;
}
void saveHashTable( HASHTABLE* hashTable){
	int i;
	FILE* hashFile= fopen("17011033.txt", "w+");					//Dosya sıfırlanır / açılır.
	fprintf(hashFile,"%f\n",hashTable->loadfactor);					//Loadfactor yazılır.
	fprintf(hashFile,"%d\n",hashTable->indexCounter);				//Indexcounter yazılır.
	for(i=0;i<SIZE;i++){
		fprintf(hashFile,"%s ", hashTable->table[i].word);			//Kelime yazılır.
		NODE* current = hashTable->table[i].documentNameHead;		
		while(current!=NULL){										//İlgili dökümanlar yazılır.
			fprintf(hashFile,"%s ",current->documentName);
			current = current->next;
		}
		fprintf(hashFile,";\n");									//Satır sonuna geldiğimizi belirten işaret konur.
	}
}

void printHashTable(HASHTABLE* hashTable) {							//Debug için kullanıldı. Kontrol etmek isterseniz k
	int i,j;
	for (i = 0; i < SIZE; i++) {
		printf("%d - %s - ", i + 1, hashTable->table[i].word);
		NODE* current = hashTable->table[i].documentNameHead;
		while(current != NULL){
			printf(" %s - ", current->documentName);
			current = current->next;
		}
		printf("\n");
	}
	printf("\nLoadFactor : %f", hashTable->loadfactor);
	printf("\nTabloda dolu alan sayisi : %d\n", hashTable->indexCounter);
}

long unsigned int horner(char word[WORD_BUFFER]) {
	int i = 0;
	long unsigned int total = 0;								//Toplamı tutucak.
	long int multiple = 1;							//Her harfin çarpılcağı değişken.
	char letter;
	while (word[i] != NULL) {
		if (word[i] >= 65 && word[i] <= 90) {
			letter = word[i] - 'A';					//Büyük harfse 'A' çıkarılır.
		}
		else {
			letter = word[i] - 'a';					//Küçük harfse 'a' çıkarılır.
		}
													//En sonra oluşucak sayıyı küçültmüş oldum.
		total = total + (letter * multiple);
		multiple *= HORNER_NUMBER;
		i++;
	}
	return total;
}

void addDocumentName(NODE* head, char filename[WORD_BUFFER]){
	NODE* current = head;													//Doküman listesinin başını tutar.
	while(current->next != NULL && strcmp(current->documentName, filename)){
		current = current->next;											//Doküman linked list tinin sonuna kadar ilerler
	}
	if(current->next == NULL && strcmp(current->documentName, filename)) {
		NODE* newNode = (NODE*)malloc(sizeof(NODE));
		strcpy(newNode->documentName, filename);							//Dökümanı ekler.
		newNode->next = NULL;
		current->next = newNode;
	}
	
}

int insertToHash(HASHTABLE* hashTable, long unsigned int key, char filename[WORD_BUFFER], char wrd[WORD_BUFFER]) {
	int i;
	int index;															//Hashten dönen index.
	if (hashTable->loadfactor < 1) {
		if (hashTable->loadfactor > 0.8) {
			printf("LOADFACTOR 0.8 den büyük. UYARI!!!!");				//LoadFactor kontrolü.
		}
		i = 0;
		do {
			index = (hash1(key) + (i * hash2(key))) % SIZE;				//Hash fonksiyonlarından dönen index.
			i++;
		} while (strcmp(hashTable->table[index].word, "-") && strcmp(hashTable->table[index].word, wrd) && i<SIZE);	//Boş alan veya kelimenin aynısını bulunca çıkıcak.

		if (!strcmp(hashTable->table[index].word, "-")) {
			strcpy(hashTable->table[index].word, wrd);			//Boş yer bulundu.
			(hashTable->indexCounter)++;						//Boş yeri doldurduğumuz için artırdık.
			
		}
		addDocumentName(hashTable->table[index].documentNameHead, filename);	//Döküman adı eklenir.
		hashTable->loadfactor = (float) (hashTable->indexCounter) / SIZE;		//Loadfactor güncellenir.
	}
	else {
		printf("TABLO DOLU.");
		return 0;
	}
	return 1;
}

void readFile(FILE* fp, HASHTABLE* hashTable, char filename[WORD_BUFFER]) {
	char buffer[WORD_BUFFER];									//Kelimeyi tutucak değişken.
	int flag = 1;												//Loadfactorün kontrol ettiği flag.
	long unsigned int key;												//Kelimenin sayı karşılığı.
	while (flag && fscanf(fp, "%s", buffer) != EOF) {
		key = horner(buffer);									//Kelime sayıya çevrilir.
		flag = insertToHash(hashTable, key, filename, buffer);	//Hash tablosuna eklenir. Flag hash tablosunun dolup dolmadığını kontrol eder.
	}
	if (!flag) {
		printf("Tablo doldu. Taşan veriler : \n");
		while (flag && fscanf(fp, "%s", buffer) != EOF) {		//Taşan veriler yazdırılır.
			printf("%s", buffer);
		}
	}
}

void prepareHashTable(HASHTABLE* hashTable) {
	int i;
	for (i = 0; i < SIZE; i++) {
		strcpy(hashTable->table[i].word,"-");								//Boş alanlara -1 yazılır.
		hashTable->table[i].documentNameHead = (NODE*)malloc(sizeof(NODE));	//Doküman linked list için head tanımlanır.
		hashTable->table[i].documentNameHead->next = NULL;					//Next null yapılır.
		strcpy(hashTable->table[i].documentNameHead->documentName,"");		// Doküman adına default değer verilir.
	}
	hashTable->indexCounter = 0;											
	hashTable->loadfactor = 0;
}

int hash1(long unsigned int key) {
	return (key % SIZE);													//Birinci hash fonksiyonu.
}

int hash2(long unsigned int key) {
	return (1 + (key % (SIZE - 1)));										//İkinci hash fonksiyonu.
}