Directions: The problems in this assignment are full programming problems. For each program, submit your source code and project files. When adding files to your zip file use folders to keep projects separate. Remember to keep a copy of your work.

1. Write recursive functions that perform insertion and retrieval operations on a pointer-based sorted linked list of integers. The insertion function should be void, taking a head pointer and the item to be inserted as parameters. The retrieval function should take a head pointer and the item to be retrieved as parameters, and should return the item's position, or -1 if the item is not found in the list. Use these procedures to write a program that inputs a series of integers, inserting them into a list until 0 is entered. Then a second series of integers is input, until 0 is entered, and the position of each integer in the list is displayed. Example:

Enter numbers to be inserted (0 to end): 34 23 1 45 7 0
The list is: 1 7 23 34 45
Enter numbers to be retrieved (0 to end): 23 8 45 0
23 is at position 3
8 is not in the list
45 is at position 5

Note that the program should be able to handle requests to retrieve items that are not in the list.

2. Create a class called Board for use in playing the game tic-tac-toe. Recall that the game is played on a 3 x 3 board, where every square is either empty, or contains an "X" or an "O." The game is won when there are three X's or three O's in a straight line, either in the same column, the same row, or one of the two diagonals. The game is a stalemate when the board has no empty squares but neither X nor O has won.

The following includes references to an enumerated type Player, defined as:
enum Player {X, O, empty};

Your class should have the following public methods:

Board: (constructor) This initializes the board, which means it sets all the positions to empty and does all else necessary to make the board ready for use.

void Place(P, Column, Row): A procedure that takes a Player P and sets the Column and Row of the board to be Player P if that position is empty.

If the position is occupied, the player loses a turn.

bool Win(P): A function that returns true if Player P has won the game, and false otherwise.
bool Stalemate(): A function that returns true if the board represents a game in stalemate, and false otherwise.

You do not have to write a complete program that plays the game. However, you are to write a short program that adequately tests all the operations of your class. Notice that the earliest either player can win is after 5 plays.

3. An integer can be represented by a linked list with one digit in each node. The least significant digit in this representation is in the first node of the list. This allows for integers of virtually any size. The nodes are of the following type:

struct digit
{ int Value; // a digit value, 0-9
digit* Next;
};

typedef digit* ptrType;

The following diagram shows the representation for 2149:

Develop an ADT named number with the following operations for unlimited-digit numbers. In the following descriptions, number refers to an object of your ADT. M, N and O are all of type number. The sample usage for each operation shows how it might be used, although you can make your operations work differently.

Increment: A method that increases the value of a number by 1. Sample usage: N.Increment();

Note that you cannot necessarily just change the last digit of the number; adding 1 to 1999, for example, requires changing all four digits to get 2000, and adding 1 to 9 requires making a new digit to get 10.

Hint: You should allow for three possibilities in your function regarding the initial value for N.

a. N is NULL
b. N is not NULL, and the value in the first node is 0..8
c. N is not NULL, and the value in the first node is 9

Copy: A method that copies one number to another. Note that you cannot just copy one pointer to another - you must create copies of each node in the original as illustrated in a copy constructor for linked lists. Sample usage: N.Copy(M);

Sum: A method that takes two numbers and sums them. Sample usage: N.Sum(M); (adds M to N). Don't forget about a carry when the sum of two digits is greater than 10.

Display Number: A method that displays the number in standard (most-significant digit first) form. Sample usage: N.DisplayNumber();

Your ADT should be a C++ class, with all functions and data declared in the appropriate sections. You may use recursion as you wish. Include a short program that adequately tests all the procedures in your ADT.