Προς το περιεχόμενο

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

Δημοσ.

 

 

Ας τρέξουμε σιγά σιγά τον κώδικα να δούμε τι δείκτες προκύπτουν. Χάριν ευκολίας ας ξεχάσουμε alignment και τέτοια και ας χρησιμοποιήσουμε 8 bytes για int και δείκτη ώστε να βγαίνουν πιο ωραία νούμερα :)

>
bool swapNodes( List *list, Node *n1, Node *n2 )
{

Σε αυτό το σημείο μόλις έχουμε μπει στην συνάρτηση και έχουμε την αρχική λίστα η οποία έχει ως εξής:

 

[1ος κόμβος]

10: 0

18: 0x20

[2ος κόμβος]

20: 1

28: 0x30

[3ος κόμβος]

30: 2

38: 0x40

[4ος κόμβος]

40: 3

48: 0x50

[5ος κόμβος]

50: 4

58: 0x60

[6ος κόμβος]

60: 5

68: 0x70

[7ος κόμβος]

70: 6

78: 0x80

[8ος κόμβος]

80: 7

88: 0x90

[9ος κόμβος]

90: 8

98: 0xa0

[10ος κόμβος]

a0: 9

a8: 0x00

 

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

 

>
prev1 = ( n1 == list->head ) ? dummyHead : node_get_prev(list, n1);
prev2 = ( n2 == list->head ) ? dummyHead : node_get_prev(list, n2);

 

Ο prev1 είναι ο κόμβος με τιμή 8 δηλαδή ο prev1 δείχνει στην διεύθυνση 0x90 και έχει επόμενο τον κόμβο με τιμή 9. Ο prev2 είναι ο dummyHead και έχει επόμενο τον κόμβο με τιμή 0.

 

>
// swap the nodes

prev1->next = n2;
prev2->next = n1;

 

[9ος κόμβος]

90: 8

98: 0x10

 

Εδώ παίρνουμε τον προηγούμενο κάθε κόμβου και τον βάζουμε να έχει ως επόμενο τον άλλον κόμβο. Έτσι ο prev2 δηλαδή ο dummyHead θα έχει επόμενο τον κόμβο με τιμή 9 και ο κόμβος με τιμή 8 δείχνει στον κόμβο με τιμή 0. Άρα η μόνη αλλαγή στη λίστα μας είναι η παραπάνω. Η διεύθυνση 0x98 άλλαξε ώστε να δείχνει στην 0x10.

 

>
temp = n2->next;
n2->next = n1->next;
n1->next = temp;

Εδώ γίνεται αλλαγή των δεικτών-επόμενων από τους ζητούμενους κόμβους. Αυτοί είναι ο επόμενος κόμβος του n2 (δηλαδή ο κόμβος με τιμή 1) και ο επόμενος κόμβος του n1 (δηλαδή ο null). Με αυτή την αλλαγή προκύπτει το παρακάτω τελικό layout.

 

[1ος κόμβος]

10: 0

18: 0x00

[2ος κόμβος]

20: 1

28: 0x30

[3ος κόμβος]

30: 2

38: 0x40

[4ος κόμβος]

40: 3

48: 0x50

[5ος κόμβος]

50: 4

58: 0x60

[6ος κόμβος]

60: 5

68: 0x70

[7ος κόμβος]

70: 6

78: 0x80

[8ος κόμβος]

80: 7

88: 0x90

[9ος κόμβος]

90: 8

98: 0x10

[10ος κόμβος]

a0: 9

a8: 0x20

 

Αν "διαβάσουμε" το παραπάνω layout βλέπουμε ότι όντως ισχύει 9->1->2->3->4->5->6->7->8->0. Επίσης παρατηρούμε ότι ο κώδικας αλλάζει τις διευθύνσεις των πεδίων next των 2 προς-εναλλαγή κόμβων καθώς και των προηγούμενων αυτών.

 

Ας κάνουμε τώρα το ίδιο για τον αρχικό κώδικα του Reactive με την swap αλλαγμένη όπως πρότεινες

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

 

Εδώ και πάλι είμαστε μόλις μπήκαμε στην συνάρτηση οπότε το layout στη μνήμη είναι το αρχικό της λίστας

 

[1ος κόμβος]

10: 9

18: 0x00

[2ος κόμβος]

20: 8

28: 0x10

[3ος κόμβος]

30: 7

38: 0x20

[4ος κόμβος]

40: 6

48: 0x30

[5ος κόμβος]

50: 5

58: 0x40

[6ος κόμβος]

60: 4

68: 0x50

[7ος κόμβος]

70: 3

78: 0x60

[8ος κόμβος]

80: 2

88: 0x70

[9ος κόμβος]

90: 1

98: 0x80

[10ος κόμβος]

a0: 0

a8: 0x90

 

Ο κώδικας του Reactive πρόσθετε στην αρχή της λίστας τον νέο κόμβο οπότε οι κόμβοι ακολουθούν αντίσροφο layout στη μνήμη.

 

>
	 temp = (*from);
	 (*from) = (*to);
	 (*to) = temp;

 

[2ος κόμβος]

20: 8

28: 0xa0

 

Εδώ η μόνη αλλαγή που βλέπουμε στον debugger είναι η παραπάνω, δηλαδή από εκεί που ο κόμβος με τιμή 8 έδειχνε σε αυτόν με τιμή 9 τώρα δείχνει στον κόμβο με τιμή 0. Ο τρόπος που καλέσαμε την συνάρτηση ήταν swap(&list, &list->next......->next) δηλαδή περάσαμε τις διευθύνσεις των δεικτών. Η διεύθυνση του δείκτη list είναι κάπου στην stack και η διεύθυνση του δείκτη "next" που δείχνει στο κόμβο με τιμή 9 είναι η 0x28 οπότε ουσιαστικά άθελά μας αλλάξαμε τον προηγούμενο κόμβο (διπλοί pointers rule :P)

 

>
	 temp = (*from)->next;
	 (*from)->next = (*to)->next;
	 (*to)->next = temp;

 

Εδώ πάλι έχουμε τα κλασικά και προκύπτει το τελικό layout που είναι:

 

[1ος κόμβος]

10: 9

18: 0x90

[2ος κόμβος]

20: 8

28: 0xa0

[3ος κόμβος]

30: 7

38: 0x20

[4ος κόμβος]

40: 6

48: 0x30

[5ος κόμβος]

50: 5

58: 0x40

[6ος κόμβος]

60: 4

68: 0x50

[7ος κόμβος]

70: 3

78: 0x60

[8ος κόμβος]

80: 2

88: 0x70

[9ος κόμβος]

90: 1

98: 0x80

[10ος κόμβος]

a0: 0

a8: 0x00

 

Αν "διαβάσουμε" το παραπάνω layout βλέπουμε ότι ισχύει 9->1->2->3->4->5->6->7->8->0. Επίσης και σε αυτή την περίπτωση, παρατηρούμε ότι ο κώδικας αλλάζει τις διευθύνσεις των πεδίων next των 2 προς-εναλλαγή κόμβων καθώς και των προηγούμενων αυτών.

 

Με λίγα λόγια, αν και δεν το τέσταρα για όλες τις περιπτώσεις αλλά μόνο για την αλλαγή 0<->9 που έτρεχαν από την μάνα τους οι κώδικες, οι κώδικες είναι ισοδύναμοι.

 

Όποιος διάβασε όλο το μήνυμα και δεν ήρθε κατευθείαν εδώ, μπράβο του :P

 

 

  • Like 2
  • Απαντ. 1,6k
  • Δημ.
  • Τελ. απάντηση

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

Δημοσ.

@imitheos:

 

(δεν βρίσκω εικονίδιο υπόκλισης στο φόρουμ :) )

 

