Program "Anagramy" – błędne wyszukiwanie słowa z polskimi znakami

0

Witam, piszę program szukający anagramów podanego przez użytkownika słowa w pliku txt. Program piszę w języku C w środowisku DEV C++
Jednak napotkałem problem bo o ile wpiszemy wyraz do szukania bez polskich znaków wszystko jest dobrze to przy przeszukiwaniu z polskimi znakami program zaczyna głupieć. Czy można ten problem jakoś obejść ? W tym przypadku realizowane są znaki tylko z tablicy kodów ASCII no chyba ze jakąś inną drogą można to zrealizować.

Docelowo program ten będę zrównoleglał do MPI więc już teraz chciałbym mieć bazowy program który będzie można realizować wielowątkowo.
Proszę o Wasze wskazówki



#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
#include <conio.h>
#include<locale.h>

bool czy_anagram(char *a, char *b)
{
  	int dl1 = strlen(a), dl2 = strlen(b);
  	  	
	if(dl1!=dl2)return false;
  
  	int licz[127]={};
  	for(int i=0;i<dl1;i++)	  
  		licz[a[i]]++; 
  	for(int i=0;i<dl1;i++)
  		licz[b[i]]--; 
  	for(int i=0;i<127;i++)
  		if(licz[i]!=0)
			return false;
		
  return true; 
} 


int main(int argc, char *argv[]) {

        setlocale(LC_CTYPE, ".1250");
	
	char a[101], b[101]; [syntax=c][syntax=c][/syntax][/syntax]
	FILE *pFile;

	pFile=fopen("slowa22.txt","r");
	  		
	printf("Podaj wyraz: ");
   		scanf ("%s", a);
		
	if (pFile != NULL){
	while ( fscanf (pFile,"%s",b) == 1) {
		
		//printf("%p\n", &b);
		
    	if(czy_anagram(a,b))
        	printf("Słowo %s jest anagramem!\n", b);
}
  	fclose(pFile);
  }
  else{
  	printf("Nie mozna otworzyc pliku.\n");
  }
  
	return 0;
}

0

licz jest za małe dla każdego kodowania, które ma polskie znaki.
W efekcie wykraczasz poza zakres tablicy i masz Undefined Behavior.
Jak to poprawisz to pamiętaj, że char jest liczbą ze znakiem.

0

Nawet po zwiększeniu tablicy nie udało mi się odczytać polskich znaków, więc nadal nwm co można zrobić

0

Jeśli potrzebujesz polskich znaków to:

pamiętaj, że jeden znak może być większy niż char
pamiętaj, że jeden symbol może się składać z więcej niż jednego znaku
w związku z powyższym zwykły for (size_t i; i < strlen(s); i++) nie wystarczy do iterowania po znakach
musisz znać kodowanie pliku wejściowego, bo w różnych kodowaniach różne rzeczy działają inaczej
Unikod może zakodować 1 111 998 znaków, czyli bardzo zdecydowanie więcej niż twoje 127

0

Jeżeli nie wystarczy zwiększenie wielkości tablicy to w takim przypadku jak powinna być realizowana taka pętla ?

0

Polskie znaki, czyli ą,ę,ć, itd. są powyżej 128.

0

Ok rozumiem, to w takim razie co mam zrobić aby je obsłużyć w tym programie, skoro zwykłe zwiększenie tablicy nie pomogło

0

Kanterin napisał(a):

Ok rozumiem, to w takim razie co mam zrobić aby je obsłużyć w tym programie, skoro zwykłe zwiększenie tablicy nie pomogło

Nie powinieneś tam w ogóle używać liczników literek, a zamiast tego wprost sprawdzać czy dana literka występuje w obu słowach.


int anagram(char *a, *b)
{
  char s[MAX_S]; strcpy(s,a); // kopia a w s
  
  for(int i = 0; b[i]; i++)
  {
    char *p = strchr(s, b[i]); // szukamy b[i] w s
    if( !p ) return 0; // nie jest anagramem
    *p = ' '; // wpisujemy spację - wymazując tę literę z s!
  }

 return 1; // jest anagramem
}

0

Algorytm masz dobry, nie wiem tylko skąd 127. Programujesz na Atari 8 bit?
A nawet jeśli to 127 byłoby za mało.

Zamień 127 na 256.

0

Zwiększałem rozmiary tablic jak i kodowanie pliku do odczytu. Dalej jednak nwm co jest nie tak, bo nie otrzymuję żadnego wyniku poza tym że program się kompiluje.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
#include <conio.h>
#include<locale.h>
/*
bool czy_anagram(char *a, char *b)
{
	//wyznaczenie liczby liter w slowie a i w slowie b
  	int dl1 = strlen(a), dl2 = strlen(b);
  	//jesli dlugosci wyrazów nie sa równe, to nie moga
  	//byc anagramy
  	  	
	if(dl1!=dl2)return false;
  
  	int licz[256]={}; //zerujemy licznniki
  	for(int i=0;i<dl1;i++)	  
  		licz[a[i]]++; //zliczamy litery pierwszego wyrazu
  	for(int i=0;i<dl1;i++)
  		licz[b[i]]--; //odejmowanie wystapien liter
  	for(int i=0;i<256;i++)
  		if(licz[i]!=0) //jesli ktorys licznik sie nie wyzerowal
			return false; //to oznacza, ze słowa nie sa anagramami
		
  return true; //jesli wszystkie liczniki sie wyzerowały, to mamy anagramy
} 
*/

