συνδεδεμένες λίστες

[voulaji]

Για άλλη μια φορά ζητώ την βοήθεια από πιο έμπειρους προγραμματιστές.

Λοιπόν συγκεκριμένα, η άσκηση λέει τα εξής:

Διευκρινίζω ότι την λύση την έχω (σσ Η μορφή της λίστας c θα είναι η εξής: 9→7→4→3→2→1→NULL). Θέλω όμως να καταλάβω πώς προκύπτει.

 

Έστω δύο συνδεδεμένες λίστες που αποτελούνται από κόμβους του τύπου:

typedef struct node *link;

struct node {

int key;

link next;

};

 

Θεωρείστε επίσης ότι ο τελευταίος κόμβος κάθε λίστας έχει τιμή NULL στο πεδίο link.

Έστω η παρακάτω συνάρτηση

link merge(link a, link {

link c = NULL, t;

while(a != NULL || b != NULL) {

if ((b == NULL) || (a != NULL && a->key < b->key)) {

t = a->next; a->next = c; c = a; a = t;

}

else {

t = b->next; b->next = c; c = b; b = t;

}

}

return c;

}

 

Θεωρείστε ότι το link a δείχνει στον πρώτο κόμβο μιας συνδεδεμένης λίστας της οποίας οι κόμβοι έχουν τιμές κλειδιών 1→2→7→9→NULL και ότι το link b δείχνει στον πρώτο κόμβο μιας συνδεδεμένης λίστας της οποίας οι κόμβοι έχουν τιμές κλειδιών 3→4→NULL.

 

Ποια θα είναι τα περιεχόμενα (τιμές κλειδιών) της διασυνδεδεμένης λίστας που θα επιστραφεί μετά την ολοκλήρωση της εκτέλεσης της συνάρτησης merge(a, ;

[parsifal]

Δεν είναι θέμα εμπειρίας. Αν δεν πάρεις μολύβι να αρχίσεις να ζωγραφίζεις στο χαρτί το τί συμβαίνει, δεν πρόκειται να καταλάβεις εύκολα πώς προκύπτει:

 

 

Αρχική κατάσταση:

>a
|
V
1 -> 2 -> 7 -> 9 -> NULL

b
|
V
3 -> 4 -> NULL

c
|
V
NULL

t
|
V
?

 

 

Εκτελείται η:

>while(a != NULL || b != NULL)

Είναι αληθής η συνθήκη, άρα πάμε παρακάτω:

>if ((b == NULL) || (a != NULL && a->key < b->key))

Αληθής. 1 < 3. Άρα, εκτελείται η:

>t = a->next;

Αποτέλεσμα:

>a    t
|    |
V    V
1 -> 2 -> 7 -> 9 -> NULL

 

Εκτελείται η:

>a->next = c;

Αποτέλεσμα:

>a    c        t
|    |        |
V    V        V
1 -> NULL     2 -> 7 -> 9 -> NULL

 

Εκτελείται η:

>c = a;

Αποτέλεσμα:

>a             t
|             |
V             V
1 -> NULL     2 -> 7 -> 9 -> NULL
^
|
c

 

Εκτελείται η:

>a = t;

Αποτέλεσμα:

>              t
             |
             V
1 -> NULL     2 -> 7 -> 9 -> NULL
^             ^
|             |
c             a

 

 

Ξανααποτιμάται η συνθήκη της while, βγαίνει αληθής, άλλη μία επανάληψη του βρόχου κ.ο.κ. Συνέχισε στο ίδιο μοτίβο και θα το βγάλεις...