CMSC 15200 - Summer 2016

Lab 4: More Linked-Lists & Streams

Preliminaries

Create and svn add a lab4 directory inside your repository.

You will write all your code for this lab in a files named lab4.c, ill.c, and ill.h. Make sure to include a Makefile.

---

Integer Linked List

As seen in class, We defined the integer linked list data structure as follows:

struct int_linked_list {
  int data;
  struct int_linked_list *next;
};
                      
typedef struct int_linked_list ILL;
                      

Place this definition in your ill.h file.

---

Integer Linked List Functions

Implement the following operations. For the most part, the intended behavior of each should be clear from a brief description, but raise your hand if you have any questions about the implementations of these functions.

/* Removes the node at the given position.
   The function returns the list with the pos node deleted, otherwise it returns 
   the list untouched if the pos is less than zero, or pos is greater than or
   equal to the length of the list. 
   Assume the list uses zero indexing. */
ILL* ILL_remove(ILL* list, int pos)

/* Use the code shown in class to implement ILL_print.
   Add brackets "[...]" around the list elements.
   E.g. 4->3->5 should be printed as "[4,3,5]".
   There is no comma after the last element in the list. 
   NULL should be printed as "[]" */
void ILL_print(ILL* list);

/* Inserts a new node with the given data value at the specified index.
   If the index is greater than then the list length then insert the node at
   the end of the list.
   The function returns the list with the new node inserted, otherwise, return
   the list untouched if index is less than zero.
   Assume the list uses zero indexing. */
ILL* ILL_insert(ILL* list, int data, int index);

/* Returns an Ill list based on commands (see next section) listed in the filename.
   Assume you start with an empty list. */ 
ILL* ILL_readCommands(const char* filename); 

Your test cases should test enough cases to convince a moderate skeptic that your code does, in fact, work. It is fine to test the functions out of order. For each test case, write a comment about what you are testing in the function. You do not need to test the ILL_print function.

---

List Commands from a File

In your lab4.c file, allow main to take in command line arguments. The user will enter in a filename via the command line. This file will contain a list of commands for updating an ILL list. Each command will be on its own line. If the user does not enter in a filename then print a usage statement (usage: lab4 input_file). You will then pass this file to the ILL_readCommands function. Here's a list of commands that could be in a file:

• INSERT DATA POSITION : INSERT is the command name, which means you will insert the DATA value at the POSITION value in the list. E.g. "INSERT 4 5" means insert a new node with the value of 4 at index 5.


• REMOVE POSITION : REMOVE is the command name, which means you will remove the node at the POSITION value in the list. E.g. "REMOVE 5" means remove the node at position 5 in the list.


• PRINT : PRINT is the command name that means print out the list.


• INSERT_VALUES DATA DATA DATA ... DATA : INSERT_VALUES is the command name that means you will continue to insert the DATA values into the list until you reach the last DATA value on the line. E.g., if you have an empty list and you had the command "INSERT_VALUES 4 5 6 7", it will create a list with the node values as 4 -> 5 -> 6 -> 7. It needs to be in the same order specified. If the list is not empty, append the entries to the end of the list.

The file is delimited by spaces within a line.

Here's a simple commands.txt file (note that it doesn't test the INSERT_VALUES command!). This file should produce the list: 2->3->5

Once completed, commit all files to your repository (except files produced by the build process, e.g. binaries and .o files).

---