Programming Projects

Programming Projects require more problem-solving than Practice Programs and can usually be solved many different ways. Visit www.myprogramminglab.com to complete many of these Programming Projects online and get instant feedback.

  1. Write a void function that takes a linked list of integers and reverses the order of its nodes. The function will have one call-by-reference parameter that is a pointer to the head of the list. After the function is called, this pointer will point to the head of a linked list that has the same nodes as the original list, but in the reverse of the order they had in the original list. Note that your function will neither create nor destroy any nodes. It will simply rearrange nodes. Place your function in a suitable test program.

  2. Write a function called mergeLists that takes two call-by-reference arguments that are pointer variables that point to the heads of linked lists of values of type int. The two linked lists are assumed to be sorted so that the number at the head is the smallest number, the number in the next node is the next smallest, and so forth. The function returns a pointer to the head of a new linked list that contains all of the nodes in the original two lists. The nodes in this longer list are also sorted from smallest to largest values. Note that your function will neither create nor destroy any nodes. When the function call ends, the two pointer variable arguments should have the value NULL.

  3. Design and implement a class whose objects represent polynomials. The polynomial

    anxn+an−1xn−1+…+a0

    will be implemented as a linked list. Each node will contain an int value for the power of x and an int value for the corresponding coefficient. The class operations should include addition, subtraction, multiplication, and evaluation of a polynomial. Overload the operators +, −, and * for addition, subtraction, and multiplication.

    Evaluation of a polynomial is implemented as a member function with one argument of type int. The evaluation member function returns the value obtained by plugging in its argument for x and performing the indicated operations. Include four constructors: a default constructor, a copy constructor, a constructor with a single argument of type int that produces the polynomial that has only one constant term that is equal to the constructor argument, and a constructor with two arguments of type int that produces the one-term polynomial whose coefficient and exponent are given by the two arguments. (In the notation above, the polynomial produced by the one-argument constructor is of the simple form consisting of only a0. The polynomial produced by the two-argument constructor is of the slightly more complicated form anxn.) Include a suitable destructor. Include member functions to input and output polynomials.

    When the user inputs a polynomial, the user types in the following:

    an×^n+an−1×^n−1+…+a0

    However, if a coefficient ai is zero, the user may omit the term aix^i. For example, the polynomial

    3x4+7x2+5

    can be input as

    3x^4 + 7x^2 + 5

    It could also be input as

    3x^4 + 0x^3 + 7x^2 + 0x^1 + 5

    If a coefficient is negative, a minus sign is used in place of a plus sign, as in the following examples:

    3x^5 − 7x^3 + 2x^1 − 8
−7x^4 + 5x^2 + 9

    A minus sign at the front of the polynomial, as in the second of the two examples, applies only to the first coefficient; it does not negate the entire polynomial. Polynomials are output in the same format. In the case of output, the terms with zero coefficients are not output.

    To simplify input, you can assume that polynomials are always entered one per line and that there will always be a constant term a0. If there is no constant term, the user enters 0 for the constant term, as in the following:

    12x^8 + 3x^2 + 0

  4. In this project you will redo Programming Project 8 from Chapter 11 using a linked list instead of an array. As noted there, this is a linked list of double items. This fact may imply changes in some of the member functions. The members are as follows: a default constructor; a member function named addItem to add a double to the list; a test for a full list that is a Boolean-valued function named full( ); and a friend function overloading the insertion operator <<.

  5. A harder version of Programming Project 4 would be to write a class named List, similar to Project 4, but with all the following member functions:

    • Default constructor, List();

    • double List::front();, which returns the first item in the list

    • double List::back();, which returns the last item in the list

    • double List::current();, which returns the “current” item

    • void List::advance();, which advances the item that current() returns

    • void List::reset(); to make current() return the first item in the list

    • void List::insert(double afterMe, double insertMe);, which inserts insertMe into the list after afterMe and increments the private: variable count.

    • int size();, which returns the number of items in the list

    • friend istream& operator <<(istream& ins, double writeMe);

    The private data members should include the following:

    node* head;
