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

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

Ορισμός

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

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

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

Παράδειγμα (διαβάζει ακέραιους σε λίστα και τους τυπώνει με την ανάποδη σειρά):
#include <stdlib.h>
#include <stdio.h>

/* List of integers */
struct s_list {
	int val;		/* Integer value */
	struct s_list *next;
};

main()
{
	struct s_list *head, *p;
	int n;

	head = NULL;
	/* Read list elements */
	while (scanf("%d", &n) == 1) {
		p = (struct s_list *)malloc(sizeof(struct s_list));
		p->val = n;
		p->next = head;
		head = p;
	}

	printf("\nStarting output:\n");
	/* Print list elements */
	for (p = head; p; p = p->next)
		printf("%d\n", p->val);
}

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

Ορισμός του τύπου της συνδεδεμένης λίστας ακεραίων
typedef struct s_int_list *int_list;
Επιστρέφεται μια άδεια συνδεδεμένη λίστα
int_list list_new(void);
Επιστρέφεται μια συνδεδεμένη λίστα με το στοιχείο i στην αρχή της
int_list int_list_add(int_list l, int i);
Επιστρέφεται μια συνδεδεμένη λίστα με το στοιχείο i διαγραμμένο
int_list int_list_del(int_list l, int i);
Επιστρέφει αληθές αν κάποιο στοιχείο της λίστας έχει την τιμή i, αλλιώς ψευδές.
int int_list_search(int_list l, int i);
Καλεί τη συνάρτηση process για κάθε στοιχείο της λίστας
void int_list_traverse(int_list l, void (*process)(int i));
Επιστρέφεται αληθές αν η λίστα είναι κενή
int int_list_isempty(int_list l);
Διαγράφει όλα τα στοιχεία της λίστας l
void int_list_delete(int_list l);

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

Διακρίνουμε τις παρακάτω ειδικές μορφές συνδεδεμένων λιστών:
διπλά συνδεδεμένη λίστα (doubly linked list)
Κάθε στοιχείο της λίστας έχει δείκτες στο προηγούμενο και το επόμενο. Αυτή μπορεί να οριστεί με την παρακάτω δομή της C:
struct s_int_dlist {
	int	val;			/* Integer value */
	struct s_int_dlist *prev;	/* Previous element */
	struct s_int_dlist *next;	/* Next element */
};
Η εισαγωγή ενός στοιχείου np πριν από το στοιχείο της λίστας p γίνεται με τις παρακάτω εντολές:
	p->prev->next = np;
	np->next = p;
	np->prev = p->prev;
	p->prev = np;
κυκλικά συνδεδεμένη λίστα
Το τελευταίο στοιχείο της λίστας δείχνει ξανά το πρώτο. Η δομή αυτή ονομάζεται και δακτύλιος (ring). Η διάσχιση της δομής αυτής πρέπει να γίνει με προσοχή για να μην καταλήξει σε ατέρμoνο βρόχο:
	struct s_dlist *start, *p;

	p = start;
	if (p)
		do {
			/* Process list element */
			...
			p = p->next;
		} while (p != start);
κυκλικά διπλά συνδεδεμένη λίστα
Σύνθεση των παραπάνω.

Εφαρμογές

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

Ασκήσεις

Άσκηση 3

  1. Να υλοποιηθεί σε C ο αφηρημένος τύπος της συνδεδεμένης λίστας χαρακτήρων σύμφωνα με τις παρακάτω συναρτήσεις:
    Ορισμός του τύπου της συνδεδεμένης λίστας χαρακτήρων
    Επιστρέφεται μια άδεια συνδεδεμένη λίστα
    char_list char_list_new(void);
    Επιστρέφεται μια συνδεδεμένη λίστα με το στοιχείο c στην αρχή της
    char_list char_list_add(char_list l, char c);
    Καλεί τη συνάρτηση process για κάθε στοιχείο της λίστας
    void char_list_traverse(char_list l, void (*process)(char c));
    Επιστρέφεται αληθές αν η λίστα είναι κενή
    int char_list_isempty(char_list l);
    Διαγράφει όλα τα στοιχεία της λίστας l
    void char_list_delete(char_list l);
  2. Με βάση τον αφηρημένο αυτό τύπο να υλοποιηθεί πρόγραμμα το οποίο να διαβάζει μια σειρά χαρακτήρων μέχρι να συναντήσει μια τελεία και στη συνέχεια να τυπώνει τους χαρακτήρες αυτούς με την αντίστροφη σειρά.
      Παράδειγμα:
      L
      I
      V
      E
      .
      E
      V
      I
      L