Free Essay


In: Computers and Technology

Submitted By teitat
Words 6423
Pages 26
Preface C++ Page iii Monday, July 16, 2001 1:44 PM


Welcome to the third edition of Data Abstraction and Problem Solving with
C++: Walls and Mirrors. Since the publication of the second edition, we all have gained experience with teaching data abstraction in an objectoriented way using C++. This edition reflects that experience and the evolution that C++ has taken.
This book is based on the original Intermediate Problem Solving and
Data Structures: Walls and Mirrors by Paul Helman and Robert Veroff
(© 1986 by The Benjamin/Cummings Publishing Company, Inc.). This work builds on their organizational framework and overall perspective and includes technical and textual content, examples, figures, and exercises derived from the original work. Professors Helman and Veroff introduced two powerful analogies, walls and mirrors, that have made it easier for us to teach—and to learn—computer science.
With its focus on data abstraction and other problem-solving tools, this book is designed for a second course in computer science. In recognition of the dynamic nature of the discipline and the great diversity in undergraduate computer science curricula, this book includes comprehensive coverage of enough topics to make it appropriate for other courses as well. For example, you can use this book in courses such as introductory data structures or advanced programming and problem solving. The goal remains to give students a superior foundation in data abstraction, object-oriented programming, and other modern problemsolving techniques.

Thousands of students before you have read and learned from Walls and
Mirrors . The walls and mirrors in the title represent two fundamental problem-solving techniques that appear throughout the presentation. Data abstraction isolates and hides the implementation details of a module from the rest of the program, much as a wall can isolate and hide you from your neighbor. Recursion is a repetitive technique that solves a problem by solving smaller problems of exactly the same type, much as mirror images grow smaller with each reflection.
This book was written with you in mind. As former college students, and as educators who are constantly learning, we appreciate the importance of a clear presentation. Our goal is to make this book as understandable as possible. To help you learn and to review for exams, we have iii Preface C++ Page iv Monday, July 16, 2001 1:44 PM



included such learning aids as margin notes, chapter summaries, self-test exercises with answers, and a glossary. As a help during programming, you will find C++ reference material in the appendixes and inside the covers. You should review the list of this book’s features given later in this preface in the section “Pedagogical Features.”
The presentation makes some basic assumptions about your knowledge of C++. Some of you may need to review this language or learn it for the first time by consulting Appendix A of this book. You will need to know about the selection statements if and switch; the iteration statements for, while, and do; functions and argument passing; arrays; strings; structures; and files. This book covers C++ classes in Chapters 1, 3, and 8 and does not assume that you already know this topic. We assume no experience with recursive functions, which are included in Chapters 2 and 5.
All of the C++ source code that appears in this book is available for your use. Later in this preface, the description of supplementary materials tells you how to obtain these files. Note, however, that your instructor may already have obtained them for you.

This edition of Walls and Mirrors uses C++ to enhance its emphasis on data abstraction and data structures. The book carefully accounts for the strengths and weaknesses of the C++ language and remains committed to a pedagogical approach that makes the material accessible to students at the introductory level.

We assume that readers either know the fundamentals of C++ or know another language and have an instructor who will help them make the transition to C++ by using the provided appendix. The book formally introduces C++ classes, and so does not assume prior knowledge of them. Included are the basic concepts of object-oriented programming, inheritance, virtual functions, and class templates, all in C++. Although the book provides an introduction to these topics in connection with the implementations of abstract data types (ADTs) as classes, the emphasis remains on the ADTs, not on C++. The material is presented in the context of object-based programming, but it assumes that future courses will cover object-oriented design and software engineering in detail, so that the focus can remain on data abstraction. We do, however, introduce the Unified Modeling Language (UML) as a design tool.

The extensive coverage of this book should provide you with the material that you want for your course. You can select the topics you desire

Preface C++ Page v Monday, July 16, 2001 1:44 PM



and present them in an order that fits your course. The chapter dependency chart shows which chapters should be covered before a given chapter can be taught.
In Part I, you can choose among topics according to your students’ background. Three of the chapters in this part provide an extensive introduction to data abstraction and recursion. Both topics are important, and there are various opinions about which should be taught first.

This chart indicates the chapters that should be studied before you cover a particular chapter.

Chapter 1

Chapter 3
Data abstraction
Chapter 2
Chapter 4
Linked lists
Chapter 5
More recursion

Chapter 6

Chapter 7

Chapter 8
Advanced C++ topics

Chapter 9
Algorithm efficiency, sorting

Chapter 10

Chapter 13

Chapter 11
Tables, priority queues

Chapter 12
Advanced tables
Chapter 14
Section on external tables
Dependency by one section of chapter
Dependency that you can ignore

Section on external sorting

Preface C++ Page vi Monday, July 16, 2001 1:44 PM



Although in this book a chapter on recursion both precedes and follows the chapter on data abstraction, you can simply rearrange this order.
Part II treats topics that you can also cover in a flexible order. For example, you can cover all or parts of Chapter 8 on advanced C++ either before or after you cover stacks (Chapter 6). You can cover algorithm efficiency and sorting (Chapter 9) any time after Chapter 5. You can introduce trees before queues or graphs before tables, or cover hashing, balanced search trees, or priority queues any time after tables and in any order. You also can cover external methods (Chapter 14) earlier in the course. For example, you can cover external sorting after you cover mergesort in Chapter 9.

Data Abstraction
The design and use of abstract data types permeate this book’s problemsolving approach. Several examples demonstrate how to design an ADT as part of the overall design of a solution. All ADTs are first specified—in both English and pseudocode—and then used in simple applications before implementation issues are considered. The distinction between an
ADT and the data structure that implements it remains in the forefront throughout the discussion. The book explains both encapsulation and
C++ classes early. Students see how C++ classes hide an implementation’s data structure from the client of the ADT. Abstract data types such as lists, stacks, queues, trees, tables, heaps, and priority queues form the basis of our discussions.

Problem Solving
This book helps students learn to integrate problem-solving and programming abilities by emphasizing both the thought processes and the techniques that computer scientists use. Learning how a computer scientist develops, analyzes, and implements a solution is just as important as learning the mechanics of the algorithm; a cookbook approach to the material is insufficient.
The presentation includes analytical techniques for the development of solutions within the context of example problems. Abstraction, the successive refinement of both algorithms and data structures, and recursion are used to design solutions to problems throughout the book.
C++ pointers and linked list processing are introduced early and used in building data structures. The book also introduces at an elementary level the order-of-magnitude analysis of algorithms. This approach allows the consideration—first at an informal level, then more quantitatively— of the advantages and disadvantages of array-based and pointer-based data structures. An emphasis on the trade-offs among potential solutions and implementations is a central problem-solving theme.
Finally, programming style, documentation including preconditions and postconditions, debugging aids, and loop invariants are important

