C by Example Cambridge Computer Science Texts Edited by D. J. Cooke, Loughborough University Page i C is one of the most popular programming languages today. It is flexible, efficient and highly portable, and is used for writing many different kinds of programs, from  compilers and assemblers to spreadsheets and games. This book is based on ANSI C — the recently adopted standard for the C language. It assumes familiarity with basic programming concepts such as variables,  constants, iteration and looping, but covers all aspects of C. In general it is as much about learning programming skills as it is about mastering the art of coding  programs in C. To this end the text contains a wealth of examples and exercises that foster and test the understanding of the concepts developed in each chapter. An outstanding feature of this book is the treatment of 'pointers'. The topic is presented in a clear logical and reasoned manner that is easy to follow. Binary files and  random access files are also treated in such a manner that the reader can easily become adept at using them. Anybody who wishes to get to grips with the art of programming in C will find this a most valuable book. Page iv Also in this series 5 An Introduction to the Uses of Computers Murray Laver 1976 8 ALGOL 68 — A first and second course  A. D. McGettrick 1978 12 Programming via Pascal J. S. Rohl and H. J. Barrett 1980 14 Simulation Techniques for Discrete Event Systems I. Mitrani 1982 15 Information Representations and Manipulation using Pascal E. S. Page and L. B. Wilson 1983 16 Writing Pascal Programs J. S. Rohl 1983 18 Computer Mathematics D. J. Cooke and H. E. Bez 1984 19 Recursion via Pascal J. S. Rohl 1984 22 Program Construction R. G. Stone and D. J. Cooke 1987 23 A Practical Introduction to Denotational Semantics Lloyd Allison 1987 24 Modelling of Computer and Communication Systems I. Mitrani 1987 25 The Principles of Computer Networking D. Russel 1989 26 Concurrent Programming C. R. Snow 1991 27 An Introduction to Functional Programming Systems Using Haskell A. J. T. Davie 1992 28 Categories and Computer Science R. F. C. Walters 1991 Page v C by Example 29 Cambridge Computer Science Texts Noel Kalicharan University of the West Indies Page vi PUBLISHED BY CAMBRIDGE UNIVERSITY PRESS (VIRTUAL PUBLISHING) FOR AND ON BEHALF OF THE PRESS SYNDICATE OF THE  UNIVERSITY OF CAMBRIDGE Published by the Press Syndicate of the University of Cambridge The Pitt Building, Trumpington Street, Cambridge CB2 1RP 40 West 20th Street, New York, NY 10011­4211, USA  10 Stamford Road, Oakleigh, Melbourne 3166, Australia © Cambridge University Press 1994 This edition   Cambridge University Press (Virtual Publishing) 2001 First published 1994 Printed in Great Britain at the University Press, Cambridge A catalogue record for this book is available from the British Library Library of Congress cataloguing in publication data Kalicharan, Noel. C by example / Noel Kalicharan. p.      cm. — (Cambridge computer science texts: 29)  Includes index. ISBN 0 521 45023 3 (hc). — ISBN 0 521 45650 9 (pb) 1. C (Computer program language) I. Title. II. Series. QA76.73.C15835  1994 005.13'3­dc20   93­27877 CIP ISBN 0 521 45023 3 hardback ISBN 0 521 45650 9 paperback eISBN  0511003447 virtual (netLibrary Edition) PR Page vii To my daughters Anushka Nikita and Anyara Saskia Page ix Contents Preface xv 1 1 Getting Started with C 1.1 The First Example 3 1.1.1 Running the Program 4 1.1.2 A Word on Program Layout 6 1.2 Comments 8 1.3 Data Types 9 1.4 Identifiers 11 1.5 Expressions 13 1.5.1 Arithmetic Operators 13 1.5.2 Assignment Operators 14 1.5.3 Relational Operators 15 1.5.4 Logical Operators 16 1.5.5 Increment and Decrement Operators 17 1.5.6 Mixing Operands in an Expression 17 1.6 Statements 18 1.7 Standard Input and Output 19 1.8 The while Statement 23 1.9 The if . . . else Statement 26 Exercises 1 30 2 32 More Control Structures and Arrays 2.1 The for Statement 32 2.2 The do . . . while Statement 36 2.3 The switch Statement 40 2.4 The continue Statement 42 Page x 2.5 Arrays 43 2.5.1 Strings 48 2.5.2 Sequential and Binary Search 50 Exercises 2 52 3 55 Functions — the Basics 3.1 An Example — Factorial 55 3.2 Function Definition 60 3.3 Sequential Search 61 3.4 Binary Search 63 3.5 The One­Zero Game 64 Exercises 3 72 4 76 Character Handling 4.1 Character Sets 77 4.2 getchar and putchar 79 4.3 Example — Letter Frequency Count 83 4.4 Strings (Arrays of Characters) 86 4.5 Example — Word Frequency Count 93 4.5.1 Hashing 94 4.5.2 Back to the Problem 98 4.5.3 Insertion Sort 106 4.5.4 Sorting the Words 110 4.5.5 Printing the Table 111 Exercises 4 118 5 120 Functions and Pointers 5.1 Parameter Passing 120 5.2 Pointer Variables 125 5.3 More on Parameter Passing 129 5.3.1 A Voting Problem 131 5.4 Character Pointers 139 5.5 Pointer Arithmetic 141 5.6 Pointers to Functions 145 5.7 Near, Far and Huge Pointers 149 5.8 Recursion 150 5.8.1 An Example — Towers of Hanoi 151 5.8.2 An Example — Decimal to Binary 153 5.8.3 An Example — Quicksort 153 Exercises 5 157 Page xi 6 160 Data Types, Operators and Storage Classes 6.1 Data Types 160 6.2 Operators 164 6.3 Bit Operators 167 6.4 Conditional Expressions 170 6.5 Storage Classes in C 171 6.5.1 Automatic 172 6.5.2 External 173 6.5.3 Static 177 6.5.4 Register 179 6.5.5 Other Scope Rules 179 6.6 Initialization 180 6.6.1 Simple Variables 180 6.6.2 Array Variables 181 6.6.3 Two­Dimensional Arrays 184 Exercises 6 185 7 187 Basic Structures and Linked Lists 7.1 The Voting Problem Revisited 187 7.1.1 typedef 189 7.1.2 Passing Structures to Functions 192 7.2 Pointers to Structures 201 7.3 Linked Lists 202 7.3.1 Dynamic Storage Allocation — Malloc, Calloc, Sizeof 204 7.3.2 Building a Linked List — Version 1 208 7.3.3 Some Characteristics of Linked Lists 210 7.3.4 Building a Linked List — Version 2 211 7.3.5 Deletion from a Linked List 213 7.3.6 Building a Linked List — Version 3 214 Exercises 7 217 8 221 Binary Trees and Other Structures 8.1 Binary Trees 221 8.1.1 Representing a Binary Tree 228 8.1.2 Binary Search Trees 228 8.2 A Cross­Reference Program 233 8.3 Initialization of an Array of Structures 243 8.4 Nested Structures 244 8.5 Unions 245