Drzewa i wskaźniki do nich

Mam strukturę zdefiniowaną następująco:

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

struct Node
{
	int licznik;
	char* slowo;
	struct Node* mniejsze;
	struct Node* wieksze;
};
typedef struct Node* Tree;

A potem taką funkcję main(nie zwracajcie uwagi na funkcje):

int main(int argc, char *argv[])
{
	int top=0;
	if(argc>1)
	{
		for(int i=0; argv[1][i]!=0; i++)
		{
			top=top*10+(int)argv[1][i]-48;
		}
	}else{top=100;}
	Tree* najczestsze=malloc(top*sizeof(Tree));
	for(int i=0; i<top; i++){najczestsze[i]=NULL;}
	Tree* ptr;
	*ptr=NULL;//!!!!!!!!!!!!
	char slowo[50];
	while(scanf("%s", slowo)!=EOF)
	{
		konwersjanaslowo(slowo);
		wstaw(slowo, ptr, najczestsze, top);
	}
	wypisz(najczestsze, top);
	zwolnij_drzewo(ptr);
	free(najczestsze);
	return 0;
}

Wszystko ładnie się kompiluje(MinGW), ale podczas działania programu wyskakuje mi błąd. Empirycznie sprawdziłem, że chodzi o linijkę zaznaczoną wykrzyknikami. Dlaczego ten błąd występuje?

Ty chcesz sprawić, aby wskaźnik wskazywał na NULL, a nie nadpisać to, gdzie wskazuje - zatem ptr = NULL;

PS nie mieszaj nazewnictwa angielskiego oraz polskiego w kodzie, a generalnie dzieci korzenia to nie jest mniejsze oraz większe, tylko lewy i prawy.

Dzięki, już rozumiem. Na ćwiczeniach zrobiliśmy to do bani i w sumie teraz nie dziwię się, że zrobiłem to źle.

1. http://4programmers.net/Forum/1101404
2. Zamiast:

    int top=0;
    if(argc>1)
    {
        for(int i=0; argv[1][i]!=0; i++)
        {
            top=top*10+(int)argv[1][i]-48;
        }
    }else{top=100;}

wystarczy:

    int top=argc>1?atoi(argv[1]):100;

3. Tree *ptr=NULL; to nie to samo co Tree *ptr; *ptr=NULL; zaś to samo co Tree *ptr; ptr=NULL;
4. Przy deklaracji radzę pisać gwiazdkę przy zmiennej: Tree *ptr; a nie Tree* ptr; aby nie pomylić się przy Tree *left,*right;
5. scanf("%s",slowo) jest niebezpieczne, bo łatwo o mazanie po pamięci, używaj scanf("%49s",slowo)
6. Prawie na 100% nie potrzebujesz tablicy najczestsze ponieważ możesz jeszcze raz powstawiać do drzewa wszystkie słowa, ale już z innym kluczem licznik,slowo
7. Strukturę radzę zmienić na:

typedef struct Node
  {
   struct Node *lf,*rt;
   unsigned count;
   char word[1];
  } Node;
typedef struct Tree { Node *root; } Tree;

Wtedy dasz rady zmienić aby działało wstaw, bo teraz nie ma szans (no chyba ze użyłeś referencji w C). Przydzielenie będzie prostsze: Node *node=malloc(sizeof(Node)+strlen(world)); zwolnienie również.

2. Nie wpadłem na to, bo nie używam biblioteki string.h.
3. To już zrozumiałem dzięki koledze wyżej.
4. Rzeczywiście, zapomniałem o tym.
5. Tablica najczestsze ma służyć do tego, żeby przechowywać najczęściej występujące słowa(o to chodzi w zadaniu). A żeby móc od razu znaleźć i słowo, i licznik, to zrobiłem tablicę wskaźników.
6. Strukturę na razie zostawię w spokoju, funkcję wstaw zmodyfikowałem i mam nadzieję, że będzie działać.

Dzięki za wszystkie rady.

2. to zapoznaj się ze sscanf
3. W zadaniu kazano zrobić to jako tablice? Nie wierzę.

Nie, nie kazano. Ale mam wypisać najczęściej występujące słowa, toteż naturalnym pomysłem było dla mnie umieszczenie ich w tablicy.

Nie, trenujesz drzewa, więc to też w drzewie ma być zrobiono.