Preface C++ Page vii Monday, July 16, 2001 1:44 PM



parts of the problem-solving methodology used to implement and verify solutions. These topics are covered throughout the book.

Classic application areas arise in the context of the major topics of this book. For example, the binary search, quicksort, and mergesort algorithms provide important applications of recursion and introduce orderof-magnitude analysis. Such topics as balanced search trees, hashing, and file indexing continue the discussion of searching. Searching and sorting are considered again in the context of external files.
Algorithms for recognizing and evaluating algebraic expressions are first introduced in the context of recursion and are considered again later as an application of stacks. Other applications include, for example, the Eight Queens problem as an example of backtracking, eventdriven simulation as an application of queues, and graph searching and traversals as other important applications of stacks and queues.

This edition retains the underlying approach and philosophy of the second edition. We present data abstraction and programming both as general concepts and in the context of C++. No sentence, example, margin note, or figure escaped scrutiny during the preparation of this edition.
Many changes, additions, and deletions to the text, figures, and margin notes were made to update and clarify the presentation. All C++ programs were revised to reflect recent changes to the language.
Although we revised all chapters and appendixes, here is a list of the major changes to the book.

The specifications of all ADT operations now use UML notation to clarify the purpose and data type of their parameters.

Chapter 1 enhances its coverage of object-oriented design and introduces the Unified Modeling Language (UML). We have revised our naming conventions for C++ identifiers to be consistent with common practice. This change will help students who either know Java or will learn Java later.

Chapter 3 briefly introduces inheritance after its presentation of
C++ classes. Also covered are the C++ namespace and exceptions. Although the ADTs in this chapter return boolean flags to indicate error conditions, subsequent chapters use exceptions.

Chapter 4 includes a new section about the C++ Standard Template Library (STL). Class templates, containers, and iterators are introduced. More extensive coverage of these topics is deferred until Chapter 8. Chapter 4 also considers the STL class list.

Preface C++ Page viii Monday, July 16, 2001 1:44 PM



Other classes in the STL are presented throughout the book, and you can either skip or postpone covering them, as desired.

Chapter 6 includes the STL class stack.

Chapter 7 includes the STL class queue.

Chapter 8 provides a deeper discussion of inheritance and class templates than was given earlier. Also covered are C++ friends and iterators.

Appendix A is an updated review of C++ that now includes coverage of exceptions. Appendix C is an updated list of C++ headers. Appendix E is new and contains the STL classes list, stack, and queue.

The pedagogical features and organization of this book were carefully designed to facilitate learning and to allow instructors to tailor the material easily to a particular course.

Pedagogical Features
This book contains the following features that help students not only during their first reading of the material, but also during subsequent review: •

Chapter outlines and previews.

Boxes listing key concepts in the material.

Margin notes.

Chapter summaries.

Cautionary warnings about common errors and misconceptions.

Self-test exercises with answers.

Chapter exercises and programming problems. The most challenging exercises are labeled with asterisks. Answers to the exercises appear in the Instructor’s Resource Manual.

Specifications for all major ADTs in both English and pseudocode, as well as in UML notation.

C++ class definitions for all major ADTs.

Examples that illustrate the role of classes and ADTs in the problem-solving process.

Appendixes, including a review of C++.

Glossary of terms.

Preface C++ Page ix Monday, July 16, 2001 1:44 PM


The chapters in this book are organized into two parts. In most cases,
Chapters 1 through 11 will form the core of a one-semester course.
Chapters 1 or 2 might be review material for your students. The coverage given to Chapters 11 through 14 will depend on the role the course plays in your curriculum. More detailed suggestions for using this book with different courses appear in the Instructor’s Resource Manual.
Part I: Problem-Solving Techniques. The first chapter in Part I emphasizes the major issues in programming and software engineering. A new introduction to the Unified Modeling Language (UML) is given here. The next chapter discusses recursion for those students who have had little exposure to this important topic. The ability to think recursively is one of the most useful skills that a computer scientist can possess and is often of great value in helping one to better understand the nature of a problem. Recursion is discussed extensively in this chapter and again in
Chapter 5 and is used throughout the book. Included examples range from simple recursive definitions to recursive algorithms for language recognition, searching, and sorting.
Chapter 3 covers data abstraction and abstract data types (ADTs) in detail. After a discussion of the specification and use of an ADT, the chapter presents C++ classes and uses them to implement ADTs. This chapter includes a brief introduction to inheritance, the C++ namespace, and exceptions. Chapter 4 presents additional implementation tools in its discussion of C++ pointer variables and linked lists. This chapter also introduces class templates, the C++ Standard Template Library (STL), containers, and iterators.
You can choose among the topics in Part I according to the background of your students and cover these topics in several orders.
Part II: Problem Solving with Abstract Data Types. Part II continues to explore data abstraction as a problem-solving technique. Basic abstract data types such as the stack, queue, binary tree, binary search tree, table, heap, and priority queue are first specified and then implemented as classes. The ADTs are used in examples and their implementations are compared. Chapter 8 extends the coverage of C++ classes by further developing inheritance, class templates, and iterators. The chapter then introduces virtual functions and friends. Chapter 9 formalizes the earlier discussions of an algorithm’s efficiency by introducing order-of-magnitude analysis and Big O notation. The chapter examines the efficiency of several searching and sorting algorithms, including the recursive mergesort and quicksort. Part II also includes advanced topics—such as balanced search trees
(2-3, 2-3-4, red-black, and AVL trees) and hashing—that are examined as table implementations. These implementations are analyzed to determine the table operations that each supports best.


Preface C++ Page x Monday, July 16, 2001 1:44 PM



Finally, data storage in external direct access files is considered.
Mergesort is modified to sort such data, and external hashing and B-tree indexes are used to search it. These searching algorithms are generalizations of the internal hashing schemes and 2-3 trees already developed.

The following supplementary materials are available online to assist instructors and students.

Source code. All of the C++ classes, functions, and programs that appear in the book are available to readers.

Errata. We have tried not to make mistakes, but mistakes are inevitable. A list of detected errors is available and updated as necessary. You are invited to contribute your finds.

The source code and errata list are available at the URL •

Instructor’s Resource Manual. Solutions to the exercises at the end of the chapters as well as teaching notes and suggestions are available only to instructors through your Addison-Wesley sales representative.

