Δομή Σωρού στην C

[drunken_guy]

Γεια σας παιδιά και καλή χρονιά. Έχουμε για άσκηση στην σχολή την δημιουργία ενός σωρού στην c. Έχω φτάσει αρκετά μακρυά πιστεύω. Αλλά έχω δυστυχώς segmentation, το οποίο εμφανίζεται στην γραμμή 62 του κώδικα που έχω επισυνάψει. Αυτό που προσπαθώ να κάνω είναι να διαβάσω μια σειρά λέξεων από τον χρήστη και έπειτα να τις ταξινομίσω αλφαβητικά σε δομή σωρού. Οποιαδήποτε ιδέα είναι ευπρόσδεκτη, γιατί έχω κολλήσει πολύ... Ευχαριστώ παιδια

 

Ο κώδικας μου:

>

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

void heapSort(char *words[],int length);
void siftDown(char *words[], int root, int bottom);




main()
{
char *frasi;
char *words[100];
int i=0;
char delims[]=" ";
char *result=NULL;
char *tok;
int length=0;
   frasi=(char*)malloc(sizeof(char)*100);
printf("Dwse mou lekseis: ");
gets(frasi);

for(i=0;i<100;i++)
{
       words[i]=NULL;
                     
   }

i=0;
   tok=strtok(frasi,delims);
   while(tok!=NULL){
   words[i]=(char*)malloc(sizeof(char)*(strlen(tok)+1));
   strcpy(words[i],tok);
   i++;
   tok=strtok(NULL,delims);                
   } 
   
i=0;
while(words[i]!=NULL)
{
                     printf("%s\n",words[i]);
                     i++;
   }
   length=i;
   heapSort(words,length);
   i=0;
   while(words[i]!=NULL)
{
                     printf("%s\n",words[i]);
                     i++;
   }

system("PAUSE");
}

void heapSort(char *words[],int length)
{
int i;
char *temp;
for(i=(length/2);i>=0;i--)
{
	siftDown(words,i,length-1);
}
for(i=length-1;i>=1;i--)
{
	strcpy(temp,words[0]);
	strcpy(words[0],words[i]);
	strcpy(words[i],temp);
	siftDown(words,0,i-1);
}
}

void siftDown(char *words[], int root, int bottom)
{
int done, maxChild;
char *temp;

done=0;
while((root*2<=bottom)&&(!done))
{
	if(root*2==bottom)
	{
	   maxChild=root*2;
	}
	else if(strcmp(words[root*2],words[root*2+1])>0)
	{
		maxChild=root*2;
	}
	else
	{
		maxChild=root*2+1;
	}
	if(strcmp(words[root],words[maxChild])<0)
	{
		strcpy(temp,words[root]);
		strcpy(words[root],words[maxChild]);
		strcpy(words[maxChild],words[root]);
		root=maxChild;
	}
	else done=1;
}
}

[ExaByte]

Το segmentation fault συμβαίνει γιατί στις συναρτήσεις heapSort και siftDοwn δεν δεσμεύεις την μεταβλητή temp με malloc και πας να κάνεις strcpy από ένα string σε χώρο που δεν έχεις δεσμεύσει.

 

Μερικές ακόμη παρατηρήσεις:

 

1.Μην χρησιμοποιείς την συνάρτηση gets γιατί δεν είναι ασφαλής.

2.Αν και είναι νωρίς άρχισε να βάζεις όπου πρέπει τους κατάλληλους ελέγχους πχ στην malloc:

αν έχεις char* a=malloc(10*sizeof(char)); από κάτω να κάνεις έλεγχο για το αν a==NULL και άλλους τέτοιους ελέγχους

3.Ακόμη χρησιμοποιείς την συνάρτηση malloc χωρίς να έχεις κάνει include την βιβλιοθήκη stdlib.

4.Όταν ποστάρεις κώδικα στο φόρουμ, βάζε τον μέσα στα tags code για να διατηρείται η στοίχιση!

πχ

>
lalalala
  lalalala
          lalalala

[Sudavar]

Ότι είπε ο προηγούμενος και θα σου πρότεινα να δοκιμάσεις debugging, σε τι δουλεύεις?? κάποιο IDE, απλό editor??

[drunken_guy]

@exabyte. Είχες δίκιο, το πρόβλημα ήταν πως δεν δέσμευα μνήμη για το temp. Πάλι καλά, γιατί φοβόμουν πως το πρόβλημα βρισκόταν κάπου στα αστεράκια ή στον πίνακα. Θα ήθελα να ρωτήσω και κάτι άλλο όμως. Πως γίνεται να μου δουλεύει αφού για κάθε θέση του πίνακα δεσμεύω δυναμικά χώρο ανάλογα με το μέγεθος της λέξης, και μετά στο swap είναι πιθανό στο ίδιο κελί να μπει λέξη με μεγαλύτερο μέγεθος;

 