Ομολογώ πως δεν έχω την υπομονή να κάνω τόσο λεπτομερές crash-test στους κώδικες (ούτε καν στον δικό μου).

 

Κάπου μπερδεύτηκα όμως, εννοείς πως η χρήση της pSwap() μια φορά για τους δείκτες των κόμβων και μια ακόμα για τους ->next των 2 κόμβων λειτουργεί; Εγώ έτσι πίστευα αρχικά, αλλά σε κάποια τεστ που έκανα διαπίστωσα πως δεν. Διότι πρέπει να χρησιμοποιήσουμε και τους prev του κάθε κόμβου, κάτι που ο παραπάνω τρόπος δεν το κάνει. Δεν θυμάμαι σε ποιες ακριβώς περιπτώσεις λειτουργούσε και σε ποιες όχι, θυμάμαι σίγουρα όμως πως σε κάποιες δεν λειτουργούσε, οπότε ήταν άχρηστη ως συνάρτηση γενικής χρήσης εκείνη η swapNodes().

 

ΥΓ. Τελικά λειτουργούσε εξαρχής ο κώδικας του φίλου Reactive; Ρωτάω επειδή παραπονέθηκε πως έχανε τον head, αλλά εγώ δεν τον έκανα trace (όπως δεν έκανα trace και τις προτάσεις που του κάνατε κι εσύ κι ο DirectX).

 