Walls and Mirrors continues to evolve. Your comments, suggestions, and corrections will be greatly appreciated. You can contact us directly by e-mail at or or through the publisher:
Computer Science Editorial Office
75 Arlington Street
Boston, MA 02116

Preface C++ Page xi Monday, July 16, 2001 1:44 PM


The suggestions from outstanding reviewers contributed greatly to this book’s present form. In alphabetical order, they are
Vicki H. Allan — Utah State University
Don Bailey — Carleton University
Sebastian Elbaum — University of Nebraska, Lincoln
Matthew Evett — Eastern Michigan University
Susan Gauch — University of Kansas
Martin Granier — Western Washington University
Judy Hankins — Middle Tennessee State University
Sr. Joan Harnett — Manhattan College
Tom Irby — University of North Texas
Edwin J. Kay — Lehigh University
David Naffin — Fullerton College
Paul Nagin — Hofstra University
Bina Ramamurthy — SUNY at Buffalo
Dwight Tunistra
Karen VanHouten — University of Idaho
Kathie Yerion — Gonzaga University
We especially thank the people who produced this book. Our editors at Addison-Wesley, Susan Hartman Sullivan and Katherine Harutunian, provided invaluable guidance and assistance. This book would not have been printed on time without our project manager, Daniel Rausch from
Argosy Publishing. Thank you, Daniel, for keeping us on schedule.
Many thanks to our copy editor, Rebecca Pepper, for smoothing out our rough edges. Also, Pat Mahtani, Michael Hirsch, Gina Hagen, Jarrod
Gibbons, Michelle Renda, and Joe Vetere contributed their expertise and care throughout the production of this book.
Many other wonderful people have contributed in various ways.
They are Doug McCreadie, Michael Hayden, Sarah Hayden, Andrew
Hayden, Albert Prichard, Ted Emmott, Maybeth Conway, Lorraine
Berube, Marge White, James Kowalski, Gerard Baudet, Joan Peckham, Ed
Lamagna, Victor Fay-Wolfe, Bala Ravikumar, Lisa DiPippo, Jean-Yves


Preface C++ Page xii Monday, July 16, 2001 1:44 PM



Hervé, Hal Records, Wally Wood, Elaine Lavallee, Ken Sousa, Sally
Lawrence, Lianne Dunn, Gail Armstrong, Tom Manning, Jim Labonte,
Jim Abreu, and Bill Harding.
Numerous other people provided input for the previous editions of
Walls and Mirrors at various stages of its development. All of their comments were useful and greatly appreciated. In alphabetical order, they are
Karl Abrahamson, Stephen Alberg, Ronald Alferez, Vicki Allan, Jihad
Almahayni, James Ames, Claude W. Anderson, Andrew Azzinaro, Tony
Baiching, Don Bailey, N. Dwight Barnette, Jack Beidler, Wolfgang W.
Bein, Sto Bell, David Berard, John Black, Richard Botting, Wolfin Brumley, Philip Carrigan, Stephen Clamage, Michael Clancy, David Clayton,
Michael Cleron, Chris Constantino, Shaun Cooper, Charles Denault,
Vincent J. DiPippo, Suzanne Dorney, Colleen Dunn, Carl Eckberg, Karla
Steinbrugge Fant, Jean Foltz, Susan Gauch, Marguerite Hafen , Randy
Hale, George Hamer, Judy Hankins, Lisa Hellerstein, Mary Lou Hines,
Jack Hodges, Stephanie Horoschak, Lily Hou, John Hubbard, Kris Jensen,
Thomas Judson, Laura Kenney, Roger King, Ladislav Kohout, Jim
LaBonte, Jean Lake, Janusz Laski, Cathie LeBlanc, Urban LeJeune, John
M. Linebarger, Ken Lord, Paul Luker, Manisha Mande, Pierre-Arnoul de
Marneffe, John Marsaglia, Jane Wallace Mayo, Mark McCormick, Dan
McCracken, Vivian McDougal, Shirley McGuire, Sue Medeiros, Jim
Miller, Guy Mills, Rameen Mohammadi, Cleve Moler, Narayan Murthy,
Paul Nagin, Rayno Niemi, John O’Donnell, Andrew Oldroyd, Larry
Olsen, Raymond L. Paden, Roy Pargas, Brenda C. Parker, Thaddeus F.
Pawlicki, Keith Pierce, Lucasz Pruski, George B. Purdy, David Radford,
Steve Ratering, Stuart Regis, J. D. Robertson, Robert A. Rossi, John Rowe,
Michael E. Rupp, Sharon Salveter, Charles Saxon, Chandra Sekharan,
Linda Shapiro, Yujian Sheng, Mary Shields, Ronnie Smith, Carl Spicola,
Richard Snodgrass, Neil Snyder, Chris Spannabel, Paul Spirakis, Clinton
Staley, Matt Stallman, Mark Stehlick, Benjamin T. Schomp, Harriet
Taylor, David Teague, David Tetreault, John Turner, Susan Wallace, James
E. Warren, Jerry Weltman, Nancy Wiegand, Howard Williams, Brad
Wilson, James Wirth, Salih Yurttas, and Alan Zaring.
Thank you all.
F. M. C.
J. J. P.

CH03.FM Page 111 Monday, July 16, 2001 1:34 PM



Data Abstraction:
The Walls

Abstract Data Types
Specifying ADTs
The ADT List
The ADT Sorted List
Designing an ADT
Axioms (Optional)
Implementing ADTs
C++ Classes
C++ Namespaces
An Array-Based Implementation of the ADT List
C++ Exceptions
Self-Test Exercises
Programming Problems

CH03.FM Page 112 Monday, July 16, 2001 1:34 PM




PREVIEW This chapter elaborates on data abstraction, which was introduced in Chapter 1 as a technique for increasing the modularity of a program—for building “walls” between a program and its data structures.
During the design of a solution, you will discover that you need to support several operations on the data and therefore need to define abstract data types (ADTs). This chapter will introduce some simple abstract data types and use them to demonstrate the advantages of abstract data types in general. In Part II of this book, you will see several other important ADTs.
Only after you have clearly specified the operations of an abstract data type should you consider data structures for implementing it. This chapter explores implementation issues and introduces C++ classes as a way to hide the implementation of an ADT from its users.


A modular program is easier to write, read, and modify

Write specifications for each module before implementing it