Ale mam zrobić drzewo alfabetyczne. Po co robić 2 drzewa w jednym programie, kiedy wystarcza tablica?
A tak btw. Na ćwiczeniach mieliśmy takie drzewo:

struct Node
{
	int value;
	struct Node *left;
	struct Node *right;
}
typedef struct Node* Tree

I mieliśmy napisać funkcję wstawiającą wartość i do tego drzewa. Rozwiązanie:

void wstaw(Tree *ptr, int i)
{
	if(!*ptr)
	{
		*ptr=malloc(sizeof(struct Node));
		(*ptr)->value=i;
		(*ptr)->left=NULL;
		(*ptr)->right=NULL;
	}
	else
	{
		if((*ptr)->value<i){wstaw(&((*ptr)->right), i);}
		else
		{if((*ptr)->value>i){wstaw(&((*ptr)->left), i);}
	}
}

zostało uznane przez ćwiczeniowca jako dobre(jeżeli jakaś wartość już wystąpiła w drzewie, to funkcja ma nie tworzyć nowego węzła). Czy takie jest w istocie? Bo mam wrażenie, że jest nie do końca ok.

Robisz drzewo alfabetycznie a przed statystykami przebudowujesz, znacznie taniej (w sensie czasowym wyjdzie).
Drzewo wstawia dobrze, tylko że po małej przebudowie możesz ten sam kod użyć do przebudowy, zwłaszcza po przyzwoitym formatowaniu to widać:

void wstaw(Tree *ptr,int i)
{
    if(!*ptr)
    {
        *ptr=malloc(sizeof(struct Node));
        (*ptr)->value=i;
        (*ptr)->left=NULL;
        (*ptr)->right=NULL;
    }
    else if((*ptr)->value<i) wstaw(&((*ptr)->right),i);
    else if((*ptr)->value>i) wstaw(&((*ptr)->left),i);
}

inna sprawa że nie nadaje się do twego problemu, ponieważ ten kod zwyczajnie pomija przypadek kiedy taki węzeł już istnieje.

Ale na pewno jest ok? Bo jeśli dobrze rozumiem, to skoro *ptr=NULL, to ptr=&NULL, a takie coś chyba nie istnieje. Poza tym jeśli (*ptr)->lewy=NULL, to &((*ptr)->lewy) chyba nie istnieje. Jeśli się mylę, to prosiłbym o poprawienie.

ptr to struct Node**
*ptr to struct Node*
(*ptr)->lewy to składowa struct Node typu struct Node*
Czemu wg ciebie nie możemy pobrać adresu tej składowej?

Jeśli (*ptr)->lewy będzie wskaźnikiem na NULL, to chyba nie ma on adresu? Czy ja po prostu źle rozumiem wskaźniki?

A jeżeli int x=0; to x też nie ma adresu?
lewy jest polem w strukturze, jak może nie mieć adresu?

Dobra, dzięki wielkie, już zrozumiałem. Moje problemy brały się stąd, że uważałem, iż nie może być adresu wskaźnika wskazującego na NULL. Ale już wiem, co zrobić- jak zdefiniuję Tree ptr=NULL i potem prześlę do funkcji &ptr, to będzie ok. Pomyśleć, że dopiero wczoraj wieczorem zauważyłem analogię do typów wbudowanych :p.

Zrobiłem sobie taką funkcję wstawiającą do drzewa:

void wstaw(char* slowo, Tree* ptr, Tree* najczestsze, int top)
{
	if(*ptr==NULL)
	{
		*ptr=malloc(sizeof(struct Node));//!!!!!!!
		(*ptr)->licznik=1;
		(*ptr)->lewy=NULL;
		(*ptr)->prawy=NULL;
		kopiuj(slowo, (*ptr)->slowo);
	}
	else
	{
		if(porownaj(slowo, (*ptr)->slowo)==0)
		{
			(*ptr)->licznik++;
		}
		else
		{
			if(porownaj(slowo, (*ptr)->slowo)==-1){wstaw(slowo, &((*ptr)->lewy), najczestsze, top);}
			else{wstaw(slowo, &((*ptr)->prawy), najczestsze, top);}
		}
	}
}

I wywołuję ją w poniższej pętli:(wcześniej mam definicję Tree ptr=NULL; )

	while(scanf("%49s", slowo)!=EOF)
	{
		konwersjanaslowo(slowo);
		wstaw(slowo, &ptr, najczestsze, top);
	}

Przy wstawianiu pierwszego słowa jest wszystko ok, a przy wstawianiu drugiego wywala błąd programu. Empirycznie sprawdziłem, że chodzi o linijkę zaznaczoną wykrzyknikami. Uprzedzam pytania: funkcje porownaj i kopiuj są w porządku. Co znowu jest nie tak?

Zmień strukturę nStrukturę radzę zmienić na:

typedef struct Node
  {
   struct Node *lf,*rt;
   unsigned count;
   char word[1];
  } Node;
typedef struct Tree { Node *root; } Tree;

oraz wywal te najczestsze razem z top.

Ta funkcja powinna wyglądać następująco:

void insertByWord(Tree *T,const char *word)
  {
   int v;
   Node **curr=&T->root,*node;
   while(*curr)
     {
      v=stricmp(word,(*curr)->word);
      if(v<0) curr=&(*curr)->lf;
      else if(v>0) curr=&(*curr)->rt;
      else
        {
         ++(*curr)->count;
         return;
        }
     }
   v=strlen(word);
   node=malloc(sizeof(Node)+v);
   memcpy(node->word,word,v+1);
   node->count=1;
   node->lf=node->rt=NULL;
   *curr=node;
  }

Przebudowa drzewa wg wystąpień:

void insertByCount(Tree *T,Node *node)
  {
   Node **curr=&T->root;
   while(*curr) if(node->count<(*curr)->count) curr=&(*curr)->rt; else curr=&(*curr)->lf;
   node->lf=node->rt=NULL;
   *curr=node;
  }

void rebuildRecurenceByCount(Tree *T,Node *node)
  {
   if(!node) return;
   rebuildRecurenceByCount(T,node->lf);
   rebuildRecurenceByCount(T,node->rt);
   insertByCount(t,node);
  }

void rebuildByCount(Tree *T) { rebuildRecurenceByCount(T,T->root); } /* to odpalamy */

Aktualnie mój main wygląda nastepująco":

int main(int argc, char *argv[])
{
	int top=0;
	if(argc>1)
	{
		for(int i=0; argv[1][i]!=0; i++)
		{
			top=top*10+(int)argv[1][i]-48;
		}
	}else{top=100;}
	Tree* najczestsze=malloc(top*sizeof(Tree));
	for(int i=0; i<top; i++){najczestsze[i]=NULL;}
	Tree ptr=NULL;
	char slowo[50];
	while(scanf("%49s", slowo)!=EOF)
	{
		konwersjanaslowo(slowo);
		wstaw(slowo, &ptr, najczestsze, top);
	}
	wypisz(najczestsze, top);
	zwolnij_drzewo(&ptr);
	free(najczestsze);
	return 0;
}

Udało się, naprawiłem. Błąd w funkcji wstawiającej tkwił w linijce, której nie było. Teraz wygląda ona tak:

void wstaw(char* slowo, Tree* ptr)
{
	if(*ptr==NULL)
	{
		*ptr=(struct Node*) malloc(sizeof(struct Node));
		(*ptr)->licznik=1;
		(*ptr)->slowo=calloc(strlen(slowo)+1, sizeof(char)); //ta linijka
		strcpy((*ptr)->slowo, slowo);
		(*ptr)->lewy=NULL;
		(*ptr)->prawy=NULL;
	}
	else
	{
		int porownanie=stricmp(slowo, (*ptr)->slowo);
		if(porownanie==0){++(*ptr)->licznik;}
		else
		{
			if(porownanie>0){wstaw(slowo, &((*ptr)->lewy));}
			else{wstaw(slowo, &((*ptr)->prawy));}
		}
	}
}

Teraz mam tylko pytanie do zwalniania pamięci. Jeżeli zwolnię osobno wszystkie pola w mojej strukturze przy pomocy free, to jest to to samo co zwolnienie całej struktury?
Edit. Chodzi mi o to, czy funkcja:

void usun_drzewo(Tree* ptr)
{
	if(*ptr!=NULL)
	{
		usun_drzewo(&((*ptr)->lewy));
		usun_drzewo(&((*ptr)->prawy));
		free((*ptr)->slowo);
		free(&((*ptr)->licznik));
		*ptr=NULL;
	}
}

poprawnie zdealokuje pamięć. Bo jak chciałem napisać po prostu free(*ptr), to miałem błąd przy uruchamianiu.