Οδηγός Μελέτης - Εισαγωγή στον Προγραμματισμό

Διάλεξη 11 · 07/11/2025 · Διαφάνειες (PDF) · Σημειώσεις 5 · Σημειώσεις 4 · Εργαστήριο 6 · Εργαστήριο 5

Κεφάλαιο 11: Δείκτες και Αναδρομή

Στόχοι: μετά από αυτό το κεφάλαιο θα μπορείτε να εξηγείτε τι είναι η διεύθυνση μιας μεταβλητής και να τη βρίσκετε με τον τελεστή &· να δηλώνετε, να αρχικοποιείτε και να χρησιμοποιείτε δείκτες (*)· να ξέρετε πότε ένας δείκτης είναι NULL ή μη έγκυρος· να κάνετε αριθμητική δεικτών και να εξηγείτε γιατί το ptr[n] είναι το ίδιο με το *(ptr + n)· να γράφετε συναρτήσεις που δέχονται πίνακες· και να γράφετε μια απλή αναδρομική συνάρτηση με βάση τερματισμού.

Προαπαιτούμενα: Κεφάλαιο 2, Κεφάλαιο 3, Κεφάλαιο 10

Χρόνος μελέτης: ~3 ώρες

Σύνοψη

Η διάλεξη αυτή εισάγει έναν νέο τύπο, τον δείκτη (pointer): μια μεταβλητή που δεν κρατά έναν αριθμό ή έναν χαρακτήρα, αλλά τη διεύθυνση μιας άλλης μεταβλητής στη μνήμη. Ξεκινάμε από το πώς η μνήμη οργανώνεται σε bytes με διευθύνσεις, βλέπουμε πώς βρίσκουμε τη διεύθυνση μιας μεταβλητής με το & και πώς φτάνουμε από τη διεύθυνση πίσω στη μεταβλητή με το *. Έπειτα μαθαίνουμε τις πράξεις που επιτρέπονται σε δείκτες και ανακαλύπτουμε ότι η γνωστή μας σύνταξη a[i] των πινάκων είναι στην πραγματικότητα αριθμητική δεικτών. Με αυτά γράφουμε συναρτήσεις που δουλεύουν πάνω σε πίνακες (μέσος όρος, αναζήτηση, μια δική μας atoi). Η διάλεξη κλείνει με την αναδρομή (recursion), όπου μια συνάρτηση καλεί τον εαυτό της, με παράδειγμα το παραγοντικό. Οι δείκτες είναι το θεμέλιο για όλο το υπόλοιπο μάθημα: δυναμική μνήμη, συμβολοσειρές, λίστες και δέντρα.

Θεωρία

§11.1 Η μνήμη και οι διευθύνσεις

Όπως είδαμε στο Κεφάλαιο 2, η μνήμη του υπολογιστή είναι μια μεγάλη σειρά από bytes (1 KB = 1.000 bytes, 1 MB = 1.000.000 bytes, 1 GB = 1.000.000.000 bytes). Μια μνήμη με N bytes έχει τα bytes 0, 1, …, N−1. Η θέση ενός κελιού στη μνήμη λέγεται διεύθυνση (address): για παράδειγμα, «στη διεύθυνση 2 υπάρχει το byte 11100011 (δυαδικό)».

Μια μεταβλητή (variable) είναι ένα τμήμα της μνήμης με συγκεκριμένο όνομα, και για να χρησιμοποιηθεί πρέπει να έχει δηλωθεί με κάποιον τύπο (type). Στη δήλωση int x; ο τύπος λέει στον μεταγλωττιστή πόση μνήμη να δεσμεύσει (π.χ. 4 bytes για έναν int), και το όνομα τον κάνει να διαλέξει πού, δηλαδή σε ποια διεύθυνση, θα αποθηκευτεί η μεταβλητή.

Η ανάθεση (assignment) μπορεί να γίνει κατά τον ορισμό (int x = 42;), αργότερα (int x; και μετά x = 42;) ή με δεκαεξαδική σταθερά (int x = 0x2A;, το ίδιο 42). Πριν από την ανάθεση, τα bytes της x έχουν ό,τι «σκουπίδια» έτυχε να υπάρχουν εκεί· μετά, κρατούν την αναπαράσταση του 42 (00101010 στο δυαδικό).

