C συχνότητα εμφάνισης

[cyber_katsarida]

Παιδιά μια μικρή βοήθεια στη C. Έστω ότι έχω ένα πίνακα (ακεραίων,χαρακτήρων…) και θέλω να εμφανίσω τη συχνότητα εμφάνισης του κάθε στοιχείου.

Πχ. “insomnia” ->

i=2

n=2

s=1

o=1

m=1

a=1

Αυτό πως μπορώ να το κάνω, γιατί έχω κολλήσει;

Λογικά θέλω και 2ο πίνακα να κρατάει τις τιμές των συχνοτήτων εμφάνισης.

[drm]

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

 

 

>
 int Freq[26];
 char *c = ' .... .. .. .. ';
 for (int i = 0; i<26; i++) Freq[i] = 0;
 sz = sizeof(c);
 for (int i =0; i < sz; i++) Freq[c[i]-'a']++;  

[cyber_katsarida]

κάτι τέτοιο σκεφτόμουνα κι εγώ.

 

αν δεν κάνω λάθος

αντι για sz = sizeof©; - > strlen.

έχω κάνει και μια μετατροπή του string σε lowcase πριν τη διαδικασία.

 

απλά σκέφτηκα και μια άλλη λύση.

να διαβάζω τη συμβολοσειρά και κάθε στοιχείο που βρίσκω να το βάζω σε μια στήλη ενός πίνακα 2 στηλών και στην άλλη στήλη να βάζω τον αριθμό εμφάνισης.μόνο που πρέπει να κάνω και έλεγχο ώστε να μη μπει ένα στοιχείο 2 φορές.

[macabre_sunsets]

>#include <stdio.h>

int main(void) {

  int N=256; //ή οσους χαρακτήρες θέλεις. 256 για να τους παίρνει όλους τους ASCII
  int i=0, j=0; 
  char *string; // το string που θέλεις να μετρήσεις την συχνότητα των χαρακτήρων του

  int **table = NULL;

  table = (int **) malloc(sizeof(int *) * N);

  string="insomnia";
  
  if (table == NULL) {
     printf("Unable to allocate enough memory!");
     exit(1);
  }

  for(i=0; i<N; i++) {

     table[i] = (int *)malloc(sizeof(int) * N);

     if (table == NULL) { 
        printf("Unable to allocate enough memory!");
        exit(1);
     }
  }

  for (i=0; i<N; i++) { // για όλους τους ASCII χαρακτήρες
     table[i][0] = i; // θέτει την μια τιμή ίση με το ASCII του χαρακτήρα για όλους τους χαρακτήρες
     table[i][1] = 0; // θέτει την συχνότητα του εκάστοτε χαρακτήρα 0
  }
  
  for (i=0; i<strlen(string); i++) // για κάθε γράμμα του string σου
  {
	table[string[i]][1]++; // η συχνότητα του εκάστοτε γράμματος + 1
  }

  for (i=0; i<N; i++) {
	if (table[i][1] != 0) // άμα η συχνότητα είναι διάφορη του μηδέν / άμα βρέθηκε ο τάδε χαρακτήρας
	{
		printf("%c : %d, ", table[i][0], table[i][1]); // εκτύπωσε τον χαρακτήρα και την συχνότητά του
		printf("\n"); // βάλε και μια κενή γραμμή
	}
  }

}

 

ouput :

>/home/lugubrious# ./a
a : 1,
i : 2,
m : 1,
n : 2,
o : 1,
s : 1,

[parsifal]

αν δεν κάνω λάθος

αντι για sz = sizeof©; - > strlen.

 

Σωστά, αν και είναι σχεδόν universal truth ότι σε ANSI C κάθε char πιάνει 1 byte, σε όποια αρχιτεκτονική και να δουλεύεις. Βέβαια, δεν είναι κακό να φυλάγεσαι, οπότε κάνε το με την strlen.

 

 

απλά σκέφτηκα και μια άλλη λύση.

να διαβάζω τη συμβολοσειρά και κάθε στοιχείο που βρίσκω να το βάζω σε μια στήλη ενός πίνακα 2 στηλών και στην άλλη στήλη να βάζω τον αριθμό εμφάνισης.μόνο που πρέπει να κάνω και έλεγχο ώστε να μη μπει ένα στοιχείο 2 φορές.

 

Είναι περιττή η χρήση δύο στηλών. Το σύνολο (με την αυστηρά μαθηματική έννοια) που εξετάζεις είναι οι lowercase λατινικοί χαρακτήρες, γνωρίζεις ότι είναι ακριβώς 26 τον αριθμό και επίσης ορίζεται διάταξη σε αυτούς. Οπότε, το indexing γίνεται εύκολα με την απλή πράξη που αναφέρει ο drm:

 

>c[i]-'a'

[_chris_]

μια ερώτηση πάνω σε αυτό.

αν αντί για χαρακτήρες είχαμε ακεραίους προφανώς αυτή η λύση δε βοηθάει.τι θα κάναμε σε αυτή την περίπτωση;

[georgemarios]

που να τους εχεις τους ακεραιους;

σαν string? δηλαδη "123456"?

σε αυτη τη περιπτωση θα ειναι (τροποποιωντας τον κωδικα του drm)

>
int Freq[[color=Red]10[/color]];
char *c = ' .... .. .. .. ';
for (int i = 0; i<10; i++) Freq[i] = 0;
sz = sizeof(c);
for (int i =0; i < sz; i++) Freq[c[i]-[color=Red]'0'[/color]]++; 

αν δεν ηθελες αυτο, εξηγησε τι ακριβως θες

 

PS... α μη ξεχασω

το

>for (int i = 0; i<10; i++) Freq[i] = 0; 

μπορει να αντικατασταθει με το

