CS1411 - Introduction to Programming Principles I

Programming / Lab Assignment 9

Warning: There will be points deducted if the assignmnent is not submitted in the correct format. Please see the submission guidelines!

Sorted Linked List

You are supposed to write functions for a sorted linked list.

Your program will consist of 3 Files: main.cpp, llist.h, llist.cpp. The main function should be in main.cpp, the struct definition and all function headers in llist.h and the function definitions in llist.cpp

Please protect you .h file agains multiple inclusion as seen in class and the book.

Use a struct similar to the following for your nodes:

struct node {
  int data;
  node *next;
  }

Write the following functions:

void init(node* &head) should initialize head to NULL

void free(node* &head) should free the memory for all the nodes in the list and reset head to NULL

int count(node* head) should return the number of nodes in the list

void add(node* &head, int element) will add a new node with the data element to the list. Since this is a sorted list, the new element should be inserted in such a way, that the list is always sorted ascending (smallest element at the head). Please make sure that you cover all possible cases (beginning of list, middle of list, end of list)!

int smallest(node* head)returns the data of the smallest element (at the head of the list) or 0 if the list is empty.

int largest(node* head)returns the data of the largest element (at the end of the list) or 0 if the list is empty.

int elementAt(node* head, int index) returns data of the element at index index. Throws an int exception with the index if the index is out of bouds. Indices start with 0 as usual (the first element has index 0).

node* findElement(node* head, int element) will return a pointer to the first node that has data element or NULL if no such node exists.

void removeElement(node* &head, node* which) will remove this element from the list. head may be NULL or which may be NULL. In this case, nothing should happen. If the element is not found, nothing should happen.

void printElements(node* head) outputs all the elements from the list to the screen, in one line, separated by a space

Please make sure that all your functions work on an empty list (head == null)!

The only part that will be graded is llist.cpp and llist.h. You may use additional functionality in you main function / file and other files if you need it for testing

Use a main function simlar to the following to test your program. You may use a different main function if all the functionality can be tested with it:

int main()
  node *list1;
  node *nd;
  int x;

  cout << "Testing list functionality..." << endl;

  init(list1);

  if (count(list1) != 0) cout << "Count function does not work on empty list" << endl;
  if (largest(list1) != 0) cout << "Largest function does not work on empty list" << endl;
  if (smallest(list1) != 0) cout << "Smallest function does not work on empty list" << endl;
  try {
    x = elementAt(list1, 0);
    cout << "ElementAt does not throw exception" << endl;
  } catch ( int e) {
    if (e != 0) cout << "ElementAt throws wrong exception" << endl;
  }
  nd = findElement(list1,5);
  if (nd != NULL) cout << "Find does not work on empty list!" << endl;
  cout << "There should be a blank line: " << endl;
  printElements(list1);
  cout << "In between these two." << endl;

  add(list1,7); 
  add(list1,9); 
  add(list1,11); 
  add(list1,13); 

  add(list1,5);
  add(list1,3);
  add(list1,-2);

  add(list1,6);
  add(list1,8);

  if (count(list1)!=9) cout << "Error in count or add!" << endl;
  if (smallest(list1)!=-2) cout << "Error in smallest or add!" << endl;
  if (largest(list1)!=13) cout << "Error in largest or add!" << endl;

  if (elementAt(list1,3)!=6) cout << "Error in elementAt or add!" << endl;
  nd = findElement(list1,7);
  nd = nd->next;
  if (nd->data !=8) cout << "Error in findElement or add!" << endl;

  cout << "-2 3 5 6 7 8 9 11 13    <---- Should be" << endl;
  printElements(list1);
  removeElement(list1,nd);
  cout << "-2 3 5 6 7 9 11 13      <---- Should be" << endl;
  printElements(list1);
  free(list1);
  cout << "There should be an empty line" << endl;
  printElements(list1);
  cout << "in here." << endl;

  cout << "End of tests" << endl;
} 

Your programs should include comments whith you name, testnumber, etc. in the top. See also the Submission guidelines

The assignment is due Friday Nov 12, 6pm. You have to submit it electronically as stated in the submission guidelines!

Lost? See the Help! page.