@Sudavar. Χρησιμοποιώ το dev-c++ το οποίο γενικότερα έχει ένα debugging αλλά δεν είναι και τόσο χρήσιμο.

 

Τέλος πάντων ευχαριστώ πολύ για την βοήθεια, σίγουρα θα είχα κολλήσει για μέρες σε αυτό το σημείο.

 

ΥΣ. Είχα και λάθος στο swap στην siftDown.

[Timonkaipumpa]

 

 

@Sudavar. Χρησιμοποιώ το dev-c++ το οποίο γενικότερα έχει ένα debugging αλλά δεν είναι και τόσο χρήσιμο.

 

Τέλος πάντων ευχαριστώ πολύ για την βοήθεια, σίγουρα θα είχα κολλήσει για μέρες σε αυτό το σημείο.

 

ΥΣ. Είχα και λάθος στο swap στην siftDown.

 

 

Δοκίμασε το LCC για C IDE. Είναι κάπως παλιό... αλλά είναι αρκετά καλό και απλό.

[ExaByte]

Θα πρότεινα τώρα που είσαι στην αρχή να μην χρησιμοποιείς κάποιο IDE. Συνήθως τα IDE τα χρησιμοποιείς όταν δουλέυεις με άπειρες libraries. Θα σου πρότεινα να βάλεις linux (αν δεν έχεις ήδη) και να χρησιμοποιείς gcc/gdb για μεταγλώττιση/αποσφαλμάτωση.

[drunken_guy]

Έχω ακόμα μια απορία στο παραπάνω πρόγραμμα. Ο καθηγητής ζήτησε στην ταξινόμηση των λέξεων, να γίνεται η δουλειά με pointers και όχι με strcpy. Οπότε αυτό που σκέφτηκα είναι να αντικαταστήσω αυτά:

>strcpy(temp,words[0]); 
  strcpy(words[0],words[i]); 
  strcpy(words[i],temp);

>strcpy(temp,words[root]); 
  strcpy(words[root],words[maxChild]); 
  strcpy(words[maxChild],words[root]); 

με αυτά:

>   temp=words[0];
     words[0]=words[i];
     words[i]=temp;

>temp=words[root];
  words[root]=words[maxChild];
  words[maxChild]=temp;

Αλλά στην εκτύπωση δεν μου δουλεύουν, καθώς μου τυπόνονται πράγματα που πιστεύω πως είναι pointers. Καμιά ιδέα;

 

@ExaByte δουλεύω σε ubuntu με terminal αλλά ποτέ δεν είχα ψάξει το debuger του, οπότε προσπαθούσα με το debugging του dev που αποδυκνύεται μεγάλη απάτη. Οπότε μάλλον θα προσπαθήσω με gdb

[MitsakosGR]

Έχω ακόμα μια απορία στο παραπάνω πρόγραμμα. Ο καθηγητής ζήτησε στην ταξινόμηση των λέξεων, να γίνεται η δουλειά με pointers και όχι με strcpy. Οπότε αυτό που σκέφτηκα είναι να αντικαταστήσω αυτά:

>strcpy(temp,words[0]); 
  strcpy(words[0],words[i]); 
  strcpy(words[i],temp);

>strcpy(temp,words[root]); 
  strcpy(words[root],words[maxChild]); 
  strcpy(words[maxChild],words[root]); 

με αυτά:

>   temp=words[0];
  words[0]=words[i];
  words[i]=temp;

>temp=words[root];
  words[root]=words[maxChild];
  words[maxChild]=temp;

Αλλά στην εκτύπωση δεν μου δουλεύουν, καθώς μου τυπόνονται πράγματα που πιστεύω πως είναι pointers. Καμιά ιδέα;

 

@ExaByte δουλεύω σε ubuntu με terminal αλλά ποτέ δεν είχα ψάξει το debuger του, οπότε προσπαθούσα με το debugging του dev που αποδυκνύεται μεγάλη απάτη. Οπότε μάλλον θα προσπαθήσω με gdb

Δοκίμασε αυτό:

>   temp = words;
  words = words + i;
  words + i = temp;

Και αντίστοιχα για το άλλο.

Το words είναι pointer, το words[0] είναι τα περιεχόμενά του.

[drunken_guy]

Δοκίμασε αυτό:

>   temp = words;
  words = words + i;
  words + i = temp;

Και αντίστοιχα για το άλλο.

Το words είναι pointer, το words[0] είναι τα περιεχόμενά του.

Το θέμα είναι πως όλη η νοοτροπία της εργασίας δείχνει πως το words[0] πρέπει να είναι pointer, αφού ο words είναι πίνακας από pointers.