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

migf1 · 28 Ιουλίου 2012

Πάντως σίγουρα μιλάμε για micro-optimization, ειδικά τις σημερινές ημέρες. Προσωπικά χρησιμοποιώ την puts() όταν δεν χρειάζομαι printf() υπό την λογική "κακό δεν πρόκειται να κάνει ποτέ".

Υπάρχει ακόμα μια παράμετρος που έχει να κάνει με την ασφάλεια, ειδικά αν στην printf() λέμε να τυπώσει string που έχουμε διαβάσει από τον χρήστη: http://www.cis.syr.e...tstring-1.2.pdf (παρόλο που κι εγώ καμιά φορά υποκύπτω στο συγκεκριμένο σφάλμα, επειδή το ξεχνάω...τυπώνω δηλαδή string με printf()... αποτελεί όμως κι αυτό έναν λόγο που προσπαθώ να τυπώνω μόνο με puts() όταν δεν χρειάζεται printf()... για να έχω δλδ το κεφάλι μου ήσυχο).

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

Κοιτα εσυ εχεις πει οτι η I/O processing ειναι η πιο χρονοβορα.... τωρα μου την βγαζεις απλα αναξιοπιστη?

ή το ιδιο εννοεις και παλι?

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

Ίσως το αξιόπιστα δεν είναι η σωστή λέξη, το πρόβλημα είναι η άμεση εξάρτηση του I/O όχι μόνο με το εκάστοτε hardware αλλά και με την υλοποίησή του. Για αυτό έφερα ως παράδειγμα το big O notation, το οποίο αφενός θεωρεί το I/O σταθερά κι αφετέρου δεν μετράει χρόνο (ανεξαρτητοποιεί δηλαδή το εκάστοτε hardware από την μέτρηση).

Επεξ/σία 28 Ιουλίου 2012 από migf1

Re4cTiV3 · 28 Ιουλίου 2012

Είναι προτιμότερο να κάνεις swap τιμές ή pointers σε μια απλά συνδεδεμένη λίστα; τι εννοώ

Έστω swap [1] με [4].

[1] -> [2] -> [3] -> [4] -> [5]

Θα ήταν καλύτερο να αντιγράψουμε τιμές(το 1 με το 4) ή το πως δείχνουν οι pointers(το [4]->[2], [3]->[1], [1]->[5] );

Επεξ/σία 28 Ιουλίου 2012 από Re4cTiV3

migf1 · 28 Ιουλίου 2012

Είναι προτιμότερο να κάνεις swap τιμές ή pointers σε μια απλά συνδεδεμένη λίστα; τι εννοώ

Έστω swap [1] με [4].

[1] -> [2] -> [3] -> [4] -> [5]

Θα ήταν καλύτερο να αντιγράψουμε τιμές(το 1 με το 4) ή το πως δείχνουν οι pointers(το [4]->[2], [3]->[1], [1]->[5] );

Το πως δείχνουν οι pointers (το πλεονέκτημα γίνεται ακόμα πιο ορατό αν για παράδειγμα οι κόμβοι της λίστας αντί να περιέχουν απλά int περιέχουν π.χ. μεγάλα struct).

Re4cTiV3 · 28 Ιουλίου 2012

Αχμμμ τι κάνω λάθος;

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

typedef struct n
{
int num;
struct n* next;
}A;

void insertList(A **sPtr,int value);
void printList(A *);
void swap(A **, A**);

int main(int argc, char *argv[])
{
A *list = NULL;

insertList(&list,5);
insertList(&list,4);
insertList(&list,3);
insertList(&list,2);
insertList(&list,1);

printList(list);

swap(&list, &list->next->next->next);
printList(list);
return 0;
}

void insertList(A **sPtr,int value)
{
 A* newPtr;
 newPtr = malloc(sizeof( A )); //mem allocation

 if(newPtr == NULL) return ;

 newPtr->num = value;
 newPtr->next = *sPtr;
*sPtr = newPtr;
}

