Lab 13
Lab assignment: Linked Lists via Tic Tac Toe
We've given you some code with the game of tic tac toe implemented in C++. Play it yourself a couple of times to verify it works, and give it a quick scan to get an idea of how the "state" of the board is being stored. You will need to add a linked list to the code to store the state of the game, adding each new state to the head of the list. Then, you should provide functionality for undoing, by removing the head of the list. Then, if you can figure it out, implement a redo, where you can get back to the part of the list you just left, even though there's no link pointing in that direction.
For this program, don't worry about deallocating memory with delete, though you will be dynamically allocating memory. The program is small enough that you won't run out of memory before the program terminates.
Stage 1 (1 point):
Create a linked list storing the relevant variables for the state. At the least, this should be both the move number and the pieces currently on the board.
Stage 2 (1 point):
Add the ability to undo in the commented section in main where I say DO YOUR UNDO CODE HERE. It's got lots of stars around it, so it should be fairly easy to find. Here you should take the state stored in the node after the head of the list, and copy its values into the variables used to store the current state that all the game logic works off of.
Stage 3 (Extra Credit) (1 point):
Add the ability to redo in the commented section in main where I say DO YOUR REDO CODE HERE. It's got lots of stars around it, so it should be fairly easy to find. Here you should take the state stored in the node before the new head of the list, and copy its values into the variables used to store the current state that all the game logic works off of. When you perform an undo, you can store the old head of the list in another variable. Note that they may have performed multiple undos in a row, but you should be able to redo past all of them, one at a time.
Though not extra credit, consider how you would remove the global variables, and work out the code using just your linked list, and the node representing the current head and state.
Notes:
Keep in mind that this is a team effort so you should agree with your partner on what you are going to do before you start typing. The partner who is typing is the "driver" and the partner watching is the "navigator." Be sure to switch roles every 10 to 15 minutes, to foster a deep understanding of the code for both partners. The navigator should be watching for syntax errors and verifying the correctness of the code you're writing.
It will speed things up for you if you keep a window open for editing and have a separate window open for compiling and running your program. Remember that windows are resizeable!
Submission:
1. You should work with a partner for this (and all the remaining) lab(s). Only one of you need to submit the program to Blackboard, though you should be certain that both of your names be present in a comment at the top of the .c or .cpp source file.
1.5 If you work alone, include just your name in a comment at the top so that I know you worked alone, and not have to guess.
2. You should turn in to Blackboard by the END OF THE LAB (8:50 for the 8-9 lab session, 9:50 for the 9-10 lab session). I know it's tempting to keep working on it, but other classes come in, and it's not fair to the students who are limited to that particular time span if you go over. Which isn't to say that you can't work on it later, to check your solution against the one I post for your own understanding. But what you submit for a grade should be before the next hour begins.
3. If you wish, you may submit your lab by 11 am on Thursday for a 1 point penalty. If you can't finish up the second point by the end of lab, you can still earn the score by completing all three steps and submitting your code by the day after.