SE250:lab-4:llay008

TASK ONE

This first task was to create a function that gave back the length. I did this by looping through the list and incrementing a value. This task was straightforward.

int length(Cons* list) {
    int i = 0;
    for( ; list != nil; list = list->tail )
         i++;
    return i; 
}

TASKS TWO, THREE, FOUR, FIVE & SIX

The next tasks were to create functions that returned values from the linked list. This was made easier by the nature of the last element, which is the nil cons cell containing the value nil and a pointer to itself. This meant that I did not need a special case as returning list->head returned the nil cons cell, which had 0 stored at its head. I didn't realise this at first and created functions that contained an if statement for the case of an empty list.

element_t first(Cons* list) {
     return list->head;
}

element_t second(Cons* list) {   
    return list->tail->head;
}

element_t third(Cons* list) {    
    return list->tail->tail->head;
}

element_t fourth(Cons* list) {
    return list->tail->tail->tail->head;
}

element_t nth(int i, Cons* list) {
    int n;
    for (n=0; n < i; n++) {
        list = list->tail;
    }
    return list->head;
}

TASK SEVEN

This task is to compare two cons cells and see if they are the same. I looped through until the the lists were not the same or one of the lists ended. Initially I tried a different approach by using length to compare lengths and a for loop but I had problems with it.

int equal(Cons* list, Cons* list2) {
    while((list != nil) | (list2 != nil)) {
	if (list->head != list2->head)
	    return 0;
	list = list->tail;
	list2 = list2->tail;
     }
    return 1;
}

TASK EIGHT

The find task used a while loop to loop through the list until it finds the value that it is looking for or the loop ends, in which case it returns either the cons cell where the element is or the nil cons cell.

Cons* find(element_t elt, Cons* list) {
    while((list != nil) & (elt != list->head)){
        list = list->tail;
    }
    return list;
}

TASK ELEVEN

This is where I get out of order with the tasks. I was actually trying to create the appends function, but discovered that when I ran the code that xs was overwritten. This is not mean't to happen as part of the append function but it is as part of the nappend function, so with a little adjustment I was able to create nappends and my efforts were not in vain.

I had trouble in that the test cases were not thorough enough as the lists were too small and I would get the correct answer even though my code did not function as it was supposed to.

This function loops through until the nil pointer was located then points it to ys.

Cons* nappend(Cons* xs, Cons* ys) {  
   Cons* cell;
   cell = xs;  
   if(xs == nil)
      return ys;  
   while (cell->tail != nil){
      cell  = cell->tail; }
  cell->tail = ys;  
  return xs;
}

TASK ??? (copy_list)

This task was another case where I tested my code to find that it worked, only to find that when I extended it to cover a longer linked list that it did not work.

I finished most of the tasks but did not have time to finish my write up, so I will do this on Friday morning.