void printList(A *head)
{
while(head)
{
printf("%d->",head->num);
head = head->next;
}
printf("NULL\n\n");
}

void swap(A **to, A** from)
{
printf("%d<->%d\n", (*to)->num, (*from)->num);

A *prev = *to;
while(prev->next != *from)
prev = prev->next;

printf("temparw to %d\n", (*from)->next->num);
A *temp = (*from)->next;

printf("vazw to %d na deixnei sto %d\n", (*from)->num, (*to)->next->num);
(*from)->next = (*to)->next;

printf("vazw to %d na deixnei sto %d\n", prev->num, (*to)->num);
prev->next = *to;

printf("kai vazw to %d na deixnei sto %d giati deixnei sto %d\n", (*to)->num, temp->num, (*to)->next->num);
(*to)->next = temp;

}

Χάνεται το head απο ότι καταλαβα??

Επεξ/σία 28 Ιουλίου 2012 από Re4cTiV3

Directx · 28 Ιουλίου 2012

Αχμμμ τι κάνω λάθος;

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

typedef struct n
{
int num;
struct n* next;
}A;

void insertList(A **sPtr,int value);
void printList(A *);
void swap(A **, A**);

int main(int argc, char *argv[])
{
A *list = NULL;

insertList(&list,5);
insertList(&list,4);
insertList(&list,3);
insertList(&list,2);
insertList(&list,1);

printList(list);

swap(&list, &list->next->next->next);
printList(list);
return 0;
}

void insertList(A **sPtr,int value)
{
 A* newPtr;
 newPtr = malloc(sizeof( A )); //mem allocation

 if(newPtr == NULL) return ;

 newPtr->num = value;
 newPtr->next = *sPtr;
*sPtr = newPtr;
}

void printList(A *head)
{
while(head)
{
printf("%d->",head->num);
head = head->next;
}
printf("NULL\n\n");
}

void swap(A **to, A** from)
{
printf("%d<->%d\n", (*to)->num, (*from)->num);

A *prev = *to;
while(prev->next != *from)
prev = prev->next;

printf("temparw to %d\n", (*from)->next->num);
A *temp = (*from)->next;

printf("vazw to %d na deixnei sto %d\n", (*from)->num, (*to)->next->num);
(*from)->next = (*to)->next;

printf("vazw to %d na deixnei sto %d\n", prev->num, (*to)->num);
prev->next = *to;

printf("kai vazw to %d na deixnei sto %d giati deixnei sto %d\n", (*to)->num, temp->num, (*to)->next->num);
(*to)->next = temp;

}

Χάνεται το head απο ότι καταλαβα??

Εκ πρώτης όψεως το NEXT του "NODE 5" (θα έπρεπε να ήταν το NODE 4 btw) δεν έχει ανανεωθεί και παραμένει NULL οπότε η λίστα διακόπτεται εκεί (1->5->NULL/Τέλος) - Συνεπώς το NODE 5 αφού είναι "τελικό" (δεν ακολουθείται από άλλο NEXT) οφείλει να δείχνει στο αμέσως επόμενο του, ενώ παράλληλα θα πρέπει το τελικό NODE της λίστας που προκύπτει μετά το SWAP και αυτό με την σειρά του να οδηγεί το NEXT του σε NULL.

--UPDATE:

Με πρόλαβε ο φίλος imitheos με μια πολύ καλή λύση

Επεξ/σία 28 Ιουλίου 2012 από Directx

imitheos · 28 Ιουλίου 2012

Αχμμμ τι κάνω λάθος;

