Doina Logofătu Einführung in C Praktisches Lern- und Arbeitsbuch für Programmieranfänger 2. Auflage Einführung in C Doina Logofătu Einführung in C Praktisches Lern- und Arbeitsbuch für Programmieranfänger 2., überarbeitete Auflage 2016 Doina Logofa˘tu Frankfurt am Main Deutschland Die erste Auflage des Buches erschien mit dem Titel „Eine praktische Einführung in C – Lern- und Arbeitsbuch für Programmiereinsteiger“ 2008 bei entwickler.press. ISBN 978-3-658-12921-7 ISBN 978-3-658-12922-4 (eBook) DOI 10.1007/978-3-658-12922-4 Die Deutsche Nationalbibliothek verzeichnet diese Publikation in der Deutschen Nationalbibliografie; detaillierte bibliografische Daten sind im Internet über http://dnb.d-nb.de abrufbar. Springer Vieweg © Springer Fachmedien Wiesbaden 2008, 2016 Das Werk einschließlich aller seiner Teile ist urheberrechtlich geschützt. Jede Verwertung, die nicht ausdrücklich vom Urheberrechtsgesetz zugelassen ist, bedarf der vorherigen Zustimmung des Verlags. Das gilt insbesondere für Vervielfältigungen, Bearbeitungen, Übersetzungen, Mikroverfilmungen und die Einspeicherung und Verarbeitung in elektronischen Systemen. Die Wiedergabe von Gebrauchsnamen, Handelsnamen, Warenbezeichnungen usw. in diesem Werk berechtigt auch ohne besondere Kennzeichnung nicht zu der Annahme, dass solche Namen im Sinne der Warenzeichen- und Markenschutz-Gesetzgebung als frei zu betrachten wären und daher von jedermann benutzt werden dürften. Der Verlag, die Autoren und die Herausgeber gehen davon aus, dass die Angaben und Informationen in diesem Werk zum Zeitpunkt der Veröffentlichung vollständig und korrekt sind. Weder der Verlag noch die Autoren oder die Herausgeber übernehmen, ausdrücklich oder implizit, Gewähr für den Inhalt des Werkes, etwaige Fehler oder Äußerungen. Gedruckt auf säurefreiem und chlorfrei gebleichtem Papier Springer Vieweg ist Teil von Springer Nature Die eingetragene Gesellschaft ist Springer Fachmedien Wiesbaden GmbH The more you can dream, the more you can do. Michael Korda Vorwort Das vorliegende Buch ist als Lern- und Arbeitsbuch der C-Programmierung kon- zipiert und versetzt Sie in die Lage, eine Vielzahl praktischer Probleme zu lösen. DastheoretischeGerüstunddieVielfältigkeitdervorgestelltenThemenmachendas BuchauchfürfortgeschritteneLeserinteressant.IchempfehleesSchülern,Studen- ten,Programmierern,InformatiklehrernundallenInteressiertenfürdasindividuelle Studium,alsArbeitsmaterialinderLehreoderalsNachschlagewerk. Da C Basis für die modernen objektorientierten Sprachen C++, Java und C# und außerdem flexibel und effizient ist, bin ich der Ansicht, dass sich die Program- miersprache ausgezeichnet für Einsteiger eignet. Bevor Sie sich mit dem Thema Objektorientierung befassen, sollten Sie sich algorithmisches, strukturiertes Den- kenaneignenunddieBasiskonzepte(Algorithmenentwurf,Variablen,Modularität, Speicherplatzmanipulation) beherrschen. Wenn Sie der Programmierung treu blei- ben, werden Sie nahezu automatisch zu C++, Java oder C# gelangen, denn diese SprachenbietenKonzeptewieDatenabstraktionodergenerischeProgrammierung. Die 100 Probleme, die Sie mit vollständigen Lösungen im Buch finden, sind unterschiedlich schwer. Zu jeder Problembeschreibung gehört ein repräsentatives Eingabe- und Ausgabe-Datenset, mit dem Sie Ihre eigene Lösung überprüfen kön- nen. Danach wird das Problem analysiert, dazu schlage ich eine mögliche Lösung vor. Und schließlich finden Sie für diese Lösung das komplette C-Programm auf- gelistet,bevorwiederIhrHirnschmalzbeidenverwandtenAufgabenundÜbungen gefragt ist. Übungen gibt es auch am Ende jedes Kapitels, insgesamt über 330 im Buch. Die Programme sind kompakt und vollständig, um eine gute Lesbarkeit zu gewährleistenunddieC-Sprachezuvertiefen.Siesind,außerdasletzteProgramm mitFraktalen(Kapitel10),mitderMicrosoftVisualC++2013kompiliertworden, dieMicrosoftkostenloszurVerfügungstellt. Entlang der zehn Kapitel lade ich Sie zu einer Reise an, die Sie mit der Sprache C vertraut macht. Das erste Kapitel startet kurz und bündig mit den Grundelementen von C und zahlreichen Beispielen. Die nächsten sechs Kapitel (2 bis 7) enthalten vielegelösteProbleme(einfacheAnweisungen,Zeichenketten,Arrays,Strukturen, Unionen, Zeiger, Bit-Operationen, Zeitfunktionen, Zufallszahlen), damit Sie sich mit C und dem Lösungsentwurf für konkrete Aufgabenstellungen anfreunden kön- nen. In den letzten drei Kapiteln (Kapitel 8 bis 10) befassen wir uns mit schwie- rigeren Dingen: verketteten Listen, komplexeren Datenstrukturen und ihrer Verar- vii viii Vorwort beitung, Fraktale. Ein Grund dafür ist auch, dass ich mir dadurch erhoffe, Sie mit diesen interessanten Themen für die Programmierung begeistern zu können. Kapi- tel 8 behandelt verkettete Strukturen (einfach und doppelt verkettete, kreisförmi- ge,Hash-Tabellen,Kellerspeicher,Bäume).InKapitel9erstellenwireineumfang- reiche Anwendung, die verkettete Listen nutzt, um die Wurzel k-ten Grades einer großenZahlzuberechnen.WirimplementierendabeiallearithmetischenOperatio- nen für solch große Zahlen. Die Applikation im letzten Kapitel zeichnet fraktale Strukturen und macht u.a. von Bitoperatoren und graphischen Routinen Gebrauch. Das Programm ist in Borland-C geschrieben, weil die graphische Bibliothek über- schaubar und lehrreich ist. Sie können den grafischen Anteil mit einem anderen ersetzen,umdieFraktalezuzeichnen. “Einführung in C” enthält viele wichtige Konzepte aus der elementaren Daten- verarbeitung, wie z. B. Suchen eines Elements, Sortieren, Löschen, Hinzufügen, Operationen mit Dateien usw. Dazu werden auch verschiedene Datenstrukturen vorgestellt: Strukturen, Bitfelder, Unionen, Arrays, Zeichenketten, Kellerspeicher, Hash-Tabellen oder Binärbäume. Die oft verwendeten Zeichenkettenoperationen, Bit-Operationen und Zeitfunktionen werden in mehreren ausgewählten Problem- stellungen vorgestellt. Funktionen erstellen wir selbst, um klassische Aufgaben zu lösen,undwirlernenauch,wiewirbestehendeFunktionenausdenHeader-Dateien verwenden können (z. B. für Zeichenkettenoperationen, Zeit- und Zufallszahlen- funktionen,SortierenoderSuchenineinemArray). Für einen Programmierer ist Mathematik sehr wichtig. Die vielen Übungen und BeispieleimBuchtragendazubei,mehreregrundlegendeKonzeptederMathema- tik aufzufrischen, u.a. Teilbarkeit und Primalität natürlicher Zahlen, Rekurrenzen, Reihen, Berechnung des Wertes π, Fibonacci-Zahlen, vollkommene und befreun- deteZahlen,OperationenmitPolynomenundMatrizen,GoldbachscheVermutung, Gleichungen,BrücheundMengen,Geometrie,SiebdesEratosthenes. Die einzige Möglichkeit, eine Programmiersprache zu beherrschen, ist kontinuier- liches Üben. Es ist wichtig, immer wieder selbständig verschiedene Aufgaben zu lösenundProgrammezuentziffern,zuerweitern,damitzu“spielen”.DiesesBuch bietet Ihnen dazu eine große Anzahl von oft auftretenden und vielschichtigen Pro- grammieraufgabenan,diemeistendavonsindvollständiggelöstundmitErklärun- genzurSpracheC,MathematikundAlgorithmikversehen. AbundzufindenSiealsBelohnungfürIhrenFleißzwischenzweiKapitelnBilder wie“HofdesKönigspalastesinMadrid”,“WinterlandschaftinSaalbach”,“Wellen- surferinMünchen”oder“GarteninAlhambra”. VielVergnügenbeimLesenundspannendesLernen! FrankfurtamMain,Mai2016 DoinaLogofa˘tu Danksagung MeinherzlicherDankgebührtallen,diemeineBücher(“AlgorithmenundProblem- lösungen mit C++”, “Grundlegende Algorithmen mit Java”, “Eine praktische Ein- führung in C”) positiv aufgenommen haben. Professoren, Studenten und Program- mierer, die mir geschrieben haben, haben mich darin bestärkt, neue Buchprojekte, insbesonderedieses,anzugehenundzuverwirklichen. MeinbesondererDankgebührtdemSpringerViewegVerlag(insbesonderemeinen LektorinnenSybilleThelenundSabineKathke).IchbinsehrdankbarfürdieUnter- stützung, die ich immer erfahren habe, für die professionelle Zusammenarbeit und fürdieGeduld,mitderaufmeinManuskriptgewartetwurde. Ichdankeauchallen,diedieFertigstellungdesBuchesermöglichthaben. FrankfurtamMain,Mai2016 DoinaLogofa˘tu ix Inhaltsverzeichnis 1 DieProgrammierspracheCimÜberblick......................... 1 1.1 KurzerhistorischerAbriss ................................... 1 1.2 GrundlegendeKonzepte ..................................... 2 1.2.1 ZeichenvorratvonC.................................. 2 1.2.2 Ausdrücke .......................................... 6 1.2.3 AufbauderC-Programme ............................. 8 1.2.4 Anweisungen ....................................... 10 1.2.5 Standardeingabe/-ausgabe............................. 14 1.2.6 Dateienoperationen .................................. 16 1.2.7 NeueDatentypen:struct,enum,union ................. 18 1.2.8 MehrüberArrays .................................... 21 1.2.9 Zeiger,sizeof,dynamischeSpeicherreservierung ........ 23 1.3 11gelösteProblemeinC .................................... 32 1.3.1 Problem1 .......................................... 32 1.3.2 Problem2 .......................................... 33 1.3.3 Problem3 .......................................... 33 1.3.4 Problem4 .......................................... 35 1.3.5 Problem5 .......................................... 36 1.3.6 Problem6 .......................................... 38 1.3.7 Problem7 .......................................... 39 1.3.8 Problem8 .......................................... 41 1.3.9 Problem9 .......................................... 43 1.3.10 Problem10 ......................................... 43 1.3.11 Problem11 ......................................... 44 1.4 Aufgaben ................................................. 49 2 ElementareOperationen ........................................ 53 2.1 TeilbarkeitdurchSubtraktionen............................... 53 2.2 EuklidischerAlgorithmus.................................... 54 2.3 EinfacherPrimalitätstest..................................... 56 2.4 DerPunktmitdemkürzestenAbstand ......................... 57 xi xii Inhaltsverzeichnis 2.5 GrößedesSpeicherplatzes ................................... 60 2.6 GoldenerSchnitt ........................................... 61 2.7 PositioneinesPunktesimKreis............................... 63 2.8 DasarithmetischeMittel..................................... 65 2.9 LineareRekurrenz.......................................... 66 2.10 SynonymeFunktionmitatol().............................. 67 2.11 InformationenüberZeichen.................................. 69 2.12 PalindromundQuersumme .................................. 70 2.13 UnendlicheWurzel ......................................... 71 2.14 ReihemitdemWertπ....................................... 72 2.15 DerbedingteAusdruck?:.................................... 78 2.16 BesonderePaare ........................................... 79 2.17 DieFarey-Reihe............................................ 81 2.18 GemeinsameTeiler ......................................... 83 2.19 ZahlenumwandlunginsDezimalsystem ........................ 84 2.20 FormatierungdernatürlichenZahlen .......................... 85 2.21 VollkommeneZahlen ....................................... 86 2.22 BefreundeteZahlen......................................... 87 2.23 SummederdrittenPotenzen ................................. 89 2.24 ASCII-Codes .............................................. 90 2.25 Aufgaben ................................................. 91 3 ArraysundZeiger ............................................. 95 3.1 KleinstesElementeinerFolge ................................ 95 3.2 BubbleSort ............................................... 97 3.3 AbleitungeinesPolynoms ................................... 99 3.4 BestimmungdergrößerenZahlen .............................101 3.5 ProdukteinesPolynomsmit(X-a) ............................102 3.6 ProduktzweierMatrizen ....................................104 3.7 DieGoldbachscheVermutung ................................107 3.8 NachbarnmitDifferenz1....................................109 3.9 LösenvonGleichungenzweitenGrades........................111 3.10 SucheneinesWertesimeindimensionalenArray ................113 3.11 SortierenderSpalteneinerMatrix.............................115 3.12 SymmetrischeElementeinquadratischerMatrix ................117 3.13 ZeigerzumDurchlaufeneinesArrays..........................119 3.14 AdresseninArrays .........................................120 3.15 VertauschenderBytes.......................................121 3.16 ArrayvonFunktionszeigern..................................123 3.17 SattelpunktederMatrix .....................................124 3.18 Aufgaben .................................................126