Δείκτες και δυναμικές δομές δεδομένων

Διάταξη των δεδομένων και του κώδικα στη μνήμη

• Στους υπολογιστές αρχιτεκτονικής von Neuman ο κώδικας του προγράμματος αποθηκεύεται μαζί με τα αντίστοιχα δεδομένα στην κεντρική μνήμη του υπολογιστή.
• Η μνήμη είναι συνήθως διατεταγμένη με τρόπο τέτοιο ώστε κάθε στοιχείο της να μπορεί να οριστεί μονοσήμαντα από ένα συγκεκριμένο αριθμό. Ο αριθμός αυτός καλείται διεύθυνση (address) του στοιχείου.
• Όλα τα στοιχεία ενός προγράμματος που καταλαμβάνουν χώρο στη μνήμη (μεταβλητές όλων των τύπων και συναρτήσεις) έχουν μια συγκεκριμένη διεύθυνση.
• Επιπλέον το λειτουργικό σύστημα μας επιτρέπει να ζητήσουμε να διατεθεί στο πρόγραμμά μας, κατά την ώρα της εκτέλεσής του, πρόσθετη μνήμη.
• Ο τύπος που μας επιτρέπει να ορίσουμε μεταβλητές που να περιέχουν διευθύνσεις μνήμης καλείται δείκτης (pointer).

Δήλωση δεικτών

• Ο ορισμός ενός δείκτη γίνεται με τη σύνταξη:

  	τύπος *
  

• Έτσι για παράδειγμα ο τύπος int * ορίζει έναν δείκτη σε ακέραιους.
• Το παρακάτω παράδειγμα δηλώνει μια μεταβλητή iptr που είναι δείκτης σε ακέραιους.
          int *iptr;
  

Ο τελεστής &

• Για να πάρει ένας δείκτης μια τιμή πρέπει να μπορέσουμε να βρούμε τη διεύθυνση της μνήμης ενός στοιχείου. Αυτό το επιτρέπει ο μοναδιαίος τελεστής &.
• Ο τελεστής & εφαρμοζόμενος σε ένα στοιχείο στο οποίο μπορεί να γίνει ανάθεση τιμής (π.χ. μεταβλητή) το μετατρέπει σε ένα δείκτη στο στοιχείο αυτό.
• Το παρακάτω παράδειγμα ορίζει ένα δείκτη σε ακέραιο (iptr) και θέτει την τιμή του στη διεύθυνση της μεταβλητής i.
          int *iptr;
          int i;
  
          iptr = &i;
  

Χρήση δεικτών

• Ο μοναδιαίος τελεστής * εφαρμοζόμενος σε ένα δείκτη μας επιτρέπει να αναθέσουμε μια τιμή αντίστοιχου τύπου στην τιμή που δείχνει ο δείκτης.
• Το παρακάτω παράδειγμα θέτει την τιμή της μεταβλητής i σε 5:
          int *iptr;
          int i;
  
          iptr = &i;
          *iptr = 5;
  

Κλήση κατ' αναφορά

• Με το συνδυασμό των τελεστών & και * μπορούμε να ορίσουμε συναρτήσεις που να αλλάζουν την τιμή μεταβλητών που περνάν σε αυτές ως δείκτες.
• Στο παρακάτω παράδειγμα η συνάρτηση int_swap αλλάζει μεταξύ τους τις τιμές των δύο δεικτών σε ακέραιους που είναι οι παράμετροί της. Το παρακάτω παράδειγμα τυπώνει 2, 1:
  void
  int_swap(int *i1, int *i2)
  {
          int tmp;
  
          tmp = *i1;
          *i1 = *i2;
          *i2 = tmp;
  }
  
  main()
  {
          int a, b;
  
          a = 1;
          b = 2;
          int_swap(&a, &b);
          printf("%d, %d\n", a, b);
  }
  
• Ο τρόπος αυτός κλήσης ονομάζεται κλήση κατ' αναφορά. Σε ορισμένες γλώσσες προγραμματισμού υποστηρίζεται κατευθείαν από τη γλώσσα χωρίς τη χρήση ειδικών τελεστών.

Αριθμητική με δείκτες

• Το όνομα ενός πίνακα είναι ουσιαστικά ένας δείκτης στο πρώτο στοιχείο του.
• Όταν προσθέτουμε ή αφαιρούμε από έναν δείκτη μια σταθερή τιμή, κάνουμε το δείκτη να δείχνει στο προηγούμενο ή στο επόμενο στοιχείο
• Με τον τρόπο αυτό μπορούμε να διασχίσουμε τα στοιχεία ενός πίνακα. Το παρακάτω παράδειγμα μηδενίζει όλα τα στοιχεία του πίνακα α:
          int a[10];
          int *iptr;
  
          for (iptr = a; iptr < &a[10]; iptr++)
                  *iptr = 0;
  
