migf1 Δημοσ. 29 Ιουλίου 2012 Δημοσ. 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** ); A* Sort(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 Η συνάρτηση λειτουργεί σωστά, όπως δείχνει και ο κώδικας που ποστάρισα (για αυτό τον ποστάρισα άλλωστε, για επιβεβαίωση πως λειτουργεί σωστά η συνάρτηση). Οπότε το πρόβλημα πιθανότατα είναι στον υπόλοιπο δικό σου κώδικα.
Re4cTiV3 Δημοσ. 29 Ιουλίου 2012 Δημοσ. 29 Ιουλίου 2012 (επεξεργασμένο) Φίλε δεν το είπα για να τρολάρω, το δοκιμασα με άλλες δυο υλοποιήσεις που βρήκα στο net.. και πάλι δεν.. > #include <stdlib.h> #include <stdio.h> #include <stdbool.h> /* The type link_t needs to be forward-declared in order that a self-reference can be made in "struct link" below. */ typedef struct link link_t; /* A link_t contains one of the links of the linked list. */ struct link { const void * data; link_t * next; }; /* linked_list_t contains a linked list. */ typedef struct linked_list { link_t * first; link_t * last; } linked_list_t; bool pSwap( link_t **p1, link_t **p2 ) { link_t *temp = NULL; if ( !p1 || !*p1 || !p2 || !*p2 ) return false; temp = *p1; *p1 = *p2; *p2 = temp; return true; } /* _ _ _ (_)_ __ (_) |_ | | '_ \| | __| | | | | | | |_ |_|_| |_|_|\__| */ /* The following function initializes the linked list by putting zeros into the pointers containing the first and last links of the linked list. */ static void linked_list_init (linked_list_t * list) { list->first = list->last = 0; } /* _ _ __ _ __| | __| | / _` |/ _` |/ _` | | (_| | (_| | (_| | \__,_|\__,_|\__,_| */ /* The following function adds a new link to the end of the linked list. It allocates memory for it. The contents of the link are copied from "data". */ static void linked_list_add (linked_list_t * list, void * data) { link_t * link; /* calloc sets the "next" field to zero. */ link = calloc (1, sizeof (link_t)); if (! link) { fprintf (stderr, "calloc failed.\n"); exit (EXIT_FAILURE); } link->data = data; if (list->last) { list->last->next = link; list->last = link; } else { list->first = link; list->last = link; } } /* _ | |_ _ __ __ ___ _____ _ __ ___ ___ | __| '__/ _` \ \ / / _ \ '__/ __|/ _ \ | |_| | | (_| |\ V / __/ | \__ \ __/ \__|_| \__,_| \_/ \___|_| |___/\___| */ /* Go along the list and operate on the data of each element with "callback". */ static void linked_list_traverse (linked_list_t * list, void (*callback) (void *)) { link_t * link; for (link = list->first; link; link = link->next) { callback ((void *) link->data); } } /* Free the list's memory. */ static void linked_list_free (linked_list_t * list) { link_t * link; link_t * next; for (link = list->first; link; link = next) { /* Store the next value so that we don't access freed memory. */ next = link->next; free (link); } } /* Example callback function. */ static void print_list (void * data) { printf ("%s ", (char *) data); } /* Make a list of words and then print them out. */ int main (void) { linked_list_t list; linked_list_init (& list); linked_list_add (& list, "this"); linked_list_add (& list, "is"); linked_list_add (& list, "a"); linked_list_add (& list, "linked"); linked_list_add (& list, "list"); linked_list_traverse (& list, print_list); printf ("\n\n"); if( pSwap(&list.first, &list.first->next->next) ) {;} linked_list_traverse (&list, print_list); system("pause"); linked_list_free (& list); return 0; } Y.Γ. το δοκίμασα και με τον κώδικα που έχεις στο site σου! > #include <stdio.h> #include <stdlib.h> typedef enum { FALSE=0, TRUE } Bool; /* ο δικός μας πρόσθετος τύπος Boolean */ typedef struct node { /* δομή του κάθε κόμβου της λίστας */ int value; struct node *next; } Node; typedef struct list { /* η κεντρική δομή της λίστας μας */ Node *head, *tail; int len; } List; /* ------------------------------------------------------------------ * Δημιουργία και εισαγωγή νέου κόμβου με τιμή value, στην ΑΡΧΗ της λίστας. * Επιστρέφει FALSE σε περίπτωση αποτυχίας της calloc(), αλλιώς TRUE * ------------------------------------------------------------------ */ Bool pSwap( Node **p1, Node **p2 ) { printf("%d<->%d\n", (*p1)->value, (*p2)->value); Node *temp = NULL; if ( !p1 || !*p1 || !p2 || !*p2 ) return FALSE; temp = *p1; *p1 = *p2; *p2 = temp; return TRUE; } Bool list_prepend( List *list, int value ) { Node *new = calloc(1, sizeof(Node) ); if ( !new ) return FALSE; new->value = value; if ( list->head == NULL ) { new->next = NULL; list->head = list->tail = new; } else { new->next = list->head; list->head = new; } (list->len)++; return TRUE; } /* ------------------------------------------------------------------ * Δημιουργία και εισαγωγή νέου κόμβου με τιμή value, στο τέλος της λίστας * με χρήση δείκτη tail για δραματική επίσπευση της ταχύτητας εισαγωγής. * Επιστρέφει FALSE σε περίπτωση αποτυχίας της calloc(), αλλιώς TRUE * ------------------------------------------------------------------ */ Bool list_append( List *list, int value ) { Node *new = calloc(1, sizeof(Node) ); if ( !new ) return FALSE; new->value= value; new->next = NULL; if ( list->head == NULL ) { list->head = list->tail = new; (list->len)++; return TRUE; } list->tail->next = new; list->tail = new; (list->len)++; return TRUE; } /* ------------------------------------------------------------------ * Τύπωμα του πεδίου value όλων των κόμβων της λίστας * ------------------------------------------------------------------ */ void list_print( List list ) { while ( list.head ) { printf("%d ", list.head->value); list.head = list.head->next; } putchar('\n'); /* αλλαγή γραμμής */ return; } /* ------------------------------------------------------------------ * Απελευθέρωση της μνήμης που έχουμε δεσμεύσει για κάθε κόμβο της λίστας * ------------------------------------------------------------------ */ void list_destroy( List list ) { if ( !list.head ) /* ισοδυναμεί με: if ( list.head == NULL ) */ return; Node *dummy = NULL; while ( list.head ) { /* ισοδυναμεί με: while ( list.head != NULL ) { */ dummy = list.head->next; free( list.head ); list.head = dummy; } return; } /* ------------------------------------------------------------------- */ int main ( void ) { List list = { NULL, NULL, 0 }; /* δημιουργία και εισαγωγή 1ου στοιχείου στο ΤΕΛΟΣ */ if ( list_append( &list, 52) == FALSE ) { /* αποτυχία */ puts("*** out of memory, aborting program"); exit( EXIT_FAILURE ); } /* δημιουργία και εισαγωγή 2ου στοιχείου στο ΤΕΛΟΣ */ if ( list_append( &list, 62) == FALSE) { /* αποτυχία */ puts("*** out of memory, aborting program"); list_destroy( list ); /* καταστροφή προηγούμενων κόμβων */ exit( EXIT_FAILURE ); } /* δημιουργία και εισαγωγή 3ου στοιχείου στην ΑΡΧΗ */ if ( list_prepend( &list, 72) == FALSE) { /* αποτυχία */ puts("*** out of memory, aborting program"); list_destroy( list ); /* καταστροφή προηγούμενων κόμβων */ exit( EXIT_FAILURE ); } /* δημιουργία και εισαγωγή 4ου στοιχείου στην ΑΡΧΗ */ if ( list_prepend( &list, 82) == FALSE) { /* αποτυχία */ puts("*** out of memory, aborting program"); list_destroy(list ); /* καταστροφή προηγούμενων κόμβων */ exit( EXIT_FAILURE ); } /* καταμέτρηση και τύπωμα του πλήθους των κόμβων στη λίστα */ printf("The list consists of %d nodes\n", list.len ); /* τύπωμα των πεδίων value του 1ου και του τελευταίου κόμβου */ printf("(head = %d, tail = %d)\n", list.head->value, list.tail->value); /* τύπωμα των στοιχείων της λίστας */ list_print( list ); system("pause"); if(pSwap(&list.head, &list.head->next->next)) { ;;;; } list_print( list ); system("pause"); /* αποδέσμευση όλων των κόμβων από τη μνήμη */ list_destroy( list ); exit( EXIT_SUCCESS ); } Επεξ/σία 29 Ιουλίου 2012 από Re4cTiV3
migf1 Δημοσ. 29 Ιουλίου 2012 Δημοσ. 29 Ιουλίου 2012 (επεξεργασμένο) Δεν εννοούσα ότι ήθελες να τρολάρεις! Στον κώδικα που ποστάρισες από το site μου το βλέπω να λειτουργεί μια χαρά . Δεν είναι λάθος της συνάρτησης pSwap() που ποστράρισα το ότι δεν φροντίζεις να κρατάς ενήμερο τον head (ενδεχομένως και τον tail) μετά από το swapping (του είπες να πάει τον head στο 3ο στοιχείο και το πήγε). ΥΓ. Τον κώδικα που ποστάρισες πριν από αυτόν του site μου δεν τον κοίταξα, υποθέτω όμως κάτι παραπλήσιο θα συμβαίνει κι εκεί. Επεξ/σία 29 Ιουλίου 2012 από migf1
Re4cTiV3 Δημοσ. 29 Ιουλίου 2012 Δημοσ. 29 Ιουλίου 2012 και του δυο ενδιάμεσους να αλλάξω πάλι δεν δουλεύει. Έξοδος 82 72 52 62 72<->52 82 52 62
imitheos Δημοσ. 29 Ιουλίου 2012 Δημοσ. 29 Ιουλίου 2012 και ένα δείγμα χρήσης της κάτι σαν το παρακάτω... > int main( void ) { int i1 = 0, i2 = 1; int *p1 = &i1, *p2 = &i2; <----- if ( pSwap( (void **)&p1, (void **)&p2 ) ) Δεν λειτουργεί σωστά αυτο που έγραψες.. Η συνάρτηση λειτουργεί σωστά, όπως δείχνει και ο κώδικας που ποστάρισα (για αυτό τον ποστάρισα άλλωστε, για επιβεβαίωση πως λειτουργεί σωστά η συνάρτηση). Οπότε το πρόβλημα πιθανότατα είναι στον υπόλοιπο δικό σου κώδικα. Στο κώδικα που ποστάρισες αλλάζεις 2 int δείκτες οπότε και λειτουργεί σωστά. Ο Re4ctiV3 όμως θέλει να αλλάζει κόμβους από λίστα οπότε δεν αρκεί αυτό που κάνει η παρούσα συνάρτηση να αλλάξει απλά τους 2 δείκτες. Σύγκρινε την pSwap με τον κώδικα που έδωσε ο DirectX και δες πόσα παραπάνω κάνει.
migf1 Δημοσ. 29 Ιουλίου 2012 Δημοσ. 29 Ιουλίου 2012 (επεξεργασμένο) Στο κώδικα που ποστάρισες αλλάζεις 2 int δείκτες οπότε και λειτουργεί σωστά. Ο Re4ctiV3 όμως θέλει να αλλάζει κόμβους από λίστα οπότε δεν αρκεί αυτό που κάνει η παρούσα συνάρτηση να αλλάξει απλά τους 2 δείκτες. Σύγκρινε την pSwap με τον κώδικα που έδωσε ο DirectX και δες πόσα παραπάνω κάνει. Όπως έγραψα και αρχικά δεν έχω κοιτάξει με προσοχή τους κώδικες που έχετε ποστάρει παιδιά, οπότε ενδέχεται να μιλάμε για διαφορετικό πράγμα. Όμως, η συνάρτηση που pSwap() που ποστάρισα δουλεύει σωστα για 2 οποιουσδήποτε δείκτες (είτε δείχνουν σε int , είτε σε κόμβους λίστας, είτε σε οτιδήποτε άλλο, primitive ή custom). Για παράδειγμα, ο κώδικας που ποστάρισα αρχικά τροποποιημένος μονάχα ως πρός το data-type των p1 και p2 ώστε να δείχνουν σε "κόμβους" λειτουργεί κανονικότατα... > #include <stdio.h> #include <stdlib.h> #include <stdbool.h> typedef struct node Node; struct node { int data; Node *next; }; /* ***************************************** */ 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 ) { Node *p1 = NULL, *p2 = NULL; if ( NULL == (p1 = calloc(1,sizeof(Node))) ) { puts( "calloc() failed;" ); exit(0); } if ( NULL == (p2 = calloc(1,sizeof(Node))) ) { puts( "calloc() failed;" ); free( p1 ); exit(0); } p1->data = 0; p2->data = 1; printf( "Before: p1 (%p): %d, p2 (%p): %d\n", p1, p1->data, p2, p2->data ); if ( pSwap( (void **)&p1, (void **)&p2 ) ) printf( "After : p1 (%p): %d, p2 (%p): %d\n", p1, p1->data, p2, p2->data ); else puts( "swapping failed!" ); free( p1 ); free( p2 ); system( "pause" ); exit(0); } δεν έχει καμία σχέση δηλαδή σε τι data-type δείχνουν οι p1 και p2 (αυτό ήταν άλλωστε και το point της παρουσίασης της στο νήμα αππο την μεριά μου). Έξοδος: > Before: p1 (00410128): 0, p2 (00410138): 1 After : p1 (00410138): 1, p2 (00410128): 0 και του δυο ενδιάμεσους να αλλάξω πάλι δεν δουλεύει. Έξοδος 82 72 52 62 72<->52 82 52 62 To swapping των δεικτών (η συνάρτηση δηλαδή) δουλεύει κανονικά. Αυτό που δεν δουλεύει είναι πως εκτός από το swapping των δεικτών πρέπει να ενημερώσεις και τα next fields των swapped κόμβων μετά από κάθε swap, κάτι που δεν το κάνεις. ... To swapping των δεικτών (η συνάρτηση δηλαδή) δουλεύει κανονικά. Αυτό που δεν δουλεύει είναι πως εκτός από το swapping των δεικτών πρέπει να ενημερώσεις και τα next fields των swapped κόμβων μετά από κάθε swap, κάτι που δεν το κάνεις. Παραθέτω κώδικα που κάνει swap 2 κόμβους κανονικής λίστας χρησιμοποιώντας την generic pSwap()... > #include <stdio.h> #include <stdlib.h> #include <stdbool.h> typedef struct node Node; struct node { int data; Node *next; }; /* ***************************************** */ bool pSwap( void **p1, void **p2 ) { void *temp = NULL; if ( !p1 || !p2 ) return false; temp = *p1; *p1 = *p2; *p2 = temp; return true; } /* ***************************************** */ bool swapNode( Node **n1, Node **n2 ) { if ( !n1 || !n2 ) return false; if ( !pSwap( (void **)n1, (void **)n2 ) ) return false; if ( !pSwap( (void **)&(*n1)->next, (void **)&(*n2)->next ) ) return false; return true; } /* ***************************************** */ int main( void ) { Node *list = NULL; if ( NULL == (list = calloc(1,sizeof(Node))) ) { puts( "calloc() failed;" ); exit(0); } if ( NULL == (list->next = calloc(1,sizeof(Node))) ) { puts( "calloc() failed;" ); free( list ); exit(0); } list->data = 0; list->next->data = 1; printf( "Before: list (%p): %d, list->next (%p): %d\n", list, list->data, list->next, list->next->data ); if ( swapNode( &list, &list->next ) ) printf( "After : list (%p): %d, list->next (%p): %d\n", list, list->data, list->next, list->next->data ); else puts( "swapping failed!" ); free( list->next ); free( list ); system( "pause" ); exit(0); } Επεξ/σία 29 Ιουλίου 2012 από migf1 2
Re4cTiV3 Δημοσ. 30 Ιουλίου 2012 Δημοσ. 30 Ιουλίου 2012 (επεξεργασμένο) Μπορείς να μου κάνεις μια printList που να εκτυπώνει την λίστα; αλλά πρώτα να έχει 3 κόμβους και να κάνεις μετά swapNode( &list, &list->next->next ) και μετά printList ; γιατί αυτό εμένα δεν δουλεύει; > #include <stdio.h> #include <stdlib.h> #include <stdbool.h> typedef struct node Node; struct node { int data; Node *next; }; /* ***************************************** */ bool pSwap( void **p1, void **p2 ) { void *temp = NULL; if ( !p1 || !p2 ) return false; temp = *p1; *p1 = *p2; *p2 = temp; return true; } /* ***************************************** */ bool swapNode( Node **n1, Node **n2 ) { printf("%d<->%d\n", (*n1)->data, (*n2)->data); if ( !n1 || !n2 ) return false; if ( !pSwap( (void **)n1, (void **)n2 ) ) return false; if ( !pSwap( (void **)&(*n1)->next, (void **)&(*n2)->next ) ) return false; return true; } /* ***************************************** */ int main( void ) { Node *list = NULL; if ( NULL == (list = calloc(1,sizeof(Node))) ) { puts( "calloc() failed;" ); exit(0); } if ( NULL == (list->next = calloc(1,sizeof(Node))) ) { puts( "calloc() failed;" ); free( list ); exit(0); } if ( NULL == (list->next->next = calloc(1,sizeof(Node))) ) { puts( "calloc() failed;" ); free( list ); exit(0); } list->data = 0; list->next->data = 1; list->next->next->data = 2; Node *walker = list; while(walker) { printf("%d->",walker->data); walker = walker->next; } puts("\n"); if ( swapNode( &list, &list->next->next ) ) puts(""); else puts( "swapping failed!" ); walker = list; while(walker) { printf("%d->",list->data); walker = walker->next; } free( list->next->next ); free( list->next ); free( list ); system( "pause" ); exit(0); } Επεξ/σία 30 Ιουλίου 2012 από Re4cTiV3
imitheos Δημοσ. 30 Ιουλίου 2012 Δημοσ. 30 Ιουλίου 2012 Μπορείς να μου κάνεις μια printList που να εκτυπώνει την λίστα; αλλά πρώτα να έχει 3 κόμβους και να κάνεις μετά swapNode( &list, &list->next->next ) και μετά printList ; γιατί αυτό εμένα δεν δουλεύει; > Node *walker = list; while(walker) { printf("%d->",walker->data); <--------- walker walker = walker->next; } puts("\n"); if ( swapNode( &list, &list->next->next ) ) puts(""); else puts( "swapping failed!" ); walker = list; while(walker) { printf("%d->",list->data); <------------- list walker = walker->next; } 1
Directx Δημοσ. 30 Ιουλίου 2012 Δημοσ. 30 Ιουλίου 2012 (επεξεργασμένο) Μπορείς να μου κάνεις μια printList που να εκτυπώνει την λίστα; αλλά πρώτα να έχει 3 κόμβους και να κάνεις μετά swapNode( &list, &list->next->next ) και μετά printList ; γιατί αυτό εμένα δεν δουλεύει; > #include <stdio.h> #include <stdlib.h> #include <stdbool.h> typedef struct node Node; struct node { int data; Node *next; }; /* ***************************************** */ bool pSwap( void **p1, void **p2 ) { void *temp = NULL; if ( !p1 || !p2 ) return false; temp = *p1; *p1 = *p2; *p2 = temp; return true; } /* ***************************************** */ bool swapNode( Node **n1, Node **n2 ) { printf("%d<->%d\n", (*n1)->data, (*n2)->data); if ( !n1 || !n2 ) return false; if ( !pSwap( (void **)n1, (void **)n2 ) ) return false; if ( !pSwap( (void **)&(*n1)->next, (void **)&(*n2)->next ) ) return false; return true; } /* ***************************************** */ int main( void ) { Node *list = NULL; if ( NULL == (list = calloc(1,sizeof(Node))) ) { puts( "calloc() failed;" ); exit(0); } if ( NULL == (list->next = calloc(1,sizeof(Node))) ) { puts( "calloc() failed;" ); free( list ); exit(0); } if ( NULL == (list->next->next = calloc(1,sizeof(Node))) ) { puts( "calloc() failed;" ); free( list ); exit(0); } list->data = 0; list->next->data = 1; list->next->next->data = 2; Node *walker = list; while(walker) { printf("%d->",walker->data); walker = walker->next; } puts("\n"); if ( swapNode( &list, &list->next->next ) ) puts(""); else puts( "swapping failed!" ); walker = list; while(walker) { printf("%d->",list->data); walker = walker->next; } free( list->next->next ); free( list->next ); free( list ); system( "pause" ); exit(0); } Άλλαξε το στο δεύτερο while(walker) το printf("%d->",list->data); σε printf("%d->",walker->data); και είσαι έτοιμος. ΕΞΟΔΟΣ: >0->1->2-> 0<->2 2->1->0-> Επεξ/σία 30 Ιουλίου 2012 από Directx 1
Re4cTiV3 Δημοσ. 30 Ιουλίου 2012 Δημοσ. 30 Ιουλίου 2012 (επεξεργασμένο) Ουπςςςς μμμ... κάνεις πρώτα swap τους κόμβους και μετά swap τους δεικτες των κόμβων καλό! Επεξ/σία 30 Ιουλίου 2012 από Re4cTiV3
migf1 Δημοσ. 30 Ιουλίου 2012 Δημοσ. 30 Ιουλίου 2012 (επεξεργασμένο) Ουπςςςς μμμ... κάνεις πρώτα swap τους κόμβους και μετά swap τους δεικτες των κόμβων καλό! Πάντως η δική μου συνάρτηση swapNodes() έχει bug-άρα παιδιά. Χρειάζεται να κρατάμε και τον ->next δείκτη του κόμβου που προηγείται του αρχικού p1 ώστε να τον βάλουμε να δείχνει στον swapped p1 μετά. Εν ολίγοις, η συνάρτηση swapNodes() που έχω γράψει παραπάνω είναι άχρηστη για γενική χρήση! Σορρυ! Επεξ/σία 30 Ιουλίου 2012 από migf1
Re4cTiV3 Δημοσ. 30 Ιουλίου 2012 Δημοσ. 30 Ιουλίου 2012 Αρα πρωτου κανουμε swap πρεπει να βρουμε τον προηγουμενο του p1?? και να βαλουμε prev->next να δειχνει στο swapped?
imitheos Δημοσ. 30 Ιουλίου 2012 Δημοσ. 30 Ιουλίου 2012 Ουπςςςς μμμ... κάνεις πρώτα swap τους κόμβους και μετά swap τους δεικτες των κόμβων καλό! Ναι. Εγώ άλλαζα πρώτα τους επόμενους οπότε όταν μετά άλλαζα τους κόμβους ήταν σαν μην είχα αλλάξει καθόλου τους επόμενους Πάντως η δική μου συνάρτηση swapNodes() έχει bug-άρα παιδιά. Χρειάζεται να κρατάμε και τον ->next δείκτη του κόμβου που προηγείται του αρχικού p1 ώστε να τον βάλουμε να δείχνει στον swapped p1 μετά. Εν ολίγοις, η συνάρτηση swapNodes() που έχω γράψει παραπάνω είναι άχρηστη για γενική χρήση! Σορρυ! Όταν γίνει dereference ο next του προηγούμενου κόμβου δεν θα διαβάσει την νέα τιμή που προέκυψε από το swap άρα την σωστή ?
migf1 Δημοσ. 30 Ιουλίου 2012 Δημοσ. 30 Ιουλίου 2012 Πρέπει να κάτσω να το δω με ησυχία κι εγώ, και όχι αποσπασματικά και στα γρήγορα όπως έκανα μέχρι τώρα. Είναι πιο tricky από ότι νόμιζα αρχικά. ΥΓ. Έχω να κάνω κάτι δουλειές τώρα (βασικά να δω τον λογιστή μου). Μετά θα πάω σπίτι και θα το κοιτάξω κι εγώ πιο προσεκτικά και αν έχω κάτι χρήσιμο να συνεισφέρω θα επανέλθω
migf1 Δημοσ. 30 Ιουλίου 2012 Δημοσ. 30 Ιουλίου 2012 ... Όταν γίνει dereference ο next του προηγούμενου κόμβου δεν θα διαβάσει την νέα τιμή που προέκυψε από το swap άρα την σωστή ? Ότι και να σου πω αυτή τη στιγμή ψέμματα θα είναι, γιατί έχω κάνει ένα κεφάλι καζάνι. Ξεκίνησα να γράφω από την αρχή ένα μικρό πρόγραμμα που να κάνει διάφορα σε μια απλα συνδεδεμένη λίστα, με κύριο στόχο το node swapping που συζητάμε εδώ... μου έβγαλε την ψυχή το swapping, οπότε το ποστάρω όπως είναι γιατί κυριολεκτικά ζαλίστηκα. Δεν χρησιμοποιεί καθόλου την pSwap(), δουλεύει απευθείας πάνω στους δείκτες και τα links των κόμβων με μια συνάρτηση swapNodes() η οποία χρησιμοποιεί μια άλλη συνάρτηση node_get_prev() για να βρει τους προηγούμενους κόμβους από αυτούς που της περνάμε ως ορίσματα (προς swapping δηλαδή). Είμαι σίγουρος πως υπάρχουν πολύ καλύτερες υλοποιήσεις, αλλά δεν την παλεύω άλλο... νομίζω πως δουλεύει σωστά όπως είναι, κρατώντας ενήμερους και τoυς δείκτες head και tail της λίστας όταν χρειάζεται (αν δηλαδή είναι ο ένας ή και οι 2 κόμβοι που του λέμε να κάνει swap). Όλη η ταλαιπωρία αυτή μπορεί να αποφευχθεί (όπως και να επισπευθεί δραματικά η ταχύτητα) αν αντί για απλη λίστα είχαμε διπλά συνδεδεμένη (οπότε η node_get_prev() δεν θα χρειαζόταν καθόλου). Εκείνος ο κόμβος dummyHead, τοπικά μέσα στην swapNodes() είναι για τις περιπτώσεις που του ζηταμε να κάνει swap τον list->head κι έχει 2πλή λειτουργικότητα: για να έχουμε prev κόμβο ακόμα και για τον list->head για να μπορούμε να κάνουμε recalc τον list->head σε περίπτωση που έχει γίνει swapped, σε Ο(1) με ανάθεση του dummyHead->next... κανονικά θα ήθελα να το κάνω inplace την ώρα που εξετάζω τους n1 και n2, αλλά δεν την παλεύω άλλο σήμερα με αυτό (ομοίως και για την list->tail) Επίσης, έχω απενεργοποιημένο μέσα σε #ifdef 0 στο σώμα της swapNodes() τον "καθαρό" κώδικα που κάνει swap χωρίς κανένα έλεγχο, ο οποίος προφανώς δεν ενημερώνει τα head και tail της λίστας, και νομίζω κρασάρει αν πάμε να κάνουμε swap τον 1ο κόμβο... ή δεν τον τυπώνει... δεν θυμάμαι ακριβώς τι κάνει τώρα, πάντως δεν δουλεύει σωστα. Δουλεύει για όλους τους υπόλοιπους κόμβους όμως (νομίζω ). Τον έχω αφήσει απενεργοποιημένο για να είναι πιο διακριτός ο αλγόριθμος του general case. Παρακαλώ, ότι πατάτα εντοπίσετε (καθώς και οποιαδήποτε βελτίωση, είτε αλγοριθμική, είτε εκτελεστική, είτε οτοδήποτε άλλο) παραθέστε την, για να μην πάρω κι άλλους στο λαιμό μου, όπως με την pSwap() Αν θέλετε να δοκιμάσετε πως κι αν δουλεύει με διάφορους κόμβους, αλλάξτε τα data των κόμβων στις 2 list_lookup_data() στην main(). Τώρα το έχω και κάνει swap τον list.tail (data = 9) με τον list.head (data = 0) αποθηκεύοντας τους κόμβους στους δείκτες p1 και p2, αντίστοιχα, τους οποίους και κάνω swap αμέσως μετά. Έχω βαλει να τυπώνει και διάφορα info πριν και μετά το swapping. Κώδικας... > /* C99 */ #include <stdio.h> #include <stdlib.h> #include <stdbool.h> typedef struct node Node; struct node { int data; Node *next; }; typedef struct { Node *head, *tail; int len; } List; /* ------------------------------------------------------------------ * */ void node_dump( const char *label, const Node *node ) { if ( label ) printf( "%s", label ); if ( !node ) { puts( " : this node is NULL!" ); return; } printf( " (%p) : %d, next", node, node->data ); if ( node->next ) printf( " (%p) : %d\n", node->next, node->next->data ); else puts( " (NULL)"); return; } /* ------------------------------------------------------------------ * */ Node *node_get_prev( const List *list, const Node *node ) { Node *prev = NULL; if ( !list || !list->head || !node || list->head == node ) return NULL; prev = list->head; while ( prev->next && prev->next != node ) prev = prev->next; return prev; } /* ------------------------------------------------------------------ * Swap 2 random nodes in the linked list */ bool swapNodes( List *list, Node *n1, Node *n2 ) { #if 1 Node *dummyHead = NULL, *tail = NULL; Node *prev1 = NULL, *prev2 = NULL, *temp = NULL; if ( !list || !list->head || !n1 || !n2 || n1 == n2 ) return false; if ( NULL == (dummyHead = calloc(1, sizeof(Node))) ) return false; // create a dymmy head node & find the previous nodes of both n1 and n2 dummyHead->next = list->head; prev1 = ( n1 == list->head ) ? dummyHead : node_get_prev(list, n1); prev2 = ( n2 == list->head ) ? dummyHead : node_get_prev(list, n2); if ( prev1 == prev2 ) { free( dummyHead ); puts( "*** cannot swap same nodes ***" ); return false; } // ensure list->tail will get updated tail = list->tail; if (n1 == tail) tail = n2; else if (n2 == tail) tail = n1; // swap the nodes prev1->next = n2; prev2->next = n1; temp = n2->next; n2->next = n1->next; n1->next = temp; // update list->tail list->tail = tail; // recalc list->head if necessary if ( dummyHead->next != list->head ) list->head = dummyHead->next; free( dummyHead ); return true; #else Node *prev1 = NULL, *prev2 = NULL, *temp = NULL; if ( !list || !list->head || !n1 || !n2 ) return false; prev1 = node_get_prev(list, n1); prev2 = node_get_prev(list, n2); prev1->next = n2; prev2->next = n1; temp = n2->next; n2->next = n1->next; n1->next = temp; return true; #endif } /* ------------------------------------------------------------------ * Insert data as FIRST node of list */ bool list_prepend( List *list, int data ) { Node *new = calloc(1, sizeof(Node) ); if ( !new ) return false; new->data = data; if ( list->head == NULL ) { new->next = NULL; list->head = list->tail = new; } else { new->next = list->head; list->head = new; } (list->len)++; return true; } /* ------------------------------------------------------------------ * Insert data as LAST node of list */ bool list_append( List *list, int data ) { Node *new = calloc(1, sizeof(Node) ); if ( !new ) return false; new->data = data; new->next = NULL; if ( list->head == NULL ) { list->head = list->tail = new; (list->len)++; return true; } list->tail->next = new; list->tail = new; (list->len)++; return true; } /* ------------------------------------------------------------------ * Delete node with data from the list */ bool list_delete( List *list, int data ) { Node *curr = NULL, *next = NULL; if ( !list->head ) // empty list return false; curr = list->head; // data equals the 1st node if ( data == curr->data ) { list->head = list->head->next; free( curr ); (list->len)--; return true; } // parse the list until either NULL or data is found // curr = list->head; next = curr->next; while ( next && data != next->data ) { curr = next; next = curr->next; } if ( !next ) // data was not found in list return false; curr->next = next->next; free( next ); (list->len)--; return true; } /* ------------------------------------------------------------------ * Lookup list for the 1st node containing the specified data */ Node *list_lookup_data( List *list, int data ) { Node *node = NULL; if ( !list ) return NULL; node = list->head; while ( node && data != node->data ) node = node->next; return node; } /* ------------------------------------------------------------------ * Print list contents */ void list_print( const List *list ) { Node *dummy = NULL; if ( !list ) return; dummy = list->head; while ( dummy ) { printf("%d ", dummy->data ); dummy = dummy->next; } putchar('\n'); // αλλαγή γραμμής return; } /* ------------------------------------------------------------------ * Free memory reserved for list */ void list_destroy( List *list ) { Node *dummy = NULL; if ( list->head == NULL ) return; while ( list->head ) { dummy = list->head->next; free( list->head ); list->head = dummy; } list->head = list->tail = NULL; list->len = 0; return; } /* ***************************************** */ int main( void ) { List list = { .head=NULL, .tail=NULL, .len=0 }; Node *p1 = NULL, *p2 = NULL; // fill in the linked list with 10 nodes (int data from 0 to 9) for (int i=0; i < 10; i++) list_append( &list, i); // print the list, along with head and tail info list_print( &list ); node_dump( "list.head", list.head ); node_dump( "list.tail", list.tail ); // set pointers p1 and p2 to 2 existed nodes p1 = list_lookup_data( &list, 9 ); p2 = list_lookup_data( &list, 0 ); puts( "\nBEFORE:" ); node_dump( "p1", p1 ); node_dump( "p2", p2 ); // swap the nodes pointed to by p1 and p2 // if ( p1 && p2 ) if ( !swapNodes( &list, p1, p2 ) ) puts( "swapping failed" ); puts( "\nAFTER:" ); node_dump( "p1", p1 ); node_dump( "p2", p2 ); putchar('\n'); // print the list, along with head and tail info list_print( &list ); node_dump( "list.head", list.head ); node_dump( "list.tail", list.tail ); list_destroy( &list ); system( "pause" ); exit(0); } Το βασικό που ήθελα να πετύχω είναι να κάνει swap 2 τυχαίους κόμβους ανεξαρτήτως ποιος από τους 2 βρίσκεται πρώτος μέσα στη λίστα (και όχι δηλαδή 2 διπλανούς και σε συγκεκριμένη σειρά όταν τους περνάμε στην swapNodes() ). Εξού και η ταλαιπωρία που τράβηξα. EDIT: Έξοδος... > 0 1 2 3 4 5 6 7 8 9 list.head (003e3dc0) : 0, next (003e3de0) : 1 list.tail (003e3e60) : 9, next (NULL) BEFORE: p1 (003e3e60) : 9, next (NULL) p2 (003e3dc0) : 0, next (003e3de0) : 1 AFTER: p1 (003e3e60) : 9, next (003e3de0) : 1 p2 (003e3dc0) : 0, next (NULL) 9 1 2 3 4 5 6 7 8 0 list.head (003e3e60) : 9, next (003e3de0) : 1 list.tail (003e3dc0) : 0, next (NULL)
Προτεινόμενες αναρτήσεις