Εισαγωγη κομβου σε λιστα μεσω συναρτησης C

[nickname2016]

Sorry για το μεγεθος του post που θα ακολουθησει, αλλα δε με νοιαζει. Πρεπει να το καταλαβω αν θελω να γινω καλυτερος.

Ας πουμε φτιαχνω μια συναρτηση που φτιαχνει 1 απλα συνδεδεμενη λιστα τριων κομβων:

 

ο κομβος μου ειναι μια απλη δομη

struct node
{
	int data;
	struct node* next;
}

 

struct node* BuildOneTwoThree()
{
struct node* head = NULL;
struct node* second = NULL;
struct node* third = NULL;

//allocates 3 nodes in the heap
head = malloc(sizeof(struct node));
second = malloc(sizeof(struct node));
third = malloc(sizeof(struct node));

//setup first node!  note pointer assignment rule
head-> data = 1;
head-> next = second; //sharing situation here!

//setup second node
second-> data = 2;
second-> next = third;

//setup third node
third-> data = 3;
third-> next = NULL;

return head;
}

 

Ας πουμε τωρα οτι εγω θελω να φτιαξω μια συναρτηση που με το που την καλω, αυτη μου βαζει εναν κομβο στην αρχη της λιστας μου.

 

Ας πουμε πως αυτη η συναρτηση ειναι η push()

void Push(struct node* head, int data)
{
	struct node* newNode = malloc(sizeof(struct node));
	newNode->data = data;//Doesn't matter...just data
	newNode->next = head;
	head = newNode;  //NO this is wrong.
}		

Θα περιμενε κανεις οτι η τελευταια γραμμη ειναι σωστη. Ωστοσο ΔΕΝ ειναι σωστη.

Η τελευταια γραμμη setαρει τον head pointer, αλλα οχι τον σωστο head! Αυτος ο head, ειναι local variable στην Push. Δεν αλλαζει  τον head που θέλουμε ο οποιος ειναι στην συναρτηση PushTest(), η οποια καλει την Push()

void PushTest() 
{
	List head = BuildTwoThree();
	Push(head, 1); // try to push a 1 on front -- doesn't work
}

Αυτο που πρεπει να γινει στην ουσια ειναι η head να περαστει by reference. Ωστοσο η head ειναι ηδη pointer... αρα θα πρεπει να περαστει στην push() με δεικτη σε δεικτη:

void Push(struct node** head, int data).

Εδω εχω χαθει λιγακι...γιατι πρεπει να περαστει μεσω διπλου δεικτη ? Γιατι την πρωτα φορα δεν περνιεται ο σωστος head και χανεται με την επιστροφη, αφου ειναι pointer!
Για ποιο λογο δεν επιστρεφει αν περαστει ως απλο δεικτη  void Push(struct node* head, int data)?

[kaliakman]

Λοιπόν θα προσπαθήσω να βοηθήσω,

 

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

 

ΠΧ το κλασσικό παράδειγμα με την swap:

#include <stdio.h>
 
void swap(int*, int*);
 
int main()
{
   int x, y;
 
   printf("Enter the value of x and y\n");
   scanf("%d%d",&x,&y);
 
   printf("Before Swapping\nx = %d\ny = %d\n", x, y);
 
   swap(&x, &y); 
 
   printf("After Swapping\nx = %d\ny = %d\n", x, y);
 
   return 0;
}
 
