Mark: 2 revision(s)

2008-11-03T05:19:37Z

2 revision(s)

New page

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

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

element_t first( Cons* list )
{
if ( length( list ) >= 1 ) {
return list->head;
}
else {
// length of list is less than one so a first element cannot exist.
return 0;
}
}
element_t second( Cons* list )
{
if ( length( list ) >= 2 ) {
Cons *cp = list;
int i;
for ( i = 0; i < 1; i++ ) {
cp = cp->tail;
}
return cp->head;
}
else {
return 0;
}
}
element_t third( Cons* list )
{
if ( length( list ) >= 3 ) {
Cons *cp = list;
int i;
for ( i = 0; i < 2; i++ ) {
cp = cp->tail;
}
return cp->head;
}
else {
return 0;
}
}
element_t fourth( Cons* list )
{
if ( length( list ) >= 4 ) {
Cons *cp = list;
int i;
for ( i = 0; i < 3; i++ ) {
cp = cp->tail;
}
return cp->head;
}
else {
return 0;
}
}

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

int equal( Cons *xs, Cons *ys )
{
if ( length( xs ) == length( ys ) ) {
Cons *cp;
int i = 1;
for ( cp = xs; cp != nil; cp = cp->tail ) {
if ( cp->head != nth( i, ys ) ) {
return 0;
}
i++;
}
return 1;
}
else {
return 0;
}
}

Cons* find( element_t t, Cons* list )
{
Cons *cp;
for ( cp = list; cp != nil; cp = cp->tail ) {
if ( cp->head == t ) {
return cp;
}
}
return 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" );
}

Cons* copy_list( Cons *list )
{
Cons *cp = nil;
Cons *copy = nil;

int len = length(list);
element_t ts[ len ];
int i = 0;

for ( cp = list; cp != nil; cp = cp->tail ) {
ts[ i ] = cp->head;
i++;
}
if ( i != 0 ) {
i = 0;
for ( i = (len - 1); i >= 0; i-- ) {
copy = cons( ts[i], copy );
}
}
return copy;
}

Cons* append( Cons *xs, Cons *ys )
{
Cons *zs = copy_list( xs );
Cons *cp;

cp = zs;
while ( cp != nil ) {
if ( cp->tail == nil ) {
cp->tail = ys;
cp = nil;
}
else {
cp = cp->tail;
}
}

return zs;
}

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

Cons* reverse( Cons *xs )
{
Cons *cp = nil;
Cons *copy = nil;

for ( cp = xs; cp != nil; cp = cp->tail ) {
copy = cons( cp->head, copy );
}
return copy;
}

Cons* nreverse( Cons *xs )
{
Cons *cp = nil;

int len = length( xs );
element_t ts[ len ];
int i = 0;

for ( cp = xs; cp != nil; cp = cp->tail ) {
ts[ i ] = cp->head;
i++;
}
if ( i != 0 ) {
i = len - 1;
for ( cp = xs; cp != nil; cp = cp->tail ) {
cp->head = ts[i];
i--;
}
cp = xs;
}

return cp;
}
/* 2nd try for the destructive reverse function */
Cons *nnreverse( Cons *xs )
{
Cons *prev = xs;
Cons *cp = xs->tail;
prev->tail = nil;
while ( cp != nil ) {
Cons *t = cp->tail;
cp->tail = prev;
prev = cp;
cp = t;
}
return prev;
}

int main( )
{
printf( "\n" );

print_list( cons(1,cons(2,cons(3,nil))) ); /* expect: List[1,2,3] */

Cons *my_list = cons(2, cons(4, cons(6, cons(8, nil))));
print_list( my_list );
printf( "Length of my_list is %d\n", length(my_list) );

printf( "First element is %d\n"
"Second element is %d\n"
"Third element is %d\n"
"Fourth element is %d\n",
first( my_list ), second( my_list ), third( my_list ), fourth( my_list ) );

int i;
for ( i = 0; i < 10; i++ ) {
printf( "The %d'th element is %d\n", i, nth( i, my_list ) );
}

Cons *xs = cons(1, cons(2, nil));
Cons *ys = cons(1, cons(2, xs));

print_list( xs );
print_list( ys );

printf( "The two lists xs and ys are %s\n", (equal(xs, ys) == 1) ? "equal" : "not equal" );

Cons *cp = cons(1, cons(2, cons(3, nil)));

Cons *result = find( 4, cp );
printf( "%d\n", (result == nil) ? 0 : result->head );

Cons *cp = cons(67, cons(45, cons(21, cons(89, nil))));

print_list( cp );
print_list( copy_list( cp ) );

printf( "%s\n", (equal( cp, copy_list(cp) ) == 1) ? "equal" : "not equal" );

Cons *xs = cons(1, cons(2, cons(3, nil)));
Cons *ys = cons(4, cons(5, cons(6, nil)));
Cons *zs = append( xs, ys );

print_list( xs );
print_list( ys );
print_list( zs );

ys->head = 5;
print_list( ys );
print_list( zs );

Cons *xs = cons(1, cons(2, cons(3, nil)));
Cons *ys = cons(4, cons(5, cons(6, nil)));
Cons *zs = nappend( xs, ys );
print_list( xs );
print_list( ys );
print_list( zs );

xs->head = 3;
ys->head = 5;

print_list( xs );
print_list( ys );
print_list( zs );

Cons *xs = cons(1, cons(2, cons(3, cons(4, cons(5, cons(6, nil))))));
print_list( xs );
Cons *ys = nnreverse( xs );

print_list( xs );

print_list( ys );

return 0;
}
</pre>

SE250:lab-4:rwan064:code - Revision history

Mark: 2 revision(s)