第1页 / 共221页
第2页 / 共221页
第3页 / 共221页
第4页 / 共221页
第5页 / 共221页
第6页 / 共221页
第7页 / 共221页
第8页 / 共221页
Object-oriented Programming with ANSI-C.pdf
Object-oriented Programming with ANSI-C
Preface
Contents
1 Abstract Data Types
2 Dynamic Linkage
3 Programming Savvy
4 Inheritance
5 Programming Savvy
6 Class Hierarchy
7 The ooc Preprocessor
8 Dynamic Type Checking
9 Static Construction
10 Delegates
11 Class Methods
12 Persistent Objects
13 Exceptions
14 Forwarding Messages
A ANSI-C Programming Hints
B The ooc Preprocessor
C Manual
Bibliography
v
___________________________________________________________________________
Preface
No programming technique solves all problems.
No programming language produces only correct results.
No programmer should start each project from scratch.
Object-oriented programming is the current cure-all — although it has been
around for much more then ten years. At the core, there is little more to it then
finally applying the good programming principles which we have been taught for
more then twenty years. C++ (Eiffel, Oberon-2, Smalltalk ... take your pick) is the
New Language because it is object-oriented — although you need not use it that
way if you do not want to (or know how to), and it turns out that you can do just as
well with plain ANSI-C. Only object-orientation permits code reuse between pro-
jects — although the idea of subroutines is as old as computers and good program-
mers always carried their toolkits and libraries with them.
This book is not going to praise object-oriented programming or condemn the
Old Way. We are simply going to use ANSI-C to discover how object-oriented pro-
gramming is done, what its techniques are, why they help us solve bigger prob-
lems, and how we harness generality and program to catch mistakes earlier. Along
the way we encounter all the jargon — classes, inheritance, instances, linkage,
methods, objects, polymorphisms, and more — but we take it out of the realm of
magic and see how it translates into the things we have known and done all along.
I had fun discovering that ANSI-C is a full-scale object-oriented language. To
share this fun you need to be reasonably fluent in ANSI-C to begin with — feeling
comfortable with structures, pointers, prototypes, and function pointers is a must.
Working through the book you will encounter all the newspeak — according to
Orwell and Webster a language ‘‘designed to diminish the range of thought’’ — and
I will try to demonstrate how it merely combines all the good programming princi-
ples that you always wanted to employ into a coherent approach. As a result, you
may well become a more proficient ANSI-C programmer.
The first six chapters develop the foundations of object-oriented programming
with ANSI-C. We start with a careful information hiding technique for abstract data
types, add generic functions based on dynamic linkage and inherit code by judicious
lengthening of structures. Finally, we put it all together in a class hierarchy that
makes code much easier to maintain.
Programming takes discipline. Good programming takes a lot of discipline, a
large number of principles, and standard, defensive ways of doing things right. Pro-
grammers use tools. Good programmers make tools to dispose of routine tasks
once and for all. Object-oriented programming with ANSI-C requires a fair amount
of immutable code — names may change but not the structures. Therefore, in
chapter seven we build a small preprocessor to create the boilerplate required.
It
looks like yet another new object-oriented dialect language (yanoodl perhaps?) but
it should not be viewed as such — it gets the dull parts out of the way and lets us
concentrate on the creative aspects of problem solving with better techniques. ooc
vi___________________________________________________________________________
Preface
(sorry) is pliable: we have made it, we understand it and can change it, and it
writes the ANSI-C code just like we would.
In chapter eight we add dynamic
The following chapters refine our technology.
type checking to catch our mistakes earlier on.
In chapter nine we arrange for
automatic initialization to prevent another class of bugs. Chapter ten introduces
delegates and shows how classes and callback functions cooperate to simplify, for
example, the constant chore of producing standard main programs. More chapters
are concerned with plugging memory leaks by using class methods, storing and
loading structured data with a coherent strategy, and disciplined error recovery
through a system of nested exception handlers.
Finally, in the last chapter we leave the confines of ANSI-C and implement the
obligatory mouse-operated calculator, first for curses and then for the X Window
System. This example neatly demonstrates how elegantly we can design and
implement using objects and classes, even if we have to cope with the idiosyn-
crasies of foreign libraries and class hierarchies.
Each chapter has a summary where I try to give the more cursory reader a run-
down on the happenings in the chapter and their importance for future work. Most
chapters suggest some exercises; however, they are not spelled out formally,
because I firmly believe that one should experiment on one’s own. Because we are
building the techniques from scratch, I have refrained from making and using a
massive class library, even though some examples could have benefited from it.
If
you want to understand object-oriented programming, it is more important to first
master the techniques and consider your options in code design; dependence on
somebody else’s library for your developments should come a bit later.
An important part of this book is the enclosed source floppy — it has a DOS file
system containing a single shell script to create all the sources arranged by chapter.
There is a ReadMe file — consult it before you say make. It is also quite instructive
to use a program like diff and trace the evolution of the root classes and ooc reports
through the later chapters.
The techniques described here grew out of my disenchantment with C++ when
I needed object-oriented techniques to implement an interactive programming
I
language and realized that I could not forge a portable implementation in C++.
turned to what I knew, ANSI-C, and I was perfectly able to do what I had to.
I have
shown this to a number of people in courses and workshops and others have used
the methods to get their jobs done.
It would have stopped there as my footnote to
a fad, if Brian Kernighan and my publishers, Hans-Joachim Niclas and John Wait,
had not encouraged me to publish the notes (and in due course to reinvent it all
once more). My thanks go to them and to all those who helped with and suffered
through the evolution of this book. Last not least I thank my family — and no,
object-orientation will not replace sliced bread.
Hollage, October 1993
Axel-Tobias Schreiner
vii
___________________________________________________________________________
Contents
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
Constructors and Destructors
Data Types .
Abstract Data Types
An Example — Set .
1.1
.
.
1.2
.
.
1.3
.
.
1.4 Memory Management
.
.
Object
1.5
.
.
.
An Application
1.6
.
.
An Implementation — Set
1.7
.
Another Implementation — Bag .
1.8
1.9
Summary
.
1.10 Exercises
.
.
.
.
.
.
.
.
.
.
.
2 Dynamic Linkage — Generic Functions .
.
Preface
.
1 Abstract Data Types — Information Hiding .
.
.
.
.
.
.
.
.
.
.
.
2.1
.
2.2 Methods, Messages, Classes and Objects
2.3
2.4
2.5
2.6
2.7
2.8
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
Selectors, Dynamic Linkage, and Polymorphisms .
An Application
.
.
.
An Implementation — String .
.
.
Another Implementation — Atom .
.
Summary
.
.
Exercises
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
4 Inheritance — Code Reuse and Refinement
.
.
.
.
.
.
.
3.1
3.2
3.3
3.4
3.5
3.6
3.7
3.8
3.9
3.10 Summary
The Main Loop
.
The Scanner
.
.
The Recognizer
.
The Processor
.
Information Hiding .
Dynamic Linkage
.
A Postfix Writer
.
Arithmetic
.
.
Infix Output
.
.
.
.
3 Programming Savvy — Arithmetic Expressions
4.1
4.2
4.3
4.4
4.5
4.6
4.7
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
A Superclass — Point .
.
Superclass Implementation — Point
Inheritance — Circle
.
.
Linkage and Inheritance .
.
Static and Dynamic Linkage
.
Visibility and Access Functions
.
Subclass Implementation — Circle .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
5
1
1
1
2
3
3
4
4
7
9
9
11
11
12
13
16
17
18
20
20
21
21
22
23
23
24
25
26
28
28
29
31
31
32
33
35
36
37
39
viii___________________________________________________________________________
Contents
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
5 Programming Savvy — Symbol Table
4.8
4.9
4.10 Multiple Inheritance
4.11 Exercises
.
Summary
.
Is It or Has It? — Inheritance vs. Aggregates
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
Scanning Identifiers
5.1
.
Using Variables
5.2
.
.
The Screener — Name
5.3
.
Superclass Implementation — Name .
5.4
Subclass Implementation — Var .
5.5
.
Assignment
5.6
.
.
5.7
Another Subclass — Constants .
.
5.8 Mathematical Functions — Math
.
5.9
Summary
.
5.10 Exercises
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
Roots — Object and Class .
Subclassing — Any
.
.
Implementation — Object
.
Implementation — Class
.
Initialization
.
.
Selectors
.
.
Superclass Selectors .
.
Requirements .
.
.
.
6 Class Hierarchy — Maintainability .
.
.
.
.
.
.
.
.
.
.
.
.
6.1
.
6.2 Metaclasses
.
6.3
.
6.4
.
6.5
.
6.6
.
6.7
.
6.8
.
6.9
.
6.10 A New Metaclass — PointClass .
6.11 Summary
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
7 The ooc Preprocessor — Enforcing a Coding Standard
7.1
7.2
7.3
7.4
7.5
7.6
7.7
7.8
.
.
.
.
.
.
.
.
.
.
.
Point Revisited
.
.
Design
.
.
.
Preprocessing
.
.
Implementation Strategy
.
Object Revisited .
.
.
Discussion .
.
.
.
An Example — List, Queue, and Stack
Exercises
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
8 Dynamic Type Checking — Defensive Programming
8.1
8.2
8.3
8.4
8.5
8.6
8.7
.
.
Technique
.
An Example — list
Implementation .
Coding Standard .
Avoiding Recursion
Summary
.
Exercises
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
40
42
42
43
45
45
45
47
48
50
51
52
52
55
55
57
57
58
59
60
62
63
65
65
66
68
70
73
73
78
79
80
82
84
85
89
91
91
92
94
94
98
100
101
ix
Contents
___________________________________________________________________________
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
9.1
9.2
9.3
9.4
9.5
9.6
Initialization
.
Initializer Lists — munch
Functions for Objects .
Implementation .
.
Summary
.
.
Exercises
.
.
.
.
.
.
10 Delegates — Callback Functions
.
.
.
.
.
.
.
.
.
.
10.1 Callbacks
.
10.2 Abstract Base Classes
.
10.3 Delegates
.
10.4 An Application Framework — Filter
10.5 The respondsTo Method
.
.
10.6 Implementation .
.
.
.
10.7 Another application — sort .
.
10.8 Summary
.
.
10.9 Exercises
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
11 Class Methods — Plugging Memory Leaks
11.1 An Example
.
11.2 Class Methods
.
11.3 Implementing Class Methods
11.4 Programming Savvy — A Classy Calculator
11.5 Summary
11.6 Exercises
9 Static Construction — Self-Organization .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
12 Persistent Objects — Storing and Loading Data Structures
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
12.1 An Example
.
.
.
12.2 Storing Objects — puto()
.
.
12.3 Filling Objects — geto()
.
.
12.4 Loading Objects — retrieve()
.
12.5 Attaching Objects — value Revisited .
12.6 Summary
.
12.7 Exercises
.
13 Exceptions — Disciplined Error Recovery .
.
.
.
.
.
13.1 Strategy .
.
13.2 Implementation — Exception .
13.3 Examples
.
13.4 Summary
.
13.5 Exercises
.
14.1 The Idea .
.
.
14.2 Implementation .
.
14.3 Object-Oriented Design by Example .
14.4 Implementation — Ic .
.
14 Forwarding Messages — A GUI Calculator
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
103
103
104
106
107
109
110
111
111
111
113
114
117
119
122
123
124
125
125
127
128
131
140
141
143
143
148
150
151
153
156
157
159
159
161
163
165
166
167
167
168
171
174
x___________________________________________________________________________
Contents
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
14.5 A Character-Based Interface — curses .
14.6 A Graphical Interface — Xt .
.
14.7 Summary
.
.
.
14.8 Exercises
.
.
.
A ANSI-C Programming Hints
.
.
Names and Scope .
A.1
.
.
Functions
A.2
.
.
.
Generic Pointers — void * .
A.3
.
const
A.4
.
.
.
.
typedef and const
A.5
.
.
.
Structures
A.6
.
.
.
.
Pointers to Functions .
A.7
.
.
Preprocessor
A.8
.
.
.
A.9
Verification — assert.h
.
.
A.10 Global Jumps — setjmp.h .
.
A.11 Variable Argument Lists — stdarg.h
.
A.12 Data Types — stddef.h .
.
.
A.13 Memory Management — stdlib.h .
.
A.14 Memory Functions — string.h
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
B The ooc Preprocessor — Hints on awk Programming .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
B.1
B.2
B.3
B.4
B.5
B.6
B.7
B.8
B.9
Bibliography .
C.1
C.2
C.3
C.4
C Manual
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
Architecture
File Management — io.awk
Recognition — parse.awk
The Database .
.
Report Generation — report.awk
Line Numbering .
.
The Main Program — main.awk .
Report Files
.
.
The ooc Command .
.
.
.
.
.
.
.
.
.
.
.
.
.
Commands .
.
Functions
.
.
Root Classes .
GUI Calculator Classes
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
179
182
188
189
191
191
191
192
193
194
194
195
196
196
196
197
198
198
198
199
199
200
200
201
202
203
204
204
205
207
207
214
214
218
223
1
___________________________________________________________________________
1
Abstract Data Types
Information Hiding
1.1 Data Types
Data types are an integral part of every programming language. ANSI-C has int,
double and char to name just a few. Programmers are rarely content with what’s
available and a programming language normally provides facilities to build new data
types from those that are predefined. A simple approach is to form aggregates
such as arrays, structures, or unions. Pointers, according to C. A. R. Hoare ‘‘a step
from which we may never recover,’’ permit us to represent and manipulate data of
essentially unlimited complexity.
What exactly is a data type? We can take several points of view. A data type
is a set of values — char typically has 256 distinct values, int has many more; both
are evenly spaced and behave more or less like the natural numbers or integers of
mathematics. double once again has many more values, but they certainly do not
behave like mathematics’ real numbers.
Alternatively, we can define a data type as a set of values plus operations to
work with them. Typically, the values are what a computer can represent, and the
operations more or less reflect the available hardware instructions.
int in ANSI-C
does not do too well in this respect: the set of values may vary between machines,
and operations like arithmetic right shift may behave differently.
More complicated examples do not fare much better. Typically we would
define an element of a linear list as a structure
typedef struct node {
struct node * next;
... information ...
} node;
and for the operations we specify function headers like
node * head (node * elt, const node * tail);
This approach, however, is quite sloppy. Good programming principles dictate
that we conceal the representation of a data item and declare only the possible
manipulations.
1.2 Abstract Data Types
We call a data type abstract, if we do not reveal its representation to the user. At a
theoretical
level this requires us to specify the properties of the data type by
mathematical axioms involving the possible operations. For example, we can
remove an element from a queue only as often as we have added one previously,
and we retrieve the elements in the same order in which they were added.
2___________________________________________________________________________
1 Abstract Data Types — Information Hiding
Abstract data types offer great
flexibility to the programmer. Since the
representation is not part of the definition, we are free to choose whatever is easi-
est or most efficient to implement.
If we manage to distribute the necessary infor-
mation correctly, use of the data type and our choice of implementation are totally
independent.
Abstract data types satisfy the good programming principles of information hid-
ing and divide and conquer. Information such as the representation of data items is
given only to the one with a need to know: to the implementer and not to the user.
With an abstract data type we cleanly separate the programming tasks of imple-
mentation and usage: we are well on our way to decompose a large system into
smaller modules.
1.3 An Example — Set
So how do we implement an abstract data type? As an example we consider a set
of elements with the operations add, find, and drop.* They all apply to a set and an
element and return the element added to, found in, or removed from a set.
find
can be used to implement a condition contains which tells us whether an element
is already contained in a set.
Viewed this way, set is an abstract data type. To declare what we can do with
a set, we start a header file Set.h:
#ifndef SET_H
#define SET_H
extern const void * Set;
void * add (void * set, const void * element);
void * find (const void * set, const void * element);
void * drop (void * set, const void * element);
int contains (const void * set, const void * element);
#endif
The preprocessor statements protect the declarations: no matter how many times
we include Set.h, the C compiler only sees the declarations once. This technique of
protecting header files is so standard, that the GNU C preprocessor recognizes it and
does not even access such a file when its protecting symbol is defined.
Set.h is complete, but is it useful? We can hardly reveal or assume less: Set
will have to somehow represent the fact, that we are working with sets; add()
takes an element, adds it to a set, and returns whatever was added or already
present in the set; find() looks for an element in a set and returns whatever is
present in the set or a null pointer; drop() locates an element, removes it from a
set, and returns whatever was removed; contains() converts the result of find()
into a truth value.
____________________________________________________________________________________________
* Unfortunately, remove is an ANSI-C library function to remove a file.
function, we could no longer include stdio.h.
If we used this name for a set
相关推荐
2023年江西萍乡中考道德与法治真题及答案.doc
2012年重庆南川中考生物真题及答案.doc
2013年江西师范大学地理学综合及文艺理论基础考研真题.doc
2020年四川甘孜小升初语文真题及答案I卷.doc
2020年注册岩土工程师专业基础考试真题及答案.doc
2023-2024学年福建省厦门市九年级上学期数学月考试题及答案.doc
2021-2022学年辽宁省沈阳市大东区九年级上学期语文期末试题及答案.doc
2022-2023学年北京东城区初三第一学期物理期末试卷及答案.doc
2018上半年江西教师资格初中地理学科知识与教学能力真题及答案.doc
2012年河北国家公务员申论考试真题及答案-省级.doc
2020-2021学年江苏省扬州市江都区邵樊片九年级上学期数学第一次质量检测试题及答案.doc
2022下半年黑龙江教师资格证中学综合素质真题及答案.doc