void swap(int *a, int *
{
   int temp;
 
   temp = *b;
   *b   = *a;
   *a   = temp;   
}

Για να γίνει η δουλεία περνάει την διεύθυνση των α,β και τα ορίζει ως pointer για να γράψει εκεί η συνάρτηση.

 

Έτσι και στην δική σου συνάρτηση το head δείχνει(είναι pointer) στο κεφάλι της λίστας.Όταν τον περνάς ως μονό pointer έχεις το ίδιο effect με την swap. Αλλάζεις τοπικά την διεύθυνση που δείχνει αλλά όταν επιστρέφει δείχνει εκεί που έδειχνε πριν καλεστεί η συνάρτηση.

Οπότε χρειάζεσαι έναν pointer που δείχνει στην διεύθυνση του *head για να σωθεί αυτή η αλλαγή με την επιστροφή.

 

Ελπίζω να βοήθησα και να μην σε μπέρδεψα και άλλο

[defacer]

Να το πω λίγο διαφορετικά σε περίπτωση που βοηθάει.

 

Καταλαβαίνεις ήδη πως αν θέλεις να περάσεις οτιδήποτε σε μια function στην οποία αυτό το οτιδήποτε θα υποστεί αλλαγεί, και θέλεις αυτή η αλλαγή να είναι ορατή όταν η function επιστρέψει, θα πρέπει αντί για something_t να περάσεις something_t*. Αυτό είναι νόμος.

 

Αν θες να περάσεις λοιπόν ένα node και να του κάνεις αλλαγές, θα πρέπει να περάσεις node*. Αν θέλεις να περάσεις node* και να του κάνεις αλλαγές, θα πρέπει να περάσεις node**. Αν θες να περάσεις node**, κλπ κλπ.

 

Μάλλον έχεις μπερδευτεί επειδή σκέφτεσαι "άμα περάσω κάτι με pointer η αλλαγή θα πρέπει πάντα να φαίνεται". Αυτό ίσως προκύπτει από αρχικά στάδια εκμάθησης όπου έχεις να κάνεις με τα σούπερ βασικά σενάρια αντί για int περνάω int* κλπ, οπότε μπορεί να σχηματιστεί η λανθασμένη εντύπωση πως ο pointer είναι μαγική σκόνη που άμα τη βάλεις μια φορά η δουλειά γίνεται. Αυτό όμως δεν ισχύει, ο τρόπος που πρέπει να το σκέφτεσαι είναι ο παραπάνω.

[groot]

Αυτό που συμβαίνει, είναι λόγω της παρανόησης του call by reference και call by value. Συνήθως (βασικά, πάντα βάσει των δικών μου παραδειγμάτων), το μαθαίνουν το call by reference ως το μαγικό ραβδί το οποίο (με κάποιο τρόπο μαγικό) λύνει το θέμα, αλλάζει τους μηχανισμούς της συνάρτησης, κάνει επίκλιση στον Δία και δεν ξέρω γω τι άλλο. Κανείς δεν λέει όμως ότι ΠΑΝΤΑ ΜΑ ΠΑΝΤΑ μία συνάρτηση λειτουργεί BY VALUE!

 

 

Σε μία συνάρτηση έχεις ΠΑΝΤΑ call by value. Δηλαδή, η συνάρτηση θα κάνει ΤΟΠΙΚΟ αντίγραφο σε ΟΤΙΔΗΠΟΤΕ περάσεις ως όρισμα.

 

Έτσι, εάν περάσεις μία μεταβλητή int x τότε μέσα στην συνάρτηση θα έχεις μία ΝΕΑ μεταβλητή int x' που θα έχει την ΙΔΙΑ ΤΙΜΗ με αυτή της x. Εάν περάσεις μία μεταβλητή int* y τότε μέσα στην συνάρτηση θα έχεις μια ΝΕΑ μεταβλητή int* y' η οποία θα έχει ΤΗΝ ΙΔΙΑ ΤΙΜΗ με αυτή της y.

 

Στην περίπτωση του swap (π.χ.) δεν σε νοιάζει αυτό γιατί ΔΕΝ ΣΕ ΑΠΑΣΧΟΛΕΙ η μεταβλητή καθαυτή (π.χ. int* y) αλλά η τιμή της και το πού δείχνει. Άρα, σου αρκεί να πάρεις ένα αντίγραφο της y. Όταν όμως θέλεις να ΑΛΛΑΞΕΙΣ ΤΗΝ ΤΙΜΗ της y, τότε πρέπει να προσπεράσεις το θέμα με τα "τοπικά αντίγραφα". Άρα, πρέπει να περάσεις μία μεταβλητή για την οποία δεν θα σε νοιάζει η μεταβλητή καθαυτή αλλά η τιμή της. Π.χ., int** z = &y.

 

Έτσι, στην δική σου περίπτωση αυτό που κάνεις ΛΕΙΤΟΥΡΓΕΙ αλλά ΜΟΝΟ ΓΙΑ ΤΟ SCOPE της συνάρτησης. Μπορείς να το τσεκάρεις στον debugger σου. Θα δεις ότι η τιμή του head σετάρετε σωστά ΜΕΣΑ στην συνάρτηση. Μόλις βγεις απέξω, τότε όχι. Βασικά, εάν ψάξεις τον debugger θα δεις ότι το head μέσα στην συνάρτηση είναι ΜΙΑ ΔΙΑΦΟΡΕΤΙΚΗ ΜΕΤΑΒΛΗΤΗ (check memory location) από το head απέξω από την συνάρτηση. Π.χ., το head απόξω από την συνάρτηση θα είναι στην μνήμη στην διεύθυνση 0x000A ενώ το head μέσα στην συνάρτηση στην διεύθυνση 0x000B.

[moukoublen]

Εγώ από την άλλη θα προσπαθήσω να σου δώσω ένα παράδειγμα.
 

void changeInteger(int a){
    a = 10;
}

Το παραπάνω ξέρουμε οτι δεν αλλάζει τον ίδιο τον integer που του δίνεις σωστά;


 

void changePointerToInteger(int* a){
    a = mia_alli_diefthinsi_mnimis;
}

Τότε αυτό γιατί να λειτουργεί; Ούτε αυτό αλλάζει τον ίδιο τον pointer που του δίνεις.

[imitheos]

Καταλαβαίνεις ήδη πως αν θέλεις να περάσεις οτιδήποτε σε μια function στην οποία αυτό το οτιδήποτε θα υποστεί αλλαγεί, και θέλεις αυτή η αλλαγή να είναι ορατή όταν η function επιστρέψει, θα πρέπει αντί για something_t να περάσεις something_t*. Αυτό είναι νόμος.

 

Αν θες να περάσεις λοιπόν ένα node και να του κάνεις αλλαγές, θα πρέπει να περάσεις node*. Αν θέλεις να περάσεις node* και να του κάνεις αλλαγές, θα πρέπει να περάσεις node**. Αν θες να περάσεις node**, κλπ κλπ.

Έτσι, εάν περάσεις μία μεταβλητή int x τότε μέσα στην συνάρτηση θα έχεις μία ΝΕΑ μεταβλητή int x' που θα έχει την ΙΔΙΑ ΤΙΜΗ με αυτή της x. Εάν περάσεις μία μεταβλητή int* y τότε μέσα στην συνάρτηση θα έχεις μια ΝΕΑ μεταβλητή int* y' η οποία θα έχει ΤΗΝ ΙΔΙΑ ΤΙΜΗ με αυτή της y.

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

 

 

void Push(long head, int data)
{
	head = 6;  //NO this is wrong.
}		

Θα περίμενες να έχει η μεταβλητή head με τύπο long την τιμή 6 εκτός της συνάρτησης ? Όχι. Γιατί λοιπόν περιμένεις να γίνει για τον τύπο "struct node*" ?

 

Όταν θέλεις να αλλάξεις την τιμή μιας μεταβλητής τύπου int μέσα σε μια συνάρτηση, τότε περνάς σαν όρισμα "int *" ή αλλάζεις την συνάρτηση ώστε να επιστρέφει int. Έτσι και στην περίπτωσή σου, θα πρέπει είτε να περάσεις σαν όρισμα "struct node **" ή να αλλάξεις την συνάρτηση ώστε να επιστρέφει "struct node *".

[DDevil]

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

 
struct *node Push(struct node* head, int data)
{
    struct node* newNode = malloc(sizeof(struct node));
    newNode->data = data;
    newNode->next = head;
    head = newNode; 
 
    return head;
}    

 
int main(void) {
 
  struct node * list;
 
  printf(" Int Data? ");
  scanf("%d" , &data);
 
  list = Push( list , data);
 
  // ....
 
 return 0;
}

Bάλε μια void print( struct node * list ) με ένα for( ; list; list = list->next) printf("%d\n" , list->data); να δεις και τις εκτυπώσεις. Απλα θα στα εκτυπώσει με αντιστροφη σειρά επειδη η εισαγωγή γινεται κάθε φορά στην αρχή της λιστας.

Αυτό που συμβαίνει, είναι λόγω της παρανόησης του call by reference και call by value. Συνήθως (βασικά, πάντα βάσει των δικών μου παραδειγμάτων), το μαθαίνουν το call by reference ως το μαγικό ραβδί το οποίο (με κάποιο τρόπο μαγικό) λύνει το θέμα, αλλάζει τους μηχανισμούς της συνάρτησης, κάνει επίκλιση στον Δία και δεν ξέρω γω τι άλλο. Κανείς δεν λέει όμως ότι ΠΑΝΤΑ ΜΑ ΠΑΝΤΑ μία συνάρτηση λειτουργεί BY VALUE!

 

 

Ποιος κανεις δεν το λέει? το έχουμε γράψει σε προηγουμενο θρέντ. Επισης η επίκληση γράφεται με 'η'.

[gon1332]

Ποιος κανεις δεν το λέει? το έχουμε γράψει σε προηγουμενο θρέντ. Επισης η επίκληση γράφεται με 'η'.

Έχει δίκιο ο groot. Η πλειοψηφία* των φοιτητών νομίζει πως η C υποστηρίζει call-by-reference.

 

*Δεν έχω γνωρίσει κάποιον που να το ξέρει μέχρι στιγμής.

[groot]

Προφανώς και δεν πήρε χαμπάρι τι έγραψα.... Ο Δίας τον πείραξε κατά τα άλλα

[bnvdarklord]

Έχει δίκιο ο groot. Η πλειοψηφία* των φοιτητών νομίζει πως η C υποστηρίζει call-by-reference.

 

*Δεν έχω γνωρίσει κάποιον που να το ξέρει μέχρι στιγμής.

Ξέρεις αν υπάρχει γλώσσα που να έχει πραγματικό call-by-reference και δεν κάνει ουσιαστικά το ίδιο με την C, έστω και κρυφα (πχ Java);

[DDevil]

Προφανώς και δεν πήρε χαμπάρι τι έγραψα.... Ο Δίας τον πείραξε κατά τα άλλα

 

 

Ναι συγχαρητήρια ανακάλυψες την Αμερική και αποψε.

 

Απο τα πρώτα πραγματα που μαθαινει κάποιος οταν συναντά τις συναρτησεις ειναι οτι στις παραμετρους περνάνε τα αντιγραφα και οχι οι πραγματικές μεταβλητές.

[Kercyn]

Ξέρεις αν υπάρχει γλώσσα που να έχει πραγματικό call-by-reference και δεν κάνει ουσιαστικά το ίδιο με την C, έστω και κρυφα (πχ Java);

 

Τι εννοείς "δεν κάνει το ίδιο με τη C";

 

Πάντως σε C# στο Unity, τα μόνα που περνάνε by value είναι τα structs και τα primitives, όλα τα υπόλοιπα είναι by reference. Σε .ΝΕΤ δεν ξέρω ακριβώς τι γίνεται οπότε μη σε πάρω στο λαιμό μου. Η C++ επίσης επιτρέπει pass by reference.

[groot]

Ναι συγχαρητήρια ανακάλυψες την Αμερική και αποψε.

 

Απο τα πρώτα πραγματα που μαθαινει κάποιος οταν συναντά τις συναρτησεις ειναι οτι στις παραμετρους περνάνε τα αντιγραφα και οχι οι πραγματικές μεταβλητές.

Έχει δίκιο ο groot. Η πλειοψηφία* των φοιτητών νομίζει πως η C υποστηρίζει call-by-reference.

 

*Δεν έχω γνωρίσει κάποιον που να το ξέρει μέχρι στιγμής.

Κατάλαβες gon?

 

 

Μερικοί δεν μπορούν να το αντιληφθούν καν, ακόμα και εάν το δουν γραμμένο!!!

 

 

 

 

Ξέρεις αν υπάρχει γλώσσα που να έχει πραγματικό call-by-reference και δεν κάνει ουσιαστικά το ίδιο με την C, έστω και κρυφα (πχ Java);

Όχι. Ό,τι και εάν σκεφτώ, πάντα "by value" είναι.

[defacer]

Ξέρεις αν υπάρχει γλώσσα που να έχει πραγματικό call-by-reference και δεν κάνει ουσιαστικά το ίδιο με την C, έστω και κρυφα (πχ Java);

 

Υποθέτω πως σε μια natively compiled γλώσσα όπως η C++ θα μπορούσε να συμβεί να έχεις κάποια τιμή κρατημένη σε CPU register (είτε επίτηδες είτε λόγω compiler optimization) η οποία να περνιέται σε κάποια κλήση by reference. Σ' αυτή την περίπτωση θεωρητικά θα μπορούσε ο compiler να καταλάβει πως δε χρειάζεται να "περάσει" απολύτως τίποτα αν δε χρειάζεται να πειράξει την τιμή του register για άλλους λόγους. Απλά συνεχίζει και μετά το call να πασπατεύει το ίδιο register όπως πριν.

 

Αλλά η ερώτηση δεν είναι και πολύ καλά διατυπωμένη επειδή το ref είναι αφηρημένη έννοια και δεν αντιστοιχεί σε κάτι χειροπιαστό, οπότε η έκφραση "πραγματικό ref" είναι οξύμωρο.

[groot]

Ερώτηση...

 

επειδή ό,τι γράφω σε bash είναι πάντα "on the fly" (a.k.a. so programming), εκεί τι παίζει σε σχέση με το παρόν θέμα; Έχει κανείς εμπειρία για να απαντήσει;