Γενικό Λύκειο > Δομές δεδομένων

Απορια στις λιστες

(1/4) > >>

computerscience:
Στα μειονεκτηματα των λιστων αναφερει οτι οι λιστες εχουν μεγαλυτερη επιβαρυνση απο τους πινακες αφου οι κομβοι ειναι δυναμικα κατανεμημενοι...κτλ
Δεν ειναι λιγο οξυμωρο μιας κ μειονεκτηματα των πινακων ειναι οτι δεσμευουν μνημη.. το οτι οι λιστες εχουν δυναμικο μεγεθος ειναι ενα απο τα πλεονεκτηματα τους..

P.Tsiotakis:
Για κάθε κόμβο της λίστας απαιτούνται 2 θέσεις μνήμης για την απλά και 3 θέσεις για την διπλά συνδεδεμένη λίστα, σε σχέση με τον πίνακα που απαιτείται 1.
Είναι περισσότερες οι θέσεις μνήμης.

Στους πίνακες το μειονέκτημα "ενεργοποιείται" όταν αναγκάζεται ο προγραμματιστής να δεσμεύσει πολλές περισσότερες θέσεις μνήμης για να είναι καλυμμένος.
Π.χ. στο θέμα εξετάσεων του 2010 θα έπρεπε να δεσμεύσει κανά εκατομμύριο θέσεις μνήμης γιατί τόσοι είναι οι μαθητές σε όλη την Ελλάδα που δυνητικά θα λάβουν μέρος στους μαθητικούς αγώνες.

petrosp13:
Και οι πίνακες και οι λίστες δεσμεύουν μνήμη, αλλά σκέψου ότι ο πίνακας αποθηκεύει μόνο τα δεδομένα και η λίστα και τους δείκτες κάθε επόμενου κόμβου
Είτε στατικά, είτε δυναμικά, οι λίστες δεσμεύουν σχεδόν διπλάσια μνήμη από τον πίνακα
Κι αυτό για απλά συνδεδεμένη λίστα
Η διπλά συνδεδεμένη, απαιτεί σχεδόν τριπλάσια μνήμη

tdrivas:

--- Παράθεση από: computerscience στις 31 Ιαν 2020, 01:51:33 μμ ---Στα μειονεκτηματα των λιστων αναφερει οτι οι λιστες εχουν μεγαλυτερη επιβαρυνση απο τους πινακες αφου οι κομβοι ειναι δυναμικα κατανεμημενοι...κτλ
Δεν ειναι λιγο οξυμωρο μιας κ μειονεκτηματα των πινακων ειναι οτι δεσμευουν μνημη.. το οτι οι λιστες εχουν δυναμικο μεγεθος ειναι ενα απο τα πλεονεκτηματα τους..

--- Τέλος παράθεσης ---

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

Στην αντίπερα όχθη, στον πίνακα a priori είναι γνωστό αυτό, καθώς οι κόμβοι του είναι σε συνεχόμενες θέσεις μνήμης.

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

π.χ. εξετάζω οχήματα που παιρνούν τα διόδια σε μία ημέρα.

Βάζω πίνακα 500,000 θέσεων για να είμαι σίγουρος => 500,000 θέσεις
Αν τελικά περάσουν 20,000 με απλά συνδεδεμένη λίστα θα ήθελα => 20,000 χ 2 = 40,000 θέσεις

Ελπίζω να βοηθήσαμε

computerscience:
Ναι ευχαριστω πολυ ολους

Πλοήγηση

[0] Λίστα μηνυμάτων

[#] Επόμενη σελίδα

Μετάβαση στην πλήρη έκδοση