Ερωτήσεις για C

[parsifal]

OK, φαίνεται πως έχεις κάποιο δίκιο και πρέπει να γίνει πιο χαλαρός ο αλγόριθμος:

 

http://en.wikipedia.org/wiki/Palindrome

 

A palindrome is a word, phrase, number, or other sequence of units that may be read the same way in either direction, with general allowances for adjustments to punctuation and word dividers.

 

Το έβλεπα πολύ αυστηρά το θέμα και αυτό που έγραψα πιο πάνω:

 

 

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

 

 

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

[migf1]

...

Παντως λογικα αν το σκεφτει κάποιος ο str αρχικα διατρέχει μια φορά μέχρι να φτάσει στο τελος , μετα μιση συνολικα εχει κανει κινηση 1 1/2 ενω ο last έχει κάνει 1/2 οποτε οταν θα έχει βρεθει η παλινδρομη ο str θα έχει κανει 1 + 1/2 και ο last μονο 1/2 + το 1 απο τον str οταν διαβάζαμε αρχικα την προταση. οΠΟΤΕ ολος ο αλγοριθμος ασχετα με τους δεικτες που χρησιμοποιούμε θα έχει κάνει 1 + 1/2 .  Μονο έτσι βγαίνει η αιτιολογηση του migf1

...

Στο Big-Oh notation οι τετριμμένες πράξεις (συγκρίσεις, εκχωρήσεις, κλπ) εντός του loop δεν μετράνε. Μετράνε μόνο οι επαναλήψεις του loop (iterations). Οπότε, όπως έγραψα εξαρχής, αφού βάλεις τον δείκτη στον τέλος της λίστας σε O(n), κατόπιν την διατρέχεις μισή φορά, τουτέστιν: O(n/2).

 

Όλο μαζί: O(n + n/2) = O(n * 1.5) = O(n).

 

 

Κύριοι, εχει μαλλιάσει η γλώσσα μου να απευθύνω προειδοποίησεις για τα δημόσια ξεκατινιάσματα. Ρίχνετε το επίπεδο του section.

 

Μετά την επιστροφή από το ban, σας θέλω αρνάκια...

To "αρνάκια" είναι σχετικό. Μιας και φτάσαμε στα άκρα, απλώς θα αλλάξω τακτική: θα γίνω "Κατίνα" και θα αρχίσω (για 1η φορά στη ζωή μου) να πατάω εκείνο το κουμπάκι που λέει "Αναφορά". Και κατόπιν θα περιμένω να δω αν και τι θα γίνει.

 

 

[Star_Light]

Έχω τον παρακάτω κώδικα (δεν ειναι δικος μου αλλα του Ilias95) ο οποίος υλοποιει με δισδιάστατο πινακα την αντιστροφη των λεξεων μιας προτασης πχ hello man -> man hello

 

 

 
#include <stdio.h>
#include <ctype.h>  // isspace()
#define MAXINPUT  255+1
#define MAXWORDS  30+1
#define LENWORD   20+1
int main( void )
{
    char input[MAXINPUT] = {'\0'}, words[MAXWORDS][LENWORD] = {{'\0'}};
    printf("Give a sentence: ");   
    fgets(input, MAXINPUT, stdin);
    
    int count =0;
      
    char *ch = input, *w, *c;
    // Ο w δείχνει στο τρέχον string του πίνακα word[i] κάθε φορά ο ch στον τρέχοντα χαρακτήρα
    // ο c στον τρέχοντα χαρακτήρα του τρέχοντος string του πίνακα word[i]. O w μετακινείται πιο κάτω
    // κατα w + LENWORD * sizeof (char) δηλαδή 21 θέσεις κάθε φορά και έτσι γεμίζουν οι επόμενοι πίνακες
    // words[0] , words[1] .... μέχρι ο w να δείχνει στον πίνακα words[20].
    
    for (w = words[0]; w <= words[MAXWORDS-1]; w += LENWORD) {
        for (; isspace(*ch); ch++);  // skip any blanks
        /*if (! *ch)
        {
            printf("\nPOTE: %d" , *ch);
            break;
        } */
      
        for (c = w; *ch && ! isspace(*ch); c++, ch++)
            *c = *ch;    // γέμισμα πίνακα
            
            count++;
                     
    }    
    
    printf(" %d " , count);
    
    printf("Reversal is: ");
   
    for (int i = MAXWORDS-1; i >= 0; i--)
        if (words[i][0])  // εκτυπώνει οσα strings υπάρχουν , έχουν γεμίσει τον πίνακα αντίστροφα.
            printf("%s ", words[i]);
                     
    putchar('\n');
    
    return 0;
}
 

 

 