§11.2 Ο τελεστής &: η διεύθυνση μιας μεταβλητής

Τη διεύθυνση μιας μεταβλητής τη βρίσκουμε με τον μοναδιαίο τελεστή & (ampersand). Αν η x τοποθετήθηκε στα bytes 100–103, τότε το &x είναι 100: η διεύθυνση του πρώτου byte της.

Διεύθυνση Περιεχόμενο
100 00000000
101 00000000
102 00000000
103 00101010

Η int x = 42; στα bytes 100–103, όπως τη σχεδιάζουν οι διαφάνειες.

Η διεύθυνση είναι πάντα ένας ακέραιος αριθμός, με όσα bits αποφασίσει ο μεταγλωττιστής: 32 σε συστήματα 32 bit (gcc -m32), 64 σε συστήματα 64 bit. Και οι διευθύνσεις μπορούν να αλλάζουν από εκτέλεση σε εκτέλεση: το 100 ισχύει για μία εκτέλεση του προγράμματος, όχι για πάντα.

Οι διαφάνειες σχεδιάζουν τον ακέραιο με το σημαντικό του μέρος στο πρώτο byte και την τιμή 42 στο τελευταίο. Η πραγματική σειρά των bytes εξαρτάται από τον επεξεργαστή (endianness) και τη βλέπουμε στο Κεφάλαιο 12.

§11.3 Ο τύπος δείκτη

Πέρα από τους βασικούς τύπους int, char, double, προσθέτουμε έναν νέο τύπο για να αποθηκεύουμε διευθύνσεις. Ένας δείκτης (pointer) είναι μια μεταβλητή που περιέχει τη διεύθυνση μνήμης ενός δεδομένου συγκεκριμένου τύπου. Η γενική μορφή της δήλωσης είναι:

τύπος * όνομα;      // π.χ.
int * pointer;

Ο τύπος τύπος * λέει στον μεταγλωττιστή ότι η διεύθυνση που θα αποθηκεύει ο δείκτης είναι για δεδομένα τύπου τύπος: ο int * δείχνει σε int, ο char * σε char. Το όνομα είναι, όπως πάντα, η μεταβλητή που κρατά την τιμή του δείκτη, και ο μεταγλωττιστής επιλέγει πού θα αποθηκευτεί. Τα κενά γύρω από το * δεν έχουν σημασία: int *p, int * p και int* p είναι το ίδιο. Σε δήλωση πολλών μεταβλητών όμως το * ανήκει στο όνομα: int *pa = &a, *pb = &b; δηλώνει δύο δείκτες.

§11.4 Αρχικοποίηση ενός δείκτη

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

int x = 42;
int *pointer = &x;

Τώρα λέμε ότι ο pointer δείχνει (points to) στη μεταβλητή x. Ο ίδιος ο δείκτης είναι μια μεταβλητή με δική της θέση στη μνήμη. Αν η x είναι στη διεύθυνση 100 και ο pointer στη 200, τότε το περιεχόμενο του pointer είναι 100 και το &pointer είναι 200· το printf("%d, %d\n", pointer, &pointer); των διαφανειών τυπώνει 100, 200 (το σωστό format για διευθύνσεις είναι το %p, βλ. παρακάτω):

flowchart LR
  P["pointer @ 200: 100"] --> X["x @ 100: 42"]

Σχήμα: ο δείκτης (στη διεύθυνση 200) κρατά την τιμή 100, τη διεύθυνση της x.

Το ίδιο γίνεται με κάθε τύπο: με char c = 42; char *pointer = &c; και τη c στη διεύθυνση 150, ο pointer περιέχει 150. Η διαφορά είναι ότι ο char πιάνει 1 byte, ενώ ο int 4.

§11.5 Ο τελεστής sizeof

Ο τελεστής sizeof υπολογίζει πόσα bytes πιάνει στη μνήμη ένας τύπος ή μια μεταβλητή. Το αποτέλεσμα έχει τύπο size_t και το σωστό format για την printf είναι το %zu (το %d συνήθως «δουλεύει», αλλά ο gcc -Wall προειδοποιεί):