Isolate the implementation details of a module from other modules Modularity is a technique that keeps the complexity of a large program manageable by systematically controlling the interaction of its components. You can focus on one task at a time in a modular program without other distractions. Thus, a modular program is easier to write, read, and modify. Modularity also isolates errors and eliminates redundancies.
You can develop modular programs by piecing together existing software components with functions that have yet to be written. In doing so, you should focus on what a module does and not on how it does it.
To use existing software, you need a clear set of specifications that details how the modules behave. To write new functions, you need to decide what you would like them to do and proceed under the assumption that they exist and work. In this way you can write the functions in relative isolation from one another, knowing what each one will do but not necessarily how each will eventually do it. That is, you should practice functional abstraction.
While writing a module’s specifications, you must identify details that you can hide within the module. The principle of information hiding involves not only hiding these details, but also making them inaccessible from outside a module. One way to understand information hiding is to imagine walls around the various tasks a program performs.
These walls prevent the tasks from becoming entangled. The wall around each task T prevents the other tasks from “seeing” how T is performed.
Thus, if task Q uses task T, and if the method for performing task T changes, task Q will not be affected. As Figure 3-1 illustrates, the wall prevents task Q’s method of solution from depending on task T’s method of solution.
The isolation of the modules cannot be total, however. Although task
Q does not know how task T is performed, it must know what task T is

CH03.FM Page 113 Monday, July 16, 2001 1:34 PM






Figure 3-1
Isolated tasks: the implementation of task T does not affect task Q

and how to initiate it. For example, suppose that a program needs to operate on a sorted array of names The program may, for instance, need to search the array for a given name or display the names in alphabetical order. The program thus needs a function S that sorts an array of names.
Although the rest of the program knows that function S will sort an array, it should not care how S accomplishes its task. Thus, imagine a tiny slit in each wall, as Figure 3-2 illustrates. The slit is not large enough to allow the outside world to see the function’s inner workings, but

Program that uses method S

Figure 3-2
A slit in the wall

Request to perform operation
Result of operation

Implementation of method S

CH03.FM Page 114 Monday, July 16, 2001 1:34 PM




things can pass through the slit into and out of the function. For example, you can pass the array into the sort function, and the function can pass the sorted array out to you. What goes in and comes out is governed by the terms of the function’s specifications, or contract: If you use the function in this way, this is exactly what it will do for you .
Often the solution to a problem requires operations on data. Such operations are broadly described in one of three ways:

An ADT is a collection of data and a set of operations on that data Specifications indicate what
ADT operations do, but not how to implement them
Data structures are part of an
ADT’s implementation

Add data to a data collection.
Remove data from a data collection.

Both functional and data abstraction ask you to think
“what,” not “how ”

Typical operations on data

Ask questions about the data in a data collection.

The details of the operations, of course, vary from application to application, but the overall theme is the management of data. Realize, however, that not all problems use or require these operations.
Data abstraction asks that you think in terms of what you can do to a collection of data independently of how you do it. Data abstraction is a technique that allows you to develop each data structure in relative isolation from the rest of the solution. The other modules of the solution will “know” what operations they can perform on the data, but they should not depend on how the data is stored or how the operations are performed. Again, the terms of the contract are what and not how. Thus, data abstraction is a natural extension of functional abstraction.
A collection of data together with a set of operations on that data are called an abstract data type, or ADT. For example, suppose that you need to store a collection of names in a manner that allows you to search rapidly for a given name. The binary search algorithm described in Chapter 2 enables you to search an array efficiently, if the array is sorted. Thus, one solution to this problem is to store the names sorted in an array and to use a binary search algorithm to search the array for a specified name. You can view the sorted array together with the binary search algorithm as an ADT that solves this problem.
The description of an ADT’s operations must be rigorous enough to specify completely their effect on the data, yet it must not specify how to store the data nor how to carry out the operations. For example, the
ADT operations should not specify whether to store the data in consecutive memory locations or in disjoint memory locations. You choose a particular data structure when you implement an ADT.
Recall that a data structure is a construct that you can define within a programming language to store a collection of data. For example, arrays and structures, which are built into C++, are data structures. However, you can invent other data structures. For example, suppose that you wanted a data structure to store both the names and salaries of a group of employees. You could use the following C++ statements: const int MAX_NUMBER = 500; string names[MAX_NUMBER]; double salaries[MAX_NUMBER];

CH03.FM Page 115 Monday, July 16, 2001 1:34 PM



Here the employee names[i] has a salary of salaries[i]. The two arrays names and salaries together form a data structure, yet C++ has no single data type to describe it.
When a program must perform data operations that are not directly supported by the language, you should first design an abstract data type and carefully specify what the ADT operations are to do (the contract).
Then—and only then—should you implement the operations with a data structure. If you implement the operations properly, the rest of the program will be able to assume that the operations perform as specified— that is, that the terms of the contract are honored. However, the program must not depend on a particular method for supporting the operations.
An abstract data type is not another name for a data structure.

Carefully specify an ADT's operations before you implement them


ADTs versus Data Structures

An abstract data type is a collection of data and a set of operations on that data.

A data structure is a construct within a programming language that stores a collection of data.

To give you a better idea of the conceptual difference between an ADT and a data structure, consider a refrigerator’s ice dispenser, as Figure 3-3 illustrates. It has water as input and produces as output either chilled water, crushed ice, or ice cubes according to which one of three buttons you push. It also has an indicator that lights when no ice is presently available. The dispenser is analogous to an abstract data type. The water is analogous to data; the operations are chill, crush, cube, and isEmpty. At this level of design, you are not concerned with how the dispenser will perform its operations, only that it performs them. If you want crushed ice, do you really care how the dispenser accomplishes its task as long as it does so correctly? Thus, after you have specified the dispenser’s functions, you can design many uses for crushed ice without knowing how the

Figure 3-3

Out-of-ice indicator
Chilled Crushed water ice

A dispenser of chilled water, crushed ice, and ice cubes

Ice cubes Water

ADTs and data structures are not the same

CH03.FM Page 116 Monday, July 16, 2001 1:34 PM


A program should not depend on the details of an ADT's implementation Using an ADT is like using a vending machine



