Liczenie ilości wystąpień znaku ( struktura ) Kodowanie Huffmana

Witam.

Od kilku godzin siedzę i nie potrafię znaleźć błędu. Próbuję napisać funkcję (chyba niezbędną do utworzenia programu kodującego huffmanem) zliczającą ilość wystąpień poszczególnych znaków i bezpośrednie wpisanie tej ilości w strukturę.

Funkcja ma kolejno pobierać pojedyncze znaki z ciągu zdanie[]; a następnie sprawdzenie czy taki znak już wcześniej występował.
Jeżeli tak : wskaźnik wskazujący na zmienną "int ile" zwiększa się o 1.
Jeśli nie : litera jest zapisywana w kolejnej, nowo utworzonej strukturze.

Docelowo chciałbym aby funkcja wyświetliła mi częstotliwość występowania znaków. Dodałem kilka komend tekstowych w celu ułatwienia znalezienia problemu.

Finalnie program ma kodować metodą huffmana. Listy i drzewa są dla mnie nowością, więc kod może być lekko (albo nawet bardzo) nieoptymalny. Z góry dziękuje za wszystkie podpowiedzi. Pozdrawiam.

#include "stdafx.h"
#include "string.h"



// zmienne testowe

char zdanie[] = "misisipi";


struct tree{

	struct tree *lewo;

	struct tree *prawo;

	struct tree *dad;

	char znak;

	int ile=0;

	struct tree *next = NULL;



};

void zlicz(tree* head)
{
	tree*wsk;
	wsk = head;

	char c;

	int x = strlen(zdanie);

	printf("%d", x);

	for (int z = 0; z < x; z++)
	{
		c = zdanie[z];
		puts("pobieram litere");

		printf("%c\n", c);


			if (wsk->next != 0)
			{
				puts("kolejny element istnieje");

				while (wsk != NULL)
				{
					puts("petla szukajaca znaku");

					if (c == wsk->znak)
					{
					wsk->ile = (wsk->ile + 1);
					puts(" dodaje do znaku");
					wsk = wsk->next;
					break;
					}
					else break;

				}

				puts("tworze nowy lisc");
				wsk = new tree;
				wsk->znak = c;
				


			} else puts("--");



		
	}

	puts("koneic petli for");


		wsk = head;

		while (wsk != NULL)
		{

			printf("%d\n", wsk->ile);
			wsk = wsk->next;

		}

}



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

	struct tree *head = new tree;

	head -> next = head;

	zlicz(head);

	puts("sialala");

	return 0;
} 

Zobacz na ten program:

#include <stdio.h>

#define NUM_OF_LETTERS 'Z' - 'A'

struct Stats{
  int white_characters;
  int letter_counter[NUM_OF_LETTERS];
};

struct Stats statistic;

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

  char c;

  while((c = getchar()) != EOF){
    if(c >= 'A' && c <= 'Z')
      statistic.letter_counter[c - 'A']++;
    else if(c == ' ' || c == '\t' || c == 'n')
      statistic.white_characters++;
  }

  int number_of_letters = 0;
  for(int i = 0; i<NUM_OF_LETTERS; ++i)
    number_of_letters += statistic.letter_counter[i];

  printf("\nYou entered: %d signs.\n", number_of_letters + statistic.white_characters);
  printf("You entered: %d letters.\n", number_of_letters);
  printf("You entered: %d white characters.\n", statistic.white_characters);

  printf("\nLetters entered: ");
  for(int i = 0; i < NUM_OF_LETTERS; ++i){
    if(statistic.letter_counter[i] != 0)
      printf("%c ", i + 'A');
  }
  printf("\b.\n");

  printf("\nLetter frequency: \n");
  for(int i = 0; i < NUM_OF_LETTERS; ++i){
    if(statistic.letter_counter[i] != 0)
      printf("%c: %02.2f\n", i + 'A', (float)statistic.letter_counter[i]/number_of_letters * 100.0);
  }

  return 0;
}

Działa tylko dla dużych liter, ale łatwo zmienić, aby obsługiwał też małe litery, czy cyfry.

Hej, wielkie dzięki za podpowiedź. W między czasie sam walczyłem z kodem i napisałem go prawie od nowa. ;)

tym razem kod bardzo dobrze radzi sobie z podanym ciągiem znaków, dla nowego znaku tworzy nowy węzeł, dla takiego który już był dodaje wartość w liczniku. Jest jednak jeden problem... zdanie[] = "aaabbbbccccc" - dla takiej kombinacji progam wypisze ze " a 3 razy" "b 4 razy" "c 5 razy". Jeśli jednak znaki te będą przerwane innym pojedynczym np aaaabaaa , program głupieje i wypisuje ze a pojawilo sie 4 razy b raz i znowu a 3 razy. Domyślam się że warunki if są nie do końca dobrze zapisane. Sam szukam błedu i jeśli go poprawie dam znać. Bardzo dziękuje za sugestie i porady. Pozdrawiam :)

#include "stdafx.h"
#include "string.h"



// zmienne testowe

char zdanie[] = "aaabbbbccccc";


struct tree{

	struct tree *lewo;

	struct tree *prawo;

	struct tree *dad;

	char znak=NULL;

	int ile=0;

	struct tree *next=NULL;



};

