CSE 303, Autumn 2009
Homework 4: basic linked list exercises

Due Tuesday, November 10, 2009, 11:30 PM
100 points total


The objective of this assignment is to ensure that you are comfortable with basic linked list manipulations in C: creating elements on the heap, linking them together with pointers, freeing space, etc.  There is no motivating problem -- it is simply a set of exercises (like practicing scales on an instrument).  If you haven't done any of this before, it may not be simple for you; definitely start early.  (And just to be explicit, when this assignment talks about "the stack" it means the one you are implementing, not the program stack that the compiler/run-time system/operating system manage.)
  1. (40 points) Implement a heap-based stack in C.  Write a file stack.c that
    1. defines a typedef struct StackNode that contains two fields: an int to store data and a pointer to a StackNode.
    2. defines a function StackNode *push(StackNode *top,int data) that pushes the data onto the top of the stack and returns a pointer to the new top element.
    3. defines a function StackNode *pop(StackNode *top,int *data) that pops the data from the top of the stack, puts the popped value into data, and returns a pointer to the new top element.
    4. if the underlying memory allocation for StackNode fails, push should return NULL.
    5. if an attempt is made to pop an empty stack, pop should return NULL.
    6. The main program reads integer values from stdin
      1. 0 terminates the program.
      2. -1 prints the top element on the stack and pops the stack (it prints "Popping <x>" where <x> is the top element of the stack); if the stack is empty, then "Stack is empty" is printed and the program continues.
      3. Any other integer is pushed on the stack (it prints "Pushing <x>" where <x> is the value being placed on top of the stack); if the element cannot be pushed, then "Stack is full" is printed and the program continues.
      4. All input is guaranteed to be well-formed.
The following figures show a sequence of the linked lists you create for this program.  The first one shows the state after a -4 and then a 10 is pushed.  The second one then shows a 173 pushed.  The third and the fourth show one pop and then another pop.


stack linked list

  1. (20 points) Reverse a linked list.  In the file reverse.c, write a function Node *reverse(Node *list)
    1. Node is defined precisely like StackNode in the first part -- an int data field and a pointer field to the next node.
    2. The reverse function takes a pointer to a list and returns a pointer to a new list that has the elements in reverse order.
    3. The original list must be freed.
    4. The main program accepts integers until a 0 input is found.
    5. Upon finding a 0, the program prints "The list is:" and then the original list with each integer on its own line.
    6. After printing the original list, the program prints "The reverse of the list is:" and then prints the reverse list with each integer on its own line.
The following shows a list before it is reversed, and after it is reversed.

reverse linked list

Your program should produce no errors or warnings from gcc -Wall .  In terms of grading, most of the points will come from the correctness of your programs, although some points will also come from the style and design and appropriate simplicity of your code. Do not leak memory -- that is, make sure to free any memory you can.  You should not use a more complex command or control structure when a more simple one would achieve the same result. You should reduce redundancy when reasonable.

  1. (40 points)  Implement an array of stacks, where the stacks are defined using your program for (1) above.  The array is of fixed size defined by the preprocessor symbol NUMSTACKS, which can be assumed to be an integer between 2 and 100.  Each array element points to a stack, each stack is initialized as an empty stack.
    The main program reads integer values from stdin and uses a slightly modified version of the above rules:
    1. -3 terminates the program.
    2. -2 indicates that the following integer indicates which stack is to be manipulated; it is guaranteed that the number following the -2 is in the range 0 to NUMSTACKS-1.
    3. The stack to be manipulated is initialized to 0.
    4. -1 prints the top element on the stack and pops the stack (it prints "Stack <y>: Popping <x>" where <x> is the top element of the stack and <y> is the stack being manipulated); if the stack is empty, then "Stack <y> is empty" is printed and the program continues.
    5. Any other integer (not -1, or -2 or -3) is pushed on the stack (it prints "Stack <y>: Pushing <x>" where <x> is the value being placed on top of the stack and <y> is the stack being manipulated); if the element cannot be pushed, then "Stack is full" is printed and the program continues.
    6. All input is guaranteed to be well-formed.
The following figure below (the stacks are show here vertically instead of horizontally, as above, but they are no different from those above internally) shows a data structure that could be created by any of the following inputs:

stack array figure

Turn in will be via the dropbox, with a single file hw4.tar.gz containing stack.c, reverse.c, and stackarray.c.