dispenser accomplishes its tasks and without the distraction of engineering details.
Eventually, however, someone must build the dispenser. Exactly how will this machine produce crushed ice, for example? It could first make ice cubes and then either crush them between two steel rollers or smash them into small pieces by using hammers. Many other techniques are possible. The internal structure of the dispenser corresponds to the implementation of the ADT in a programming language, that is, to a data structure.
Although the owner of the dispenser does not care about its inner workings, he or she does want a design that is as efficient in its operation as possible. Similarly, the dispenser’s manufacturer wants a design that is as easy and cheap to build as possible. You should have these same concerns when you choose a data structure to implement an ADT in C++.
Even if you do not implement the ADT yourself, but instead use an already implemented ADT, you—like the person who buys a refrigerator— should care about at least the ADT’s efficiency.
Notice that the dispenser is surrounded by steel walls. The only breaks in the walls accommodate the input (water) to the machine and its output (chilled water, crushed ice, or ice cubes). Thus, the machine’s interior mechanisms are not only hidden from the user but also are inaccessible. In addition, the mechanism of one operation is hidden from and inaccessible to another operation.
This modular design has benefits. For example, you can improve the operation crush by modifying its module without affecting the other modules. You could also add an operation by adding another module to the machine without affecting the original three operations. Thus, both abstraction and information hiding are at work here.
To summarize, data abstraction results in a wall of ADT operations between data structures and the program that accesses the data within these data structures, as Figure 3-4 illustrates. If you are on the program’s side of the wall, you will see an interface that enables you to communicate with the data structure. That is, you request the ADT operations to manipulate the data in the data structure, and they pass the results of these manipulations back to you.
This process is analogous to using a vending machine. You press buttons to communicate with the machine and obtain something in return. The machine’s external design dictates how you use it, much as an ADT’s specifications govern what its operations are and what they do.
As long as you use a vending machine according to its design, you can ignore its inner technology. As long as you agree to access data only by using ADT operations, your program can be oblivious to any change in the data structures that implement the ADT.
The following pages describe how to use an abstract data type to realize data abstraction’s goal of separating the operations on data from the implementation of these operations. In doing so, we will look at several examples of ADTs.

CH03.FM Page 117 Monday, July 16, 2001 1:34 PM






Request to perform operation find Result of operation display Wall of ADT operations

Figure 3-4
A wall of ADT operations isolates a data structure from the program that uses it

To elaborate on the notion of an abstract data type, consider a list that you might encounter, such as a list of chores, a list of important dates, a list of addresses, or the grocery list pictured in Figure 3-5. As you write a grocery list, where do you put new items? Assuming that you write a neat one-column list, you probably add new items to the end of the list. You could just as well add items to the beginning of the list or add them so that your list is sorted alphabetically. Regardless, the items on a list appear in a sequence. The list has one first item and one last item. Except for the first and last items, each item has a unique predecessor and a unique successor. The first item—the head or front

milk eggs butter

apples bread chicken

Figure 3-5
A grocery list

CH03.FM Page 118 Monday, July 16, 2001 1:34 PM




of the list—does not have a predecessor, and the last item—the tail or end of the list—does not have a successor.
Lists contain items of the same type: You can have a list of grocery items or a list of phone numbers. What can you do to the items on a list?
You might count the items to determine the length of the list, add an item to the list, remove an item from the list, or look at (retrieve) an item. The items on a list, together with operations that you can perform on the items, form an abstract data type. You must specify the behavior of the ADT’s operations on its data, that is, the list items. It is important that you focus only on specifying the operations and not on how you will implement them. That is, do not bring to this discussion any preconceived notion of a data structure that the term “list” might suggest.
Where do you add a new item and which item do you want to look at? The various answers to these questions lead to several kinds of lists.
You might decide to add, delete, and retrieve items only at the end of the list or only at the front of the list or at both the front and end of the list.
The specifications of these lists are left as an exercise; next we will discuss a more general list.

The ADT List
Once again, consider the grocery list pictured in Figure 3-5. The previously described lists, which manipulate items at one or both ends of the list, are not really adequate for an actual grocery list. You would probably want to access items anywhere on the list. That is, you might look at the item at position i, delete the item at position i, or insert an item at position i on the list. Such operations are part of the ADT list.


ADT List Operations

Create an empty list.


Destroy a list.


Determine whether a list is empty.


Determine the number of items on a list.


Insert an item at a given position in the list.


Delete the item at a given position in the list.


Look at (retrieve) the item at a given position in the list.

Note that it is customary to include an initialization operation that creates an empty list and an operation that destroys a list. Other operations that determine whether the list is empty or the length of the list are also useful.
Although the six items on the list in Figure 3-5 have a sequential order, they are not necessarily sorted by name. Perhaps the items appear

CH03.FM Page 119 Monday, July 16, 2001 1:34 PM



in the order in which they occur on the grocer’s shelves, but more likely they appear in the order in which they occurred to you as you wrote the list. The ADT list is simply an ordered collection of items that you reference by position number.
The following pseudocode specifies the operations for the ADT list in more detail. Figure 3-6 shows the UML diagram for this ADT.

You reference list items by their position within the list

Pseudocode for the ADT List Operations


// ListItemType is the type of the items stored in the list.
// Creates an empty list.
// Destroys a list.
+isEmpty():boolean {query}
// Determines whether a list is empty.
+getLength():integer {query}
// Returns the number of items that are in a list.
+insert(in index:integer, in newItem:ListItemType, out success:boolean)
// Inserts newItem at position index of a list, if
// 1

Similar Documents

Premium Essay


...North Korea: A Stand Down or a Stand Off? Christopher Caver Strayer University North Korea ENG 215 Research & Writing Professor J. Welch June 9, 2013 With North Korea´s recent threats on several occasions to launch a nuclear weapon at various countries to include South Korea, Guam, Japan, and even the United States, the United Nations and the United States cannot standby any longer. Additionally does North Korea’s recent withdraw from verbal threats to the United States and its allies indicate a stand down? Although nuclear talks and heated talks between the U.S. and North Korea are nothing new, it has become progressively more frequent and North Korea has been determined to be seen as a nuclear capable country. Although for now, North Korea’s leader, Kim Jong Un has receded from his talks of going to war with South Korea and other United States´ allies, can the U.S. trust the North Koreans knowing how they continually say one thing while secretly doing the opposite. Additionally can the U.S. and the U.N. continue to allow North Korea to possess nuclear capabilities while continuing to ignore other major issues within the country? [pic] As you can see in the photograph above, North Korea has gone as far as to strategically place several missles which could be possibly armed with nuclear warheads in various positions in the launch position for the world to see.......

Words: 2675 - Pages: 11

Premium Essay