printf("int size: %zu\n", sizeof(int));   // int size: 4

Πόσο μεγάλος είναι ένας δείκτης; Όσο μια διεύθυνση, ανεξάρτητα από τον τύπο στον οποίο δείχνει. Σε σύστημα 64 bit οι int *, char * και double * πιάνουν όλοι 8 bytes (σε 32 bit, 4). Ο τύπος του δείκτη δεν αλλάζει το μέγεθός του, αλλάζει το πώς ερμηνεύεται η μνήμη όπου δείχνει.

§11.6 Η ειδική τιμή NULL

Όταν θέλουμε να δηλώσουμε ότι ένας δείκτης δεν δείχνει σε κάποια μεταβλητή, του αναθέτουμε την τιμή NULL (τη διεύθυνση 0), και μπορούμε να την ελέγξουμε:

int * ipointer = NULL;
if (ipointer == NULL) {
  printf("pointer does not point anywhere\n");
}

Δεν υπάρχει περίπτωση να βρίσκεται μια μεταβλητή στη διεύθυνση 0; Θεωρητικά ναι, πρακτικά όχι: τα συστήματα κρατούν αυτή τη διεύθυνση εκτός χρήσης ακριβώς για να σημαίνει «πουθενά». Ο Tony Hoare, που εισήγαγε τις null αναφορές, την ονόμασε «the billion dollar mistake», γιατί η χρήση ενός NULL δείκτη σαν να ήταν έγκυρος είναι μία από τις πιο συχνές αιτίες σφαλμάτων.

§11.7 Αποαναφορά: ο τελεστής *

Ο δείκτης δείχνει σε μια μεταβλητή· μπορούμε να φτάσουμε στη μεταβλητή έχοντας μόνο τη διεύθυνσή της; Ναι: με τον μοναδιαίο τελεστή *, που λέγεται αποαναφορά (dereference). Το *pointer είναι η μεταβλητή στην οποία δείχνει ο pointer:

int x = 42;
int *pointer = &x;
printf("%d\n", *pointer);   // 42

Η χρήση του *pointer είναι ισοδύναμη με τη χρήση της μεταβλητής x, και για διάβασμα και για γράψιμο: το *pointer = 7; αλλάζει την x. Προσέξτε ότι το * έχει δύο ρόλους: στη δήλωση (int *p) λέει «ο p είναι δείκτης», ενώ σε μια έκφραση (*p) λέει «πήγαινε εκεί που δείχνει ο p».

§11.8 Μη έγκυροι δείκτες

Για να χρησιμοποιήσουμε το περιεχόμενο της διεύθυνσης όπου δείχνει ένας δείκτης, η διεύθυνση πρέπει πρώτα να υπάρχει:

int *pointer;
printf("%d\n", *pointer);   // μη αρχικοποιημένος δείκτης!

Αυτό κατά πάσα πιθανότητα θα τερματίσει με segmentation fault: ο pointer δεν αρχικοποιήθηκε, άρα περιέχει μια τυχαία τιμή που δεν είναι έγκυρη διεύθυνση μνήμης. Το ίδιο συμβαίνει με αποαναφορά ενός NULL δείκτη. Κανόνας: κάθε δείκτης είτε δείχνει σε κάτι έγκυρο, είτε είναι NULL και ελέγχεται πριν χρησιμοποιηθεί.

§11.9 Οι τελεστές * και & είναι συμπληρωματικοί

Ο * δίνει τη μεταβλητή σε μια διεύθυνση, ο & τη διεύθυνση μιας μεταβλητής. Είναι λοιπόν αντίστροφοι: όταν εφαρμόζονται σε έγκυρους δείκτες αλληλοαναιρούνται. Με int x = 42; int *pointer = &x; τα pointer, &*pointer και *&pointer έχουν όλα την ίδια τιμή. Για να τυπώσουμε μια διεύθυνση χρησιμοποιούμε το format %p, που τη δείχνει στο δεκαεξαδικό:

$ ./pointer_size
0x7ffcf94870cc 0x7ffcf94870cc 0x7ffcf94870cc

§11.10 Πράξεις με δείκτες

Σε δείκτες επιτρέπονται μόνο οι εξής πράξεις:

Το κρίσιμο σημείο είναι η πρόσθεση. Η πρόσθεση ενός ακεραίου αυξάνει τη διεύθυνση κατά το μέγεθος του τύπου όπου δείχνει ο δείκτης, πολλαπλασιασμένο με τον ακέραιο. Για τύπος *pointer; το pointer += N μεταφέρει τη διεύθυνση κατά N * sizeof(τύπος) bytes:

int *ipointer;    ipointer += 2;   // + 2 * sizeof(int)    = 8 bytes
char *cpointer;   cpointer += 2;   // + 2 * sizeof(char)   = 2 bytes
double *dpointer; dpointer += 2;   // + 2 * sizeof(double) = 16 bytes

Δηλαδή ο δείκτης μετακινείται κατά N στοιχεία, όχι κατά N bytes. Έτσι, αν ο int *pointer δείχνει στη 100, το ++pointer τον κάνει 104· αν ο char *pointer δείχνει στη 150, το --pointer τον κάνει 149. Η αφαίρεση δύο δεικτών δίνει αντίστοιχα πόσα στοιχεία απέχουν, και έχει νόημα, όπως και η σύγκρισή τους, μόνο όταν δείχνουν στο ίδιο μπλοκ μνήμης, π.χ. στον ίδιο πίνακα (σημειώσεις, «Δείκτες»).

Γιατί να μετακινήσουμε έναν δείκτη; Η μνήμη δίπλα σε μια απλή μεταβλητή δεν μας ανήκει. Έχει νόημα όταν ο δείκτης δείχνει μέσα σε συνεχόμενες θέσεις ίδιου τύπου, δηλαδή σε έναν πίνακα.

§11.11 Δείκτες και πίνακες: *(ptr + n) και ptr[n]

Τα στοιχεία ενός πίνακα είναι σε συνεχόμενες θέσεις (Κεφάλαιο 10). Αν ptr = &arr[0], τότε το ptr + 2 δείχνει στο arr[2] και το *(ptr + 2) είναι το ίδιο το arr[2]. Η έκφραση *(ptr + n), «υπολόγισε τη διεύθυνση n στοιχεία μετά τον δείκτη και δώσε μου τη μεταβλητή εκεί», είναι τόσο συχνή που η C έχει συντομογραφία:

*(ptr + n)   // ⇔ ptr[n]
*(ptr + 3)   // ⇔ ptr[3]

Μας θυμίζει κάτι; Είναι ακριβώς η σύνταξη αναφοράς σε στοιχείο πίνακα. Και πράγματι, το όνομα ενός πίνακα συμπεριφέρεται σαν δείκτης κολλημένος στο πρώτο του στοιχείο: για int a[100]; το a είναι το &a[0], το a[i] είναι το *(a + i) και το a + i είναι το &a[i].

flowchart LR
  P["ptr"] --> A0["arr[0] = 10"]
  A0 --- A1["arr[1] = 20"]
  A1 --- A2["arr[2] = 30"]
  Q["ptr + 2"] --> A2

Σχήμα: ο ptr δείχνει στο arr[0]· το ptr + 2 δείχνει δύο στοιχεία (8 bytes) πιο μετά, στο arr[2].

Γι’ αυτό μια συνάρτηση που δέχεται πίνακα στην πραγματικότητα δέχεται τη διεύθυνση του πρώτου στοιχείου: η παράμετρος int grades[100] είναι ισοδύναμη με int *grades, και ο πίνακας δεν αντιγράφεται (σημειώσεις, «Πίνακες»).

§11.12 Διαφορές πινάκων και δεικτών

Παρόλο που η προσπέλαση στοιχείων είναι ίδια και ο πίνακας είναι ουσιαστικά δείκτης στο πρώτο στοιχείο, πίνακας και δείκτης δεν είναι το ίδιο πράγμα. Με int a[100]; int *ptr;:

  Πίνακας a Δείκτης ptr