• Στην πραγματικότητα για έναν πίνακα a η έκφραση a[i] είναι συντομογραφία της έκφρασης *(a + i).

Ο τελεστής sizeof

• Ο τελεστής sizeof επιστρέφει το μέγεθος της μεταβλητής ή του τύπου στον οποίο εφαρμόζεται. Το μέγεθος αυτό εκφράζεται σε bytes.
• Παράδειγμα (τυπώνει 1, 2, 4, 4, 40, 1 σε υπολογιστές Pentium):
  main()
  {
          char c;
          short s;
          int i;
          double d;
          int a[10];
  
          printf("%d\n", sizeof(c));
          printf("%d\n", sizeof(s));
          printf("%d\n", sizeof(i));
          printf("%d\n", sizeof(d));
          printf("%d\n", sizeof(a));
          printf("%d\n", sizeof(char));
  }
  
• Με τη χρήση της sizeof μπορούμε να γράψουμε κώδικα ο οποίος να μην εξαρτάται από το μέγεθος ενός πίνακα ή ενός τύπου. Παράδειγμα (μηδενίζει τον πίνακα a):
          int a[10];
          int *iptr;
  
          for (iptr = a; iptr < a + sizeof(a) / sizeof(int); iptr++)
                  *iptr = 0;
  

Δυναμική διάθεση μνήμης

• Η συνάρτηση malloc() μας επιτρέπει να ζητήσουμε έναν ελεύθερο χώρο μνήμης για να χρησιμοποιήσουμε στο πρόγραμμά μας.
• Η malloc έχει ως όρισμα το μέγεθος της μνήμης που απαιτούμε και επιστρέφει ένα δείκτη στην αρχή του αντίστοιχου χώρου. Ο τύπος της τιμής που επιστρέφει δεν είναι αντίστοιχος με τον τύπο που χρειαζόμαστε και γι' αυτό πρέπει να χρησιμοποιήσουμε την αντίστοιχη μετατροπή (π.χ. (double *)malloc...).
• Σε περίπτωση που το σύστημα δεν έχει άλλη διαθέσιμη μνήμη η malloc επιστρέφει τη σταθερά NULL.
  Παράδειγμα:
          char *c;
  
          c = (char *)malloc(1000 * sizeof(char));
          if (c == NULL) {
                  printf("Out of memory!\n");
                  return (1);
          }
  
• Με τη χρήση της malloc μπορούμε να δημιουργήσουμε δυναμικά χώρο για πίνακες τους οποίους δηλώνουμε ως δείκτες.
• Το παρακάτω παράδειγμα ζητάει από το χρήστη να ορίσει το μέγεθος ενός πίνακα και στη συνέχεια να δώσει τα στοιχεία του.
  #include <stdlib.h>
  #include <stdio.h>
  
  main()
  {
          int *int_table;         /* Table of integers */
          int nelem;              /* Number of elements */
          int i;
  
          printf("Enter number of elements:");
          scanf("%d", &nelem);
          int_table = (int *)malloc(nelem * sizeof(int));
          for (i = 0; i < nelem; i++) {
                  printf("Element %d=", i);
                  scanf("%d", &int_table[i]);
          }
  }
  
• Η συνάρτηση free(δείκτης) ελευθερώνει το χώρο που έχει επιστραφεί από τη malloc για ανακύκλωση.
• Η συνάρτηση realloc(δείκτης, νέο μέγεθος) λαμβάνει ως όρισμα ένα δείκτη που έχει επιστραφεί από τη malloc και επιστρέφει έναν δείκτη σε χώρο με το νέο μέγεθος που έχει προσδιοριστεί.
  Παράδειγμα:
          int *iptr;
  
          iptr = (int *)malloc(10 * sizeof(int));
          /* iptr[0] to iptr[9] can now be used */
  
          iptr = (int *)realloc(iptr, 20 * sizeof(int));
          /* 
           * iptr[0] to iptr[9] retain old values
           * iptr[0] to iptr[19] can now be used */
           */
  
          free(iptr);
          /* Do not access iptr[0] to iptr[19] from this point onwards */
  
• Οι malloc, free, realloc, NULL ορίζονται στο αρχείο stdlib.h.

Φροντιστηριακές ασκήσεις