...BUCA, Inc. and Subsidiaries Consolidated Balance Sheets (in thousands, except share data) 30-Dec 2001 ASSETS CURRENT ASSETS: Cash and cash equivalents Accounts receivable Inventories Prepaid expenses and other Total current assets PROPERTY AND EQUIPMENT, net OTHER ASSETS GOODWILL Total assets CURRENT LIABILITIES: Accounts payable Accrued expenses, deferred taxes and other Line of credit borrowings Current maturities of long-term debt and capitalized leases Total current liabilities LONG-TERM DEBT AND CAPITALIZED LEASES, less current maturities OTHER LIABILITIES Total liabilities SHAREHOLDERS’ EQUITY: Common stock, $.01 par value per share, 30,000,000 authorized; 16,615,919 and 16,804,921 shares issuedand outstanding, respectively Additional paid-in capital Retained earnings (accumulated deficit) Total shareholders’ equity Notes receivable from employee shareholders Total shareholders’ equity Total liabilities and shareholders' equity 29-Dec 2002 $ changes % changes 12,444 2,026 4,784 2,834 22,088 140,755 5,239 168,082 3,408 2,673 6,218 3,078 15,377 181,587 8,707 11,759 217,430 (9,036) 647 1,434 244 (6,711) 40,832 3,468 11,759 49,348 -73% 32% 30% 9% -30% 29% 66% 9,928 11,481 16 21,425 452 613 22,490 13,457 13,702 4,000 5,082 36,241 20,808 3,618 60,667 3,529 2,221 4,000 5,066 14,816 20,356 3,005 38,177 36% 19% 31663% 69% 4504% 490% 170% 163 146,674 (311) 146...

Words: 285 - Pages: 2

Premium Essay


...[pic] 本科生毕业论文文献综述 (2012届) |论文题目 |A Study on Racial Discrimination in Crash | | | | | | |学生姓名 |谢薇 |学 号 |0808031004 | |专 业 |英语 |班 级 |085 | |指导教师 |颜钟祜 |职 称 |教授 | 杭州师范大学外国语学院 文献综述基本要求 |一、文献综述 | |含本选题国内外研究现状、研究主要成果、发展趋势、存在问题等内容,字数不少于3000字,力求内容切题,具综合归纳性。 | |综述正文须用本专业语种撰写。 | |二、查阅中外文献资料目录 | |所查阅的中外文献资料不得少于15篇(其中外文资料至少8篇),含作者、书名或论文题目、出版社或刊名、出版年月或期号及页码等,未经本人查阅的文献 | |资料目录不得列上。 | | ...

Words: 3088 - Pages: 13

Free Essay


...Bullying has been a widespread headache in our school. Most of the riots and gang war started from bullying. Most of the schools bullying were just ignored, they even don’t take actions of the damages cause by bullying. I remembered from a parent in the school of my son where she shared what happened to her son inside the school. Her son was bullied from the school paper. Imagine his own pictures were the source of laugh in the whole campus and he is in high school level. Just imagine how embarrassing it is for him. For a month or two her son suffered from trauma and he stop for a while but came back to school after a long and several talk. Aside from that I also heard lots of news about bullying inside the school. Just the same the school did not do anything about it. I am really surprised that the school head and administration did not do anything about it. Anyway maybe because the school administration where not capable enough to handle such things and maybe they don’t have enough knowledge about it. Now that the law about Anti – bullying where passed, I guess school administration and heads can now be guided on what to do if such things occurs inside the school campuses. They just can’t ignore such things especially if it is the main reason why the students were having problem. I am glad that this law has been passed on; I hope and prayed that it will be used according to its purpose. Then served rightfully to those who deserved to be punished according to the law.......

Words: 410 - Pages: 2

Free Essay


...Todd Terje-Inspector Norse (Dope as Fuck) Twin sister – lady day dream (coo) Twin sister – I want a house (coo) Mr twin sister – Blush (Dope AF) Mr twin sister – Sensitive (nice AF) Clark – winter linn (coo) Mr twin sister – Rude boy (Dope) Jodeci Acapella on soultrain(the intro) Boyz 2 Men – Don’t go/can you stand the rain (live) Jodice – What about us (This is a hit!!!) Jodice – Alone (dope) Isaac Hayes – Ik’s Mood (dope) Mark Asari –Revive (dope AF) Michael Jackson – The Lady in my life (Dope) Ericka Baduh – didn’t u know (ill) Switch- I call your name(coo) Erick Sermon – Fat gold chain (Dope AF) Silver Convention – Fly robin, fly (Checkit) SWV – Weak Mikey Dread – Roots and Culture (nice) Charles Earland – Happy ‘cause I’m goin’ home (Dope) Cortex – Juit Octobre 1971 (dope AF) Cortex – Triypeau bleu (coo) Cortex – Chanson D’un jour D'hiver (This shit is crazy!!!) Carole King – It’s to late (nice) The Shirelles – Baby it’s you (???) Tony! Toni! Tone! – Pillow (???) Luther Vandross – So Amazing (The Montserrat session) (nice) Melvin Sparks – Cranberry Sunshine Kaskade-Fire and Ice (kaskade mix) (Coo) Blank & Jones – Face La Mer (this shit is ill) Zeb – The Circle (This is it!!!) Smadj – Sel (Dope AF) Ella Fitzgerald & Louis Armstrong – Summertime (the end is trill) Joe – All the things (the break down in the middle is ill) Earl Klugh –A Certain Smile (intro) Earl Klugh – Another Time, Another Place Earl Klugh – Could it be I’m......

Words: 14135 - Pages: 57

Premium Essay


...TOPIC 7: Power and Conflict i. Which power bases lie with the individual? Which are derived from the organisation? Expert and Referent power base lie with the individual. Expert power influence based on special skills or knowledge. Because the specialisation of jobs becomes more and more popular, we become increasingly dependent on experts to achieve goals. Referent power influence based on possession by an individual of desirable resources or personal traits. Referent power develops out of admiration of another and a desire to be like that person. For example, If I like, respect and admire you, you can exercise power over me because I want to please you. Coercive and Reward and Legitimate power are the power derived from the organisation. Coercive power is the power base that is dependent on fear. In other words, The coercive power base depends on fear of the negative results from failing to comply. Coercive power can also come from withholding key information. Reward power is the opposite power of coercive power. Reward power is the compliance achieved based on the ability to distribute rewards that others view as valuable. Legitimate power is the power a person receives as a result of his or her position in the formal hierarchy of an organisation. It includes members’ acceptance of the authority of a position. ii. Write a 200 word summary of the argument in the article by Politis. This paper examines the relationship between credibility, the dimensions of......

Words: 565 - Pages: 3

Free Essay


