ASSIGNMENT SIX consists of two unrelated parts. One deals with linked lists and one with recursion. This is a relatively short assignment. It is due next Monday, March 25.
Part one of the assignment is to write two list-handling functions and some code to test them. You can add the functions to the sample program ListSort.cc, which was handed out in class. You can add the testing code to the main() routine of the program. The two functions that you should write are:
A compiled solution to this assignment can be found in the program listsort_complete in the directory /home/cs225/assg6. You can write your program to work like this one if you want. Your program doesn't have to work in exactly the same way, but whatever it does, it should test the two functions that you write.
(Note: Neither of the functions needs to be recursive. It would be possible to write the remove function recursively, and it might even be easier than the non-recursive version. However, the reverse function is easier to write non-recursively. Hint: Just read the original list from front-to-back while building the reverse list from back-to-front.)
I will discuss maze solving in class as an example of a recursive algorithm. The second part of this assignment is to write a program that implements this algorithm. A maze for this program is represented by a 39-by-39 two-dimensional array. Each position in the array is either part of a "wall" or part of a "corridor". All positions along the edges are walls. The corridors form a maze. Your program will search for a path through the maze between the upper left corner -- the (1,1) position -- and the lower right corner -- the (37,37) position. It will use the recursive algorithm that we discuss in class to do so.
Here is a picture of the type of maze you will work with. In this picture, I've used two characters for each position. This makes the structure easier to see:
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %% %% %% %% %% %% %% %% %%%%%%%%%% %% %%%%%% %%%%%% %% %%%%%%%%%%%%%% %%%%%%%%%% %% %%%%%% %% %% %% %% %% %% %% %% %% %% %% %% %% %% %% %%%%%%%%%%%%%% %%%%%%%%%%%%%% %% %% %% %%%%%% %% %%%%%% %% %% %% %% %% %% %% %% %% %% %% %% %% %% %% %%%%%%%%%%%%%% %% %% %%%%%% %%%%%% %%%%%% %% %% %%%%%%%%%% %% %% %% %% %% %% %% %% %% %% %% %%%%%% %%%%%% %%%%%%%%%% %%%%%% %%%%%%%%%%%%%% %% %%%%%%%%%% %% %%%%%% %% %% %% %% %% %% %% %% %% %% %% %%%%%%%%%% %%%%%%%%%% %%%%%% %% %%%%%% %%%%%% %%%%%% %% %%%%%% %% %% %% %% %% %% %% %% %% %% %% %% %% %% %% %%%%%% %% %%%%%% %% %% %%%%%%%%%%%%%%%%%%%%%% %% %%%%%%%%%% %% %% %% %% %% %% %% %% %% %% %% %%%%%% %%%%%%%%%%%%%% %%%%%%%%%% %% %% %%%%%%%%%% %% %%%%%% %%%%%% %% %% %% %% %% %% %% %% %% %% %%%%%%%%%% %% %% %%%%%% %%%%%%%%%%%%%%%%%% %% %%%%%% %% %%%%%% %% %% %% %% %% %% %% %% %% %% %% %% %% %% %% %% %%%%%%%%%%%%%% %% %%%%%% %% %%%%%%%%%%%%%% %%%%%% %% %% %% %% %% %% %% %% %% %% %% %% %% %% %% %% %% %%%%%%%%%% %% %% %%%%%%%%%% %%%%%% %%%%%% %% %% %%%%%% %% %% %%%%%% %% %% %% %% %% %% %% %% %% %% %% %% %% %% %%%%%% %%%%%%%%%% %% %% %%%%%% %% %%%%%%%%%% %%%%%%%%%% %% %% %% %% %% %% %% %% %% %%%%%% %%%%%%%%%%%%%%%%%%%%%% %% %%%%%%%%%% %%%%%% %%%%%% %%%%%% %%%%%% %% %% %% %% %% %% %% %% %% %% %% %% %%%%%% %%%%%% %%%%%%%%%% %%%%%% %% %%%%%% %%%%%% %% %% %% %%%%%% %% %% %% %% %% %% %% %% %% %% %% %% %%%%%%%%%%%%%% %%%%%% %% %%%%%% %% %% %%%%%%%%%%%%%% %%%%%%%%%% %% %% %% %% %% %% %% %% %% %% %% %%%%%%%%%% %% %%%%%% %%%%%% %% %%%%%%%%%%%%%% %%%%%% %% %%%%%%%%%% %% %% %% %% %% %% %% %% %% %% %%%%%% %% %% %%%%%%%%%% %%%%%% %%%%%%%%%%%%%%%%%% %%%%%% %% %% %% %% %% %% %% %% %% %% %% %% %% %% %% %% %%%%%%%%%% %%%%%%%%%%%%%% %% %% %%%%%% %% %% %% %% %% %%%%%% %% %% %% %% %% %% %% %% %% %% %% %% %% %% %% %% %%%%%% %% %% %% %% %% %% %%%%%%%%%% %%%%%% %% %%%%%%%%%% %% %% %% %% %% %% %% %% %% %% %% %% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
The compiled program makemaze in the directory /home/cs225/assg6 creates a random maze, displays it on the screen in this form, and writes the data for the maze to the file named "maze.dat". In the file, a wall is represented by a single '%' character, and a corridor is represented by a single '.' character. (This makes it easier to read the file into a program, but makes it harder to see what the maze looks like by viewing the file.)
You should write a program that reads the description of a maze from a file, finds a path from position (1,1) to position (37,37), and then displays the solution on the screen. (A maze produced by the makemaze program will have one and only one solution; it will not contain any path that loops back on itself.)
The compiled program solvemaze in the directory /home/cs225/assg6 is a sample solution to this assignment. If you run this program with no command-line argument, it will read the data for the maze from the file "maze.dat". If you want to read the maze from a different file, give the file name as a command-line argument. For example, you can try "solvemaze maze1.dat" and "solvemaze maze2.dat". The makemaze program can be used to make additional data files for your program.