Programmeermethoden C++
Walter Kosters Leiden Institute of Advanced Computer Science Universiteit Leiden
september 2007
Inhoudsopgave 1
2
3
Computers en programmeren 1.1 De computer algemeen # . . . . . . . . . . . . . . . . . . . . . . 1.2 De C++ compiler # . . . . . . . . . . . . . . . . . . . . . . . . . 1.3 Operating Systemen # . . . . . . . . . . . . . . . . . . . . . . . . 1.4 Andere termen # . . . . . . . . . . . . . . . . . . . . . . . . . . 1.5 Een klein programma # . . . . . . . . . . . . . . . . . . . . . . . 1.6 Windows computers . . . . . . . . . . . . . . . . . . . . . . . . . 1.6.1 Inloggen en bladeren # . . . . . . . . . . . . . . . . . . . 1.6.2 Programmeren . . . . . . . . . . . . . . . . . . . . . . . 1.6.3 Thuis in C++ programmeren met Windows . . . . . . . . 1.7 Unix computers . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.7.1 Beginnen op de Linux PC’s # . . . . . . . . . . . . . . . 1.7.2 De Unix terminal, programma’s starten en bestandsbeheer 1.7.3 Programmeren . . . . . . . . . . . . . . . . . . . . . . . 1.7.4 Thuis in C++ programmeren met Linux * . . . . . . . . . 1.8 Mailen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Werken met Unix 2.1 Unix commando’s * . . . . . . . . 2.1.1 Syntax van een commando 2.1.2 Procesbeheer . . . . . . . 2.1.3 Files . . . . . . . . . . . . 2.1.4 Input/Output . . . . . . . 2.1.5 Pipelining . . . . . . . . . 2.1.6 Geschiedenis . . . . . . . 2.2 De editor vi in een notedop * . . . 2.3 Mailen met elm/mutt * . . . . . . 2.4 Slotopmerkingen * . . . . . . . .
. . . . . . . . . . . . . . .
. . . . . . . . . . . . . . .
. . . . . . . . . . . . . . .
. . . . . . . . . . . . . . .
. . . . . . . . . . . . . . .
. . . . . . . . . . . . . . .
. . . . . . . . . . . . . . .
3 3 4 5 6 7 7 7 8 8 9 9 10 12 12 13
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
14 14 14 14 15 17 17 17 17 19 19
C++: Concepten en programmeervoorbeelden 3.1 Bibliotheken . . . . . . . . . . . . . . . . . . 3.2 Commentaar . . . . . . . . . . . . . . . . . . 3.3 Variabelen . . . . . . . . . . . . . . . . . . . 3.4 Condities . . . . . . . . . . . . . . . . . . . 3.5 Loops . . . . . . . . . . . . . . . . . . . . . 3.6 Functies . . . . . . . . . . . . . . . . . . . . 3.6.1 Parameters . . . . . . . . . . . . . . 3.7 Files . . . . . . . . . . . . . . . . . . . . . . 3.8 Arrays en matrices . . . . . . . . . . . . . . 3.9 Werken met variabelen en getallen . . . . . . 3.9.1 Werken met verschillende types . . . 3.9.2 Rekenen . . . . . . . . . . . . . . . . 3.9.3 Random getallen en static variabelen 3.10 Recursie . . . . . . . . . . . . . . . . . . . . 3.11 Object geori¨enteerd programmeren . . . . . .
. . . . . . . . . . . . . . .
. . . . . . . . . . . . . . .
. . . . . . . . . . . . . . .
. . . . . . . . . . . . . . .
. . . . . . . . . . . . . . .
. . . . . . . . . . . . . . .
. . . . . . . . . . . . . . .
. . . . . . . . . . . . . . .
. . . . . . . . . . . . . . .
. . . . . . . . . . . . . . .
. . . . . . . . . . . . . . .
. . . . . . . . . . . . . . .
. . . . . . . . . . . . . . .
. . . . . . . . . . . . . . .
. . . . . . . . . . . . . . .
. . . . . . . . . . . . . . .
. . . . . . . . . . . . . . .
. . . . . . . . . . . . . . .
21 21 21 22 22 24 26 27 29 31 32 32 34 35 36 40
. . . . . . . . . .
. . . . . . . . . .
i
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . .
41 41 44 47 48 49
. . . . . . . . . . . . . . .
50 50 50 51 52 54 54 57 57 58 58 60 61 61 61 62
5
Abstracte Datastructuren 5.1 Stapels en rijen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.2 Binaire bomen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
64 64 68
6
Meerdere files compileren 6.1 Waarom meerdere files? . . . . . . . . . . 6.2 Header files en implementaties . . . . . . 6.3 Meerdere header en meerdere source files 6.4 Linking . . . . . . . . . . . . . . . . . . 6.4.1 Visual C++ . . . . . . . . . . . . 6.4.2 Unix en de Makefile . . . . . . .
. . . . . .
72 72 73 74 76 76 76
. . . . . . . . .
79 79 80 80 83 85 85 87 87 89
3.12 3.13 3.14 3.15 4
7
3.11.1 Struct’s . . . . . . . . . . . . 3.11.2 Classes . . . . . . . . . . . . Pointers . . . . . . . . . . . . . . . . Strings . . . . . . . . . . . . . . . . . De Standard Template Library — STL C++-standaards . . . . . . . . . . . .
. . . . . .
. . . . . .
. . . . . .
Algoritmen 4.1 Rekenalgoritmen . . . . . . . . . . . . . . 4.1.1 Grootste gemeenschappelijke deler 4.1.2 Priemgetallen . . . . . . . . . . . . 4.1.3 Driehoek van Pascal . . . . . . . . 4.1.4 Matrixvermenigvuldiging . . . . . 4.1.5 Verzamelingen . . . . . . . . . . . 4.2 Zoeken en Sorteren . . . . . . . . . . . . . 4.2.1 Lineair zoeken . . . . . . . . . . . 4.2.2 Binair zoeken . . . . . . . . . . . . 4.2.3 Een eenvoudige sorteermethode . . 4.2.4 Bubblesort . . . . . . . . . . . . . 4.2.5 Invoegsorteer . . . . . . . . . . . . 4.2.6 Shellsort . . . . . . . . . . . . . . 4.2.7 Quicksort . . . . . . . . . . . . . . 4.2.8 Indexbestanden . . . . . . . . . . .
. . . . . .
. . . . . .
. . . . . . . . . . . . . . .
. . . . . .
. . . . . .
. . . . . . . . . . . . . . .
. . . . . .
. . . . . .
. . . . . . . . . . . . . . .
. . . . . .
. . . . . .
. . . . . . . . . . . . . . .
. . . . . .
. . . . . .
. . . . . . . . . . . . . . .
. . . . . .
. . . . . .
. . . . . . . . . . . . . . .
. . . . . .
. . . . . .
. . . . . . . . . . . . . . .
. . . . . .
Grafische interfaces 7.1 Visual C++ . . . . . . . . . . . . . . . . . . . . . . . . 7.2 De BKE applicatie . . . . . . . . . . . . . . . . . . . . 7.3 Een nieuw project starten . . . . . . . . . . . . . . . . . 7.4 Controls en resources toevoegen . . . . . . . . . . . . . 7.5 Tussen interface en code . . . . . . . . . . . . . . . . . 7.5.1 Het koppelen van controls aan membervariabelen 7.5.2 Het koppelen van signals aan code . . . . . . . . 7.6 Het invullen van de functionaliteit . . . . . . . . . . . . 7.7 Koppelen van de echte BKE functionaliteit . . . . . . . .
ii
. . . . . .
. . . . . . . . . . . . . . .
. . . . . .
. . . . . . . . .
. . . . . .
. . . . . . . . . . . . . . .
. . . . . .
. . . . . . . . .
. . . . . .
. . . . . . . . . . . . . . .
. . . . . .
. . . . . . . . .
. . . . . .
. . . . . . . . . . . . . . .
. . . . . .
. . . . . . . . .
. . . . . .
. . . . . . . . . . . . . . .
. . . . . .
. . . . . . . . .
. . . . . .
. . . . . . . . . . . . . . .
. . . . . .
. . . . . . . . .
. . . . . .
. . . . . . . . . . . . . . .
. . . . . .
. . . . . . . . .
. . . . . .
. . . . . . . . . . . . . . .
. . . . . .
. . . . . . . . .
. . . . . .
. . . . . . . . . . . . . . .
. . . . . .
. . . . . . . . .
. . . . . .
. . . . . . . . . . . . . . .
. . . . . .
. . . . . . . . .
. . . . . .
. . . . . . . . . . . . . . .
. . . . . .
. . . . . . . . .
8
9
Richtlijnen bij programmeeropgaven 8.1 Commentaar . . . . . . . . . . . . 8.2 Layout . . . . . . . . . . . . . . . 8.3 Modulariteit . . . . . . . . . . . . 8.4 Conclusie . . . . . . . . . . . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
Opgaven
92 92 93 94 94 95
10 Oude tentamens 10.1 Tentamen vrijdag 5 januari 1996 . . . . . . . . . . . 10.2 Tentamen vrijdag 8 augustus 1997 . . . . . . . . . . 10.2.1 Uitwerking tentamen vrijdag 8 augustus 1997 10.3 Tentamen maandag 5 januari 2004 . . . . . . . . . .
iii
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
109 109 111 113 115
Lijst met voorbeeldprogramma’s
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43
Dit komt op het scherm . . . . . . . Straal berekenen . . . . . . . . . . . Kwadraten 1 . . . . . . . . . . . . . Kwadraten 2 . . . . . . . . . . . . . Integers wisselen . . . . . . . . . . Soorten variabelen . . . . . . . . . Wisseltruc . . . . . . . . . . . . . . File kopi¨eren . . . . . . . . . . . . Array-elementen optellen . . . . . . Matrix-elementen optellen . . . . . Integer-types . . . . . . . . . . . . Integer naar double . . . . . . . . . Double naar integer . . . . . . . . . Re¨ele getallen afdrukken . . . . . . Random getal . . . . . . . . . . . . Random getal beter . . . . . . . . . Random permutatie . . . . . . . . . Faculteit berekenen . . . . . . . . . Fibonacci getallen . . . . . . . . . . Fibonacci getallen effici¨ent . . . . . Fibonacci getallen effici¨ent (iteratief) Torens van Hanoi . . . . . . . . . . Klasse: IJsjes maken . . . . . . . . Werken met pointers . . . . . . . . Pointerlijst: doorlopen . . . . . . . Pointerlijst: vooraan toevoegen . . . Pointerlijst: achteraan toevoegen . . Pointerlijst: vakje vinden . . . . . . Pointerlijst: recursief vakje vinden . String compare . . . . . . . . . . . GGD berekenen . . . . . . . . . . . Breuken vereenvoudigen . . . . . . GGD recursief berekenen . . . . . . Priemgetal? . . . . . . . . . . . . . De zeef van Erathosthenes . . . . . Driehoek van Pascal . . . . . . . . . Driehoek van Pascal effici¨ent . . . . Matrixvermenigvuldiging . . . . . . Verzameling . . . . . . . . . . . . . Trekking uit een verzameling . . . . Zoek kleinste getal . . . . . . . . . Lineair zoeken . . . . . . . . . . . Binair zoeken iteratief . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
iv
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7 23 24 25 27 28 29 30 31 32 33 33 33 34 35 35 36 37 37 38 39 40 42 44 45 45 46 47 47 48 50 50 51 51 52 53 53 54 55 56 57 58 59
44 45 46 47 48 49 50 51 52 53 54 55 56 57
Binair zoeken recursief . . . . Simpel sorteren . . . . . . . . Bubblesort . . . . . . . . . . . Shellsort . . . . . . . . . . . . Stapel: Verwijder grootste . . . Een Stapelvakje . . . . . . . . De klasse stapel . . . . . . . . De klasse rij . . . . . . . . . . Een alternatieve rij . . . . . . Knoop van een binaire boom . Preorde wandeling . . . . . . Boomknopen tellen . . . . . . Binaire boom vellen . . . . . . Boter, Kaas en Eieren, het bord
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .
v
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .
59 60 61 62 65 65 66 67 69 70 70 71 71 73
Inleiding Dit dictaat is bedoeld als hulpmiddel bij het volgen van het vak Programmeermethoden. Het biedt niet voldoende informatie om te leren programmeren in C++. Daarvoor is het in de eerste plaats verstandig een goed boek aan te schaffen, zoals dat van Savitch (zie verderop). Dit dictaat is noodzakelijk om verschillende redenen: • Dit dictaat geeft aan hoe de computers in het Snellius gebruikt kunnen worden om te programmeren. Niet alle computers werken met een variant van Microsoft Windows zoals de meeste mensen dat thuis hebben. Om met de alternatieven te kunnen werken is enige extra uitleg noodzakelijk. • De meeste boeken sluiten niet goed aan op de inhoud van het vak zoals dat in Leiden gegeven wordt. Zo staat in dit dictaat een uitgebreidere beschrijving van “algoritmen” (rekenvoorschriften). • Het dictaat biedt een kort overzicht van de elementen van de programmeertaal C++ die belangrijk zijn bij het volgen van het vak. Boeken bespreken over het algemeen namelijk veel meer taalconstructies dan nodig zijn bij dit vak. • Er staan flink wat opgaven en oude tentamens in het dictaat. • En: de beginselen van het werken aan een grafische user interface.
Leeswijzer In dit dictaat is dus een heleboel informatie verzameld, en daarnaast is er ook nog het boek van Savitch. Het is echter niet nodig alle informatie te begrijpen of te onthouden. Om het lezen iets gemakkelijker te maken, zijn er in dit dictaat markeringen aangebracht. Paragrafen met een ster (*) zijn bedoeld voor gevorderde computergebruikers. In sommige situaties kan het handig zijn deze paragrafen door te lezen, maar zonder ze door te nemen is het ook mogelijk het vak goed te doorlopen. Hoofdstuk 2 heeft bijvoorbeeld een * omdat je dit gedeelte niet meteen uit je hoofd hoeft te weten, maar het voor het (Unix-)vervolg wel erg handig is. Een ander soort paragrafen zijn die met een #. Ervaren computergebruikers (cq. programmeurs) kunnen deze paragrafen overslaan, maar voor de deelnemers die nog weinig ervaring hebben met computers, is het zeer raadzaam ze door te nemen. Als bijvoorbeeld termen zoals “compilers” of “shells” onbekend voorkomen, is het wijs deze paragrafen niet over te slaan. In Hoofdstuk 1 wordt begonnen met een algemene uitleg over computers (op beginnersniveau). In Hoofdstuk 1.6 en Hoofdstuk 1.7 vind je terug hoe je met de computers in het Snellius (maar ook thuis) moet werken om programma’s te kunnen maken. In Hoofdstuk 3 staan een flink aantal belangrijke C++- en programmeerconcepten op een rijtje die aan de hand van voorbeeldprogrammaatjes duidelijk worden gemaakt. Meer voorbeeldprogramma’s zijn te vinden in Hoofdstuk 4. Hierin ligt de nadruk op het maken van ingewikkelde stappenplannen. Deze komen ook tijdens het college aan de orde. Het maken van nieuwe datatypes wordt behandeld in Hoofdstuk 5 en het verdelen van het programma over meerdere files in Hoofdstuk 6. Hoofdstuk 7 gaat over het programmeren van programma’s met een grafische interface. Voor het maken van de programmeeropdrachten zijn enkele richtlijnen opgesteld. Deze zijn in Hoofdstuk 8 opgetekend. In Hoofdstuk 9 staat een grote serie opgaven. Tot slot zijn in Hoofdstuk 10 enkele oude tentamens met uitwerkingen te vinden. 1
Achterin het dictaat is er in de appendices nog een kleine handleiding voor Unix te vinden. Ook staat hier een overzichtelijke lijst van voorbeeldprogramma’s die in het dictaat gebruikt worden.
Electronische hulpmiddelen Voor meer informatie over het vak kun je terecht op de volgende webpagina: http://www.liacs.nl/home/kosters/pm/ Hier zijn onder andere te vinden: • een van-week-tot-week overzicht van de colleges, inclusief de sheets; • informatie over de werkcolleges; • de programmeeropgaven van het practicum; • uitwerkingen van de opgaven uit dit dictaat; • nog meer oude tentamens, en uitwerkingen van al deze tentamens; • cijfers; • weblinks; • informatie over software (Windows, Linux, . . . ); • data (van deadlines en tentamens), boeken, . . .
Boeken Er zijn vele andere manieren om iets meer over C++ te weten te komen. In de boekwinkels liggen tientallen titels, waaronder: • W. Savitch, Absolute C++, Addison-Wesley, third edition, 2008. Prima Engelstalig boek. • L. Ammeraal, Basiscursus C++, Academic Service, 1999 (derde herziene uitgave). Goedkoop boek. • H.M. Deitel en P.J. Deitel, C++ how to program, Prentice Hall, 2008. Zeer uitgebreid en duidelijk (maar ook prijzig), met Standard Template Library en UML. • B. Kernighan en D.M. Ritchie, C Handboek, Prentice Hall – Academic Service, 1990. Uitstekend boek van de makers van C over C. Bij het vak Programmeermethoden maken we vooral gebruik van het boek van Savitch. Het dictaat is voornamelijk geschreven door Herbert Bos, Tim Cocx, Jeannette de Graaf, Walter Kosters en Siegfried Nijssen. Vragen/opmerkingen kunnen worden gestuurd naar
[email protected].
Walter Kosters, Leiden, september 2007 2
1 Computers en programmeren Dit deel van het dictaat biedt enige elementaire kennis van computers. Met deze kennis als bagage is het gemakkelijker te begrijpen waar het vak Programmeermethoden over gaat en hoe het zich verhoudt tot andere vakken.
1.1 De computer algemeen # De computer en alle erop aangesloten apparatuur is als volgt voor te stellen:
Processor
Monitor
Toetsenbord
M ui s
Snel geheugen
Randapparatuur
Langzaam Geheugen
Netwerk
Floppy/ CD/DVD
Hard Disk
Computer
Internet
Hard Disk
Server
Figuur 1: Computer overzicht Het beeldscherm en het toetsenbord, maar ook de muis, luidsprekers, enzovoort, vormen de randapparatuur van de computer. Via deze apparatuur communiceren de computer en de menselijke gebruiker met elkaar. In de computer zelf zitten verschillende onderdelen. De belangrijkste daarvan zijn de processor, het geheugen en de diskdrives. Daarnaast bevat ze nog andere onderdelen, die ervoor zorgen dat de bouwblokken van de computer met elkaar kunnen communiceren. De processor heeft de centrale rol in de computer. Deze chip, die ook wel CPU (central processing unit, ofwel: centrale rekeneenheid) genoemd wordt, verricht het echte (reken)werk. Ook zorgt deze chip ervoor dat alle andere onderdelen van de computer aangestuurd worden. Bekende voorbeelden van processoren zijn de Pentium en Celeron (van Intel), de Athlon en Duron (van AMD) en de SPARC (van SUN). Processoren verrichten rekenwerk door een stappenplan uit te voeren. Dit stappenplan is volgens bepaalde afspraken in nullen en enen opgesteld. Intel en AMD processoren houden zich aan dezelfde afspraken; beide processoren kunnen dezelfde stappenplannen uitvoeren. SUN processoren houden zich aan andere afspraken. Het is daarom niet mogelijk een stappenplan dat voor een Intel processor bedoeld is, op een SUN uit te voeren. Computers die Intel stappenplannen uit kunnen voeren, worden PC’s (Personal Computers) genoemd. 3
Omdat in het Engels een stappenplan vaak met “program” wordt aangeduid, wordt in het Nederlands een computerstappenplan meestal een programma genoemd. Dat is vanwege de lengte van het woord ook wel zo gemakkelijk. De opdrachten waaruit een programma bestaat — je kunt dan denken aan “tel a en b op” — worden instructies genoemd. Om de instructies in het programma bij te houden, zijn computers uitgerust met een (snel) geheugen (memory) waar de processor direct bij kan. De processor kan dit geheugen ook gebruiken om aantekeningen tijdens het rekenen bij te houden. Het nadeel van het snelle geheugen is dat hetgeen er in opgeslagen is slechts bewaard blijft zolang de computer aanstaat. Omdat er over het algemeen een heleboel programma’s zijn (een Internetbladerprogramma (browser), een tekstverwerker, een rekenmachine, enzovoort), en mensen daarnaast ook fors veel informatie via hun computer op willen bergen (werkstukken, muziek, films), hebben computers ook een veel groter, maar langzamer, geheugen. Dit langzame geheugen is heel divers. In de computer zelf zit meestal een harddisk. Daarnaast kun je een floppydisk, een CD/DVD of USB-stick in je computer stoppen, zodat de informatie op de floppy/CD/DVD/stick beschikbaar komt voor de processor. Als de gebruiker een programma wil gebruiken dat in het langzame geheugen is opgeslagen, wordt het programma van het langzame geheugen in het snelle geheugen gekopieerd zodat de processor daarna de instructies uit kan voeren. Een andere mogelijkheid om bij informatie te komen, is deze informatie via een netwerk van kabels (buiten de computer) uit de harddisk van een andere computer te halen. Computers waaruit je informatie kunt halen, of waarin je informatie kunt opslaan, worden servers genoemd. Sommige servers stellen hun harddisk zodanig beschikbaar aan andere computers, dat het op daarop net lijkt of de netwerkharddisk in de “locale” computer zit.
1.2 De C++ compiler # In essentie bestaat een stappenplan dat de computer uit kan voeren dus uit nullen en enen (binaire code). Om zo’n programma te maken (oftewel: om te programmeren), moet een opeenvolging van nullen en enen gecre¨eerd worden, waarbij de afspraken van de processor strikt nageleefd moeten worden. Omdat het een erg vervelende bezigheid is om dit met de hand te doen (voor elke processor opnieuw), hebben informatici gezocht naar methoden om het programmeren te vergemakkelijken. E´en van de oplossingen die ze bedacht hebben is de compiler. Een compiler is een programma dat een tekst (opgeslagen in langzaam geheugen, bijvoorbeeld een harddisk) omzet in binaire code (dat ook weer wordt opgeslagen in langzaam geheugen). Zodoende hoeft de programmeur niet te weten hoe nullen en enen gecomponeerd dienen te worden. Verder is het zo mogelijk om dezelfde tekst voor zowel een SUN als een PC onder Windows of Linux te compileren — dat levert allemaal verschillende executables op. Hoe ziet nu de tekst eruit die aan de compiler gegeven wordt? Eigenlijk is dat ook een stappenplan, alleen dan opgesteld in een andere, makkelijkere taal dan die van nullen en enen. Er zijn veel verschillende van deze talen (Pascal, Algol, Java, . . . ) waarvan C++ er e´ e´ n is. C++ is de opvolger van de taal C. Een compiler kan maar e´ e´ n taal omzetten naar binaire code (compileren). In C++ zijn echter ook de “oude” instructies uit C nog toegestaan. In het vak Programmeermethoden zullen we leren hoe een stappenplan (ofwel: programma) eruit moet zien zodat een C++-compiler die tekst kan compileren. We zagen hierboven dat het woord “programma” nogal algemeen is. Om een goed onderscheid te kunnen maken, wordt een programma dat uit nullen en enen bestaat ook wel een executable of een binary genoemd. De tekst van een programma wordt ook wel de broncode (of: sourcecode) 4
genoemd.
1.3 Operating Systemen # Door de meeste programma’s moet een grote hoeveeheid aan taken uitgevoerd worden — denk hierbij aan: zaken afdrukken op het scherm, het toetsenbord uitlezen, gegevens opslaan op de harde schijf, etc. Het lijkt om meerdere redenen niet praktisch al deze “standaard” taken mee te compileren met elk afzonderlijk programma: • alle binaries hebben dan voor een groot deel dezelfde inhoud, waardoor het geheugen snel vol komt te zitten; • ook al hebben computers dezelfde processor, vaak hebben ze niet hetzelfde toetsenbord, muis, beeldscherm, harddisk, netwerk, enzovoort. Om alle verschillende soorten apparaten aan te kunnen sturen, zou de binary heel groot moeten zijn.
Windows binary van het eigen programma
C++ code (tekst)
Linux C++ compiler voor PC
Windows OS binary
Windows C++ compiler voor PC
De voor de hand liggende oplossing waarvoor gekozen is, is de computer uit te rusten met een binary die direct bij het aanzetten van de computer in het geheugen geplaatst wordt: het Operating System (OS). Voor veel voorkomende taken kunnen programma’s dan gebruik maken van de functionaliteit die deze binary biedt. Een probleem (maar eigenlijk ook een voordeel) is dat er per processor vaak meerdere operating systems bestaan. Zo zijn er op de Snellius PC’s twee operating systemen ge¨ınstalleerd: Linux en Windows XP. Als je een programma compileert onder e´ e´ n van die operating systemen, heeft de compiler daarbij in gedachten dat het OS bepaalde functionaliteit biedt (zodat hij die bijvoorbeeld niet in de executable hoeft te stoppen). Omdat verschillende operating systems vaak andere standaard-functionaliteiten bieden is een gevolg hiervan dat een C++-binary die onder Linux gemaakt werd, niet onder Windows werkt — en andersom — (zie Figuur 2).
Linux OS binary Linux binary van het eigen programma
Figuur 2: Het operating systeem en de compiler
Een ander gevolg is dat sommige code maar op e´ e´ n van de operating systemen gecompileerd kan worden. In Windows, bijvoorbeeld, kan een programma gebruik maken van schuifbalken, knoppen en menu’s die in de operating systeem binary zitten. Niemand heeft echter deze zelfde schuifbalken, knoppen en menu’s in een Linux binary gestopt (ook al probeert men dat wel). Het is daardoor onmogelijk deze typische Windows-programma’s onder Linux te hercompileren. Dat verklaart ook waarom veel Windows-programma’s niet onder Linux bestaan, en andersom.
5
Aan de andere kant zijn er ook operating systemen die zoveel van elkaar weg hebben dat vrijwel elk programma dat op het ene OS compileert, ook op het andere compileerbaar is. Een voorbeeld hiervan is het duo Linux en SunOS, die beide tot de klasse van Unix operating systemen behoren. Op veel plaatsen in dit dictaat zullen deze operating systemen daarom samen behandeld worden. Het belangrijkste verschil ertussen is de processor waarvoor ze ontworpen zijn. E´en en ander is samengevat in Figuur 3. Processoren Intel
AMD SUN
PC Werkt op
Werkt op
Windows
Werkt op
Linux
SunOS UNIX
Operating Systemen
Figuur 3: Verhoudingen tussen de verschillends OS’s Wij zullen ons bij het vak Programmeermethoden voornamelijk toeleggen op het schrijven van programma’s die op alle computers en op alle operating systemen te compileren zijn. Het voordeel daarvan is dat het in principe mogelijk is om de opdrachten bij het vak op alle computers te maken. Het nadeel is dat je de specifieke voordelen van een operating systeem niet kunt benutten.
1.4 Andere termen # Er zijn verschillende andere termen die je bij computers vaak zult tegenkomen. Hieronder zijn deze kort nader toegelicht. Editor: een programma waarmee je een tekst zonder opmaak in kunt typen. Onder Windows is Notepad een editor, Word is geen editor. C++-code zal in een editor ingetypt worden. Terminal/Console/Shell: een programma waarin je opdrachten kunt intypen die het operating systeem direct uit moet voeren. Je kunt in dit programma bijvoorbeeld opdracht geven om een tekst van de floppy naar de (netwerk)harddisk te kopi¨eren, of om een programma te starten. Algoritme: een algoritme is een stappenplan om een bepaald probleem op te lossen. Het stappenplan hoeft nog niet in een programmeertaal uitgewerkt te zijn en kan nog Nederlandse of Engelse zinnen bevatten. Grafisch/GUI programma: een programma dat niet alleen met de gebruiker communiceert door middel van tekst en toetsenbord. Secundaire opslag (secondary storage): het langzame geheugen van de computer. 6
Account: alle onderdelen van het netwerk (delen van een harddisk, passwords, . . . ) die bij een bepaalde gebruiker horen. Linken: vaak is een programma zo groot, dat het overzichtelijker is de broncode niet in e´ e´ n bestand te stoppen. Deze onderdelen kunnen wel apart gecompileerd worden, maar moeten uiteindelijk toch aan elkaar geplakt worden in e´ e´ n binary. Dit proces van aan elkaar plakken heet linken. Veel compilers hebben standaard-binaries die aan elk programma toegevoegd dienen te worden; ook om die in een programma te stoppen moet er gelinkt worden. Dat verklaart waarom programma’s met e´ e´ n broncode-bestand vaak ook gelinkt moeten worden.
1.5 Een klein programma # Een klein C++-programma dat gebruikt zal worden als illustratie is het volgende: #include
using namespace std; int main ( ) { cout << "Dit komt op het scherm" << endl; return 0; } // main Voorbeeldprogramma 1: Dit komt op het scherm Het bovenstaand programma doet niet veel meer dan de volgende tekst op het scherm afdrukken: Dit komt op het scherm In onderstaande paragrafen is terug te vinden hoe dit kleine voorbeeld-programma (en andere, moeilijkere programma’s) op de verschillende operating systemen te cre¨eren en compileren zijn.
1.6 Windows computers In dit hoofdstuk wordt het gebruik van Windows computers om te programmeren kort toegelicht. We nemen daarbij aan dat de lezer al vaker met Windows gewerkt heeft. We gaan verder niet in op het onderscheid tussen de verschillende Windows varianten. Op de wiskundecomputers van het Snellius is overigens geen Windows versie aanwezig. 1.6.1
Inloggen en bladeren #
Zorg er eerst voor dat de PC het Windows OS gestart heeft. Mocht de PC op Linux staan, herstart de PC dan via shutdown⇒restart, en kies voor Windows. Om in te loggen onder Windows moeten de gebruikersnaam en het Windows password (oftewel wachtwoord) worden ingetypt. Het Windows password is een ander password dan het Unix password. Druk pas op ENTER nadat zowel de gebruikersnaam als het wachtwoord is ingevuld. Met TAB kun je van het ene invoerveld naar het andere gaan. Met de Windows Explorer (te vinden in het startmenu) is het mogelijk rond te bladeren op het systeem. Aan de linkerkant van de explorer staan de verschillende stations (diskdrives, 7
cdrom, . . . ) aangegeven waarover de computer de beschikking heeft. E´en van de stations heet Z:\. Dit is een onderdeel van een netwerkharddisk. Deze Z:\ is via elke Windows computer in het gebouw te benaderen. Bestanden die op locale harde schijven zijn opgeslagen, kunnen alleen achter de desbetreffende computer bekeken worden. Het valt aan te raden de harde schijven te gebruiken bij het compileren van de programma’s (vanwege de grote tijdelijke bestanden die gemaakt worden tijdens het compileerproces) en na het werken de benodigde bestanden (alleen de .h en de .cpp bestanden zijn echt noodzakelijk) op Z:\ op te slaan voor later gebruik. 1.6.2
Programmeren
Voor het schrijven van C++-programma’s onder Windows is op de universitaire computers Microsoft Visual C++ 6.0 ge¨ınstalleerd. In Visual C++ zijn de editor en de compiler gecombineerd. Ook is Dev-C++ ge¨ınstalleerd (zie verderop). Ga in het startmenu naar Programs⇒Microsoft Visual C++ 6.0⇒Microsoft Visual C++ 6.0 toe om Visual C++ te starten. Sluit de “Tip of the Day”. We gaan eerst de broncode intypen. Selecteer daartoe File⇒New en dan bij Files (dat is een tabblad, bovenaan): C++ Source File. Geef de filenaam op (deze maakt nu niet zoveel uit, maar laten we kiezen voor eerste), de harde schijf waar het bestand wordt opgeslagen en klik op OK. Het nieuwe bestand wordt nu opgeslagen eindigend op .cpp, zodat Visual Studio het herkent als een C++ bestand. Typ in het venster dat verschijnt het voorbeeld-programma uit Hoofdstuk 1.5. Om het bestand te compileren, dient in het Build menu de optie Compile gekozen te worden. Visual C++ vraagt om een bijbehorend project te openen. Door op OK/Yes te klikken wordt dit automatisch gedaan. Vervolgens wordt de broncode gecompileerd; onderin het scherm verschijnen waarschuwingen en foutmeldingen bij dat compileren. Door op de foutmelding te dubbel-klikken kan de cursor verplaatst worden naar de plaats in de broncode waar zich een fout voordeed. Op deze manier kunnen hopelijk alle C++-fouten verbeterd worden. Vervolgens dient het programma gelinkt te worden (zelfs als het, zoals hier, slechts uit e´ e´ n bestand bestaat, zie Hoofdstuk 1.4). Doe dit door op Build⇒Build te klikken. Tenslotte kan het programma gestart worden door Build⇒Execute te selecteren. Nu alle compileer- en build-stappen eenmaal zijn uitgevoerd zullen in het vervolg alle voorgaande stappen indien nodig herhaald worden wanneer er op het rode uitroepteken (Execute) geklikt wordt. Klik daar nu op. Op het beeldscherm verschijnt dan (zoals verwacht) in een zwart venster: Dit komt op het scherm Je kunt nu beginnen met het schrijven van grotere programma’s. Gefeliciteerd! Denk eraan de bestanden naar Z:\ te kopi¨eren als je het voor later wilt bewaren. Als je in een later stadium een bestaand programma weer verder wilt bewerken, en je alle bestanden bewaard hebt kun je het beste het “project” ophalen. In bovenstaande situatie zou dat project eerste.dsw heten, en is het op te halen via File⇒Open Workspace. 1.6.3
Thuis in C++ programmeren met Windows
Om thuis C++-programma’s onder Windows te kunnen schrijven, zijn er een heleboel verschillende mogelijkheden. Hieronder staan er enkele op een rijtje. MicroSoft Visual C++: Dit programma wordt in nieuwere versies tegenwoordig ondergebracht in .net. Een demo-versie van (de ook goede) versie 6.0 zit soms bij het boek van Savitch. Dev-C++: Dit programma is kosteloos te downloaden van 8
www.bloodshed.net Net zoals bij Visual C++ zijn de compiler en editor bij Dev-C++ ge¨ıntegreerd. Het mist echter enkele opties voor het schrijven van grafische programma’s. De werking lijkt op die van Visual C++. Kies aan het begin Bestand⇒Nieuw⇒Broncode, type weer dezelfde C++-tekst in als boven, en compileer en executeer het programma. Als het executeerbare programma voorbij flitst (er is immers geen interactie met de gebruiker), voeg dan een programmaregel int i; cin >> i; voor de return 0; toe. Er wordt dan gewacht op een getal dat de gebruiker moet invoeren (en met Enter moet afsluiten). Borland C++ Builder: De Universiteit Leiden heeft voor deze ge¨ıntegreerde compiler en editor een zogeheten campuslicentie. Tegen een gereduceerd tarief is het pakket aldaar te verkrijgen. Zie: www.surfspot.nl Borland C++ Compiler: De compiler van Borland is kosteloos te downloaden van www.borland.com Dit pakket bevat alleen een compiler (en dus geen editor). Daarnaast is enige functionaliteit van de C++ Builder, zoals het gebruik van de Windows user interface, afwezig. Een editor zoals Notepad moet gebruikt worden om broncode in te typen.
1.7 Unix computers In het Snellius is op de meeste PC’s Linux aanwezig. Sommige PC’s kunnen zowel onder Windows als onder Linux draaien. 1.7.1
Beginnen op de Linux PC’s #
Zorg er eerst voor dat de PC het Linux OS gestart heeft. Als de PC op Windows staat, geeft deze PC meestal de boodschap “Press CTRL+ALT+DELETE to log on”. Om naar Linux te gaan, moet eerst het drietal toetsen CTRL+ALT+DELETE tegelijk ingedrukt worden en daarna Shutdown⇒Shutdown and Restart gekozen worden. De computer start dan opnieuw op en Linux kan gekozen worden. Als Linux opgestart is, is het eerst noodzakelijk zich aan het systeem bekend te maken. Doe dit door de username en het password in te typen die het systeembeheer gegeven heeft. Ga met TAB of de muis van het ene invoerveld naar het andere. Let erop dat bij sessiontype “KDE” staat; er wordt dan gekozen voor KDE, de K Desktop Environment, een windows-omgeving bovenop Linux. Druk daarna op Go! Op de systemen van Wiskunde wordt meestal (automatisch) voor “Gnome” gekozen. Het beeldscherm dat dan verschijnt, kan er op een heleboel verschillende manieren uitzien (dat is onder andere afhankelijk van het hierboven gekozen session type). E´en mogelijkheid is dat de onderkant van het scherm er uitziet als Figuur 4. De getoonde icoontjes kunnen er (net) ietsje anders uitzien of op een andere plaats staan; je kunt zelf eenvoudig de vormgeving wijzigen. De programma’s zijn te starten door op het bijbehorende icoontje te klikken. Probeer eerst een Internet browser te gebruiken. De werking van 9
Terminal Konqueror (Internet browser)
Uitloggen
Figuur 4: Linux KDE balk
de programma’s is ongeveer gelijk aan die van bekende Windows programma’s. Vraag om hulp indien zich problemen voordoen. Het belangrijkst is te ontdekken hoe de terminal (shell, konsole) opgestart wordt. Meestal is daar wel een aparte icoon voor, met een schelp of een beeldscherm. In de rest van het dictaat zullen we de terminal vaak gebruiken om aan te geven hoe je een programma start. 1.7.2
De Unix terminal, programma’s starten en bestandsbeheer
In deze paragraaf zullen we kort het gebruik toelichten van de “Unix terminal”. In Hoofdstuk 2 is een uitgebreid overzicht te vinden van diverse commando’s die in de Unix terminal gebruikt kunnen worden. De Unix terminal wordt overigens ook wel eens “xterm” genoemd. In feite is het gewoon een window waarin je Unix-opdrachten kunt geven. Wachtwoord wijzigen Na de eerste keer ingelogd te zijn met het password van het systeembeheer, is het belangrijk het password te veranderen. Dit kan door het volgende commando in te typen (alle commando’s worden gevolgd door ENTER; de “yp” komt van “yellow pages”): yppasswd Je nieuwe password moet hoofd- en kleine letters, en rare tekens, door elkaar bevatten: geen namen, woorden, gironummers, . . . , maar bijvoorbeeld beginletters van een zinnetje met cijfers, & en * ertussen. Bestandsbeheer Op de Unix systemen start de terminal altijd in jouw eigen homedir Dit is het beginpunt van je bestandssysteem Om de homedir te bekijken kan het commando ls ingetypt worden. Of, voor iets meer bestandsinformatie: ls -l (achter de min staat de kleine letter l). Net als bij de Windows systemen heeft ook een Unix systeem een directory structuur om bestanden te organiseren. Om van directory te wisselen gebruik je cd directory waarbij directory als volgt voorgesteld kan worden:
10
.. ~ naam
Ga een directory “hoger” Ga naar je homedir (“tilde”) Ga naar directory naam
Overigens staan de slashes in bestands- en directorynamen net andersom dan in Windows: / in plaats van \. Om een nieuwe directory te maken gebruik je mkdir: mkdir naam Als je e´ e´ n van de bestanden wil verwijderen dan kan dat met rm: rm naam Als je e´ e´ n van de bestanden wil verplaatsen dan kan mv gebruikt worden: mv oudenaam nieuwenaam Als je opnieuw ls uitvoert, heeft het oude bestand nu een nieuwe naam en is identiek aan het origineel van daarnet. Als je bij nieuwe naam ook een nieuwe directory invoert zal het bestand ook van directory veranderen. Als je van e´ e´ n van deze bestanden een kopie wilt maken, kan cp gebruikt worden: cp oudenaam nieuwenaam Als je opnieuw ls uitvoert, staat er nu een nieuw bestand met een nieuwe naam dat identiek is aan het origineel van daarnet. Om een bestand naar een floppydisk te kopi¨eren (bij PC’s) kan cp oudenaam /floppy gebruikt worden. Er wordt dan een kopie met dezelfde bestandsnaam op de floppydisk gezet. Grafische programma’s starten vanaf de terminal Bij het starten van grafische programma’s — tekstverwerking, webbrowser — vanaf de terminal is het noodzakelijk om de opdracht die het programma start te laten volgen door een &. Op die manier kan de terminal gebruikt blijven worden voor het uitvoeren van andere opdrachten. Surfen op Internet Om de Firefox webbrowser te starten kan (behalve door te klikken op het desbetreffende icoontje) ook het volgende commando worden ingetypt: firefox & Een simpele tekst editor Om een tekstbestand aan te maken kan de editor NEdit gebruikt worden — er zijn trouwens nog vele andere editors. NEdit wordt gestart door het volgende commando in te typen: nedit & Om een bestand met betekenisvolle kleurtjes weer te geven, kan in het Preferences menu de optie Highlight Syntax aangezet worden. Om elk bestand altijd met kleurtjes weer te geven, moet de juiste optie in het Preferences⇒Default Settings menu aangezet worden en vervolgens Save Defaults gekozen worden. Om voor elke regel een regelnummer af te beelden, kan in het Preferences menu de optie Show Line Numbers aangezet worden. Typ bij wijze van proef een kleine tekst in het venster, en schrijf deze weg door naar File⇒Save As. . . te gaan. Typ achter /home/iemand/ (iemand is jouw gebruikersnaam) een bestandsnaam zonder spaties in en klik op OK. Het bestand wordt hiermee ergens op jouw account opgeslagen (in je homedir). 11
1.7.3
Programmeren
Open NEdit en voer het programma van Hoofdstuk 1.5 in. Bewaar deze code onder de naam eerste.cc (het is onder Unix gebruikelijk C++-bestanden een naam te geven die op .cc eindigt). Typ daarna het volgende commando in: g++ -Wall -o eerste eerste.cc De compiler (g++) wordt hiermee gestart. Achteraan het lijstje staat het bestand dat je wil gebruiken als bron voor het nieuw te maken programma. Na de optie -o staat de naam die het nieuwe programma moet krijgen (dit hoeft niet hetzelfde te zijn als de naam van het bronbestand!). Met (-Wall) geven we aan dat we alle waarschuwingen over C++-fouten te zien willen krijgen. Als het voorbeeldbestand goed ingetypt en weggeschreven is, zegt de compiler niets en kun je vervolgens het nieuwe programma starten. Typ als commando: ./eerste Op het beeldscherm verschijnt dan (zoals verwacht): Dit komt op het scherm Dit betekent dat de C++-code goed was, gecompileerd kon worden en dat de processor het simpele programma uit kon voeren. Gefeliciteerd! 1.7.4
Thuis in C++ programmeren met Linux *
Het is goedkoop en “eenvoudig” om Linux op je PC thuis te gebruiken. Wellicht de eenvoudigste methode is om gebruik te maken van “(K)Ubuntu”. Dit zijn versies van Linux die je vanaf CD of DVD kunt starten (een “live CD”); je hoeft het niet meteen op je computer te installeren. Je kunt de CD eenvoudig van het web halen: http://www.kubuntu.org/. Denk er aan een “image” op te halen. Stop de CD in je computer, en zorg ervoor dat deze vanaf CD kan opstarten. Je komt dan vanzelf in KDE terecht. Ietsje ingrijpender is het om Linux thuis op je PC te installeren. Je zult dan namelijk de harddisk in je computer moeten partitioneren: de harddisk moet zodanig worden ingedeeld dat een vast deel ervan door Linux gebruikt kan worden. Vanuit Windows kun je dat deel van je harddisk echter niet meer gebruiken. Het is daarom aan te raden eerst vertrouwd met Unix te raken. Raadpleeg http://www.linux.org/, of een van de talloze andere websites, of vriendjes. Er zijn verschillende fabrikanten of groepen mensen die een versie van Linux in elkaar zetten. E´en zo’n versie wordt een distributie genoemd, en elke distributie is afgestemd op een bepaalde gebruikersgroep. Een degelijke, maar ook zeer technische, distributie is Debian GNU/Linux: goedkoop, in feite zelfs gratis, en eenvoudig te verkrijgen. Minder technisch (maar daarom ook minder geliefd bij sommige computeraars) zijn Mandriva (voorheen Mandrake), SUSE en RedHat/Fedora. Ook deze zijn min of meer gratis van het Internet te halen, maar handiger is soms de aanschaf van een paar goedkope CD’s of een DVD. Voor extra informatie over Linux zijn de boeken van uitgeverij O’Reilly, zoals “Linux in a nutshell” (ook in het Nederlands), meestal hun geld meer dan waard. Bij de meeste distributies wordt software meegeleverd om de harddisk te partitioneren; soms is echter nog een afzonderlijk programma nodig om harde schijven anders te partitioneren.
12
1.8 Mailen Voor het versturen van mailtjes (en het inleveren van de opdrachten) onder beide operating systemen adviseren we je om gebruik te maken van de webmail service die te vinden is op https://mailserver.liacs.nl Let op de s achter http. Je zult enkele keren op Yes of OK moeten klikken voordat je de inlogpagina van de webmail service te zien krijgt. Voor de webmail service dien je hetzelfde password te gebruiken als voor het inloggen onder UNIX. Je UNIX inlognaam, gevolgd door @liacs.nl is tevens je e-mail adres. Natuurlijk kan je ook je eigen webmail service (hotmail of gmail) gebruiken om de programma’s op te sturen. Sommige providers staan op een zwarte lijst, waardoor je email geweigerd wordt en teruggestuurd; probeer het dan nog eens vanaf een ander mail-adres.
13
2 Werken met Unix 2.1 Unix commando’s * Hier wordt meer uitgebreid uitgelegd hoe Unix (terminal)commando’s er uitzien en wat ze doen. Er wordt slechts een heel klein, maar wel nuttig gedeelte van dit gigantische syteem behandeld. 2.1.1
Syntax van een commando
Een commando bestaat uit een of meer woorden, gescheiden door spaties. Een woord is een string zonder spaties. Het eerste woord van een commando is de naam, de rest zijn parameters en argumenten. Bijvoorbeeld: lpr -Php-146-bw rommel.txt Hier is lpr de naam van het commando (output naar een printer), -P is een parameter (om de naam van de gewenste printer aan te geven), “hp-146-bw” is het argument van “P”, terwijl “rommel.txt” het argument van het commando is om de naam van de te printen file mee aan te geven. Parameters zoals P die voorafgegaan worden door een “-” heten “switches” en bieden de mogelijkheid te kiezen tussen de verschillende opties van het commando. In dit speciale geval: als de switch afwezig is, wordt de file geprint op de “default” printer — en die is in principe voor iedereen anders. Als dat toevallig een matrix-printer is, en de file is een PostScript-file, haal je je overigens een hoop narigheid op de hals. In het vervolg worden parameters of argumenten die niet verplicht zijn tussen vierkante haakjes gezet, met “[...]”; als er een waarde voor het een of ander gespecificeerd moet worden, wordt dit genoteerd met “” (de < en > niet intikken!). 2.1.2
Procesbeheer
Met Unix kun je allerlei processen (programma’s) tegelijkertijd draaien. Zo draait er altijd al een fors aantal processen zonder dat je daar erg in hebt, dit om de computer zijn werk te laten doen: een klokje op het scherm te zetten, een CD te lezen, naar email te kijken, enzovoorts. Soms geeft een commando een eigen window waarin het programma zich verder ontwikkelt, soms niet. De volgende commando’s zijn in staat op allerlei manieren processen te manipuleren: CTRL -c CTRL -z
ps eaf
kill kill -HUP exit of logout yppasswd
stopt een lopend proces interrumpeert een lopend proces, dat later weer verder kan gaan; het proces blijft bestaan geeft overzicht van lopende processen; ps -u Clinton doet dit voor gebruiker Clinton; op sommige systemen ps aux of ps -eaf gooit proces met process-id PID uit de lijst met processen gooit iets netter proces met process-id PID uit de lijst met processen (via een “hangup-signaal”) verlaat een shell of command window; ook: CTRL -d verander je eigen password
14
En wat meer gevorderde commando’s: bg
fg jobs top & CTRL -s CTRL -q
stuurt een proces gestopt met CTRL -z naar de achtergrond, dat wil zeggen: ga er mee door zonder op stoppen te wachten haalt het huidig lopende proces van achtergrond naar voorgrond laat de huidige achtergrond-processen zien laat de processen actief op de machine zien, ook processen van andere gebruikers start een commando op de achtergrond, dat wil zeggen zonder op stoppen te wachten stopt output naar het scherm gaat verder met uitvoer naar het scherm
Een voorbeeld. Stel je wilt een (misschien nieuwe) file nieuw.cc editen met het programma Nedit. Je tikt in nedit nieuw.cc, gevolgd door een druk op de Enter-toets Je kunt dan in een nieuw window aan het editen slaan, maar stel dat je in het oorspronkelijk window weer wat wilt doen. Dat kan nu helaas niet, want de controle is helemaal overgegeven aan het nedit-proces. Dat kun je tijdelijk staken door CTRL -z in het oorspronkelijke window te geven (het proces wordt dan gesuspend; nu kun je voorlopig niet meer editen), en als je verder wilt met editen: bg. Het was eenvoudiger geweest om meteen aan het begin nedit nieuw.cc & te geven, waardoor je in het oorspronkelijke window gewoon door kunt werken. Overigens zijn er ook programma’s die zelf die & er als het ware bijdoen: gvim nieuw.cc edit, met de editor gvim, de file nieuw.cc — een & is overbodig. 2.1.3
Files
Unix heeft een boomstructuur met als bladeren de files, en als (interne) knopen de directories — ook wel mappen genoemd. Elke directory kan andere directories en files bevatten. Aan de wortel staat altijd “/”. De directory waarin je meteen na het inloggen terecht komt, heet je “homedirectory”, doorgaans met een ~ aangegeven (dit is trouwens hetzelfde als /home/iemand als je iemand bent). Alle files en directories die je zelf maakt horen hieronder te zitten. Elke file wordt gekarakteriseerd door: 1. het pad er naar toe (bijvoorbeeld /home/clinton/geheim/ ) 2. de filenaam (bijvoorbeeld dagboek.txt ) 3. de eigenschappen (properties): eigenaar, grootte, toegangsrechten, soort en dergelijke Om naar een file te verwijzen moet je of de volledige naam geven (waarbij zeer lange namen, eventueel met punten erin, kunnen voorkomen — en let er ook op dat kleine letters en hoofdletters verschil maken!): /home/clinton/geheim/dagboek.txt of — doorgaans eenvoudiger — de plaats met betrekking tot de huidige “working directory” (cwd) (geen / in het begin!): geheim/dagboek.txt als je op dit moment in directory /home/clinton zit.
15
Afkortingen voor directories en files: . .. ~ ∗ ?
huidige working directory (cwd) ouder-directory van cwd je eigen home-directory (een “tilde”) staat voor elke serie karakters in een filenaam (bijvoorbeeld rm ∗.c gooit alle files die eindigen op .c weg uit de cwd) staat voor precies e´ e´ n karakters in een filenaam (bijvoorbeeld lpr data? print alle files waarvan de naam begint met data, en waar nog e´ e´ n karakter achter komt)
En commando’s om files en directories te manipuleren: cat less lpr rm cp ls [-al] []
pwd cd [] mkdir mv
rmdir chmod [auog][+-][rwx]
wc grep [<patroon>] []
output file(s) op beeldscherm (zie ook “redirection” van output) eenvoudige output van file(s), pagina voor pagina output naar een printer verwijder file(s) — oppassen! kopieer file1 naar file2 laat informatie zien over de inhoud van een directory; -a laat ook “setup” files zien (“dot files”), zoals .login; -l laat meer informatie zie (eigenaar, datum, grootte, . . . ) laat huidige working directory (cwd) zien, doorgaans ook in de prompt genoemd verander cwd in directory (cd zonder directory maakt home-directory de cwd) maakt binnen cwd een nieuwe directory aan geheten directory als nieuwenaam een bestaande directory is, wordt oudenaam naar deze directory verplaatst; hernoem anders oudenaam in nieuwenaam verwijder (lege) directory/ies wijzig de rechten van file(s), waarbij de eerste parameter vertelt om wie het gaat (a=all, u=user, g=group, o=others), de tweede parameter of toegang wordt verstrekt (+) of afgenomen (-), en de derde welke toegangsvorm wordt gewijzigd (r=read, w=write, x=execute). Oude stijl: chmod 644 * of chmod 750 * telt aantal regels, woorden en bytes van file(s) doorzoekt file(s) op patroon, dat een (wellicht kryptisch) reguliere expressie zoals ’[kK][a-zA-Z]*[sS]’ kan zijn 16
Een voorbeeld: gebruik rm core om zogeheten core-dumps weg te gooien (grote files in noodgevallen door het systeem gemaakt); gebruik cd .. (en niet cd..) om naar de ouder-directory van de cwd te gaan. 2.1.4
Input/Output
Veel Unix-commando’s maken gebruik van de drie standaard devices, te weten: standard-input, standard-output en standard-error-output, die normaal gekoppeld zijn aan toetsenbord (de eerste) en beeldscherm (de tweede en de derde). Ze kunnen ook eenvoudig worden ge-“redirect” naar files (de middelste >, >> en < wel intikken): > >> < 2.1.5
redirect output van commando naar file file append (hang) output van commando achter file file haal input voor commando uit file file
Pipelining
Een zeer nuttige eigenschap van Unix is de mogelijkheid tot “pipelining”. Dat is de uitvoering, achter elkaar, van verscheidene commando’s, waarbij de output van ieder commando dient als invoer voor het volgende. Het pipelining symbool is ‘|’. Enkele voorbeelden: ps -uGore | grep 15 retourneert (onder meer) informatie over alle processen van Gore, gestart tussen 3:00 pm en 3:59 pm en de processen met 15 in hun processid. Het grep-commando grijpt namelijk alle regels waar 15 in voorkomt uit de lijst met processen van Gore. find . -name ’*.cc’ | xargs grep -i "Bush" zoekt in de huidige directory en daaronder naar files met extensie .cc, selecteert daaruit die files die de string Bush bevatten, niet lettend op het verschil tussen kleine letters en hoofdletters, en zet de betreffende regels met filenaam erbij op het scherm. 2.1.6
Geschiedenis
De shell heeft een mechanisme dat gegeven commando’s bijhoudt. Als je history als commando geeft (h werkt vaak ook) krijg je een genummerde lijst met de laatste commando’s. Met behulp van ‘!’ kun je oude commando’s of gedeeltes daarvan gebruiken in je volgende commando. Als voorbeeld: !c wordt het laatste commando dat begon met een c. Gebruik de pijltjes-toetsen om vorige commando’s te krijgen en de TAB-toets om je commando’s af te maken. Bijvoorbeeld, als je de TAB-toets gebruikt na rm fil — voor de Enter-toets te gebruiken — krijg je een lijst van alle filenamen die beginnen met fil (als zulke files bestaan); dit werkt ook met begingedeeltes van commando’s. Doorgaans worden beginstukken aangevuld tot het systeem verschillende vervolgmogelijkheden ziet.
2.2 De editor vi in een notedop * Het programma vi, de “visual editor”, is een zeer krachtige editor die op elk Unix-systeem aanwezig is (soms overigens ook vim geheten). Het is een alternatief voor het simpelere nedit. Voor liefhebbers van grafische user interfaces is er ook een grafische variant, gvim, beschikbaar. 17
Sommige mensen vinden het lastig om met vi te werken, maar eigenlijk is het heel simpel. Het enige waar je op moet letten is dat er een command-mode is en een input-mode. In de command-mode (de naam zegt het al) wordt alles wat je intikt opgevat als een commando. In de input-mode wordt alles opgevat als tekst. Als je vi aanroept met vi kom je in de command-mode. Met de volgende commando’s kom je in de input-mode: i voeg tekst toe voor het huidige character A voeg tekst toe achter de huidige regel Met de ESC-toets verlaat je weer de input-mode en kom je terug in de command-mode. Er zijn een aantal manieren om vi te verlaten. De belangrijkste zijn: ZZ verlaat vi en save de file :q! verlaat vi zonder de file te saven (noodsprong) De cursor kan doorgaans worden verplaatst met behulp van de pijltjes op het toetsenbord, of — altijd — met de letters h, j, k en l in command-mode. Tekst verwijderen gebeurt met de volgende commando’s: x delete het huidige character dd delete de huidige regel Het kopi¨eren van stukken tekst kan op de volgende manier: • ga met de cursor naar de beginregel van de te kopi¨eren tekst; • geef het aantal regels dat je wilt kopi¨eren; • “yank” die regels met behulp van het commando Y; • ga vervolgens naar de regel waar je de tekst wilt toevoegen; • geef het commando p (put). Het vlot doorlopen van je tekst doe je — behalve met Page Up en Down — met de volgende commando’s: CTRL -f CTRL -b
:27
ga naar de volgende pagina ga naar de vorige pagina ga naar regelnummer 27
Uiteraard heeft vi nog veel meer commando’s, bijvoorbeeld voor het zoeken naar strings; soms werkt ook de backspace-toets. Nog een voorbeeld: een punt in command-mode herhaalt het laatste commando. Als je in command-mode een : intikt zit je overigens in ex-mode. Je kunt meer informatie vinden in de systeem-documentatie. Als je gvim gebruikt, is het handig om een file .gvimrc (let op de punt aan het begin) in je eigen home-directory te zetten met daarin je eigen standaardinstellingen.
18
2.3 Mailen met elm/mutt * Alhoewel elke variant van Unix wel een grafisch mailprogramma heeft, zien deze er allemaal anders uit. Er is echter een mailprogramma dat op alle Unix computers aanwezig is: elm (van “electronic mail”); elm kan opgestart worden door het commando elm in te typen en de vragen daarna met ‘y’ te beantwoorden. Onderaan het scherm staan de e´ e´ n-letterige commando’s die aan elm gegeven kunnen worden. Met ‘m’ kan een mailtje opgesteld worden. Onder Linux roept elm hiervoor standaard vi aan. Zodra de editor afgesloten wordt, kan het mailtje verstuurd worden. Het programma mutt is een modernere sterk verbeterde versie. In de home-directory van je UNIX-account kun je overigens een file .forward (let op de punt aan het begin) zetten waarin je een emailadres kunt deponeren. Alle email naar je UNIX-account wordt dan automatisch onveranderd doorgestuurd naar dat adres.
2.4 Slotopmerkingen * Dit overzicht is bij lange na niet compleet. Maar er staat voldoende in om voorlopig aardig uit de voeten te kunnen. Het is een goed idee om je eigen file .tcshrc (als je tenminste tcsh als shell gebruikt, anders misschien .bashrc; let op de punt aan het begin van de filenaam: het betreft een zogeheten “dotfile”) in je home-diectory eens te bekijken. Deze file bevat persoonlijke informatie en wordt bij het opstarten van het systeem uitgevoerd. De file kan door de gebruiker zelf aangepast worden, bijvoorbeeld door eigen “aliases” (afkortingen) voor veelgebruikte commando’s toe te voegen, of het zoekpad te wijzigen (zo zit vaak de huidige directory niet in dit pad, vandaar dat je ./eerste moet zeggen om de executable eerste uit ., de huidige directory, uit te voeren). Veel Unix-programma’s hebben zogeheten “resource-configuration” (rc) files voor persoonlijke instellingen. Meer informatie over Unix-commando’s kan worden gevonden via de online handleidingen. Type man om dit te bekijken, bijvoorbeeld man ls. Als je de naam van een commando niet (meer) weet kun je proberen man -k <woord> in te tikken: er verschijnt dan een lijst met commando’s die iets met “woord” te maken hebben, bijvoorbeeld: man -k process of man -k debug. Niet alle commando’s zijn gedocumenteerd met man; het GNU project (de makers van gcc/g++) gebruikt bijvoorbeeld TeXinfo. Probeer ook maar eens man ddd om informatie te krijgen over de fraaie Data Display Debugger DDD, die op diverse systemen beschikbaar is. Een ander probleem is het volgende. Stel dat je wilt weten hoeveel tijd je C++-programma doorbrengt in zijn verschillende functies. Je bent dan op zoek naar een “profiler”. Op sommige systemen bestaat gprof. Compileer eerst je programma, zeg eerste.cc, met g++ -o eerste eerste.cc -pg run daarna ./eerste, en laat dan gprof zijn werk doen: gprof eerste gmon.out > eerste.prof De file eerste.prof bevat nu interessante informatie. In de Unix-wereld worden regelovergangen met e´ e´ n symbool, de LF oftewel LineFeed (karakter 10) verzorgd. In de Windows-wereld zijn dat er twee: een CR oftewel CarriageReturn (karakter 13), e` n een LF. Sommige editors hebben hier problemen mee. Onder Linux kun je het ene formaat in het andere omzetten met dos2unix en unix2dos. En hoe kun je files “zippen”, en meerdere files tegelijk per email versturen? Gebruik 19
tar cvfz naam.tgz *cc plus.txt om een gezipt “archief” naam.tgz te maken dat alle files waarvan de naam eindigt op cc en de file plus.txt uit de huidige directory. Het archief kan worden uitgepakt (“extracten”) met tar xvfz naam.tgz. En waar komen al deze programma’s vandaan? Probeer which, bijvoorbeeld which g++. Of waar is time.h? Gebruik locate, bijvoorbeeld locate time.h. Het is heel eenvoudig om vanuit huis op het Unix-systeem in te loggen. Gebruik daar het kleine Windows-programma putty voor, gratis op te halen bij http://www.chiark.greenend.org.uk/~sgtatham/putty/ Je moet dan “ssh-en” (ssh staat voor “secure shell”) naar ssh.liacs.nl. En als je files heen en/of weer wilt transporteren, begruik dan het aldaar ook te verkrijgen ftp-programma psftp. Het World Wide Web (WWW) bevat allerlei on line informatie. Zoeken met de bekende zoekmachine www.google.com levert al heel wat op, of speur naar files met Frequently Asked Questions, de zogeheten FAQs. Een goede Unix-introductie is beschikbaar als http://www.liacs.nl/home/kosters/unixfour.ps Voordat je de printer aanzet: dit is een PostScript file, en die wordt niet door iedere printer goed afgehandeld! En misschien ben je geinteresseerd in het produceren van prachtig vormgegeven output: op zoek naar TEX of LATEX? Probeer http://www.liacs.nl/home/kosters/stuva1/lshort.pdf Of wil je meer weten van reguliere expressies en Perl . . . zoek dan zelf bij http://www.google.com/
20
3 C++: Concepten en programmeervoorbeelden In dit gedeelte komen de C++-concepten aan bod die bij het vak Programmeermethoden belangrijk zijn en behandeld worden. Ze worden ge¨ıllustreerd met korte, duidelijke voorbeeldprogramma’s. Voorin is een lijst te vinden met alle in het dictaat aanwezige voorbeeldprogramma’s (zie de inhoudsopgave).
3.1 Bibliotheken Een groot deel van de C++ functionaliteit is opgeslagen in zogeheten bibliotheken. Deze bibliotheken bevatten een collectie standaard instructies op een bepaald gebied. In bijna ieder programma gebruiken we bijvoorbeeld de bibliotheek iostream, die we als volgt in het programma opnemen: #include In het oude C was dit nog: #include Maar in C++ laten we de lijst van standaard-bibliotheken volgen door: using namespace std De iostream bibliotheek bevat instructies op het gebied van de in- en uitvoer. Een veel gebruikt voorbeeld hiervan, cout, vonden we al terug in het eerste programma. Hier wordt iets mee op het scherm afgedrukt. Zonder het gebruik van de iostream bibliotheek zou deze opdracht niet “herkend” worden door C++ (de compiler eigenlijk).
3.2 Commentaar Het is mogelijk e´ n gebruikelijk C++ programma’s te voorzien van stukken tekst die in het programma zelf niets doen, maar commentaar zijn voor de menselijke lezer — de programmeur zelf of anderen. Commentaar ziet er als volgt uit: // Deze tekst wordt niet "uitgevoerd" Het kan overal aan het einde van een regel toegevoegd worden. Commentaar over meerdere regels of zelfs tussen opdrachten is ook een mogelijkheid en ziet er zo uit: /*Ook deze twee regels aan commentaar bij het programma worden niet uitgevoerd*/ Voor het gebruik van commentaar in de programma’s, zoals die voor het vak Programmeermethoden gemaakt moeten worden, zijn richtlijnen opgesteld.
21
3.3 Variabelen Aan de basis van de meeste programmeertalen staat het concept: variabele. Een variabele is in feite een klein stukje in het (snelle) geheugen dat gereserveerd wordt voor het opslaan van een bepaald type data. In C++ is het verplicht dit stukje geheugen eerst te reserveren voor een bepaald type, het zogenaamde “declareren van een variabale”. Dit gaat bijvoorbeeld als volgt: int zakgeld; Hiermee reserveren we een stuk geheugen voor het opslaan van een geheel getal (int). Na de declaratie kunnen we allerlei operaties uitvoeren op de variabele zakgeld, bijvoorbeeld: zakgeld = 300; // erg lief kind Waarmee we het getal 300 opslaan op de geheugenlocatie van zakgeld. Er zijn een heleboel verschillende typen mogelijk, die soms goed en soms minder goed uitwisselbaar zijn. Bij het vak Programmeermethoden zijn dit de belangrijkste: int double char bool
Een geheel getal Een (benadering van een) re¨eel getal Een karakter Waar of onwaar
Later volgt meer informatie over het werken met de verschillende typen variabelen.
3.4 Condities Een van de belangrijkste mogelijkheden in een programma is het uitvoeren van verschillende stukken code afhankelijk van een bepaalde conditie. Denk hierbij bijvoorbeeld aan: Als x groter is dan 0 dan is x positief, anders is x 0 of negatief. Bovenstaande conditie zou er in C++ bijvoorbeeld zo uit kunnen zien: if ( x > 0 ) { cout << "x is positief" << endl; } // if else { cout << "x is 0 of negatief" << endl; } // else Indien er meer dan een “eis” wordt gesteld dan wordt dat zo gedaan: if ( ( x > 0 ) && ( x < 25 ) ) Meervoudige condities als 0.0 <= x <= 1.0 worden in C++niet op die manier geformuleerd. if ( 0.0 <= x <= 1.0 ) betekent namelijk iets anders. De genoemde conditie wordt dan ook als if ( 0.0 <= x && x <= 1.0 ) in de C++-code opgenomen. Iets dergelijks geldt ook voor if ( x and y > 0 ), waarschijnlijk wordt in dit geval if ( x > 0 and y > 0 ) bedoeld. Merk tevens op dat bij de regel met && de tweede test niet meer gedaan wordt als de eerste al uitsluitsel geeft. Een constructie als if ( ( x != 0 ) && ( 1.0 / x == 0.5 ) ) is dus toegestaan. Dit fenomeen heet shortcircuiting; ook hoor je hier wel eens de term lazy 22
evaluation vallen. In de nieuwste C++-versies mag overigens in plaats van && weer and gebruikt worden, en analoog or voor || en not voor !. Laten we nu eens kijken naar een compleet voorbeeld-programma waar in de tot nu toe besproken concepten naar voren komen. De eerste regel van dit programma bevat commentaar voor // Dit is een regel met commentaar ... #include // moet er ieder C++-programma bij using namespace std; const double pie = 3.14159; // een constante (beter uit cmath) int main ( ) { double straal; // straal van de cirkel cout << "Geef straal, daarna Enter .. "; cin >> straal; if ( straal > 0 ) cout << "Oppervlakte " << pie * straal * straal << endl; else cout << "Niet zo negatief ..." << endl; cout << "Einde van dit programma." << endl; return 0; } // main Voorbeeldprogramma 2: Straal berekenen de menselijke lezer. In de tweede en de derde regel wordt verteld dat er instructies uit de bibliotheek iostream gebruikt zullen gaan worden. Dan volgt een regel waarin aan de naam pie het getal 3.14159 gekoppeld wordt; dit is een constante, een geheugenlocatie die verderop in het programma niet meer gewijzigd kan en mag worden. Het eigenlijke C++-programma begint bij de regel met main. E´en voor e´ e´ n worden dan de regels (of beter statements, de opdrachten) uitgevoerd. Eerst wordt een variabele met de naam straal aangemaakt; de betreffende geheugenruimte kan een re¨eel getal (komma-getal) — of beter gezegd een benadering daarvan — bevatten. Dan komt er een tekst op het beeldscherm via de cout-regel. Alles wat tussen de "’s staat, komt letterlijk op het scherm. Dankzij de cin-regel wordt de door de gebruiker ingevoerde waarde gestopt in de variabele straal. Dan komt een if-statement, dat verscheidene regels beslaat. Indien straal een waarde groter dan 0 bevat, wordt de oppervlakte van de betreffende cirkel uitgerekend en afgedrukt (zie Hoofdstuk 3.9.2 voor meer over rekenen). Merk op dat wanneer de "’s ontbreken, de waarde van een uitdrukking (expressie) wordt afgedrukt door een cout-statement, maar met "’s erbij wordt letterlijk wat er tussen de "’s staat op het scherm gezet. In e´ e´ n cout-statement kunnen ook diverse zaken, gescheiden door <<’s, afgedrukt worden. Indien straal een waarde kleiner dan of gelijk aan 0 bevat, wordt de tekst Niet zo negatief ... op het scherm gezet, waarbij dankzij de endl de cursor naar een nieuwe regel gaat; de endl zorgt er trouwens ook voor dat de “output-buffer” (alles dat in de wachtrij staat om uitgevoerd te worden) op het beeldscherm geleegd wordt: hij flusht. Tot slot wordt nog een tekst afgedrukt, waarna het programma klaar is: met return 0; wordt het be¨eindigd. Zou een van de laatste regels uit het programma zo ingesprongen zijn dat de twee cout-regels direct onder elkaar staan, dan maakt dat niets uit voor de werking; een if of een else (of later andere block-statements) beslaan standaard alleen de eerstvolgende instructie. Er wordt een 23
ander effect bereikt door een { voor de op een na laatste cout-regel en na de laatste cout-regel te zetten: deze horen dan bij elkaar en worden als e´ e´ n statement, horend bij de else, opgevat. De laatste cout-regel wordt dan niet meer uitgevoerd als straal groter dan 0 is. Meer over de richtlijnen voor inspringende regels is overigens elders te vinden. Denk er aan dat een enkele = in C++ een toekenning is, en niet een test op gelijkheid. Zo zou in bovenstaand programma de regel if ( straal = 0 ) ongeacht de ingevoerde waarde van straal resulteren in het uitvoeren van de else-situatie. Er wordt namelijk 0 in straal gestopt, wat ook meteen het resultaat van de toekenning is, en 0 is in C++ hetzelfde als false, “niet waar” dus. Testen op gelijkheid gaat in C++ met ==. In veel andere talen gaat een toekenning overigens met een :=. Een ander bekend probleem is de zogenaamde hangende else (dangling else): if ( a > if ( b cout else cout
0 ) > 0 ) << "a en b groter dan 0" << endl; << "???" << endl;
Nu is de afspraak dat een else hoort bij de laatste nog openstaande if, dus in ons voorbeeld bij if ( b > 0 ). Wil je hem toch bij de eerste if laten horen, dan moeten er handig accolades worden gezet. Een schoon scherm/window is overigens als volgt “eenvoudig” te verkrijgen: #include ... system ("clear");
// op UNIX-systeem, voor DOS/Windows: "cls"
3.5 Loops Het meerdere malen herhalen van een aantal statements is een integraal deel van elke programmeertaal. Herhalingen worden in C++ met behulp van for- en while-loops bewerkstelligd. Hoewel ze in zekere zin equivalent zijn, is het een goede programmeerpraktijk om een while-loop te gebruiken als het aantal herhalingen van te voren onbekend is (“net zolang zeuren totdat”), of lastig te bepalen, en for-loops te reserveren voor situaties waarbij het aantal herhalingen vast ligt (“drie maal bellen”). Enkele elementaire voorbeelden: // druk eerste n getallen met hun kwadraat af void kwadraten1 (int n) { int i = 1; // tellertje, meteen initialiseren while ( i <= n ) { cout << i << " -- " << i * i << endl; i++; } // while } // kwadraten1 Voorbeeldprogramma 3: Kwadraten 1 Zolang de waarde van i kleiner dan of gelijk aan n is, worden de regels tussen de binnenste accolades herhaald. Omdat we weten hoe vaak de regels tussen de accolades uitgevoerd moeten 24
worden (namelijk n keer), horen we hier eigenlijk een for-loop te gebruiken. Hieronder staat hetzelfde programma waarbij de while-loop vervangen wordt door een for-loop. Er is meteen te zien dat dit een aantal statements scheelt: // druk eerste n getallen met hun kwadraat af void kwadraten2 (int n) { int i; // tellertje for ( i = 1; i <= n ; i++ ) cout << i << " -- " << i * i << endl; } // kwadraten2 Voorbeeldprogramma 4: Kwadraten 2 Zelfs mag je zeggen for ( int i = 1; i <= n ; i++ ), waarbij i een locale variabele voor de for-loop wordt, die niet nog eens apart in de functie hoeft te worden aangemaakt. Let er wel op dat i dan niet buiten de for-loop mag worden gebruikt, iets waar verschillende compilers ook nog wel eens verschillend mee omspringen. Het is verstandig om de test niet i != n+1 te laten zijn: het levert hier wel hetzelfde resultaat op, maar zou i per ongeluk een startwaarde groter dan n+1 hebben gekregen, dan waren de gevolgen niet prettig. Algemeen geldt dat een for-loop een while-loop met een standaard tellertje is volgens het volgende schema: for (maken en beginwaarde teller; zo lang gaat de loop door; hoe wordt de teller veranderd) Let hierbij op de plaats van de punt-komma’s (;). De volgende code is typisch geschikt voor een while loop: while ( x != 1 ) if ( x % 2 == 0 ) x = x / 2; else x = 3 * x + 1; Tot op heden is nog niet bekend of deze while-loop voor ieder positief geheel begingetal x stopt. En indien het stopt, is het nog maar de vraag wat het aantal doorgangen door de test is geweest. Het probleem staat onder meer bekend als het Syracuse-probleem, het Collatz-probleem of het 3x + 1-vermoeden. Ook bij een programma als: x = 1; while ( x < 1000 ) x = 2 * x; is het eenvoudig in te zien dat het stopt en dat na afloop x de waarde 1024 heeft, maar het aantal doorgangen is in het algemeen — met n in plaats van 1000 — niet voor elke situatie vooraf vast te stellen; een while-loop geniet hier dus de voorkeur. Soms komt de variant 25
do { cin >> getal; } while ( getal <= 0 ); // nu is een positief getal ingelezen goed van pas. Denk eraan dat de body (het stuk tussen accolades) van de loop hier altijd minstens e´ e´ n keer wordt uitgevoerd.
3.6 Functies Het komt vaak voor dat een aantal regels code meerdere malen voorkomt in het te ontwerpen programma. Denk hierbij bijvoorbeeld aan het afdrukken van het schaakbord of het berekenen van een faculteit. Het is in de meeste talen, waaronder C++, mogelijk kleine subprogramma’s te ontwerpen die deze taken op zich nemen. Deze kleine stukken code worden veelal functies genoemd. Hierboven zagen we er al enkele voorbeelden van (een functie die kwadraten afdrukt). Er bestaan twee soorten van functies: functies en procedures. Een functie voert handelingen uit en levert een resultaat op, bijvoorbeeld kwadraat (x) of oppervlaktecirkel (straal). Een procedure voert slechts een aantal (vaak voorkomende) handelingen uit en heeft verder geen resultaat, zoals bijvoorbeeld drukafplaatje ( ) of savefile ("geld.txt");. Een functie wordt, net als een variabele, gekoppeld aan een bepaald type (return-type) en wordt dus ook gedeclareerd (functie-declaraties staan boven main ( )!). Dit gaat als volgt: int kwadraat (int x) { int uitkomst; // doe hier de berekening return uitkomst; } // kwadraat de functie wordt vervolgens als volgt in main ( ) of andere functies gebruikt: int coordinaat1 = kwadraat (10); int coordinaat2 = kwadraat (8); Procedures moeten ook gedeclareerd worden en hebben het type void: void drukafplaatje ( ) { // instructies om het plaatje af te drukken } // drukafplaatje en worden als volgt aangeroepen: drukafplaatje ( ); Een speciale functie is main ( ). Dit is de functie waar het programma altijd mee begint. main ( ) is een int -functie en ziet er (meestal) als volgt uit: int main ( ) { // hier staat het hoofdprogramma return 0; // het getal 0 heet de exit-code van het programma } 26
Het is doorgaans verstandig om vanuit functies zo weinig mogelijk uitvoer en invoer te plegen, behalve bij functies die daar speciaal voor bedoeld zijn; zo houd je functies algemeen toepasbaar. Als je een functie al klaar hebt, en later eens een keer gebruikt, doe je aan bottom-up programmeren. Ga je de functie pas schrijven wanneer je hem nodig hebt, dan ben je top-down bezig. 3.6.1
Parameters
We zullen de mogelijkheden van een functie nu wat nader bekijken. We gebruiken daarvoor twee (verschillende) functies die getallen verwisselen. De eerste is meteen de “beste”. void wissel (int& a, int& b) { int temp; // ook mag (in een keer): temp = a; // int temp = a; a = b; b = temp; // en dus niet: a = b; b = a; } // wissel Voorbeeldprogramma 5: Integers wisselen We zagen net al dat sommige functies informatie nodig hebben (bijvoorbeeld de x waar het kwadraat van berekend moet worden). De benodigde informatie voor een functie wordt doorgegeven middels de parameters; de variabelen in de functie-declaratie (de heading). Deze parameters moeten ook gedeclareerd worden met een type en staan op volgorde. Na het aangeroepen van de functie kunnen de parameters binnen die functie gebruikt worden als gewone variabelen. De bovenstaande functie wisselt de inhoud van twee variabelen om. Het is dan ook logisch dat er twee parameters doorgegeven worden. Wat meteen opvalt is dat de parameters vergezeld zijn van een &. Dit brengt ons bij een belangrijk concept met betrekking tot parameters; het verschil tussen call-by-value en call-by-reference. Bij het gebruik van bovenstaande functie is het duidelijk dat de programmeur wil dat na de aanroep int x = 1; int y = 2; wissel (x,y); de variabele x 2 bevat en de variabele y 1. Om dit te bewerkstelligen is het noodzakelijk dat alles wat met a gebeurd binnen de functie, ook met x gebeurd daarbuiten. Het is dus zo dat bij een aanroep als wissel (x,y) a als synoniem voor x functioneert: alles wat met de e´ e´ n gebeurt, gebeurt met de ander. In feite wordt er bij aanroep met een & een referentie, een geheugenadres, doorgegeven. Dit heet call-by-reference. Zouden we in het voorbeeld de twee &’s weglaten, dan wordt de huidige waarde van x gekopieerd naar de variabele a. Zouden we die functie dan aanroepen met bijvoorbeeld wissel (x,y), dan zouden er locale variabelen a en b worden gecre¨eerd, die als startwaarde de waarde van x respectievelijk y zouden krijgen. De twee variabelen zouden binnen de functie worden gewisseld, de functie wordt be¨eindigd en aan x en y zou niets veranderd zijn. Om het bovenstaande “wissel-doel” te bereiken zijn de &’s (de en-percenten) dus noodzakelijk. Bij een functie als: int kwadraat (int x) 27
maakt het niet uit omdat de x zelf niet verandert of hoeft te veranderen. In het geval van call-by-reference mag overigens een aanroep als wissel (42,88); niet meer: tussen de haakjes moet een l-value staan, iets waaraan je kunt toekennen en wat dus bijvoorbeeld ook links van de toekenning = mag staan. Rechts van toekenningen mogen r-values komen: dit kunnen ook expressies zijn als 42 of m+2. Het is handig om de variabelen en parameters met verschillende functies ook anders te noemen. In het hieronder staande voorbeeld is te zien hoe we in het vervolg over de verschillende soorten variabelen en parameters zullen spreken. const int geld = 300; //constante (verandert nooit) char euro = ’E’ ; //globale variabele (in alle functies te gebruiken) void maakmerijk (int & zakgeld, //een formele parameter //call-by-reference int bonus) { //een formele parameter //call-by-value int kwadraat = 0; //een locale variabele //alleen bruikbaar in ’maakmerijk’ kwadraat = bonus * bonus; zakgeld += kwadraat; } // maakmerijk int main ( ) { int bonus = 0;
//ook een locale variabale //alleen bruikbaar in ’main’ cout << "Hoeveel wil je erbij? .. "; cin >> bonus; euro = ’e’; zakgeld = geld; maakmerijk (zakgeld, bonus); //zakgeld en bonus zijn actuele parameters cout << "ik krijg " << zakgeld << euro << " zakgeld" << endl; return 0; } // main Voorbeeldprogramma 6: Soorten variabelen Als er “synoniemen” in het spel zijn, lijkt het ingewikkelder: void alias (int r, int& s ) { int t; t = 3; r = r + 2; s = s + r + t; t = t + 1; r = r - 3; cout << r << s << t << endl; } // alias
28
int main ( ) { int t = 12; alias (t,t); cout << t << endl; return 0; } // main De uitvoer van dit programma zal zijn (ga maar eens na): 11
29
4 29
Als in de eerste regel van de functie een & voor r wordt toegevoegd krijgen we echter: 28
28
4 28
Tot slot een wat getructe versie om te laten zien dat het wisselen ook zonder hulpvariabele kan: // Verwissel (swap) de inhoud van a en b. // Dit maal doen we het met een truc: zonder hulpvariabele. // Het werkt niet als a en b dezelfde variabele zijn (aliases). // In de praktijk wordt dit eigenlijk nooit gebruikt. void wisseltruc (int& a, int& b) { a = a + b; // a = a_oud + b_oud b = a - b; // b = a_oud a = a - b; // a = b_oud } // wisseltruc Voorbeeldprogramma 7: Wisseltruc Nogmaals: dit is alleen een aardigheidje, geen zinvolle programmeer-praktijk. De aanroep wisseltruc (r,r) levert ook onverwachte effecten!
3.7 Files Soms is het nodig dat er informatie uit een bepaald bestand (file) gelezen wordt of dat het nodig is er informatie in op te slaan. In C++ is dit redelijk eenvoudig te realiseren. Het nu volgende programma kopieert een invoerfile onveranderd door naar een uitvoerfile, karakter voor karakter. Uiteraard kunnen de namen van de files ook in strings worden ingelezen en zo worden doorgegeven. Let er wel op dat als de filenaam van klasse string is, dat er soms naar “ouderwetse” C-stijl moet worden geconverteerd: stel je hebt string naam; gebruik dan invoer.open (naam.c_str ( ),ios::in);
29
#include #include #include // voor exit using namespace std; int main ( ) { ifstream invoer; ofstream uitvoer; char kar; invoer.open ("invoer.txt",ios::in); // koppel invoer aan (echte) file if ( ! invoer ) { // of: if ( invoer.fail ( ) ) cout << "File niet geopend" << endl; exit (1); // stopt het programma; return 1 was ook goed } // if uitvoer.open ("uitvoer.txt",ios::out); kar = invoer.get ( ); while ( ! invoer.eof ( ) ) { uitvoer.put (kar); kar = invoer.get ( ); } // while invoer.close ( ); uitvoer.close ( ); return 0; } // main Voorbeeldprogramma 8: File kopi¨eren
Verder zijn er nog veel meer mogelijkheden met file-IO. Let er ook op dat de memberfunctie eof pas dan een zinvol resultaat geeft als er een leespoging gedaan is. In het bovenstaande programma schijnt het aantal get’s e´ e´ n groter te zijn dan het aantal put’s; echter, het afsluitende EOF-symbool wordt door uitvoer.close ( ); gezet. Het letterlijk intikken van EOF gaat overigens soms ook goed (bijvoorbeeld zoiets als if ( kar == EOF ) ...); denk er wel aan dat dan kar een int moet zijn, want EOF is doorgaans -1! Door voor de regel uitvoer.put (kar); een test als if ( kar != ’e’ ) te zetten worden alle e’s “overgeslagen”. Er kan bijvoorbeeld ook op regelovergangen (LineFeed, ’\n’) getest worden. In een DOS of Windows-omgeving worden deze doorgaans onmiddellijk voorafgegaan door een CarriageReturn (’\r’) die alleen in binary mode (met ios::binary) worden gelezen; bovenstaand programma kopieert ze wel goed, maar handelt met e´ e´ n get zowel de ’\r’ als de er meteen na staande ’\n’ af. Ook bij het van cin lezen kunnen deze commando’s worden gebruikt. Als cin >> en het beruchte cin.get ( ) of cin.getline ( ) door elkaar worden gebruikt treden er soms vervelende effecten op: een \n wordt schijnbaar soms wel en soms niet gelezen. Het is allemaal te begrijpen, maar niet altijd even prettig. Zo slaat cin >> getal op zijn jacht naar getal bijvoorbeeld spaties en regelovergangen over, en heeft een regelovergang nodig om de buffer van cin binnen te krijgen.
30
3.8 Arrays en matrices Het is in C++ mogelijk om kleine tabelletjes of rijen van getallen, karakters of andere variabelen bij te houden. Dit gebeurt in zogenaamde arrays. Een array ziet er typisch als volgt uit: int rijtje[100]; Dit is een rijtje van 100 gehele getallen. Het getal dat aangeeft hoe groot het array is (hier dus 100) moet een constante zijn, zodat de compiler weet hoeveel ruimte hij voor het array in het geheugen moet reserveren. Eventueel mag een array dus ook zo aangemaakt worden: const int zogroot = 100; int rijtje[zogroot]; Na het declareren van het array kunnen de verschillende vakjes als volgt benaderd worden: rijtje[10] = 41; Het getal 10 wordt de index genoemd — het geeft aan over welk vakje we het hebben —, het getal 41 is hierbij de (nieuwe) inhoud van dat vakje. In tegenstelling tot een aantal andere talen loopt de index in C++ van 0...grootte - 1. Dit wil zeggen dat we bij het bovenstaande array van 100 groot de vakjes van 0 tot 99 kunnen gebruiken. Het is overigens wel mogelijk gegevens naar vakjes boven de 99 te schrijven maar dit levert vaak onverwachte en onwenselijke effecten op. De meeste problemen die ontstaan bij het werken met arrays komen dan ook door het overschrijden van deze bounds. Bij het doorgeven van een array aan een functie is het niet nodig tussen de vierkante haken de grootte aan te geven. Wel is het om bovenstaande reden vaak handig om deze grootte in een aparte variabele mee te geven: void doeiets (int rijtje[ ], int grootte) Arrays zijn gemakkelijk te vullen of uit te lezen met een for-loop. In het onderstaande voorbeeld worden alle getallen van een (eerder gevuld) array opgeteld. const int n = 100; int rijtje[n]; ... int telarrayop (int rijtje[ ], int n){ int som = 0, i; for ( i = 0; i < n; i++) { som += rijtje[i]; } // for return som; } // telarrayop Voorbeeldprogramma 9: Array-elementen optellen Let erop dat de for-loop hierbij doorgaat tot en met het laatste getal voor n; in dit geval dus (correct) tot en met 99. Veelvuldig wordt er gewerkt met dubbele (2-dimensionale) arrays, beter bekend als matrices. Zo’n array, zeg 31
int A[n][n];
// n moet const int n = ... zijn
verbeeldt een vierkante n bij n matrix. Niet-vierkante matrices kunnen uiteraard ook worden gedefinieerd. Je kunt zelfs een nieuw type maken via typedef int matrix[n][n];
// n moet const int n = ... zijn
Het element uit de i-de rij en de j-de kolom van een variabele A van type matrix is te vinden in A[i][j]. Denk eraan dat rijen en kolommen beginnen te nummeren met 0, en eindigen met n-1. Net als deze 2-dimensionale arrays is het overigens net zo makkelijk mogelijk om 3- of meerdimensionale arrays te gebruiken. Het doorgeven van meerdimensionale array’s aan functies heeft lastige kanten. De volgende functie, die de som van alle array-elementen van het array A berekent, maakt een en ander hopelijk duidelijk: // bepaal som van array-elementen uit eerste rijen van A int sommatrix (int A[ ][10], int rijen) { int i, j, som = 0; for ( i = 0; i < rijen; i++ ) for ( j = 0; j < 10; j++ ) som += A[i][j]; return som; } // sommatrix Voorbeeldprogramma 10: Matrix-elementen optellen De value-parameter rijen geeft het aantal rijen door, maar het aantal kolommen moet een const zijn, bijvoorbeeld 10. Dat moet de compiler weten om bij bijvoorbeeld A[3][5] het betreffende adres te kunnen berekenen. Dat adres is hier A + 3*10+5, of eigenlijk beter nog A + (3*10+5)*sizeof (int), want bij + wordt met de stapgrootte, dat wil zeggen de grootte van de array-elementen in bytes, rekening gehouden. De waarde van A is hier het adres waar het array begint. De rijen van het array liggen vanaf dit adres achter elkaar in het geheugen, en de rijlengte (het aantal kolommen) moet dus van te voren vastliggen. De ontwerpers van C++ hebben uit efficiency-overwegingen voor deze aanpak gekozen. De unaire operator sizeof geeft de grootte van het betreffende type — of de variabele — in bytes. Arrays en matrices worden vaak gebruikt voor het zoeken in of het sorteren van gegevens. Voorbeelden hiervan zijn te vinden in Hoofdstuk 4.2.
3.9 Werken met variabelen en getallen We kijken nu hoe we elementaire bewerkingen kunnen uitvoeren met getallen. 3.9.1
Werken met verschillende types
Aan het converteren, afdrukken en werken met verschillende typen variabelen zitten een aantal haken en ogen. Deze worden hier behandeld.
32
Gehele getallen Gehele getallen worden in C++ gerepresenteerd door het type int (van integer); meestal zijn dit 4 bytes. Een int-variabele kan vrijwel naar alle andere variabelen gecast (geconverteerd, gepromoveerd) worden. Stiekem zijn de types char (de getalsinhoud staat voor het nummer van het karakter in de ASCII-tabel) en bool (0 is false, rest is true) ook integers, waardoor die drie types makkelijk naar elkaar om te zetten zijn door simpele toekenningen. Tevens kan met al deze typen net als met int’s gerekend worden: //van integer-type naar integer-type bool test = false; int getal = test; // getal is nu 0 char karakter = ’A’; getal = karakter; // getal is nu 65 test = getal; // test is nu ’true’ getal = 40; karakter = getal; // karakter is nu ’(’ Voorbeeldprogramma 11: Integer-types Een int kan overigens ook makkelijk gecast worden naar een re¨eel getal: // van integer naar double int zakgeld = 100; double zakgeldcenten = zakgeld;
// zakgeldcenten is nu 100.000
Voorbeeldprogramma 12: Integer naar double Re¨ele getallen Voor re¨ele getallen, of liever benaderingen daarvan, heb je in C++ onder meer de types float (van floating point) en double (van double precision). Meestal gebruikt men de meest precieze van de twee: double’s, die typisch 8 bytes geheugen innemen. Bij het omzetten van re¨ele getallen naar gehele getallen wordt er automatisch gecast: double x = 1.8; int i; i = x; //automatische casting Voorbeeldprogramma 13: Double naar integer Bij een dergelijke automatische cast wordt altijd naar beneden afgerond (de cijfers achter de komma worden weggegooid) en dus niet naar het dichtstbijzijnde gehele getal, zodat bijvoorbeeld als x de waarde 1.9999 heeft i de waarde 1 krijgt. In zulke gevallen wordt vaak de truc i = x + 0.5 gebruikt. Vanwege het feit dat een double slechts een benadering is van een re¨eel getal volstaat een test als if ( x == y ) niet om double’s x en y op gelijkheid te testen. Zelfs if ( fabs (x - y) < epsilon ) 33
(waarbij epsilon bijvoorbeeld 0.00001 is, en fabs de absolute waarde is, doorgaans afkomstig uit cmath) voldoet niet, en dus moet zoiets als if ( fabs (x - y) < max ( fabs (x), fabs (y) ) * epsilon ) komen, waarbij max (.,.) een zelfgeschreven maximum-functie is. Het afdrukken van re¨ele getallen wordt door het volgende voorbeeld hopelijk duidelijk: #include ... double x = 92.36718; cout << "En x is:" << setw (8) << setprecision (2) << setiosflags (ios::fixed|ios::showpoint) << x << endl; Voorbeeldprogramma 14: Re¨ele getallen afdrukken Met setw (8) wordt de eerstvolgende af te drukken expressie 8 posities breed rechts uitgelijnd afgedrukt, de “stream manipulator” setprecision zorgt er voor dat er voortaan 2 cijfers na de decimale punt-komma komen — het mag ook met de memberfunctie precision —, en verder zorgt fixed er voor dat een decimale punt wordt gebruikt (in plaats van de “scientific notation” als in 5.1e+012) en laat showpoint een getal als 88.00 zo afdrukken, en niet als 88. Als het goed is verschijnt er nu 92.37 op het scherm, waarbij een spatie aanduidt. Er zijn allerlei varianten als cout << fixed; mogelijk. Boolean Bij sommige oudere compilers komt het voor dat het type bool niet beschikbaar is. Het is echter eenvoudig zelf te maken via: // Type boolean (meestal onder de naam bool al aanwezig!): enum boolean {False = 0, True = 1}; 3.9.2
Rekenen
Het rekenen binnen C++ werkt met de bekende rekenkundige operatoren (* betekent ’maal’). Bij het gebruik hiervan werken een aantal zaken anders dan je in eerste instantie verwacht. Zo wordt door 9/5 altijd, ook al zeg je x = 9/5 waarbij x een double is, 1 opgeleverd (want 5 past 1 maal in 9). De operator / is dus standaard de integer-operator ”delen door”. Wil je dat de berekening een exacter, re¨eel getal oplevert, gebruik dan casting door middel van (double)9/5 of 9.0/5. Het resultaat is dan 1.8000. Nog mooier is de nieuwe C++-notatie: static_cast<double>(9). Een speciale integer-operator is de %. Deze heet de modulo-operator en levert de rest bij deling op. 9 % 5 heeft als resultaat dan ook 4. Een andere merkwaardigheid binnen C++ is dat bij bijvoorbeeld de operator + de “evaluatievolgorde” niet vastligt: als in een programma ergens f(x) + g(x) staat, is niet vastgelegd of eerst f(x) of eerst g(x) wordt ge¨evalueerd. Meestal merk je het verschil niet, maar als een functie neveneffecten (side effects) heeft kan het resultaat van de volgorde afhangen! In C++ is een zeer precieze prioriteitenlijst van operatoren vastgesteld. Het is daarom niet altijd nodig — maar wel duidelijk — haakjes te plaatsen.
34
3.9.3
Random getallen en static variabelen
Vaak is het nodig om willekeurige (random) getallen te fabriceren. Daar valt veel over te zeggen, zie bijvoorbeeld de beroemde boeken van Knuth. Daaruit valt te leren dat een willekeurige methode doorgaans geen willekeurige getallen levert. Een heel eenvoudige methode is de volgende. Stel je hebt een eerste random-getal, zeg xoud (geheel). We berekenen het volgende random-getal xnieuw als (a ∗ xoud + c) modulo m, waarbij a, c en m zekere parameters zijn. Dit wordt steeds herhaald, waarbij uiteraard telkens de waarde van xoud aan het begin op de laatste xnieuw gezet wordt. Zo krijgen we schijnbaar willekeurige getallen uit {0, 1, 2, . . . , m − 1}. Duidelijk is dit niet echt random: door de keuze van a, c, m en de startwaarde van x — ook wel seed genoemd —, liggen alle volgende x-waarden vast. We spreken van dan ook van pseudorandom-getallen. Voor veel toepassingen is deze methode goed genoeg. Wel is de keuze van de parameters belangrijk. Vaak neemt men c = 1, en (als m een macht van 2 is, wat modulorekenen eenvoudig maakt) a modulo 8 gelijk aan 5, of (als m een macht van 10 is) a modulo 200 gelijk aan 21. Wordt dit gedaan, dan duurt het lang voordat herhaling optreedt (zodra een x al eerder is geweest, herhaalt zich immers de hele rij!); nu komen alle getallen tussen 0 en m − 1 aan de beurt. We krijgen dus bijvoorbeeld, met long (een grotere int) om wat grotere berekeningen toe te staan: // Pseudo-random-getal tussen 0 en 999: void randomgetal (long& getal) { getal = ( 221 * getal + 1 ) % 1000; } // randomgetal Voorbeeldprogramma 15: Random getal De laatste cijfers van de zo gegenereerde getallen worden hier overigens achtereenvolgens 1, 2, 3, 4, 5, . . . — niet zo willekeurig helaas. Iets netter kan de functie als volgt worden geschreven: // Pseudo-random-getal tussen 0 en 999: long randomgetal ( ) { static long getal = 42; getal = ( 221 * getal + 1 ) % 1000; return getal; } // randomgetal Voorbeeldprogramma 16: Random getal beter De initialisatie van een static variabele gebeurt maar e´ e´ n keer, terwijl de waarde behouden blijft tussen twee functie-aanroepen. Je kunt hier ook een functie laten aanroepen die van de tijd gebruik maakt, of die een getal aan de gebruiker van het programma vraagt, en zo de randomgenerator initialiseren. Als je een keer zo’n randomgenerator geschreven hebt, kun je deze op allerlei manieren gebruiken. Een voorbeeld: stel je wilt een willekeurige permutatie van de getallen 0 tot en met n-1 opbergen in het array int per[n]. Dan kun je dat als volgt doen:
35
// stop random permutatie van 0,1,...,n-1 in array A void maakpermutatie (int A[ ], int n) { int i; // array-index int r; // random array-index for ( i = 0; i < n; i++ ) A[i] = i; for ( i = n-1; i >= 0; i-- ) { r = randomgetal ( ) % ( i+1 ); // 0 <= r <= i wissel (A[i],A[r]); } // for } // maakpermutatie Voorbeeldprogramma 17: Random permutatie
Let er op dat bij deze methode alle n! permutaties evenveel kans hebben om gegenereerd te worden. In standaardbibliotheken voor C++ zitten meestal verschillende random-generatoren, die overigens doorgaans van het hierboven genoemde type, de lineaire congruentie methode, zijn. In cmath (vroeger math.h) zijn de betreffende functies meestal wel te vinden.
3.10 Recursie Recursieve functies zijn een speciaal soort functies. Er is sprake van recursie als een functie zichzelf direct of indirect aanroept. In het algemeen bestaat een recursief proces (functie) uit twee delen: 1. Een kleinste geval (basisgeval), dat eenvoudig genoeg is om direct op te lossen, dus zonder recursie. 2. Een algemene methode die een bepaald geval reduceert tot e´ e´ n of meer kleinere gevallen, waarbij men uiteindelijk bij het basisgeval uitkomt. De algemene gedaante van een recursieve functie (in een eenvoudige symbolische notatie met een if ... then ... else ... fi statement) is dan ook als volgt: if basisgeval then // test: geval simpel genoeg? los op zonder recursie (soms: niets doen); else een of meer recursieve (eenvoudigere) aanroepen; fi Faculteiten Het eenvoudigste voorbeeld van het gebruik van recursie is het berekenen van recursief gedefinieerde functies, zoals faculteiten, gedefinieerd door: 1 als n = 0 fac(n) = n ∗ fac(n − 1) als n > 0 Hieruit laat zich eenvoudig een programma afleiden: 36
// Berekent n! recursief. Neem aan dat n >= 0. long faculteit (int n) { if ( n == 0 ) // dus niet: if ( n = 0 ) return 1; else return n * faculteit (n - 1); } // faculteit Voorbeeldprogramma 18: Faculteit berekenen
Het resultaat-type long zorgt ervoor dat we iets grotere faculteiten kunnen berekenen dan als er int gestaan zou hebben. De body van de functie kan ook geschreven worden als return ( n ? n * faculteit (n - 1) : 1 ); Uiteraard kan deze functie ook eenvoudig niet-recursief (iteratief ) geschreven worden (Opgave 9). Analoog, stel dat de functie is: int som (int n) { return ( n ? n + som (n - 1) : 0 ); } // som Nu wordt de som van de getallen 0 tot en met n berekend. Dat kan ook heel eenvoudig met een gesloten formule via return ( n * ( n + 1 ) ) / 2 ; Fibonacci getallen Een zeer bekend en illustratief voorbeeld van recursie is de berekening van de Fibonaccigetallen. Deze zijn (recursief) gedefinieerd door 1 als n = 0 of n = 1 fib(n) = fib(n − 1) + fib(n − 2) als n > 1 Dit levert de welbekende rij 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610 . . . op. Bovenstaande definitie geeft het n-de getal uit deze rij (beginnend bij 0). De recursieve definitie geeft onmiddellijk aanleiding tot een recursieve C++-functie: long fib1 (int n) { if ( ( n == 0 ) || ( n == 1 ) ) return 1; else return fib1 (n-1) + fib1 (n-2); } // fib1 Voorbeeldprogramma 19: Fibonacci getallen Deze functie lijdt helaas aan het zogenaamde waterval-effect (ook wel Fibonacci-effect geheten). De aanroep fib1 (n) veroorzaakt een waterval van aanroepen, waarbij aanroepen ook 37
nog eens veel vaker dan e´ e´ n keer plaatsvinden. Zo veroorzaakt de berekening van het 10de Fibonacci-getal (n = 10) bijvoorbeeld vijf maal exact dezelfde berekening van het 6-de Fibonacci-getal (n = 6). In het algemeen vergt de berekening van het n-de Fibonacci-getal zo in totaal maar liefst 2 fib(n) − 1 aanroepen van fib1 (ga na). Dit probleem kan verbeterd worden met behulp van dynamisch programmeren, waarbij handige tabellen worden bijgehouden. De herhaalde aanroepen van het Fibonacci-effect worden hierbij vermeden door eerder behaalde tussenresultaten te onthouden in een tabel. Verder wordt voordat een aanroep gepleegd wordt, eerst in de tabel gekeken of dit Fibonacci-getal al niet eerder is uitgerekend. Als dat zo is, is de aanroep overbodig. Op deze manier worden alle aanroepen maar e´ e´ n keer gedaan, ten koste van een voldoende groot array. We krijgen: const int MAX = 100; long memo[MAX]; // stiekem gebruikte globale variabele // deze eerst geheel met nullen vullen long fib2 (int n) { if ( n >= MAX ) // helaas return fib2 (n-1) + fib2 (n-2); else if ( memo[n] > 0 ) // al eerder berekend return memo[n]; else { if ( ( n == 0 ) || ( n == 1 ) ) memo[n] = 1; else memo[n] = fib2 (n-1) + fib2 (n-2); return memo[n]; } // else } // fib2 Voorbeeldprogramma 20: Fibonacci getallen effici¨ent Het kan overigens ook met een eenvoudige iteratieve functie. Deze is veel effici¨enter dan de recursieve versie. Deze iteratieve versie leent zich uitstekend voor — in plaats van long — nog grotere getallen: een eigen gemaakt grootgetal, waarvoor dan wel onder andere een kopieer-operatie (=) en een optelling (+, +1) gemaakt moeten worden. Overigens kan het binnen de loop ook zonder hulp-variabele: tweede = eerste + tweede; eerste = tweede - eerste; Maar nu moet je ook nog grote getallen van elkaar aftrekken . . . Een mooi, maar wat ingewikkelder voorbeeld van het optreden van recursie vinden we bij de zogenaamde Ackermann-functie: als m = 0 en n ≥ 0 n+1 Ack(m − 1, 1) als m > 0 en n = 0 Ack(m, n) = Ack(m − 1, Ack(m, n − 1)) als m > 0 en n > 0 38
long fib3 (int n) { long eerste, tweede, hulp; int teller; eerste = 1; tweede = 1; for ( teller = 2; teller <= n; teller++ ) { // nu geldt: eerste == fib (teller-2) en tweede == fib (teller-1) hulp = tweede; tweede = eerste + tweede; eerste = hulp; } // for return tweede; } // fib3 Voorbeeldprogramma 21: Fibonacci getallen effici¨ent (iteratief)
Vele van de onderstaande zoek- en sorteermethoden (zie Hoofdstuk 4.2) kunnen eenvoudig recursief geprogrammeerd worden. We zullen nu enkele andere voorbeelden bekijken. Torens van Hanoi Gegeven zijn n (n ≥ 1) schijven, alle verschillend in grootte. Bij aanvang liggen alle schijven boven op elkaar op e´ e´ n stapel, en wel zo dat de grootste onderop ligt, dan de op een na grootste, . . . , en de kleinste bovenop. Kortom: een grotere schijf ligt nooit op een kleinere. Er zijn verder nog twee lege plaatsen beschikbaar. Voor n = 4 ziet de beginsituatie er zo uit:
plek 1
plek 2
plek 3
De bedoeling is om de hele toren op een van de twee lege plaatsen te krijgen, waarbij weer de grootste onder en de kleinste boven ligt (en klein op groot). Dit alles moet liefst zo snel mogelijk gebeuren. We zoeken dus een optimale oplossing. Om dit voor elkaar te krijgen mag men per keer maar e´ e´ n schijf oppakken (en wel alleen de bovenste van een stapel!) en deze bovenop een andere stapel leggen. Een belangrijke restrictie hierbij: er mogen alleen kleinere schijven op grotere gelegd worden, en niet omgekeerd. De recursieve oplossing hieronder volgt direct uit de volgende observaties. Om de grootste schijf te kunnen verzetten moeten alle n − 1 schijven erboven weg zijn. Bovendien moet de plek
39
waar de grootste heen moet leeg zijn. Aangezien we een optimale oplossing willen zal dit dan ook meteen de uiteindelijke bestemming van de grootste schijf moeten zijn. Dus: verplaats de bovenste n−1 schijven zo snel mogelijk naar de hulpplek (zeg plek 2), zet dan de grootste schijf van plek 1 naar de doelplek (plek 3), en verplaats dan de n − 1 schijven zo snel mogelijk van de hulpplek naar de doelplek. // torens van Hanoi: recursief // zet toren van n stuks (optimaal) van a naar b via c void zet (int n, int a, int b, int c) { if ( n > 0 ) { zet (n-1,a,c,b); cout << "zet van " << a << "naar " << b << endl; // print zet zet (n-1,c,b,a); } // if } // zet Voorbeeldprogramma 22: Torens van Hanoi
3.11 Object geori¨enteerd programmeren C++ biedt ons een aantal standaard-typen. Het komt echter vaak voor dat een programmeur deze typen wil samenpakken tot e´ e´ n geheel of totaal nieuwe types met eigen mogelijkheden (funcionaliteit) wil aanmaken. C++ geeft ons hiervoor genoeg mogelijkheden. Om eenvoudig te beginnen bekijken we eerst de volgende standaard-declaratie: int zakgeld; Zoals eerder gezegd is int hier het type en is zakgeld de naam van de variabele. In het object geori¨enteerd programmeren worden andere termen gebruikt. Variabelen, pointers, arrays, enz. zijn binnen C++ allemaal objecten; je kunt er wat mee doen (er dingen in opslaan, ze wissen, legen, kopi¨eren, ermee rekenen, etc.). Objecten die zich hetzelfde gedragen worden ondergebracht in eenzelfde klasse. Zo zijn bijvoorbeeld alle variabelen die gehele getallen kunnen bevatten en waar je mee kunt rekenen ondergebracht in de klasse int. Een klasse kan dus een simpel type variabele zijn — zie het voorbeeld met de int —, maar zoals we later zullen zien ook meer. Een klasse is dus eigenlijk een blauwdruk die eigenschappen en functionaliteit vastlegt. Een object dat gedeclareerd wordt volgens deze klasse noemen we een instantie van die klasse. Bij object geori¨enteerd programmeren draait alles om het ontwerpen van classes en het maken van instances hiervan. De objecten zijn dan vaak de basis waar mee gewerkt wordt. Voordelen hiervan zijn dat deze manier van programmeren beter aansluit bij de denkwijze van de ”echte wereld” en dat de zelf gedefinieerde classes (klassen) herbruikbaar zijn en ze de modulariteit (zie bij de richtlijnen) verhogen. Kijk maar eens naar onderstaand voorbeeld: int main ( ) { schaakbord nieuwbord; schaakspel nieuwspel; schaakstuk ditstuk; nieuwspel.start (nieuwbord); 40
... nieuwspel.zetstuk (ditstuk); ... if ( nieuwspel.afgelopen ( ) ) { cout << " einde spel" << endl; } // if } // main 3.11.1
Struct’s
De eenvoudigste (en dus ook de meest beperkte) mogelijkheid bij het maken van nieuwe blauwdrukken is die van de struct. Een struct kan opgevat worden als een collectie standaardobjecten die samengevoegd worden, maar ook als een aantal objecten die samen een bepaald concept realiseren. Het onderstaande voorbeeld maakt dit duidelijk. struct MeetkundigeBalk { int lengte; int breedte; int hoogte; }; // MeetkundigeBalk
let op de ;
Het concept van de meetkundige balk wordt vastgelegd door de drie maten lengte, breedte en hoogte. Er kan nu als volgt met de struct gewerkt worden: int main ( ) { MeetkundigeBalk balk; balk.hoogte = 10; balk.lengte = 15; balk.breedte = 30; int inhoud = balk.hoogte * balk.breedte * balk.lengte; cout << inhoud << endl; return 0; } // main Conceptmatig werken is een kenmerk van object geori¨enteerd programmeren. De mogelijkheden van een struct zijn op het eerste gezicht redelijk beperkt. Eigenlijk is een struct slechts een collectie eigenschappen. In de volgende paragraaf zien we hoe we hiernaast ook functionaliteit kunnen toevoegen — en in plaats van struct gebruiken we dan class. 3.11.2
Classes
Met behulp van een class is het mogelijk een heel nieuwe klasse te maken, compleet met een collectie variabelen en functionaliteit. Hier eerst een voorbeeld van zo’n klasse: Met een ijsje kan je een aantal dingen doen. Je kan een ijsje maken met behulp van bolletjes of je kan een ijsje opeten. Acties die je met of met behulp van een object kan doen vormen diens functionaliteit. Functionaliteit wordt in classes gerealiseerd door het declareren van functies in de klasse-definitie, zoals hierboven geldt voor de klasse ijsje. Functies die binnen zo’n klasse worden gedeclareerd heten member-functies. Ze worden als volgt gedefini¨eerd:
41
enum soorten {aardbei, vanille, pistache}; enum groottes {klein, middel, groot); struct bolletje { soorten soort; groottes grootte; int prijs; }; // bolletje class ijsje { public: void schepopbol (soorten soort, groottes grootte); void eetopbol ( ); int geefprijs ( ); ijsje ( ); ~ijsje ( ); int berekenprijs ( ); void leegijsje ( ); bool isleeg ( ); private: int prijs; bolletje bolletje1; bolletje bolletje2; }; // ijsje Voorbeeldprogramma 23: Klasse: IJsjes maken
void ijsje::eetopbol ( ) { ... } en zo aangeroepen: ijsje turbohoorn; ... turbohoorn.eetopbol ( ); De variabelen van een klasse worden member-variabelen genoemd of de eigenschappen (properties) van zo’n klasse. Member-variabelen en member-functies worden binnen member-functies aangeroepen zonder het object erbij. In plaats hiervan is het mogelijk this te gebruiken om het object aan te geven waarvan de member-functie wordt aangeroepen, maar dat is niet gebruikelijk (een enkele keer echter wel nodig): int ijsje::eetopbol ( if ( ! isleeg ( ) ) if ( bolletje2 != bolletje2 = -1;
) { { -1 ) { // of this->bolletje2 = -1; 42
} // if else { bolletje1 = -1; // of this->bolletje1 = -1; } // else } // if } // ijsje::eetopbol Public versus private Bij het gebruik van classes is het gebruikelijk de member-functies en member-variabelen op te delen in twee verschillende groepen: public en private. Zaken die binnen het public gedeelte staan zijn van buitenaf te ”bekijken” of aan te roepen. eetopbol hierboven is daar een voorbeeld van. Zaken die in het private gedeelte van de class gedeclareerd worden mogen echter alleen vanuit de eigen member-functies aangeroepen worden. Dit is dus verboden: int main ( ) { ijsje turbohoorn; int x = turbohoorn.prijs; } // main en dit mag wel: int ijsje::geefprijs ( ) { return prijs; } // ijsje::geefprijs Constructor en destructor Vaak is het handig om bij het aanmaken van een object alvast een initialisatie functie uit te voeren. Denk hierbij bijvoorbeeld aan het ”leeg maken” van het ijsje. Binnen C++ is dit mogelijk met behulp van de zogeheten constructor; een functie die meteen bij het maken van een nieuw object wordt aangeroepen, zoals bijvoorbeeld bij de declaratie ijsje turbohoorn. Hierboven valt te zien hoe een constructor gedeclareerd wordt, hieronder staat hoe de definitie eruit ziet. ijsje::ijsje ( ) { leegijsje ( ); } // ijsje::ijsje Merk op dat een constructor geen resultaat-type als void of int heeft. Soms is het noodzakelijk dat je aangeeft hoe een bepaalde class ”weggegooid” moet worden, om bijvoorbeeld te voorkomen dat ongebruikt geheugen gereserveerd blijft. Dit kan nodig zijn als tijdens het maken van het object ook andere objecten zijn aangemaakt. In C++ worden de ”weggooi-instructies” uitgevoerd in een destructor die net als de constructor geen resultaat-type heeft en er zo uitziet: ijsje::~ijsje ( ) { ... } // ijsje::~ijsje Een destructor wordt automatisch aangeroepen als de betreffende variabele aan het eind van zijn leven komt. 43
3.12 Pointers Pointers zijn speciale variabelen binnen C++ . Ze kunnen het beste gezien worden als een ”pijl” naar een andere variabele (of object). In werkelijkheid zijn het de adressen van de variabelen waar ze naartoe ”wijzen”. Laten we beginnen met een eenvoudig voorbeeld. Stel we hebben int* p; int* q; Dan zijn p en q pointers naar integers, oftewel adressen van integers. Voorlopig wijzen ze nog nergens naar, of liever: ze zijn onbepaald. Het volgende programma-fragment laat elementaire handelingen zien: p = new int; *p = 42; q = p; *q = 37; p = NULL; p = q; delete q;
// // // // // // //
maak een nieuwe int en stop diens adres in p die int wordt 42 kopieer zijn adres in q ook via q kun je de int wijzigen nu wijst p ECHT nergens naar en nu weer naar die oude int die we tot slot via q weggooien Voorbeeldprogramma 24: Werken met pointers
Samengevat: p is een pointer, een adres, terwijl *p datgene is waar die pointer naar wijst. En zodra je zegt int* p bestaat de pointer p, maar waar hij naar toe wijst weet je dan nog niet. Maar zeg je p = NULL, dan weet je dat wel: nergens naar. Denk eraan dat delete q de integer waar q naar wijst weggooit, en niet q zelf. Overigens is delete q; q = NULL; netjes, maar q = NULL; delete q; niet. Dit laatste gaat niet fout — er gebeurt gewoon niets. Wat overigens nergens op slaat is iets als q = new int; q = p; Eerst een nieuwe int maken, en dan diens adres overschrijven, is nogal onzinnig. We geven hier een enkel voorbeeld om met pointers te leren omgaan. Stel we hebben een lijst met karakters nodig, waar “willekeurig” lange series karakters in kunnen worden opgeslagen. We defini¨eren: class vakje { // een struct mag ook public: char info; vakje* volgende; }; // vakje 44
vakje* hulp = ingang; while ( hulp != NULL ) { cout << hulp->info; // hulp->info betekent: (*hulp).info hulp = hulp->volgende; } // while Voorbeeldprogramma 25: Pointerlijst: doorlopen
Nu kunnen we zo’n pointerlijst, als die ten minste eenmaal is opgebouwd, met ingang ingang van type vakje*, eenvoudig aflopen met Laten we eerst eens met de hand e´ e´ n voor e´ e´ n vakjes bouwen en aan elkaar vast maken. Om te beginnen een vakje met alleen een ’l’ erin: vakje* ingang; ingang = new vakje; ingang->info = ’l’; ingang->volgende = NULL; Als we nu een vakje met ’c’ erin hier voor willen zetten hebben we een hulppointer, zeg p, nodig: vakje* p; p = new vakje; p->info = ’c’; p->volgende = ingang; ingang = p; Stel dat we tussen de vakjes met ’c’ en ’l’ een vakje met ’a’ erin willen krijgen. Dat gaat als volgt: vakje* p; p = new vakje; p->info = ’a’; p->volgende = ingang->volgende; ingang->volgende = p; Een nieuw vakje vooraan een bestaande lijst toevoegen gaat algemener met: void zetervoor (char letter, vakje*& ingang) { vakje* p; p = new vakje; p->info = letter; p->volgende = ingang; ingang = p; } // zetervoor
// let op de &
Voorbeeldprogramma 26: Pointerlijst: vooraan toevoegen Deze functie werkt zelfs goed als ingang NULL was. Aan het eind van de functie, vlak voor de afsluitende accolade, moet NIET delete p; staan; p wordt immers als locale variabele vanzelf 45
weer vrijgegeven, terwijl dat waar p naar wijst uiteraard moet blijven bestaan! We kunnen dezelfde lijst als boven nu opbouwen met: vakje* ingang = NULL; zetervoor (’l’,ingang); zetervoor (’a’,ingang); zetervoor (’c’,ingang); Maar het is wellicht slim om achteraan de lijst toe te voegen. Dat kan met de volgende functie, waarbij de pointer laatste steeds naar het laatste vakje van een lijst wijst: void zeterachter (char letter, vakje*& laatste) { vakje* p = new vakje; p->info = letter; p->volgende = NULL; if ( laatste != NULL) laatste->volgende = p; laatste = p; } // zetervoor
// let op de &
Voorbeeldprogramma 27: Pointerlijst: achteraan toevoegen De prijs die je betaalt is dat je naast de ingangspointer ook een pointer naar het laatste vakje moet onthouden. Dezelfde lijst als boven wordt nu opgebouwd met: vakje* ingang = NULL; vakje* laatste = NULL; zeterachter (’c’,laatste); // of: zeterachter (’c’,ingang); ingang = laatste; // laatste = ingang; zeterachter (’a’,laatste); zeterachter (’l’,laatste); Call-by-reference en call-by-value spelen bij pointers een belangrijke rol. Stel we hebben de functie void demo (char letter, vakje*& ingang) { if ( ingang != NULL ) ingang->info = letter; } // demo Laten we eens achtereenvolgens uitvoeren ingang = NULL; zetervoor (’A’,ingang);, en daarna demo (’B’,ingang);. Of nu de & al of niet in de heading van demo voorkomt, de letter B komt in het door ingang aangewezen vakje terecht. Immers, de pointer ingang verandert niet — en dat is de parameter waar het over gaat —, maar wel datgene waar deze pointer naar wijst. Vergelijk dit met void demo2 (vakje*& ingang) { ingang = NULL; } // demo2
46
// Vindt eerste vakje met letter erin (uit lijst met ingang), // als zo’n vakje bestaat; anders NULL vakje* vind (char letter, vakje* ingang) { bool gevonden = false; vakje* hulp = ingang; // NIET eerst hulp = new vakje while ( ( hulp != NULL ) && !gevonden ) if ( letter == hulp->info ) gevonden = true; else hulp = hulp->volgende; return hulp; } // vind Voorbeeldprogramma 28: Pointerlijst: vakje vinden
Nu zal, als de & wordt weggelaten, een kopie van de actuele parameter NULL gemaakt worden! De echte actuele parameter verandert niet, wat wel gebeurt als & er weer bij staat. Een pointerlijst doorzoeken verloopt via: Dit gaat analoog aan lineair zoeken. Zie hiervoor Hoofdstuk 4.2. Het kan natuurlijk ook recursief: // Als vind, maar nu recursief vakje* vindrecursief (char letter, vakje* ingang) { if ( ingang == NULL ) return NULL; else if ( letter == ingang->info ) return ingang; else // komt letter voor in de rest van de lijst? return vindrecurief (letter,ingang->volgende); } // vindrecursief Voorbeeldprogramma 29: Pointerlijst: recursief vakje vinden
3.13 Strings Vaak wordt in programma’s met een rijtje karakters, een string, gewerkt. Vooral bij in- en uitvoer worden strings gebruikt. In string.h zitten allerlei handige functies om strings te manipuleren. Ze werken met variabelen van type char*, bijvoorbeeld ook char tekst[100]: de variabele tekst is hier eigenlijk een pointer naar een char. Let er op dat je zelf in principe dit geheugen moet beheren, dus new en delete moet gebruiken. Een “leuk” voorbeeld is de functie strcpy, die ongeveer als volgt is ge¨ımplementeerd: void strcpy (char* s, char* t) { while ( *s++ = *t++ ) ; } // strcpy
// kopieer t naar s
47
Hier wordt dus in e´ e´ n regeltje een string gekopieerd! Een eenvoudiger voorbeeld is de functie strcmp die een getal kleiner dan 0 oplevert als de string s alfabetisch voorafgaat aan de string t, 0 als ze gelijk zijn, en in de overige gevallen een getal groter dan 0. Hierbij wordt dankbaar de afsluitende ’\0’ die elke string hoort te hebben gebruikt. int strcmp (char* s, char* t) { // komt s voor t? int i; for ( i = 0; s[i] == t[i]; i++ ) if ( s[i] == ’\0’ ) return 0; return s[i] - t[i]; } // strcmp Voorbeeldprogramma 30: String compare Overigens wordt een " in een string voorgesteld door \". Veel mensen gebruiken in plaats van endl ook binnen de " " een \n, en schrijven cout << "Hij zei: \"Leuk!\"\n";. Denk er wel aan dat een \n niet “flusht”: de uitvoer wordt gebufferd weggeschreven. Tot slot: in de nieuwere C++-versies wordt in plaats van de “oude C-stijl” string.h de nieuwe verbeterde string gebruikt. Daar kun je “gewoon” strings kopi¨eren. Onder het oude bewind komt getline soms van pas: char zin[80]; cin.getline (zin,80); zorgt ervoor dat er maximaal 79 karakters plus de afsluitende \0 in de variabele zin terecht komen: er wordt tot dit aantal of tot (en met) de Enter gelezen. Let er op dat de afsluitende Enter alleen wordt weggelezen als hij bereikt wordt. Die lastige buffers maken het leven niet eenvoudiger . . .
3.14 De Standard Template Library — STL In de Standard Template Library, afgekort STL, zijn allerlei fraaie datastructuren, zoals rijen en verzamelingen (zie Hoofdstuk 5), reeds aanwezig. In bijvoorbeeld het boek van Deitel en Deitel of in dat van Ammeraal is hier volop informatie over te vinden. We bekijken hier kort e´ e´ n voorbeeld: de klasse vector. Met behulp van de uit het voorafgaande bekende array-operator [ ] kunnen als gebruikelijk elementen benaderd worden, maar “vectoren” kunnen ook dynamisch groeien en krimpen! Bovenaan het programma moet #include staan. Een vector v met gehele getallen wordt gedeclareerd door vector< int>v; Met v.push_back (1215); wordt 1215 achteraan v toegevoegd, en de grootte (v.size ( )) van v groeit automatisch met e´ e´ n. Eigenlijk is de klasse vector een container.
48
3.15 C++-standaards In 1998 zijn allerlei standaards vastgesteld voor C++. Ook zijn diverse aanvullingen doorgevoerd. Voor meer details raadplege men bijvoorbeeld het uitgebreide boek van Deitel en Deitel. We geven hier slechts enkele voorbeelden. Oudere compilers — en zelfs nieuwe — voldoen helaas niet altijd aan alle vernieuwingen. Allereerst zijn zogeheten namespaces ge¨ıntroduceerd. Hiermee kan voorkomen worden dat dingen die per ongeluk hetzelfde heten door elkaar worden gehaald. Zo kan bijvoorbeeld cout een andere betekenis toebedeeld krijgen — maar wie zou dat nu willen? Bovenaan een programma komt in plaats van de ook nog dikwijls gebruikte ene regel #include nu: #include using namespace std; Ook eigen namespaces kunnen worden gefabriceerd. In bovenstaand voorbeeld mag je in plaats van het gewone cout << ... nu ook zeggen std::cout << ... en zo naamsconflicten voorkomen. In het voorbeeld is ook te zien dat de .h bij de include-regel verdwenen is. Dat geldt voor de standaard includefiles; eigengemaakte behouden hun .h. Bij enkele standaard includefiles is de naam iets gewijzigd: , , en vervangen respectievelijk <math.h>, , <string.h> en . Er zijn ook mooie nieuwe gemaakt, zoals <stack>, <string> (!), (!) en <set>, zie Hoofdstuk 3.14 over de Standard Template Library. Als je compiler erop berekend is kunnen ook templates gebruikt worden; meer hierover bij vervolgcolleges als Datastructuren. Een enkel voorbeeld, waarin het maximum van drie variabelen van klasse Tiep wordt bepaald: template Tiep maximum (Tiep x, Tiep y, Tiep z) { Tiep max = x; if ( y > max ) max = y; if ( z > max ) max = z; return max; } // maximum Mits de klasse Tiep maar kopi¨eren met = toestaat en objecten van klasse Tiep zich met > laten vergelijken, hebben we hier een algemeen werkend sjabloon gemaakt.
49
4 Algoritmen Bij programmeren draait bijna alles om het vervaardigen van stappenplannen ofwel algoritmen. In dit hoofdstuk bekijken we een aantal illustratieve en/of veel gebruikte algoritmen(soorten). In het vervolgvak Algoritmiek wordt meer aandacht besteed aan handigheidjes, nieuwe algoritmen, en zaken als effici¨entie- en ordevergelijkingen ervan.
4.1 Rekenalgoritmen Algoritmen draaien doorgaans om het berekenen van een of ander gegeven. Vele hiervan komen voort uit de wiskunde. Hieronder behandelen we er een paar. 4.1.1
Grootste gemeenschappelijke deler
Allereerst een functie die de grootste gemeenschappelijke (gemene) deler, de ggd, van twee gegeven gehele getallen berekent. // Bepaal grootste gemene deler (ggd) van gehele, positieve x en y // met behulp van het algoritme van Euclides. int ggd (int x, int y) { int rest; while ( y != 0 ) { rest = x % y; // rest bij deling van x door y (x modulo y) x = y; y = rest; } // while return x; } // ggd Voorbeeldprogramma 31: GGD berekenen Verstokte C-liefhebbers zullen als test overigens schrijven while ( y ) { ... }, maar of dat de duidelijkheid bevordert is nog maar de vraag. De ggd-functie kan bijvoorbeeld gebruikt worden om breuken te vereenvoudigen, zie verderop. // Vereenvoudig de breuk teller/noemer zoveel mogelijk. // Neem aan dat teller >= 0 en noemer > 0. void vereenvoudig (int& teller, int& noemer) { int deler = ggd (teller,noemer); if ( deler > 1 ) { teller = teller / deler; noemer = noemer / deler; } // if } // vereenvoudig Voorbeeldprogramma 32: Breuken vereenvoudigen De test if ( deler > 1 ) hoeft er overigens niet bij. Wel moet er van een hulpvariabele deler gebruik gemaakt worden: wordt er geprobeerd twee maal door de grootste gemene deler 50
van teller en noemer te delen (dus tweemaal “dezelfde” functieaanroep, wat op zich ook al niet zo snugger is), dan zal bij de tweede deling de helaas gewijzigde waarde van teller gebruikt worden. De noemer van de breuk zal dan niet veranderen, wat — als de ggd niet 1 is — toch in de bedoeling ligt! De functie voor de ggd kan ook eenvoudig recursief geschreven worden, zie onder. In feite gebeurt hier hetzelfde als bij de niet-recursieve versie: beide zijn implementaties van het algoritme van Euclides. // Als ggd, maar nu recursief. int ggdrecursief (int x, int y) { if ( y == 0 ) return x; // want ggd (x,0) = x als x niet 0 is else return ggdrecursief (y, x % y); } // ggdrecursief Voorbeeldprogramma 33: GGD recursief berekenen
4.1.2
Priemgetallen
Er zijn vele manieren om te bepalen of een gegeven geheel getal groter dan 1 een priemgetal is, dat wil zeggen geen delers heeft behalve 1 en zichzelf. Het meest voor de hand liggende algoritme — maar lang niet het snelste — staat verderop. // Voor sqrt (worteltrekken): #include // Levert true precies als getal een priemgetal is. bool priem (int getal) { int deler = 2; double wortel = sqrt (getal); bool geendelers = true; while ( ( deler <= wortel ) && geendelers ) { if ( ( getal % deler ) == 0 ) // deler gevonden: getal niet priem geendelers = false; deler++; } // while return geendelers; } // priem Voorbeeldprogramma 34: Priemgetal? De extra hulpvariabele wortel voorkomt het steeds opnieuw uitrekenen van de wortel uit het oorspronkelijke getal. Het is duidelijk dat je niet meer voorbij deze wortel hoeft te kijken: als daar een deler van het oorspronkelijke getal zou zitten, zou er ergens voor die wortel ook een moeten zijn. De while-loop kan overigens ook als for-loop opgeschreven worden. Doorgaans zullen wij, zoals al eerder opgemerkt, alleen een for-loop gebruiken als het aantal keren dat de body doorlopen moet worden van te voren duidelijk bekend is (we moeten iets bijvoorbeeld 17 keer, of n 51
keer, doen). In andere gevallen geven we zoals eerder gezegd de voorkeur aan een while-loop (we moeten dan iets doen net zolang als . . . ). Een vergelijkbaar algoritme is de zeef van Erathosthenes. Hier wordt in een array bijgehouden welke getallen, kleiner dan een zekere bovengrens, nu wel of niet priem zijn. We geven dit algoritme als een “hoofdprogramma”, main dus. #include using namespace std; const int MAX = 100; int main ( ) { bool zeef[MAX]; // zijn getallen 0,1,...,MAX-1 priem (zeef[i] true)? int getal; int veelvoud; double wortel = sqrt (MAX); zeef[0] = false; zeef[1] = false; for ( getal = 2; getal < MAX; getal++ ) zeef[getal] = true; // ... tot het tegendeel bewezen is for ( getal = 2; getal < wortel; getal++ ) if ( zeef[getal] ) { veelvoud = 2 * getal; // getal + getal als * "te duur" is while ( veelvoud < MAX ) { zeef[veelvoud] = false; veelvoud = veelvoud + getal; // oftewel veelvoud += getal; } // while } // if for ( getal = 2; getal < MAX; getal++ ) { if ( zeef[getal] ) cout << getal << " "; } // for return 0; // sommige compilers waarschuwen als deze regel ontbreekt } // main Voorbeeldprogramma 35: De zeef van Erathosthenes
4.1.3
Driehoek van Pascal
Nog een voorbeeld uit de wereld van de gehele getallen betreft de welbekende driehoek van Pascal. Elk getal in de driehoek is de som van de twee getallen erboven. De getallen heten ook wel binomiaalco¨effici¨enten. We lopen op een handige manier door de matrix heen en vullen rij voor rij de array-elementen in. We maken gebruik van de bekende identiteit i i−1 i−1 = + j j−1 j en krijgen zo het volgende programma: We vullen alleen die array-elementen die we echt nodig hebben: 52
void pascaldriehoek ( ) { int i, j; int Pascal[n][n]; // in i-de rij, j-de kolom komt "i boven j" for ( i = 0; i < n; i++ ) Pascal[i][0] = 1; // de eerste kolom bevat enen Pascal[0][1] = 0; for ( i = 1; i < n; i++ ) { cout << endl << Pascal[i][0] << " "; // 1 op een nieuwe regel for ( j = 1; j <= i ; j++ ) { Pascal[i][j] = Pascal[i-1][j-1] + Pascal[i-1][j]; cout << Pascal[i][j] << " "; } // for if ( i != n - 1 ) Pascal[i][i+1] = 0; } // for } // pascaldriehoek Voorbeeldprogramma 36: Driehoek van Pascal
1
0
... 1
1
0
... 1
2
1
0
... 1
3
3
1
0
...
Het is overigens ook mogelijk om met een enkel array te werken. In de i-de slag bevat dat array dan de getallen uit de i-de rij van de driehoek van Pascal. Nu moet elk getal de som van de twee getallen erboven worden, wat in het enkele array betekent de som van het getal links van jezelf en jezelf. Loop je nu van links naar rechts door het array, dan wordt te vroeg de waarde van de array-elementen gewijzigd, namelijk terwijl je hun oude waarde nog nodig hebt. Door van rechts naar links te lopen, en op te merken dat de driehoek toch symmetrisch is, ontstaat een eenvoudig programma. void pascaldriehoekbeter ( ) { int i, j; int rij[n]; for ( j = 1; j < n; j++ ) rij[j] = 0; rij[0] = 1; for ( i = 1; i < n; i++ ) { for ( j = i; j > 0 ; j-- ) { rij[j] = rij[j-1] + rij[j]; cout << rij[j] << " "; } // for cout << rij[0] << endl; // een 1 erachter } // for } // pascaldriehoekbeter Voorbeeldprogramma 37: Driehoek van Pascal effici¨ent
53
4.1.4
Matrixvermenigvuldiging
Matrices willen graag met elkaar vermenigvuldigd worden. (Voor diegenen die nog niet weten wat dat is: geen nood.) Het ligt voor de hand om een klasse matrix te maken, waarbij memberfuncties voor bijvoorbeeld inverteren, determinant nemen, vermenigvuldigen, kopi¨eren (altijd mee oppassen: met pointers in het spel kan het fout aflopen). In de Standard Template Library (STL, zie Hoofdstuk 3.14) is zo’n type overigens al aanwezig. Wij zullen hier “gewoon” twee vierkante matrices, zeg A en B, vermenigvuldigen, met als resultaat C. De definitie is dat n−1
Ci j =
∑ Aik Bk j ,
0 ≤ i, j < n.
k=0
De getallen uit de i-de rij van A en de j-de kolom van B worden paarsgewijs vermenigvuldigd en de resultaten opgeteld ten einde het matrixelement Ci j op te leveren. // C wordt A * B (matrixvermenigvuldiging). void vermenigvuldigen (int A[n][n], int B[n][n], int C[n][n]) { int i, j, k; for ( i = 0; i < n; i++ ) for ( j = 0; j < n; j++ ) { C[i][j] = 0; for ( k = 0; k < n; k++ ) C[i][j] += A[i][k] * B[k][j]; } // for } // vermenigvuldigen Voorbeeldprogramma 38: Matrixvermenigvuldiging Hierbij moeten aanroepen als vermenigvuldigen (A,A,A) vermeden worden! Zo te zien kost matrixvermenigvuldigen van twee n bij n matrices overigens n3 vermenigvuldigingen van array-elementen; men zegt wel: een O(n3 )-algoritme (zie het college Algoritmiek voor deze notatie). Het kan ook sneller, zie het college Complexiteit. 4.1.5
Verzamelingen
We gaan nu uit een vaas met verschillend genummerde balletjes een aantal balletjes trekken zonder teruglegging. Welke getallen-volgordes zijn er mogelijk? Een vaas is eigenlijk wat in de wiskunde een verzameling genoemd wordt. We zullen dan ook een C++-klasse verzameling maken, en vervolgens ons probleem oplossen. Deze klasse kunnen we vast wel vaker gebruiken. Wat we dan gedaan hebben is in feite het maken van een abstract datatype (ADT); andere voorbeelden hiervan zijn stapels en rijen (zie Hoofdstuk 5). We beginnen met: In principe kun je met templates ook verzamelingen fabriceren waarvan de elementen niet noodzakelijk getallen zijn, maar van een algemeen type; dat zullen we nu maar niet doen. We moeten dus nog wel de verschillende member-functies schrijven. verzameling::verzameling ( ) { int i; 54
// Grootte van het universum: const int n = 20; // En de klasse verzameling voor deelverzamelingen van {0,1,2,...,n-1}: class verzameling { public: // default constructor (de lege verzameling) verzameling ( ); // destructor: niks doen in dit geval ~verzameling ( ) { } // destructor verzameling void drukaf ( ); void erbij (int i); void eruit (int i); bool ziterin (int i); // geef alle volgordes om hoeveel getallen // uit de verzameling te trekken; // diepte geeft de recursie-diepte aan void trekking (int hoeveel, int diepte); private: // i-de element true betekent dat i in de verzameling zit bool inhoud[n]; }; // verzameling Voorbeeldprogramma 39: Verzameling
for ( i = 0; i < n; i++ ) inhoud[i] = false; } // default constructor verzameling void verzameling::drukaf ( ) { int i; cout << endl; for ( i = 0; i < n; i++ ) if ( ziterin (i) ) cout << i << " "; cout << endl; } // verzameling::drukaf void verzameling::erbij (int i) { inhoud[i] = true; } // verzameling::erbij void verzameling::eruit (int i) { inhoud[i] = false; } // verzameling::eruit bool verzameling::ziterin (int i) { return inhoud[i]; 55
}
// verzameling::ziterin
Resteert nog trekking te schrijven, want daar ging het om: // We moeten uit de verzameling hoeveel getallen trekken (zonder // teruglegging). Als hoeveel 0 is hoeven we niets te doen. // In diepte houden we de recursie-diepte bij. void verzameling::trekking (int hoeveel, int diepte) { int knikker; if ( hoeveel > 0 ) { for ( knikker = 0; knikker < n; knikker++ ) if ( ziterin (knikker) ) { spaties (2*diepte); cout << knikker << endl; eruit (knikker); trekking (hoeveel-1,diepte+1); erbij (knikker); } // if } // if } // verzameling::trekking Voorbeeldprogramma 40: Trekking uit een verzameling Hierbij wordt een functie void spaties (int aantal) gebruikt die aantal spaties afdrukt (opgave: schrijf deze zelf). Het doel hiervan is dat uit de uitvoer met enige moeite af te lezen valt wat we willen weten. Zo zal 3 5 9 5 3 ... betekenen dat de getallenrijtjes 3 5, 3 9, 5 3, ... geproduceerd zijn. Probeer zelf eens de uitvoer wat mooier te krijgen (Opgave 29). De — overigens niet gebruikte — member-functie drukaf levert ook niet zulke mooie resultaten op het beeldscherm. Probeer zelf ook eens de functie zo te verbeteren dat bijvoorbeeld netjes komma’s en accolades toegevoegd worden, zoals past bij een verzameling. Uiteindelijk kan de functie trekking als volgt worden aangeroepen: // Voorbeeldaanroep int main ( ) { verzameling vaas; // aanroep default constructor ==> geen ( ) vaas.erbij (3); vaas.erbij (5); vaas.erbij (9); vaas.trekking (2,0); return 0; } // main 56
Het is ook mogelijk een verzameling als een enkelverbonden pointerlijst te implementeren. Dit is met name verstandig wanneer het kleine deelverzamelingen van een groot universum betreft: er zouden anders arrays met veel elementen false nodig zijn. Dankzij de bovenstaande opzet hoeven gelukkig de functies drukaf en trekking niet gewijzigd te worden; ze maken alleen via andere member-functies gebruik van het array of de pointerlijst.
4.2 Zoeken en Sorteren Van oudsher hebben algoritmes voor sorteren en zoeken in de belangstelling gestaan. Bijvoorbeeld voor het zoeken van een telefoonnummer of het sorteren van een leden-database. Gezien de vaak grote hoeveelheden gegevens is het belangrijk dat dit enigszins effci¨ent gaat. Er zijn dan ook veel verschillende algoritmen bedacht. We zullen er hier enkele kort behandelen. Steeds gebruiken we een array van het volgende type: // Arraygrootte: const int n = 20; // Een array A: int A[n]; Eigenlijk moeten we de array-grootte n steeds als parameter doorgeven. Let erop de arraygrenzen niet te overschrijden! Laten we als voorbeeld eens het kleinste getal uit een array opsporen (zie verderop). // Geef kleinste getal uit array A (dat n elementen heeft) int minimum (const int A[ ], int n) { int klein = A[0]; int i; for ( i = 1; i < n; i++ ) if ( A[i] < klein ) // kleinere gevonden klein = A[i]; return klein; } // minimum Voorbeeldprogramma 41: Zoek kleinste getal Arrays en pointers hebben in C++ een nauwe band. Wij zullen proberen de twee zaken niet te verwarren, en ons niet bezighouden met zaken als de gelijkheid van &A[0] en A voor een variabele A van type array. Zo mag bijvoorbeeld in de heading van de functie ook const int * A staan. Eigenlijk staat hier voor de compiler de volgende informatie: op deze plek staat een serie int’s; hoeveel dat er zijn is “niet van belang”. De tweede parameter, n, wordt gebruikt om dit aantal door te geven. De const zorgt er hier voor dat je de array-elementen niet mag wijzigen. In bovenstaande functie zou A[0] = klein; een waarschuwing van de compiler opleveren. 4.2.1
Lineair zoeken
We zoeken in een (ongesorteerd) array naar een getal. Voor de hand ligt het volgende. Vooraan (of achteraan) beginnen en element voor element vergelijken tot we het gezochte element gevonden hebben of tot alle elementen geweest zijn, en het getal klaarblijkelijk niet voorkomt. 57
// Zoek getal in array A. Lineair zoeken. // Geeft index met A[index] = getal, als getal ten minste // voorkomt; zo niet: resultaat wordt -1. int lineairzoeken (int A[n], int getal) { int index = 0; bool gevonden = false; while ( ! gevonden && ( index < n ) ) { if ( getal == A[index] ) gevonden = true; // of meteen return index; else index++; } // while if ( gevonden ) return index; else return -1; } // lineairzoeken Voorbeeldprogramma 42: Lineair zoeken
Als je pech hebt, bijvoorbeeld als het gezochte getal niet voorkomt, kost je dat voor een array met n elementen n vergelijkingen; kortom: O(n) (lineaire orde); zie Opgave 51. De methode heet lineair zoeken. 4.2.2
Binair zoeken
Als het array gesorteerd is kunnen we wat slimmer zijn. In een telefoonboek bijvoorbeeld zal iedereen die een naam zoekt (om het bijbehorende telefoonnummer te krijgen) gebruik maken van de alfabetische ordening. Zoek je overigens op nummer (om te weten wie dat nummer heeft), dan zit er — tenzij je bij de telefoondienst werkt — niets anders op dan met lineair zoeken het hele telefoonboek door te nemen. Binair zoeken is een voor de hand liggende methode om een getal op te sporen in een gesorteerd array. Kijk allereerst of het middelste element het gezochte element is. Zo niet, bepaal dan op grond van vergelijken met dat middelste element of het zoekproces voortgezet moet worden in de linker helft of juist in de rechter helft van het array en herhaal dit. Stop zodra het element gevonden is, danwel het te onderzoeken array leeg is. Als het aantal elementen even is: kies e´ e´ n van de twee middelste. Een aanroep ziet eruit als index = binairzoeken (A,n,getal). In het slechtste geval ben je hier, als er bijvoorbeeld n = 2k − 1 (met k > 0 geheel) elementen zijn, k vergelijkingen aan kwijt; men zegt wel: O(log n) (logaritmische orde). De methode binair zoeken kan ook recursief worden opgeschreven. Zonder verder commentaar: 4.2.3
Een eenvoudige sorteermethode
Nu willen we een array (rij) op grootte oplopend sorteren. Een heel eenvoudige methode is de volgende. Beginsituatie: het gesorteerde stuk is leeg en het ongesorteerde stuk is de hele rij. Zoek nu eerst het kleinste element in het ongesorteerde stuk en verwissel dat met het voorste 58
// Zoek getal in GESORTEERD array A met n elementen. // Binair zoeken. // Geeft index met A[index] = getal, als getal ten minste // voorkomt; zo niet: resultaat wordt -1. int binairzoeken (int A[n], int n, int getal) { int links = 0, int rechts = n-1; // zoek tussen links en rechts int midden; bool gevonden = false; while ( ! gevonden && ( links <= rechts ) ) { midden = ( links + rechts ) / 2; if ( getal == A[midden] ) gevonden = true; // of meteen return midden; else if ( getal > A[midden] ) links = midden + 1; else rechts = midden - 1; } // while if ( gevonden ) return midden; else return -1; } // binairzoeken Voorbeeldprogramma 43: Binair zoeken iteratief
// zoek in een oplopend gesorteerd array A, tussen links en rechts, // de index met A[index] == getal; -1 als getal niet in A voorkomt int binairzoeken (int A[ ], int n, int links, int rechts, int getal) { int midden; if ( links > rechts ) // basisgeval return -1; else { // recursieve aanroepen midden = (links + rechts)/2; if ( getal == A[midden] ) // gevonden! return midden; else // verder zoeken: recursieve aanroepen if ( getal > A[midden] ) // rechts hetzelfde doen return binairzoeken (A, n, midden+1, rechts, getal); else // links hetzelfde doen return binairzoeken (A, n, links, midden-1, getal); } // else recursieve aanroepen } // binairzoeken Voorbeeldprogramma 44: Binair zoeken recursief
59
element van dat stuk. Het gesorteerde stuk is nu e´ e´ n element groter en het ongesorteerde stuk is e´ e´ n element kleiner. Herhaal dit totdat het ongesorteerde stuk leeg is. De methode heet ook wel selection sort. We zullen het nu schrijven als ware array een klasse, waarvan we een member-functie aan het maken zijn. We gebruiken een (private) member-variabele inhoud, waarin uiteraard het array zit opgeborgen: class array { private: int inhoud[n]; public: void simpelsort ( ); ... }; // array void array::simpelsort ( ) { int voorste, kleinste, plaatskleinste, k; for ( voorste = 0; voorste < n; voorste++ ) { plaatskleinste = voorste; kleinste = inhoud[voorste]; for ( k = voorste + 1; k < n; k++ ) if ( inhoud[k] < kleinste ) { kleinste = inhoud[k]; plaatskleinste = k; } // if if ( plaatskleinste > voorste ) wissel (inhoud[plaatskleinste],inhoud[voorste]); } // for } // array::simpelsort Voorbeeldprogramma 45: Simpel sorteren Hierbij geeft de “binary scope resolution operator” :: aan dat de functie simpelsort hoort bij de klasse array. De heading zou hier (zonder OOP) ook mogen luiden: void simpelsort (int inhoud[ ], int n) { Nogmaals: de eerste parameter is een array, wat in C++ hetzelfde is als een pointer naar — in dit geval — een int. De actuele lengte van dit array wordt als tweede parameter meegegeven; zelfs als de eerste parameter int inhoud[n] was geweest — waar de C++-compiler overigens niets speciaals mee doet — moeten we nog steeds goed op de array-grenzen letten! 4.2.4
Bubblesort
Een eenvoudige variant hierop is de methode bubblesort. De C++-code is bijzonder compact, maar bubblesort is helaas niet zo’n goede sorteermethode. Het sorteren van een rijtje met n getallen kost altijd 21 n(n − 1) vergelijkingen; vaak zegt men: O(n2 ) (kwadratische orde). De
60
void bubblesort (int A[ ], int n) { int ronde, j; for ( ronde = 1; ronde < n; ronde++ ) for ( j = 0; j < n - ronde; j++ ) if ( A[j] > A[j+1] ) wissel (A[j],A[j+1]); } // bubblesort Voorbeeldprogramma 46: Bubblesort
volgende methodes, Shellsort en quicksort, doen dat soms of vaak (misschien zelfs altijd) sneller. Een array, A geheten, wordt als volgt op grootte gesorteerd. In de eerste ronde worden A[0] en A[1] vergeleken en indien nodig (namelijk als A[0] groter is dan A[1]) wordt hun inhoud verwisseld; daarna A[1] en A[2], . . . , A[n-2] en A[n-1]; het is duidelijk dat het grootste element nu achteraan staat. In de tweede ronde worden A[0] en A[1] vergeleken, . . . , A[n-3] en A[n-2]; er vindt dus e´ e´ n vergelijking minder plaats. Zo gaat dit verder; in de laatste (de (n-1)ste) ronde hoeven alleen nog maar A[0] en A[1] vergeleken te worden. De grote getallen “borrelen” als het ware naar achteren, vandaar de naam bubblesort. 4.2.5
Invoegsorteer
Als een rij gesorteerd is en men wil een element toevoegen, dan kan invoegsorteer, oftewel insertion sort, gebruikt worden: zoek de plaats op waar het element moet komen en voeg het element op die plaats ertussen (bij een array betekent dat, dat het achterstuk e´ e´ n plaats naar achter moet schuiven). Een ongesorteerde rij kan men met invoegsorteer sorteren door element voor element aan een oorspronkelijke lege rij (die is namelijk “per definitie” gesorteerd) toe te voegen zoals beschreven. De complexiteit is vergelijkbaar met die van bubblesort. De C++-code laten we als opgave: Opgave 54. 4.2.6
Shellsort
De methode Shellsort sorteert bijzonder snel. Het gaat als volgt: we zetten eerst de getallen in het array A die op zekere afstand, zeg h, van elkaar liggen goed ten opzichte van elkaar; dit noemen we h-sorteren. Er geldt dan A[i] <= A[i+h] voor alle i waarvoor i en i+h geldige array-indices zijn. Verander (bijvoorbeeld halveer, maar er zijn betere keuzes) die afstand in h’, en ga dan h’-sorteren. Herhaal dit tot (en met) de afstand 1 is. Het sorteren van de deelrijen gaat met een of andere “snelle” methode. Wij gebruiken hier een variant op bubblesort, waarbij de deelrijen ingenieus vervlochten worden. Het aardige is dat een h-gesorteerde rij na het h’sorteren nog steeds h-gesorteerd is. De complexiteit van Shellsort hangt sterk af van de keuze van de h’s. Zie verder Opgave 54. 4.2.7
Quicksort
Het sorteren van een rij getallen kunnen we ook recursief doen. We krijgen dan (symbolisch genoteerd) zoiets als:
61
void array::shellsort ( ) { int i, j, sprong = n; bool klaar; while ( sprong > 1 ) { // inhoud is nu sprong-gesorteerd sprong = sprong / 2; // er bestaan betere keuzes dan / 2 klaar = false; while ( ! klaar ) { klaar = true; for ( i = 0; i + sprong < n; i++ ) { j = i + sprong; if ( inhoud[i] > inhoud[j] ) { wissel (inhoud[i],inhoud[j]); klaar = false; } // if } // for } // while } // while } // array::shellsort Voorbeeldprogramma 47: Shellsort
sorteer (rij) : if ( rij heeft meer dan 1 element ) { verdeel rij in linkerrij en rechterrij; sorteer (linkerrij); sorteer (rechterrij); combineer (linkerrij, rechterrij); } De methode quicksort heeft deze vorm. Bij quicksort wordt al het werk gestoken in de verdeelstap, waardoor het combineren niets doen wordt. Bij de recursieve methode mergesort daarentegen is het verdelen makkelijk (in twee¨en hakken), en zit al het werk in de combineerstap (ritsen). Als men een rij van n stuks verdeelt in een linkerrij van n − 1 elementen en een rechterrij van 1, en combineren wordt invoegen, dan krijgen we de methode insertion sort terug. Het sorteeralgoritme quicksort, dat gebruikt wordt om een array A dat n gehele getallen bevat te sorteren, werkt als volgt. Zij K gelijk aan A[0]. Alle getallen kleiner dan K worden vooraan gezet, alle getallen groter dan K achteraan, en K zelf ertussen. Vervolgens worden begin- en eindstuk (recursief) met quicksort gesorteerd. De C++-code laten we liggen voor het college Algoritmiek. Het handig in het array zelf manipuleren (met K) blijkt nog niet zo eenvoudig te zijn. Hoe het ook zij, de methode doet zijn naam eer aan: mits zorgvuldig toegepast, wordt er snel gesorteerd. Zie Opgave 55. Op internet zijn mooie visualisaties van sorteermethoden te bewonderen. 4.2.8
Indexbestanden
Vaak wordt een groot bestand niet fysiek gesorteerd, maar met behulp van zogeheten indexbestanden — ook wel index-arrays genoemd, let op het verschil met array-indices (in het Engels 62
subscripts) — toegankelijk gemaakt. Dit heeft verschillende oorzaken. Het bestand kan te groot zijn, of het is al op een andere sleutel gesorteerd. Een indexbestand is een array met gehele getallen die aangeven in welke volgorde het oorspronkelijke bestand gesorteerd moet worden doorlopen. Zo is het eerste element uit het indexbestand de array-index van het “kleinste” element uit het oorspronkelijke bestand. Als opgave: schrijf een C++-programma dat dit proces implementeert, zie ook Opgave 50.
63
5 Abstracte Datastructuren Soms zijn de door C++ standaard aangeleverde datatypen niet toereikend; bijvoorbeeld omdat je algoritme minder goed werkt, je niet-standaard gegevens wilt gebruiken of de opslagcapaciteit te klein is. Met behulp van de in C++ aangeleverde mechanismen als classes en pointers is het goed mogelijk zelf wat ingewikkeldere en meer specialistische datastructuren te cre¨eren. De kenmerken hiervan hangen meestal sterk samen met het algoritme waar ze voor ontwikkeld worden. Bij vakken als Algoritmiek en Datastructuren zal dieper ingegaan worden op de verschillende mogelijkheden.
5.1 Stapels en rijen Stapels en rijen zijn, evenals de reeds genoemde verzamelingen, een fraai voorbeeld van abstracte datatypen. Stapels en rijen zijn datastructuren waarmee een aantal problemen op inzichtelijke wijze kan worden opgelost. Ze zijn niet standaard in C++ aanwezig, dus als men er gebruik van wil maken zal men eerst een implementatie moeten maken. Nu kan een rij of stapel zowel met behulp van array’s als met behulp van pointers worden gefabriceerd. Beide methoden hebben hun eigen verdiensten. Een stapel (stack, denk aan een stapel borden) is een reeks elementen van hetzelfde type met de volgende toegestane operaties: • men kan een lege stapel aanmaken, • men kan zien of de stapel leeg is, • men kan er een element aan toevoegen (push), • men kan er het laatst-toegevoegde element weer uithalen (pop). Een stapel heeft dus de LIFO-eigenschap: LIFO = Last In First Out. Een rij (queue, denk aan een rij voor een kassa) is een reeks elementen van hetzelfde type met de volgende toegestane operaties: • men kan een lege rij aanmaken, • men kan zien of de rij leeg is, • men kan er een element aan toevoegen, • men kan er het eerst-toegevoegde element weer uithalen. Een rij heeft dus de FIFO-eigenschap: FIFO = First In First Out. Bij implementaties van stapels/rijen moet men soms nog een functie toevoegen: • kijk of de stapel/rij vol is. Als we alleen naar deze eigenschappen kijken vatten we stapels en rijen op als zogenaamde abstracte datatypen. Deze blijken een zeer belangrijke rol te vervullen binnen de informatica; we zullen ze nog vaak tegenkomen, met name bij vakken als Algoritmiek en Datastructuren. De taal C++ leent er zich bijzonder goed voor om abstracte datatypen te maken. Dat komt ook omdat het begrip abstract datatype in de object-geori¨enteerde wereld zit ingebakken. Een voorbeeld. Stel dat we uit een stapel met gehele getallen alle optredens van het grootste getal willen verwijderen; verder moet de stapel onderanderd blijven. Als de stapel leeg was moet er niets gebeuren. 64
void haalgrootstegetaluitstapel (stapel& S) { stapel hulp; int x, max; if ( ! S.isstapelleeg ( ) ) { S.haalvanstapel (max); hulp.zetopstapel (max); while ( ! S.isstapelleeg ( ) ) { S.haalvanstapel (x); if ( x > max ) max = x; hulp.zetopstapel (x); } // while while ( ! hulp.isstapelleeg ( ) ) { hulp.haalvanstapel (x); if ( x != max ) S.zetopstapel (x); } // while } // if } // haalgrootstegetaluitstapel Voorbeeldprogramma 48: Stapel: Verwijder grootste Let er op dat klassen in C++ doorgaans call-by-reference worden doorgegeven, met een & dus. Dan wordt er namelijk geen lokale kopie gemaakt, wat anders soms nare gevolgen heeft. Verder nemen we aan dat er een constructor is, die ervoor zorgt dat stapel hulp; meteen hulp de lege stapel maakt. Als voorbeeld zullen we nu een pointer-implementatie maken van een stapel voor gehele getallen. Als opgave: geef een array-implementatie. Met behulp van templates kunnen we zelfs stapels voor “willekeurige” types fabriceren. We hebben allereerst een overigens al bekend extra type nodig: class vakje { // een struct mag ook public: // constructor (een destructor hoeft misschien niet) vakje ( ) { info = 0; volgende = NULL; } // constructor vakje int info; vakje* volgende; }; // vakje Voorbeeldprogramma 49: Een Stapelvakje De vakjes waaruit de pointerlijst straks bestaat, zijn opgebouwd uit een veld info voor een geheel getal en een veld volgende voor de rest van de stapel. En nu de klasse stapel:
65
// Klasse stapel: class stapel { public: // constructor stapel ( ) { bovenste = NULL; } // constructor stapel // destructor ~stapel ( ); // zet element bovenop stapel: push void zetopstapel (int); // haal element van stapel: pop void haalvanstapel (int&); // is stapel leeg? bool isstapelleeg ( ) { return ( ( bovenste == NULL ) ? true : false ); // return !bovenste; doet het ook, of if ( bovenste == NULL ) ... } // isstapelleeg // afdrukken stapel: soms handig void drukaf ( ); private: vakje *bovenste; }; // stapel Voorbeeldprogramma 50: De klasse stapel De member-functies van de klasse stapel zijn: stapel::~stapel ( ) { int getal; while ( ! isstapelleeg ( ) ) haalvanstapel (getal); } // stapel::~stapel void stapel::zetopstapel (int getal) { vakje *temp; temp = new vakje; // constructor voor vakje wordt aangeroepen! temp->info = getal; temp->volgende = bovenste; bovenste = temp; } // stapel::zetopstapel void stapel::haalvanstapel (int& getal) { vakje *temp; getal = bovenste->info; temp = bovenste; bovenste = bovenste->volgende; delete temp; } // stapel::haalvanstapel void stapel::drukaf ( ) { 66
vakje *temp = bovenste; cout << "Stapel bevat:" << endl; while ( temp != NULL ) { // while ( temp ) mag ook: NULL == 0! cout << temp->info << " "; temp = temp ->volgende; } // while cout << endl; } // stapel::drukaf Tot slot een main die dit gebruikt: main ( ) { stapel S; int getal = 0; while ( getal >= 0 ) { S.drukaf ( ); cout << "Zet getal op stapel; 0 haalt van stapel, < 0 stopt" << endl; cin >> getal; if ( getal > 0 ) S.zetopstapel (getal); else if ( ( getal == 0 ) && ( ! S.isstapelleeg ( ) ) ) { S.haalvanstapel (getal); cout << getal << " van stapel gehaald " << endl; } // if } // while return 0; } // main Voor een rij gaat het analoog: class rij { private: int aantal; // is niet nodig, misschien wel handig vakje* voorste; vakje* achterste; public: rij ( ) { aantal = 0; voorste = NULL; achterste = NULL; } // constructor rij ~rij ( ); bool isrijleeg ( ) { return ( voorste == NULL ); } // isrijleeg void zetinrij (int getal ); void haaluitrij (int& getal ); }; // rij Voorbeeldprogramma 51: De klasse rij Bij de implementatie moet erop gelet worden aan welke kant verwijderd en aan welke kant toegevoegd moet worden. Het blijkt lastig om te verwijderen bij achterste (als tenminste de enkelverbonden lijst bij voorste begint), dus verwijderen we bij voorste. We krijgen: 67
rij::~rij ( ) { int getal; while ( ! isrijleeg ( ) ) haaluitrij (getal); } // rij::~rij void rij::zetinrij (int getal) { vakje* hulp = new vakje; aantal++; hulp->info = getal; hulp->volgende = NULL; if ( achterste != NULL ) achterste->volgende = hulp; else voorste = hulp; achterste = hulp; } // rij::zetinrij void rij::haaluitrij (int& getal) { vakje* hulp = voorste; aantal--; getal = hulp->info; voorste = voorste->volgende; if ( voorste == NULL ) achterste = NULL; delete hulp; } // rij::haaluitrij Een rij kan ook met behulp van een array worden gemaakt, zie verderop. Hierbij is voor de array-index van het voorste getal uit de rij, en achter de array-index van het laatste getal uit de rij. Omdat een volle rij van een lege rij moet kunnen worden onderscheiden, blijft er altijd minstens e´ e´ n array-element ongebruikt. In de praktijk wordt dit vaak anders opgelost: introduceer een extra membervariabele aantal die het actuele aantal elementen in de rij bijhoudt. Een destructor mag hier weer achterwege blijven.
5.2 Binaire bomen Een boom wordt in de discrete wiskunde gedefinieerd als een samenhangende (dat wil zeggen bestaande uit e´ e´ n stuk) graaf zonder cykels (= kringen). Als we nu een speciale knoop aanwijzen, de wortel, en we tekenen de paden vanaf de wortel naar de andere knopen naar beneden, dan krijgen we een hi¨erarchische structuur die lijkt op een stamboom. We gebruiken voor dit soort bomen dan ook eenzelfde terminologie: kind, afstammeling, ouder, voorouder. In een boom hebben we dus ouder-kind relaties tussen knopen, en men kan sommige andere knopen alleen via de wortel bereiken. Hieronder een voorbeeld met karakters in de knopen.
68
const int MAX = 100; class rij { // maximaal MAX-1 elementen public: rij ( ) { voor = 1; achter = 0; } // constructor rij bool isrijleeg ( ) { return ( ( achter + 1 ) % MAX == voor ); } // isrijleeg bool isrijvol ( ) { return ( ( achter + 2 ) % MAX == voor ); } // isrijvol void zetinrij (int getal) { achter = ( achter + 1 ) % MAX; inhoud[achter] = getal; } // zetintrij void haaluitrij (int& getal) { getal = inhoud[voor]; voor = ( voor + 1 ) % MAX; } // haaluitrij private: int inhoud[MAX]; int voor, achter; }; // rij Voorbeeldprogramma 52: Een alternatieve rij
Sm Hm
A A m X Cm
@ @
m A PP @ PPP PP @ P m Dm Fm G
Jm
Km Vm
@ @
Lm
@ @ Bm Nm Mm
Zm
Een binaire boom is nu een boom waarin elke knoop ofwel nul, ofwel e´ e´ n ofwel twee kinderen heeft. In dat laatste geval noemen we het ene kind het linkerkind, en het andere het rechterkind. Als een knoop e´ e´ n kind heeft, dan is dat ofwel een linkerkind ofwel een rechterkind. Een betere definitie van binaire boom is de volgende. Hierin wordt een binaire boom recursief gedefinieerd. Definitie: een binaire boom is een eindige verzameling knopen die ofwel leeg is, ofwel bestaat uit een knoop (de wortel) en twee disjuncte verzamelingen knopen die beide ook weer een binaire boom zijn, genaamd linkersubboom en rechtersubboom.
We zullen een binaire boom gebruiken om informatie in op te slaan. Die informatie, bijvoorbeeld gehele getallen of letters, staat in de knopen. De structuur is slechts toegankelijk via de wortel. Een voor de hand liggende implementatie van een binaire boom is met pointers, en staat hieronder. We gebruiken hier even geen aparte klasse binaire boom om het niet nodeloos ingewikkeld te maken. Allereerst defini¨eren we een klasse knoop, vervolgens de boom als een
69
pointer naar een knoop. Het gaat hier om een binaire boom die gehele getallen bevat. De knopen zijn opgebouwd uit een veld info voor een geheel getal, een veld links voor de linkersubboom en een veld rechts voor de rechtersubboom. class knoop { // een struct mag ook public: knoop ( ) { info = 0; links = NULL; rechts = NULL; } int info; knoop* links; knoop* rechts; }; // knoop
// constructor knoop
Voorbeeldprogramma 53: Knoop van een binaire boom knoop* wortel; // de ingang tot de binaire boom Aangezien een binaire boom recursief gedefinieerd is, is het niet verwonderlijk dat veel functies die iets met bomen doen ook recursief zijn. We geven wat voorbeelden. 1. Wandelingen Vaak is het nodig om alle knopen van de boom te bezoeken. Bijvoorbeeld om de volledige inhoud van de boom achter elkaar af te drukken. De drie meest gebruikte wandelingen zijn de preorde wandeling (WLR: Wortel-Links-Rechts), de symmetrische wandeling (LWR) en de postorde wandeling (LRW). Als voorbeeld bekijken we de preorde wandeling. Hierbij wordt eerst de wortel van de boom bezocht, en vervolgens de linkersubboom (op preorde manier) en tenslotte de rechtersubboom (op preorde manier). Het basisgeval is de lege boom (niets doen!). Dit leidt tot de volgende recursieve C++functie : void preorde (knoop* wortel) { if ( wortel != NULL ) { cout << wortel->info << endl; preorde (wortel->links); preorde (wortel->rechts); } // if } // preorde Voorbeeldprogramma 54: Preorde wandeling 2. Knopen tellen Om het aantal knopen van de hele boom te bepalen moet je het aantal knopen van de linkersubboom en het aantal knopen van de rechtersubboom bij elkaar optellen, plus nog 1 voor de wortel. De lege boom heeft uiteraard 0 knopen. We krijgen in C++: 3. Boom afbreken We willen nu de boom netjes helemaal afbreken, dus alle knopen met delete weghalen. Na afloop is de boom dus leeg (NULL!). Merk op dat we hier een postorde wandeling gebruiken. 70
int aantal (knoop* wortel) { if ( wortel == NULL ) return 0; else return ( 1 + aantal (wortel->links) + aantal (wortel->rechts) ); } // aantal Voorbeeldprogramma 55: Boomknopen tellen void breekaf (knoop* & wortel) { if ( wortel != NULL ) { breekaf (wortel->links); breekaf (wortel->rechts); delete wortel; wortel = NULL; } // if } // breekaf Voorbeeldprogramma 56: Binaire boom vellen
Er zijn vele soorten binaire bomen, elk met hun eigen toepassingen. We noemen hier even binaire zoekboom. Dit is een binaire boom waarin voor de waarden in de knopen geldt: waarde in de knoop zelf is groter dan de waarden in zijn linkersubboom, en kleiner dan waarden in zijn rechtersubboom. In deze bomen kunnen we effici¨ent zoeken. Zie verder vakken Algoritmiek en Datastructuren.
71
de de de de
6 Meerdere files compileren Tot nu toe hebben we vooral/alleen gekeken naar korte programma’s die allemaal in e´ e´ n bestand ingetypt werden en als zodanig ook werden gecompileerd. Wanneer je met grotere opdrachten bezig gaat zul je zien dat het handig is om een applicatie uit meerdere bestanden op te bouwen. In dit hoofdstuk geven we een korte introductie hoe je dit het best kunt aanpakken.
6.1 Waarom meerdere files? Voordat we uitleggen hoe je een applicatie kunt verdelen over meerdere files, is het belangrijk om eerst goed te weten waarom je dat zou doen. Een aantal belangrijke redenen is: Scheiding van interface en implementatie Deze belangrijke overweging zegt eigenlijk niets anders dan: “Je hoeft niet te weten wat erin zit, zolang je maar weet hoe je het moet gebruiken”. Stel bijvoorbeeld dat je een programma hebt geschreven dat het spel Boter, Kaas en Eieren (BKE) speelt. Je hebt een heel effici¨ente BKE-computerspeler ge¨ımplementeerd, met daarin een klasse, zeg, BKE, met duidelijke member-functies zoals vind_beste_zet ( ), doe_zet ( ), print_bord ( ), onderzoek_alle_zetten ( ), undo_zet ( ), etc. Al deze member-functies bestaan zelf misschien wel uit heel veel regels ingewikkelde C++ programma-code en roepen allerhande functies aan uit bibliotheken, etcetera. Stel nu ook dat iemand (jijzelf of iemand anders) gebruik wil maken van jouw mooi ontworpen klasse BKE. Dan is deze persoon helemaal niet ge¨ınteresseerd in de precieze implementatie van al die member-functies. Het enige wat belangrijk is, is dat bekend is welke member-functies er zijn, en hoe hun declaratie eruitziet. Het is daarom een goede gewoonte om de definitie van je klasse in een zogenaamde include file te zetten (deze worden ook wel header files genoemd; gewoonlijk hebben ze .h of .hh als extensie) en de werkelijke implementatie in een normale .cc of .cpp file (de source-file). Men hoeft dan alleen maar naar de include file te kijken om te zien wat jij hebt geschreven en hoe het moet worden gebruikt. Overzichtelijkheid Maar zelfs als je de scheiding tussen implementatie en header file buiten beschouwing laat is het overzichtelijker om verschillende onderdelen van een groot programma onder te brengen in verschillende bestanden. Als je bijvoorbeeld een klasse document hebt die onder andere bestaat uit objecten van klassen tekst en tekening, dan verdient het aanbeveling om alle programma code die te maken heeft met de tekst in een apart bestand onder te brengen (of eigenlijk 2 bestanden met bijvoorbeeld namen tekst.cc voor de implementatie en tekst.h voor de include file) en hetzelfde te doen voor de tekening code. Je kunt dan bijvoorbeeld snel de bij een bepaald onderdeel horende functies vinden. Modulariteit Dit is een heel belangrijk aspect van programmeren dat aangeeft hoe gemakkelijk het is om modules (onderdelen) van je programma te wijzigen of volledig te vervangen. Als je een mooi modulair opgebouwd programma hebt kun je eenvoudig een module vervangen door een andere module, zonder dat dat gevolgen heeft voor de overige onderdelen. Een voorwaarde is dan natuurlijk wel dat de nieuwe functies op dezelfde wijze kunnen worden gebruikt als de oude (dat wil zeggen dezelfde interface implementeren, maar misschien effici¨enter of beter). Het voordeel is dan gelijk dat als twee verschillende programma’s gebruik willen maken van de BKE klasse, ze allebei alleen maar #include "bke.h" hoeven toe te voegen aan hun code 72
om van de definitie gebruik te maken. Het enige alternatief zou zijn dat je in beide bestanden de definitie van klasse BKE zou moeten opnemen. Stel nu dat 100 programma’s gebruik maken van deze klasse en stel nu ook dat je op een gegeven moment besluit om de klasse aan te passen (bijvoorbeeld uit te breiden) — je zou dan alle 100 bestanden moeten wijzigen en dat is niet de bedoeling. Ook kunnen anderen gemakkelijk jouw code gebruiken door slechts e´ e´ n bestand te includen. Compilatie-snelheid Een laatste voordeel van het verdelen van een programma over verschillende bestanden is dat dit de compilatie-snelheid ten goede komt. Stel dat je applicatie uit 10 bestanden bestaat waarvan er 9 foutloos zijn en 1 een bug bevat. Die 9 goede bestanden kunnen dan eenmalig gecompileerd worden en hoeven daarna nooit meer opnieuw. Die ene file met de fout kan vervolgens gewijzigd worden (waarschijnlijk zelfs meerdere keren) en iedere keer dat er opnieuw gecompileerd wordt hoef je alleen die ene file te compileren en dat gaat veel sneller dan wanneer alles steeds van begin af aan gecompileerd moet worden.
6.2 Header files en implementaties We hebben hierboven gepleit voor het scheiden van interface en implementatie, maar hoe doen we dat dan precies? Een simpele vuistregel is dat je in je header alleen maar declaraties opneemt, en geen definities en geen implementaties. Je kunt er bijvoorbeeld wel goed een definitie van een klasse opnemen. De volgende code zou goed in een header file voor een BKE bord passen: class bke_bord { public: void print ( ); void maak_leeg ( ); public: int bord[3][3]; }; // bke_bord
// misschien beter als constructor?
Voorbeeldprogramma 57: Boter, Kaas en Eieren, het bord We hebben hier een klasse bke_bord gedefinieerd die slechts 2 member-functies heeft (het voorbeeld is nogal simplistisch), namelijk print (om het bord af te drukken) en de welbekende maak_leeg ( ) om het bord “leeg” te maken (dat wil zeggen elk veld te vullen met 0). De klasse heeft eveneens 1 member-variabele, namelijk het 3 × 3 bord. We hebben echter nog niets gezegd over hoe de print functie ge¨ımplementeerd moet worden. Dat bewaren we voor de source-file. Die ziet er bijvoorbeeld als volgt uit: #include #include "bke_bord.h"
// lees de header file
void bke_bord::print ( ) { int i, j; for ( i = 0; i < 3; i++ ) { for ( j = 0; j < 3; j++ ) 73
cout << bord [i][j] << " "; cout << endl; } // for } // print void bke_bord::maak_leeg ( ) { int i, j; for ( i = 0; i < 3; i++ ) for ( j = 0; j < 3; j++ ) bord[i][j] = 0; } // maak_leeg In deze laatste file zouden we ook onze main functie op kunnen nemen (het mag ook in een andere file), om er een werkend programma van te maken. Bijvoorbeeld: int main ( ) { bke_bord b; b.maak_leeg ( ); b.print ( ); return 0; } // main Let er op dat in de implementatie file een #include plaatsvindt van de header file. Vanaf dat moment kunnen we de definities uit de header file gewoon gebruiken in de implementatie. Probeer zelf ook eens wat header files te schrijven en die te gebruiken in je implementaties. Begin simpel en probeer langzaam ingewikkelder headers te schrijven. (Wat moet je bijvoorbeeld doen als je in een header file voor een klasse, de definitie van een andere klasse nodig hebt?)
6.3 Meerdere header en meerdere source files We weten nu hoe we header en implementatie van elkaar scheiden. De volgende stap betreft het samenstellen van e´ e´ n executeerbaar programma uit meerdere header- en source-files. Met andere woorden, we willen (zoals in Hoofdstuk 6.1 al werd gesuggereerd) meerdere source bestanden apart compileren en deze gecompileerde programma’s uiteindelijk aan elkaar plakken voor het uiteindelijke programma. Dit aan elkaar plakken wordt linken genoemd. Het zal duidelijk zijn dat we slechts e´ e´ n main ( ) mogen gebruiken in ons programma. De overige files bevatten alleen de implementatie van specifieke functies en klassen en dergelijke. Deze files kunnen ieder wel gecompileerd worden, maar natuurlijk niet naar een executable. In plaats daarvan worden ze “zover gecompileerd als mogelijk is en zodanig dat ze later gemakkelijk aan elkaar gelinked kunnen worden”. De precieze terminologie is: zulke files worden gecompileerd naar object files. De extensie van object files is .o met g++ en .obj onder Visual C++. Laten we een voorbeeld bekijken. Stel we hebben een klasse bke_bord en een hieraan gerelateerde klasse array_van_borden (die alleen maar een array van 10 borden bevat). Deze klasse kan handig zijn wanneer we een spel “simultaan-BKE” willen implementeren. De bijbehorende klassen kennen definities die in header files staan. De header file bke_bord.h is bijvoorbeeld:
74
class bke_bord { public: void print ( ); // druk het bord af void maak_leeg ( ); // maak het bord leeg public: int bord[3][3]; }; // bke_bord Met andere woorden: dit is precies de bke_bord klasse uit Hoofdstuk 6.2. De headerfile array_van_borden.h wordt gegeven door: #include "bke_bord.h" // nodig voor declaratie van bke_bord class array_van_borden { public: void print_bord (int t); // print het t-de bord void maak_bord_leeg (int t); // maak het t-de bord leeg bke_bord bord_verzameling[10]; // de daadwerkelijke borden }; // array_van_borden De implementatie van deze files bestaat uit de twee bijbehorende source bestanden. Het bestand bke_bord.cc (of .cpp) hebben we hierboven eerder gezien en blijft onveranderd. Het source bestand array_van_borden.cc is niet heel anders en ziet er bijvoorbeeld zo uit: #include "array_van_borden.h" void array_van_borden::print_bord (int t) { bord_verzameling[t].print ( ); } // print_bord void array_van_borden::maak_bord_leeg (int t) { bord_verzameling[t].maak_leeg ( ); } // maak_bord_leeg Let erop dat we alleen de file array_van_borden.h “includen” en niet bke_bord.h, terwijl we wel gebruik maken van de functies van deze klasse. De reden waarom we deze header file niet hoeven te includen is dat deze include al gebeurt in array_van_borden.h. (Sommige mensen includen overigens alleen in .cc-files.) Tenslotte hebben we nog een derde source-file, en dat is het bestand dat main ( ) bevat. Let op: het programma hieronder doet eigenlijk nog niets — het declareert een variabele van klasse array_van_borden en verder niets. Laten we zeggen dat het bestand met main ( ) de naam prog.cc heeft en er als volgt uitziet: #include "array_van_borden.h"
// voor de definitie van array_van_borden
int main ( ) { array_van_borden mijn_borden; // declareer de borden ... } // main
75
6.4 Linking Nu hebben we vijf bestanden, prog.cc, bke_bord.cc, bke_bord.h, array_van_borden.cc en array_van_borden.h, die tezamen het programma vormen. Hoe combineren we ze nu precies? Vooraf moeten we e´ e´ n ding duidelijk maken: header files hoeven niet apart gecompileerd te worden. De reden is dat ze ge-include worden in de source bestanden. Dat betekent dat ze in de allereerste compilerstap letterlijk in de programma-tekst van de source bestanden worden gekopieerd (en daarna met de implementatie worden gecompileerd). Met andere woorden, alleen de source bestanden hoeven te worden gecompileerd. Op de verschillende operating systemen werkt het linken met wisselend gemak. 6.4.1
Visual C++
Bij het programmeren op een Windows-systeem met behulp van Visual Studio is het werken met meerdere files erg eenvoudig. Bij het toevoegen van een header- of sourcebestand kiest men voor de optie: project⇒add to project. Het bestand zal, als het ge-include wordt in het hoofdbestand of e´ e´ n van de al ge-include bestanden automatisch worden meegenomen bij het compileerproces. Denk er wel aan dat je voortaan de project file opent (.dsw) om verder te programmeren aan je project!! 6.4.2
Unix en de Makefile
Bij het werken op de Unix systemen is het noodzakelijk de verschillende compileerstappen via de commandprompt uit te voeren. De manier waarop we iets compileren naar een object (.o) file is met behulp van de compiler optie -c. Bijvoorbeeld als volgt: g++ -Wall -c prog.cc Dit vertelt de compiler dat hij niet hoeft te proberen er een executeerbaar programma van te maken. Het enige dat nodig is is een .o file die later makkelijk gelinked kan worden om het eindprogramma te vormen. Laten we dus eerst maar alle .cc bestanden compileren naar de corresponderende .o bestanden. g++ -Wall -c prog.cc g++ -Wall -c bke_bord.cc g++ -Wall -c array_van_borden.cc We hebben nu 3 .o bestanden gemaakt. Hoe worden deze gecompileerde bestanden vervolgens gelinked tot een werkend programma? Hiervoor kunnen we gewoon weer g++ gebruiken (maar nu zonder -c optie). Als we onze executable doe_sim_bke willen noemen, dan stellen we deze als volgt samen uit de drie object bestanden (de -o geeft aan dat de “output” doe_sim_bke moet heten): g++ -Wall prog.o bke_bord.o array_van_borden.o -o doe_sim_bke In principe hebben we nu veruit de belangrijkste aspecten behandeld van het samenstellen van een programma uit meerdere .h en .cc files. We zullen nu gaan kijken hoe we zoveel mogelijk
76
van dit proces kunnen automatiseren, zodat we niet steeds alle commando’s (zoals “g++ ...”) opnieuw in hoeven te typen. Stel dat je applicatie bestaat uit 50 files (dit is geen uitzondering in echte projecten), dan wordt deze handmatige compilatie snel vervelend. Een ander nadeel daarvan is dat het soms lastig is om te bepalen welke files je moet hercompileren wanneer je een van de bestanden wijzigt. Zelfs in het extreem eenvoudige voorbeeld uit de vorige paragraaf moet je even goed kijken voor dat duidelijk is. Een wijziging in bke_bord.cc heeft enkel gevolgen voor dit bestand zelf en zal alleen hoeven leiden tot hercompilatie van dit bestand, maar hoe zit het wanneer je een wijziging aanbrengt in bke_bord.h (bijvoorbeeld wanneer de naam van de methode “print ( )” wordt veranderd in “druk_af ( )”)? Het zal duidelijk zijn dat bke_bord.cc dan opnieuw gecompileerd (en zelfs zelf gewijzigd) moet worden, maar hoe zit het met de andere bestanden? Je moet goed kijken om te zien dat de methode print ( ) ook wordt aangeroepen in de file array_van_borden ( ) en dat deze dus ook gecompileerd moet worden. Als er meer bestanden zijn en de functies en klassen ingewikkelder worden, is dit alleen nog maar lastiger. Het zou mooi zijn als we konden aangeven welke .o files van welke bestanden afhangen. Onder UNIX wordt gebruik gemaakt van de/een Makefile om beide problemen op te lossen. Een Makefile geeft aan wat van wat afhangt en hoe je alles moet compileren. In Visual C++ wordt zo’n file automatisch gemaakt — deze kan je overigens wel bewerken! Een geavanceerde Makefile kan erg gecompliceerd zijn. In dit vak behandelen we alleen de meest elementaire aspecten ervan. Een voorbeeld van een eenvoudige Makefile vind je hieronder: # Alles wat begint met ’#’ is commentaar (analoog aan ’//’ in C++). # # # #
De volgende regel geeft aan wat er allemaal ’gemaakt’ moet worden. In dit geval is dat slechts 1 applicatie, maar het mogen ook meerdere executables zijn - deze scheidt je dan met een spatie. De ’all:’ regel geeft de ultieme ’targets’ van deze Makefile
all: doe_sim_bke # # # # # #
Om het programma ’doe_sim_bke’ te maken hebben we nodig: prog.o, bke_bord.o en array_van_borden.o. Dat geven we aan met de ’target’-naam gevolgd door een ’:’, en de namen van de bestanden die nodig zijn om deze file te maken. De regel eronder geeft aan hoe, als we die bestanden eenmaal hebben, de ’target’ van deze regel gebouwd kan worden (gebruik ‘tabs’ om in te springen!).
doe_sim_bke: prog.o bke_bord.o array_van_borden.o g++ -Wall prog.o bke_bord.o array_van_borden.o -o doe_sim_bke # de regel hierboven begint dus met een tab!!! # prog.o hangt alleen af van prog.cc en array_van_borden.h prog.o: prog.cc array_van_borden.h g++ -Wall -c prog.cc
77
# bke_bord.o hangt alleen af van bke_bord.cc en bke_bord.h bke_bord.o: bke_bord.cc bke_bord.h g++ -Wall -c bke_bord.cc # array_van_borden.o hangt af van: # 1. array_van_borden.cc # 2. array_van_borden.h, EN # 3. bke_bord.h (!) array_van_borden.o: array_van_borden.cc array_van_borden.h bke_bord.h g++ -Wall -c array_van_borden.cc Bovenstaande Makefile geeft als het ware het “recept” voor het bouwen van de applicatie doe_sim_bke. Als je nu make intypt op de command line, dan wordt de Makefile gelezen en het recept gevolgd om de applicatie te bouwen. De make tool gaat bijvoorbeeld eerst prog.cc, array_van_borden.cc en bke_bord.cc compileren (want volgens het recept zijn die nodig voor doe_sim_bke). De make tool begrijpt de afhankelijkheden die je in het recept hebt aangegeven. Als je bijvoorbeeld een wijziging aanbrengt in bke_bord.h, dan zorgt hij er voor dat automatisch de regels voor bke_bord.o en array_van_borden.o worden uitgevoerd. En omdat deze .o files wijzigen en het recept aangeeft dat de applicatie doe_sim_bke daarvan afhankelijk is, dan zal vervolgens deze regel ook uitgevoerd worden. Het resultaat is dat je een gestructureerde hercompilatie krijgt, waarbij de afhankelijkheden automatisch in het oog worden gehouden. Een laatste opmerking over Makefiles. Het is vaak handig om in een directory met schone lei te beginnen. Dat wil zeggen dat je dan af wil van allerlei executables en object files die daarin misschien al aanwezig zijn. Een handige manier om dat te doen in Makefiles is het opnemen van een clean regel (onderaan) in de Makefile. De clean regel ziet er dan bijvoorbeeld uit zoals hieronder: clean: rm -f *.o doe_sim_bke Wat hier staat is dat er een target clean is die nergens van afhankelijk is. Wat er moet gebeuren om deze target te “halen” is het verwijderen (“removen”) van alle files die eindigen op .o en ook de file doe_sim_bke. Je kunt deze target expliciet laten maken door het volgende commando: make clean Hiermee zijn we aan het eind gekomen van dit hoofdstuk. Het verdient ten zeerste aanbeveling om eens met de stof uit dit hoofdstuk te oefenen. Schrijf zelf een paar Makefiles en kijk eens naar manieren om je programma op een nette wijze onder te brengen in meerdere bestanden.
78
7 Grafische interfaces In dit hoofdstuk gaan we kijken naar grafische schermuitvoer. We zullen dit doen aan de hand van het bekende spel Boter-Kaas-en-Eieren (afgekort BKE). We zullen een grafische interface maken die het spelen van het spel door twee spelers mooi weergeeft. Er wordt een speelbord op het scherm gezet, en men kan zetten doen door te klikken op een bepaald veld, waarna de eigen kleur en/of teken verschijnt. Onze programma’s tot nu toe waren prima wat betreft de functionaliteit, maar qua uitvoer leken ze in het geheel niet op de programma’s die mensen gewoonlijk op hun computers gebruiken. De in- en uitvoer bestonden uit simpele karakters, terwijl de meeste praktijkprogramma’s gebruik maken van windows, buttons, etcetera. Wat we in dit hoofdstuk gaan doen is een heel eenvoudige graphical user interface, of GUI (een grafische schil) bouwen om ons Boter-Kaas-en-Eieren spel (BKE). Dit hoofdstuk is alleen maar bedoeld als eerste kennismaking met het ontwikkelen van GUIs (meer informatie wordt gegeven in een ander vak). Als je eenmaal gezien hebt hoe de basiselementen gemaakt kunnen worden, zou het redelijk eenvoudig moeten zijn om hier zelf verder mee te spelen. Een andere reden om je te laten werken met een pakket waarmee je grafische interfaces programmeert is dat tegenwoordig steeds meer mensen gebruik maken van “development studio’s”, zoals het hier gebruikte Visual Studio 6.0. Andere voorbeelden hiervan zijn .net, Delphi, Kdeveloper, etc.
7.1 Visual C++ Als voorbeeld zullen we onze GUIs maken op Windows machines, met behulp van het pakket Visual C++ 6.0. Deze ontwikkelomgeving staat ge¨ınstalleerd op een flink aantal studenten-PC’s. Waarom Windows en waarom Visual C++? Het maakt eigenlijk niet uit welk operating systeem je gebruikt. In principe is Linux ook een prima omgeving voor het ontwikkelen van GUIs en de ondersteuning in pakketten zoals QT designer lijkt in alle opzichten sterk op wat we in dit hoofdstuk behandelen. Het grote voordeel van Windows is dat het over de hele wereld door iedereen gebruikt wordt. Bedrijven, je huisgenoten en je ouders zijn makkelijk in staat programma’s te gebruiken die op het Windows systeem ontwikkeld zijn. Zo kan je omgeving ook eens zien wat je allemaal kunt. Visual Studio is een professionele omgeving zoals ook bij bedrijven gebruikt wordt om software te ontwikkelen. Ervaring hiermee kan dus bijzonder nuttig zijn. Het is de voorloper van het nieuwere .NET, maar wordt zelf nog volop in de verschillende bedrijven gebruikt. Kennis van Visual Studio, waar Visual C++ onderdeel van is, maakt het daarnaast sneller mogelijk over te stappen naar .NET. Compileren werkt eenvoudig en veroorzaakt geen overhead, zoals het gebruik van makefiles. De executable (de .exe file) is makkelijk te kopi¨eren en overal te gebruiken. Eigen projecten zien er al snel herkenbaar en dus professioneel uit. Desalniettemin benadrukken we dat je hetzelfde kunt bereiken met andere operating systemen en met andere pakketten. Visual C++ start je makkelijk via het Windows startmenu. Het is een programma waarmee het ontwerpen en bouwen van grafische user interfaces eenvoudig wordt gemaakt. Je werkt grotendeels in een grafische omgeving waarbij je knoppen, menu’s, tekstvelden en dergelijke, naar een canvas (een tekenveld) kunt slepen om daar — grafisch — je GUI mee samen te stellen. De grafische applicatie is op dezelfde manier te starten als de command line programmatuur, zonder extra stappen. Natuurlijk kan je eenvoudig je eigen functies, objecten enzovoorts met de interface integreren via de welbekende editor (zodat, bijvoorbeeld, een druk op een bepaalde 79
knop bij een BKE (Boter, Kaas en Eieren) interface het bord leegmaakt voor een nieuw spel). We zullen nu eerst laten zien wat voor applicatie we in dit hoofdstuk willen bouwen en daarna gaan we kijken hoe we dit voor elkaar kunnen krijgen met behulp van Visual C++.
7.2 De BKE applicatie Wat we zullen bouwen in dit hoofdstuk als voorbeeld-applicatie is een GUI die er ongeveer uitziet zoals weergegeven in Figuur 5.
Figuur 5: Een GUI voor het BKE spel.
De GUI zoals die wordt gebouwd in dit hoofdstuk is niets anders dan een vervanging van pen en papier: het laat twee spelers om de beurt een zet doen door een veld aan te klikken op een simpele representatie van een BKE bord. Wanneer Speler 1 een veld aanklikt wordt dit rood ingekleurd en gevuld met een zwart kruis. Als Speler 2 een veld aanklikt, dan wordt dit groen gemaakt en komt er een rondje in te staan. Een druk op de “maak leeg” knop (in Figuur 5 Leeg veld) zorgt ervoor dat het bord wordt leeggemaakt, zodat een nieuw spel gespeeld kan worden. Om het simpel te houden bouwen we geen functionaliteit in die bepaalt of een van de spelers heeft gewonnen (dat moeten de spelers zelf maar doen), en beperken we ons tot twee menselijke spelers, hoewel het vrij gemakkelijk is een en ander zodanig in te passen dat we een echte computerspeler hebben. Het is de bedoeling hier zelf wat mee te experimenteren in het kader van de vierde programmeeropgave.
7.3 Een nieuw project starten Start Visual C++ op en kies voor File⇒New. Als het goed is zie je nu het scherm van Figuur 6.
80
Figuur 6: Visual C++: een nieuw grafisch project.
Ga naar het tabblad Projects en kies voor de MFC AppWizard (exe). Vul rechts bovenin in dat het nieuwe project BKE gaat heten en kies voor een locatie waar de nieuwe projectmap komt te staan. Hierin komen de bestanden voor de nieuwe applicatie. Klik op OK om te beginnen met een standaard grafische applicatie. Voer nu de stappen uit zoals aangegeven in Figuur 7.
Figuur 7: Visual C++: de Project Wizard.
Kies in het eerste scherm voor Dialog based. We maken namelijk een applicatie met een eenvoudig schermpje, waar we geen documenten of iets dergelijks in gaan laden (zoals bij Word of NEdit). In het tweede schermpje geven we aan dat we geen About box willen en dat ons window “Boter Kaas en Eieren” gaat heten. Op het derde scherm zetten we automatisch gegenereerd commentaar uit. Klik nu op Finish om te beginnen met je applicatie. Selecteer op het op het scherm verschenen canvas eerst de TODO-tekst door erop te klikken en druk drie keer 81
op DEL om alle standaard schermelementen weg te gooien: we willen beginnen met een leeg tekenveld (canvas). We zien nu het scherm ongeveer zoals weergegeven in Figuur 8.
Figuur 8: Visual C++: het hele scherm
Links van het midden (of elders) staat de kolom met de meest gebruikte windows controls (schermelementen). Hier kunnen we straks de velden van het speelbord, de knop en het tekstveld mee tekenen. Links daarvan een window dat we al eerder zagen, maar nu ook gaan gebruiken om op verschillende manieren naar de applicatie te kijken. Bovenaan staan weer de bekende compileerknoppen. Probeer deze lege applicatie maar eens te compileren en uit te voeren. Op het scherm verschijnt nu een, niet zo interessant, leeg window. Sluit dit ook weer af. Het binnenhalen van een bestaand project gaat weer met File⇒Open Workspace (hier BKE.dsw). Het is uiteraard verstandig om regelmatig te saven (bijvoorbeeld met File⇒Save All). Mocht de Controls balk per ongeluk weggeklikt zijn, dan kun je die terugkrijgen door rechtsboven op de achtergrond te klikken met de rechtermuisknop en Controls aan te vinken. Het dialog window kun je terugvinden via het ResourceView tabblad: open BKE resourses en dubbelklik IDD_BKE_DIALOG.
82
7.4 Controls en resources toevoegen Nu komt het leuke deel van het bouwen van de interface: het plaatsen van de verschillende onderdelen van de interface, en het maken van een aantrekkelijk ontwerp. We willen een GUI voor het BKE spel en we hebben gezegd dat we zoiets willen als weergegeven in Figuur 5. Deze GUI bestaat uit 9 velden, een “maak leeg” knop en een tekst die aangeeft welke speler aan de beurt is. De 9 velden zijn eigenlijk gewoon plaatjes (leeg, kruisje, rondje) die we clickable (indrukbaar) maken — net zoals bijvoorbeeld plaatjes op een website. Nadat er op een plaatje geklikt is moet de inhoud veranderen. We gaan dus een interface opbouwen die bestaat uit 9 picture controls, 1 static text en 1 button control — en misschien nog een UnDo knop. Om ervoor te zorgen dat we de controls goed op het scherm kunnen positioneren zetten we eerst de grid aan. Kies voor Layout⇒Guide Settings en kies voor de optie Grid. We kunnen de controls nu makkelijk uitlijnen. Als eerste gaan we de plaatjes toevoegen voor ons BKE spel. Deze willen we namelijk het liefste meecompileren in e´ e´ n enkele executable. Zet de linkerbalk op resources-view met behulp van het middelste tabblad:
Figuur 9: Visual C++: ResourceView
Resources zijn alle aan de code toegevoegde elementen zoals plaatjes, geluid, een menuutje of verschillende talen. Kies om de plaatjes toe te voegen voor Insert⇒Resource en klik op Bitmap. Je kunt de plaatjes hier eenvoudig zelf maken via de optie New; liefhebbers kunnen ook bestaande plaatjes gebruiken via Import (zie Figuur 10).
Figuur 10: Visual C++: Resources toevoegen
De plaatjes worden opgeslagen onder de naam IDB_BITMAP1, etc. Het lijkt wenselijk de plaatjes een duidelijkere naam te geven. Open hiertoe het Properties window (rechtsklik⇒Properties). 83
Figuur 11: Visual C++: Het Properties window
We noemen de plaatjes respectievelijk IDB_cross, IDB_round en IDB_empty. Klik op de verschillende plaatjes in het Resource scherm om dit via het Properties window te bewerkstelligen. Keuzes hoeven hierbij niet met ENTER of iets dergelijks bevestigd te worden. Het Resource window (waarin IDB_BITMAP3 nog niet is hernoemd) ziet er nu zo uit:
Figuur 12: Visual C++: Plaatjes toegevoegd
We kunnen nu in e´ e´ n keer de hele interface opbouwen. Laten we beginnen met de static text control1 . Selecteer in de Controls balk de static text control en zet/sleep die op het form (canvas). We zien nu een tekst op het scherm verschijnen. Verander de naam van het veld via het inmiddels bekende property window in IDC_message en de caption (de inhoud) in Speler 1 is aan de beurt. Met het styles tabblad in het Property window kan de tekst gecentreerd worden. Voeg nu een button toe. Noem deze IDC_maakleeg en zet de inhoud op Begin opnieuw. Als laatste voegen we de 9 speelvelden (pictures) toe. Zet/sleep een picture op het scherm en geef het een naam. We zullen de vakjes benoemen volgens het co¨ordinatensysteem; ons eerste vakje heet dus IDC_11 en het laatste IDC_33. Zet het type op Bitmap en selecteer als Image (beginplaatje) IDB_empty. Geef bij het Styles tabblad aan dat we gebeurtenissen met het plaatje (in ons geval is dat aanklikken door de gebruiker) door willen geven door het Notify vakje aan te vinken. Herhaal dit negen keer. Onze interface is nu compleet en ziet er ongeveer zo uit als het linker plaatje: 1 Door
je muis-pointer even op een icon te laten rusten, laat je zogenaamde tooltips verschijnen: deze geven in enkele woorden aan wat het icon is of doet.
84
Figuur 13: Visual C++: Onze interface
Omdat alles er nog lelijk uitziet verplaatsen en verkleinen of vergroten we de controls nog even netjes zodat het eruit gaat zien als het rechter plaatje hierboven. Dit gaat op de bekende sleep manier (sleep de randjes om de grootte aan te passen, sleep de control zelf om te verplaatsen). Dit gaat makkelijk met behulp van de grid. Onze interface is nu af.
7.5 Tussen interface en code De communicatie tussen de interface en de code verloopt op twee verschillende manieren. Voor de real-time communicatie bestaan er signals. Dit zijn bepaalde gebeurtenissen die gestart worden door iets wat er op het scherm gebeurt. Denk hierbij aan het veranderen van een tekstveld of het indrukken van een knop. Bij sommige controls worden de signals altijd doorgestuurd, zoals bijvoorbeeld bij knoppen of selectievakken. Bij andere controls moet je expliciet aangeven dat je wilt dat dat gebeurt, zoals we net al deden bij de images door het aanvinken van Notify. Vaak worden signals gegeven op het moment dat de gebruiker klaar is met invoeren of een bepaalde optie gekozen heeft. Om uit te vinden w´at de gebruiker dan vermeld of gekozen heeft is het noodzakelijk de status van sommige controls uit te lezen. Andersom is het soms noodzakelijk bepaalde zaken op het scherm vanuit het programma te veranderen — bijvoorbeeld ons bericht welke speler aan de beurt is, of het veranderen van een leeg vakje in een kruisje. Het uitlezen of aanpassen van de status van een control gaat via speciale member-variabelen. 7.5.1
Het koppelen van controls aan membervariabelen
De gekoppelde membervariabelen beginnen meestal met m_. Het voorbeeld hieronder laat zien hoe we de inhoud van een tekstvak control met behulp van zo’n variabele kunnen manipuleren. 85
Stel dat het tekstvak ingevuld is met: Clinton // Laad de inhoud van het scherm in de variabelen UpdateData (true); // m_tekstvak bevat nu "Clinton" string Naam = m_tekstvak; // Naam is nu "Clinton" m_tekstvak = "Bush"; // m_tekstvak is nu "Bush" UpdateData (false); // Op het scherm staat nu in het tekstvak "Bush" Updates vinden dus plaats via de functie UpdateData (...). In het kort wordt het scherm in het systeem geladen door true als argument mee te geven. Het systeem wordt naar het scherm geschreven met behulp van false. Hoe maken we nu die gekoppelde membervariabelen? Kies voor View⇒ClassWizard en selecteer het tabblad Member Variables. We zien nu het volgende scherm:
Figuur 14: Visual C++: De Class Wizard Als eerste gaan we een variabele aan het tekstvak (IDC_message) koppelen. Klik het tekstvak aan en druk op Add Variable. Geef het de naam m_message (gewoon dezelfde naam kiezen is het makkelijkst). Omdat we hier de inhoud van willen aanpassen kiezen we voor het type of category Value en vervolgens klikken we op OK. De variabele m_message is nu aangemaakt. Met de status van de knop (IDC_maakleeg) willen we niets doen dus hiervoor is geen membervariabele noodzakelijk. Voor de speelvelden doen we hetzelfde als hierboven alleen kiezen we 86
dan voor Control in plaats van Value als type — het inladen van een plaatje doe je op control niveau. Nu hebben alle noodzakelijke controls een koppeling in de code. Nu moeten we alleen nog de signals afvangen. 7.5.2
Het koppelen van signals aan code
Het koppelen van signals aan code gaat eenvoudig via de ClassWizard. Kies in dat geval voor het tabblad Message Maps. Omdat aanklikken de meest standaard handeling is die voorkomt is het koppelen van dat signal nog makkelijker gemaakt. Dubbelklik op de knop waarmee spelers opnieuw beginnen (maakleeg). Het volgende scherm verschijnt:
Figuur 15: Visual C++: Signals afvangen
Accepteer de suggestie en de code-editor verschijnt, waarbij de cursor in een nieuwe functie staat. Deze functie wordt aangeroepen als er op de betreffende button geklikt wordt. We kunnen nu beginnen met het maken van de functionaliteit.
7.6 Het invullen van de functionaliteit We zijn nu een heel eind op weg. We hebben (1) de vorm van de GUI ontworpen, (2) controls en signals aan de code gekoppeld. Dat betekent dat het eigenlijke GUI ontwerpgedeelte zo goed als af is. We moeten alleen nog de echte acties “invullen” en hiervoor dienen we zelf de daarbij behorende C++-code schrijven. Omdat we bitmaps via zogeheten CBitmap variabelen moeten inlezen maken we eerst 3 variabelen die de genoemde plaatjes gaan bevatten. Dit doen we in de FileView modus die we kunnen kiezen bij de tabbladen van de linker zijbalk. Ga naar de header file van onze interface, BKEDlg.h (dubbelklik). Hier voegen we eerst aan de klasse CBKEDlg bovenaan bij public de volgende code toe: CBitmap cross; CBitmap round; CBitmap empty; int speler; We hebben nu drie nieuwe member-variabelen van ons form die de plaatjes voorstellen. Daarnaast hebben we de variabele die bijhoudt welke speler aan de beurt is. In de file BKEDlg.cpp voegen we aan de constructor van diezelfde klasse, CBKEDlg::CBKEDlg de volgende regels toe:
87
cross.LoadBitmap (IDB_cross); round.LoadBitmap (IDB_round); empty.LoadBitmap (IDB_empty); speler = 1; De plaatjes zijn nu ge¨ınitialiseerd en we beginnen met speler 1. Om ervoor te zorgen dat ons tekstvak ook op de goede stand begint veranderen we hier ook m_message = _T(""); in m_message = "Speler 1 is aan de beurt"; Nu naar de functionaliteit van onze knop om opnieuw te beginnen: de functie Onmaakleeg ( ). De code hiervoor wordt nu heel eenvoudig: m_11.SetBitmap m_12.SetBitmap m_13.SetBitmap m_21.SetBitmap m_22.SetBitmap m_23.SetBitmap m_31.SetBitmap m_32.SetBitmap m_33.SetBitmap
(empty); (empty); (empty); (empty); (empty); (empty); (empty); (empty); (empty);
m_message = "Speler 1 is aan de beurt"; speler = 1; UpdateData (false); Nu rest ons slechts de functie te maken die een daadwerkelijke zet doet. Ga naar de class-view in de linkerbalk en rechtsklik op de CBKEDlg klasse. Kies voor Add Member Function en vul het scherm als volgt in:
Figuur 16: Visual C++: Member-functie toevoegen In CBKEDlg.cpp staat nu de functie klaar. Vul de volgende code in. Er valt duidelijk te zien hoe deze werkt. void CBKEDlg::doezet (CStatic *metdeze, CString & berichtje) { if ( speler == 1 ) { metdeze->SetBitmap (cross); 88
speler = 2; berichtje = "Speler 2 is aan de beurt"; }//if else { metdeze->SetBitmap (round); speler = 1; berichtje = "Speler 1 is aan de beurt"; }//else UpdateData (false); }//CBKEDlg::doezet We roepen deze functie als volgt aan: doezet (&m_12, m_message); We dubbelklikken nu op alle plaatjes en vullen de functies in BKEDlg.cpp met de respectievelijke doezet aanroepen. Na compileren zijn we klaar met onze simpele BKE applicatie! Kijk maar eens hoe het programma werkt en probeer te ontdekken waar het verbeterd kan worden.
7.7 Koppelen van de echte BKE functionaliteit In dit hoofdstuk gaan we stap voor stap het niet grafische BKE programma van Hoofdstuk 6.2 overzetten naar de zojuist gemaakte grafische schil, zodat het programma ook echt doet wat het moet doen — niet twee keer hetzelfde veld klikken, kijken of er gewonnen is, etc. De klasse die we zullen gebruiken ziet er ongeveer als volgt uit: class BKEbord { public: int bord[4][4];
// de huidige stand
BKEbord ( ) { nieuwspel ( ); }; // constructor bool gewonnen (int & wie); // heeft iemand gewonnen (en wie?) void nieuwspel ( ); // maakt veld leeg en speler 1 begint bool magzet (int wie, int i, int j); // mag wie op (i,j) zetten? bool doezet (int i, int j); // doe als het mag een zet op veld (i,j) };//BKEbord Deze klasse staat in de file bkebord.h. De definities van deze functies staan zoals gebruikelijk in bkebord.cpp, maar we zullen niet op de verdere inhoud hiervan ingaan. We laten nu zien hoe we deze integreren in de BKE applicatie. We zullen de computer de zetten voor Speler 2 laten doen. Er moeten enkele dingen daartoe iets anders dan boven. 1. Voeg de files toe aan het BKE project door Project⇒Add To Project⇒Files te kiezen en de .h en .cpp files te selecteren. 2. Een tweede belangrijke stap is het toevoegen van #include "stdafx.h" helemaal aan het begin van de file bkebord.cpp. Dit is nodig voor alle grafische applicaties. 3. Voeg v´oo´ r de klasse BKEDlg in BKEDlg.h de include toe: 89
#include "bkebord.h" De files zijn nu allemaal aan elkaar gelinkt. 4. Verwijder de member-variabele speler uit BKEDlg.h en BKEdlg.cpp; nu we de klasse BKEbord gaan gebruiken hebben we deze niet meer nodig. Voeg in BKEDlg.h deze klasse als volgt in de klasse BKEDlg als membervariabele toe: BKEbord hetbord; 5. We maken een nieuwe functie void zetbord ( ) die het hele speelbord van de interface vult, afhankelijk van de inhoud van het daadwerkelijke bord in de code: void CBKEDlg::doezet2 (CStatic *vakje, int wat) { switch (wat) { case 0: vakje->SetBitmap (empty); break; case 1: vakje->SetBitmap (cross); break; case 2: vakje->SetBitmap (round); break; }//switch }//CBKEDlg::doezet2 void CBKEDlg::zetbord ( ) { doezet2 (&m_11,hetbord.bord[1][1]); doezet2 (&m_12,hetbord.bord[1][2]); doezet2 (&m_13,hetbord.bord[1][3]); ... m_message = "Leuk bericht"; UpdateData (false); }// CBKEDlg::zetbord
6. We kunnen nu de functie veranderen die het bord leegmaakt. Deze wordt nu: hetbord.nieuwspel ( ); zetbord ( );
7. Als laatste veranderen we de functies voor de spelvelden als volgt, bijvoorbeeld voor veld (2,3): int wie = 1; if ( hetbord.magzet (wie,2,3) ) { hetbord.doezet (2,3); zetbord ( ); if ( hetbord.gewonnen (wie) ) { 90
if ( wie == 1) m_message = "Speler 1 wint"; else if ( wie == 2 ) m_message = "Speler 2 wint"; else m_message = "Remise"; }//if else ... computerzet ... UpdateData (false); }//if
Als je veel knoppen hebt, bij een “groot” speelveld, moet je deze functie dus nogal vaak intikken. Het is dan handig om een extra functie te maken, met de coordinaten als parameters, die je bij iedere knop kunt aanroepen. Nadat we dit bij alle knoppen hebben gedaan kunnen we de applicatie compileren. Onze volledige BKE applicatie is nu klaar en kan gebruikt worden. Zoals gezegd is het makkelijk de applicatie mee te nemen naar een andere machine (Laat het ze thuis ook eens zien!). Kopieer hiertoe de .exe file in de debug map. Probeer zelf ook eens een leuk icoontje te maken voor je nieuwe applicatie en uit te zoeken hoe je dat aan je nieuwe applicatie koppelt. Je kent nu de basis van grafisch programmeren. In de praktijk komt er echter nog veel meer bij kijken, maar oefening baart kunst. Succes!
91
8 Richtlijnen bij programmeeropgaven Een belangrijke taak van de programmeur is ervoor te zorgen dat zijn of haar code begrijpelijk is. Bij Programmeermethoden moet je code tenslotte nagekeken worden en ook later, bijvoorbeeld bij een bedrijf, heb je meestal collega’s die willen begrijpen wat jij gedaan hebt. En later wil je je eigen code ook nog steeds snappen. Verschillende dingen kunnen ervoor zorgen dat code begrijpelijk is: een nette layout, goed commentaar en een goede modulariteit. Wat voor richtlijnen wij hierbij hanteren, is hieronder kort toegelicht. Uiteraard is over deze regels discussie mogelijk.
8.1 Commentaar • In principe moet op alle gebruikte variabelen commentaar gegeven worden. Alleen als het commentaar triviaal zou zijn, mag het achterwege gelaten worden. Een voorbeeld van noodzakelijk commentaar is: int i; // teller voor het aantal pogingen Overbodig commentaar is: int pogingteller; // teller voor het aantal pogingen Zoals uit dit voorbeeld blijkt, is commentaar uit te sparen door duidelijke namen voor variabelen te kiezen. Door duidelijke namen te gebruiken wordt de verdere C++ code bovendien ook veel leesbaarder. • Bij elke functie moet commentaar staan dat de bedoeling van de functie toelicht. De betekenis van elke parameter moet uitgelegd worden. Probeer een zin (of misschien twee) te maken die de werking beschrijft in termen van de parameters. Geef zoveel mogelijk aan waarom parameters een bepaald type hebben. • Bovenaan elk C++ bestand moet commentaar staan. Dit commentaar moet ten minste bevatten: – de naam van de auteur(s); – de naam van het bestand; – wat het programma(onderdeel) doet; – welke compiler(s) en programma(s) gebruikt zijn om het bestand te maken en te testen; – de datum waarop (voor het laatst) aan het bestand gewerkt is.
92
8.2 Layout • Maak de regels niet te lang. Een maximum van 70 karakters per regel zorgt er voor dat op iedere printer en op (bijna) ieder beeldscherm de regels niet afgebroken worden. • De declaraties van variabelen staan bovenaan de functie(s); main is ook een functie! • Alle instructies die binnen een if, while, else, do, for, switch of class vallen, alsmede alle instructies die binnen functies staan, moeten ingesprongen worden ten opzichte van die if, while, etc. als ze bij die die if, while, etc. horen. De volgende layout is fout: if ( k == 0 ) k++; De volgende layouts zijn acceptabel: if ( k == 0 ) k++; else if ( j == 0 ) j++; of if ( k == 0 ) k++; else if ( j == 0 ) j++; • Bij functies zijn verschillende mogelijkheden: int doewat (int x) { return x-1; } // doewat of int doewat (int x) { return x-1; } // doewat • Een regel bevat niet meer dan twee instructies, en doorgaans niet meer dan e´ e´ n. • De layout moet consequent zijn, bijvoorbeeld: – waar ingesprongen wordt, moet overal evenveel ingesprongen worden. Fout is: 93
if ( k == 0 ) k++; if ( l == 1 ) l++; De laatste regel is namelijk iets meer ingesprongen dan de tweede regel. – als in een situatie ingesprongen wordt, moet bij voorkeur in alle “vergelijkbare” situaties ook ingesprongen worden. “Vergelijkbaar” moet niet al te streng opgevat worden. Ter illustratie, de volgende layout is niet erg mooi omdat in “vergelijkbare” situaties niet op dezelfde manier ingesprongen wordt: if ( k == 0 ) k++; if ( l == 1 ) k++; Enkele “overtredingen” van dit criterium worden meestal getolereerd. Te zien is overigens dat de variabele l lastig van de 1 te onderscheiden is! – Accolades staan bij voorkeur altijd op “dezelfde” plaats. Niet mooi, want inconsequent, is: if ( k == 0 ){ k++}; if ( l == 1 ) { l++; } Ook hier worden enkele “overtredingen” meestal getolereerd.
8.3 Modulariteit • Er moeten zo min mogelijk globale variabelen gebruikt worden, liefst 0. • Gebruik zoveel mogelijk geschikte functies. • Maak de functies niet te lang: ze zouden op een klein beeldscherm (in e´ e´ n klein window) goed te volgen moeten zijn. • Splits grote programma’s in meerdere files.
8.4 Conclusie Ten overvloede tot besluit nog: deze richtlijnen zijn er niet om studenten te pesten! Kortom: ze zijn er voor ieders bestwil. Een klein voorbeeld tot besluit. De fout in de volgende stukjes code is niet direct te zien door de slechte layout: while ( k < 10 ) cout << k; k++;
while ( k < 10 ) cout << k; k++;
94
9 Opgaven 1. Geef type en zo mogelijk de waarde van de volgende uitdrukkingen. Hierbij zijn p, q, r en s variabelen van type bool, en k van type int. a. d. g. h. k. l. m.
sqrt (4) b. sqrt (4.0) c. ’t’ - ’e’ ceil (-99.9) e. - floor (99.9) f. - floor (-99.9) !(p && q) == !(!p && !q) 10 % 3 i. 10 / 3 j. 126 / 3 % 5 ( p && (q && !q) ) || !( r || (s || !s) ) ( floor (-65.3) < fabs (-65.3) ) && p odd (k) || odd (k+1)
2. a. Schrijf een C++-programma dat de gebruiker om een temperatuur in graden Fahrenheit als invoer vraagt. Na het inlezen hiervan wordt deze temperatuur omgerekend in graden Celsius, waarna beide getallen afgedrukt worden. Gebruik: Temp(in Celsius) = (5/9) ∗ (Temp(in Fahrenheit) – 32). b. Idem, maar nu mag alleen met gehele getallen gerekend worden. In dit geval moet er dus afgerond worden. 3. Schrijf een C++-programma dat het aantal seconden vanaf middernacht aan de gebruiker vraagt en de tijd uitvoert als: ’uren:minuten:seconden’. Probeer ook eens uit zoeken hoe je de tijd uit het computersysteem kunt aflezen via C++. 4. Wat is het grootste gehele getal dat in C++ in een int past? Waarom dit getal? Hangt dit af van de C++-implementatie? En hoe staat het bij een long? Wat gebeurt er als je 1 optelt bij het grootste te representeren getal? Wat is het grootste getal dat in een double past? En het kleinste positieve (groter dan nul) getal? 5. Geef kritiek op de het volgende stukje C++, waarbij de variabele doorgaan van het type bool is: if ( doorgaan = true ) ... 6. a. Laat zien dat elk do-while-statement herschreven kan worden met behulp van if- en while-statements. b. Laat zien dat elk while-statement herschreven kan worden met behulp van if- en dowhile-statements. Kan het ook zonder if-statements? 7. Een slecht geschreven C++-programma bevatte het volgende statement: if ( a < b ) if ( c < d ) x = 1; else if ( a < c ) if ( b < d ) x = 2; else x = 3; else if ( a < d ) if ( b < c ) x = 4; else x = 5; else x = 6; else x = 7;
95
a. Herschrijf dit statement; gebruik een betere layout. b. Staan er overbodige of tegenstrijdige condities in? c. Schrijf een eenvoudiger statement dat hetzelfde effect heeft. 8. Schrijf een programma dat drie gehele getallen inleest en deze in volgorde van grootte afdrukt. Geef enkele verschillende methoden. Zo kunnen de getallen alleen op het beeldscherm gesorteerd afgedrukt worden, maar ook intern in het programma gesorteerd worden. 9. Schrijf een programma dat een geheel getal n inleest, en vervolgens (als tenminste n ≥ 0) n! = n ∗ (n − 1) ∗ . . . ∗ 2 ∗ 1 berekent. Als n < 0 moet er een passende foutmelding afgeleverd worden. Gebruik hierbij: a. het while-statement, b. het for-statement, c. het do-while-statement. Welke mogelijkheid levert het “beste” programma? Schrijf ook een functie (zonder recursie) die n! berekent. 10. Schrijf een functie spaties (int aantal) die aantal spaties op het beeldscherm zet. 11. Omschrijf een klasse-structuur voor de volgende situaties: a. een paar re¨ele co¨ordinaten met een plaatsnaam, b. een studentenadministratie op een faculteitsburo, c. idem, voor het sportcentrum. Stel dat voor de situatie van b een (groot) programma geschreven moet worden om de studentenadministratie bij te houden. Geef de benodigde functie-headings, met commentaar. 12. Schrijf een programma dat als invoer om een rij positieve getallen vraagt, afgesloten door een getal kleiner dan of gelijk aan nul. Vervolgens moeten het maximum, het minimum en het gemiddelde van deze getallen (het laatste getal niet inbegrepen) bepaald worden. Is het for-statement of het while-statement beter geschikt? 13. Schrijf een programma dat voor elk bedrag kleiner dan een euro het kleinste aantal munten bepaalt dat samen dit bedrag oplevert. Gebruikt mogen worden: munten van e´ e´ n, twee, vijf, tien, twintig en vijftig eurocent. De gebruikte munten moeten ook worden afgedrukt. 14. Schrijf een programma dat uitdrukkingen als 56-664-77+2-888; inleest en berekent. Elk (geheel) getal wordt voorafgegaan door een teken, terwijl de hele uitdrukking door een punt-komma wordt afgesloten. Schrijf ook een versie die echt karakter voor karakter inleest (met kar = cin.get ( );). 15. Schrijf een programma dat voor gegeven gehele n het volgende berekent: A(n) = 1/2 + 2/4 + 3/8 + 4/16 + . . . + n/2n . Gebruik een functie; maak hierbij geen aparte functie voor machtsverheffen. Maakt het overigens uit in welke volgorde de sommatie berekend wordt? 96
16. Voorspel de uitvoer van de volgende twee programma’s: #include using namespace std; int iets; void wat (int& a, int& b) { a = -1; b = -2 * a; cout << a << b << endl; } // wat int main ( ) { iets = 1; wat (iets,iets); cout << iets << endl; return 0; } // main
#include using namespace std; int iets; void bla (int &a, int & b) { a = 10 * b + iets / 2; cout << a << b << endl; } // bla int main ( ) { iets = 10; bla (iets,iets); cout << iets << endl; return 0; } // main
Wat gebeurt er als & weggelaten wordt in de headings? 17. Gegeven is de functie: void test (int x, int& y) { int z = 9; x = 5; y = 6; z = 7; } // test Stel dat x 1 is, y 2 en z 3 voor globale variabelen x, y en z (van type int). Wat is de uitvoer geproduceerd door: a. test (x,y); cout << x << y << z << endl; b. test (y,x); cout << x << y << z << endl; c. test (1,z); cout << x << y << z << endl; d. test (z,1); cout << x << y << z << endl; e. test (z,x); cout << x << y << z << endl; 18. (Tentamen 6 januari 1997) Gegeven zijn de volgende functies: int f (int x, int y) { x--; return x*y; } // f int g (int a, int b) { int x = 3; b += x; a--; a = f (a,b) + f (a,a); cout << x << a << b; return a+x-2; } // g a. Neem aan dat de waardes van de globale variabelen x en y, beide int, bij binnenkomst van g 6 respectievelijk 16 zijn. 97
Wat gebeurt er bij cout << g (x,y) << x << y << endl;? Wat wordt er afgedrukt? Probeer duidelijke uitleg te geven. b. Geef een functie int G (int a, int b) die dezelfde return-waarde oplevert als g voor alle mogelijke waardes van de parameters, maar die uit slechts e´ e´ n return-statement bestaat, en waarin f niet meer wordt aangeroepen. c. We voegen vier maal een & toe, en wel bij alle parameters in de headings van f en g. Beantwoord opnieuw vraag a. Geef alle mogelijke uitvoeren, en leg uit waarom er verschillende antwoorden mogelijk zijn. 19. (Tentamen 5 januari 1998) Gegeven zijn de volgende functies: int peter (int r, int s) { s--; return r+s+2; } // peter int ellen (int p, int q) { int a = 7; p++; q -= 2; for ( a = 2; a < q; a++ ) p = p + peter (p,q); cout << a << p << q << endl; return a+p+q; } // ellen a. Neem aan dat de waardes van de globale variabelen a en b, beide int, bij binnenkomst van de functie ellen 2 respectievelijk 6 zijn. Wat gebeurt er bij cout << ellen (a,b); cout << a << b << endl;? Wat zou er worden afgedrukt? Probeer duidelijke uitleg te geven. b. We voegen vier maal een & toe, en wel bij alle parameters in de headings van ellen en peter. Beantwoord opnieuw de vorige vraag. c. Vervang in de functie ellen het statement p = p + peter (p,q); door het statement p = p + peter (q,p);. Zet de vier &’s er weer bij, net als bij b. Leg uit waarom uiteindelijk de globale variabele a verschillende waarden kan hebben, en geef deze. 20. Schrijf een functie die x tot de macht y berekent, waarbij a. x en y beide van type double zijn, b. x van type double is, y van type int, en exp en log (uit math.h of cmath) niet gebruikt mogen worden. Gebruik overloading. Vergelijk het resultaat eens met pow uit math.h of cmath. 21. Gegeven een functie F: int F (int& x) { x = x + 4; return x; } // F a. Wat gebeurt er bij cout << (x + F(x)); (x is een globale variabele van type int met waarde 7)? b. Wat gebeurt er bij cout << (F(x) + x); ? c. Idem, als & weggelaten wordt. d. Is het verstandig als functies die een int als resultaat hebben van “call by reference” gebruik maken? 98
22. Schrijf een functie drukaf (char letter) die de letters a, b en c afdrukt als: **** * * **** * * * *
,
**** * * **** * * ****
,
**** * * * ****
.
23. Schrijf een functie Pyramide (int hoogte) die een pyramide, bestaande uit sterretjes, en ter hoogte hoogte afdrukt (zie beneden voor hoogte = 4). Er moet getest worden of hoogte positief is. Als hoogte negatief is gebeurt er niets. * *** ***** ******* 24. Schrijf een functie die elk voorkomen van het woordje "er" in een (onzin)tekst verandert in "ER"; tevens moet het aantal regels van de tekst bepaald worden. 25. Schrijf een functie die voor elke ingevoerde datum tussen 1 januari 1900 en 31 december 2100 de bijbehorende dag afdrukt. Gegeven is dat 1 januari 2002 op een dinsdag viel. Het jaar 2000 is overigens wel een schrikkeljaar, maar 1900 en 2100 niet. 26. Schrijf een functie fibo (int n) die het n-de getal van Fibonacci Fibo (n) berekent. Er geldt Fibo (1) = Fibo (2) = 1 en Fibo (n) = Fibo (n-1) + Fibo (n-2), voor n > 2 (gebruik nog geen recursie, zie later). 27. Schrijf een functie die waarden van de zogenaamde Hermite-polynomen uitrekent (zie ook later voor een recursieve versie). Er geldt: H0 (x) = 1, H1 (x) = 2x en Hn (x) = 2xHn−1 (x) − 2(n − 1)Hn−2 (x) voor n > 1. 28. In een zeker C++-programma moeten de functies P, Q en R voorkomen. In de functie P wordt gebruik gemaakt van de functies Q en R. Geef zoveel mogelijk verschillende manieren om dit te programmeren. 29. Het te betalen bedrag voor het sturen van een pakketje overzee wordt als volgt berekend (nemen we aan). Eerst wordt het gewicht naar boven afgerond op het dichtstbijzijnde veelvoud van 15 gram. Dan wordt het tarief uit de volgende tabel afgelezen: • Als het gewicht 15 gram is, wordt het tarief 120 eurocent, • Als het gewicht 30 gram is, wordt het tarief 220 eurocent, • Als het gewicht 45 gram is, wordt het tarief 310 eurocent, • Als het gewicht 60 gram is, wordt het tarief 360 eurocent, plus 20 eurocent per volledige 1000 km, • Als het gewicht 75 gram of meer is, wordt het tarief 400 eurocent, plus 30 eurocent per volledige 1000 km. 99
a. Maak een switch-statement dat bij gegeven gewicht en —indien nodig— de afstand het tarief uitrekent. Maak hier ook een functie van. b. De invoer bestaat nu uit een aantal regels. Elke regel bevat de gegevens van een te versturen pakketje: het gewicht (in grammen) en daarna de af te leggen afstand (in kilometers). De laatste regel bevat alleen het getal 0. Schrijf een programma dat de verzendkosten van al de pakketjes samen berekent. Bovendien moet worden bijgehouden hoeveel pakketjes uit elke gewichtscategorie verstuurd worden. 30. a. Maak een klasse complexgetal die een complex getal moet representeren. b. Schrijf member-functies voor het afdrukken en het conjugeren van een complex getal. c. Schrijf een member-functie die twee variabelen van type complexgetal op de juiste manier bij elkaar optelt. Het resultaat komt in de variabele van de klasse waar deze functie bijhoort. d. Idem voor vermenigvuldigen. 31. a. Verbeter de functie drukaf uit het programma met de vaas en de knikkers zodat verzamelingen netter afgedrukt worden, bijvoorbeeld als {2,4,7,16}. Denk ook aan 0, / de lege verzameling. b. Verbeter het programma zodat de uitvoer “leesbaar” wordt: afgedrukt moeten worden rijtjes als 3 5, 3 9, . . . 32. Schrijf een programma dat een int array[100] vult met de eerste honderd kwadraten. Maak hier ook een functie van. Druk het array tevens af. 33. Er is een enquete gehouden onder honderd mensen. De enquete bestond uit drie vragen. Op elke vraag waren slechts de antwoorden ja en nee mogelijk. De resultaten staan in een array bool uitslag[100][3]. Zo bevat uitslag[30][1] het antwoord van persoon 31 op vraag 2, waarbij true ja betekent en false nee. Schrijf een functie die voor elk van de acht mogelijke antwoord-combinaties bepaalt bij hoeveel mensen deze voorkomt. 34. Gegeven: char boek[99][35][60];. a. Hoe kun je verwijzen naar de derde letter van de vierde regel op bladzijde 55 van een “boek”? b. Kopieer van iedere bladzijde de eerste vijf regels naar een nieuw array. c. Verwissel eerste en laatste bladzijde. 35. Geef een programma dat een tekst regel voor regel inleest en elke regel van achter naar voren afdrukt. Hierbij moet een char regel[80] gebruikt worden om de regel in op te slaan, aannemend dat er hoogstens 80 (of 79) tekens per regel staan. Wat verandert er als char* gebruikt moet worden? 36. Schrijf een programma dat alle in een invoertekst voorkomende woorden in een array opslaat. Als woorden twee keer (of nog vaker) voorkomen moeten ze maar e´ e´ n keer opgeslagen worden. 37. Schrijf een functie vermenigvuldig (int A[ ][n], int v[ ], int res[ ]) die het product van de matrix A en de vector v in de vector res stopt. Neem aan dat A een n bij n matrix is en v een vector met n componenten. 100
38. a. Bedenk een array-representatie voor een stand op een schaakbord. b. Is er een betere (minder geheugenruimte) denkbaar? c. Idem voor een stand op een dambord. 39. a. Schrijf een functie die de array-indices oplevert van het grootste en van het op een na grootste getal van een gegeven array int A[max], met max ≥ 2. b. Geef in woorden een methode aan die ditzelfde bewerkstelligt, maar dan met minder vergelijkingen tussen gehele getallen. Hint: hoe vind je de twee echt beste spelers van een tennistoernooi? 40. Gegeven class grootgetal {public: int inhoud[MAX]};. Hierbij is MAX een zekere constante, zeg 25. In een variabele van klasse grootgetal wordt een geheel getal met veel cijfers opgeslagen. Schrijf nu een functie die de som van twee variabelen van klasse grootgetal uitrekent. Geef methoden om de “lengte” van het getal goed bij te houden. 41. a. Schrijf een functie omzetten die getallen als long gegeven, omzet in array-vorm (elk array-element bevat een of meer cijfers, zie de vorige opgave). b. Schrijf een functie terug die het omgekeerde bewerkstelligt. c. Hoe kun je controleren of voor het getal 1234 de zaak klopt? 42. Gegeven zijn de volgende declaraties in C++: char woord[m]; char verhaal[n]; met m en n constanten (gehele getallen) met n > m > 0. Schrijf nu een C++-functie die vertelt of een variabele woord voorkomt in een variabele verhaal. Als dat zo is moet de array-index die het eerste optreden van woord aanduidt afgedrukt worden. Enkele voorbeelden (in string-notatie): • woord = "la" (m = 2), terwijl verhaal = "leuter babbel bla bla" (met n = 21), met als uitvoer: Ja, index = 15. • woord = "tja" (m = 3), verhaal als boven, levert als uitvoer: Nee. 43. Gegeven een array bord: char bord[8][8];. Dit is dus een “schaakbord” gevuld met letters. a. Schrijf een boolese functie in C++ die true oplevert als er in bord minstens twee aangrenzende (naast elkaar of boven elkaar gelegen) vakjes zijn met dezelfde letter, en anders false. b. Idem, maar nu moet er true opgeleverd worden als er alleen hoofdletters in het array zitten opgeslagen. c. Neem aan dat er alleen hoofdletters worden opgeslagen. Schrijf een functie die bepaalt of er ten minste e´ e´ n rij in bord is die geheel uit klinkers (’A’, ’E’, ’I’, ’O’, ’U’) bestaat. De functiewaarde moet het nummer van zo’n rij zijn en -1 als zo’n rij niet bestaat.
101
d. Herschrijf de functie van c zo dat er geen overbodige tests uitgevoerd worden. Bijvoorbeeld: als er een rij met alleen klinkers gevonden is hoeven de overige rijen niet meer bekeken te worden. 44. (Tentamen 6 januari 1997) Gegeven zijn: const int m = 30; const int n = 40; char puzzel[m][n]; int nummers[m][n]; In een array puzzel zit een kruiswoordraadsel opgeslagen. De zwarte vakjes worden met ’#’ aangegeven, woorden staan in hoofdletters. Een voorbeeld (m = 3, n = 4): H E T # A # O M # S P A
1 0 2 0 0 0 3 4 0 5 0 0
a. Schrijf een boolese C++-functie BestaatHoriWoord (puzzel, i, j) die precies dan true oplevert als op positie (i, j), dus beginnend in de i-de rij en de j-de kolom, een horizontaal woord begint. Het woord moet meer dan e´ e´ n letter hebben, en echt op deze plek beginnen. Aangenomen mag worden dat (i, j) binnen de puzzel valt. b. Schrijf een C++-functie Nummeren (puzzel, nummers) die de vakjes van nummers nummert zoals de puzzel uit puzzel aangeeft (zie voorbeeld). Vakjes waar geen woord begint, bijvoorbeeld de met een ’#’ gemarkeerde, krijgen een 0. Vakjes waar wel een horizontaal en/of verticaal woord begint, krijgen regel voor regel, van links naar rechts, een rangnummer, beginnend bij 1. Gebruik de functie van a, en een soortgelijke functie voor verticale woorden (deze hoeft niet meer geschreven te worden). c. Schrijf een C++-functie Woord (puzzel, w) die het w-de woord uit puzzel puzzel afdrukt, als hier een horizontaal woord staat, en anders niets. Neem aan dat de puzzel minimaal w woorden heeft. In het voorbeeld wordt bij 1 HET afgedrukt, bij 2 niets en bij 3 OM. 45. (Tentamen 5 januari 1999) In een array T (int T[m][n] met m en n constanten) wordt van m personen bijgehouden wie op welke tijdschriften geabonneerd is. Zo betekent T[3][2] == 13 dat klant 3 tijdschrift 13 leest; de 2 heeft geen speciale betekenis. Als een array-element echter 0 is, wordt het nog niet, of niet meer, gebruikt voor een tijdschrift— de persoon in kwestie heeft dan dus minder dan n abonnementen, het maximale aantal. Per klant zijn de tijdschriftnummers verschillend en oplopend gesorteerd, maar er kunnen nullen tussen de niet-nullen zitten. Twee voorbeelden die dezelfde situatie beschrijven (met m == 3 en n == 4): 0 0 1
3 10 13 0 10 0 5 0 10
3 10 13 10 0 0 1 5 10
0 0 0
a. Schrijf een int C++-functie die de persoon met de meeste abonnementen (de index van de rij met de meeste niet-nullen) geeft. Als er meer dan e´ e´ n persoon is die het grootste aantal abonnementen heeft, doet het er niet toe welke wordt opgeleverd. In het voorbeeld hierboven: 0 of 2. 102
b. Schrijf een void C++-functie die in iedere rij de niet-nullen zoveel mogelijk naar links aanschuift—van het voorbeeld linksboven naar dat rechtsboven. c. Schrijf een int C++-functie die oplevert hoeveel tijdschriften door meer dan e´ e´ n persoon gelezen worden. In het voorbeeld zou het antwoord 1 zijn. Als het helpt, mag aangenomen worden dat de tijdschriftnummers tussen 1 en 999 liggen, grenzen inbegrepen. 46. a. Bedenk zelf methoden om willekeurige (“random”) getallen te genereren. Geef vooren nadelen. b. Bekijk de lineaire congruentie methode. Bereken y = ( 3 * x + 5 ) % 16; , waarbij x om te beginnen 1 is, dus y wordt 8: het eerste random-getal. Vervang vervolgens x door y en bereken de nieuwe y; deze is 13: het tweede random-getal. Ga zo door. Reken de rij verder uit. Wat zijn (lijken) voor- en nadelen van deze methode? c. Probeer de getallen van b zo te kiezen dat de methode beter loopt. 47. Schrijf een recursieve functie die x tot de macht y berekent, waarbij y een natuurlijk getal is (zie ook vroeger). Probeer dit op twee verschillende manieren te doen. Zeg iets over het verschil in complexiteit. 48. Schrijf een recursieve functie die a. het n-de Fibonacci-getal berekent (zie ook vroeger), b. waarden van het n-de Hermite-polynoom berekent (zie ook vroeger). 49. Gegeven een array int A[30]. Schrijf een recursieve functie die true oplevert precies dan als een gegeven getal in het array voorkomt. 50. We hebben de volgende drie functies: void keerom1 ( ) { char kar; cin >> kar; if ( kar != ’.’ ) keerom1 ( ); cout << kar; } // keerom1
void keerom2 (char kar) { if ( kar != ’.’ ) { cin >> kar; keerom2 (kar); } // if cout << kar; } // keerom2
De functie keerom3 is als keerom2, maar met elke 2 vervangen door 3 en als functiehoofd keerom3(char& kar);. De invoertekst is: "De parterretrap was vies.". Stel dat kar een globale variabele is van type char. Wat gebeurt er a. bij keerom1 ( );, b. bij cin >> kar; keerom2 (kar);, c. bij cin >> kar; keerom3 (kar);? 51. Het gegevensbestand van een schilderijenverzameling wordt opgeslagen in een array van schilderijen: schilderij bestand[max], waarbij schilderij een klasse is van een bepaalde vorm. Voor elk schilderij worden onder meer opgeslagen: catalogusnummer, naam van de maker (indien bekend) en jaar waarin het gemaakt is (idem). 103
a. Beschrijf de klasse schilderij. b. Schrijf een functie die de gegevens afdrukt van alle schilderijen die voor 1800 gemaakt zijn. c. Schrijf een functie die een zeker catalogusnummer opzoekt, melding geeft van het eventueel niet voorkomen, en anders vraagt of de gegevens veranderd moeten worden. d. Schrijf een functie voor het cre¨eren van een index-array (ook wel indexbestand genoemd), waarmee het bestand in alfabetische volgorde van schildersnaam doorlopen kan worden. e. Idem, maar nu voor de jaartallen. f. Geef aan hoe een en ander werkt voor het volgende bestand(je): array-index 0 1 2 3 4 5 6
cat-nr 546 12 111 554 33 274 849
naam Matisse Appel Rembrandt ? Matisse Mondriaan Rembrandt
jaar 1934 1977 1654 1666 1912 1934 ?
52. Lineair zoeken is een voor de hand liggende methode om een getal in een array op te zoeken. In een reeds gesorteerd array kan een getal snel worden opgespoord met binair zoeken. a. Gegeven de rij 1, 3, 9, 10, 13, 17, 19, 21, 28. Hoe verloopt het zoeken naar het getal 9? En naar 21? En naar 18? Beantwoord de vraag zowel voor lineair als voor binair zoeken. b. Stel dat het aantal elementen in de rij 2k −1 (met k > 0 geheel) is, bijvoorbeeld 8−1 = 7 of 16 − 1 = 15. Hoeveel vergelijkingen heb je nodig om het eerste array-element te vinden? En hoeveel om te constateren dat een bepaald element niet voorkomt? Beantwoord de vraag wederom zowel voor lineair als voor binair zoeken. 53. a. Pas de sorteermethode bubblesort zo aan dat er gestopt wordt zodra er een ronde zonder verwisselingen geweest is. Pas de methode vervolgens zo aan dat bij iedere ronde begonnen wordt bij het eerste element dat wellicht verkeerd zou kunnen staan, en ge¨eindigd wordt bij het laatste element dat wellicht verkeerd zou kunnen staan (op grond van kennis uit de vorige ronde). b. Hoeveel vergelijkingen van array-elementen doet de oorspronkelijke bubblesort, respectievelijk de aangepaste versie, bij het sorteren van n getallen in het beste geval en in het slechtste geval? 54. (Tentamen 4 januari 1996) Gegeven zijn const int n = 1000; en int A[n];. De variabele A bevat een rij onderling verschillende getallen. a. Schrijf nu een C++-functie bergop (A,i,j) die het array-element A[i] (met i tussen 0 en j–2) op de juiste plaats opbergt tussen de reeds oplopend gesorteerde arrayelementen A[i+1],A[i+2],. . . ,A[j-1]. 104
b. Schrijf een C++-functie sorteer (A) die het array A oplopend sorteert door de functie bergop herhaald aan te roepen. c. Hoeveel vergelijkingen tussen array-elementen doet dit sorteer-algoritme voor het rijtje n,n − 1,. . . ,1? d. Is de methode beter dan, gelijkwaardig met of slechter dan de gewone bubblesort qua complexiteit (gedaan aantal vergelijkingen), zowel in het beste als in het slechtste geval? e. Geef C++-code voor invoegsorteer. 55. De sorteermethode Shellsort moet gebruikt worden om de volgende rij in volgorde van grootte te sorteren: 503, 087, 512, 061, 908, 170, 897, 275, 653, 426, 154, 509, 612, 677, 765, 703. a. We doen dit als volgt: we zetten eerst de getallen (op positie) 1 en (op positie) 9 goed ten opzichte van elkaar (503 en 653), dan getallen 2 en 10, enzovoorts. De stapgrootte is dus 8, en de rij wordt “8-gesorteerd”. Zet vervolgens de getallen 1, 5, 9 en 13 goed, enzovoorts. De stapgrootte is nu 4. Vervolgens alle elementen die 2 van elkaar af staan en tenslotte de hele rij. Het sorteren van de deelrijen gaat met een of andere “snelle” methode. b. Bij a spelen de getallen 8, 4, 2 en 1 een rol. Sorteer de rij nu door het rijtje 7, 5, 3 en 1 te gebruiken. c. Geef een wat formelere beschrijving van deze sorteermethode. d. Sorteer de rij ook met bubblesort, invoegsorteer en functie simpelsort. Tel de aantallen vergelijkingen tussen array-elementen die de verschillende methoden nodig hebben. 56. a. Sorteer met behulp van quicksort de rij 3, 7, 2, 5, 1, 9, 4 . b. Wat doet quicksort met een al gesorteerde rij? c. Wat doet quicksort met een omgekeerd gesorteerde rij zoals 4, 3, 2, 1 ? 57. Gegeven: int getal, cijfer; int* p, *q; int* r, s; int A[10]; a. Wat stellen p, *p, &p, q, s, &getal, A, A[3] en A[10] voor? b. Geef equivalente expressies voor A[3]. c. Is int* p, q; hetzelfde als int* p; int* q; of als int *p, *q;? d. Wat betekenen A[9], *A[9], &A[9], (*A)[9] en *(A[9])? Stel dat getal de waarde 4 heeft en cijfer de waarde 7. Wat gebeurt er in de volgende gevallen: e. p = getal; f. *q = cijfer; g. p = new int; p = cijfer; 105
h. q = new int; *q = getal; i. p = new int; p = NULL; (is dit overigens in het algemeen handig?) Stel dat p wijst naar een int met waarde 16 en q naar een int met waarde 75. j. Verwissel deze waarden met behulp van de variabele getal. Geef verschillende manieren om dit te bewerkstelligen. k. Laat beide naar het getal dat in cijfer staat wijzen. l. Stel dat A[i] = i voor i = 0, 1, 2, . . . , 9. Laat de pointer r naar een zelfde array als A verwijzen. Laat q hetzelfde aanwijzen. m. Zorg er vervolgens voor dat q een array “is” waarin de eerste 10 kwadraten zijn opgeslagen. Verandert het door r? 58. Bekijk het volgende programma: #include using namespace std; void tjatja (int* & r, int* & s) { r = new int; *r = 1; *s = 96; } // tjatja int main ( ) { int* p; int* q; p = new int; *p = 3; q = new int; *q = 4; cout << *p << *q << endl; tjatja (p,q); cout << *p << *q << endl; return 0; } // main a. Wat stellen p, *p en &p voor? b. Wat zijn hier actuele en formele parameters? c. Wat is de uitvoer van dit programma (met uitleg/plaatjes)? d. Idem als in de functie-heading van tjatja het symbool & twee maal wordt weggelaten. e. Pas de programma’s van c en d zo aan (met delete) dat na afloop er geen vakjes meer in het geheugen loos rondhangen. 59. Gegeven:
106
class mens { public: char naam[30]; mens* kind; }; // mens Deze “datastructuur” is bedoeld om een ouder-kind-kleinkind-. . . - relatie te representeren, een soort stamboom dus. a. Cre¨eer een variabele van type mens, die een persoon geheten Wilhelmina voorstelt. b. Voeg haar dochter Juliana toe. c. Voeg haar kleindochter Beatrix toe. d. Voeg de vader van Wilhelmina, Willem, toe. Doe eventueel a opnieuw. Maak een tekening van de tot hier gemaakte structuur. e. Hoe kun je de naam van het kleinkind van Willem vinden? f. Stel dat je —in plaats van e´ e´ n— twee kinderen per mens wil toelaten. Hoe moet je de type-definitie dan aanpassen? g. Stel dat je de twee ouders van een kind ook zou willen weten. Hoe moet je de datastructuur dan aanpassen? Teken dit. h. Maakt het uit of in de definitie van de klasse private in plaats van public gebruikt wordt? 60. We hebben een lijst: p −→ 4 −→ 9 −→ 5. a. Geef de noodzakelijke type-definities, declaraties, toekenningen etcetera om deze structuur te cre¨eren. b. Schrijf een functie die in staat is een nieuw element achteraan de lijst toe te voegen (eerst voor deze speciale lijst, daarna algemeen). c. Hoe zou zo’n functie getest moeten worden? 61. (Tentamen 9 augustus 1996) Gegeven is het volgende type: class vakje { int info; vakje* rechts; vakje* onder; }; // vakje
// een getal // wijst naar vakje er rechts naast // wijst naar vakje er onder
Met behulp hiervan kan een lijst worden opgebouwd. Neem aan dat als het info-veld een waarde groter dan 0 bevat, de pointer onder NULL is, terwijl de pointer rechts NULL is als het info-veld een waarde kleiner dan 0 bevat. De andere pointer wijst dan naar het “volgende” vakje. Als de waarde 0 is, zijn beide pointers NULL. Een voorbeeld, met ingang van type vakje* (het vakje met -2 erin bevat hier een pointer (de “lijn” naar beneden) naar het vakje met 5 erin en een NULL-pointer):
107
ingang --> 3 --> -2 | 5 --> 10 --> 0 a. Schrijf een C++-functie voegtoe (ingang,getal) die de int getal in een vakje vooraan de niet-lege lijst met ingang als ingang toevoegt. Denk eraan dat de werking afhangt van het al dan niet positief zijn van getal; neem aan dat getal niet 0 is. b. Schrijf een C++-functie klapom (ingang) die de waarde van het info-veld uit het eerste vakje van de niet-lege lijst ingang door zijn tegengestelde vervangt, en de pointers op de juiste wijze aanpast. In bovenstaand voorbeeld zou 3 vervangen worden door -3, en zou het vakje met -2 erin er onder komen te hangen. c. Schrijf een C++-functie verwijder (ingang) die het eerste vakje uit de lijst ingang verwijdert. Als de lijst leeg is hoeft er niets te worden gedaan. d. In de functies bij a, b en c staat in de heading steeds de parameter ingang. Deze heb je al dan niet “call by reference” gedeclareerd (met een &). Maakt het voor de werking van deze functies verschil uit of die & erbij staat? Leg ook uit wat er bij deze twee mogelijkheden precies gebeurt tijdens executie van de betreffende functie. e. Schrijf een integer C++-functie som (ingang) die de som oplevert van alle in de lijst ingang voorkomende info-velden. Als de lijst leeg is moet er 0 uitkomen.
108
10
Oude tentamens
Er volgen nu enkele oude tentamens. Bij e´ e´ n tentamen zit een uitwerking. De uitwerkingen van de overige tentamens (en zelfs van alle recente tentamens), evenals deze tentamens zelf, zijn beschikbaar via WWW: http://www.liacs.nl/home/kosters/pm/ . Bij alle te schrijven functies moeten de variabelen in de heading voorkomen (niet stiekem globale variabelen gebruiken). De opgaven tellen steeds alle vier even zwaar mee.
10.1 Tentamen vrijdag 5 januari 1996 1. Gegeven zijn const int n = 1000; en een array A (int A[n]) met een rij onderling verschillende getallen. Bij deze opgave nemen we aan dat de eerste helft en de tweede helft van het array A oplopend gesorteerd zijn: A[0] < A[1] < . . . < A[n/2-1] en A[n/2] < A[n/2+1] < . . . < A[n-1]. a. Schrijf nu een C++-functie eenna (A) die het opeennagrootste array-element van A oplevert. In de functie mogen maximaal drie vergelijkingen waarbij een array-element betrokken is gedaan worden. b. Schrijf een C++-functie sorteer (A,B) die het array A oplopend gesorteerd in het array B opbergt. Hint: gebruik twee indices die elementen uit de eerste respectievelijk tweede helft van A aanduiden; kopieer steeds de kleinste van de twee betreffende arrayelementen naar B. Denk eraan dat een van de twee helften “leeg” kan (en zal) raken! c. Hoeveel vergelijkingen tussen array-elementen doet het sorteer-algoritme van b minimaal? Geef een rijtje getallen waarbij dit gebeurt. d. Hoeveel vergelijkingen tussen array-elementen doet het sorteer-algoritme van b maximaal? Geef een rijtje getallen waarbij dit gebeurt. 2. a. Bij een functie kun je te maken hebben met call by value en call by reference, en ook met locale en globale variabelen. Verder heb je ook nog formele en actuele parameters. Leg deze zes begrippen aan de hand van een klein voorbeeld duidelijk uit. b. Gegeven zijn de volgende functies: int functie (int& a, int& r) { a++; r = r * 3; return (r + 1); } // functie void werken (int& x, int y) { int t = 5; x = x + functie (y,r) + t; y = x + 3; r--; t++; cout << "werken" << r << x << y << t << endl; }
// werken
Neem aan dat de waarde van de globale variabele r van type int bij binnenkomst van werken 14 is, en dat u en v int’s zijn met waarde respectievelijk 17 en 2. Wat gebeurt er bij de aanroep werken (u,v);, gevolgd door cout << r << u << v << endl;? Wat wordt er afgedrukt? Probeer duidelijke uitleg te geven. c. Idem, maar nu zonder & in de twee headings.
109
d. En wat gebeurt er als de aanroep werken (x,x); wordt, gevolgd door het statement cout << r << x << endl; (x een int met waarde 5; & er wel bij; r weer 14)? e. Als d, maar nu met int& y in de heading van werken in plaats van int y. Leg uit waarom er verschillende antwoorden mogelijk zijn. 3. Gegeven zijn: const int n = 40; const int m = 10; char v[n][n]; char w[m]; We gaan vierkanten met woorden onderzoeken. Een variabele w met m verschillende letters komt voor in een variabele v precies dan als je beginnende bij een vakje naar keuze, alle letters uit w in de juiste volgorde kunt vinden door steeds naar een van de vier directe buren (twee horizontaal, twee verticaal; bij randvakjes minder) van het vakje waar je dan bent te gaan. Neem aan dat de letters in v zo zijn, dat geen enkel vakje directe buren heeft met dezelfde inhoud. a. Schrijf een boolese C++-functie komtvoor (v,w,i,j) die precies dan true oplevert indien w in v voorkomt, beginnend in rij i en kolom j (0 ≤ i, j ≤ n-1). b. Schrijf een C++-functie jaofnee (v,w) die precies dan true oplevert indien w in v exact e´ e´ n maal voorkomt. Gebruik a. 4. Gegeven zijn de volgende types: class CD { public: char titel; // korte naam van de CD CD* volgende; // wijst naar de volgende CD CD* vorige; // wijst naar de vorige CD }; // CD Met behulp hiervan kan een CD-lijst worden opgebouwd. Neem aan dat elke CD een unieke titel van type char heeft. Een voorbeeld met drie CD’s, met CDs van type CD*: ←− ←− CDs −→ NULL ’D’ −→ ’X’ −→ ’G’ NULL Het vakje met ’X’ erin bevat hier dus een pointer (de pijl naar links) naar het vakje met ’D’ erin en een pointer (de pijl naar rechts) naar het vakje met ’G’ erin. a. CD ’X’ uit een lijst met ingang CDs (van type CD*) krijgt een andere titel. Schrijf een C++-functie anders (CDs,naam) die de titel van ’X’ verandert in naam (van type char). Neem aan dat ’X’ als eerste of als tweede in de lijst staat. b. Schrijf een C++-functie voegtoe (CDs,naam) die de nieuwe CD geheten naam (van type char) toevoegt vooraan de eventueel lege lijst CDs. c. Schrijf een C++-functie die de eerste CD uit de lijst CDs verwijdert. Als de lijst leeg is hoeft er niets te worden gedaan. d. In de functies bij a, b en c staat in de heading de parameter CDs. Deze heb je al dan niet call-by-reference gedeclareerd (met een &). Maakt het voor de werking van deze functies
110
verschil uit of die & erbij staat? Leg ook uit wat er bij deze twee mogelijkheden precies gebeurt tijdens executie van de betreffende functie. e. Schrijf een boolese C++-functie gesorteerd (CDs) die true teruggeeft precies als de lijst CDs alfabetisch oplopend of teruglopend gesorteerd is.
10.2 Tentamen vrijdag 8 augustus 1997 1. We willen een array int A[10000] oplopend sorteren, waarbij we weten dat alle arrayelementen 4, 6 of 9 zijn. a. Schrijf een C++-functie sorteer (... A ...) die dit doet. Tel hiertoe de aantallen vieren, zessen en negens, en stop precies deze aantallen in de goede volgorde in het array. b. Schrijf een C++-functie bubblesort (... A ...) die het array sorteert, maar nu met behulp van bubblesort. Hierbij hoeft niet gebruikt te worden dat het array alleen uit vieren, zessen en negens bestaat. c. Hoeveel vergelijkingen tussen array-elementen doet bubblesort (ongeveer) bij het sorteren van een array met n elementen? d. De methode bij a is veel sneller. Waarom is deze niet altijd beter dan bubblesort? 2. Bij een functie kun je te maken hebben met call by value en call by reference, en ook met locale en globale variabelen. Verder heb je ook nog formele en actuele parameters. a. Leg deze zes begrippen aan de hand van een klein voorbeeld duidelijk uit. b. Gegeven zijn de volgende functies: int hals (bool& p, int s) { p = !p; s--; if (p) return ( s + 2 ); else return ( s - 1 ); } // hals void vermeer (bool& q, int& d) { int w = 5; d = d + hals (q,d) + w; w = 2 * w + 1; y--; cout << "vermeer" << q << d << y << w << endl; } // vermeer Neem aan dat de waardes van de globale variabelen t (van type bool) en y (van type int) bij binnenkomst van vermeer respectievelijk true en 8 zijn. Wat gebeurt er bij de aanroep vermeer (t,y);, gevolgd door cout << t << y << endl;? Wat wordt er afgedrukt? Probeer duidelijke uitleg te geven. Neem aan dat bij het afdrukken van een bool gewoon true of false wordt afgedrukt. c. Idem, maar nu zonder & in de twee headings. d. En wat gebeurt er als de aanroep vermeer (t,t); wordt, gevolgd door het statement cout << t << y << endl;? Hier ook zonder & in de twee headings, net als bij c. Neem aan dat de waardes van t (van type bool) en y (van type int) bij binnenkomst van vermeer respectievelijk false en 5 zijn. e. Als onderdeel d (dus weer zonder &), maar nu met int& s in de heading van hals in plaats van int s. Leg uit waarom er verschillende antwoorden mogelijk zijn, en geef deze verschillende antwoorden. 3. Gegeven zijn (met const int m = ...; const int n = ...;, beide minstens 1): 111
int A[n]; int B[m]; a. Schrijf een C++-functie die bij gegeven arrays A en B het grootst mogelijke produkt van een getal uit A en een getal uit B op het beeldscherm afdrukt. b. Schrijf nu een C++-functie die bij gegeven arrays A en B het array C met n integers als volgt vult: voor iedere i moet het i-de element van C de waarde van het array-element uit B krijgen die het dichtst bij het i-de element van A ligt. Als dit er twee zijn, moet het het dichtst bij 0 gelegen getal van deze twee zijn. Als deze even ver van 0 liggen, dan het positieve getal van deze twee. Voorbeeld: A[0] = 4; A[1] = -5; A[2] = 0; B[0] = 17; B[1] = -7; B[2] = -3; B[3] = 3; B[4] = 9; C[0] = 3; C[1] = -3 (niet -7); C[2] = 3 (niet -3). Gebruik hierbij de functie fabs (x), die de absolute waarde van x teruggeeft. c. Geef in woorden aan hoe het probleem van b effici¨enter kan worden opgelost als het array B oplopend gesorteerd is. d. Kan het nog beter als ook A oplopend gesorteerd is? En het probleem van a? 4. We bekijken een cirkelvormige enkelverbonden lijst. We gebruiken: class vakje { public: int inhoud; vakje* volgende; // pointer naar volgende vakje };
// vakje
De pointer vanuit het laatste vakje moet altijd wijzen naar het eerste vakje. a. Neem aan dat de lijst met ingang van type vakje* als ingang minstens twee vakjes heeft. Schrijf een C++-functie die de (integer-)inhoud van de twee eerste vakjes verwisselt. b. Neem aan dat de lijst met ingang van type vakje* als ingang precies twee vakjes heeft. Schrijf een C++-functie die een vakje met de int getal erin vooraan de lijst toevoegt. Let er op dat de pointer vanuit het laatste vakje naar dit nieuwe vakje gaat wijzen. c. Stel dat we een C++-functie vakje* laatste (vakje* ingang) hebben die een pointer naar het laatste vakje uit de lijst oplevert. Schrijf een C++-functie die het eerste vakje uit de lijst met ingang van type vakje* als ingang verwijdert. Zorg —met behulp van laatste— ervoor dat de pointer vanuit het laatste vakje gaat wijzen naar het nieuwe eerste (en vroegere tweede) vakje. Neem aan dat de lijst minstens twee vakjes bevat. d. In de functies bij a, b en c staat in de heading de parameter ingang. Deze heb je al dan niet call by reference doorgegeven (met een &). Maakt het voor de werking van deze functies verschil uit of die & erbij staat? Leg ook uit wat er bij deze twee mogelijkheden precies gebeurt tijdens executie van de betreffende functie. e. Schrijf de bij c gebruikte C++-functie laatste. Neem weer aan dat de lijst minstens twee vakjes bevat.
112
10.2.1
Uitwerking tentamen vrijdag 8 augustus 1997
1.a. void sorteer (int A[10000]) { int vier = 0, zes = 0, negen = 0, i; for ( i = 0; i < 10000; i++ ) if ( A[i] == 4 ) vier++; else if ( A[i] == 6 ) zes++; else negen++; for ( i = 0; i < vier; i++ ) A[i] = 4; for ( i = 0; i < zes; i++ ) A[vier+i] = 6; for ( i = 0; i < negen; i++ ) A[vier+zes+i] = 9; } // sorteer b. void bubblesort (int A[10000]) { int i, j, Temp; for ( i = 1; i < 10000; i++ ) for (j = 0; j < 10000 - i; j++ ) if ( A[j] > A[j+1] ) { Temp = A[j]; A[j] = A[j+1]; A[j+1] = Temp; } } // bubblesort
// if
c. (n-1) + (n-2) + ... + 3 + 2 + 1 = n(n-1)/2 d. Problematisch als er meer mogelijke waarden in het array zitten, bijvoorbeeld double A[10000]. 2.b. vermeer false 18 18 11 false 18
(hals geeft 6)
c. vermeer true 19 7 11 true 7
(hals geeft weer 6)
d. vermeer false 6 4 11 false 4
(hals geeft nu 1)
e. vermeer false 5OF6 4 11 (hals geeft weer 1) false 4 Afhankelijk van de evaluatievolgorde bij +. 3.a. void gr (int A[n], int B[m]) { int i, j, groot = A[0] * B[0]; for ( i = 0; i < n; i++ ) for ( j = 0; j < m; j++ ) if ( A[i] * B[j] > groot ) groot = A[i] * B[j]; cout << groot << endl; } // gr 3.b. void vul (int A[n], int B[m], int C[n]) { int i, j, dicht;
113
for ( i = 0; i < n; i++ ) { dicht = B[0]; for ( j = 1; j < m; j++ ) if ( fabs (A[i]-B[j]) < fabs (A[i]-dicht) ) dicht = B[j]; else if ( fabs (A[i]-B[j]) == fabs (A[i]-dicht) ) if ( fabs (B[j]) < fabs (dicht) ) dicht = B[j]; else if ( ( B[j] == -dicht ) && ( B[j] > 0 ) ) dicht = B[j]; C[i] = dicht; } // for } // vul c. Binair zoeken in B levert snel de twee (of een) rondom A[i] liggende waarden uit B op, waaruit eenvoudig de juiste kan worden geselecteerd. d. Je kunt met binair zoeken steeds beginnen bij de van de vorige A[i] bekende grens. Het probleem van a is ook eenvoudiger op te lossen: het gevraagde produkt is een van: grootste A maal grootste B, grootste A maal kleinste B, kleinste A maal grootste B, kleinste A maal kleinste B. (Het is niet altijd de grootste maal de grootste, er kunnen namelijk ook negatieve getallen in het spel zijn.) 4.a. void wissel (vakje* ingang) { int Temp = ingang->inhoud; ingang->inhoud = ingang->volgende->inhoud; ingang->volgende->inhoud = Temp; } // wissel b. void voegtoe (vakje*& ingang, int getal) { vakje* p = new vakje; p->inhoud = getal; p->volgende = ingang; ingang->volgende->volgende = p; ingang = p; } // voegtoe 4.c. void verwijder (vakje*& ingang) { vakje* p = laatste (ingang); vakje* q = ingang; ingang = ingang->volgende; p->volgende = ingang; 114
delete q; } // verwijder d. Bij a maakt het niet uit, bij b en c MOET er een & bij; immers in die twee gevallen moet de pointer ingang veranderen! e. vakje* laatste (vakje* ingang) { vakje* p = ingang; while ( p->volgende != ingang ) p = p->volgende; return p; } // laatste
10.3 Tentamen maandag 5 januari 2004 1. Deze opgave gaat over array’s met n karakters: char A[n];, met const int n = 8;. a. Geef een C++-functie void sorteer (A,n) die A aflopend sorteert met behulp van bubblesort. b. Stel dat zo’n array A de tientallige representatie voorstelt van een positief geheel getal. Ieder karakter stelt e´ e´ n cijfer van het getal voor. Een voorbeeld: het getal 1273 wordt gerepresenteerd als ’0’ ’0’ ’0’ ’0’ ’1’ ’2’ ’7’ ’3’, waarbij bijvoorbeeld A[n-2] ’7’ is en A[n-1] ’3’. Schrijf een C++-functie int getal (A,n) die het getal oplevert dat door A wordt voorgesteld. c. Schrijf een functie void som (a,b,c,over) die de char’s a en b “modulo 10 optelt” in c, en de boolean over false maakt precies als er overflow is, dat wil zeggen wanneer de som van de twee getallen groter dan 9 is — en anders true. Een voorbeeld: met a gelijk aan ’8’ en b gelijk aan ’7’, moet c (via 8 + 7 = 15) ’5’ worden en over false. d. Schrijf een C++-functie bool totaalsom (A,B,C,n) die de som van de “getallen” uit de array’s A en B in C zet, en false teruggeeft als er overflow optreedt, dus als de som van A en B te groot is voor C — en anders true. Als er overflow optreedt maakt het niet uit wat er in C terecht komt. Gebruik c, en niet b. 2. a. Bij een functie kun je te maken hebben met call by value en call by reference, en ook met locale en globale variabelen. Verder heb je ook nog formele en actuele parameters. Leg deze zes begrippen duidelijk uit. b. Een zeker C++-programma bevat de volgende programmaregels: int art (int n, int m) { n--; return n+m-1; } // art int paul (int n, int m) { int a = 3; m--; n += 2; a++; m = n + art (n,m) + art (m,n) + a; cout << a << m << n << endl; return a+m-n; } Wat levert op (met globale variabelen a en m van type int): 115
// paul
a = 1; m = 4; cout << paul (m,a) << endl; cout << a << m << endl; Wat wordt er afgedrukt? Geef hierbij uiteraard uitleg. c. We voegen twee maal een & toe, en wel bij de parameters in de heading van paul. Beantwoord opnieuw vraag b. d. Voeg nu ook nog twee maal een & toe bij de parameters in de heading van art. Beantwoord opnieuw vraag c. Waarom zijn verschillende uitkomsten mogelijk? Geef deze. e. Stel dat er in art een aanroep van paul moet bijkomen. Mag dit en hoe kan dit in C++ worden gerealiseerd? En is er dan sprake van recursie? 3. Gegeven is een m bij n array cijfers, gevuld met integers die alle een waarde hebben tussen 1 en m × n. Twee voorbeelden met m = 3 en n = 5: 1 2 11
2 4 12
3 6 13
4 8 14
5 10 15
1 2 11
2 4 12
13 3 6
4 8 14
5 10 15
a. Schrijf een C++-functie bool tweemaal (cijfers,i,j) die bepaalt of de getallen in rij i allemaal gelijk zijn aan twee keer de overeenkomstige getallen uit rij j. Voor het linker voorbeeld is rij 1 twee maal rij 0, en de functie levert daar dus true. b. Schrijf een C++-functie int fraai (cijfers,m) die nagaat in hoeverre het array precies de getallen 1 tot en met m × n bevat, en wel in oplopende volgorde van boven naar beneden en van links naar rechts (rij 0: 1 2 3 . . . ). De functie geeft het aantal plekken in het array waar niet de goede waarde staat. In het linker voorbeeld zijn alleen de getallen 2, 4, 6 en 8 in rij 1 fout, en levert de functie dus 4 op. c. Schrijf een C++-functie void schuifdoor (cijfers,j,m) die alle elementen uit kolom j een plek naar beneden schuift, waarbij het laatste getal op de bovenste plek komt. In het linker voorbeeld kolom 2 doorschuiven levert het rechter voorbeeld. d. Schrijf een C++-functie int hoevaak (cijfers,m) die kijkt hoe vaak je het volgende kunt doen zonder het array uit te lopen (beginnend bij array-element (0,0) linksboven): ga cijfers[0][0] naar rechts naar (zeg) (p,q), dan cijfers[p][q] naar beneden, dan weer naar rechts etcetera. In het linker voorbeeld: van 1 naar 2 naar 12, klaar: 2 keer. 4. Voor het beschrijven van alle films die gedraaid worden tijdens de jaarlijkse filmmarathon gebruiken we het type film. De filmmarathon is een enkelverbonden lijst van films, toegankelijk via de pointer marathon van type film*. class film { // een struct public: char naam; int lengte; film* volgende; }; // film
mag ook // de naam van de film // de duur van de film in minuten // pointer naar volgende film
a. Net voordat de filmmarathon begint blijkt de tweede film spoorloos verdwenen. Schrijf een C++-functie void verwijder (marathon), die de tweede film uit de lijst verwijdert. Je mag aannemen dat de lijst ten minste twee films bevat. 116
b. Schrijf een C++-functie void toevoegen (marathon,titel,duur), die vooraan de lijst een nieuwe film met naam titel en lengte duur toevoegt. Houd hierbij rekening met het feit dat de lijst mogelijk leeg is. c. Er blijkt dat de film met de naam titel langer duurt dan eerst was aangenomen. Gegeven is dat deze film de eerste of de tweede in de lijst is. Schrijf een C++-functie void verbeter (marathon,titel,duur), die het lengteveld van de betreffende film verandert in de juiste lengte (namelijk duur). d. In de functies bij a, b en c staat in de heading de parameter marathon. Deze heb je call by value of call by reference doorgegeven (met een &). Maakt het voor de werking van deze functies verschil uit of die & erbij staat? Leg ook uit wat er bij deze twee situaties precies gebeurt tijdens executie van de betreffende functies. e. Schrijf een C++-functie int hoeveel (marathon), die het aantal films bepaalt die langer duren dan de gemiddelde lengte van de films uit de lijst. Hint: 2 keer lopen.
117
