SE250:lab-4:hpan027

Straightforward coding lab.

Length

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

• Kept a counter and went through the list until the end, pretty simple

First/Second/Third/Fourth

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

• Well...

element_t second( Cons* list ) {
    int i;
    for ( i = 0; i < 1; i++) {
	if (list == nil)
	    return 0;
	list = list->tail;
    }
    return list->head;
}

• This time pass over the first element

element_t third( Cons* list ) {
    int i;
    for ( i = 0; i < 2; i++) {
	if (list == nil)
	    return 0;
	list = list->tail;
    }
    return list->head;
}

element_t fourth( Cons* list ) {
    int i;
    for ( i = 0; i < 3; i++) {
	if (list == nil)
	    return 0;
	list = list->tail;
    }
    return list->head;
}

• And so on

Nth

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

• Same code, except no need for a counter

Equal

int equal( Cons* first, Cons* second ) {
    while ( first->head == second->head ) {
	if (first->tail == nil && second->tail == nil)
	    return 1;
	first = first->tail;
	second = second->tail;
    }
    return 0;
}

• Again, not much to say. Go through each list until the elements are different or until the end is reached

Find

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

• Instructions weren't too clear as to what happens if a list has multiple elements of same value - assumed to be the first that comes up
• Code goes through list until the value is found, and return the cell at which it was found
• Otherwise return nil

Copy list

Cons* copy_list( Cons* list ) {
    Cons* copied = nil;
    int size = length(list);
    int i;

    for ( i = 1; i < size + 1 ; i++ ) {
	copied = cons(nth(size-i,list), copied);
    }
    return copied;
}

• This was a bit hard to do
• At first I pulled out every element in the list and stored into an array and then remade the list using cons (seeing as you have to start with the last value in the list when using cons)
• But then I realised I wrote an nth function and rewrote the code

Append

Cons* append( Cons* xs, Cons* ys ) {
    int size = length(xs);
    int i;

    for ( i = 1 ; i < size + 1; i++ ) 
	ys = cons( nth( size-i, xs ), ys );

    return ys;
}

• Pretty much identical code to above
• The instruction says xs/ys is not to be modified - however, seeing as these are simply local copies of the original lists, I don't really see how they can be modified

Nappend

• I wasn't sure how to do this without passing the function the address of xs seeing as any changes done within the function is lost once you are back in the main programme
• This would have required me to change the function to

Cons* nappend( Cons** xs, Cons* ys ) 

and I wasn't sure if this was what he had in mind

Reverse

Cons* reverse( Cons* xs ) {
    Cons* reversed = nil;
    int size = length(xs);
    int i = 0;

    for ( i = 0 ; i < size; i++ )
	reversed = cons( nth( i, xs), reversed );
    
    return reversed;
}

• Like append, copylist etc except without having to start from the end

Nreverse

• Same problem here as nappend - I'm not sure how I can modify the list without passing the function the address of the list