Άσκηση σε γλωσσά c

[mike2012]

Παιδιά έχω να κάνω μια άσκηση η οποία λέει το έξεις :

 

Γράψτε ένα πρόγραμμα που θα διαβάζει από το πληκτρολόγιο έναν ακέραιο αριθμό

N, στη συνέχεια θα διαβάζει N λέξεις, θα υπολογίζει την πιο συχνή λέξη ανάμεσα στις N και

θα την τυπώνει.

 

Άλλα δεν μπορώ να βρω τον έλεγχο της συνθικης μπορεί κανείς να με βοηθήσει ???

 

Ευχαριστώ εκ τον προτέρων

[albNik]

Αν η strcmp επιστρέψει 0 τότε οι δυο λέξεις είναι ίδιες.

 

 

#include <stdio.h>

 

int strcmp(char *string1, char *string2);

[migf1]

Οι συχνότητες συνήθως μετριούνται με την βοήθεια ιστογράμματος, δηλαδή ενός πίνακα ακεραίων αρχικοποιημένου με μηδενικά. Κάθε θέση του ιστογράμματος αντιστοιχεί σε κάθε μοναδική διαβασμένη λέξη. Εφόσον δεν ξέρεις εξαρχής τις λέξεις, το ιστόγραμμά σου θα έχει Ν θέσεις.

 

Χρειάζεσαι επίσης έναν τρόπο να αντιστοιχείς την κάθε μοναδική λέξη από αυτές που διαβάζεις με την κατάλληλη θέση του ιστογράμματος, δηλαδή ένα hash function όπως λέγεται. Ιδανικά θα ήθελες μια perfect hashing function για τις λέξεις σου, αλλά αυτό είναι πρακτικά αδύνατον αν οι λέξεις σου έχουν απροσδιόριστο μήκος.

 

Μπορείς όμως να κάνεις κάτι που δεν είναι τόσο efficient όσο ένα κανονικό hash-function, αλλά δουλεύει για όλες τις λέξεις ανεξαιρέτως μήκους τους...

 

Φτιάχνεις έναν πίνακα από Ν λέξεις, και για κάθε λέξη που διαβάζεις την προσθέτεις σε αυτόν τον πινάκα μονάχα αν δεν υπάρχει ήδη. Είτε βρεις την λέξη, είτε όχι και την προσθέσεις στον πίνακα, αυξάνεις κατά ένα τον ακέραιο στην αντίστοιχη θέση του ιστογράμματος.

 

Για παράδειγμα...

 

>
...
int histogram[N] = {0};       // το ιστόγραμμα
char *arrWords[N] = {NULL}; // πίνακας Ν (απροσδιόριστου μήκους) λέξεων

int hash_word( const char *word, char *arrWords[N] );
...

 

Τη συνάρτηση hash_word() θα τη φτιάξεις να ψάχνει τη λέξη word στον πίνακα arrWords[].

 

Αν την βρει θα επιστρέφει τη θέση του πίνακα στην οποία βρέθηκε η λέξη. Αν δεν τη βρει θα την προσθέτει στην 1η διαθέσιμη θέση του πίνακα, την οποία και θα επιστρέφει. Σε περίπτωση σφάλματος (π.χ. αν ο πίνακας είναι ήδη γεμάτος) μπορείς να την βάλεις να επιστρέφει μια αρνητική τιμή (π.χ. -1, μιας και οι θέσεις πινάκων ξεκινάνε πάντα από 0).

 

Από εκεί και πέρα, η λύση συρρικνώνεται σε 2 loops (π.χ. μέσα στην main() ):

α) ένα για το διάβασμα και ταυτόχρονο hashing των N λέξεων

β) ένα για τον εντοπισμό της συχνότερης λέξης στο ιστόγραμμα...

 

>
int main( void )
{
   ...
   // read & hash words
   int posHashed = -1;
   for (int i=0; i < N; i++) {
       scanf("%s", word);   // word must have been already malloc'ed
       posHashed = hash_word(word, arrWords);
       if ( -1 != posHashed )
          histogram[ posHashed ]++;
   }

   // find most frequent word
   int maxFreq = posMaxFreq = -1;
   for (int i=0; i < N; i++) {
       if ( histogram[i] > maxFreq ) {
           maxFreq = histogram[i];
           posMaxFreq = i;
       }
   }

   // print most frequent word
   if ( -1 != posMaxFreq )
       printf( "most frequent word: %s (%d) times\n",
           (NULL == arrWords[posMaxFreq]) ?  "***ERROR***" : arrWords[ posMaxFreq ],
           histogram[ posMaxFreq ]    // or maxFreq
       );
   ...
}

 

ΥΓ. Ο κώδικας είναι untested (τον έγραψα απευθείας στον editor του φόρουμ, οπότε ενδέχεται να έχει bugs).

 

