Program haszujący + biblioteka słów

0

Witam... Nie za bardzo ogarniam sie w c++ , więc jeżeli mógłbym prosić uniżenie o pomoc to by bylo super :D...
Otóż mam do napisania program haszujacy z bazą słów + hasło które użytkownik wpisze. Już kij z tym że tablica ma byc max 100 elementowa i każdy element w indeksie ma być listą. z tym chyba sobie poradzę... ale nie umiem ogarnąć jak ta baza słów(która u mnie jest wczytywana z pliku do stringa) ma zostać zhaszowana... ogólnie mam problem z funkcją gdzie program ma za zadanie zrobić z każdego słowa w bazie hasz i dalej ten hasz wpisać do wyżej wymienionej tablicy(a jesli już taka liczba istnieje to wpisać jako kolejny element listy)... Innymi słowy string zamienić na wiele małych stringów i z kazdego z nich po kolei ma wyliczyć hasze... Jak to zrobić? Zaznaczam że nie ogarniam C, nie ogarniam (jeszcze) list i jestem na poziomie,erm...struktur? Taa... także klasy też mi obce..
Na razie mam to(czyt.jeden wielki chaos):

#include <iostream>
#include <stdlib.h>
#include <string>
#include <fstream> 
using namespace std;
int liczba;
wchar_t tab[]=
	{
		'?','/','.','>','<',',','M','N','B','V',
		'C','X','Z','A','S','D','F','G','H','J',
		'K','L',';',':','"','|',']','}','{','[',
		'P','O','I','U','Y','T','R','E','W','Q',
		'+','=','-','_','0',')','(','9','*','8',
		'%','5','4','$','3','#','@','2','!','1',
		'~','`','q','w','e','r','t','y','u','i',
		'o','p','a','s','d','f','g','h','j','k',
		'l','z','x','c','v','b','n','m','&','7',
		'6','^',
	};
