Παρουσίαση/Προβολή

ΑΝΑΠΤΥΞΗ ΕΦΑΡΜΟΓΩΝ ΣΕ ΠΡΟΓ. ΠΕΡΙΒΑΛΛΟΝ - ΛΙΣΤΕΣ - ΠΙΝΑΚΕΣ - Γοικ

(EL226183) - ΘΕΟΔΩΡΟΣ ΚΟΥΤΣΟΥΜΑΡΗΣ

Περιγραφή Μαθήματος

Επανάληψη και επικέντρωση στην έννοια Λιστών και διαφορών από τους Πίνακες

Πριν προχωρήσουμε πιό κάτω, ας δούμε την λύση των ασκήσεων του προηγούμενου μαθήματος:

ΛΥΣΕΙΣ ΤΩΝ ΑΣΚΗΣΕΩΝ ΤΟΥ ΠΡΟΗΓΟΫΜΕΝΟΥ ΜΑΘΗΜΑΤΟΣ

Aσκηση 1

Γραψε ‘Δώσε στοιχείο για να προστεθεί στην λίστα’

Διάβασε στοιχείο

top <- top+1

A[top] <- στοιχείο

αλλιώς

Γράψε υπερχείλειση στοίβας‘

τελος_αν

Aσκηση 2

ΠΡΟΓΡΑΜΜΑ πρωτο
ΜΕΤΑΒΛΗΤΕΣ
    ΑΚΕΡΑΙΕΣ: A[10], i, top! τον πίνακα Α θα χρησιμοποιήσω σαν Στοίβα (stack)
ΑΡΧΗ
    ΓΙΑ i ΑΠΟ 1 ΜΕΧΡΙ 10          ! Γεμίζω τον πίνακα
    ΔΙΑΒΑΣΕ A[i]
    ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
top <- 10 ! μπορώ και top <- i
    ΟΣΟ top > 0 ΕΠΑΝΑΛΑΒΕ   ! Απώθηση
     ΓΡΑΨΕ A[top]
     top <- top - 1
ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
ΤΕΛΟΣ_ΠΡΟΓΡΑΜΜΑΤΟΣ

ΕΚΤΕΛΕΣΗ

δεδομενα: 2,5,7,12,0,3,4,5,9,80

αποτέλεσμα : 80,9,5,4,3,0,12,7,5,2
Aσκηση 3

ΠΡΟΓΡΑΜΜΑ Δεύτερο
ΜΕΤΑΒΛΗΤΕΣ
    ΑΚΕΡΑΙΕΣ: A[10], front, rear! τον πίνακα Α θα χρησιμοποιήσω σαν ουρά (queue)
ΑΡΧΗ
    front <- 1
    rear <- 1            ! το πίσω μέρος της ουράς
ΟΣΟ rear <= 10 ΕΠΑΝΑΛΑΒΕ ! Γεμίζω τον πίνακα (queue)
     ΔΙΑΒΑΣΕ A[rear]
    rear <- rear + 1
ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
           ! εξαγωγή
ΟΣΟ front <= 10 ΕΠΑΝΑΛΑΒΕ              ! Απώθηση
     ΓΡΑΨΕ A[front]
     front <- front + 1
ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ

ΤΕΛΟΣ_ΠΡΟΓΡΑΜΜΑΤΟΣ

ΕΚΤΕΛΕΣΗ

δεδομενα: 2,4,6,8,10,12,14,16,18,20 (εισαγωγή)

αποτέλεσμα: 2,4,6,8,10,12,14,16,18,20 (εξαγωγή)

Mind stimulus

Φανταστήτε ότι δουλεύετε σε μία εταιρία και είστε προγραμματιστής/τρια. Σας έχει ανατεθεί να

βρείτε ποιοί συνταξιούχοι στην χώρα σας εισπράτουν πάνω από 1000 ευρώ το μήνα σύνταξη.

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

ονόματα τους σε έναν πίνακα. Πόσο μεγάλος πρέπει να είναι ο πίνακας για να τα χωρέσει;

Αυθαίρετα, ορίζετε έναν πίνακα (πχ άν είστε Ελληνας 800.000 θέσεις, άν είστε Αμερικάνος πιθανόν 30.000.000

θέσεις γιατί η Αμερική έχει πάνω από 220.000.000 κατοίκους) αρκετά μεγάλο για να μην πάθει το πρόγραμμα

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

Αυτό σημαίνει μεγάλη δέσμευση και σπατάλη χώρου μνήμης RAM.

Οι διαστάσεις τών πινάκων ορίζονται μία φορά στην αρχή του προγράμματος και δεν μπορούν να αλλάξουν κατα

την διάρκεια εκτέλεσης του προγράμματος. Για αυτό λέμε πως οι πίνακες ανήκουν στις Στατικές Δομές

Δεδομένων.

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

την διάρκεια της εκτέλεσης του προγράμματος;

Η λύση υπάρχει και είναι οι ΛΙΣΤΕΣ (lists or linked lists).

Η δομή αυτή ονομάζεται Δυναμική Δομη Δεδομένων διότι μπορεί να αυξομειώνει το μέγεθός της.

ΛΙΓΗ ΘΕΩΡΙΑ

Η λίστα αποτελείται από ένα σύνολο κόμβων (nodes) και μία κεφαλή. Η κεφαλή της λίστας

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

αυτή «δείχνει» πού είναι ο επόμενος κόμβος. Όταν η λίστα είναι άδεια είναι μόνον η κεφαλή χωρίς διεύθυνση

και αυτό συμβολίζεται με τον NIL ή NULL (ανάλογα την βιβλιογραφία).

Κάθε επιπλέον κόμβος αποτελείται από τουλάχιστον δύο μέρη: α) το τμήμα που περιέχει το

δεδομένο (data) που θέλουμε να αποθηκεύσουμε και β) τον δείκτη (pointer) που περιέχει την διεύθυνση

που δείχνει στον επόμενο κόμβο. Το τμήμα δείκτη του τελευταίου κόμβου περιέχει NIL.

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

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

λίστες (υπολίστες - sublists), ή επιπλέον δείκτη που να δείχνει τον προηγούμενο κόμβο double linked Lists,

αλλά αυτά θα τα συναντήσετε στις ανώτερες σπουδές σας

Ερώτηση SOS : ΒΑΣΙΚΕΣ ΠΡΑΞΕΙΣ ΛΙΣΤΩΝ

1) ΕΙΣΑΓΩΓΗ ΚΟΜΒΟΥ ΣΤΗΝ ΛΙΣΤΑ

2) ΔΙΑΓΡΑΦΗ ΚΟΜΒΟΥ ΑΠΟ ΤΗΝ ΛΙΣΤΑ

3) ΕΛΕΓΧΟΣ ΑΝ Η ΛΊΣΤΑ ΕΙΝΑΙ ΚΕΝΗ (ΕΙΔΙΚΗ ΣΥΝΑΡΤΗΣΗ)

4) ΑΝΑΖΗΤΗΣΗ ΣΥΓΚΕΚΡΙΜΕΝΟΥ ΚΟΜΒΟΥ

5) ΔΙΑΣΧΙΣΗ ΚΑΙ ΠΡΟΣΠΕΛΑΣΗ ΛΙΣΤΑΣ (για να δουμε τι περιέχει κάθε κόμβος και να το εκτυπώσουμε)

Ερώτηση SOS : Πλεονεκτήματα μειονεκτήματα

1) Δεν χρειάζεται να νοιαστούμε για το μέγεθός τους απλώς προσθέτουμε νεους κόμβους

με ειδικές εντολές ενώ στους πίνακες έχω υπερχείληση αν δεν έχω προϋπολογίσει το

σωστό του μέγεθος.

2) Μπορώ να προσθέσω ένα νέο κόμβο ανάμεσα σε δύο προϋπάρχοντες, αλλά στον πίνακα

δεν μπορώ να εισάγω κάποιο νέο δεδομένο ανάμεσα σε δύο κελιά. Πρέπει να το βάλω

σε ελεύθερο κελί του πίνακα και μετά να κάνω ταξινόμηση.

3) Οι προσπέλαση στις λίστες σε αντίθεση με τους πίνακες είναι πιό αργή διότι οι κομβοι δεν

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

να ακολουθούμε τις διευθύνσεις των δεικτών.

Ερώτηση SOS : Διαφορές ΛΙΣΤΩΝ και ΠΙΝΑΚΩΝ

1) Το μέγεθος μιάς λίστας μεταβάλλεται κατα την διάρκεια της εκτέλεσης του

προγράμματος ενώ του πίνακα όχι.

2) Οι φυσικές θέσεις στην μνήμη των στοιχείων των πινάκων είναι διαδοχικές

(η μία δίπλα στην άλλη), ενώ στις λίστες μπορεί να βρίσκονται μακριά του

ενός από από το άλλο.

3) Ένας πίνακας ιδίου μεγέθους με μια λίστα, καταλαμβάνει πάντα μικρότερο

χώρο στην μνήμη του Η/Υ. Αυτό είναι γιατί κάθε κόμβος μιας λίστας, εκτός

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

που δείχνει τον επόμενο κόμβο.

4) Η προσπέλαση στους κόμβους μιάς λίστας είναι πολύ αργή σε σχέση με την

προσπέλαση στα στοιχεία του πίνακα. Αυτό γίνεται γιατί στίς λίστες το

Λειτουργικό Σύστημα πρέπει να ακολουθεί τους δείκτες διευθύνσεων (pointers)

για να βρεί το επόμενο στοιχείο της λίστας (περισσότρες προσπελάσεις.

Τώρα πατήστε το κουμπάκι "ΑΣΚΗΣΕΙΣ"

στο πλαϊνο MENU

Ημερομηνία δημιουργίας

Τρίτη 31 Μαρτίου 2020

Σελίδα μαθήματος

Περίγραμμα

Δεν υπάρχει περίγραμμα