bool czy_anagram(char *a, char *b)
{
  char s[101]; strcpy(s,a); // kopia a w s
  int dl1 = strlen(a), dl2 = strlen(b);
  
  if(dl1!=dl2) return false;
 
  for(int i = 0; b[i]; i++)
  {
    char *p = strchr(s, b[i]); // szukamy b[i] w s
    if( !p ) return false; // nie jest anagramem
    *p = ' '; // wpisujemy spację - wymazując tę literę z s!
  }
 
 return true; // jest anagramem
}

int main(int argc, char *argv[]) {
	
	setlocale(LC_CTYPE, ".1250");
	
	char a[101], b[101]; //dwa słowa, maksymalnie 100 znaków
	FILE *pFile;

	pFile=fopen("slowa22.txt","r");
	  		
	printf("Podaj wyraz: ");
   		scanf ("%s", a);
		
	if (pFile != NULL){
	while ( fscanf (pFile,"%s",b) == 1) {
		
		//printf("%p\n", &b);
		
    	if(czy_anagram(a,b))
        	printf("Słowo %s jest anagramem!\n", b);
}
  	fclose(pFile);
  }
  else{
  	printf("Nie mozna otworzyc pliku.\n");
  }
  
	return 0;
}

1

popraw te linijki w swoim pierwotnym kodzie:

int licz[0x100]={};
… … …
    licz[(unsigned char)a[i]]++;
… … …
    licz[(unsigned char)b[i]]--;

algorytm od @wil jest dużo gorszy bo ma złożoność kwadratową (twój ma złożoność liniową).

Jakie kodowanie ma twój plik?

0

Poprawiłem... ale jak ma wyglądać ta pętla? Skoro ma w 127 nie sprawdzać

--------------
for(int i=0;i<  ?  ;i++)
  		if(licz[i]!=0) //jesli ktorys licznik sie nie wyzerowal
			return false;
---------------

Plik próbowałem w rożnych kodowaniach, ale jakikolwiek wynik co prawda nie prawidłowy wyświetlany jest jedynie w ANSI

title

0

Może tam powinieneś wyzerować ten licznik, np. tak: memset(licz, 0, sizeof(licz));

Potem zapisz do tego pliku takie coś:
ąęćśłóĄŻŹŚśź
odczytaj i wydrukuj to na ekran.

generalnie moja metoda i tak jest szybsza, bo słowa są zwykle krótkie; do kilkunastu znaków w porywach, zatem nawet: 20^2 = 400 < 4*256 = 1024;

0

Lepiej pokaż jak to poprawiłeś.
Jakie masz kodowanie pliku tekstowego?

0

Poprawiłem tak jak radziłeś. Co do pętli to nwm
Tak jak pisałem próbowałem z rożnym kodowaniem plików. Aktualnie mam go w ANSI ale mogę zmienić bez przeszkód na inne chociażby UTF-8, Windows-1250 czy OEM 852. Chciałbym tylko żeby była możliwość obsługi polskich znaków i poprawnie wypisywane zostały dla użytkownika.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
#include <conio.h>
#include<locale.h>

bool czy_anagram(char *a, char *b)
{
	//wyznaczenie liczby liter w slowie a i w slowie b
  	int dl1 = strlen(a), dl2 = strlen(b);
  	//jesli dlugosci wyrazów nie sa równe, to nie moga
  	//byc anagramy
  	  	
	if(dl1!=dl2)return false;
  
  	int licz[0x100]={}; //zerujemy licznniki
  	for(int i=0;i<dl1;i++)	  
  		licz[(unsigned char) a[i]]++; //zliczamy litery pierwszego wyrazu
  	for(int i=0;i<dl1;i++)
  		licz[(unsigned char) b[i]]--; //odejmowanie wystapien liter
  		
  	for(int i=0;i<127;i++) //skoro 127 nie moze być to jak poprawić ta linię
  	
  		if(licz[i]!=0) //jesli ktorys licznik sie nie wyzerowal
			return false; //to oznacza, ze słowa nie sa anagramami
		
  return true; //jesli wszystkie liczniki sie wyzerowały, to mamy anagramy
} 

int main(int argc, char *argv[]) {
	
	setlocale(LC_CTYPE, ".1250");
	
	char a[101], b[101]; //dwa słowa, maksymalnie 100 znaków
	FILE *pFile;

	pFile=fopen("slowa22.txt","r");
	  		
	printf("Podaj wyraz: ");
   		scanf ("%s", a);
		
	if (pFile != NULL){
	while ( fscanf (pFile,"%s",b) == 1) {
		
		//printf("%p\n", &b);
		
    	if(czy_anagram(a,b))
        	printf("Słowo %s jest anagramem!\n", b);
}
  	fclose(pFile);
  }
  else{
  	printf("Nie mozna otworzyc pliku.\n");
  }
  
	return 0;
}

Proszę o jakieś porady co więcej tu zmienić

0

zamień to 127 na 256 = 0x100;

0

Ok zamieniłem i zmieniłem kodowanie pliku UTF-8 na OEM852.

Najpierw otrzymałem taki efekt, wiec to już coś:

title

Później za komentowałem linię setlocale(LC_CTYPE, ".1250"); i w sumie otrzymałem żądany efekt jednak niestety kosztem wyświetlania polskich znaków pod windows.

title

Można to jakoś pogodzić na systemie windows? I co zrobić żeby w pliku txt nie dostać stada krzaczków tylko zwykły tekst czy nie można nic z tym poradzić bo plik został zmieniony na OEM852

Program "Anagramy" – błędne wyszukiwanie słowa z polskimi znakami

Kanterin napisał(a):

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

Praca dla programistów

Forum dyskusyjne

Sprawy administracyjne

O nas

Skontaktuj się z nami