node* current;
int count;

    and possibly one more pointer.

    You will need the following struct (outside the list class) for the linked list nodes:

    struct node
{
    double item;
    node *next;
};

    Incremental development is essential to all projects of any size, and this is no exception. Write the definition for the List class, but do not implement any members yet. Place this class definition in a file list.h. Then #include "list.h" in a file that contains int main(){}.Compile your file. This will find syntax errors and many typographical errors that would cause untold difficulty if you attempted to implement members without this check. Then you should implement and compile one member at a time, until you have enough to write test code in your main function.

  6. In an ancient land, the beautiful princess Eve had many suitors. She decided on the following procedure to determine which suitor she would marry. First, all of the suitors would be lined up one after the other and assigned numbers. The first suitor would be number 1, the second number 2, and so on up to the last suitor, number n. Starting at the first suitor she would then count three suitors down the line (because of the three letters in her name) and the third suitor would be eliminated from winning her hand and removed from the line. Eve would then continue, counting three more suitors, and eliminate every third suitor. When she reached the end of the line she would continue counting from the beginning.

    For example, if there were six suitors then the elimination process would proceed as follows:

    123456 initial list of suitors, start counting from 1
    12456 suitor 3 eliminated, continue counting from 4
    1245 suitor 6 eliminated, continue counting from 1
    125 suitor 4 eliminated, continue counting from 5
    15 suitor 2 eliminated, continue counting from 5
    1 suitor 5 eliminated, 1 is the lucky winner

    Write a program that creates a circular linked list of nodes to determine which position you should stand in to marry the princess if there are n suitors. A circular linked list is a linked list where the link field of the last node in the list refers to the node that is the head of the list. Your program should simulate the elimination process by deleting the node that corresponds to the suitor that is eliminated for each step in the process. Consider the possibility that you may need to delete the "head" node in the list.

  7. Redo (or do for the first time) Programming Project 5 from Chapter 9. However, instead of a dynamic array to store the list of user IDs for each computer station, use a linked list. The node for the lists should contain the station number and user ID of the person logged in on that station. If nobody is logged on to a computer station, then no entry should exist in the linked list for that computer station.

  8. Modify or rewrite the Queue class (Display 13.21 through 13.23) to simulate customer arrivals at the Department of Motor Vehicles (DMV) counter. As customers arrive, they are given a ticket number starting at 1 and incrementing with each new customer. When a customer service agent is free, the customer with the next ticket number is called. This system results in a FIFO queue of customers ordered by ticket number. Write a program that implements the queue and simulates customers entering and leaving the queue. Input into the queue should be the ticket number and a timestamp when the ticket was entered into the queue. A ticket and its corresponding timestamp is removed when a customer service agent handles the next customer. Your program should save the length of time the last three customers spent waiting in the queue. Every time a ticket is removed from the queue, update these times and output the average of the last three customers as an estimate of how long it will take until the next customer is handled. If nobody is in the queue, output that the line is empty.

    Code to compute a timestamp based on the computer’s clock is given below. The time(NULL) function returns the number of seconds since January 1, 1970, on most implementations of C++:

    #include <ctime>
