Κώδικας C για ταξινόμηση απλά συνδεδεμένης λίστας με αλλαγή των pointers

[nikolaos_]

Το θέμα θα ήταν υπεραρκετό με τον τίτλο του για να καταλάβετε τι ζητάει, αλλά βάζω λίγα λόγια:

 

Ζητώ κώδικα. Ό,τι κώδικα έχω βρει, είναι είτε σε arrays, είτε κάνοντας αλλαγή των τιμών. Επειδή έχω πολύπλοκα nodes, αυτό δε μπορώ να το εφαρμόσω, πρέπει να ανταλλάξω με ασφάλεια τους pointers.

 

Η λίστα είναι απλά συνδεδεμένη. Δηλαδή υπάρχει μόνο ένας pointer *next, όχι *previous ή άλλα σχετικά.

 

Επιπλέον: Υπάρχει στο πρόγραμμά μου εκτός από μια μεγάλη απλά συνδεδεμένη λίστα και μια μικρή που χρειάζεται ταξινόμηση. Η μεγάλη μπορεί να αποκτήσει και 10000 στοιχεία, ενώ η μικρή ποτέ δε ξεπερνά τα 4 nodes. Υπάρχει κάτι που να ταξινομεί στο τσάκα-τσάκα μια λιστούλα 4 nodes χωρίς να βάζω άλλους 3 pointers για αυτό το σκοπό;

[kagelos]

Δοκίμασε κάτι απλό ως εξής :

Παίρνεις το πρώτο node και το προχωράς μπροστά όσο είναι π.χ. μεγαλύτερο από τα άλλα nodes. Μετά πας στο δεύτερο κοκ.

 

Έστω μη ταξινομημένη :

D->C->A->B

 

Ξεκινάς με την αρχή της λίστας και όσο το next δεν είναι null και το node είναι μεγαλύτερο από το επόμενο κάνεις :

Current->next = Next->next

Next->next = Current

Άρα η αρχή τώρα είναι το C και η λίστα :

C->D->A->B

 

Συνεχίζεις με το D εώς ότου δεν πάει πιο μπροστά και καταλήγεις :

 

C->A->B->D

 

Μόλις τελειώσεις με το τρέχων node πας πάλι στο πρώτο και ξανά το ίδιο. Σταματάς όταν το τρέχων είναι ακόμα πρώτο.

[V.I.Smirnov]

H ταξινόμηση λιστών είναι πιο εξεζητημένη από τους πίνακες και δεν συναντάται συχνά.

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

Για μικρές λίστες (με λιγότερο από 9 στοιχεία) χρησιμοποιείται σχεδόν πάντα insertion sort.

Για μεγαλύτερες εφαρμόζεται quick sort και βοηθητικά insertion sort.

Tα υπόλοιπα είναι ημίμετρα.

 

Έχω διαβάσει το ζήτημα αυτό πριν αρκετά χρόνια από το βιβλίο των Rex & Binstock.

Κάπως παλιό αλλά δίνουν πλήρη κώδικα όπου κάνουν τα παραπάνω (σε απλά συνδεδεμένη λίστα).

Για μικρή λίστα (<9 στοιχεία) γράφουν ξεκάθαρα ότι εφαρμόζεται Insertion sort.

Μάλιστα αν θυμάμαι καλά κάνουν και μια μικρή τροποποίηση ώστε ο συνολικός αλγόριθμος να είναι και ευσταθής για πολλαπλά κλειδιά.

 

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

 

-

[nikolaos_]

Καλές ιδέες δείχνουν και οι δυο, να 'στε καλά.

Αυτό περί insertion sort για στοιχεία <9 με απασχολεί πολύ.

Θα το ψάξω.

[thanos713]

Για ποιο λόγο να ταξινομήσεις λίστα;

[nikolaos_]

Για ποιο λόγο να ταξινομήσεις λίστα;

 

Είναι μεγάλα (σε μνήμη) nodes που συνδέονται μόνο με pointers μεταξύ τους οπότε η ταξινόμηση θα με εξυπηρετήσει στην αναζήτηση στοιχείων.

[thanos713]

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

[V.I.Smirnov]

@thanos

 

Tα δέντρα έχουν καλές ιδιότητες όταν είναι ισορροpημένα (balanced) αλλιώς εκφυλλίζονται σε λίστες και η αυξημένη

πολυπλοκότητα που απαιτούν επιβαρύνει το πρόγραμμα δίχως αντίκρυσμα.

 

Όμως η δημιουργία και ο χειρισμός ενός τέτοιου δέντρου (προσθήκη & διαγραφή κόμβων) είναι πολύ πιο δύσκολα από τις λίστες.

Π.χ. σε ένα ballanced tree όπως τα AVL το να διαγράψεις έναν κόμβο είναι περίπλοκο πρόβλημα (όσοι το έχουν δοκιμάσει ξέρουν καλά τι εννοώ).

Σε αρκετές περιπτώσεις το πρόβλημα της σωστής διαγραφής είναι τόσο μπελάς που ο κόμβος απλώς "σημαδεύεται" ως διεγραμμένος και

δεν χρησιμοποιοείται αλλά παραμένει στην θέση του.

Αντίθετα στις λίστες γίνεται αμέσως.

 

Εξάλλου το παιδί δουλεύει στην C κι' όχι στην C++ οπότε δεν μπορεί να χρησιμοποιήσει έτοιμα πράγματα σε σχετικά θέματα από την STL.

Aυτός είναι ο λόγος που εγώ δεν ασχολήθηκα ποτέ με C αλλά μόνον με C++ : υπάρχουν πολύ περισσότερες ευκολίες και υλικό.

