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

Διομήδης Σπινέλλης
Τμήμα Διοικητικής Επιστήμης και Τεχνολογίας
Οικονομικό Πανεπιστήμιο Αθηνών
dds@aueb.gr

Ορισμός

Υλοποίηση στη μνήμη

Υλοποίηση με πίνακα

Υλοποίηση σε Pascal

Παράδειγμα:
program list;

type
    intList = ^intListElem;

    intListElem = record
        val : integer;
        next : intList;
    end;


var
    theList, node : intList;

begin
    new(node);
    node^.val := 5;
    node^.next := nil;
    theList := node;

    new(node);
    node^.val := 12;
    node^.next := theList;
    theList := node
end.

Αφηρημένος τύπος

{ Ορισμός του τύπου της συνδεδεμένης λίστας }
type
    intList = ^intListElem;

    intListElem = record
        val : integer;
        next : intList;
    end;
{ Επιστρέφεται μια άδεια συνδεδεμένη λίστα }
function newIntList : intList;
{ Επιστρέφεται μια συνδεδεμένη λίστα με το στοιχείο i στην αρχή της }
function addIntList(l : intList; i : integer) : intList;
{ Επιστρέφεται μια συνδεδεμένη λίστα με το στοιχείο i διαγραμμένο }
function delIntList(l : intList; i : integer) : intList;
{ Επιστρέφεται ένας δείκτης στο στοιχείο της λίστας που έχει την τιμή i }
function searchIntList(l : intList; i : integer) : intList;
{ Επιστρέφεται αληθές αν η λίστα είναι κενή }
function isEmtyIntList(l : intList) : boolean;

Ειδικές μορφές λιστών

Διακρίνουμε τις παρακάτω ειδικές μορφές συνδεδεμένων λιστών:
διπλά συνδεδεμένη λίστα (doubly linked list)
Κάθε στοιχείο της λίστας έχει δείκτες στο προηγούμενο και το επόμενο.
κυκλικά συνδεδεμένη λίστα
Το τελευταίο στοιχείο της λίστας δείχνει ξανά το πρώτο. Η δομή αυτή ονομάζεται και δακτύλιος (ring).
κυκλικά διπλά συνδεδεμένη λίστα
Σύνθεση των παραπάνω.

Εφαρμογές

Βιβλιογραφία

Ασκήσεις

Άσκηση ADS04

  1. Να υλοποιηθεί σε Pascal ο αφηρημένος τύπος της συνδεδεμένης λίστας χαρακτήρων σύμφωνα με τις παρακάτω συναρτήσεις:
    { Ορισμός του τύπου της συνδεδεμένης λίστας }
    type
        charList = ...
    
    { Επιστρέφεται μια άδεια συνδεδεμένη λίστα }
    function newCharList : charList;
    { Επιστρέφεται μια συνδεδεμένη λίστα με το στοιχείο c στην αρχή της }
    function addCharList(l : charList; c : char) : charList;
    { Επιστρέφεται μια συνδεδεμένη λίστα με το πρώτο στοιχείο διαγραμμένο. Κατά την επιστροφή η μεταβλητή c περιέχει την τιμή του. }
    function delCharListHead(l : charList; var c : char) : charList;
    { Επιστρέφεται ένας δείκτης στο στοιχείο της λίστας που έχει την τιμή c }
    function searchCharList(l : charList; c : char) : charList;
    { Επιστρέφεται αληθές αν η λίστα είναι κενή }
    function isEmtyCharList(l : charList) : boolean;
  2. Με βάση τον αφηρημένο αυτό τύπο να υλοποιηθεί πρόγραμμα το οποίο να διαβάζει μια σειρά χαρακτήρων μέχρι να συναντήσει μια τελεία και στη συνέχεια να τυπώνει τους χαρακτήρες αυτούς με την αντίστροφη σειρά.
      Παράδειγμα:
      L
      I
      V
      E
      .
      E
      V
      I
      L
      
    Περισσότερες λεπτομέρειες για τις ασκήσεις