Αλλαγή διεύθυνσης Δεν γίνεται: a = ptr; και a++ είναι λάθη Επιτρέπεται: ptr = a;, ptr++
Τι δημιουργεί η δήλωση Θέσεις για τα στοιχεία (100 int) Θέση για μία διεύθυνση
sizeof Όλος ο πίνακας: 100 * sizeof(int) Μία διεύθυνση (8 σε 64 bit)
& &a έχει τη διεύθυνση του πρώτου στοιχείου (&a[0]) &ptr είναι η διεύθυνση του ίδιου του δείκτη

§11.13 Αναδρομή

Αναδρομή (recursion) είναι η μέθοδος κατά την οποία μια συνάρτηση καλεί τον εαυτό της για να λύσει ένα υποπρόβλημα του αρχικού προβλήματος, έως ότου φτάσει σε μια βάση τερματισμού, όπου η αναδρομή σταματά. Έχει δύο βασικά στοιχεία:

  1. Βασική περίπτωση τερματισμού (base case): μια συνθήκη που καθορίζει πότε θα σταματήσει η αναδρομή, και η απάντηση δίνεται απευθείας.
  2. Αναδρομική περίπτωση (recursive case): το τμήμα του κώδικα όπου η συνάρτηση καλεί τον εαυτό της με ένα «μικρότερο» πρόβλημα, που πλησιάζει τη βάση.

Το κλασικό παράδειγμα είναι το παραγοντικό (factorial): το \(n!\) ενός φυσικού αριθμού είναι το γινόμενο όλων των θετικών ακεραίων μικρότερων ή ίσων του \(n\). Ο μαθηματικός του ορισμός είναι ήδη αναδρομικός:

\[n! = 1 \text{ αν } n = 0, \qquad n! = n \times (n-1)! \text{ αν } n > 0\]

και μεταφράζεται στην C σχεδόν λέξη προς λέξη:

int factorial(int number) {
  if (number == 0) return 1;                  // base case
  else return number * factorial(number - 1); // recursive case
}

Η αναδρομική υλοποίηση είναι πολύ κοντά στον ορισμό, κι αυτό κάνει «εύκολο» τον έλεγχο ορθότητας: αρκεί να ελέγξουμε ότι η βάση είναι σωστή και ότι κάθε βήμα εφαρμόζει σωστά τον κανόνα. Κάθε κλήση περιμένει το αποτέλεσμα της επόμενης, και ο πολλαπλασιασμός γίνεται στην «επιστροφή»:

flowchart LR
  F5["factorial(5)"] --> F4["5 * factorial(4)"]
  F4 --> F3["4 * factorial(3)"]
  F3 --> F2["3 * factorial(2)"]
  F2 --> F1["2 * factorial(1)"]
  F1 --> F0["1 * factorial(0)"]
  F0 --> B["1"]

Σχήμα: η αλυσίδα κλήσεων του factorial(5)· οι τιμές επιστρέφονται από δεξιά προς τα αριστερά: 1, 1, 2, 6, 24, 120.

Η αναδρομή πρέπει να τερματίζει. Αν η βάση λείπει ή δεν φτάνεται ποτέ, η συνάρτηση καλεί τον εαυτό της ξανά και ξανά. Κάθε κλήση που δεν έχει επιστρέψει πιάνει χώρο στη μνήμη (στη στοίβα, βλ. Κεφάλαιο 13), οπότε κάποια στιγμή η μνήμη αυτή εξαντλείται και το πρόγραμμα καταρρέει, συνήθως με segmentation fault. Μην ξεχνάτε λοιπόν να γράφετε σωστά base cases, που να καλύπτουν όλες τις εισόδους.

Παραδείγματα

§11.14 Τι τυπώνει: αναθέσεις μέσω δεικτών

Εφαρμογή της αποαναφοράς (*) για γράψιμο και διάβασμα:

#include <stdio.h>
int main() {
  int a = 100, b = 200, c;
  int *ptr_a = &a, *ptr_b = &b, *ptr_c = &c;
  *ptr_c = a;
  *ptr_a = b;
  *ptr_b = *ptr_c;
  printf("%d %d %d", a, b, c);
  return 0;
}

