Κεφάλαιο 10

• Συνδεδεμένη λίστα


  Ένα σύνολο κόμβων διατεταγμένων γραμμικά (ο ένας μετά τον άλλο). Κάθε κόμβος περιέχει εκτός από τα δεδομένα του και έναν δείκτη που δείχνει προς τον επόμενο κόμβο. Ο δείκτης του τελευταίου κόμβου δε δείχνει σε κάποιον κόμβο (δείκτης στο κενό).

  
• Προσπέλαση σε συνδεδεμένη λίστα


  1. Γνωρίζουμε τη διεύθυνση (θέση στη μνήμη) του πρώτου κόμβου της λίστας

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

  1. Ο δείκτης του κόμβου μετά τον οποίο θα γίνει η παρεμβολή, να δείχνει τον νέο κόμβο

  2. Ο δείκτης του νέου κόμβου, να δείχνει αυτό που έδειχνε ο προηγούμενος

  
• Διαγραφή κόμβου από συνδεδεμένη λίστα

  Ο δείκτης του προηγούμενου κόμβου αλλάζει τιμή και δείχνει στον επόμενο αυτού που διαγράφεται
• Διπλά συνδεδεμένη λίστα


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


  Λόγω της δυνατότητας αυξομείωσης του μεγέθους τους
• Υλοποίηση στοίβας με απλά συνδεδεμένη λίστα


  Οι κόμβοι (στοιχεία) εισέρχονται από την αρχή της λίστας και εξέρχονται πάλι από την αρχή της λίστας (LIFO)
• Πότε χρησιμοποιούμε λίστα ή πίνακα για υλοποίηση στοίβας

  Λίστα αν δεν γνωρίζουμε εκ των προτέρων τον μέγιστο αριθμό στοιχείων, πίνακας αν θέλουμε μια εύκολη και γρήγορη λύση
• Υλοποίηση ουράς με διπλά συνδεδεμένη λίστα


  Εισαγωγή κόμβου στο τέλος της λίστας, διαγραφή κόμβου στην αρχή της λίστας
• Διαφορές λιστών και πινάκων

  • Πίνακας: δομή τυχαίας προσπέλασης, σταθερό μέγεθος, στοιχεία σε συνεχόμενες θέσεις μνήμης
  • Λίστα: δομή ακολουθιακής προσπέλασης, δυναμικό μέγεθος, κόμβοι σε μη συνεχόμενες θέσεις μνήμης
• Πλεονεκτήματα λιστών


  • Δυναμικό μέγεθος
  • Ευκολία εισαγωγής και διαγραφής
  • Μη αναγκαιότητα δήλωσης μεγέθους
• Συνδεδεμένη λίστα


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


  • Δυναμικό μέγεθος
  • Ευκολία εισαγωγής και διαγραφής
  • Μη αναγκαιότητα δήλωσης μεγέθους
• Μειονεκτήματα λιστών


  • Δεν επιτρέπεται τυχαία πρόσβαση
  • Μεγαλύτερη επιβάρυνση μνήμης
• Βασικές πράξεις συνδεδεμένων λιστών

  • Εισαγωγή κόμβου
  • Διαγραφή κόμβου
  • Έλεγχος για κενή λίστα
  • Αναζήτηση κόμβου
  • Διάσχιση και προσπέλαση στοιχείων
• Δέντρο


  Δομή που αποτελείται από κόμβους και ακμές, με ένα ξεχωριστό κόμβο ως ρίζα και μοναδική διαδρομή από τη ρίζα σε κάθε κόμβο
• Φύλλα


  Κόμβοι χωρίς παιδιά
• Αδέλφια


  Κόμβοι με τον ίδιο γονέα
• Διατεταγμένα δέντρα


  Δέντρα με γραμμική σχέση μεταξύ των παιδιών κάθε κόμβου
• Τομείς που χρησιμοποιούνται τα δέντρα


  • Λειτουργικά συστήματα
  • Γραφικά
  • Βάσεις δεδομένων
  • Παιχνίδια
  • Τεχνητή νοημοσύνη
  • Δικτύωση
• Δέντρο παιχνιδιού


  Δέντρο που μοντελοποιεί τις πιθανές κινήσεις των παικτών σε ένα παιχνίδι
• Δέντρο απόφασης


  Δέντρο όπου κάθε κόμβος αντιπροσωπεύει ένα χαρακτηριστικό, κάθε ακμή μια απόφαση και κάθε φύλλο ένα αποτέλεσμα
• Παραδείγματα χρήσης δέντρων


  • το σύστημα αρχείων του υπολογιστή
  • το οικογενειακό δένδρο
  • δομή ενός οργανισμού
  • πίνακας περιεχομένων ενός βιβλίου
  • μέρη που απαρτίζουν την μηχανή ενός αυτοκινήτου
• Δένδρο του παιχνιδιού (game tree)


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


  Δένδρα στα οποία κάθε κόμβος αντιπροσωπεύει ένα χαρακτηριστικό (ιδιότητα), κάθε ακμή αντιπροσωπεύει μια απόφαση (κανόνα) και κάθε φύλλο αντιπροσωπεύει ένα αποτέλεσμα
• Παράδειγμα δένδρου απόφασης


  • Το πρόβλημα λήψης απόφασης για την καθαριότητα του φοιτητικού σπιτιού
• Χρήση δέντρων για υπολογισμό αριθμητικών εκφράσεων


  Στα φύλλα του δέντρου μπαίνουν οι τελεστέοι, ενώ στους εσωτερικούς κόμβους οι τελεστές
• Γιατί τα δέντρα θεωρούνται ισχυρές δομές

  • Είναι εύκολο να προσθέσετε, να αφαιρέσετε ή να αναζητήσετε ένα στοιχείο
  • Η δομή των δένδρων μεταφέρει πληροφορίες
• Δυαδικό δένδρο


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


  Ένα δυαδικό δένδρο, όπου για κάθε κόμβο u, όλοι οι κόμβοι του αριστερού υποδένδρου έχουν τιμές μικρότερες της τιμής του κόμβου u και όλοι οι κόμβοι του δεξιού υποδένδρου έχουν τιμές μεγαλύτερες (ή ίσες) της τιμής του κόμβου u
• Γράφος


  Μία δομή που αποτελείται από ένα σύνολο κόμβων (ή σημείων ή κορυφών) και ένα σύνολο γραμμών (ή ακμών ή τόξων) που ενώνουν μερικούς ή όλους τους κόμβους
• Ο γράφος αποτελεί την πιο γενική δομή δεδομένων, με την έννοια ότι όλες οι προηγούμενες δομές που παρουσιάστηκαν μπορούν να θεωρηθούν περιπτώσεις γράφων
• Τύποι γράφων


  • Κατευθυνόμενος γράφος (directed graph)
  • Μη κατευθυνόμενος γράφος (undirected graph)

  
• Παγκόσμιος Ιστός (WWW)


  Ένας τεράστιος γράφος, όπου μερικές φορές οι ακμές είναι μη κατευθυνόμενες (μπορούμε να προχωρήσουμε από μια ιστοσελίδα σε μια άλλη και το αντίστροφο) και άλλες φορές οι ακμές είναι κατευθυνόμενες (μπορούμε να πάμε μόνο από την ιστοσελίδα Α στην ιστοσελίδα Β, και ποτέ το αντίστροφο)
• Facebook


  Μη κατευθυνόμενος γράφος, επειδή η σχέση μεταξύ δύο χρηστών (κόμβων) είναι αμφίδρομη
• Twitter


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