dsa-a2.txt

真的很麻烦也

                                 DSA 2004 
                               ASSIGNMENT 2

In lectures, I have mentioned several times that it is a good idea, when 
we have a specification of an abstraction, to build an understanding of 
how it works by working through a series of operations on one or more 
examples, setting out at each step the operation, any output it might 
produce, and a representation of the structure after the operation. This 
idea is illustrated in, for example, Examples 4.3, 4.4, 4.5, and 5.1 of the 
textbook.

We can extend this idea in order to validate a given implementation of an 
abstraction. We can write some code, derived from the series of operations 
mentioned above, that "exercises" the implementation by testing its 
behaviour. We will call such a piece of code a "test driver" for the 
given abstraction and associated implementation. Its purpose is to test all 
aspects: normal behaviour, empty and full structures, and exceptions.

In this assignment, we ask you to write such test drivers for:

  stack with array implementation;
  stack with list implementation;
  queue with circular array implementation.

For the first two, use the implementation code of the book.  For the third,
we will specify a variant of the implementation strategy used in the boook.

We also ask you to write some simple algorithms using these abstractions.

You will write one program, the main method of which invokes separate
methods to implement each of several parts of the exercise, as specified
below.

You will be asked to handin a file, named output.txt, containing the output
produced by your program.  This file will play a major role in the
assessemnt of your exercise.  Below you will find some guidelines as to the
output produced, but it is primarily your responsibility to design your
program such that the output produced is a clear record of (for the
drivers) the test operations used, any output produced, and a printout of
the contents of the structure after the operation.

You will of course need more than one file for your solution: you will need
to decide how many, their names, and their organization.

Assessment will be based primarily on the output file, and explanatory
comments in your program code.  We expect your main method to have at its
head: firstly, your name and other details, and secondly, a block of
comments giving an overview of your solution, and its organization.  The
methods written for each part of the exercise must also begin with a
comment block explaining what you have done for that part of the exercise.
For example, for a a stack driver (part 1 below), explain why you believe
that you have thoroughly tested the stack implementation.


The details of the assignment follow below.


From the website for Goodrich and Tamassia


   http://www.datastructures.net/


download the code fragments for

  ArrayStack (code fragments 4.4 (p142)and 4.5(p143))
  example reverse (4.6(p145))

1.  Write a driver that carries out several operations on a stack, similar
to example 4.3 on page 138).  It is up to you to choose the operations --
make sure that they thoroughly test the behaviour of the stack
implementation.  Your driver should (as indicated above) produce clear
output that identifies the operation concerned, its expected result, and
actual output, as well as the the contents of the stack after the
operation.


2.  Now set up an array of ten integer objects (you may code the values
directly into the program, rather than reading them in), print it, reverse
it (putting the result in another array), and print the result.  Use a
stack to achieve the reversal.

3,4.  Repeat the above two steps using a singly-linked list to implement
the stack abstraction.  Use a list without sentinels, as in Figure 4.8 (p151) and
Code Fragment 4.11 (p164)of the textbook.  Your code will be quite smilar to
steps 1 and 2 above.  However, there are differences in behaviour between
the two implementations, and we will expect your code and output to show
those differences.


5.  Now write code for a class ArrayQueue that implements a queue using a
circular array.  Base your code on that given in the textbook, with one
change.  The code in the book allows the usage of only N-1 elements of an
array of size N i.e. one element is always left unused.  Explain clearly
why this happens, then devise, explain and implement an alternative
strategy whereby all N elements can be used.  Then write a driver (as
above) that carries out several operations on a queue, like example 4.4 on
page 150.  Make sure that your driver illustrates all aspects of the
behaviour of the implementation.  (Hint: see Tutorial 2, problem 5.)

6.  Take the original (un-reversed) array of ten integers, as used above,
and put all its elements into a queue (first element first).  Write a
method to reverse the order of the elements in the queue, as in problem 3
of Tutorial 2.  You may use a stack as an auxiliary data structure, but
only one queue.


As an example of what should appear in the file output.txt, the driver for 
part 1 above might include the lines (for example only):

  Operation pop()
  Output: 2
  Stack (array) contents: TOP [1]

In devising a way of printing the contents of a structure, recall that the 
class Object in Java defines a method toString.

There are different ways to construct the file output.txt. One is to code 
your program to write to standard output, and use Unix redirection to send 
the output to a file. Another is to use Java FileWriter classes. Explain 
and justify the choice that you make.


Keep all files for this assignment in one directory. I will advise later 
how to hand it in.


The due date is Tuesday 20th April, and the assignment counts 4% towards
your final mark.  It is compulsory, and satisfactory results must be
achieved to be eligible to pass the subject.



Andrew L Wendelborn, Francis Vaughan, Charles Lakos
2004-03-26