Консультации Портала - Консультация #173765

Задать вопрос Консультации Пользователи Форум

Задать вопрос экспертам

Консультация № 173765

27.10.2009, 18:41

25.00 руб.

0 13 1

Компьютеры Программирование

Здравствуйте уважаемые эксперты! Прошу помощи у тех кто разбирается как в Си так и в Си++. Мне нужно перевести код с С++ на Си (чтобы скомпилировать в Turbo C). Сколько не пытался сам перевести, все никак не хочет компилироваться.
Ниже задание и готовое решение на "borland c++ builder 6". Буду ОЧЕНЬ рад если удастся это сделать и скажу Большооое спасибо :).

Задача.
1. Построить хэш-таблицу методом линейных проб для слов заданного текста. Текст находится в некотором файле (примерно 200 слов). Экспериментально определить минимально необходимый объем хэш-таблицы и число коллизий при построении.
2. Построить хэш-таблицу методом квадратичных проб для слов заданного текста. Файл с текстом должен быть тот же, что и п.1. Экспериментально определить минимально необходимый объем хэш-таблицы и число коллизий при построении.

Приложение:
#include <vcl.h>
#include <stdio.h>
#include <stdlib.h>
#include <fstream.h>
#include <string.h>
using std::ifstream;
#pragma hdrstop

//---------------------------------------------------------------------------

const int maxn=10000;
struct node
{
char znac[20];
int key;
};

int kolcol;
int kolsl;
int ObTable;

node hashtable[maxn];

int myhash(char* s)
{
int result=0;
for (unsigned int i=0; i<strlen(s); i++)
{
result=(255*result+abs(s[i]))%kolsl;
}
return result;
}

//линейные пробы
int linhash(char* s)
{
//получаем хэш-код слова
int hs=myhash(s);
int num=hs;
//идем по массиву пока не найдем ему место
//сразу же считаем количество коллизий
while (true)
{
//если в ячейке таблицы уже есть значение
//то коллизия и переходим к следующему полю
if (hashtable[num].key!=0)
{
kolcol++;
//строки равны то выходим
if (strcmp(hashtable[num].znac,s)==0) break;
num++;
//если вышли за пределы хэш-таблицы, то увеличиваем ее размер
if (num>kolsl && num<kolsl) kolsl=num;
if (num>maxn) num=num%maxn;
}
else
{
ObTable++;
strcpy(hashtable[num].znac,s);
hashtable[num].key=hs;
break;
}
}
return 0;
}

//квадратичные пробы
int kvhash(char* s)
{
//получаем хэш-код слова
int hs=myhash(s);
int num=hs;
int zn=1;
int i=1;
//идем по массиву пока не найдем ему место
//сразу же считаем количество коллизий
while (true)
{
//если в ячейке таблицы уже есть значение
//то коллизия и переходим к следующему полю
if (hashtable[num].key!=0)
{
kolcol++;
//строки равны то выходим
if (strcmp(hashtable[num].znac,s)==0) break;
//находим новую позицию как квадрат, меняем знак
num=(num+i*zn)*(num+i*zn); zn=-zn;
if (zn==1) i++;
//если вышли за пределы хэш-таблицы, то увеличиваем ее размер
if (num>kolsl && num<maxn) kolsl=num;
//проверяем, не вышли ли за пределы массива
if (num>maxn) num=num%maxn;
if (num<0) num=1;
}
else
{
ObTable++;
strcpy(hashtable[num].znac,s);
hashtable[num].key=hs;
break;
}
}
return 0;
}

#pragma argsused
int main(int argc, char* argv[])
{
ifstream inStream;
ifstream inStream2;

char s[20];
int KolSlFile=0;
kolsl=200;
ObTable=0;
kolcol=0;
inStream.open("file.txt");
//очищаем хеш-таблицу
memset(hashtable,NULL,sizeof(hashtable));
while (!inStream.eof())
{
KolSlFile++;
inStream >> s;
if (strcmp(s," ")==0) continue;
linhash(s);
}
inStream.close();
printf("Lineinie probi:\n Number of the words in file= %i\n Rasmer HashTable= %i\n Number collision= %i\n\n", KolSlFile, ObTable, kolcol);
inStream2.open("file.txt");
memset(hashtable,NULL,sizeof(hashtable));
KolSlFile=0;
ObTable=0;
kolcol=0;
while (!inStream2.eof())
{
KolSlFile++;
inStream2 >> s;
if (strcmp(s," ")==0) continue;
kvhash(s);
}
printf("Kvadratichnie probi:\n Number of the words in file= %i\n Rasmer HashTable= %i\n Number collision= %i\n\n", KolSlFile, ObTable, kolcol);
inStream2.close();
getchar();

return 0;
}
//---------------------------------------------------------------------------