typedef struct{
        wchar_t tab[S]; //moze byc tez char
		int dl;
		string p;
}struktura;
string slowa()//moja biblioteka ktora jest wczytywana z pliku
{
	string slowa;
	fstream plik("nazwa.txt",ios::in); //(nazwa umieszczona w folderze z kodem źródłowym)
	getline(plik, slowa);//( w nawiasach kolejno: argument z którego są zczytywane dane, zmienna do ktorej są wczytywane dane)
	void close(void);
	return slowa;
}
struktura strpassword()
{
			struktura strpassword;
			cout<<"\nPlease enter your password: ";
			cin>>strpassword.p;
			return strpassword;
}
int encryptor(struktura strpassword)
{
	struktura nowatab;
	int sumakontrolna=0;
	for(int i=0;i<strpassword.p.length();i++)
		nowatab.tab[i]=0;
	for(int j=0; j<strpassword.p.length();j++)
		for(int i=0;i<92;i++)
			if(strpassword.p[j]==tab[i])
				nowatab.tab[j]=i;//kodowanie hasla
	for(int i=0;i<strpassword.p.length();i++)
		sumakontrolna=sumakontrolna+nowatab.tab[i]; //obliczanie sumy kontrolnej
	if(sumakontrolna>100)
		do
			sumakontrolna=sumakontrolna%2;
		while(sumakontrolna>100); //przycinanie sumy kontrolnej do 100 żeby tablica nie urosła
	return sumakontrolna;
}
void strcpy(char *zrodlo)
{
	struktura strpassword;
	int suma;
	bool wyr=false;
	for(;*zrodlo;++zrodlo) // pętla znak po znaku ze źródła
	{
	if(*zrodlo!=' ') // jeżeli nie spacja
	{
		if(!wyr) // jeżeli to pierwsza litera słowa
		{
			if(suma*suma++=' ') 
			{
				wyr=true; // już jesteśmy w słowie
				*zrodlo=strpassword.p;
				struktura nowatab;
				int sumakontrolna=0;
				for(int i=0;i<strpassword.p.length();i++)
					nowatab.tab[i]=0;//zerowanie nowataba...bo by były krzaki...
				for(int j=0; j<strpassword.p.length();j++)
					for(int i=0;i<92;i++)
						if(strpassword.p[j]==tab[i])
							nowatab.tab[j]=i;//kodowanie hasla
				for(int i=0;i<strpassword.p.length();i++)
					sumakontrolna=sumakontrolna+nowatab.tab[i]; //obliczanie sumy kontrolnej
				if(sumakontrolna>100)
					do
						sumakontrolna=sumakontrolna%2;
					while(sumakontrolna>100); //przycinanie sumy kontrolnej do 100 żeby tablica nie urosła
			}

			
		}
	else wyr=false; // już jesteśmy pomiędzy słowami
	}

}
int main()
{
	cout<<"############################################"<<endl;
	cout<<"   ###    PASSWORD ENCRYPTOR(1)   ###       "<<endl;
	cout<<"   ###     HASH DECRYPTOR(2)      ###       "<<endl;
	cout<<"   ###      SEEK & FIND (3)       ###       "<<endl;
	cout<<"   ###          EXIT(0)           ###       "<<endl;
	void strcpy(string *zrodlo,char *suma);
	char suma[100];
	cin>>liczba;
	switch(liczba)
	{
	case 1: 
		{
			system("CLS");
			cout<<"### PASSWORD ENCRYPTOR ###\n\n"<<endl;
			cout<<"initializing encryption stream # .......\n"<<endl;
			system("PAUSE");
			encryptor(strpassword());
			strcpy(slowa,suma);
		}
	case 2:
			{
				cout<<"### PASSWORD DECRYPTOR ###\n\n";
				system("PAUSE");
				system("CLS");
			}
	case 3: 
		{
			cout<<"#########   SEEK & FIND  ################"<<endl;
			return main();
		}
	case 0: break;
	default: cout<<"jeszcze raz..."<<endl;
	}
	
	return 0;
}
	

Już nie patrzeć na te wchar_t... akurat szybkość wykonywania i wielkość najmniej mnie interesują...eh..

0

spuść z tonu. Dużo linijek nadźgałeś i nie chce mi się tego całego analizować, ale wystarczy, że spojrzałem i wiem, że na pewno da sie to napisać 2/3 razy mniejszą ilością linijek.
Czyli te funkcje haszujące działają? Jeżeli tak, to dlaczego nie zrobisz sobie jakiejś struktury pomocniczej w main, którą przekazujesz przez referencje do funkcji i nie zapisujesz w niej wyniku?
Napisz dokładnie jak brzmi treść zadania które dostałeś.

0
kopernik napisał(a)

spuść z tonu. Dużo linijek nadźgałeś i nie chce mi się tego całego analizować, ale wystarczy, że spojrzałem i wiem, że na pewno da sie to napisać 2/3 razy mniejszą ilością linijek.
Czyli te funkcje haszujące działają? Jeżeli tak, to dlaczego nie zrobisz sobie jakiejś struktury pomocniczej w main, którą przekazujesz przez referencje do funkcji i nie zapisujesz w niej wyniku?
Napisz dokładnie jak brzmi treść zadania które dostałeś.

Duzą ilość linijek nadźgałem bo musiałem jakoś drugi raz koło wymyśleć... Ogólnie sama funkcja haszująca działa. Nie działa przekazanie wyniku tej funkcji dalej... Ale to będę dalej pisać i w razie czego poproszę o pomoc :) Głównie problemem jest przekazanie całej biblioteki haseł do funkcji haszującej, które dalej zostaną przypisane do odpowiedniego indeksu tablicy zawierającej te hasze,a jeżeli istnieje już na danym indeksie tablicy hasło, to przez listę dopisanie dalej tego hasła... A zadanie brzmi mniej więcej tak, że mam stworzyć funkcję haszującą która zapisuje wyniki do tabeli z listami na poszczególnych indeksach, do tego mam stworzyć funkcję wyszukiwania i usuwania haseł z tablicy. Tak to mniej więcej wygląda...

0

