Mark: 2 revision(s)

2008-11-03T05:19:34Z

2 revision(s)

New page

/*
File: lab-4-soln.c
Date: 1 April 2008
Author: John Hamer
Purpose: Sample solution to SOFTENG lab #4, 2008
*/

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

void print_list( Cons* list ) {
char* sep = "";
printf( "List[" );
for( ; list != nil; list = list->tail ) {
printf( "%s%d", sep, list->head );
sep = ",";
}
printf( "]\n" );
}

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

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 ) {
while( i-- > 0 )
list = list->tail;
return list->head;
}

int equal( Cons* xs, Cons* ys ) {
while( xs != nil && ys != nil ) {
if( xs->head != ys->head )
return 0;
xs = xs->tail;
ys = ys->tail;
}
return xs == ys;
}

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

Cons* append( Cons* xs, Cons* ys ) {
Cons* result; /* deliberately left uninitialised */
Cons** cpp = &result; /* pointer to the last uninitialised list pointer */
for( ; xs != nil; xs = xs->tail ) {
*cpp = cons(xs->head, (Cons*)0); /* nil would be misleading; this list is incomplete */
cpp = &(*cpp)->tail;
}
*cpp = ys;
return result;
}

Cons* copy_list( Cons* list ) { return append( list, nil ); }

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

Cons* reverse( Cons* list ) {
Cons* rev = nil;
for( ; list != nil; list = list->tail )
rev = cons( list->head, rev );
return rev;
}

Cons* nreverse( Cons* list ) {
Cons* prev = nil;
Cons* next;
for( ; list != nil; list = next ) {
next = list->tail;
list->tail = prev;
prev = list;
}
return prev;
}

int main( ) {
print_list( nil ); /* List[] */
print_list( cons(10,cons(20,cons(30,nil))) ); /* List[10,20,30] */

assert( length( nil ) == 0 );
assert( length( cons(10,cons(20,cons(30,nil))) ) == 3 );

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

assert( nth(0,nil) == 0 );
assert( nth(1,nil) == 0 );
assert( nth(0,cons(10,nil)) == 10 );
assert( nth(1,cons(10,nil)) == 0 );

assert( equal(nil,nil) );
assert( ! equal(nil,cons(10,nil)) );
assert( ! equal(cons(10,nil),nil) );
assert( equal(cons(10,nil),cons(10,nil)) );
assert( ! equal(cons(10,nil),cons(20,nil)) );

print_list( find(10,nil) ); /* List[] */
print_list( find(20,cons(10,nil)) ); /* List[] */
print_list( find(10,cons(10,nil)) ); /* List[10] */

print_list( append(nil,nil) ); /* List[] */
print_list( append(nil,cons(10,nil)) ); /* List[10] */
print_list( append(cons(10,nil),nil) ); /* List[10] */
print_list( append(cons(10,nil),cons(20,nil)) ); /* List[10,20] */

print_list( copy_list(nil) ); /* List[] */
print_list( copy_list(cons(10,nil)) ); /* List[10] */
print_list( copy_list(cons(10,cons(20,nil))) ); /* List[10,20] */

print_list( nappend(nil,nil) ); /* List[] */
print_list( nappend(nil,cons(10,nil)) ); /* List[10] */
print_list( nappend(cons(10,nil),nil) ); /* List[10] */
print_list( nappend(cons(10,nil),cons(20,nil)) ); /* List[10,20] */

print_list( reverse(nil) ); /* List[] */
print_list( reverse(cons(10,nil)) ); /* List[10] */
print_list( reverse(cons(10,cons(20,nil))) ); /* List[20,10] */

print_list( nreverse(nil) ); /* List[] */
print_list( nreverse(cons(10,nil)) ); /* List[10] */
print_list( nreverse(cons(10,cons(20,nil))) ); /* List[20,10] */

return 0;
}

/*
Local Variables:
compile-command: "gcc -Wall lab-4-soln.c -o lab-4-soln && ./lab-4-soln"
End:
*/

SE250:lab-4:jham005 - Revision history

Mark: 2 revision(s)