Ακολουθούμε ποια μεταβλητή αλλάζει σε κάθε γραμμή: *ptr_c = a είναι c = 100· *ptr_a = b είναι a = 200· *ptr_b = *ptr_c είναι b = c, δηλαδή b = 100. Τυπώνει 200 100 100 (χωρίς αλλαγή γραμμής, αφού λείπει το \n). Οι δείκτες εδώ λειτουργούν απλώς ως δεύτερα ονόματα για τις a, b, c.

§11.15 Αναφορά σε στοιχεία πίνακα μέσω δείκτη

Εφαρμογή της αριθμητικής δεικτών σε πίνακα:

#include <stdio.h>
int main() {
  int *ptr, arr[] = {10, 20, 30};
  ptr = &arr[0];
  printf("mem[%p], %d\n", ptr, *ptr);
  ptr += 2;
  printf("mem[%p], %d\n", ptr, *ptr);
  return 0;
}

$ ./test
mem[0xffa35e60], 10
mem[0xffa35e68], 30

Το ptr += 2 πρόσθεσε 2 * sizeof(int) = 8 στη διεύθυνση (0x...60 → 0x...68) και ο δείκτης δείχνει πια στο arr[2]. Οι ίδιες οι διευθύνσεις θα είναι διαφορετικές στον δικό σας υπολογιστή· η διαφορά 8 όχι.

§11.16 Πώς τυπώνω μόνο το "World\n";

Από την προηγούμενη διάλεξη έχουμε μια συμβολοσειρά, και θέλουμε να τυπώσουμε μόνο το δεύτερο μισό της:

char hello[] = "Hello World\n";
char *world = &hello[6];
printf("%s", world);          // World

Το %s τυπώνει χαρακτήρες από τη διεύθυνση που του δίνουμε μέχρι το '\0'. Το &hello[6] (ισοδύναμα hello + 6) είναι η διεύθυνση του 'W', άρα τυπώνεται World και η αλλαγή γραμμής. Δεν χρειάστηκε καμία αντιγραφή: ο world απλώς δείχνει μέσα στον ίδιο πίνακα.

§11.17 Μέσος όρος ενός πίνακα 100 ακεραίων

Μια συνάρτηση που δέχεται πίνακα 100 ακεραίων και επιστρέφει τον μέσο όρο:

int average(int grades[100]) {
  int i, sum = 0;
  for (i = 0; i < 100; i++) {
    sum += grades[i];
  }
  return sum / 100;
}

Η συνάρτηση παίρνει τη διεύθυνση του πίνακα (όχι αντίγραφο) και διατρέχει τα στοιχεία με grades[i]. Προσέξτε ότι το sum / 100 είναι ακέραια διαίρεση: ο μέσος όρος στρογγυλεύεται προς τα κάτω. Για ακρίβεια θα επιστρέφαμε double και θα γράφαμε sum / 100.0.

§11.18 Αναζήτηση στοιχείου σε πίνακα

Μια συνάρτηση που δέχεται πίνακα 100 ακεραίων και έναν ακέραιο, και επιστρέφει τη θέση του στοιχείου αν το βρει, αλλιώς -1:

int find(int haystack[100], int needle) {
  int i;
  for (i = 0; i < 100; i++) {
    if (haystack[i] == needle) {
      return i;
    }
  }
  return -1;
}

Το return i μέσα στον βρόχο τερματίζει αμέσως τη συνάρτηση στην πρώτη εμφάνιση. Αν ο βρόχος τελειώσει χωρίς να βρει τίποτα, φτάνουμε στο return -1. Το -1 είναι ασφαλής «σημαία αποτυχίας», γιατί δεν είναι ποτέ έγκυρη θέση πίνακα.

§11.19 Η δική μας atoi

Μια συνάρτηση που παίρνει πίνακα χαρακτήρων (μόνο ψηφία) και επιστρέφει τον ακέραιο που αναπαριστά:

int atoi(char digits[]) {
  int result = 0;
  for (int i = 0; digits[i]; i++) {
    result = 10 * result + digits[i] - '0';
  }
  return result;
}

Η συνθήκη digits[i] σταματά στο '\0' (τιμή 0) στο τέλος της συμβολοσειράς. Το digits[i] - '0' μετατρέπει τον χαρακτήρα ψηφίου στην τιμή του ('7' - '0' == 7), και το 10 * result + «σπρώχνει» τα ψηφία που έχουμε ήδη μία θέση αριστερά: για "123" το result γίνεται 1, 12, 123.

Τι μπορεί να πάει στραβά; Η συνάρτηση υποθέτει πολλά: αν η είσοδος έχει χαρακτήρα που δεν είναι ψηφίο (π.χ. "12a" ή "-5") υπολογίζει σκουπίδια χωρίς να το αναφέρει· αν ο αριθμός δεν χωρά σε int έχουμε υπερχείλιση· και αν ο πίνακας δεν τελειώνει σε '\0', ο βρόχος διαβάζει εκτός ορίων. Επίσης το όνομα atoi συγκρούεται με τη συνάρτηση της stdlib.h, οπότε σε πραγματικό πρόγραμμα θα διαλέγαμε άλλο όνομα.

§11.20 Παραγοντικό από τη γραμμή εντολών

Εφαρμογή της αναδρομής: ολόκληρο το πρόγραμμα, που διαβάζει τον αριθμό από τη γραμμή εντολών (τα argc/argv τα εξηγούμε στο Κεφάλαιο 12):

#include <stdio.h>
#include <stdlib.h>
// Compute the factorial of a number using the recursive
// formula.
int factorial(int number) {
  if (number == 0) return 1;
  else return number * factorial(number - 1);
}
int main(int argc, char **argv) {
  if (argc != 2) {
    printf("Program needs to be called as `./prog number`\n");
    return 1;
  }
  int number = atoi(argv[1]);
  printf("%d! = %d\n", number, factorial(number));
  return 0;
}

Οι διαφάνειες θέτουν τρεις ερωτήσεις για αυτό το πρόγραμμα:

Για εξάσκηση στην αναδρομή, το Εργαστήριο 5 έχει την ακολουθία Collatz και τους αριθμούς Fibonacci.

Κύρια σημεία

  1. Η μνήμη είναι μια σειρά από bytes, και η θέση κάθε byte λέγεται διεύθυνση· η διεύθυνση μιας μεταβλητής είναι η διεύθυνση του πρώτου της byte.
  2. Ο τελεστής & δίνει τη διεύθυνση μιας μεταβλητής· η διεύθυνση είναι ακέραιος και μπορεί να αλλάζει από εκτέλεση σε εκτέλεση.
  3. Ένας δείκτης (τύπος *όνομα) είναι μεταβλητή που κρατά τη διεύθυνση ενός δεδομένου του συγκεκριμένου τύπου.
  4. Όλοι οι δείκτες έχουν το ίδιο μέγεθος, όσο μια διεύθυνση (8 bytes σε 64 bit), ανεξάρτητα από τον τύπο στον οποίο δείχνουν.
  5. Ο τελεστής * (αποαναφορά) δίνει τη μεταβλητή όπου δείχνει ο δείκτης· οι * και & είναι αντίστροφοι, και οι διευθύνσεις τυπώνονται με %p.
  6. Το NULL σημαίνει «πουθενά»· αποαναφορά ενός NULL ή μη αρχικοποιημένου δείκτη οδηγεί συνήθως σε segmentation fault.
  7. Σε δείκτες επιτρέπονται πρόσθεση/αφαίρεση ακεραίου, αφαίρεση δύο δεικτών και σύγκριση· το p + N προχωρά κατά N * sizeof(τύπος) bytes, δηλαδή N στοιχεία.
  8. Το *(ptr + n) γράφεται συντομότερα ptr[n], και το όνομα ενός πίνακα είναι δείκτης κολλημένος στο πρώτο του στοιχείο.
  9. Ένας πίνακας δεν μπορεί να αλλάξει διεύθυνση, και τα sizeof, & δίνουν άλλα αποτελέσματα σε πίνακα και σε δείκτη.
  10. Μια συνάρτηση που δέχεται πίνακα δουλεύει πάνω στον ίδιο πίνακα, μέσω της διεύθυνσής του.
  11. Αναδρομή είναι μια συνάρτηση που καλεί τον εαυτό της· χρειάζεται base case και recursive case που πλησιάζει τη βάση, και η αναδρομική υλοποίηση του παραγοντικού ακολουθεί κατά λέξη τον μαθηματικό ορισμό.
  12. Η αναδρομή πρέπει να τερματίζει: χωρίς σωστή βάση για όλες τις εισόδους, το πρόγραμμα καταρρέει.