Π.χ. αν θυμάμαι καλά τα map που έχει η STL είναι στην πραγματικότητα red-black trees...

 

-

[thanos713]

Αυτό που λες είναι μόνο στην διαγραφή, άμα θες να κάνεις αναζήτηση πού θα είναι πιο γρήγορη; Άμα κάνεις στην λίστα (άμα είναι ταξινομημένη) binary search, O(log N), είναι ακριβώς το ίδιο όπως και στο δυαδικό δέντρο, άμα έχεις μια λίστα 100.000 δεδομένων και θες να είναι ταξινομημένη τι κάνεις; Μόνο τον σταυρό σου μπορείς, ενώ στο δυαδικό δέντρο από το add του node είναι ήδη ταξινομημένο...

[npapak]

Δεν θα ηταν λιγο πιο ευκολο να κανεις ταξινομημενη εισαγωγη των στοιχείων?

Συνηθως ειναι πιο ευκολο απο το να αλλαζεις θεση στα στοιχεια της λιστας.

[V.I.Smirnov]

Αυτό που λες είναι μόνο στην διαγραφή, άμα θες να κάνεις αναζήτηση πού θα είναι πιο γρήγορη;

Άμα κάνεις στην λίστα (άμα είναι ταξινομημένη) binary search, O(log N), είναι ακριβώς το ίδιο όπως και στο δυαδικό δέντρο,

άμα έχεις μια λίστα 100.000 δεδομένων και θες να είναι ταξινομημένη τι κάνεις;

Μόνο τον σταυρό σου μπορείς, ενώ στο δυαδικό δέντρο από το add του node είναι ήδη ταξινομημένο...

 

Μάλλον δεν κατάλαβες τι έγραψα.

Δεν διαφωνώ σε αυτό που λες. Το θέμα είναι να φτιάξεις τη ρουτίνα που στήνει το δέντρο (ballanced tree).

Και αυτό είναι πολύ πιο δύσκολο να γίνει σωστά με δέντρα και γι' αυτό το αποφεύγουν αν δεν είναι ανάγκη.

Αυτό είπα.

 

 

Εξάλλου, αν τα δεδομένα τίθενται στην λίστα ενώ διαβάζονται από αρχείο, δεν μπορούν να είναι εξαρχής ταξινομημένα.

[thanos713]

Μάλλον δεν κατάλαβες τι έγραψα.

Δεν διαφωνώ σε αυτό που λες. Το θέμα είναι να φτιάξεις τη ρουτίνα που στήνει το δέντρο (ballanced tree).

Και αυτό είναι πολύ πιο δύσκολο να γίνει σωστά με δέντρα και γι' αυτό το αποφεύγουν αν δεν είναι ανάγκη.

Ναι μάλλον δεν κατάλαβα και συνεχίζω να μην καταλαβαίνω... Με την ρουτίνα που στήνει το δέντρο τι εννοείς;

[V.I.Smirnov]

Ναι μάλλον δεν κατάλαβα και συνεχίζω να μην καταλαβαίνω... Με την ρουτίνα που στήνει το δέντρο τι εννοείς;

 

Tι δεν καταλαβαίνεις ;

 

Για να φτιάξεις μια λίστα πρέπει να γράψεις ρουτίνες που προσθέτουν/διαγράφουν κόμβους κλπ.

Για τα δέντρα το ίδιο αλλά είναι σημαντικά πιο δύσκολο.

Η ρουτίνα για προσθήκη και κυρίως για διαγραφή κόμβου από ένα ballanced tree είναι γενικά ΠΟΛΥ περίπλοκες - καμιά σχέση με τις λίστες.

Ευτυχώς η STL έχει έτοιμα red-black trees και μας βγάζει από τον μπελά να φτιάξουμε δικά μας...

 

-

[thanos713]

Tι δεν καταλαβαίνεις ;

 

Για να φτιάξεις μια λίστα πρέπει να γράψεις ρουτίνες που προσθέτουν/διαγράφουν κόμβους κλπ.

Σύμφωνοι.

Για τα δέντρα το ίδιο αλλά είναι σημαντικά πιο δύσκολο.

Η ρουτίνα για προσθήκη και κυρίως για διαγραφή κόμβου από ένα ballanced tree είναι γενικά ΠΟΛΥ περίπλοκες - καμιά σχέση με τις λίστες.

Συμφωνώ μόνο όμως στην διαγραφή, άμα θες να έχεις ταξινομημένη λίστα πρέπει σε κάθε add να ξανακάνεις ταξινόμηση, ενώ στο δέντρο είναι πιο εύκολο... Άμα τώρα θες να έχεις μια λίστα για να θυμάσαι με ποια σειρά έδωσε ο χρήστης τα δεδομένα είναι λογικό να γίνεται να το κάνεις μόνο με λίστα...

[V.I.Smirnov]

Σύμφωνοι.

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

 

Λάθος κάνεις.

Όχι μόνον η διαγραφή αλλά και η προσθήκη κόμβου σε ένα ballanced tree είναι σχεδόν το ίδιο δύσκολη, δυο σκαλιά πιο κάτω.

Λίγοι ξέρουν να τις κάνουν.

Εγώ προσωπικά ξέρω να τα κάνω αυτά για AVL trees.

Για red-black trees που είναι καλύτερα από τα AVL δεν δοκίμασα - τα AVL μου ήταν αρκετά.

 

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

Το δύσκολο είναι πώς να κάνεις σωστά την προσθήκη & διαγραφή....