Duck Duck Goose Game

In this assignment, you are required to implement a Doubly Linked List using C++ as well as a game that uses Doubly Linked List as the data structure. To get started on the assignment, you should read the details given in this question paper. The description for what you need to do is described in the section “Problem Description”. In order to make the program implementation easier, you are suggested to write your program using Visual C++ instead of doing it directly using paper & pencil.

Objective

The objective of this assignment is to consolidate your concepts and programming skills of basic data structure, specifically, Doubly Linked List. Upon completion of this assignment, you should be able to:

• Demonstrate your understanding on how a Doubly Linked List works
• Implement a fundamental data structure with the use of C++ and its constructs, e.g. classes, objects, pointers as well as all the other features that you should have learned in the last programming course.
• Construct a C++ test program to test your implemented class.
• Understand how to use appropriate data structure(s) for application development.

Problem Description

In this assignment, you are required to work in a GROUP OF TWO to produce a simple program using Visual C++. Specifically, you are required to create classes to implement a Doubly Linked List.

The following gives further details of the problem.

• Create a New Project and give your project the name ProgAssignment.
• Add a header file to your project, called DataNode.h for a class template DataNode according to the UML class diagram below. See image.
• In the constructor DataNode(val: T, p: DataNode T*, n: DataNode T*), you are required to initialize all the data members of the class. In addition, NULL should be assigned to p and n as default values. Note that you are required to make another class DoublyLinkedList as a friend of DataNode to facilitate efficient access of data members.
• Add another header file to your project, called DoublyLinkedList.h that corresponds to the class template DoublyLinkedList. Once again, your implementation should be in according to the given UML class diagram as shown below: See image.
• Implement all the member functions in DoublyLinkedList.h according to the following function description:
  • head is a data member of class template DoublyLinkedList to store the address of the first DataNode in the list.
  • tail is a data member of class template DoublyLinkedList to store the address of the last DataNode in the list.
  • DoublyLinkedList() is a constructor that initializes the data members by assigning NULL to head and tail.
  • ~DoublyLinkedList() is a destructor that used to destroy all the DataNode in the Doubly Listed List so as to avoid memory leakage.
  • isEmpty() is a function that checks whether the list is empty. If it is empty, return true, otherwise, return false.
  • insertFront() is a function to insert data at the front of the list.
  • insertBack() is a function to insert data at the back of the list.
  • removeFront() is a function to remove data at the front of the list. You are required to return the removed data to the function caller.
  • removeBack() is a function to remove data at the back of the list. You are required to return the removed data to the function caller.
  • insertNode(el: T, index: int) is a function to insert data to the list as specified by the value in index. index = 0 means inserting the data to the very beginning of the list, index = 1 means inserting the data to position after the 1st node, index = 2 means inserting the data to position after the 2nd node, etc.
  • deleteNode(index: int) is a function to remove the data node at position specified by index.
  • get(index: int) is a function to get the data at position specified by index.
  • sort(index: int) is a function to sort the data in the list. The value in index specifies the range of data to be sorted. For instance, index = 5 means sort all the data between the 5th data node to the end in non-decreasing order.
  • printList() is a function to display all the data in the list on screen.
• Add a source file main.cpp to your project and implement a main function by incorporating the following to test your implemented classes.
  • Ask the user to input the total number of data to be inserted.
  • Ask the user to input all the data to the linked list.
  • Print all the data on screen.
  • Perform sorting and then print all the data on screen.
  • Finally, allow the user to perform insertion, deletion, data retrieval, sorting and printing of data. In addition, you should allow user to input 'q' to quit the program.

The following gives the sample program sessions of the test.

Number of input data: 5
Enter all your data: 8 3 5 13 1
Data in the doubly linked list: 8 3 5 13 1
After sorting of the whole list: 1 3 5 8 13
i = insert; d = delete; g = get data; s = sorting; p = printing; q = quit: i
Data to insert: 30
Where to insert: 2
i = insert; d = delete; g = get data; s = sorting; p = printing; q = quit: p
Data in the doubly linked list: 1 3 30 5 8 13
i = insert; d = delete; g = get data; s = sorting; p = printing; q = quit: g
Index to get: 5
The data at 5 is 13
i = insert; d = delete; g = get data; s = sorting; p = printing; q = quit: d
Index to delete: 3
i = insert; d = delete; g = get data; s = sorting; p = printing; q = quit: p
Data in the doubly linked list: 1 3 30 8 13
i = insert; d = delete; g = get data; s = sorting; p = printing; q = quit: i
Data to insert: 7
Where to insert: 4
i = insert; d = delete; g = get data; s = sorting; p = printing; q = quit: p
Data in the doubly linked list: 1 3 30 8 7 13
i = insert; d = delete; g = get data; s = sorting; p = printing; q = quit: s
After sorting: 1 3 7 8 13 30
i = insert; d = delete; g = get data; s = sorting; p = printing; q = quit: q
End of program.

• Remove (not delete) the source file main.cpp from your project and add a new source file DuckDuckGoose.cpp. Use your implemented data structure Doubly Linked List to simulate a "Duck, Duck, Goose" game. The rules of "Duck, Duck, Goose" game is described as follows.
  • A group of players sit in a circle and face inward.
  • One of the players is selected as the "picker", who will walk around and tap each player in turn and say "duck" until one of them is to be picked as a "goose".
  • The picked "goose" will stand up and chase the "picker". The "picker" will try to return to the goose's position.
  • If the picker success, the "goose" is now the picker of the game and the process starts again.

Algorithm:

• Obtain the number of players of the game and their names and insert all of them to the circle simulated using Doubly Linked List.
• Ask the user the total number of rounds of the simulation.
• Output the initial circle.
• The simulation is then executed as follows:
  • Initially, the first node is chosen as the "picker".
  • Randomly generate an integer value n to represent how many players would be called "Duck" until a "Goose" is called.
  • Randomly decide whether the walking path should be in clockwise or anti-clockwise direction.
  • Advances the pointer to the next node n times in the decided direction and call "Goose".
  • The node being called "Goose" will be removed from the list.
  • Generate another number to decide whether the "Goose" or the "picker" wins the race.
  • Insert the winner back into the circle at the Goose's position.
  • Output the circle.
  • Repeated steps (b) to (h) until the total number of rounds is done.

Hints:

• In DataNode.h, you need to add the following lines of code before the DataNode class to ensure the correctness of friend statement.

template [typename T] class DoublyLinkedList;

• Similarly, you need to do the same thing for DoublyLinkedList.h as follows.

template [typename T] class DataNode;