Kap04.pps - Lehrstuhl 11 Algorithm Engineering

 Documents

 21 views
of 36
All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.
Description
Einführung in die Programmierung Wintersemester 2009/10 Prof. Dr. Günter Rudolph Lehrstuhl für Algorithm Engineering Fakultät für Informatik TU Dortmund…
Share
Transcript
Einführung in die Programmierung Wintersemester 2009/10 Prof. Dr. Günter Rudolph Lehrstuhl für Algorithm Engineering Fakultät für Informatik TU Dortmund Kapitel 4: Zeiger Kapitel 4 Inhalt ● Zeiger ● Zeigerarithmetik ● Zeiger für dynamischen Speicher ● Anwendungen G. Rudolph: Einführung in die Programmierung ▪ WS 2009/10 2 Zeiger Kapitel 4 Caveat! ● Fehlermöglichkeiten immens groß! ● Falsch gesetzte Zeiger  Programm- und zuweilen Rechnerabstürze! Aber: ● Machtvolles Konzept! ● Deshalb genaues Verständnis unvermeidlich! ● Dazu müssen wir etwas ausholen ... G. Rudolph: Einführung in die Programmierung ▪ WS 2009/10 3 Zeiger Kapitel 4 ● Speicherplätzen sind fortlaufende Nummern (= Adressen) zugeordnet ● Datentyp legt Größe eines Datenobjektes fest ● Lage eines Datenobjektes im Speicher bestimmt durch Anfangsadresse ● Zeiger = Datenobjekt mit Inhalt (4 Byte) ● Inhalt interpretiert als Adresse eines anderen Datenobjektes Zeiger Datenobjekt Adresse Inhalt Adresse Inhalt 4711 32760 32760 G. Rudolph: Einführung in die Programmierung ▪ WS 2009/10 4 Zeiger Kapitel 4 Zeiger Datenobjekt Adresse Inhalt Adresse Inhalt 4711 32760 32760 Adresse Inhalt Adresse Inhalt des des des des Zeigers Zeigers Objekts Objekts G. Rudolph: Einführung in die Programmierung ▪ WS 2009/10 5 Zeiger Kapitel 4 Beispiel: Visitenkarte Hugo Hase X-Weg 4 X-Weg 42 2 Zeiger Objekt Inhalt: Adresse X-Weg 42 Inhalt: Hugo Hase G. Rudolph: Einführung in die Programmierung ▪ WS 2009/10 6 Zeiger Kapitel 4 Zeiger: Wofür? ● Zeiger weiterreichen einfacher als Datenobjekt weiterreichen ● Zeiger verschieben einfacher / effizienter als Datenobjekt verschieben ● etc. Datendefinition Datentyp *Bezeichner; → reserviert 4 Byte für einen Zeiger, der auf ein Datenobjekt vom Typ des angegebenen Datentyps verweist Beispiel ● double Umsatz; „Herkömmliche“ Variable vom Type double double *pUmsatz; Zeiger auf Datentyp double G. Rudolph: Einführung in die Programmierung ▪ WS 2009/10 7 Zeiger Kapitel 4 Was passiert genau? reserviert 8 Byte für Datentyp double; double Umsatz; symbolischer Name: Umsatz; Rechner kennt jetzt Adresse des Datenobjektes reserviert 4 Byte für einen Zeiger, double *pUmsatz; der auf ein Datenobjekt vom Type double zeigen kann; symbolischer Name: pUmsatz Umsatz = 122542.12; Speicherung des Wertes 122542.12 an Speicherort mit symbolischer Adresse Umsatz holt Adresse des Datenobjektes, pUmsatz = &Umsatz; das an symbolischer Adresse Umsatz gespeichert ist; speichert Adresse in pUmsatz indirekte Wertzuweisung: *pUmsatz = 125000.; Wert 125000. wird als Inhalt an den Speicherort gelegt, auf den pUmsatz zeigt G. Rudolph: Einführung in die Programmierung ▪ WS 2009/10 8 Zeiger Kapitel 4 Zwei Operatoren: * und & ● *-Operator: - mit Datentyp: Erzeugung eines Zeigers double *pUmsatz; - mit Variable: Inhalt des Ortes, an den Zeiger zeigt *pUmsatz = 10.24; ● &-Operator: ermittelt Adresse des Datenobjektes pUmsatz = &Umsatz; Wie interpretiert man Datendefinition richtig? Man lese von rechts nach links! double *pUmsatz; 1. pUmsatz ist … 2. Zeiger auf … 3. Typ double G. Rudolph: Einführung in die Programmierung ▪ WS 2009/10 9 Zeiger Kapitel 4 Initialisierung Sei bereits double Umsatz; vorhanden: double *pUmsatz = &Umsatz; oder int *pINT = NULL; oder Nullpointer! Symbolisiert Adresse, int *pINT = 0; auf der niemals ein Datenobjekt liegt! Verwendung Nullzeiger: Zeiger zeigt auf Nichts! Er ist „leer“! G. Rudolph: Einführung in die Programmierung ▪ WS 2009/10 10 Zeiger Kapitel 4 Beispiele: double a = 4.0, b = 5.0, c; c = a + b; double *pa = &a, *pb = &b, *pc = &c; *pc = *pa + *pb; double x = 10.; double y = *&x; G. Rudolph: Einführung in die Programmierung ▪ WS 2009/10 11 Zeiger Kapitel 4 Typischer Fehler ● double *widerstand; *widerstand = 120.5; Dem Zeiger wurde keine Adresse zugewiesen! Er zeigt also irgendwo hin: a) Falls in geschützten Speicher, dann Abbruch wg. Speicherverletzung!  b) Falls in nicht geschützten Speicher, dann Veränderung anderer Daten! Folge: Seltsames Programmverhalten! Schwer zu erkennender Fehler!  G. Rudolph: Einführung in die Programmierung ▪ WS 2009/10 12 Zeiger Kapitel 4 Unterscheidung ● Konstante Zeiger char *text = “Hallo“; Aber: Es gibt int feld[] = { 2, 3, 4 }; Compiler- zeigt auf feste Adresse im Speicher, spezifische auf die Programmierer nicht verändernd zugreifen kann! Unterschiede! text → H a l l o \0 feld → 2 3 4 int *const cpFeld = feld; v.r.n.l.: cpFeld ist constanter Zeiger auf Datentyp int G. Rudolph: Einführung in die Programmierung ▪ WS 2009/10 13 Exkurs: const Qualifizierer Kapitel 4 Schlüsselwort const gibt an, dass Werte nicht verändert werden können! Leider gibt es 2 Schreibweisen: const int a = 1; identisch zu int const a = 1; ) konstanter Integer ) da Konstanten kein Wert zuweisbar, Wertbelegung bei Initialisierung! verschiedene Schreibweisen können zu Verwirrungen führen … (besonders bei Zeigern !) ) am besten konsistent bei einer Schreibweise bleiben! G. Rudolph: Einführung in die Programmierung ▪ WS 2009/10 14 Exkurs: const Qualifizierer Kapitel 4 Fragen: 1. Was ist konstant? 2. Wo kommt das Schlüsselwort const hin? char* s1 = "Zeiger auf char"; char const* s2 = "Zeiger auf konstante char"; char* const s3 = "Konstanter Zeiger auf char"; char const* const s4 = "Konstanter Zeiger auf konstante char"; Sinnvolle Konvention / Schreibweise: Konstant ist, was vor dem Schlüsselwort const steht! ) Interpretation der Datendefinition / Initialisierung von rechts nach links! G. Rudolph: Einführung in die Programmierung ▪ WS 2009/10 15 Exkurs: const Qualifizierer Kapitel 4 Zeiger Inhalt char* s1 = "1"; V V char const* s2 = "2"; V K V: veränderlich K: konstant char* const s3 = "3"; K V char const* const s4 = "4"; K K *s1 = 'a'; *s2 = 'b'; // Fehler: Inhalt nicht veränderbar *s3 = 'c'; *s4 = 'd'; // Fehler: Inhalt nicht veränderbar char* s0 = "0"; s1 = s0; s2 = s0; s3 = s0; // Fehler: Zeiger nicht veränderbar s4 = s0; // Fehler: Zeiger nicht veränderbar G. Rudolph: Einführung in die Programmierung ▪ WS 2009/10 16 Zeiger Kapitel 4 Unterscheidung ● Veränderliche Zeiger double x = 2.0, y = 3.0, z = 7.0, s = 0.0, *ptr; ptr = &x; s += *ptr; ptr = &y; s += *ptr; ptr = &z; s += *ptr; ptr nimmt nacheinander verschiedene Werte (Adressen) an s hat am Ende den Wert 12.0 ptr x y z G. Rudolph: Einführung in die Programmierung ▪ WS 2009/10 17 Zeiger Kapitel 4 Zeigerarithmetik Sei T ein beliebiger Datentyp in der Datendefinition T *ptr; und ptr ein Zeiger auf ein Feldelement eines Arrays von Typ T Dann bedeutet: ptr = ptr + 1; oder ++ptr; dass der Zeiger ptr auf das nächste Feldelement zeigt. Analog: ptr = ptr – 1; oder --ptr; Zeiger ptr zeigt dann auf das vorherige Feldelement G. Rudolph: Einführung in die Programmierung ▪ WS 2009/10 18 Zeiger Kapitel 4 Zeigerarithmetik Achtung: T val; T *ptr = &val; ptr = ptr + 2; In der letzten Zeile werden nicht 2 Byte zu ptr hinzugezählt, sondern 2 mal die Speichergröße des Typs T. Das wird auch dann durchgeführt wenn ptr nicht auf Array zeigt. G. Rudolph: Einführung in die Programmierung ▪ WS 2009/10 19 Zeiger Kapitel 4 Zeigerarithmetik int a[] = { 100, 110, 120, 130 }, *pa, sum = 0; pa = &a[0]; sum += *pa + *(pa + 1) + *(pa + 2) + *(pa + 3); struct KundeT { Größe des Datentyps KundeT: double umsatz; float skonto; 8 + 4 = 12 Byte }; KundeT Kunde[5], *pKunde; pKunde = &Kunde[0]; Sei pKunde == 10000 int i = 3; *pKunde = *(pKunde + i); Dann(pKunde + i) == 10036 G. Rudolph: Einführung in die Programmierung ▪ WS 2009/10 20 Zeiger Kapitel 4 Zeigerarithmetik char *quelle = “Ich bin eine Zeichenkette“; char ziel[100] , *pz; // Länge der Zeichenkette Kommentar char *pq = quelle; while (*pq != ‘\0‘) pq++; int len = pq – quelle; if (len < 100) { // Kopieren der Zeichenkette Kommentar pq = quelle; pz = ziel; while (*pq != ‘\0‘) { *pz = *pq; pz++; pq++; } später! } *pz = ‘\0‘; G. Rudolph: Einführung in die Programmierung ▪ WS 2009/10 21 Zeiger Kapitel 4 Zeiger auf Datenverbund (struct) struct punktT { int x , y; }; punktT punkt[1000]; punktT *ptr = punkt; punkt[0].x = 10; ptr->x = 10; punkt[2].x = 20;  (ptr + 2)->x = 20; punkt[k].x = 100; (ptr + k)->x = 100; (*ptr).x ist identisch zu ptr->x G. Rudolph: Einführung in die Programmierung ▪ WS 2009/10 22 Zeiger Kapitel 4 Aufgabe: Lese zwei Vektoren reeller Zahlen der Länge n ein. Berechne das Skalarprodukt … … und gebe den Wert auf dem Bildschirm aus! Lösungsansatz: Vektoren als Arrays von Typ double. n darf höchstens gleich der Arraygröße sein! Testen und ggf. erneute Eingabe! G. Rudolph: Einführung in die Programmierung ▪ WS 2009/10 23 Zeiger Kapitel 4 #include using namespace std; int main() { unsigned int const nmax = 100; unsigned int i, n; double a[nmax], b[nmax]; // Dimension n einlesen und überprüfen do { cout << "Dimension ( n < " << nmax << " ): "; cin >> n; } while (n < 1 || n > nmax); (Fortsetzung folgt …) Datendefinition double a[nmax] OK, weil nmax eine Konstante ist! Ohne const: Fehlermeldung! z.B. „Konstanter Ausdruck erwartet“ G. Rudolph: Einführung in die Programmierung ▪ WS 2009/10 24 Sinn & Zweck des ISO Standards für C++ Kapitel Intermezzo4 Der aktuelle GNU C++ Compiler erlaubt folgendes: #include Aber: Der Microsoft C++ Compiler (VS 2003) meldet einen Fehler! int main() { int n; Variable Arraygrenzen sind nicht std::cin >> n; Bestandteil des C++ Standards! double a[n]; a[0] = 3.14; Verwendung von Compiler-spezifischen return 0; Spracherweiterungen führt zu Code, der } nicht portabel ist!    Das ist nicht wünschenswert! G. Rudolph: Einführung in die Programmierung ▪ WS 2009/10 25 Sinn & Zweck des ISO Standards für C++ Kapitel Intermezzo4 #include Also: Bei Softwareentwicklung nur Sprachelemente des C++ Standards int main() { verwenden! int n; Bei GNU Compiler: Option -pedantic std::cin >> n; double a[n]; a[0] = 3.14; C++ Standard ISO/IEC 14882-2003 return 0; z.B. als PDF-Datei erhältlich für 30$ } http://webstore.ansi.org/ G. Rudolph: Einführung in die Programmierung ▪ WS 2009/10 26 Zeiger Kapitel 4 (… Fortsetzung) // Vektor a einlesen for (i = 0; i < n; i++) { cout << "a[" << i << "]= "; cin >> a[i]; Anmerkung: } // Vektor b einlesen Fast identischer for (i = 0; i < n; i++) { Code! cout << "b[" << i << "]= "; cin >> b[i]; Effizienter mit } Funktionen! // Skalarprodukt berechnen → nächstes double sp = 0.; Kapitel! for (i = 0; i < n; i++) sp += a[i] * b[i]; // Ausgabe cout << "Skalarprodukt = " << sp << endl; return 0; } G. Rudolph: Einführung in die Programmierung ▪ WS 2009/10 27 Zeiger Kapitel 4 Unbefriedigend bei der Implementierung: Maximale festgelegte Größe des Vektors! → Liegt an der unterliegenden Datenstruktur Array: Array ist statisch, d.h. Größe wird zur Übersetzungszeit festgelegt und ist während der Laufzeit des Programms nicht veränderbar! Schön wären dynamische Datenstrukturen, d.h. Größe wird zur Übersetzungszeit nicht festgelegt und ist während der Laufzeit des Programms veränderbar! Das geht mit dynamischem Speicher … … und Zeigern! G. Rudolph: Einführung in die Programmierung ▪ WS 2009/10 28 Exkurs: Dynamischer Speicher Kapitel 4 Erzeugen und Löschen eines Objekts zur Laufzeit: 1. Operator new erzeugt Objekt 2. Operator delete löscht zuvor erzeugtes Objekt Beispiel: (Erzeugen) Beispiel: (Löschen) int *xp = new int; delete xp; double *yp = new double; delete yp; struct PunktT { int x, y; }; PunktT *pp = new PunktT; delete pp; int n = 10; variabel, int *xap = new int[n]; delete[] xap; nicht PunktT *pap = new PunktT[n]; delete[] pap; konstant! G. Rudolph: Einführung in die Programmierung ▪ WS 2009/10 29 Exkurs: Dynamischer Speicher Kapitel 4 Bauplan: Datentyp *Variable = new Datentyp; (Erzeugen) delete Variable; (Löschen) Bauplan für Arrays: Datentyp *Variable = new Datentyp[Anzahl]; (Erzeugen) delete[] Variable; (Löschen) Achtung: Dynamisch erzeugte Objekte müssen auch wieder gelöscht werden! Keine automatische Speicherbereinigung! G. Rudolph: Einführung in die Programmierung ▪ WS 2009/10 30 Exkurs: Dynamischer Speicher Kapitel 4 Wo wird Speicher angelegt?  im Freispeicher alias Heap alias dynamischen Speicher wächst nach Heap „unten“ wenn Heapgrenze auf Stackgrenze stösst: Out of Memory Error Stack wächst nach  „oben“ Stack bereinigt sich selbst, Programm und für Heap ist Programmierer statischer Speicher verantwortlich! G. Rudolph: Einführung in die Programmierung ▪ WS 2009/10 31 Zeiger Kapitel 4 Zurück zur Beispielaufgabe: unsigned int const nmax = 100; unsigned int i, n; double a[nmax], b[nmax]; vorher: do { statischer cout << "Dimension ( n < " << nmax << " ): "; Speicher cin >> n; } while (n < 1 || n > nmax); unsigned int i, n; double *a, *b; do { nachher: cout << "Dimension: "; cin >> n; dynamischer } while (n < 1); Speicher a = new double[n]; b = new double[n]; G. Rudolph: Einführung in die Programmierung ▪ WS 2009/10 32 Zeiger Kapitel 4 Nicht vergessen: Am Ende angeforderten dynamische Speicher wieder freigeben! delete[] a; delete[] b; return 0; } Sonst „Speicherleck“! ) Programm terminiert möglicherweise anormal mit Fehlermeldung! G. Rudolph: Einführung in die Programmierung ▪ WS 2009/10 33 Zeiger Kapitel 4 Beispiel für programmierten Absturz: #include using namespace std; int main() { unsigned int const size = 100 * 1024; unsigned short k = 0; while (++k < 5000) { bei k ¼ 2500 sind double* ptr = new double[size]; 2 GB erreicht cout << k << endl; // delete[] ptr; ) Abbruch! } return 0; } G. Rudolph: Einführung in die Programmierung ▪ WS 2009/10 34 Zeiger Kapitel 4 Projekt: Matrix mit dynamischem Speicher (Größe zur Laufzeit festgelegt!) Vorüberlegungen: Speicher im Rechner ist linear! ) Rechteckige / flächige Struktur der Matrix linearisieren! x x x x x x x x y y y y z z z z y y y y z z z z n Zeilen, m Spalten ) n x m Speicherplätze! G. Rudolph: Einführung in die Programmierung ▪ WS 2009/10 35 Zeiger Kapitel 4 Projekt: Matrix mit dynamischem Speicher (Größe zur Laufzeit festgelegt!) double **matrix; matrix = new double*[zeilen]; Zugriff wie beim matrix[0] = new double[zeilen * spalten]; zweidimensionalen for (i = 1; i < zeilen; i++) statischen Array: matrix[i] = matrix[i-1] + spalten; matrix[2][3] = 2.3; matrix zeigt matrix[0] auf double* matrix[2][3] G. Rudolph: Einführung in die Programmierung ▪ WS 2009/10 36
Related Search
We Need Your Support
Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

Thanks to everyone for your continued support.

No, Thanks