Troszkę poprawiłem kod(teraz mi wczytuje i zapisuje do tablicy to co użytkownik podaje) ale nadal mam problem z tą tablicą list... nie wiem jak to poprawnie zaimplementować... Byłbym bardzo wdzięczny za każdą pomoc...

 
#include <iostream>
#include <string>
#include <fstream>
using namespace std;
const int S=500,Q=200;
wchar_t tab[]=
{
'?','/','.','>','<',',','M','N','B','V',
'C','X','Z','A','S','D','F','G','H','J',
'K','L',';',':','"','|',']','}','{','[',
'P','O','I','U','Y','T','R','E','W','Q',
'+','=','-','_','0',')','(','9','*','8',
'%','5','4','$','3','#','@','2','!','1',
'~','`','q','w','e','r','t','y','u','i',
'o','p','a','s','d','f','g','h','j','k',
'l','z','x','c','v','b','n','m','&','7',
'6','^',
};
typedef struct
{
	char tab[S]; //moze byc tez char
	string p;
	char hasz[Q];
}struktura;
string slowa()
{
	string slowa;
	fstream plik("nazwa.txt",ios::in); //(nazwa umieszczona w folderze z kodem źródłowym)
	getline(plik, slowa);//( w nawiasach kolejno: argument z którego są zczytywane dane, zmienna do ktorej są wczytywane dane)
	void close(void);
	return slowa;
}
string strpassword()
{
	string password;
	cout<<"\nPlease enter your password: ";
	cin>>password;
	return password;
}
int encryptor(string strpassword)
{
	struktura nowatab;
	int sumakontrolna=0;
	for(int i=0;i<strpassword.length();i++)
		nowatab.tab[i]=0;
	for(int j=0; j<strpassword.length();j++)
		for(int i=0;i<92;i++)
			if(strpassword[j]==tab[i])
				nowatab.tab[j]=i;//kodowanie hasla
	for(int i=0;i<strpassword.length();i++)
		sumakontrolna=sumakontrolna+nowatab.tab[i]; //obliczanie sumy kontrolnej
	if(sumakontrolna>Q)
		do
			sumakontrolna=sumakontrolna/7;
		while(sumakontrolna>Q); //przycinanie sumy kontrolnej do 100 żeby tablica nie urosła
	cout<<"suma kontrolna: "<<sumakontrolna<<endl;
	string *password=&strpassword;
	return sumakontrolna;
}
string tablicahaszy[Q];
int main()
{
	int suma,liczba;
	string password;
	cout<<"Funkcja haszujaca (1)"<<endl;
	cout<<"Tablica haszy (2)"<<endl;
	cout<<"EXIT 0"<<endl;
	cin>>liczba;
	do
	{
		switch(liczba)
		{
			case 1:
			{
				suma=encryptor(password=strpassword());
				for(int i=0;i<Q;i++)
				{
					if(tablicahaszy[i].empty()==true)
						tablicahaszy[suma]=password;
					else//tu ma prawdopodobnie zadziałać lista...
					{
												          
					};
				return main();
			}
			case 2:
			{
				system("CLS");
				for(int i=0;i<Q;i++)
					if(tablicahaszy[i].empty()!=true)
						cout<<tablicahaszy[i]<<endl;
				return main();
			}
			case 0: break;
			default: break;
			}}}
	while(liczba!=0);
return 0;
}
0

Cały twój problem polega na tym, że źle określiłeś swój problem.
Napisz dokładnie CO MASZ ZROBIĆ, bo nikt nie ma ochoty rozszyfrowywać tego na podstawie kodu? Przy czym: zero wstępniaków, zero narzekania, zero pisania co ci się wydaje!

Czy masz wyszukiwać słowa w słowniku (sprawdzanie pisowni)?
A może masz zaszyfrować hasło, by w ten sposób weryfikować uprawnienia?
W obu wypadkach potrzebna jest funkcja hash, ale nieco inaczej się jej używa.

WTF: rekurencja na main !

2