Αν δουλεύουν όλα πάντως, ακόμα καλύτερα διότι έτσι έχουμε 3-4 ισοδύναμες λύσεις για το ίδιο πρόβλημα :)

Δημοσ.

Κάπου μπερδεύτηκα όμως, εννοείς πως η χρήση της pSwap() μια φορά για τους δείκτες των κόμβων και μια ακόμα για τους ->next των 2 κόμβων λειτουργεί; Εγώ έτσι πίστευα αρχικά, αλλά σε κάποια τεστ που έκανα διαπίστωσα πως δεν.

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

Διότι πρέπει να χρησιμοποιήσουμε και τους prev του κάθε κόμβου, κάτι που ο παραπάνω τρόπος δεν το κάνει.

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

 

ΥΓ. Τελικά λειτουργούσε εξαρχής ο κώδικας του φίλου Reactive; Ρωτάω επειδή παραπονέθηκε πως έχανε τον head, αλλά εγώ δεν τον έκανα trace (όπως δεν έκανα trace και τις προτάσεις που του κάνατε κι εσύ κι ο DirectX).

 

Ως κώδικα του Reactive εννοώ με αλλαγμένη την swap του όπως είχες προτείνει στην swap_node (αν θυμάσαι εγώ άλλαζα πρώτα τους next και δεν έπαιζε ενώ εσύ έκανες το αντίθετο).

Δημοσ.

παιδες στις σχολες προγραματισμου σε διδασκουν μια συγκεκριμενη γλωσσα (αυτην που επελεξες εσυ) η ολα μαζι π.χ c,c++,java κ.λ.π?

Δημοσ.

ε;

Αν κρινω απο τις αποριες που βλεπω ανα τα φορουμ, @@ διδασκουν.

 

ΥΓ: Αν και νομιζω οτι εκανε λαθος ο τιμο, μαλλον ηθελε να πει δεν διδασκουν γλωσσες προγραμματισμου αλλα προγραμματισμο.

Δημοσ.

Αν κρινω απο τις αποριες που βλεπω ανα τα φορουμ, @@ διδασκουν.

 

ΥΓ: Αν και νομιζω οτι εκανε λαθος ο τιμο, μαλλον ηθελε να πει δεν διδασκουν γλωσσες προγραμματισμου αλλα προγραμματισμο.

 

 

Ναι... σόρρυ για το λάθος και thank you Duck!

Δημοσ.

 

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

void push(int n , int []);
void pop( int n , int []);
void error(int n);

int i;

int main(void) {

 int n;

 puts("Δωσε αριθμο στοιχειων  : ");
 scanf("%d" , &n);

 int arr[n];

 if(!n || n <0 )
 {
     error(n);
     exit(EXIT_FAILURE);
 }

 push( n , arr);
 pop( n , arr);
   
   return 0;
}

/********************************
*Εισαγωγή στοιχείων στη στοίβα  *
********************************/
void push( int n , int arr[n])
{
   i=0;
   printf("%d το πλήθος στοιχεία ... \n" , n);
   puts("Δωσε τα στοιχεια >");
   
   for(; i<n; i++)
   scanf("%d" , &arr[i]);
   
   return;
}
/********************************
*Εξαγωγή στοιχείων απο τη στοίβα*
********************************/
void pop(int n , int arr[n])