...
int main()
{
    long seconds;
    seconds = static_cast<long>(time(NULL));
    cout << "Seconds since 1/1/1970: " << seconds << endl;
    return 0;
}
Sample execution is shown here:
The line is empty.
Enter '1' to simulate a customer's arrival, '2' to help the next customer, or '3' to quit.
1
Customer 1 entered the queue at time 100000044.
Enter '1' to simulate a customer's arrival, '2' to help the next customer, or '3' to quit.
1
Customer 2 entered the queue at time 100000049.
Enter '1' to simulate a customer's arrival, '2' to help the next customer, or '3' to quit.
1
Customer 3 entered the queue at time 100000055.
Enter '1' to simulate a customer's arrival, '2' to help the
next customer, or '3' to quit.
2
Customer 1 is being helped at time 100000069. Wait time = 25 seconds.
The estimated wait time for customer 2 is 25 seconds.
Enter '1' to simulate a customer's arrival, '2' to help the next customer, or '3' to quit.
2
Customer 2 is being helped at time 100000076. Wait time = 27 seconds.
The estimated wait time for customer 3 is 26 seconds.
Enter '1' to simulate a customer's arrival, '2' to help the next customer, or '3' to quit.
1
Customer 4 entered the queue at time 100000080.
Enter '1' to simulate a customer's arrival, '2' to help the
next customer, or '3' to quit.
2
Customer 3 is being helped at time 100000099. Wait time = 44
seconds.
The estimated wait time for customer 4 is 32 seconds.

  9. The following figure is called a graph. The circles are called nodes, and the lines are called edges. An edge connects two nodes. You can interpret the graph as a maze of rooms and passages. The nodes can be thought of as rooms, and an edge connects one room to another. Note that each node has at most four edges in the graph.

    A graph consisting of nodes and edges.

    Write a program that implements the maze using nodes and pointers. Each node in the graph will correspond to a node in your code that is implemented in the form of a class or struct. The edges correspond to bidirectional links that point from one node to another. Start the user in node A. The user’s goal is to reach the finish in node L. The program should output possible moves in the north, south, east, or west direction. Sample execution is shown here.

    You are in room A of a maze of twisty little passages, all alike.
You can go (E)ast, (S)outh, or (Q)uit.
E
You are in room B of a maze of twisty little passages, all alike.
You can go (W)est, (S)outh, or (Q)uit.
S
You are in room F of a maze of twisty little passages, all alike.
You can go (E)ast, (N)orth, or (Q)uit.
E

  10. Reverse Polish Notation (RPN), or postfix notation, is a format to specify mathematical expressions. In RPN, the operator comes after the operands instead of the normal format in which the operator is between the operands (this is called infix notation). Starting with an empty stack, a RPN calculator can be implemented with the following rules:

    • If a number is input, push it on the stack.

    • If "+" is input, then pop the last two operands off the stack, add them, and push the result on the stack.

    • If "−" is input then pop value1, pop value2, then push value2-value1 on the stack.

    • If "*" is input, then pop the last two operands off the stack, multiply them, and push the result on the stack

    • If "/" is input them pop value1, pop value2, then push value2/value1 on the stack

    • If "q" is input, then stop inputting values, print out the top of the stack, and exit the program

    Modify the Stack class given in Section 13.2 to store integers instead of characters. Use the modified stack to implement a RPN calculator. Output an appropriate error message if there are not two operands on the stack when given an operator. Here is a sample input and output that is equivalent to ((10 − (2 + 3)) * 2)/5:

    10
2
3
+
−
2
*
5
/
q
The top of the stack is:  2

  11. You should complete the Programming Project 10 before attempting this one. Write a program that converts a fully parenthesized mathematical infix expression into an equivalent postfix expression and then evaluates the postfix expression. A fully parenthesized expression is one in which parentheses surround every operator and its operands. Starting with an empty stack of strings to store operators and an empty queue of strings to store the postfix expression, the conversion can be implemented with the following rules:

    • If "(" is input, then ignore it.

    • If a number is input, then add it to the queue.

    • If an operator (either "*", "+", "−", or "/") is input, then push it on the stack.

    • If ")" is input, then pop the operator from the stack and add it to the queue.

    • If "q" is input, then exit.

    When the final operator is popped from the stack, the queue contains the equivalent postfix expression. Use your solution from Programming Project 10 to evaluate it. You will need to convert a string object to an integer. Use the cStr() function to convert the string to a C string, and then use the atoi function to convert the C string into an integer. Refer to Chapter 8 for details.

    Sample output is shown below for ((10 − (2 + 3)) * 2),which translates to the postfix expression 10 2 3 + − 2 *:

    (
(
10
−
(
2
+
3
)
)
*
2
)
q
The expression evaluates to 10