Dobra, ja ogarniam o co chodzi. Łap przykładowy kod. Pisany dawno i na kolanie, a teraz nie mam jak przetestować ;] Jak ktoś ma czas to niech poprawi (np. zamiast char* dając stringi ;])

//Autor: Stanisław Podgórski
#include <iostream>
using namespace std;

int modulo=91; //od tego zalezy ile będzie pozycji w tablicy, proponowałbym liczbe pierwszą w okolicach np. ilosc wyrazow / 2 albo /3

struct Node
  {
    char* val;
    Node* next;
  };

int hash(const char* slowo);
void add(char* klucz, Node*& lista);
void search(char* klucz, Node* lista);

int main()
{
  char* buf=new char[150]; //zakładam ze dłuższego slowa nie będzie :P
  int ile;
  cout<<"Ile elementow?"<<endl;
  cin>>ile;

  Node** tablica = new Node*[modulo]; //nasza tablica z hashująca
  for (int i=0;i<modulo;i++)
    tablica[i]=NULL;

  for (int i=0;i<ile;i++)
  {
    cin>>buf; //wczytywanie wyrazów do tablicy
    char* str = new char[150];
    strcpy(str,buf);
    add(str, tablica[hash(str)]); //dodawanie kolejnych wyrazów do tablicy
  }

  for (int i=0;i<modulo;i++) //wypisanie tablicy
  {
    Node* rob=tablica[i];
    cout<<"Tablica["<<i<<"] =";
    while(rob)
      {
        cout<<" "<<rob->val;
        rob=rob->next;
      }
    cout<<endl;
  }

  cout<<"Czego szukac?"<<endl;
  cin>>buf;
  search(buf, tablica[hash(buf)]);

  cin.sync();
  cin.get();
  return EXIT_SUCCESS;
}
//////////////////////////////////////////////////////////
int hash(const char* slowo)
{
  int ret=0;
  int n=strlen(slowo); //dlugosć słowa

  while(n>=sizeof(int)) //dopóki są kawałki po 4 bajty
  {
   ret^=*(int*)slowo; //xor na 4 bajtach
   n-=sizeof(int); //"skracamy słowo"
   slowo+=sizeof(int); //przesuwamy sie dalej
  }

  int rem=0; //to co nam zostało, tzn 1,2 lub 3 bajty
  while(n--)
  {
    rem<<=8; //przesuwamy się o 1 bajt
    rem^=*slowo++; //xor
  }
  ret^=rem;
  return ret%modulo;
}
//////////////////////////////////////////////////////////
void add(char* klucz, Node*& lista)
{
  Node* tmp = new Node;
  tmp->val = klucz;
  tmp->next = lista;
  lista=tmp;
}
/////////////////////////////////////////////////////////////
void search(char* klucz, Node* lista)
{
  int ile = 1;
  if (!lista)
    cout<<"Brak, lista dla danego hasha pusta"<<endl;
  else
    {
      while((lista) && (strcmp(lista->val,klucz)))
      {
        lista=lista->next;
        ile++;
      }
      if (lista && !strcmp(lista->val,klucz))
        cout<<klucz<<" znalezione po "<<ile<<" porownaniach"<<endl;
    }
}
0
Shalom napisał(a)

Dobra, ja ogarniam o co chodzi. Łap przykładowy kod. Pisany dawno i na kolanie, a teraz nie mam jak przetestować ;] Jak ktoś ma czas to niech poprawi (np. zamiast char* dając stringi ;])

//Autor: Stanisław Podgórski
#include <iostream>
using namespace std;

int modulo=91; //od tego zalezy ile będzie pozycji w tablicy, proponowałbym liczbe pierwszą w okolicach np. ilosc wyrazow / 2 albo /3

struct Node
  {
    char* val;
    Node* next;
  };

int hash(const char* slowo);
void add(char* klucz, Node*& lista);
void search(char* klucz, Node* lista);

