University of Delaware



Lab 4b (Game)(100 pts total)You may work with a partner, or you may work on your own. You know the rules.This lab requires the NodeT class definitions and the BSTY class definitions from last class. You will be modifying both to create an AVL Tree. Note: the lab must compile in order to be graded. In addition, for this lab, the lab must run to the point of producing output, or it will not be graded. At this point in the semester you should be proficient enough at programming in c++ so that your code produces output at least close to the desired output for a grade.Part 1: Binary Search Tree code, (hopefully you’ve already finished this)Part 2 (65 pts): AVL Tree Modify the BSTY class so that you’ve included the following methods:NodeT * BSTY::rotateRight(NodeT *n) NodeT * BSTY::rotateLeft(NodeT *n) In addition, modify your adjustHeights method so that it checks balances and, when necessary, rotates appropriately. You may wish to write a helper method int BSTY::findBalance(NodeT *n)that finds the balance of node n, and returns that balance. Once you have this code working, download and run my updated TreePuzzle.cpp and hpp filesGame.cpp and Game.hpp filesmainYahtzee.cpp file (I thought this game was Yahtzee, but when I googled it it’s actually closer to wordhub)Run the mainYahtzee.cpp with the Game object and startGame commented out (this is how it is coming to you).(note that I included specifications of when I rotated right and left and double-rotated, for your information). For this part, you will have to make sur PART 1 and PART 2 are uncommented out in the main() function in mainYahtzee.cpp. Your output should look like the output shown below. (35 pts for correct order of letters, 25 pts for correct height at each node)Part 3 (40 pts): WordHubish GameThe game: WordHubThe idea: A player gets a set of letters of size x (you pick) and then generates as many words as possible with those letters only. The words are then checked for validity or not, and a player gets a final score that is the total number of words that used only the letters and occur in a dictionary versus the words that either use invalid letters or don’t occur in the dictionary.The crux of this: Reading in a dictionary file into a BST modified using AVL (an AVL tree). Things I didn’t worry about: caps versus small letters.Your Part:Make sure you’ve downloaded usanoswears.txt. This is the file that will be read into the AVL Tree.Modify the find method in BSTY so that it keeps track of the number of comparisons needed to find a node.Include your linked list from the last lab.The linked list portion is for the words the user types in after s/he has received his/her letters. Each word is added to the linked list. These are the words that are checked with the dictionary (which is in the form of a binary search tree) in the Game object’s methods. Your job is to write the header file and the definitions for a Linked List. Because we’re just adding words to an empty linked list, the methods required are a subset of the methods you wrote for the linked list lab. The only new field and method is the score field/ getScore method. The score is initially set to 0. The getScore method traverses the list and adds the score of each word/Node in the list, then sets the score to be that total.For the Linked List, you should have at a minimum the following fields:NodeL *first;NodeL *last;int size;int score; // This field is for the game’s score, and will be set using a getScore method, below. It should be initialized in the constructor to 0.And your methods you’ll need for this are:LL();void push(string s);void addFirst(string s);void printList();void getScore(); // This is the new method – each word already has a score. This method just traverses the linked list from the first to the last node and keeps a running total of the wscore of each node. Then the score field is set to that total.When you have this modified, go back to mainYahtzee.cpp and comment out parts 1 and 2. Uncomment out the game portion. Then run it. You should have output along the lines of the output shown at the bottom of this file. When you test this, make sure you try a word with characters not in your list. Make sure at least one word has characters but is not in the dictionary. Make sure one workd is both in the list and in the dictionary. HINTS FOR THIS LAB:Make sure you leave time for debugging this lab.Remember the parents!!!! Draw out a rotation, including all changes in height and all changes in pointers, both to children and parents. When you do a rotation, which nodes’ parents change? Make sure you include all of those changes in your code.Remember to check for NULL pointersWhen rotating, if you rotate one node down, and another node up, you must modify the height of the node that rotated to the child position before you modify the height of the new parent (the node that just rotated).Make sure you check for the condition of a node being the root of the tree (in which case it will have no parents). Extra Credit Opportunities:NOTE: to receive any extra credit, you must have the AVL tree working first!This game screams to be made more interesting. For instance, a timer could be added that limits the amount of time a player has to come up with words. A scrabble-like count could be added that makes words with infrequently-occurring letters worth more. The interface could be modified so that if a word isn’t found in the current dictionary, you could have something ask, “do you wish to add this word”, and if the user says “yes”, add the word to the tree and count the word’s score towards the total count. The game could be made so that it works with multiple players. And, of course, the interface could be seriously improved upon. These are just thoughts I’m having in my 2 minutes of sitting here typing this. So for extra credit:1)(5 pts) add a timer element that only allows users to input words for a certain amount of time. 2) (5 pts) add a letter-count that counts different letters as being worth different values. This could work for both the score that gets added to the total score for valid words, and the score that gets subtracted for invalid words3) (4 pts) allow users to enter words that should be valid but aren’t in the current tree, and then update the score accordingly4) (5 pts) make it a 2 player game5) up to 30 pts: add a cool user interface6) propose an idea to the TA and/or me for extra credit/***********************************************************************************/OUTPUT FOR PART 1 AND 2:inserting runinserting tuxedoinserting ocelotinserting vastinserting barkinserting punctiliosinserting helloinserting isbark must rotate left (-2) inserting sibylicinserting goocelot must rotate right (2) Mine 3.141592653*******************************PREORDER |run(4): |hello(3): |bark(2): |go(1): |ocelot(2): |is(1): |punctilios(1): |tuxedo(2): |sibylic(1): |vast(1): *******************************INORDER |bark(2): |go(1): |hello(3): |is(1): |ocelot(2): |punctilios(1): |run(4): |sibylic(1): |tuxedo(2): |vast(1): *******************************POSTORDER |go(1): |bark(2): |is(1): |punctilios(1): |ocelot(2): |hello(3): |sibylic(1): |vast(1): |tuxedo(2): |run(4): PART TWO 3: |ocelot(2): perforated not found 3: |sibylic(1): 4: |go(1): A LOT OF LEFT ROTATIONS inserting ainserting binserting ca must rotate left (-2) inserting dinserting ec must rotate left (-2) inserting fb must rotate left (-2) inserting ge must rotate left (-2) inserting hinserting ig must rotate left (-2) inserting jf must rotate left (-2) *******************************PREORDER |d(4): |b(2): |a(1): |c(1): |h(3): |f(2): |e(1): |g(1): |i(2): |j(1): *******************************INORDER |a(1): |b(2): |c(1): |d(4): |e(1): |f(2): |g(1): |h(3): |i(2): |j(1): *******************************POSTORDER |a(1): |c(1): |b(2): |e(1): |g(1): |f(2): |j(1): |i(2): |h(3): |d(4): A LOT OF RIGHT ROTATIONS inserting jinserting iinserting hj must rotate right (2) inserting ginserting fh must rotate right (2) inserting ei must rotate right (2) inserting df must rotate right (2) inserting cinserting bd must rotate right (2) inserting ae must rotate right (2) *******************************PREORDER |g(4): |c(3): |b(2): |a(1): |e(2): |d(1): |f(1): |i(2): |h(1): |j(1): *******************************INORDER |a(1): |b(2): |c(3): |d(1): |e(2): |f(1): |g(4): |h(1): |i(2): |j(1): *******************************POSTORDER |a(1): |b(2): |d(1): |f(1): |e(2): |c(3): |h(1): |j(1): |i(2): |g(4): A LOT OF RIGHT-LEFT ROTATIONS inserting ginserting jinserting ig must rotate left (-2) j child, rotating right inserting cinserting fg must rotate right (2) c must rotate left (child) inserting hi must rotate right (2) f must rotate left (child) inserting ef must rotate right (2) c must rotate left (child) inserting dinserting ainserting be must rotate right (2) *******************************PREORDER |g(4): |c(3): |a(2): |b(1): |e(2): |d(1): |f(1): |i(2): |h(1): |j(1): *******************************INORDER |a(2): |b(1): |c(3): |d(1): |e(2): |f(1): |g(4): |h(1): |i(2): |j(1): *******************************POSTORDER |b(1): |a(2): |d(1): |f(1): |e(2): |c(3): |h(1): |j(1): |i(2): |g(4): A LOT OF LEFT-RIGHT ROTATIONS inserting ainserting pinserting da must rotate left (-2) p child, rotating right inserting ginserting fp must rotate right (2) inserting ed must rotate left (-2) g child, rotating right inserting kg must rotate left (-2) p child, rotating right inserting jinserting vinserting b*******************************PREORDER |f(4): |d(3): |a(2): |b(1): |e(1): |k(3): |g(2): |j(1): |p(2): |v(1): *******************************INORDER |a(2): |b(1): |d(3): |e(1): |f(4): |g(2): |j(1): |k(3): |p(2): |v(1): *******************************POSTORDER |b(1): |a(2): |e(1): |d(3): |j(1): |g(2): |v(1): |p(2): |k(3): |f(4):/********************************************************************************************************************************/GAME OUTPUT:NOTE: There is a lot of printing as the dictionary is read into the AVL TREE. I’m only including the last portion of the insertion into the tree so you can double-check. The actual game part is at the very end. I’ve included 2 plays so you can see it:…inserting touchedinserting strengtheningstrengthen must rotate left (-2) strengths child, rotating right inserting colognecolor must rotate right (2) inserting gzipinserting wishinginserting rangerrank must rotate right (2) inserting smallestinserting insulationinserting newmannews must rotate right (2) inserting marshinserting rickyinserting ctrlinserting scaredscale must rotate left (-2) schedule child, rotating right inserting thetainserting infringementinserting bentbenjamin must rotate left (-2) benz child, rotating right inserting laoslanka must rotate left (-2) lap child, rotating right inserting subjectiveinserting monstersinserting asyluminserting lightboxlight must rotate left (-2) lighter child, rotating right inserting robbierom must rotate right (2) inserting stakeinserting cocktailcoat must rotate left (-2) inserting outletsinserting swazilandinserting varietiesvariety must rotate right (2) varies must rotate left (child) inserting arborarbitrary must rotate left (-2) inserting mediawikimedian must rotate left (-2) medicaid child, rotating right inserting configurationsconfirm must rotate right (2) inserting poisonpoker must rotate right (2) How many letters do you want?7oaiotzlYour letters are: o a i o t z l Start generating words: tooatitzoolotlitcatsaiotalt-1too at it zoo lot lit cats aiot alt 9: |too(6): too is okay 7: |at(9): at is okay 9: |it(7): it is okay 14: |zoo(2): zoo is okay 11: |lot(3): lot is okay 13: |lit(1): lit is okay cats is invalid aiot not found aiot is invalid 13: |alt(1): alt is okay Number of valid words: 7 Invalid words: 2Final Score is: 9/**********************************/Game played a second time:How many letters do you want?7uoerndwYour letters are: u o e r n d w Start generating words: onwonrundonewordnerddrewruderedwedwornmerpwone-1on won run done word nerd drew rude red wed worn merp wone 14: |on(3): on is okay 13: |won(2): won is okay 13: |run(3): run is okay 13: |done(1): done is okay 13: |word(3): word is okay nerd not found nerd is invalid 11: |drew(3): drew is okay rude not found rude is invalid 10: |red(6): red is okay 14: |wed(1): wed is okay 14: |worn(2): worn is okay merp is invalid wone not found wone is invalid Number of valid words: 9 Invalid words: 4Final Score is: 3 ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download