发表于   |   分类于

Requirement

Implement a templated Stack class. It must implement the following interface (abstract class), which you should inherit from. In other words, create a file IStack.h which contains this definition, and then your own class (which may be called something like ListStack or ArrayStack or other, depending on how you impement it) should inherit publicly from IStack.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
template <class T>
class IStack
{
public:
  /* returns whether the stack contains any elements */
  virtual bool isEmpty() const = 0;
  
  /* adds a value to the top of the stack */
  virtual void push(const T& val) = 0;
  
  /* deletes the top value from the stack.
     Throws EmptyStackException if stack was empty.
     However, you should avoid having this exception thrown,
     by checking whether the stack is empty before calling it. */
  virtual void pop() = 0;
  
  /* returns the top value on the stack.
     Throws EmptyStackException if stack was empty.
     However, you should avoid having this exception thrown,
     by checking whether the stack is empty before calling it. */
  virtual const T& top() const = 0;
};

Your implementation can reuse some of your earlier linked list code, or you can build it on top of an array (which you dynamically allocate) - your choice. You must ensure that all functions run in time O(1) (amortized time O(1) if you use an array implementation), and should give an explanation with your code for why your code runs in O(1) time.
Your solution to this problem absolutely cannot use STL container classes (so no stack or vector or deque or list or such provided by STL).

阅读全文 »

发表于   |   分类于

Requirement

In this lab, each student is to write a program that allows the user to manipulate the entries in vector, or in a matrix. The program should keep track of one vector of variable length, and one matrix of exactly 4x4 size. The program should enter a loop, displaying a set of options (given below). Once the user selects an option, the program should display the vector (or matrix, as appropriate) before and after the operation chosen by the user. For example, if the user selects “reverse vector” and the current vector is [-3 0 2 5] then the program should display:

1
2
3
4
input
-3 0 2 5
reversed
5 2 0 -1

The program should run until the user selects an option to quit.
The program must use the following structure definitions.

1
2
3
4
5
6
7
8
struct vector {
  float *data;
  int    size;
};

struct matrix {
  struct vector rows[4];
};

阅读全文 »

发表于   |   分类于

Requirement

In this assignment you will write a graphics-based program to do a random walk, sometimes also known as a drunkard’s walk. This random walk simulates the wandering of an intoxicated person on a square street grid. The drunkard will start out in the middle of the grid and will randomly pick one of the four compass directions, and take a step in that direction, then another step from that new location in a random direction, etc.

This assignment will give you practice with creating classes, using loops, using the java library for random number generation, doing console-based IO, and drawing to a graphics window. Also you’ll get practice in general program development.

阅读全文 »

发表于   |   分类于

Requirement

Tic-tac-toe is a two-player game that children often play to pass the time. The game is usually played using a 3-by-3 game board. Each player chooses a symbol to play with (usually an X or an O) and the goal is to be the first player to place 3 of their symbols in a straight line on the game board (either across a row on the board, down a column or along one of the two main diagonals).

In this Assignment, you are to complete some functions that make up part of a larger program for playing tic-tac-toe. In the program, game boards are not restricted to being 3-by-3, but are instead N-by-N, where N is one of the integers from 1 through 9, inclusive. Our game boards will always be square. When you have completed your functions for this Assignment, you will be able to play games of tic-tac-toe on your computer!

阅读全文 »