Обсуждение

Неизвестный

27.10.2009, 19:17

общий

Slayder:
А Вам нужно строго на C или достаточно избавиться от потоков? Если второе, то можно написать так:

Код:

int main(int argc, char* argv[])
{
//	ifstream inStream;
//	ifstream inStream2;

	char s[20];
	int KolSlFile=0;
	kolsl=200;
	ObTable=0;
	kolcol=0;
	FILE* f = fopen( "file.txt", "rt" );
	//очищаем хеш-таблицу
	memset(hashtable,NULL,sizeof(hashtable));
	while (!feof(f))
	{
		KolSlFile++;
		fgets( s, sizeof(s), f );
		if( strcmp(s," ")==0) continue;
		linhash(s);
	}
	fclose(f);
	
	printf("Lineinie probi:\n  Number of the words in file= %i\n  Rasmer HashTable= %i\n  Number collision= %i\n\n", KolSlFile, ObTable, kolcol);

	f = fopen( "file.txt", "rt" );
	memset(hashtable,NULL,sizeof(hashtable));
	KolSlFile=0;
	ObTable=0;
	kolcol=0;
	while (!feof(f))
	{
	    KolSlFile++;
		fgets( s, sizeof(s), f );
		if (strcmp(s," ")==0) continue;
		kvhash(s);
	}
	printf("Kvadratichnie probi:\n  Number of the words in file= %i\n  Rasmer HashTable= %i\n  Number collision= %i\n\n", KolSlFile, ObTable, kolcol);
	fclose(f);
	getchar();

	return 0;
}

И конечно, убрать

#include <vcl.h>
#include <fstream.h>
using std::ifstream;

давно

Асмик Гаряка

Профессор
230118
3054

28.10.2009, 10:38

общий

это ответ

Здравствуйте, Slayder.
Кроме потоков, о которых говорил первый эксперт, в С есть и другие отличия от С++.
У компиляторов обычно есть опция - компилировать на С, поэтому можете проверить свою программу таким образом.
* в С++ можно задавать значения по умолчанию
* в С++ появились inline функции, в Си роль которых играли макросы
* в С++ появился спецификатор const (в Си константы определялись директивой define)
* в С++ появились операторы new/delete
* в С++ появились шаблоны
* в С++ появились пространства имен
* в С++ комментарии другие :D
* в С++ появились ссылки