1. Συμπληρώστε τον πίνακα με τις τιμές των μεταβλητών μετά την εκτέλεση κάθε μιας από τις παρακάτω εντολές.
           int a, b, c;
           int *ip1, *ip2, *ip3;
   
           a = 3;
           b = 4;
           ip1 = &a;
           *ip1 = 8;
           ip3 = &c;
           ip2 = ip3;
           b = *ip1;
           *ip2 = *ip1;
   

   	a	b	c	ip1	ip2	ip3
   Αρχή	-	-	-	-	-	-
   a = 3	3	-	-	-	-	-
   b = 4	3	4	-	-	-	-
   ip1 = &a	3	4	-	&a	-	-
   *ip1 = 8
   ip3 = &c
   ip2 = ip3
   b = *ip1
   *ip2 = *ip1

2. Υπολογίστε τους τύπους των εκφράσεων δεξιά και αριστερά από κάθε ανάθεση και γράψτε ποιες από τις παρακάτω γραμμές είναι σωστές και ποιες όχι.
           int a, b, c, *p1, *p2, *p3;
           double da, db, dc, *pd1, *pd2, *pd3;
   
           p1 = &a;
           *p1 = 4;
           p2 = &p1;
           *p2 = *c;
           p3 = a;
           p2 = p3;
           pd1 = p2;
           pd2 = &da;
           dc = *pd3;
           db = *p2;
           &a = 43;
   

Ασκήσεις

Δυναμική χρήση της μνήμης

1. Να σχεδιάσετε και να γράψετε ένα πρόγραμμα το οποίο τυπώνει τους χαρακτήρες που διαβάζει με την ανάποδη σειρά. Δεν πρέπει να υπάρχει περιορισμός από το πρόγραμμα στον αριθμό των χαρακτήρων που να μπορεί να δεχτεί.
2. Το παρακάτω πρόγραμμα προσθέτει διανύσματα ν διαστάσεων:
   /*
    * Add two vectors
    *
    * Diomidis Spinellis, December 1998
    */
   
   #include <stdio.h>
   
   /*
    * Print the contents of vector v consisting of n elements
    */
   void
   vector_print(double v[], int n)
   {
           int i;
   
           putchar('(');
           for (i = 0; i < n; i++) {
                   printf("%g", v[i]);
                   if (i < n - 1)
                           printf(", ");
           }
           putchar(')');
   }
   
   
   /*
    * Input a vector v consisting of n elements
    */
   void
   vector_input(double v[], int n)
   {
           int i;
   
           for (i = 0; i < n; i++) {
                   printf("\tEnter element %d: ", i);
                   scanf("%lg", &v[i]);
           }
   }
   
   
   /*
    * Sum vector a and vector b to vector c
    * All vectors consist of n elements
    */
   void
   vector_add(double a[], double b[], double c[], int n)
   {
           int i;
   
           for (i = 0; i < n; i++)
                   c[i] = a[i] + b[i];
   }
   
   main()
   {
           int nelem;
           double a[10], b[10], c[10];
   
           printf("Enter number of vector elements: ");
           scanf("%d", &nelem);
           if (nelem > sizeof(a) / sizeof(double)) {
                   printf("Vector size too large.  The maximum vector size is %d.\n",
                           sizeof(a) / sizeof(double));
                   return (1);
           }
           printf("Enter vector a\n");
           vector_input(a, nelem);
           printf("Enter vector b\n");
           vector_input(b, nelem);
           vector_add(a, b, c, nelem);
           vector_print(a, nelem);
           putchar('+');
           vector_print(b, nelem);
           putchar('=');
           vector_print(c, nelem);
   }
   
   1. Να το μεταγλωττίσετε και να το δοκιμάσετε στη μορφή που είναι.
   2. Να το αλλάξετε έτσι ώστε να μην έχει περιορισμό ως προς το μέγεθος των διανυσμάτων που μπορεί να δεχτεί.
   3. Να το αλλάξετε έτσι ώστε να μην εμφανίζονται καθόλου σε αυτό οι χαρακτήρες [ και ] (χρησιμοποιήστε δείκτες αντί για πίνακες).

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

• Brian W. Kernighan, Dennis M. Ritchie Η γλώσσα προγραμματισμού C. σ. 135-178 (τμήματα) Δεύτερη έκδοση. Κλειδάριθμος, 1988.

• Brian W. Kernighan and Dennis M. Ritchie. The C Programming Language, pages 93-126 (parts). Prentice-Hall, second edition, 1988.

• Περιεχόμενα

 Τελευταία αλλαγή: Τρίτη, 29 Ιανουαρίου 2002 10:22 πμ
 Εκτός αν αναφέρεται κάτι διαφορετικό, όλο το πρωτότυπο υλικό της σελίδας αυτής του οποίου δημιουργός είναι ο Διομήδης Σπινέλλης παρέχεται σύμφωνα με τους όρους της άδειας «Creative Commons Attribution-Share Alike 3.0 Greece License».