>
void swap(A **to, A** from)
{
printf("%d<->%d\n", (*to)->num, (*from)->num);

A *prev = *to;
while(prev->next != *from)
prev = prev->next;

** Εδώ το prev είναι το 3ο στοιχείο **

printf("temparw to %d\n", (*from)->next->num);
A *temp = (*from)->next;

** Το temp είναι το 5ο **

printf("vazw to %d na deixnei sto %d\n", (*from)->num, (*to)->next->num);
(*from)->next = (*to)->next;

** Το επόμενο του 4ο στοιχείου θα είναι το επόμενο του 1ου δηλαδή το 2 άρα έχουμε 1->2->3->4->2->3->4->2... **

printf("vazw to %d na deixnei sto %d\n", prev->num, (*to)->num);
prev->next = *to;

** Το επόμενο του 3ου στοιχείου θα γίνει το 1ο, άρα έχουμε 1->2->3->1->2->3.... **

printf("kai vazw to %d na deixnei sto %d giati deixnei sto %d\n", (*to)->num, temp->num, (*to)->next->num);
(*to)->next = temp;

** Το επόμενο του 1ου στοχείου θα γίνει το 5ο άρα έχουμε 1->5 **

}

Edit: Μια γρήγορη λύση είναι η παρακάτω

>
void swap(A **to, A** from)												
{																			
 printf("%d<->%d\n", (*to)->num, (*from)->num);

 A *temp = (*from)->next;
 printf("To temp einai to %d\n", temp->num);

 printf("To %d ginetai %d\n", (*from)->next->num, (*to)->next->num);
 (*from)->next = (*to)->next;

 printf("To %d ginetai %d\n", (*to)->next->num, temp->num);
 (*to)->next = temp;

 temp = (*from);
 printf("To temp einai to %d\n", temp->num);
 printf("To %d ginetai %d\n", (*from)->num, (*to)->num);
 (*from) = (*to);
 printf("To %d ginetai %d\n", (*to)->num, temp->num);
 (*to) = temp;																			
}

Έξοδος:
before
1->2->3->4->5->NULL

1<->4
To temp einai to 5
To 5 ginetai 2
To 2 ginetai 5

To temp einai to 4
To 4 ginetai 1
To 1 ginetai 4
after
4->2->3->1->5->NULL

Στο 1ο στάδιο αλλάζουμε τους επόμενους κόμβους, δηλαδή το 1ο στοιχείο έχει ως επόμενο το 5 ενώ το 4ο έχει ως επόμενο το 2. Αν σε αυτό το σημείο τυπώναμε την λίστα θα είχε την μορφή 1->5->NULL (και σε ένα μακρινό σύμπαν 2->3->4->2).

Στο 2ο στάδιο αλλάζουμε τους ίδιους τους κόμβους. Στη θέση του 4ου κόμβου μπαίνει ο 1ος και στη θέση του 1ου ο 4ος οπότε και έχουμε το τελικό 4->2->3->1->5.

Επεξ/σία 28 Ιουλίου 2012 από imitheos

Re4cTiV3 · 28 Ιουλίου 2012

Το 'χασα λίγο!

(te = temp, fr = from)

[1] -> [5]

to te

[4] -> [2] -> [3] -> [4]....

fr

Μέχρι εδω όλα εντάξει!

Στο 2ο στάδιο κάνεις αυτό

===== temp = (*from); =====

[1] -> [5]

to

[4] -> [2] -> [3] -> [4].....

fr

te

====== (*from) = (*to); ====

[1] -> [5]

to

fr

[4] -> [2] -> [3] -> [4]......

te

====== (*to) = temp; ====

[1] -> [5]

fr

[4] -> [2] -> [3] -> [4]......

te

to

Πως συνδέεται το 3 με το 1;

Επεξ/σία 28 Ιουλίου 2012 από Re4cTiV3

imitheos · 28 Ιουλίου 2012

Το 3ο στοιχείο έχει ως επόμενο μια διεύθυνση μνήμης η οποία αρχικά είναι το 4ο στοιχείο. Όταν όμως με το (*from) = (*to) εναλλάξαμε τα στοιχεία, κάναμε την διεύθυνση αυτή να αντιστοιχεί στο 1ο στοιχείο.