{
   i=n-1;
   
   puts("Υλοποιηση στοίβας .... ");
   
   for(; i>=0; i--)
   printf("%2d",arr[i]);
   
   return;
}
/********************************
*	  Χειρισμός λαθων		  *
********************************/
void error(int n)
{
   if(0==n)
   {
   puts("Η στοίβα ειναι κενή.");
   exit(EXIT_FAILURE);
}

if( n < 0 )
{
   puts("Λανθασμενη παραμετρος ");
   exit(EXIT_FAILURE);
}

return;

}
  

 

 

Μια στοίβα χωρις δείκτες :P

Δημοσ.

...

Μια στοίβα χωρις δείκτες

 

Χωρίς δείκτες έχει το μειονέκτημα της fixed χωρητικότητας. Επίσης, σύμφωνα με την τεκμηρίωση των στοιβών η push() ιδανικά πρέπει να πουσάρει ένα μόνο στοιχείο στη λίστα και η pop() να επιστρέφει το στοιχείο της κορυφής της λίστας (και χωρίς να χρειάζεται να περνάμε την χωρητικότητα της λίστας ως όρισμα).

 

Σου έγραψα ένα stack-interface που υλοποιεί κι αυτό την στοίβα ως πίνακα, αλλά ως δυναμικό πίνακα (δείκτη). Έτσι είναι πολύ πιο εύκολο να γίνει realloc() όποτε γεμίσει (δεν το έχω κάνει στον κώδικα που ακολουθεί)...

 

 

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

#define MAXINPUT        (255+1)

typedef struct Stack {
   int nelems;        // capacity of our stack
   int tos;        // index of top of stack
   int *array;        // our stack is a dynamic array
} Stack;

bool    init( Stack *stack, int maxelems );
bool    cleanup( Stack *stack );
bool    isEmpty( Stack *stack );
void    print( Stack *stack );
bool     push( Stack *stack, int data );
int    pop( Stack *stack );
bool     fill( Stack *stack );


/************************************************/
bool init( Stack *stack, int maxelems )
{
   if ( !stack || maxelems < 0
   || NULL == (stack->array = calloc(maxelems, sizeof(int))) )
       return false;

   stack->nelems = maxelems;
   stack->tos = -1;

   return true;
}
/************************************************/
bool cleanup( Stack *stack )
{
   if ( !stack )
       return false;

   if ( stack->array ) {
       free( stack->array );
       stack->array = NULL;
   }

   stack->tos = -1;
   stack->nelems = 0;

   return true;
}
/************************************************/
bool isEmpty( Stack *stack )
{
   if ( !stack || !stack->array || stack->tos < 0 )
       return true;

   return false;
}

/************************************************/
void print( Stack *stack )
{
   printf( "Εκτύπωση στοίβας: " );

   if ( !isEmpty(stack) ) {
       for (int i=0; i < stack->tos+1; i++)
           printf( "%d ", stack->array[i] );
       puts( "\b" );
   }
   else
       puts( "Η στοίβα είναι κενή" );

   return;
}

/************************************************/
bool push( Stack *stack, int data )
{
   if ( !stack || !stack->array ) {
       puts( "*** εσωτερικό σφάλμα ***" );
       return false;
   }
   if ( stack->tos == stack->nelems ) {
       puts( "*** η στοίβα είναι γεμάτη ***" );
       return false;
   }

   stack->array[ ++(stack->tos)] = data;
   return true;
}
/************************************************/
int pop( Stack *stack )
{
   if ( !stack || !stack->array ) {
       puts( "*** εσωτερικό σφάλμα ***" );
       return INT_MIN;
   }
   if ( isEmpty(stack) ) {
       puts( "Η στοίβα είναι κενή" );
       return INT_MIN;
   }

   return stack->array[ (stack->tos)-- ];
}
/************************************************/
bool fill( Stack *stack )
{
   char input[ MAXINPUT ] = {'\0'};

   if ( !stack )
       return false;

   for (int i=0; i < stack->nelems; i++)
   {
       printf( "Στοιχειο #%d: ", i+1 );
       if ( !fgets( input, MAXINPUT, stdin )
       || !push( stack, atoi(input) ) )
           return false;
   }

   return true;
}