объявление переменных только в начале функции..
конструкции типа for(int i=0... не допускаются
У вас есть такое
for (unsigned int i=0; i<strlen(s); i++)
надо заменить на
int i=0;
for (int i=0; i<strlen(s); i++)
Хотя в современной версии С это допускается.
Нельзя объявлять перменные не в начале функции.
Опять-таки сейчас это можно. Зависит от того, насколько старый компилятор.
В С не было ключевого слова const. Сейчас есть.

давно

Асмик Гаряка

Профессор
230118
3054

28.10.2009, 10:46

общий

Slayder:
Комментарии в стиле С - /* в начале и */ в конце.

Неизвестный

30.10.2009, 21:47

общий

Ashoth, amnick - спасибо Вам за содействие. На Си запустить удалось, но программа выдает неверные данные. Немного по эксперементировав, я пришел к выводу что прога игнорирует каждое третье слово, т.е. к примеру, в тексте 99 слов, а программа "видит" всего 66. Может я чего лишнего убрал?!

Вот измененный код.

Код:


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


//---------------------------------------------------------------------------

const int maxn=10000;
struct node
{
	char znac[20];
	int key;
};

int kolcol;
int kolsl;
int ObTable;

node hashtable[maxn];

int hash(char* s)
{
	int result=0;
        int i=0;
	for (i=0; i<strlen(s); i++)
	{
		result=(255*result+abs(s[i]))%kolsl;
	}
	return result;
}

//ëèíåéíûå ïðîáû
int linhash(char* s)
{
	//ïîëó÷àåì õýø-êîä ñëîâà
	int hs=hash(s);
	int num=hs;
	//èäåì ïî ìàññèâó ïîêà íå íàéäåì åìó ìåñòî
	//ñðàçó æå ñ÷èòàåì êîëè÷åñòâî êîëëèçèé
	while (true)
	{
		//åñëè â ÿ÷åéêå òàáëèöû óæå åñòü çíà÷åíèå
		//òî êîëëèçèÿ è ïåðåõîäèì ê ñëåäóþùåìó ïîëþ
		if (hashtable[num].key!=0)
		{
			kolcol++;
			//ñòðîêè ðàâíû òî âûõîäèì
			if (strcmp(hashtable[num].znac,s)==0) break;
			num++;
			//åñëè âûøëè çà ïðåäåëû õýø-òàáëèöû, òî óâåëè÷èâàåì åå ðàçìåð
			if (num>kolsl && num<kolsl) kolsl=num;
			if (num>maxn) num=num%maxn;
		}
		else
		{
		    ObTable++;
			strcpy(hashtable[num].znac,s);
			hashtable[num].key=hs;
			break;
		}
	}
	return 0;
}

//êâàäðàòè÷íûå ïðîáû
int kvhash(char* s)
{
	//ïîëó÷àåì õýø-êîä ñëîâà
	int hs=hash(s);
	int num=hs;
	int zn=1;
	int i=1;
	//èäåì ïî ìàññèâó ïîêà íå íàéäåì åìó ìåñòî
	//ñðàçó æå ñ÷èòàåì êîëè÷åñòâî êîëëèçèé
	while (true)
	{
		//åñëè â ÿ÷åéêå òàáëèöû óæå åñòü çíà÷åíèå
		//òî êîëëèçèÿ è ïåðåõîäèì ê ñëåäóþùåìó ïîëþ
		if (hashtable[num].key!=0)
		{
            kolcol++;
			//ñòðîêè ðàâíû òî âûõîäèì
			if (strcmp(hashtable[num].znac,s)==0) break;
			//íàõîäèì íîâóþ ïîçèöèþ êàê êâàäðàò, ìåíÿåì çíàê
			num=(num+i*zn)*(num+i*zn); zn=-zn; 
			if (zn==1) i++;
			//åñëè âûøëè çà ïðåäåëû õýø-òàáëèöû, òî óâåëè÷èâàåì åå ðàçìåð
			if (num>kolsl && num<maxn) kolsl=num;
			//ïðîâåðÿåì, íå âûøëè ëè çà ïðåäåëû ìàññèâà
			if (num>maxn) num=num%maxn;
			if (num<0) num=1;
		}
		else
		{
            ObTable++;
			strcpy(hashtable[num].znac,s);
			hashtable[num].key=hs;
			break;
		}
	}
	return 0;
}  




int main(int argc, char* argv[])
{
//	ifstream inStream;
//	ifstream inStream2;

	char s[20];
	int KolSlFile=0;
	kolsl=200;
	ObTable=0;
	kolcol=0;
	FILE* f = fopen( "file.txt", "rt" );
	//î÷èùàåì õåø-òàáëèöó
	memset(hashtable,0,sizeof(hashtable));
	while (!feof(f))
	{
		KolSlFile++;
		fgets( s, sizeof(s), f );
		if( strcmp(s," ")==0) continue;
		linhash(s);
	}
	fclose(f);
	
	printf("Lineinie probi:\n  Number of the words in file= %i\n  Rasmer HashTable= %i\n  Number collision= %i\n\n", KolSlFile, ObTable, kolcol);

	f = fopen( "file.txt", "rt" );
	memset(hashtable,0,sizeof(hashtable));
	KolSlFile=0;
	ObTable=0;
	kolcol=0;
	while (!feof(f))
	{
	    KolSlFile++;
		fgets( s, sizeof(s), f );
		if (strcmp(s," ")==0) continue;
		kvhash(s);
	}
	printf("Kvadratichnie probi:\n  Number of the words in file= %i\n  Rasmer HashTable= %i\n  Number collision= %i\n\n", KolSlFile, ObTable, kolcol);
	fclose(f);
	getchar();

	return 0;
}

Неизвестный

30.10.2009, 22:26

общий

Пример входного файла, пожалуйста.
Программа расчитана на файл с одним словом на каждой строке. Если в строке может быть больше одного слова, то можно заменить fgets на
fscanf( f, "%s", s ); Скорее всего, проблема в этом.

А что это за конструкция такая хитрая в функции linhash:

Код:

//если вышли за пределы хэш-таблицы, то увеличиваем ее размер
if (num>kolsl && num<kolsl) kolsl=num;

условие, насколько я понимаю, всегда ложно.
Кстати, в kvhash выгдлядит логично:

Код:

//если вышли за пределы хэш-таблицы, то увеличиваем ее размер
if (num>kolsl && num<maxn) kolsl=num;

Неизвестный

02.11.2009, 01:23

общий

Блин! Ничего не выходит! Как же такое возможно - я ведь только немного подкорректировал прогу а алгоритм тот-же остался. fscanf вместо fgets пробовал - неверные данные выводит.
Пробовал текст с одним словом в каждой строке - неверные данные.

Здесь сам файл http://webfile.ru/4051638

Файл содержит 174 слова. Вот данные которые должна выдавать программа:

Lineinie probi:
Number of the words in file= 174
Rasmer HashTable= 118
Number collision= 214

Kvadratichnie probi:
Number of the words in file= 174
Rasmer HashTable= 129
Number collision= 46

А вот данные которые она выдает:

Lineinie probi:
Number of the words in file= 116
Rasmer HashTable= 77 // Заметьте, все данные это 2\3 от правильного результата!
Number collision= 30

Kvadratichnie probi:
Number of the words in file= 116 // Почему-то прога не выдает результат по квадратиным пробам.
Rasmer HashTable= 77
Number collision= 30

А вот данные которые она выдает, если в файле по одному слову на строку:

Lineinie probi:
Number of the words in file= 209
Rasmer HashTable= 196
Number collision= 3

Kvadratichnie probi:
Number of the words in file= 209
Rasmer HashTable= 196
Number collision= 3

Просидел весь выходной гипнотизировав монитор, но все тщетно....

Неизвестный

02.11.2009, 16:47

общий

Slayder:
Я бы посмотрел, но не удается скачать файл. Попробуйте закинуть на ifolder.

Неизвестный

02.11.2009, 22:39

общий

http://ifolder.ru/14808256

Неизвестный

17.11.2009, 21:46

общий

Slayder:
Дошли наконец-то руки до Вашей задачи.

1. Ваши исходные файлы — в unicode (16-битные символы), а программа расчитана на работу с текстовыми ASCII файлами (plain text, 8-битные символы). В этом основная проблема.
2. Поскольку в строке может быть больше одного слова, то заменяем fgets на fscanf( f, "%s", s );

Вы задавали вопрос о компиляции в Turbo C, т.е. под DOS. Это предполагает, что входной файл должен быть в ASCII.
После преобразования файла в ASCII и замены fgets на fscanf( f, "%s", s ) получилось так:

Lineinie probi:
Number of the words in file= 174
Rasmer HashTable= 120
Number collision= 208

Kvadratichnie probi:
Number of the words in file= 174
Rasmer HashTable= 130
Number collision= 45

Код:


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


//---------------------------------------------------------------------------

const int maxn=10000;
struct node
{
	char znac[20];
	int key;
};

int kolcol;
int kolsl;
int ObTable;

node hashtable[maxn];

int hash(char* s)
{
	int result=0;
        int i=0;
	for (i=0; i<strlen(s); i++)
	{
		result=(255*result+abs(s[i]))%kolsl;
	}
	return result;
}

//линейные пробы
int linhash(char* s)
{
	//получаем хэш-код слова
	int hs=hash(s);
	int num=hs;
	//идем по массиву пока не найдем ему место
	//сразу же считаем количество коллизий
	while (true)
	{
		//если в ячейке таблицы уже есть значение
		//то коллизия и переходим к следующему полю
		if (hashtable[num].key!=0)
		{
			kolcol++;
			//строки равны то выходим
			if (strcmp(hashtable[num].znac,s)==0) break;
			num++;
			//если вышли за пределы хэш-таблицы, то увеличиваем ее размер
			if (num>kolsl && num<maxn) kolsl=num;
			if (num>maxn) num=num%maxn;
		}
		else
		{
		    ObTable++;
			strcpy(hashtable[num].znac,s);
			hashtable[num].key=hs;
			break;
		}
	}
	return 0;
}

//квадратичные пробы
int kvhash(char* s)
{
	//получаем хэш-код слова
	int hs=hash(s);
	int num=hs;
	int zn=1;
	int i=1;
	//идем по массиву пока не найдем ему место
	//сразу же считаем количество коллизий
	while (true)
	{
		//если в ячейке таблицы уже есть значение
		//то коллизия и переходим к следующему полю
		if (hashtable[num].key!=0)
		{
            kolcol++;
			//строки равны то выходим
			if (strcmp(hashtable[num].znac,s)==0) break;
			//находим новую позицию как квадрат, меняем знак
			num=(num+i*zn)*(num+i*zn); zn=-zn;
			if (zn==1) i++;
			//если вышли за пределы хэш-таблицы, то увеличиваем ее размер
			if (num>kolsl && num<maxn) kolsl=num;
			//проверяем, не вышли ли за пределы массива
			if (num>maxn) num=num%maxn;
			if (num<0) num=1;
		}
		else
		{
            ObTable++;
			strcpy(hashtable[num].znac,s);
			hashtable[num].key=hs;
			break;
		}
	}
	return 0;
}


int main(int argc, char* argv[])
{
	char s[20];
	int KolSlFile=0;
	kolsl=200;
	ObTable=0;
	kolcol=0;
	FILE* f = fopen( "file.txt", "rt" );
	//очищаем хеш-таблицу
	memset(hashtable,0,sizeof(hashtable));
	while (!feof(f))
	{
		KolSlFile++;
		fscanf( f, "%s", s );
		if( strcmp(s," ")==0) continue;
		linhash(s);
	}
	fclose(f);

	printf("Lineinie probi:\n  Number of the words in file= %i\n  Rasmer HashTable= %i\n  Number collision= %i\n\n", KolSlFile, ObTable, kolcol);

	f = fopen( "file.txt", "rt" );
	memset(hashtable,0,sizeof(hashtable));
	KolSlFile=0;
	ObTable=0;
	kolcol=0;
	while (!feof(f))
	{
	    KolSlFile++;
		fscanf( f, "%s", s );
		if (strcmp(s," ")==0) continue;
		kvhash(s);
	}
	printf("Kvadratichnie probi:\n  Number of the words in file= %i\n  Rasmer HashTable= %i\n  Number collision= %i\n\n", KolSlFile, ObTable, kolcol);
	fclose(f);
	getchar();

	return 0;
}

Неизвестный

17.11.2009, 21:51

общий

Slayder:
Кстати, сравнение строки с пробелом

fscanf( f, "%s", s );
if (strcmp(s," ")==0) continue;

излишнее. scanf() пропускает пробельные символы (пробел, табуляция, перевод строки).

Неизвестный

18.11.2009, 01:15

общий

Уважаемый amnick - Вы гений!!! Спасибо большое за помощь! 5++++ Вам.

Неизвестный

18.11.2009, 01:23

общий

PS: С вебманей нет желания париться, поэтому рейтинг поднял. Надеюсь не обидитесь :).

Неизвестный

18.11.2009, 17:07

общий

Slayder:
Спасибо за повышение рейтинга.
я совсем не гений, даже не талант.
собственно, это было совсем несложно, просто не было времени раньше — работа. Хватило бы и просто "спасибо", задача-то была простая.
Успехов Вам!

Форма ответа

Отправка постов/ответов доступна только зарегистрированным и подтвержденным пользователям.

Если Вы уже зарегистрированы на Портале - войдите в систему, если Вы еще не регистрировались - пройдите простую процедуру регистрации.