Re4cTiV3 · 28 Ιουλίου 2012

Αν είναι ο επομενοσ κόμβος, αυτό δεν δουλεύει

Επεξ/σία 28 Ιουλίου 2012 από Re4cTiV3

Directx · 28 Ιουλίου 2012

Αν είναι γειτονικός κόμβος, αυτό δεν δουλεύει

Το swap είναι tricky διότι υπό συνθήκες τα "to" & "from" μπορεί να οδηγήσουν σε recursion οπότε με την βοήθεια του debugger μου εντόπισα μερικές από αυτές τις περιπτώσεις και τις εξάλειψα μέσο ifs.

Ο κώδικας δεν είναι καθαρός και φυσικά μπορεί να περιέχει bugs ή άλλες αβλεψίες (ζητώ συγγνώμη εκ των προτέρων αλλά πάει πολύς καιρός που έπαιζα με λίστες σε C και αν ήθελα υποχρεωτικά swap θα προτιμούσα ανταλλαγή τιμών παρά διευθύνσεων - τώρα πια δουλεύω με STL, JAVA & C# που παρέχουν έτοιμα containers).

ΚΩΔΙΚΑΣ:

>
void swap(A **to, A** from)
{
   printf("%d<->%d\n", (*to)->num, (*from)->num);

    A *temp_a = *to,
      *temp_b = *from,
      *temp_c = (*from)->next;

    if(temp_a == temp_c)
    {
       void *addr = temp_c->next;

       (*from)= temp_a;
       temp_a->next = temp_b;
       temp_b->next = (A*)addr;

       /*puts("Recursive trap!");*/
    }
    else
    {
        *to = *from;

        if(*to == temp_a->next)
        {
           (*to)->next = temp_a;
           temp_a->next = temp_c;

           /*puts("Recursive trap!");*/
        }
        else
        {
            (*to)->next = temp_a->next;
            *from = temp_a;
            (*from)->next = temp_c;
        }
   }
}

* Ο κώδικας έχει δοκιμασθεί σε C++ Builder.

ΕΙΣΟΔΟΣ / ΕΞΟΔΟΣ:

>
1->2->3->4->5->NULL

1<->4
4->2->3->1->5->NULL

***

1->2->3->4->5->NULL

5<->4
1->2->3->5->4->NULL

***

1->2->3->4->5->NULL

3<->2
1->3->2->4->5->NULL

***

1->2->3->4->5->NULL

5<->5
1->2->3->4->5->NULL

***

1->2->3->4->5->NULL

1<->1
1->2->3->4->5->NULL

(Ελπίζω να μην έχω κάνει κάποιο λάθος κατά το copy & paste της εξόδου του προγράμματος)

--UPDATE:

Αναθεώρηση της συνθήκης "if(temp_a == temp_c)" ώστε να δουλεύει σωστά (ελπίζω )..

Επεξ/σία 28 Ιουλίου 2012 από Directx

imitheos · 28 Ιουλίου 2012

Αν είναι ο επομενοσ κόμβος, αυτό δεν δουλεύει

Αν λάβουμε υπόψη ότι το έγραψα μέσα σε 2 λεπτά και ενώ ταυτόχρονα εγκαθιστούσα το Skyrim στο Wine, και που παίζει για μη γειτονικούς κόμβους πάλι καλά είναι. Ούτε του παπά να μη το πούμε

Re4cTiV3 · 29 Ιουλίου 2012

Δεν περίμενα τόσο κώδικα για swap :/

Η υλοποίηση σου δούλευε για όλες τις περιπτώσεις!

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

Ήθελα να κάνω sorting σε λίστα γι αυτό και το swap..

Επεξ/σία 29 Ιουλίου 2012 από Re4cTiV3

ChRis6 · 29 Ιουλίου 2012

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

Ακριβως

Η διαδικασια ειναι ασυγχρονη και δεν μπορεις να πεις εγγυημενα ποσο χρονο διαρκει. Ακομα και με flush δεν ειναι απολυτα σωστη η μετρηση

migf1 · 29 Ιουλίου 2012

Δεν περίμενα τόσο κώδικα για swap :/

Η υλοποίηση σου δούλευε για όλες τις περιπτώσεις!

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

Ήθελα να κάνω sorting σε λίστα γι αυτό και το swap..

Καλησπέρα (σόρυ για την καθυστερημένη απάντηση, αλλά έφυγα χτες για μπάνιο εκείνη την ώρα και γύρισα σήμερα πριν λίγο )

Λοιπόν, δεν κοίταξα αναλυτικά τον κώδικα που ποστάρισες, ούτε τις προτάσεις των άλλων παιδιών, είδα όμως πως δεν χρησιμοποιείτε dedicated συνάρτηση που να κάνει απλώς swap 2 δείκτες. Με υλοποίηση μιας τέτοιας, ξεχωριστής συνάρτησης, ενδέχεται να απλοποιηθεί μετά πολύ ο κώδικας της συνάρτησης που θα κάνει το sorting (και θα χρησιμοποιεί την swap() ).

Μια γενική υλοποίηση συνάρτησης που κάνει swap απευθείας 2 δείκτες θα μπορούσε να είναι κάπως έτσι...

>
/* ***************************************** */
bool pSwap( void **p1, void **p2 )
{
   void *temp = NULL;

   if ( !p1 || !*p1 || !p2 || !*p2 )
    return false;

   temp = *p1;
   *p1 = *p2;
   *p2 = temp;

   return true;
}

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

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

/* ***************************************** */
bool pSwap( void **p1, void **p2 )
{
   void *temp = NULL;

   if ( !p1 || !*p1 || !p2 || !*p2 )
    return false;

   temp = *p1;
   *p1 = *p2;
   *p2 = temp;

   return true;
}

/* ***************************************** */
int main( void )
{
   int i1 = 0, i2 = 1;
   int *p1 = &i1, *p2 = &i2;

   printf( "Before: p1 (%p): %d, p2 (%p): %d\n", p1, *p1, p2, *p2 );
   if ( pSwap( (void **)&p1, (void **)&p2 ) )
    printf( "After : p1 (%p): %d, p2 (%p): %d\n", p1, *p1, p2, *p2 );
   else
    puts( "swapping failed!" );

   system( "pause" );
   exit(0);
}

Το μείον αυτής της generic υλοποίησης της pSwap() είναι πως για να μην παίρνεις warnings (ή ακόμα και errors, αν είναι πολύ strict ο compiler) πρέπει να κάνεις cast τις διευθύνσεις των ορίσματων της συνάρτησης σε (void **) όταν την καλείς.

Το συν της είναι πως λειτουργεί με οποιοδήποτε data-type (π.χ. στο παραπάνω παράδειγμα λειτουργεί με int *, μπορείς να το δοκιμάσεις και με οποιοδήποτε άλλο data-type και θα λειτουργεί επίσης).

Αν σε χαλάει ότι πρέπει να κάνεις cast τις διευθύνσεις των ορίσματων σε (void **) μπορείς να τα συγκεκριμενοποιήσεις εξαρχής στο data-type με το οποίο σκοπεύεις να χρησιμοποιήσεις την συνάρτηση.

Δηλαδή, στο παραπάνω παράδειγμα, μπορείς να κάνεις τη συνάρτηση να λειτουργεί απευθείας με int ** (αντί για void **) οπότε δεν θα χρειάζεσαι το cast κατά την κλήση (δεν θα μπορείς όμως να την χρησιμοποιήσεις με άλλα data-types)...

>
...
/* ***************************************** */
bool pSwapInt( int **p1, int **p2 )
{
   int *temp = NULL;

   if ( !p1 || !*p1 || !p2 || !*p2 )
    return false;

   temp = *p1;
   *p1 = *p2;
   *p2 = temp;

   return true;
}

/* ***************************************** */
int main( void )
{
   int i1 = 0, i2 = 1;
   int *p1 = &i1, *p2 = &i2;

   printf( "Before: p1 (%p): %d, p2 (%p): %d\n", p1, *p1, p2, *p2 );
   if ( pSwapInt( &p1, &p2 ) )
    printf( "After : p1 (%p): %d, p2 (%p): %d\n", p1, *p1, p2, *p2 );
   else
    puts( "swapping failed!" );

   system( "pause" );
   exit(0);
}

Είτε έτσι, είτε αλλιώς, έχοντας ξεχωριστή συνάρτηση για το swapping των δεικτών, μπορείς να την χρησιμοποιήσεις σε οποιονδήποτε αλγόριθμο ταξινόμησης λιστών που χρησιμοποιεί swapping. Ενώ τώρα, αν ειδα σωστά, η συνάρτηση που ονομάζεις swap() διατρέχει και τη λίστα, κάνει και sort;

Ίσως να κάνω λάθος για το τι ακριβώς κάνει η swap() σου, σίγουρα όμως δεν κάνει σκέτο swapping, όπως κατά την γνώμη μου θα έπρεπε να κάνει, για να είναι re-usable σε οποιονδήποτε αλγόριθμο ταξινόμησης.

EDIT: Μέγα πρόβλημα με τα tabs στον κώδικα η αναβάθμιση του φόρουμ

Επεξ/σία 29 Ιουλίου 2012 από migf1

Re4cTiV3 · 29 Ιουλίου 2012

Δεν λειτουργεί σωστά αυτο που έγραψες..

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

typedef struct n
{
   int num;
   struct n* next;
}A;

void insertList(A **sPtr,int value);
void printList(A *);
bool pSwap(A **, A** );

int main(int argc, char *argv[])
{
   A *list = NULL;
   
   insertList(&list,40);
   insertList(&list,70);
   insertList(&list,8);
   insertList(&list,45);
   insertList(&list,90);

   printList(list);

   if(pSwap(&list->next, &list->next->next)) {;}

   printList(list);

   return 0;
}

void insertList(A **sPtr,int value)
{
 A* newPtr;
 newPtr = malloc(sizeof( A )); //mem allocation

 if(newPtr == NULL) return ;
   
 newPtr->num = value;
 newPtr->next = *sPtr;
    *sPtr = newPtr;
}

void printList(A *head)
{
   while(head)
   {
       printf("%d->",head->num);
       head = head->next;
       //system("pause");
   }
   printf("NULL\n\n");
}


bool pSwap( A **p1, A **p2 )
{
       printf("%d<->%d\n", (*p1)->num, (*p2)->num);

    A *temp = NULL;

    if ( !p1 || !*p1 || !p2 || !*p2 )
		    return false;

    temp = *p1;
    *p1 = *p2;
    *p2 = temp;

    return true;
}

Έξοδος:

90->45->8->70->40->NULL

45<->8

90->8->70->40->NULL

Έχω βάλει και system("pause") στο printList για παν ενδεχόμενο infinite loop :-D

Επεξ/σία 29 Ιουλίου 2012 από Re4cTiV3

Σύνδεση

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

Προτεινόμενες αναρτήσεις

migf1

Συχνή συμμετοχή στο θέμα

Δημοφιλείς Ημέρες

Συχνή συμμετοχή στο θέμα

Δημοφιλείς Ημέρες

Δημοφιλή Μηνύματα

imitheos

migf1

defacer

Δημοσιευμένες Εικόνες

Re4cTiV3

migf1

Re4cTiV3

Directx

imitheos

Re4cTiV3

imitheos

Re4cTiV3

Directx

imitheos

Re4cTiV3

ChRis6

migf1

Re4cTiV3

imitheos

migf1

defacer

Σύνδεση