Preface
Elementary Data
Structures with Pascal
Angela B. Shiflet
Elementary Data Structures with Pascal
introduces the CS2 or elementary data structures student to the
subject in a clear, visual, top-down manner. The text first
presents each data structure as an abstract data type (ADT), or a
set of data objects and fundamental operations on this set.
English descriptions and accompanying diagrams, having boldface
to emphasize changes in the structures and the values of the
variables, give the student a visual concept of the data
structure.
Applications are then developed using
pseudocode and ADT operations, often with diagrams to clarify the
words of the algorithms. By first considering data structures on
a high level without concern for the implementation details, the
student obtains a powerful tool which simplifies the process of
handling data and extends naturally the concept of structured
programming.
After studying and using the data structure
on the abstract data type level, the text examines how the
structure is represented and how the operations can be written in
Standard Pascal. Appendix B covers important extensions in Turbo
Pascal and UCSD Pascal. Often, there are several ways to
implement a particular ADT. Advantages and disadvantages of these
implementations and the circumstances which make one more
desirable than another are also discussed.
For the convenience of the professor, a
disk is available with Standard Pascal implementations of the
abstract data types. Use of these files save time in designing,
coding, typing, and testing the Pascal implementations of the
abstract data types. This disk, which is described in greater
detail under Supplementary Materials below, may be copied
freely for the students.
The text presents many applications in
examples, exercises, and programming projects. Each section
contains a number of exercises with answers to selected problems
with boldface numbers in Appendix D and with all the remaining
answers in the Instructor's Manual. A more detailed
description of pedagological features follows.
Pedagological Features
Chapter introduction
One to several paragraphs at the
beginning of each chapter give an overview of the
material in the chapter.
Clear presentation of each data
structure as an abstract data type before discussion of
implementations
A data structure is first considered
on a high level without concern for the details of
implementation. One of the major goals of data
abstraction is to encapsulate the structure so that
details of implementation are hidden from the user. With
such information hidden, the programmer can consider
applications on a higher plane with major operations as
opposed to on a lower level where there is the very real
danger of becoming lost in a sea of details.
Example operations/applications
Examples help to clarify the material.
The organized approach to examples, particularly with
accompanying diagrams, aids understanding of the
material. Applications illustrate the use of a data
structure, demonstrate its importance, and provide
interest.
Numerous diagrams with boldface to
emphasize changes
Diagrams help students visualize the
actions of operations and algorithms.
Implementations of an ADT presented
after the formal definition
Only after students become familiar
with a data structure on the higher level of an ADT does
the text consider implementation details.
Historical anecdotes
Such anecdotes add interest to the
text. Moreover, they often present material that a
computer science major should know about the history of
the discipline.
Numerous exercises at the end of each
section
Exercises are at the end of each
section, not just at the end of the chapter. On the
average there are 21 exercises per section, 95 per
chapter. Exercises include short answer problems,
diagrams of the execution of segments, design of
procedures and functions using pseudocode and ADT
operations, coding of procedures and functions,
applications, and questions from the Advanced Placement
Examination in Computer Science.
Answers to all exercises
Answers in Appendix D to some
exercises (those with boldface numbers) for each section
allow students to check their work for immediate
reinforcement. The Instructor's Manual contains
answers to the remaining exercises. Answers involving
Pascal code have been computer tested.
Programming projects
On the average, there are 6
programming projects per chapter. These are major
assignments to be implemented on the computer. By
completing such a project, the student implements an
application of the data structure and enhances his or her
understanding of the material and abilities in software
design.
Organized comparison of different
implementations of ADTs
These comparisons provide guidelines
for which implementation to employ in various situations.
Organization
Chapter 1
Sections 1.1 through 1.3 examine the
process of developing quality software. These sections
provide a good review and enhancement of the programming
principles covered in the prerequisite course of Pascal
programming. Early discussion of analysis of algorithms
(Section 1.4) provides a measure of the efficiency of
algorithms to be used throughout the text.
Chapter 2
Recursion is covered early (Section
2.1) in the text. Thus, this powerful technique is
employed in the development of a number of procedures and
functions. Section 2.2 compares recursion and iteration
and discusses how to convert a recursive algorithm to an
iterative one. The study of program verification
techniques is important to the computer science major.
The professor may decide, however, to postpone its study
in Section 2.3 to later in the course. The last section
of the chapter introduces the topic of abstract data
type, the fundamental approach to data structures
employed in the text.
Chapter 3
In this chapter the text continues the
study of abstract data types by examining various
composite types that are built into Pascal--arrray,
record, file, and set. After defining each as an ADT, the
text presents its built-in Standard Pascal implementation
along with applications. The discussion of arrays is
augmented by a study of the sequential and binary search
methods in Section 3.2. Depending on the level of the
class, the professor can treat this chapter as reference
material or cover the topics in detail.
Chapter 4
Chapter 4 covers the ADT string along
with various array implementations and applications in
text editing. After the discussion in Chapter 7, a linked
list implementation is considered and compared to the
array one (Section 8.2). The professor again has the
option of treating the material of this chapter in a
cursory or detailed fashion.
Chapter 5
Section 5.1 gives a conceptual view of
a stack, defines stack as an abstract data type, and
presents various short applications. The next section
discusses an implementation of the ADT stack with arrays,
postponing one with linked lists until Chapter 8.
Additional applications in Section 5.3 include postfix
notation and simulation of recursion using a stack and
iteration.
Chapter 6
The format of this chapter parallels
that of Chapter 5. The first section covers the abstract
data type queue with several short applications, and
Section 6.2 presents an array implementation. The last
section develops a simulation of a waiting line at a post
office with top-down design and pseudocode development of
the procedures.
Chapter 7
After studying pointers in Section
7.1, the text devotes the rest of this chapter to the
abstract data type linked list. Manipulations of linked
lists pictorially (Section 7.2) precede the formal ADT
definition (Section 7.3). Section 7.4 covers
implementations with dynamic and static memory
allocations. Circular, doubly, and multiply linked lists
are discussed in the optional, last section along with an
application to sparse matrices.
Chapter 8
In Section 8.1 the text discusses
various applications of linked lists: memory management
with the development of user-defined New and Dispose
operations; arithmetic on very large, nonnegative
integers; and a generalized list structure similar to
that employed by the language LISP. In Sections 8.2
through 8.4 the text reconsiders the abstract data types
of string, stack, and queue, previously implemented
statically with arrays, now implemented dynamically with
linked lists. For each ADT the advantages and
disadvantages of these two implementation techniques are
discussed. Faced with a choice in the coding of the
abstract data types, in Section 8.5 the text reexamines
how the programmer should develop Pascal programs with
ADT objects and operations hidden, to be used like they
are predefined. The student sees that by using ADT
objects and operations in the development of
applications, he of she can substitute different
implementations of the ADT without changing significantly
the code of the application program.
Chapter 9
This chapter examines the ADT table
along with five implementations and applications, such as
to relational data bases. Section 9.2 compares and
contrasts four implementations of the ADT table involving
a static memory allocation with ordered and unordered
arrays and a dynamic memory allocation with ordered and
unordered linked lists. The hash table implementation is
presented in the last section.
Chapter 10
The first section of this chapter
introduces tree terminology and traversals, while the
next defines the abstract data type binary tree. Two
binary tree implementations involving pointers are
presented in Sections 10.3 and 10.4. With the first of
these implementations, many of the algorithms are
developed recursively. The professor may choose to omit
the second method, using threaded trees, which
illustrates a nonrecursive alternative. Section 10.5
explores binary search trees, while optional Section 10.6
introduces AVL trees. The last of this chapter examines
several applications of binary trees: expression trees,
decision trees, game trees, and Huffman codes.
Chapter 11
In this chapter the text presents
several algorithms for sorting: insertion sort, selection
sort, quicksort, heapsort, mergesort, and sorting with a
permutation array. This examination of sorting considers
the complexities of the various methods and the
situations for which they are best suited. The professor
may, however, choose to omit one or more of these
techniques, such as the selection sort of Section 11.2.
Because this chapter is substantially self-contained, the
professor also has the option of covering the material
earlier in the course.
Chapter 12
The abstract data type graph,
discussed in Section 12.1, is implemented with adjacency
matrices (Section 12.2) and with adjacency lists (Section
12.3). Section 12.4 presents algorithms with accompanying
diagrams for depth-first and breadth-first traversals of
graphs. In the last section the text covers applications
involving mazes, minimal spanning trees, and shortest
paths in networks.
Supplementary Materials
Instructor's Manual
An Instructor's Manual, written by the
author and John S. Hinkel, contains solutions to text
exercises not found in the appendix, answers to at least
one project per chapter, and additional test problems
with answers. Dr. Hinkel has tested on the computer
operations coded in Pascal.
Disk of ADT implementations
- A disk with implementations in
Standard Pascal of the abstract data types is available
upon request for the professor. Each ADT implementation
appears in two source files on the disk:
- A text file in the format of a
Turbo Pascal unit is ready for compilation in
that version of the language. Minor modifications
convert this file to one that can be used by
other versions of Pascal which permit separate
compilation.
- Another text file contains the
implementation as it would appear after a program
statement. For appropriate versions of Pascal,
this file can be used as an "include"
file. If separately compiled units or include
files are not available, this text file can be
copied for use in a program.
A file, called "Read Me,"
describes how to employ these. Since the files are stored
as text files, they can be easily edited with a word
processor. The disk is available as a 3ڌ''
Macintosh, 3ڌ'' IBM, or 5ډ'' IBM disk. A
site license is issued to any school which adopts the
text.
Acknowledgements
Many people provided valuable assistance in
the completion of this book. John S. Hinkel has been extremely
helpful in many ways. As coauthor of the Instructor's Manual,
among other tasks, he wrote and implemented the programming
exercises, projects, and units in Pascal. As problem checker, he
carefully verified all examples and answers included in the text,
testing operations on the computer where appropriate. As one of
the reviewers of the first and second drafts of the manuscript,
he provided insightful suggestions for improvements to the book.
As a colleague, he gave me another viewpoint concerning issues
relative to the text. I truly appreciate his help and friendship.
The administration at Wofford College,
where I teach, has been generous in providing me encouragement
and a reduced load to write the book.
Friends at Lawrence Livermore National
Laboratory (LLNL), where I have worked for six summers, have
given me many opportunities and taught me much which have
enhanced this text. Special thanks go to Ted Einwohner, Bob
Cralle, George Michael, and John Ranelletti ***. I greatly
appreciate all the time and effort of James E. Stoots, Jr.,
technical photographer at LLNL who created the beautiful cover
picture for the book.
Peter Marshall, Executive Editor at West
Publishing Company, is a marvelous editor. He provided many good
ideas, a clear direction, and valuable assistance. Tambohra ***
Moore, Production Editor, kept the production moving smoothly and
on time. My thanks also go to *** for her accurate copy editing;
*** for her nice design; Marlene Bates for her assistance in the
review stage; and *** , Marketing ***, for development of the
marketing brochures.
I am grateful to the following reviewers
who offered many valuable constructive criticisms:
***
David Kidd, a student at Wofford College,
and George W. Shiflet, Jr., my husband, we helpful in proof
reading the galleys and page proofs.
George and my parents, Isabell and Carroll
Buzzett, have given me many years of love and encouragement.
Without them this book would not be possible; and so, it is
dedicated to those whom I love the most. And thank you, God, for
answering so many prayers.