/************************************************/
bool remove_all( Stack *stack )
{
   if ( isEmpty( stack ) ) {
       puts( "*** η στοίβα είνα κενή ή ανύπαρκτη ***" );
       return false;
   }

   for (int i=stack->tos; i > -1; i--)
       printf( "διαγραφή του %d\n", pop(stack) );

   return true;
}

/************************************************/
int main( void )
{
   char input[ MAXINPUT ] = {'\0'};
   Stack stack = { .nelems = 0, .tos = -1, .array = NULL };
   int maxelems = 0;

   // set capacity of the stack

   do {
       printf( "Πόσα στοιχεια συνολικά; " );
       fgets( input, MAXINPUT, stdin );
       maxelems = atoi( input );
   } while (maxelems < 1);

   if ( !init(&stack, maxelems) )
       goto exit_failure;
   printf( "-- επιτυχής δημιουργία στοίβας %d στοιχείων --\n", stack.nelems );

   if ( !fill( &stack ) ) {
       puts( "*** Παρουσιάστηκε σφάλμα κατά το γέμισμα της στοίβας ***" );
       goto exit_failure;
   }
   print( &stack );

   remove_all( &stack );
   print( &stack );

   cleanup( &stack );
   system( "pause" );        // windows only
   exit(0);

exit_failure:
   cleanup( &stack );
   system( "pause" );        // windows only
   exit(1);
}

 

 

 

Μπορεί να περιέχει bugs.

 

ΥΓ. Προσωπικά όταν θέλω στοίβα την υλοποιώ ως απλά συνδεδεμένη λίστα, και πολύ σπανιότερα ως δυναμικό πίνακα. Στατικό πίνακα ή VLA δεν χρησιμοποιώ σχεδόν ποτέ, διότι δεν βρίσκω να έχει κανένα ουσιαστικό πλεονέκτημα (αντίθετα έχει περισσότερα μειονεκτήματα)

.

Δημοσ.

Χρειαζεται να περνάς το μήκος του πινακα ως ορισμα γιατι το χρησιμοποιεις και στις 2 συναρτησεις.....

εκτος και αν εννοεις αλλο πραγμα... συμφωνα με την συγκεκριμενη παντα υλοποιηση. Δεικτες δεν εχω κοιταξει ακομη :P

Δημοσ. (επεξεργασμένο)

Χωρίς δείκτες, και χωρίς struct, θα μπορούσε να γίνει κάπως έτσι:

 

 

 

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

#define STACKSTART 1
#define HEAD 1
#define AMOUNTELEM 10

int initStack ( int theStack[] );
int pushStack ( int datum, int theStack[] );
int popStack ( int *datum, int theStack[] );
int isEmpty ( int theStack[] );
int isFull ( int theStack[] );
int sizeOfStack ( int theStack[] );


int main(int argc, char** argv)
{
int indx, datum, allOK;
int theStack[AMOUNTELEM]

allOK = initStack( theStack );

if ( allOK )
{
for ( indx = 0; indx <= AMOUNTELEM; indx++ )

{
 if ( !(pushStack(indx, theStack, AMOUNTELEM)))
 {
	if (!isFull(theStack))
	{
	 allOK = 0;
	}
	break;
 }
}
}

if ( !allOK )
{
printf("Found error\n");
} else {
for ( indx = 0; indx <= AMOUNTELEM; indx++ )
{
 if ( !(popStack( &datum, theStack, AMOUNTELEM)))
 {
	printf("End of list\n");
	break;
 } else {
	printf("Poped %d\n", datum);
 }
}
}
return (EXIT_SUCCESS);
}

int initStack ( int theStack[] )
{
int toReturn = 1;

theStack[0] = AMOUNTELEM;
theStack[HEAD] = STACKSTART;

return toReturn;
}

int sizeOfStack ( int theStack[] )
{
return theStack[0];
}

int isFull ( int theStack[] )
{
int toReturn = 0;

if ( !(sizeOfStack(theStack) - (theStack[HEAD] + 1) ) )
{
toReturn = 1;
}

return toReturn;
}

int isEmpty ( int theStack[] )
{
int toReturn = 0;

if ( theStack[HEAD] == STACKSTART )
{
toReturn = 1;
}

return toReturn;
}

]int pushStack ( int datum, int theStack[] )
{
int toReturn = 0;

if ( !(isFull((theStack))) )
{
theStack[theStack[HEAD]+1] = datum;
theStack[HEAD] += 1;
toReturn = 1;
}

return toReturn;
}

int popStack ( int *datum, int theStack[] )
{
int toReturn = 0;

if ( !(isEmpty((theStack))) )
{
*datum = theStack[theStack[HEAD]];
theStack[HEAD] -= 1;
toReturn = 1;
}

return toReturn;
}

 

 

 

edit: μπήκε spoiler

 

Υ.Γ. Δεν είναι απολύτως σωστό (bugs δεν έχει, νομίζω)... αλλά την χρήση θέλει να δείξει.

Επεξ/σία από Timonkaipumpa
Δημοσ.

Διαβάζω αυτή τη περίοδο για εισαγωγή ορισμάτων στη main και λέει το βιβλίο ότι τα ορίσματα γραμμής εντολής,μπλα μπλα μπλα...Γραμμή εντολής εννοεί το command prompt,σωστά:Γιατί εμένα δεν μπορεί να τρέξει τίποτα(το σφάλμα-'όνομα προγράμματος'δεν αναγνωρίζεται ως εσωτερική ή εξωτερική εντολή,εκτελέσιμο πρόγραμμα ή αρχείο δέσμης ενεργειών).

 

Υ.Γ.'όνομα προγράμματος' είναι ένα οποιοδήποτε όνομα,δεν είναι το όνομα που έχω δώσει εγώ στο πρόγραμμα.

Δημοσ.

Διαβάζω αυτή τη περίοδο για εισαγωγή ορισμάτων στη main και λέει το βιβλίο ότι τα ορίσματα γραμμής εντολής,μπλα μπλα μπλα...Γραμμή εντολής εννοεί το command prompt,σωστά:Γιατί εμένα δεν μπορεί να τρέξει τίποτα(το σφάλμα-'όνομα προγράμματος'δεν αναγνωρίζεται ως εσωτερική ή εξωτερική εντολή,εκτελέσιμο πρόγραμμα ή αρχείο δέσμης ενεργειών).

 

Υ.Γ.'όνομα προγράμματος' είναι ένα οποιοδήποτε όνομα,δεν είναι το όνομα που έχω δώσει εγώ στο πρόγραμμα.

 

Πρεπει να κανεςι registry το προγραμμα ως εντολη του cmd που δεν θυμαμαι πως γινεται. Τεσπα βαλε full path και θα εισαι οκ.

πχ

cmd

>
Microsoft Windows [Version 6.1.7600]
Copyright (c) 2009 Microsoft Corporation.  All rights reserved.
E:\Users\papi>"E:\Users\papi\Documents\visual studio 2010\Projects\Test1\Debug\t
est1.exe" arg1 arg2 arg3 klp
arg idx:0 arg:E:\Users\papi\Documents\visual studio 2010\Projects\Test1\Debug\te
st1.exe
arg idx:1 arg:arg1
arg idx:2 arg:arg2
arg idx:3 arg:arg3
arg idx:4 arg:klp
E:\Users\papi>

 

program

>
int main(int argc, char **argv)
{
int i;
for(i = 0; i < argc; i++)
 printf("arg idx:%d arg:%s\n",i,argv[i]);
return 0;
}

 

για vs users

 

 

Το visual studio εχει επιλογη που βαζεις τα agrs για debuging

project properties-> config prop -> debugging -> command args

 

 

Επισκέπτης
Αυτό το θέμα είναι πλέον κλειστό για περαιτέρω απαντήσεις.

  • Δημιουργία νέου...