...Cash and credit management: Otorgamiento Gestión Mantenimiento y cobro de los créditos comerciales o de interempresas Credit Management Créditos comerciales o de interempresas: Créditos que nos han otorgado nuestros proveedores son financiación a corto plazo Activo aplicaciones de los fondos lo que me viene del pasivo lo invierto en grandes masas: Fijo y circulante Credit management se encarga de la inversión que hacemos en cuentas por cobrar una inversión que puede ser el 95% de mi activo Una empresa de trabajo temporal (ttt) empleas temporal en una agencia y esta agencia envía el personal a tu empresa y lo empleas por 3 meses , esta empresa tiene cartera de empleados, el 95 % del activo se encontraría en Cuentas por cobrar En una empresa industrial seria el 35% en clientes o cuentas por cobrar Otorgamiento Los proveedores me permiten financiación algunos te piden interés de financiación no es habitual, si dejo de pagar a un proveedor este esperara a que le pague (esto en España) El que otorga el crédito es el elejecutivo que es el credit management el cual para dar crédito pide un folio investigado del cliente y las informaciones de buró de crédito que según el riesgo (cuanto le vamos a prestar) se gasta mas en el informe, analizamos quien es el cliente: en su aspecto jurídico, nos encontramos a empresarios que responde con todo lo que va a tener, su responsabilidad ante acreedores limitada e ilimitada( esta me interesa mas ya que significa que responde con todo...

Words: 304 - Pages: 2

Free Essay


...Journal of Addictive Diseases, 30:110–115, 2011 Copyright c Taylor & Francis Group, LLC ISSN: 1055-0887 print / 1545-0848 online DOI: 10.1080/10550887.2011.554778 Ingestions of Hydrocodone, Carisoprodol, and Alprazolam in Combination Reported to Texas Poison Centers Mathias B. Forrester, BS ABSTRACT. The combination of hydrocodone, carisoprodol, and alprazolam is subject to abuse. Ingestions of this drug combination reported to Texas poison centers during 1998–2009 were identified (totaling 1,295 cases) and the distribution of ingestions by selected factors was determined. The number of cases increased from 0 in 1998 to 200 in 2007, and then decreased to 132 in 2009. The counties in eastern and southeastern Texas accounted for 80.9% of the cases. Of the patients, 57.3% were women and 94.6% were age 20 or older. Suspected attempted suicide accounted for 59.3% of the cases and intentional misuse or abuse for 27.3%. KEYWORDS. Alprazolam, carisoprodol, hydrocodone, poison center INTRODUCTION Abuse of prescription drugs is increasing in the United States. Rates of overdose deaths involving prescription drugs increased during 1999–2006.1 Emergency department visits involving the nonmedical use of opioid analgesics increased during 2004–2008.2 There has also been an increase in prescription drug abuse among adolescents.3,4 Hydrocodone is a prescription narcotic pain reliever sold alone or in combination with other medications known by the brand names Vicodin (Abbot......

Words: 2676 - Pages: 11

Free Essay


...Sjdha sdsjh shdjshd dhs dh shdh shdshd hsd sd shd sd shdshdhs dhs dhshdhsh d s ds Sjdha sdsjh shdjshd dhs dh shdh shdshd hsd sd shd sd shdshdhs dhs dhshdhsh d s ds Sjdha sdsjh shdjshd dhs dh shdh shdshd hsd sd shd sd shdshdhs dhs dhshdhsh d s ds Sjdha sdsjh shdjshd dhs dh shdh shdshd hsd sd shd sd shdshdhs dhs dhshdhsh d s ds Sjdha sdsjh shdjshd dhs dh shdh shdshd hsd sd shd sd shdshdhs dhs dhshdhsh d s ds Sjdha sdsjh shdjshd dhs dh shdh shdshd hsd sd shd sd shdshdhs dhs dhshdhsh d s ds Sjdha sdsjh shdjshd dhs dh shdh shdshd hsd sd shd sd shdshdhs dhs dhshdhsh d s ds Sjdha sdsjh shdjshd dhs dh shdh shdshd hsd sd shd sd shdshdhs dhs dhshdhsh d s ds Sjdha sdsjh shdjshd dhs dh shdh shdshd hsd sd shd sd shdshdhs dhs dhshdhsh d s ds Sjdha sdsjh shdjshd dhs dh shdh shdshd hsd sd shd sd shdshdhs dhs dhshdhsh d s ds Sjdha sdsjh shdjshd dhs dh shdh shdshd hsd sd shd sd shdshdhs dhs dhshdhsh d s ds sdsjh shdjshd dhs dh shdh shdshd hsd sd shd sd shdshdhs dhs dhshdhsh d s ds Sjdha sdsjh shdjshd dhs dh shdh shdshd hsd sd shd sd shdshdhs dhs dhshdhsh d s ds Sjdha sdsjh shdjshd dhs dh shdh shdshd hsd sd shd sd shdshdhs dhs dhshdhsh d s ds Sjdha sdsjh shdjshd dhs dh shdh shdshd hsd sd shd sd shdshdhs dhs dhshdhsh d s ds Sjdha sdsjh shdjshd dhs dh shdh shdshd hsd sd shd sd shdshdhs dhs dhshdhsh d s ds Sjdha sdsjh shdjshd dhs dh shdh shdshd hsd sd shd sd shdshdhs dhs dhshdhsh d s ds Sjdha sdsjh shdjshd dhs dh shdh shdshd hsd sd shd sd shdshdhs dhs dhshdhsh d s......

Words: 931 - Pages: 4

Premium Essay


...Asian Journal of Counselling Vol. 11 No . 2 pp. 55-59. © Copyright 1993 by The Hong Kong Association of Psychological and Educational Counsellors e Education of International Counseling Psychology Students in the United States Y. Barry Chung University of Illinois at Urbana-Charnpaign The special needs and concerns of international counseling psychology students in the United States have been largely ignored. The purpose of this paper is to discuss education issues regarding this student population . Topics covered include: admission, language and cultural adjustment, learning experience, practicum and internship, thesis and dissertation, reentry, and recommendations for future research . Many counseling psychology education programs in the United States are committed to increasing diversity in their student body by recruiting students from different demographic backgrounds (e .g ., sex, age, geographic location, race/ethnicity, sexual orientation, physical disability, etc .) . Some programs are more successful than others in this effort . However, a diverse student body also demands special attention in education programs . It is obvious that students from different backgrounds may have different needs and concerns . Unfortunately, some programs tend to treat everybody the same way with limited assistance for the professional growth of students from diverse backgrounds . International counseling psychology students in the U.S . are among those whose needs and...

Words: 2545 - Pages: 11

Premium Essay


...TG3001 INDUSTRIAL PRACTICE Report 3 The Department SEMESTER II 2013/2014 Name Matrix No. : Chi Chang Kai : A0103804 Refinery Operations Refining is a complex operation that depends upon the skills of operators, engineers and planners in combination of cutting edge technology to produce products that meet the demands of competitive market. Some of the greatest challenges for the refinery in recent years have been changes to the specification of transportation fuels. The switch between leaded to unleaded petrol, the reduction of sulfur levels in diesel and petrol have all required major investments in new units and upgrades to existing units. What do operations do? Oil refining is the separation of crude oil by distillation into different fractions. But many other complex processes are necessary to produce a full range of products, that includes propane and butane (LPG), petrol, jet fuel, diesel, marine fuels, heating oil, lubricant basestocks and fuel oil In Singapore Jurong refinery, the operations mainly consist of 3 team forces – S1, S2 and S4. All teams are operating in 24 hours continuously. S1 and S2 teams are in charge of on-site units as shown in below Figure 1-A-1 to ensure the units are performing on their specifications. S4 is taking care of off-sites, as sub-sea pipe line, transportation and tankage for products. Daily work support 1. Plant Stability Refinery units are not always running at their specifications due to unexpected......

Words: 723 - Pages: 3

Premium Essay


...JOURNAL OF WOMEN’S HEALTH Volume 14, Number 8, 2005 © Mary Ann Liebert, Inc. Changes in Health Status Experienced by Women with Gestational Diabetes and Pregnancy-Induced Hypertensive Disorders CATHERINE KIM, M.D., M.P.H..1 PHYLLIS BRAWARSKY, M.P.H.,2 REBECCA A. JACKSON, M.D.,3 ELENA FUENTES-AFFLICK, M.D., M.P.H.,4 and JENNIFER S. HAAS, M.D., M.S.P.H.2 ABSTRACT Objective: To examine changes in health status among women with gestational diabetes mellitus (GDM) and pregnancy-induced hypertension (PIH). Methods: We examined perceived health status changes from the prepregnancy, as recalled at 12–20 weeks gestation, to the postpartum period in women with GDM (n 64) vs. unaffected gravidas (n 1233) and women diagnosed with PIH (n 148) vs. unaffected gravidas. We used patient survey and medical record data from a prospective cohort study. Health status measures included the Short Form-36 scales for physical function, vitality, and self-rated health and the Center for Epidemiologic Studies-Depression Scale (CES-D). Multivariate logistic regression models controlled for age, parity, race, education, prepregnancy body mass index (BMI) and exercise levels, food insufficiency, and GDM or PIH during a prior pregnancy. Results: Women with PIH more often reported a significant decline in vitality (odds ratio [OR] 1.51, 95% confidence interval [CI] 1.02-2.23) and self-rated health (OR 2.12, 95% CI 1.193.77) and an increase in depressive symptoms from prepregnancy to postpartum......

Words: 5024 - Pages: 21

Premium Essay

Xxxx Australia’s Best Hospitality Training School - Get a Fun Job today!! Ph: 02 9211 4292 787 George St Haymarket NSW 2000 (Opposite Central Station) Fax: 02 8221 9511 Email: Book Online & SAVE 30% Package Discount! RSA & RCG $189 RSA - Responsible Service of Alcohol - SITHFAB201 $110 One Day Course - Duration 6.5 hrs Morning Classes Held every Mon, Tues, Wed, Thurs, Fri, Sat 9:30am - 4pm Evening Classses Held every Tues & Thurs 4pm - 10:30pm You will need your RSA to get a job at any licensed venue where alcohol is served Complete your RSA Course and be ready to start working right away in restaurants, bars, clubs and cafes What you will get • RSA Interim Certificate OLGR NSW allowing you to begin working immediately after course completion • RSA OLGR NSW Competency Card • Nationally Recognised Statement of Attainment - SITHFAB201 Provide Responsible Service of Alcohol RCG - Responsible Conduct of Gambling - SITHGAM201 $85 One Day Course - Duration 6.5 hrs Classes Held every Thursday and Sunday 9:30am - 4pm You will need your RCG to get a job at any venue where gambling takes place such as pubs, clubs and casinos Complete your RCG Course and be ready to start working right away What you will get • RCG Interim Certificate OLGR NSW allowing you to begin working immediately after course completion • RCG OLGR NSW Competency Card • SITHFAB201 Provide Responsible Service......

Words: 911 - Pages: 4

Free Essay


...Município de Alfândega da Fé — Câmara Municipal DIVISÃO DE DESENVOLVIMENTO SOCIAL ( DDS ) CARTA EDUCATIVA MUNICIPIO ALFÂNDEGA DA FÉ PG.01_PROC.07_IMP.00 DDS │ Serviço de Acção Social e Educação 1 de 53 Município de Alfândega da Fé — Câmara Municipal DIVISÃO DE DESENVOLVIMENTO SOCIAL ( DDS ) Índice Índice de Ilustrações .....................................................................................................................................3 Mapas ......................................................................................................................................................3 Quadros ...................................................................................................................................................3 Gráficos ....................................................................................................................................................3 Apresentação da Carta Educativa.................................................................................................................4 1. ENQUADRAMENTO TERRITORIAL E CARACTERISTICAS FISICAS DO CONCELHO ........................5 1.1 CARACTERIZAÇÃO SÓCIO ECONÓMICA............................................................................................6 1.1.1 Actividades Económicas do Concelho.............................................................................................6 1.1.2 Análise Demográfica ...............

Words: 12687 - Pages: 51

Premium Essay

Managerial Accounting

...Chapter #7: Cost-Volume-Profit Relationship Cost-volume-profit analysis – mangers use to help them understand the interrelationship among cost, volume, and profit in an organization by focusing on interactions among the following 5 elements * Prices of products * Volume or level of activity * Per unit variable costs * Total fixed costs * Mixed of products sold The contribution format * Total unit CM Ratio * Sales (400 speakers) $100,000 $50 100% * Less: variable costs 60,000 30 60% * Contribution margin 40,000 20 40% * Less: fixed Costs 30,000 * Net operating income 10,000 * Contribution margin – amount remaining from sales after variable expenses been deducted * CM Ratio – divide total CM by total sales (40,000/100,000) * CM Ratio in terms of units – Unit CM divided by Unit selling price (20/50) Traditional approach * Revenue Revenue Sales – cost of goods sold = gross margin – operating expense = net operating income Expense Expense Break-even point – level of sales to which profit is zero CVP Graph 1. Fixed cost Fixed cost Draw horizontal line on graph for fixed cost 2. Draw the expense line (keep in mind to add fixed cost) 3. Draw the revenue line (starts form 0 unlike the expense line) Profit Graph (simpler form) * Profit = Unit CM x Q – Fixed expenses * Unit CM x Q = Fixed expenses (the break-even point) Break-even Analysis * Equation method......

Words: 1140 - Pages: 5