Επίσης, δεν προβλέπει περαιτέρω ανάλυση σε περίπτωση που υπάρχουν περισσότερες της μιας λέξης με την υψηλότερη συχνότητα εμφάνισης. Σε τέτοιες περιπτώσεις τυπώνει την 1η.

Επεξ/σία 26 Οκτωβρίου 2012 από migf1

[mike2012]

προσπαθω να εφαρμόσω όλα αυτα που μου λετε αλλα δεν τα καταφέρνω γινετε να μου τα κανετε πιο σαφη......εχω καταλαβει πως λειτουργεί h strcmp αλλα δεν μπορω να το κανω να μπει μια φορα

 

 

for( i=0; i<=n; i++)

{

for( j=0; j<n; j++)

{

if( strcmp( &l[j], &l[i+1][j])==0)

{

k++;

 

}

 

}

}

[migf1]

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

 

Σε περίπτωση που έχεις σημαντικές ελλείψεις υπόβαθρου δεν μπορείς να λύσεις την άσκηση. Αν υπάρχει χρόνος μπορείς να καλύψεις τις όποιες ελλείψεις διαβάζοντας την ύλη που προϋποθέτει η λύση της άσκηση. Αν δεν υπάρχει χρόνος, υποθέτω συμφιλιώνεσαι με την ιδέα πως δεν θα την λύσεις (ή προσπαθείς να βρεις να σου τη λύσει κάποιος άλλος, με ή χωρίς πληρωμή).

 

Μια πιθανή συνάρτηση που ελέγχει αν μια λέξη βρίσκεται ή όχι σε έναν πίνακα λέξεων (με περιορισμό πως αν μια θέση περιέχει NULL, σηματοδοτεί τη λήξη των χρήσιμων περιεχόμενων... συνήθως αναφέρονται ως NULL terminated string arrays) θα μπορούσε να είναι κάπως έτσι (!!!untested!!!)...

 

>
int arrWords_lookup( char *arrWords[N], const char *word )
{
   for (int i=0; i < N; i++) {
       if ( NULL == arrWords[i] )
           return -1;
       if ( 0 == strcmp(arrWords[i], word) )
           return i;
   }

   return -1;
}

 

Επιστρέφει -1 είτε σε περίπτωση ο πίνακας arrWords[] είναι γεμάτος είτε σε περίπτωση που η λέξη word δεν υπάρχει στον πίνακα. Aλλιώς επιστρέφει -1.

 

Για να μετατραπεί στη συνάρτηση hash_word() που αναφέρω στην αρχική μου απάντηση, θα πρέπει να τροποποιηθεί έτσι ώστε να προσθέτει την λέξη στην 1η διαθέσιμη του πίνακα, σε περίπτωση που δεν υπάρχει ήδη, και να επιστρέφειτη θέση της.

[albNik]

Μια άλλη μέθοδος που θα άρεσε και στον καθηγητή σου είναι να φτιάξεις μια συνδεδεμένη λίστα από struct.

Κάθε struct περιέχει τη λέξη (char* ), τον αριθμό εμφανίσεων της (freq), και το next.

Aν μια λέξη υπάρχει στη λίστα αύξησε της το freq κατά 1, αλλιώς πρόσθεσε στη λίστα ένα struct με τη συγκεκριμένη λέξη και freq=1.

[migf1]

Μια άλλη μέθοδος που θα άρεσε και στον καθηγητή σου είναι να φτιάξεις μια συνδεδεμένη λίστα από struct.

Κάθε struct περιέχει τη λέξη (char* ), τον αριθμό εμφανίσεων της (freq), και το next.

Aν μια λέξη υπάρχει στη λίστα αύξησε της το freq κατά 1, αλλιώς πρόσθεσε στη λίστα ένα struct με τη συγκεκριμένη λέξη και freq=1.

 

Yeap!

 

Αν και η λογική είναι ακριβώς η ίδια. Του πρότεινα πίνακα (δυναμικά ορισμένο ή VLA) γιατί η άσκηση δίνει πεπερασμένο πλήθος στοιχείων N.

 

Το ιστόγραμμα και ο arrWords[N] μπορούν να ενοποιηθούν σε έναν πίνακα, με το κάθε του στοιχείο να έχει την δομή που περιγράφεις).

[albNik]

Γενικά αποφεύγω τον πινάκα όταν το Ν το δίνει ο χρήστης. Η πίνακες θέλουν το Ν γνωστό από πριν.

[mike2012]

βασικά δεν μας έχει κάνει ακόμα πολυδιάστατους πινάκες και δεν ξέρω πως να τους χρησιμοποιήσω έχουμε κάνει μονό τα βασικά.. για αυτο

 

βασικά δεν μας έχει κάνει ακόμα πολυδιάστατους πινάκες και δεν ξέρω πως να τους χρησιμοποιήσω έχουμε κάνει μονό τα βασικά.. για αυτο

