C Programming_ An Advanced Course [Kalicharan 2008-08-11].pdf

(892 KB) Pobierz
C
Programming
omputer
An Advanced Course
Noel Kalicharan
Senior Lecturer, Computer Science
The University of the West Indies
St. Augustine, Trinidad
Published September 2006
©
Noel Kalicharan, 2006
nkalicharan@fsa.uwi.tt
All rights reserved
The text of this publication, or any part thereof, may not
be reproduced or transmitted in any form or by any
means, electronic or mechanical, including photocopying,
recording, storage in an information retrieval system, the
Internet, or otherwise, without prior written permission
of the author.
Preface
This book takes up where
C Programming – A Beginner’s Course
leaves off. It assumes
you have a working knowledge of basic programming concepts such as variables,
constants, assignment, selection (if...else) and looping (while,
for).
It also assumes you are
comfortable with writing functions and working with arrays. If you are not, it is
recommended that you study
A Beginner’s Course
before tackling the material in this
book.
As in the first book, the emphasis is not on teaching the C language, per se, but rather, on
using C to teach concepts that any budding programmer should know. The major topics
covered are sorting, searching, merging, structures, pointers, linked lists, stacks, queues,
recursion and random numbers.
Chapter 1 deals with sorting a list, searching a list and merging two ordered lists.
Chapter 2 introduces an important concept—the structure. Structures allow you to group
a set of related data and manipulate them as one. This chapter shows you how to search
and sort an array of structures and how to create useful user-defined types using
typedef
and
structs.
Chapter 3 covers that elusive but very powerful concept—pointers. Many programmers
will tell you that this is probably the most difficult concept to grasp and the one that
gives them the most headache. We hope that, after reading this chapter, you will agree
that it does not have to be so.
Chapter 4 deals with linked lists—an important data structure in its own right but also the
foundation for more advanced structures such as trees and graphs.
Chapter 5 is devoted specifically to stacks and queues, perhaps the most useful kinds of
linear lists. They have important applications in Computer Science.
Chapter 6 introduces a powerful programming methodology—recursion. There is no
doubt that recursion takes a bit of getting used to. But, once mastered, you would be able
to solve a whole new world of problems that would be difficult to solve using traditional
techniques.
We all like to play games. But what lurks inside these game-playing programs? Random
numbers. Chapter 7 shows you how to use random numbers to play some simple games
and simulate real-life situations.
Almost anything we need to store on a computer must be stored in a file. We use text
files for storing the kinds of documents we create with a text editor or word processor.
We use binary files for storing photographic image files, sound files, video files and files
of ‘records’. Chapter 8 shows how to create and manipulate text and binary files. And it
also explains how to work with that most versatile kind of file—a random access file.
I wish to express my thanks to Anisa Sawh-Ramdhan for her careful reading of the
manuscript. Any errors that remain are all mine.
Noel Kalicharan
Contents
1 Sorting, searching and merging
........................................................................... 1
1.1 Sorting an array – insertion sort ........................................................................... 1
1.2 Inserting an element in place................................................................................ 7
1.3 Sorting an array of strings .................................................................................... 8
1.4 Sorting parallel arrays ........................................................................................ 10
1.5 Binary search...................................................................................................... 10
1.6 Searching an array of strings.............................................................................. 13
1.7 Example – word frequency count....................................................................... 13
1.8 Merging ordered lists... ...................................................................................... 19
Exercises 1 ................................................................................................................... 22
2 Structures....... ............................................................................................... 24
2.1 How to declare a structure.................................................................................. 25
2.2 Working with an array of structures................................................................... 29
2.3 Searching an array of structures ......................................................................... 30
2.4 Sorting an array of structures ............................................................................. 31
2.5 Putting it all together .......................................................................................... 32
2.6 Nested structures ................................................................................................ 35
2.7 Fractions............................................................................................................. 36
2.8 A voting problem ............................................................................................... 39
2.9 Passing structures to functions ........................................................................... 46
Exercises 2 ................................................................................................................... 47
3 Pointers........... .............................................................................................. 48
3.1 Passing pointers as arguments............................................................................ 50
3.2 More on passing an array as an argument ......................................................... 52
3.3 Character pointers .............................................................................................. 54
3.4 Pointer arithmetic ............................................................................................... 55
3.5 Pointers to structures .......................................................................................... 58
3.6 Pointers to functions........................................................................................... 60
3.7 Void pointers...................................................................................................... 63
Exercises 3 ................................................................................................................... 65
4 Linked lists........... ......................................................................................... 67
4.1 Basic operations on a linked list......................................................................... 69
4.1.1 Counting the nodes in a linked list ........................................................ 69
4.1.2 Searching a linked list ........................................................................... 71
4.1.3 Finding the last node in a linked list ..................................................... 72
4.2 Dynamic storage allocation – malloc, calloc, sizeof, free.................................. 72
4.3 Building a linked list – adding new item at the tail............................................ 76
4.4 Insertion into a linked list................................................................................... 79
4.5 Building a linked list – adding new item at the head ......................................... 82
4.6 Deletion from a linked list.................................................................................. 83
4.7 Building a sorted linked list ............................................................................... 85
4.8 Example – palindrome ....................................................................................... 89
4.9 Merging two sorted linked lists.......................................................................... 92
Exercises 4 ................................................................................................................... 96
5 Stacks and queues........... ............................................................................ 98
5.1 Abstract data types ............................................................................................. 98
5.2 Stacks
.......................................................................................................... 98
iv
5.2.1 Implementing a stack using an array................................................... 100
5.2.2 Implementing a stack using a linked list ............................................. 104
5.3 Creating a stack header file .............................................................................. 107
5.4 A general stack type ......................................................................................... 108
5.4.1 Example – convert from decimal to binary ......................................... 112
5.5 How to convert from infix to postfix ............................................................... 113
5.5.1 How to evaluate a postfix expression.................................................. 118
5.6 Queues
........................................................................................................ 120
5.6.1 Implementing a queue using an array ................................................. 120
5.6.2 Implementing a queue using a linked list............................................ 125
Exercises 5 ................................................................................................................. 131
6 Recursion........... ......................................................................................... 132
6.1 Recursive functions in C .................................................................................. 133
6.2 Recursive decimal to binary............................................................................. 136
6.3 Printing a linked list in reverse order ............................................................... 139
6.4 Towers of Hanoi............................................................................................... 140
6.5 The power function .......................................................................................... 142
6.6 Merge sort ........................................................................................................ 144
6.7
static
variables.................................................................................................. 147
6.8 Counting organisms ......................................................................................... 149
6.9 Finding a path through a maze ......................................................................... 154
Exercises 6 ................................................................................................................. 158
7 Random numbers, games and simulation ............................................... 160
7.1 Random numbers ............................................................................................. 160
7.2 Random and pseudo-random numbers ............................................................. 161
7.3 Generating random numbers by computer ....................................................... 162
7.4 A guessing game .............................................................................................. 165
7.5 Drills in addition .............................................................................................. 165
7.6 Nim................................................................................................................... 167
7.7 Non-uniform distributions................................................................................ 171
7.7.1 Collecting bottle caps .......................................................................... 173
7.8 Simulation of real-life problems ...................................................................... 176
7.9 Simulating a queue ........................................................................................... 177
7.10 Estimating numerical values using random numbers....................................... 181
Exercises 7 ................................................................................................................. 184
8 Working with files ....................................................................................... 186
8.1 Reading data from a file ................................................................................... 186
8.2 Sending output to a file .................................................................................... 189
8.3 Text and binary files......................................................................................... 191
8.4 Internal vs external file name ........................................................................... 191
8.5
fopen
and
fclose................................................................................................
192
8.6
getc
and
putc....................................................................................................
195
8.7
feof
and
ferror...................................................................................................
195
8.8
fgets
and
fputs
.................................................................................................. 197
8.9 Input/output for binary files ............................................................................. 199
8.9.1
fread
and
fwrite...................................................................................
200
8.10 Random access files ......................................................................................... 202
8.11 Indexed files ..................................................................................................... 206
8.12 Updating a random access file ......................................................................... 212
Exercises 8 ................................................................................................................. 216
Index ............................................................................................................................... 217
v

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin