Lab: Exam Review

Generalizing List Operations

Two problems from the exam to work on today. Please commit them as two separate cpp files, with clear names so we know what we're looking at.

https://cssvn.utrgv.edu/svn_etomai/201720_2380/lab05_review/<your username>

Commit your work at the end of lab for lab credit!

Truncate

Write a function that takes a node pointer to a linked list and an integer n and truncates the list to length n (i.e. deletes all the nodes past the nth one). If n is greater or equal to the length of the list, you don't need to do anything. Do not create a memory leak!

Setup

Note: not complete, and does a lot of silly hardcoded stuff just for testing purposes. Typically we'd write a bunch of useful functions like print, append, find and such for testing (and because they're useful), but here we don't want to give too many hints by providing working functions. All list operations are fairly similar after all. Feel free to write whatever functions you find useful in solving the problem.

#include <cassert>

class node
{
public:
  int data;
  node * next;
  node(int d) { data = d; next = NULL; }
};

int main()
{
  // Test 1: general case
  // create a test list 17, 18, 19, 20
  node * head = new node(17);
  head->next = new node(18);
  head->next->next = new node(19);
  head->next->next->next = new node(20);

  // call your function
  truncate(head, 2);

  // test the results
  // (note, can't really test for memory leak in any simple way,
  //  so make sure you are deleting *all* the rest of the nodes!)
  assert(head != NULL);
  assert(head->data == 17);
  assert(head->next->data == 18);
  assert(head->next->next == NULL);


  // Test 2: n > length of list
  // create a test list 17, 18, 19, 20
  head = new node(17);
  head->next = new node(18);
  head->next->next = new node(19);
  head->next->next->next = new node(20);

  // call your function
  truncate(head, 10);

  // test the results
  // (note, can't really test for memory leak in any simple way,
  //  so make sure you are deleting *all* the rest of the nodes!)
  assert(head != NULL);
  assert(head->data == 17);
  assert(head->next->data == 18);
  assert(head->next->next->data == 19);
  assert(head->next->next->next->data == 20);
  assert(head->next->next->next->next == NULL);


  // Test 3: n == 0
  // create a test list 17, 18, 19, 20
  head = new node(17);
  head->next = new node(18);
  head->next->next = new node(19);
  head->next->next->next = new node(20);

  // call your function
  truncate(head, 0);

  // test the results
  // (note, can't really test for memory leak in any simple way,
  //  so make sure you are deleting *all* the rest of the nodes!)
  assert(head == NULL);

  return 0;
}

Reverse

Write a function that takes a node pointer and reverses the order of the items in the list. More specific than the exam: actually reverse the nodes themselves rather than changing the data!

Setup

#include <cassert>

class node
{
public:
  int data;
  node * next;
  node(int d) { data = d; next = NULL; }
};

int main()
{
  // Test 1: general case
  // create a test list 17, 18, 19, 20
  node * head = new node(17);
  head->next = new node(18);
  head->next->next = new node(19);
  head->next->next->next = new node(20);

  // store pointers to the nodes for testing that you didn't just change the data
  node * n0 = head;
  node * n1 = head->next;
  node * n2 = head->next->next;
  node * n3 = head->next->next->next;

  // call your function
  reverse(head);

  // test the results
  assert(head != NULL);
  assert(head == n3);
  assert(head->next == n2);
  assert(head->next->next == n1);
  assert(head->next->next->next == n0);
  assert(head->next->next->next->next == NULL);


  // Test 2: degenerate case (just to make sure it doesn't crash!)
  // create an empty test list
  head = NULL;

  // call your function
  reverse(head);


  return 0;
}