και προσπαθώ να λύσω την άσκηση με δισδιάστατο πινάκα

[migf1]

Γενικά αποφεύγω τον πινάκα όταν το Ν το δίνει ο χρήστης. Η πίνακες θέλουν το Ν γνωστό από πριν.

 

Οι δυναμικοί πίνακες όχι...

 

>
int n = 0, *arr = NULL;
...
scanf( "%d", &n)
...
if ( NULL == (arr=calloc(n, sizeof(int))) )
  exit(1);

for (int i=0; i < n; i+)
   printf( "%d ", arr[i] );
puts("\b");
...
free( arr );
exit(0);

 

βασικά δεν μας έχει κάνει ακόμα πολυδιάστατους πινάκες και δεν ξέρω πως να τους χρησιμοποιήσω έχουμε κάνει μονό τα βασικά.. για αυτο

 

και προσπαθώ να λύσω την άσκηση με δισδιάστατο πινάκα

 

Θα πρέπει τότε να μας πεις τι γνωσικοί περιορισμοί υπάρχουν για την λύση της άσκησης. Αν και οι λέξεις είναι έτσι κι αλλιώς 2Δ πίνακες χαρακτήρων, οπότε αν δεν σας έχει μιλήσει για 2Δ πίνακες, η άσκηση αυτή είναι εκτός ύλης.

[mike2012]

Βασικά αυτό που μας ζητάει η άσκηση είναι να βρούμε πόσες φορές εμφανίζετε μια λέξη ..... και όχι αν ένας πινάκας είναι γεμάτος

αυτό που κάνω εγώ είναι ότι δημιουργώ ένα πινάκα κ[1000][1000] και αποθηκευω μια λέξη σα κάθε γραμμή και μετά με την strcmp ελέγχω αν είναι αυτές οι δυο ίδιες αλλά αυτή ελενχει έναν έναν χαρακτήρα και μου αυξάνει τον μετρητή και εγώ θέλω να των αυξήσει μονο μια φορά

 

Οι δυναμικοί πίνακες όχι...

 

>
int n = 0, *arr = NULL;
...
scanf( "%d", &n)
...
if ( NULL == (arr=calloc(n, sizeof(int))) )
exit(1);

for (int i=0; i < n; i+)
printf( "%d ", arr[i] );
puts("\b");
...
free( arr );
exit(0);

 

 

 

Θα πρέπει τότε να μας πεις τι γνωσικοί περιορισμοί υπάρχουν για την λύση της άσκησης. Αν και οι λέξεις είναι έτσι κι αλλιώς 2Δ πίνακες χαρακτήρων, οπότε αν δεν σας έχει μιλήσει για 2Δ πίνακες, η άσκηση αυτή είναι εκτός ύλης.

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

[albNik]

Αν έχεις ένα μονοδιάστατο πίνακα από λέξεις με πολλαπλές εμφανίσεις πρέπει να κάνεις κάποια αλφαβητική ταξινόμηση. Αν έχετε μάθει bubble sort, merge sort η quicksort για αριθμούς , το ίδιο ισχύει και για λέξεις (τις συγκρίνεις ( < > = ) με την strcmp).

Μετά μετράς το bloc με τις περισσότερες επαναλαμβανόμενες λέξεις.

[mike2012]

στην c άμα αποθηκεύσω ένα string σε ενα πινάκα δεν βάζει στο κάθε "κουτί"ένα γραμμα

[migf1]

στην c άμα αποθηκεύσω ένα string σε ενα πινάκα δεν βάζει στο κάθε "κουτί"ένα γραμμα

 

Από default όχι. Το κάθε string είναι ένας πίνακας χαρακτήρων, ο οποίος για να μπορεί να χρησιμοποιηθεί με τις στάνταρ συναρτήσεις διαχείρισης της γλώσσας (όπως π.χ. την strcmp() ) πρέπει ο τελευταίος τους χρήσιμος χαρακτήρας να ακολουθείται από έναν ή περισσότερους μηδενικούς χαρακτήρες.

 

Ρίξε μια ματιά στο link της υπογραφής μου, ίσως σε βοηθήσει.

 

ΥΓ. Παρεμπιπτόντως, αν εξαιρέσουμε τις λέξεις, όλα τα υπόλοιπα που έχουμε γράψει στο νήμα χρησιμοποιούν λογική μονοδιάστατων πινάκων.

[albNik]

Μπορείς να έχεις μονοδιάστατο πινάκα από δείκτες σε λέξεις (char*).

 

Αν πας γράμμα γράμμα τότε θες διδιαστατο 1000x20 (πίνακα από πίνακες 1000 λέξεις , 19 γράμματα το πολύ η λέξη) ,μετά γίνεται πιο περίπλοκη η ταξινόμηση .