Ορολογία

Ελληνικά English Σύντομος ορισμός
διεύθυνση address Η θέση ενός byte στη μνήμη· ένας ακέραιος.
δείκτης pointer Μεταβλητή που κρατά τη διεύθυνση ενός δεδομένου.
δείχνει σε points to Ο δείκτης κρατά τη διεύθυνση της μεταβλητής.
αποαναφορά dereference Πρόσβαση με * στη μεταβλητή όπου δείχνει ο δείκτης.
κενός δείκτης null pointer (NULL) Δείκτης με τιμή 0 που δεν δείχνει πουθενά.
μη έγκυρος δείκτης invalid pointer Δείκτης που δεν κρατά έγκυρη διεύθυνση.
σφάλμα κατάτμησης segmentation fault Τερματισμός από πρόσβαση σε μη επιτρεπτή μνήμη.
αριθμητική δεικτών pointer arithmetic Το p + n δείχνει n στοιχεία (όχι bytes) μετά.
αναδρομή recursion Μια συνάρτηση καλεί τον εαυτό της.
βασική περίπτωση base case Η συνθήκη όπου η αναδρομή σταματά.
αναδρομική περίπτωση recursive case Το σημείο όπου η συνάρτηση καλεί τον εαυτό της.
παραγοντικό factorial \(n! = 1 \cdot 2 \cdots n\), με \(0! = 1\).
υπερχείλιση overflow Αποτέλεσμα που δεν χωρά στον τύπο του.

Διάβασμα

Συχνά λάθη

Τι δυσκόλεψε την τάξη

Από τα Kahoot των διαλέξεων: οι ερωτήσεις όπου μια λάθος απάντηση μάζεψε πολλές ψήφους, με το ποσοστό σωστών απαντήσεων.

Ερωτήσεις κατανόησης

Kahoot από το αμφιθέατρο (Κ11.1–Κ11.14)

Ερωτήσεις που παίχτηκαν στις διαλέξεις, με το ποσοστό των φοιτητών που απάντησαν σωστά.

Ασκήσεις

Ζέσταμα: από τις διαφάνειες (Α11.1–Α11.13)

Εργαστήριο (Α11.14–Α11.18)

Εργασίες (Α11.19–Α11.21)

Θέματα εξετάσεων (Α11.22)

Σχετικές ασκήσεις από άλλα κεφάλαια

  1. Η διεύθυνση του πρώτου byte της, 100. ↩

  2. p είναι η διεύθυνση της x· *p είναι η ίδια η x (42)· &p είναι η διεύθυνση του δείκτη p. ↩

  3. 8 bytes ο καθένας: ο δείκτης κρατά μια διεύθυνση, ανεξάρτητα από τον τύπο. ↩

  4. Ο p δεν αρχικοποιήθηκε, άρα δεν περιέχει έγκυρη διεύθυνση· η αποαναφορά του δίνει συνήθως segmentation fault. ↩

  5. Στη 1000 + 3 · 8 = 1024. ↩

  6. *(arr + 4). ↩

  7. sizeof(a) είναι 400, sizeof(ptr) είναι 8. ↩

  8. Η βασική περίπτωση τερματισμού (base case) και η αναδρομική περίπτωση (recursive case). ↩

  9. 4 φορές: factorial(3), (2), (1), (0), δηλαδή 3 αναδρομικές κλήσεις. ↩

Κατεβάστε το κεφάλαιο: PDF · Markdown · GitHub