SE250:lab-4:shua066

Lab4

This Lab are all about Linked list.

Start code from LL.c Use Test code from test-code.c

task1

use funtion int Length(Cons*) to return the number of elements in the list

code

#include <assert.h>
#include <stdlib.h>
#include <stdio.h>
typedef int element_t;
typedef
struct Cons {
  element_t head;
  struct Cons* tail;
} Cons;
static Cons NIL = { 0, &NIL };
Cons* nil = &NIL;
Cons* cons( element_t elt, Cons* tail ) {
  Cons* cell = malloc( sizeof(Cons) );
  assert( cell != 0 );
  cell->head = elt;
  cell->tail = tail;
  return cell;
}
int length(Cons* list){
    int length=0;
    for (; list!=nil; list=list->tail){
       length++;
    }
    return length;
}
int main( ) {
  print_list( cons(1,cons(2,cons(3,nil))) ); /* expect: List[1,2,3] */
  assert( length( nil ) == 0 );
  assert( length( cons(10,cons(20,cons(30,nil))) ) == 3 );
  return 0;
}

for the funtion length need to check the list not equal to nil and list = list->tail.

task2

write functions element_t first(Cons*), element_t second(Cons*), element_t third(Cons*), element_t fourth(Cons*) that return the element in the named position.

code

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;
}

test code is

  assert( first( nil ) == 0 );
  assert( first( cons(10,cons(20,nil)) ) == 10 );
  assert( second( nil ) == 0 );
  assert( second( cons(10,cons(20,nil)) ) == 20 );
  assert( third( nil ) == 0 );
  assert( third( cons(10,cons(20,nil)) ) == 0 );
  assert( third( cons(10,cons(20,cons(30,nil))) ) == 30 );
  assert( fourth( nil ) == 0 );
  assert( fourth( cons(10,cons(20,nil)) ) == 0 );
  assert( fourth( cons(10,cons(20,cons(30,nil))) ) == 0 );
  assert( fourth( cons(10,cons(20,cons(30,cons(40,nil)))) ) == 40 );

because the code has

 static Cons NIL = { 0, &NIL };

so dont need to check that whether the tail is equal to nil.

task3

write a funtion element_t nth(int i,Cons*) the return the i'th element of a list. or 0 if no such element exists.

code

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

this task is need to check that whether i is bigger than the length of the Cons* and return the element.

task4

write a funtion int equal(Cons*,Cons*) that returns true(1)if both list have exactly the same elements in same order,false(0) otherwise.

task5

write a funtion Cond* find(element_t,Cons*) to search for an element in list and return the Cons cell that contains this value,or the empty list if i does not occour in the list.