>memset(Freq,0,10);

δες το memset εδω

[_chris_]

εννοώ αυτό:

έχω τον παρακάτω πίνακα άκεραίων,(οι αριθμοί δεν είναι σαν string) και θέλω την συχνότητα εμφάνισης του κάθε ακεραίου.

 

>
int pinakas[]={135,758,135,2,135,1};

 

135 3 φορές

758 1

2 1

1 1

[georgemarios]

σε αυτη τη περιπτωση νομιζω η καλυτερη λυση ειναι να χρησιμοποιησεις ενα STL map

 

παραδειγμα:

 

>
#include <iostream>
#include <map>

using namespace std;

typedef map<int,int> IntMap;
IntMap counts;

int numbers[] = {135,758,135,2,135,1};


int main()
{
   // calculate the size of the array
   int sz = (int)(sizeof(numbers)/sizeof(int));
   
   // iterate through the elements of the array and
   // count the occurrences of each number
   for (int i=0; i<sz; i++)
   {
       // if the value in numbers[i] has never occurred before,
       // it will automatically be added to the counts map
       counts[ numbers[i] ]++;  
   }


   // now iterate through the map to show the results....
   IntMap::iterator it = counts.begin();
   for(it=counts.begin(); it!=counts.end(); it++)
   {
       cout << it->first << " " << it->second << endl;
   }

   return 0;
}

 

 

περισσοτερα για το map

εχει και μερικα παραδειγματα, το προγραμμα που εβαλα απο πανω το εγραψα απο μυαλο μου οποτε δε ξερω αν εχει λαθη (του πουστη ομως, 10 γραμμες κωδικα, λες να εκανα γκαφα? χαχα)

[_chris_]

Το πρόγραμμά σου δουλεύει μια χαρά.

Μόνο που είναι σε C++ και δεν έχω ιδέα.

Αναφερόμουνα σε C αν έχεις καμιά ιδέα.

[parsifal]

Για τη γενική περίπτωση, δε μπορείς να κάνεις direct indexing όπως με τους χαρακτήρες (κάποιου) αλφαβήτου, πρέπει να γίνει με άλλον τρόπος.

 

Μία προσέγγιση που μου έρχεται στο μυαλό είναι με 2-διάστατο πίνακα Nx2: στα κελιά της πρώτης στήλης θα αποθηκεύεις κάθε νέο αριθμό που συναντάς και στο διπλανό κελί την αντίστοιχη συχνότητα εμφάνισης. Αυτή η λύση όμως θα έχει ως υπολογιστικό κόστος την αναζήτηση που θα γίνεται κάθε φορά που συναντάται ένας αριθμός (θα πρέπει να διατρέχεις όλον τον πίνακα), ώστε να αποφασιστεί αν είναι νέος αριθμός ή αν υπάρχει ήδη καταχώρηση γι' αυτόν.

 

Μετά υπάρχουν και άλλα θέματα όπως π.χ. ο καθορισμός της διάστασης N: Θα είναι στατικός πίνακας αρκούντως μεγάλου μεγέθους (ρεαλιστικό ερώτημα, αν γνωρίζεις σίγουρα ότι η είσοδος θα περιορίζεται π.χ. σε αριθμούς από 0 ή 1 μέχρι 100, 1000 κλπ); Ή μήπως θα δεσμεύσεις δυναμικά μνήμη γι' αυτόν και πόση; Όταν χρειαστούν περισσότερες θέσεις μνήμης, θα κάνεις realloc για κάθε νέο στοιχείο ή μήπως θα κάνεις realloc φιξαρισμένου μέγεθους; Κ.ά...

[slvsnt]

Για τη γενική περίπτωση, δε μπορείς να κάνεις direct indexing όπως με τους χαρακτήρες (κάποιου) αλφαβήτου, πρέπει να γίνει με άλλον τρόπος.

 

Μία προσέγγιση που μου έρχεται στο μυαλό είναι με 2-διάστατο πίνακα Nx2: στα κελιά της πρώτης στήλης θα αποθηκεύεις κάθε νέο αριθμό που συναντάς και στο διπλανό κελί την αντίστοιχη συχνότητα εμφάνισης. Αυτή η λύση όμως θα έχει ως υπολογιστικό κόστος την αναζήτηση που θα γίνεται κάθε φορά που συναντάται ένας αριθμός (θα πρέπει να διατρέχεις όλον τον πίνακα), ώστε να αποφασιστεί αν είναι νέος αριθμός ή αν υπάρχει ήδη καταχώρηση γι' αυτόν.

 

Μετά υπάρχουν και άλλα θέματα όπως π.χ. ο καθορισμός της διάστασης N: Θα είναι στατικός πίνακας αρκούντως μεγάλου μεγέθους (ρεαλιστικό ερώτημα, αν γνωρίζεις σίγουρα ότι η είσοδος θα περιορίζεται π.χ. σε αριθμούς από 0 ή 1 μέχρι 100, 1000 κλπ); Ή μήπως θα δεσμεύσεις δυναμικά μνήμη γι' αυτόν και πόση; Όταν χρειαστούν περισσότερες θέσεις μνήμης, θα κάνεις realloc για κάθε νέο στοιχείο ή μήπως θα κάνεις realloc φιξαρισμένου μέγεθους; Κ.ά...

 

τελικά το έκανα με τον τρόπο που είπες.

όρισα έναν πίνακα ίσης διάστασης με τον αρχικό που έχω αποθηκευμένα τα στοιχεία

(μένει κενός χώρος βέβαια με αυτόν τον τρόπο)

και όταν τα εμφανίζω δεν εμφανίζω αυτά που έχουν συχνότητα μηδεν.

(έχω μηδενίσει τον πίνακα στην αρχή).