Νομιζω οτι η if που έχω βαλει σε σχολια δεν χρειάζεται . Έχω κάποιες αποριες.... καταρχην γιατι θέλουμε +1 στο MAXWORDS ? Δεν καλύπτει το LENWORD με τον '\0'? Πρεπει δηλαδη και στις 2 διστάσεις να βάλουμε τον τερματικο χαρακτηρα του string? Αφου αν φτασουμε στην τελευταια λέξη ο τελευταιος character δεν θα ειναι ο '\0' λογω αρχικοποιησης?

 

Η fgets κοβει την εισοδο στους 255 χαρακτηρες μεχρι εκει διαβάζει... γιατι κανονικα ολος ο πινακας καταλαμβανει 31 * 21 * sizeof( char ) ετσι δεν ειναι?

 

Αν δώσεις μια λέξη μεγαλύτερη απο 20 ωφέλιμους μεσα στην προταση θα κρασάρει το προγραμμα και λογικο......

 

p.s Το char c = 'x' ;

 

if ( c )

puts("Right");

 

φανταζομαι ειναι legal ετσι?

[bird]

Στο MAXWORDS δε νομίζω οτι χρειάζεται +1 γιατί εκεί απλά δηλώνεις τον αριθμό των λέξεω που μπορείς να διαβάσεις, δεν αποθηκευεις κάποιο string για να χρειάζεσαι '\0'.
 

Η fgets κοβει την εισοδο στους 255 χαρακτηρες μεχρι εκει διαβάζει... γιατι κανονικα ολος ο πινακας καταλαμβανει 31 * 21 * sizeof( char ) ετσι δεν ειναι?

Τι εννοείς εδώ;
 
 

p.s Το char c = 'x' ;
 
if ( c )
puts("Right");
 
φανταζομαι ειναι legal ετσι?

Ναι legal είναι
 
edit:
Αν δώσεις λέξη με περισσότερους απο 20 χαρακτήρες πιθανοτατα δε θα κρασάρει (γιατί δεν πας να κάνεις access κάποιο στοιχείο πίνακα που δεν υπάρχει, μιας και αυξάνεις απλα τον δείκτη του πίνακα) όμως δε θα δουλεψει σωστά.
Τουλάχιστον σε εμένα (minGW) δεν κρασάρει...
 
PS2.

 

for (int i = MAXWORDS-1; i >= 0; i--)
     if (words[0]) // εκτυπώνει οσα strings υπάρχουν , έχουν γεμίσει τον πίνακα αντίστροφα.
     printf("%s ", words);

Ο πίνακας δεν έχει γεμίσει αντίστροφα, Έχει γεμίσει κανονικά (κάνοντας skip τα κενά) απλά τον τυπώνει ανάποδα.

[Star_Light]

Στο MAXWORDS δε νομίζω οτι χρειάζεται +1 γιατί εκεί απλά δηλώνεις τον αριθμό των λέξεω που μπορείς να διαβάσεις, δεν αποθηκευεις κάποιο string για να χρειάζεσαι '\0'.

 

Τι εννοείς εδώ;

 

 

Ναι legal είναι

 

edit:

Αν δώσεις λέξη με περισσότερους απο 20 χαρακτήρες πιθανοτατα δε θα κρασάρει (γιατί δεν πας να κάνεις access κάποιο στοιχείο πίνακα που δεν υπάρχει, μιας και αυξάνεις απλα τον δείκτη του πίνακα) όμως δε θα δουλεψει σωστά.

Τουλάχιστον σε εμένα (minGW) δεν κρασάρει...

 

PS2.

Ο πίνακας δεν έχει γεμίσει αντίστροφα, Έχει γεμίσει κανονικά (κάνοντας skip τα κενά) απλά τον τυπώνει ανάποδα.

 Ναι ουτε εγω νομιζω οτι χρειαζεται +1 στο MAXWORDS. Εννοω οτι ο πινακας εχει μεγεθος 31 * 21 = 651 bytes ενω η fgets δεν θα σε αφησει να δωσεις εισοδο πανω απο 255 χαρακτηρες. (Αλλωστε διαβαζει μεχρι nums - 1 ) , ναι ενταξει για το κρασαρει.... δεν χρησιμοποιησα καταλληλη λεξη. Αυτο που λες ειναι αλλα δεν θα το φτιαξω επισης το προγραμμα αν παρει σαν εισοδο 2 λεξεις hello man πχ θα τρεξει το σωμα του loop 30 φορες. Αλλα νταξ δεν με πειραζει ουτε και αυτο.

 

Δικιο εχεις και στον πινακα δεν εννοουσα οτι γεμιζει αντιστροφα .... εχει γεμισει κανονικα απλα εμεις τον βαζουμε να εκτυπωσει αντιστροφα με το if που εχει βαλει ομως δεν γλιτωνει και παλι τις 31 συγκρισεις.....

[bird]

Αν αλλάξεις το for σε:

for (w = words[0]; w <= words[MAXWORDS-1] && *ch; w += LENWORD){...

δε θα γλυτώσεις κάποιες επαναλήψεις; (μπορεί και να λέω βλακεία γιατί είμαι κουρασμένος και δεν πολυδιάβασα τον κώδικα )

[Star_Light]

Αν αλλάξεις το for σε:

for (w = words[0]; w <= words[MAXWORDS-1] && *ch; w += LENWORD){...

δε θα γλυτώσεις κάποιες επαναλήψεις; (μπορεί και να λέω βλακεία γιατί είμαι κουρασμένος και δεν πολυδιάβασα τον κώδικα )

 

 

Bασικα για αυτο το λογο ειχε και το if ( ! *ch) μεσα απλα το ειχα βγαλει σε σχολια οταν εβαλα τον count για να μετρησω και μου ξεφυγε.

 

 

 for (w = words[0]; w <= words[MAXWORDS-1]; w += LENWORD) {
        for (; isspace(*ch); ch++);  // Κάνε skip τους white space
        if (! *ch)
            break;  // Βγές οταν φτάσεις στον '\0'
      
        for (c = w; *ch && ! isspace(*ch); c++, ch++)
            *c = *ch;    // γέμισμα πίνακα
             
            count++;             
    }    
    
    printf(" %d " , count);
 

 

 

Καταλαβες? σιγα μην το εβαζε χωρις λογο ο Ilias μέσα ο '\0' δεν ειναι white space , πρεπει να ειμαστε λιγο πονηροι και εδω ακομη. Επισης μπορει να ξεφυγει κατι για πλακα... btw επιστρεφω σε λιγο με 2 αλλες ασκησεις που έχω γραψει.

[Star_Light]

Σε μια άσκηση που ζητάει να αντιστρέψεις ενα string..... το Hint που δινει ειναι :

 

Use two pointers , one initially pointing to the first character of the string and the other initially pointing to the last character . Have the function reverse these characters and then move pointers towards each other , repeating the process until the pointers meet

 

To bold δεν το καταλαβαινω.... να συναντηθουν στο μέσον? Εγω το εφτιαξα αλλιως

 

> #include<stdio.h>
#include<string.h>
#include <ctype.h>
#define STR_LEN 50
void reverse( const char []);
void read_line(char [] , int );
int main( void )
{
    char str[sTR_LEN + 1] = {'\0'};
    
    printf("Enter a word : \n");
    read_line(str , STR_LEN );  // Διάβασμα της λέξης
    puts("The reversal of the word: ");
    reverse( str );
    
        return 0;
}
void read_line(char str[] , int n)
{
    int ch , i=0;
    while( (ch = getchar()) != '\n' ) {
        
        if( !isalpha(ch)) {
        printf(" \n *Rejected* '%c' is not a letter " , ch);
        continue;
        }    // Aπορριψη χαρακτήρων που δεν ειναι γράμματα
        
        if(i < n )
        str[i++] = ch;
    }
        
        str[i] = '\0';
}

void reverse(const char* str) {
    
    const char *last = str + strlen(str) - 1;
    
    while( str <= last )
        putchar(*last--);
        
    }

 

Βασικα ειναι η λυση της 10 σελ 212 στο βιβλιο που έχουν προτεινει του King τα παιδια εδω για την C. Δεν ακολουθησα πιστα την εκφωνηση αλλα δουλευει.

 

Μια ακομα ασκηση που ελυσα ειναι η 5 επισης Σελ. 312 αλλα ειπα να προσθεσω και την επιλογη να μην υπολογιζονται στο αθροισμα χαρακτηρες που δεν ειναι αριθμοι :

 

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

int main(int argc , char *argv[])
{
    int i , sum=0;
    
    for( i = 1; i < argc; i++)
    {
        if ( isalpha( *argv[i] ) )
        continue;
        
        sum += atoi(argv[i]);
        
    }
    
    printf("Total: %d\n" , sum);
        
    return 0;
}

 

Πιστευω δουλευει σωστα.

[ChRis6]

 

Αρχη επαναληψης:

 

κανεις swap τους χαρακτηρες.

 

Μεγαλωνεις τον αριστερο δεικτη κατα 1.

Μικραινεις τον δεξιο δεικτη κατα 1.

 

Αν δειχνουν στην ιδια θεση μνήμης: break;

 

Τελος_επαναληψης

[παπι]

alternative

http://ideone.com/1Nt5nD

[Star_Light]

alternative

http://ideone.com/1Nt5nD

 

 

Ευχαριστω παπι. Βεβαια η εκφωνηση ζητα να αντιστρεψεις τα γραμματα μιας λεξης και οχι τις λεξεις μιας προτασης.

[migf1]

Σε μια άσκηση που ζητάει να αντιστρέψεις ενα string..... το Hint που δινει ειναι :

 

Use two pointers , one initially pointing to the first character of the string and the other initially pointing to the last character . Have the function reverse these characters and then move pointers towards each other , repeating the process until the pointers meet

 

To bold δεν το καταλαβαινω.... να συναντηθουν στο μέσον?

Προφανώς! Τι λέγαμε επί τόσα ποστ για την ανίχνευση παλίνδρομου (μέχρι και μπαν έφαγα). Σου λέει αυτό ακριβώς που κάνει ο κώδικας που σου είχα δώσει εκεί, και που σου εξήγησα ότι διατρέχει το string 1 1/2 φορά.

 

Ορίστε και ειδικά για το reverse: http://x-karagiannis.gr/prg/custom/doc/libs/html/s2_8c_source.html#l00310 .

 

Εγω το εφτιαξα αλλιως

 

 

 

 
#include<stdio.h>
#include<string.h>
#include <ctype.h>
#define STR_LEN 50
void reverse( const char []);
void read_line(char [] , int );
int main( void )
{
    char str[STR_LEN + 1] = {'\0'};
    
    printf("Enter a word : \n");
    read_line(str , STR_LEN );  // Διάβασμα της λέξης
    puts("The reversal of the word: ");
    reverse( str );
    
        return 0;
}
void read_line(char str[] , int n)
{
    int ch , i=0;
    while( (ch = getchar()) != '\n' ) {
        
        if( !isalpha(ch)) {
        printf(" \n *Rejected* '%c' is not a letter " , ch);
        continue;
        }    // Aπορριψη χαρακτήρων που δεν ειναι γράμματα
        
        if(i < n )
        str[i++] = ch;
    }
        
        str[i] = '\0';
}
void reverse(const char* str) {
    
    const char *last = str + strlen(str) - 1;
    
    while( str <= last )
        putchar(*last--);
        
    }

 

 

Βασικα ειναι η λυση της 10 σελ 212 στο βιβλιο που έχουν προτεινει του King τα παιδια εδω για την C. Δεν ακολουθησα πιστα την εκφωνηση αλλα δουλευει.

 

 

 

 

 

 

 

Διατρέχεις το string 1/2 φορά περισσότερη από ότι χρειάζεται.

 

Έχω τον παρακάτω κώδικα (δεν ειναι δικος μου αλλα του Ilias95) ο οποίος υλοποιει με δισδιάστατο πινακα την αντιστροφη των λεξεων μιας προτασης πχ hello man -> man hello

 

...

EDIT: Το παρακάτω έχει αλγοριθμικό λάθος. Το εντόπισε ο bird και το διόρθωσα σε νέο ποστ.

 

Δεν γνωρίζω αν είναι προαπαιτούμενο της άσκησης, αλλά για την αντιστροφή λέξεων αρκεί μονάχα ένα string, αυτό της εισόδου. Το διαβάζεις, αντιστρέφεις τους χαρακτήρες του και κατόπιν το τυπώνεις EDIT: αντιστρέφοντας τις λέξεις in-place.

 

 

...

s_getsflushed(s);

s_reverse(s);

for (int i=strlen(s)-1; i > -1; i--)

putchar( s[ i ] );

 

...

 

Προφανώς, μπορείς να βελτιστοποιήσεις το efficiency αν αντί για γενικές συναρτήσεις φτιάξεις εξειδικευμένες πάνω στο πρόβλημα. Όπως για παράδειγμα μια παραλλαγή της s_reverse() που αντί να σου επιστρέφει την αρχή του s να σου επιστρέφει το τέλος του.

Σε αυτή την περίπτωση το loop αλλάζει σε...

for (char *cp=s_reverse(s); cp && cp > s; cp--)
   putchar( cp );

και γλιτώνεις το strlen().

Ή μπορείς την s_getsflushed() να την βάλεις να σου επιστρέφει το πλήθος των χαρακτήρων που διάβασε, οπότε πάλι γλιτώνεις το strlen()... κλπ κλπ κλπ.

 

ΥΓ. Κι εδώ μια πολύ γενική και πολύπλοκη υλοποίηση: τεκμηρίωση, κώδικας.

Επεξ/σία 27 Ιανουαρίου 2013 από migf1

[bird]

 

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

 

 

...

s_getsflushed(s);

s_reverse(s);

for (int i=strlen(s)-1; i > -1; i--)

putchar( s[ i ] );

...

 

 

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

[Star_Light]

μιγφ1 εντάξει μην βαράς ...... αφαιρέθηκα.

 

 

 
char * reverse(char* str) {
    
    char *last = str + strlen(str) - 1;
    char dummy = '\0';
    
    while( str < last )
    {
        dummy = *str;
        *str = *last;
        *last = dummy;
        
        last--; str++;
        
    }
    
    return str;
}

[migf1]

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

Ουπς, έχεις απόλυτο δίκιο, my bad! Still, γίνεται με ένα μόνο string (της εισόδου) αλλά μετά την αντιστροφή των χαρακτήρων του το πιάνουμε από την αρχή και αντιστρέφουμε μια-μια τις λέξεις του in-place. Οπότε, αντί για το loop που έχω δώσει παραπάνω, βάζουμε κάτι σαν αυτό: http://stackoverflow.com/a/47426 (btw, αναφέρεται κι αυτός στα περί O(n/2)... λέγοντας κι αυτός το αυτονόητο "obviously").