int main()
{
  char* buf=new char[150]; //zakładam ze dłuższego slowa nie będzie :P
  int ile;
  cout<<"Ile elementow?"<<endl;
  cin>>ile;

  Node** tablica = new Node*[modulo]; //nasza tablica z hashująca
  for (int i=0;i<modulo;i++)
    tablica[i]=NULL;

  for (int i=0;i<ile;i++)
  {
    cin>>buf; //wczytywanie wyrazów do tablicy
    char* str = new char[150];
    strcpy(str,buf);
    add(str, tablica[hash(str)]); //dodawanie kolejnych wyrazów do tablicy
  }

  for (int i=0;i<modulo;i++) //wypisanie tablicy
  {
    Node* rob=tablica[i];
    cout<<"Tablica["<<i<<"] =";
    while(rob)
      {
        cout<<" "<<rob->val;
        rob=rob->next;
      }
    cout<<endl;
  }

  cout<<"Czego szukac?"<<endl;
  cin>>buf;
  search(buf, tablica[hash(buf)]);

  cin.sync();
  cin.get();
  return EXIT_SUCCESS;
}
//////////////////////////////////////////////////////////
int hash(const char* slowo)
{
  int ret=0;
  int n=strlen(slowo); //dlugosć słowa

  while(n>=sizeof(int)) //dopóki są kawałki po 4 bajty
  {
   ret^=*(int*)slowo; //xor na 4 bajtach
   n-=sizeof(int); //"skracamy słowo"
   slowo+=sizeof(int); //przesuwamy sie dalej
  }

  int rem=0; //to co nam zostało, tzn 1,2 lub 3 bajty
  while(n--)
  {
    rem<<=8; //przesuwamy się o 1 bajt
    rem^=*slowo++; //xor
  }
  ret^=rem;
  return ret%modulo;
}
//////////////////////////////////////////////////////////
void add(char* klucz, Node*& lista)
{
  Node* tmp = new Node;
  tmp->val = klucz;
  tmp->next = lista;
  lista=tmp;
}
/////////////////////////////////////////////////////////////
void search(char* klucz, Node* lista)
{
  int ile = 1;
  if (!lista)
    cout<<"Brak, lista dla danego hasha pusta"<<endl;
  else
    {
      while((lista) && (strcmp(lista->val,klucz)))
      {
        lista=lista->next;
        ile++;
      }
      if (lista && !strcmp(lista->val,klucz))
        cout<<klucz<<" znalezione po "<<ile<<" porownaniach"<<endl;
    }
}

Visual robi mi jakieś wielkie halo podczas pisania i w mainie mówi że hash is too ambigous... Co to znaczy?

0

http://ideone.com/S24CH
Brakowało kilku includów najwyżej.

0

@Shalom
Przy przekonwertowaniu charów na stringi wszystko zaczyna sie walić...
Możesz powiedziec co znaczy w funkcji:
void search(char* klucz, Node* lista)
{
int ile = 1,s;
if (!lista)
cout<<"Brak, lista dla danego hasha pusta"<<endl;
else
{
while((lista) && (strcmp(lista->val,klucz)))
{
lista=lista->next;
ile++;
}

  if (lista && !strcmp(lista->val,klucz))
    cout<<klucz<<" znalezione po "<<ile<<" porownaniach"<<endl;
}

}

 

ta linijka while((lista) && (strcmp(lista->val,klucz)))? Bo przy skonwertowaniu do stringów to wszystko zaczyna sie walic...

0

Jak masz tam string to powinno tam być:

while((lista) && (lista->val!=klucz))

i wszystkie inne strcmp trzeba pozamieniać na == i !=

0

Heja, słuchajcie,dotąd sie nie uporałem z tą tablicą... Kto wie jak rozwalić taki błąd: hash is ambiguous? Nie moge przez ten błąd nawet programu ruszyc a nie wiem do czego menda pije...

 
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <string>
#include <stdlib.h>
using namespace std;
 