void zlicz(tree* head)
{
	tree*wsk;
	wsk = head;

	int ilosc_liter = strlen(zdanie);
	char litera;
	
	for (int i = 0; i < ilosc_liter; i++)
	{
		litera = zdanie[i];
		int z = 0;
		printf("w petli %d ej pobralem litere %c\n",i, litera);

		while( wsk != NULL)
		{ 
			if (wsk->znak == litera && wsk->znak != NULL)
			{
				puts("znalazlem litere");
				wsk->ile += 1;
				printf("%d\n\n", wsk->ile);
				break;
			}

			else
			{
				wsk->next = new tree;
				wsk = wsk->next;
				wsk->znak = litera;
				wsk->ile += 1;
				puts("nowa litera, dodaje wezel");
				break;
			}


			break;

			
			
			
				
		}
		puts("koniec wezlow");




	}

	wsk = head;
	while (wsk != NULL)
	{

		printf("znak %c  wystepuje %d razy \n", wsk->znak, wsk->ile);
		wsk = wsk->next;

	}
	

}
	



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

	struct tree *head = new tree;

	head -> next = head;

	zlicz(head);


	

	return 0;
} 

Proponuję, abyś oddzielił implementację listy od poszukiwania liter, bo teraz jest tu straszny bałagan. Możesz też użyć listy z biblioteki STL, jeśli kod nie musi być napisany w języku C.

Mieszasz też polskie nazwy zmiennych z angielskimi. Postaraj się o spójne nazewnictwo. Funkcja 'zlicz' jest za długa i robi za dużo rzeczy.

magnusik22 napisał(a)

Dodałem kilka komend tekstowych w celu ułatwienia znalezienia problemu
Zamiast dodawania komend tekstowych zacznij korzystać z debuggera.

Program, źle działa, bo trafiając na kolejny nowy znak nie sprawdzasz nigdzie, czy on już wystąpił wcześniej i czy jest już w twojej liście.

Hej wszystkim, znalazłem błędy logiczne. Tak prezentuje się program liczący częstotliwość wystąpienia każdego z znaków i bezpośrednie wpisanie go do struktury. Kolejnym krokiem będzie zmiana źródła odczytu zdania, chcę pobierać je z dowolnego pliku txt. Do kodowania huffmana jeszcze daleko ale krok po kroczku idę do przodu, nie pogardzę pomocą dotyczącą implementacji drzew i operowania na nich. Pozdrawiam a oto kod.

// Antczak Kamil 2016-01-25
//POLSL AEiI
//---------------------------

#include "stdafx.h"
#include "string.h"
#include <stdio.h>





struct tree{

	struct tree *lewo;

	struct tree *prawo;

	struct tree *dad;

	char znak=NULL;

	int ile=0;

	struct tree *next=NULL;



};

char zdanie[] = "heja ludziska, to dziala. Misisipi, warszawa, rabarbar";

void zlicz(tree* head)
{
	tree*wsk;
	wsk = head;

	int ilosc_liter = strlen(zdanie);
	char litera;
	
	for (int i = 0; i < ilosc_liter; i++)
	{
		litera = zdanie[i];
		int z = 0;
		printf("w petli %d ej pobralem litere %c\n",i, litera);

		wsk = head;
		while(wsk != NULL)
		{ 
			if (litera == wsk->znak)
			{
				puts("znalazlem litere");
				wsk->ile += 1;
				printf("%d\n\n", wsk->ile);
				break;
			}

			else if (wsk->znak == NULL )
			{
				wsk->next = new tree;
				wsk->znak = litera;
				wsk->ile += 1;
				puts("nowa litera, dodaje wezel");		
				break;
			}

			wsk = wsk->next;
	
			printf(" petla nr %d \n", z);
			z++;
				
		}
		puts("koniec wezlow");




	}

	wsk = head;
	while (wsk != NULL)
	{

		printf("znak %c  wystepuje %d razy \n", wsk->znak, wsk->ile);
		wsk = wsk->next;

	}
	

}
	



int main()
{
	

	struct tree *head = new tree;

	head -> next = head;

	zlicz(head);
	

	return 0;
}
 

Hej, program zrobił krok do przodu, teraz jest w stanie pobrać i zliczyć znaki z pliku.txt .

kolejny krok to stworzenie drzewa binarnego, czas pokaże jak to pójdzie.

// Antczak Kamil 2016-01-25
//POLSL AEiI
//---------------------------

#include "stdafx.h"
#include "string.h"
#include <stdio.h>





struct tree{

	struct tree *left;

	struct tree *right;

	struct tree *dad;

	char sign=NULL;

	int count=0;

	struct tree *next=NULL;



};


void zlicz(tree* head)
{
	tree*wsk;
	wsk = head;

	FILE * plik;

	plik = fopen("plik.txt", "r");

	int number_letter= NULL;
	char letter;
	int total=0;
 	while (number_letter != EOF)
	{
		letter = getc(plik);
		total++;
		printf("znak nr %d -  %c\n", number_letter, letter);

		wsk = head;
		while(wsk != NULL)
		{ 
			if (letter == wsk->sign)
			{
				puts("znalazlem litere");
				wsk->count += 1;
				printf("%d\n\n", wsk->count);
				break;
			}

			else if (wsk->sign == NULL )
			{
				wsk->next = new tree;
				wsk->count += 1;
				wsk->sign = letter;
				puts("nowa litera, dodaje wezel");		
				break;
			}
			else { puts("szukam dalej"); }

			wsk = wsk->next;

			number_letter = letter;
				
		}
		puts("koniec wezlow");
		printf("tekst ma %d znakow \n", total);
	}

	wsk = head;
	while (wsk != NULL)
	{

		printf("znak %c  wystepuje %d razy \n", wsk->sign, wsk->count);
		wsk = wsk->next;

	}
	
	fclose(plik);

}
	



int main()
{

	struct tree *head = new tree;

	head -> next = head;

	zlicz(head);
	

	return 0;
}