| CSCI 230 | Data Structures and Algorithms | Fall 1998 |
The objective of this lab is to familiarize you with compiling, running, and debugging programs in the Microsoft Developer Studio/Visual C++ environment. Along the way you will be exposed to the fundamentals of good design as well as some common C++ pitfalls, a theme we will continue throughout the semester.
Work your way through the following steps, in order:
Note: The Samba server can be quite slow, so it is recommended that you copy the files onto the local drive.
Work within Developer Studio is organized around projects and workspaces. Projects are collections of files used to create an executable program; a workspace is a collection of one or more projects. (You might want to browse the online help on workspaces and projects.)
Note: Learn how to save all of your work (look under the File menu). It is a good idea to save your work frequently, so that if the computer crashes you do not lose too much. (Hint: Try the Alt-F-L shortcut.)
main.cpp buffer.cpp buffer.h
Click the "+" next to your project in the workspace view,
and you should see the files listed.
Take a few moments to read through the code. The main program is very simple and exists simply to test the implementation of the "buffer" class. A couple of things that may be new to you are the include file iostream (the ".h" extension is missing on purpose) and the appearance of std:: throughout the code. These are both new aspects of the latest version of C++. Standard header files no longer use the ".h" extension; the old-style files still exist to provide backward compatibility, but you should get accustomed to doing things the new way. The std:: prefix you see is the normal C++ scoping operator, but the identifier "std" refers not to a class, as you would expect, but to something called a namespace.
A namespace is simply a collection of identifiers, or names. Namespaces allow us to use the same identifier to refer to different things within different namespaces (this is exactly analagous to the way in which different C++ functions can use the same identifier, say i, to refer to different local variables). In the new standard library, many components have names that are very likely to conflict with names you might want to use in your program; for example, there are standard functions called "swap", "sort", etc. To prevent conflicts, all the components in the standard library belong to a namespace called "std". The benefit of this is that you can use names like "swap" in your program; the downside is that you must prefix standard library components that you use with std::.
The buffer class captures the idea of a fixed size buffer that can hold data (in this case, integers). Note that, like all good class designs, the class is split into a public interface and a private implementation. The public interface provided by the class consists of functions to add and remove items from the buffer, to "peek" at the next item to be removed from the buffer without actually removing it, and to return the number of items held in the buffer. There are also the usual constructors and destructors. The buffer class provides FIFO (first in, first out) semantics; the items in the buffer are kept in the order they were added, and the next item to be removed will be the one that was first added. (This type of data structure is often called a "queue".)
The private implementation that was chosen for this project is a technique called a "circular array". The items in the buffer are kept in an array; at any one time, all the items in the buffer occupy a contiguous portion of the array, not necessarily starting at the begining. Two indexes (head and tail) keep track of the begining and end of this part of the array, respectively. As new items are added, the end of the occupied part of the array moves toward the physical end of the array, as does the begining of the occupied part when items are removed. When the occupied part reaches the physical end of the array, it simply "wraps around" to the physical begining of the array (assuming of course that there is sufficient free space and it will not overlap the begining part). It helps if you visualize bending the end of the array around in a circle and connecting it to its begining, which is where this technique gets its name. It will also probably help if you draw some diagrams of what the data structure would look like in various situations; this will be especially useful in debugging. Pay special attention to how we make the array "wrap around", so that the end appears to be connected to the beginning.
Before continuing, make sure you are reasonably comfortable with the code. Don't worry if you suspect there are bugs; there are, and we will be discovering and fixing them below. Likewise, don't worry if you don't fully understand how everything in the code works; below you will step through the program in the debugger, which will help you to see what is going on.
Note that the output from the compiler and linker is directed to the status pane along the bottom of your screen. If you get errors, pressing F4 will scroll the status pane to the error and position the cursor in the editing pane to the file and line number where the error occured. Press F4 repeatedly to loop through all the errors. Fix any compiler errors in the editing pane and rebuild the project until you are successful.
When you do this, a console window will pop up with the output from the program; press Return to make the window disappear. If you compare the output to the main program, it should be apparent that there are some bugs in the buffer class (there are no bugs in the main program). To help find the bugs, we will run the program in the debugger.
As you step through the program, notice how the "call stack" pane in the lower left quadrant is updated to show the values of the variables that are in scope. You can scan backwards through the scope stack (for example, to see local variables in the main program when you are currently in a function call) by using the pull down menu at the top of this pane. You can also make use of the watch pane in the lower right quadrant to track the value of other variables (e.g., globals) or even C++ expressions by typing the appropriate expression there.
There are a number of bugs you need to locate and fix in the buffer class; each test in the main program uncovers the effects of one or more bugs. You should attack the bugs in the order of the tests. When you think you have resolved all the bugs associated with a given test case, notify one of the lab monitors; they will verify that you have corrected the bug so that you can move on to the next test. The monitors will also ensure that you do not get stuck on a particular bug by giving you hints if you are taking too much time to fix it.
sorted_buffer.cpp sorted_buffer.h test_sorted.cpp
Modify main.cpp by adding the following two lines to the end
of the main function:
void test_sorted();
test_sorted();
This adds a new class, sorted_buffer, and some test code. A sorted_buffer works exactly like a the buffer above, except that it keeps its contents in sorted, rather than FIFO, order (so the remove member function removes the smallest item in the buffer). The implementation of this is accomplished by inheriting the functionality of the normal buffer, and then overriding the definition of the add function.
Read and make sure you understand the new code; then rebuild the project, fixing any compile-time errors as necessary. When you have successfully built the executable, use the debugger to fix any bugs in the implementation of sorted_buffer. (There are no bugs in the test_sorted function.)
At the conclusion of this lab, take a moment to review the following:
You should understand the difference between "pass-by-value" and "pass-by-reference", and the types of situations in which to use each. You should also know how to spot, using the debugger, the bug caused when an argument is passed the wrong way, and you should appreciate why it is important to pass class objects by reference, rather than by value.
You should appreciate the importance of providing a custom assignment operator to classes that you design, and what type of bugs can occur if you don't.
You should be comfortable with the Microsoft Developer Studo environment: setting up workspaces and projects, editing and building your program, and running it in the debugger.
You should be able to fix bugs by using the debugger and drawing a diagram of the data structure to figure out what is wrong.