const int S=94,Q=100;//Q=ilosc indeksow w tablicy,S=rozmiar tablicy znakow
char tab[]=
{
'?','/','.','>','<',',','M','N','B','V',
'C','X','Z','A','S','D','F','G','H','J',
'K','L',';',':','"','|',']','}','{','[',
'P','O','I','U','Y','T','R','E','W','Q',
'+','=','-','_','0',')','(','9','*','8',
'%','5','4','$','3','#','@','2','!','1',
'~','`','q','w','e','r','t','y','u','i',
'o','p','a','s','d','f','g','h','j','k',
'l','z','x','c','v','b','n','m','&','7',
'6','^',
};
struct Node
  {
    string* val;
    Node* next;
  };
typedef struct
{
	char tab[S]; 
	string p;
}struktura;

int hash(string *slowo);
void add(string* klucz, Node*& lista);
void search(string* klucz, Node* lista);

int hash(string *slowo)
{
	string slowoo=*slowo;
	struktura nowatab;
	int suma;
	for(int i=0;i<slowoo.length();i++)
			nowatab.tab[i]=0;
	for(int j=0; j<slowoo.length();j++)
			for(int i=0;i<92;i++)
					if(slowoo[j]==tab[i])
							nowatab.tab[j]=i;//kodowanie hasla
	for(int i=0;i<slowoo.length();i++)
			suma=suma+nowatab.tab[i]; //obliczanie sumy kontrolnej
	if(suma>Q)
			while(suma>Q)
					suma=suma/7; //przycinanie sumy kontrolnej do 100 żeby tablica nie urosła
	cout<<"suma znakow: "<<suma<<endl;
	return suma;
}
void add(string *klucz, Node*& lista)
{
	Node* tmp = new Node;
	tmp->val = klucz;
	tmp->next = lista;
	lista=tmp;
}

void search(string* klucz, Node* lista)
{
		int ile = 1;
		if (!lista)
		cout<<"Brak, lista dla danego hasha pusta"<<endl;
		else
		{
			while((lista) && (lista->val!=klucz))
			{
				lista=lista->next;
				ile++;
			}
			if (lista && ((lista->val)!=(klucz)))
				cout<<klucz<<" znalezione po "<<ile<<" porownaniach"<<endl;
		}
}
int main()
{
	string *str;
	int ile,suma=0,c;
	Node** tablica = new Node*[Q]; //nasza tablica z hashująca
	for (int i=0;i<Q;i++)
		tablica[i]=NULL;
	switch(c)
	{
	case 1:
		{
			cout<<"Ile elementow?"<<endl;
			cin>>ile;
			for (int i=0;i<ile;i++)
			{
				cout<<"\nPlease enter your password: ";
				cin>>*str;
				add(str,tablica[(hash(str))]); //dodawanie kolejnych wyrazów do tablicy
			}
		}
	case 2:
		{
			for (int i=0;i<Q;i++) //wypisanie tablicy
			{
				Node* rob=tablica[i];
				cout<<"Tablica["<<i<<"] =";
				while(rob)
				{
					cout<<" "<<rob->val;
					rob=rob->next;
				}
				cout<<endl;
			}
		}
	case 3:
		{
			cout<<"Czego szukac?"<<endl;
			cin>>*str;
			search(str, tablica[hash(*str)]);
		}
	case 0:
		break;
	}
	return 0;
}

0

najprawdopodobniej niepotrzebna ci ta gwiazda przy wywołaniu!

Na dodatek posługujesz się nieustawionym wskaźnikiem str!

hash z definicji ma być szybki, a twój jest napisany totalnie bezsensu.
tak może wyglądać funkcja hash:

const int hashFactors[] = { 23, 13, 57, 3, 1, 101, 29 };
const int hashFactorsCount = sizeof(hashFactors)/sizeof(hashFactors[0]);
const int maxHash = 332312411;

int hash(const string &s) {
     result = 0;
     for (int i=0; i<s.length(); ++i)
         result = (result + s.at(i)*hashFactors[i%hashFactorsCount]) % maxHash;
     return result
}
0
MarekR22 napisał(a)

najprawdopodobniej niepotrzebna ci ta gwiazda przy wywołaniu!

Na dodatek posługujesz się nieustawionym wskaźnikiem str!

Jak to zmienić?

1 użytkowników online, w tym zalogowanych: 0, gości: 1