SE250:lab-4:dcho040

Codes

/*
  File: LL.c
  Date: 1 April 2008
  Author: John Hamer
  Purpose: Starter code for SOFTENG 250 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;

// all cons have to initialized by nil to have length more than 1 ( because (length(list) - 1) is used in the codes )
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 count = 0;
  for( ; list != nil; list = list->tail ) {
	count ++;
  }
  return count;
}

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

element_t second(Cons* list) { return nth(1,list); }

element_t third(Cons* list) { return nth(2,list); }

element_t fourth(Cons* list) { return nth(3,list); }

element_t nth(int i, Cons* list) {
  // check i is bigger than the length of the list
  if (length( list ) < i) { return 0; }

  // goes i th element
  int j;
  for ( j=0; j < i; j++ ) {
    list = list -> tail;
  }

  // return the value from i the element
  return list -> head;
}

Cons* nth_cons(int i, Cons* list) {
  // check i is bigger than the length of the list
  if (length( list ) < i) { return nil; }

  // goes i th element
  int j;
  for ( j=0; j < i; j++ ) {
    list = list -> tail;
  }

  // return the value from i the element
  return list;
}

int equal(Cons* list, Cons* list2) {
  // check the length
  if ( length(list) != length(list2) ) { return 0; }

  // check the values
  int i;
  for(i=0; i < length( list ); i++) {
	if ( nth(i, list) != nth(i, list2) ) { return 0; }
  }

  // return 1 (two lists are same)
  return 1;
}

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

Cons* copy_list(Cons* list) {
  Cons* new_list = nil;
  int i;
  for(i = (length( list ) - 1); i >= 0; i--) {
    new_list = cons(nth(i, list), new_list);
  }
  return new_list;
}

Cons* append(Cons* xs, Cons* ys) {
  Cons* both = copy_list(ys);
  int i;
  for (i = (length( xs )-1); i >= 0; i--) {
	both = cons(nth(i, xs), both);
  }
  return both;
}

Cons* nappend(Cons* xs, Cons* ys) {
  Cons* both = copy_list(ys);
  if ( xs == nil ) {
	 xs = both;
	  return xs;
  }
  nth_cons(length(xs)-1, xs) -> tail = both;
  return xs;
}

Cons* reverse(Cons* xs) {
  int i;
  Cons* new_list = nil;
  for(i=0; i < length( xs ); i++) {
	new_list = cons(nth(i, xs), new_list);
  }
  return new_list;
}

Cons* nreverse(Cons* xs) {
  int i, j, exchange; // i: nth from first, j: nth from last
  for(i=0; i < (length( xs ) / 2); i++) {
	j = (length( xs ) - 1) - i;
	exchange = nth(i, xs);
	nth_cons(i, xs) -> head = nth_cons(j, xs) -> head;
	nth_cons(j, xs) -> head = exchange;
  }
  return xs;
}

void test_LL( ) {
  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] */
}

int main( ) {
  Cons* list = cons(1,cons(2,cons(3,nil)));

  // 1th
  printf("-1th-\n");
  print_list( list ); /* expect: List[1,2,3] */
  printf("\n");

  // 2th
  printf("-2th-\n");
  printf("Length of the list = %d\n", length( list ));
  printf("\n");

  // 3th
  printf("-3th-\n"
         "first : %d\n"
         "second: %d\n"
         "third : %d\n"
         "fourth : %d\n"
         , first( list ), second( list ), third( list ), fourth( list ));
  printf("\n");

  // 4th
  printf("-4th-\n"
         "first : %d\n"
         "second: %d\n"
         "third : %d\n"
         "fourth : %d\n"
         , nth(0, list ), nth(1, list ), nth(2, list ), nth(3, list ));
  printf("\n");

  // 5th
  Cons* list2 = cons(1,cons(2,cons(3,nil)));
  Cons* list3 = cons(1,cons(2,nil));
  Cons* list4 = cons(1,cons(10,cons(2,nil)));
  printf("-5th-\n"
         "same            : %d\n"
         "diffenent length: %d\n"
         "diffenent values: %d\n"
         , equal(list, list2), equal(list, list3), equal(list, list4));
  printf("\n");

  // 6th
  Cons* found = find(2, list);
  printf("-6th-\n"
  		 "Looking for 2 in the list [1, 2, 3]\n"
         "head: %d\n"
         "tail: %p\n"
         , found -> head, found -> tail);
  printf("\n");

  // 7th
  Cons* copy = copy_list(list);
  printf("-7th-\n"
         "after copy\n"
         " orignal & copy : %d\n"
         , equal(list, copy));
    // change the copyed list
  copy = cons(6, copy);
    // compare again
  printf("after change the copy \n"
         " orignal & copy : %d\n"
         , equal(list, copy));
  printf("\n");

 // 8th
  printf("-8th-\n"
         "list  = ");
  print_list( list ); /* expect: List[1,2,3] */

  printf("list3 = ");
  print_list( list3 ); /* expect: List[1,2] */

  printf("use append to both\n");
  Cons* both = append(list, list3);

  printf("both  = "); /* expect: List[1,2,3,1,2] */
  print_list( both );

  printf("after use append\n"
         "list  = ");
  print_list( list ); /* expect: List[1,2,3] */

  printf("list3 = ");
  print_list( list3 ); /* expect: List[1,2] */
  printf("\n");

  // 9th
  printf("-9th-\n"
         "list  = ");
  print_list( list ); /* expect: List[1,2,3] */

  printf("list3 = ");
  print_list( list3 ); /* expect: List[1,2] */

  printf("use nappend to list_extend\n");
  Cons* list_extend = nappend(list, list3);

  printf("list_extend = "); /* expect: List[1,2,3,1,2] */
  print_list( list_extend );

  printf("after use nappend\n"
         "list  = ");
  print_list( list ); /* expect: List[1,2,3] */

  printf("list3 = ");
  print_list( list3 ); /* expect: List[1,2] */
  printf("\n");

  // 10th
  printf("-10th-\n"
         "list          = ");
  print_list( list ); /* expect: List[1,2,3,1,2] */
    // do reverse
  Cons* list_reverse = reverse( list );
  printf("use reverse\n"
         "list_reverse  = ");
  print_list( list_reverse ); /* expect: List[2,1,3,2,1] */
  printf("list          = ");
  print_list( list ); /* expect: List[2,1,3,2,1] */
  printf("\n");

 // 11th
  printf("-11th-\n"
         "list          = ");
  print_list( list ); /* expect: List[1,2,3,1,2] */
    // do reverse
  Cons* list_nreverse = nreverse( list );
  printf("use nreverse\n"
         "list_nreverse = ");
  print_list( list_nreverse ); /* expect: List[2,1,3,2,1] */
  printf("list          = ");
  print_list( list ); /* expect: List[2,1,3,2,1] */
  printf("\n");
  test_LL();

  return 0;
}

�
/*
Local Variables:
compile-command: "gcc -Wall LL.c -o LL && ./LL"
End:
*/

Results

-1th-
List[1,2,3]

-2th-
Length of the list = 3

-3th-
first : 1
second: 2
third : 3
fourth : 0

-4th-
first : 1
second: 2
third : 3
fourth : 0

-5th-
same            : 1
diffenent length: 0
diffenent values: 0

-6th-
Looking for 2 in the list [1, 2, 3]
head: 2
tail: 0xde0158

-7th-
after copy
 orignal & copy : 1
after change the copy 
 orignal & copy : 0

-8th-
list  = List[1,2,3]
list3 = List[1,2]
use append to both
both  = List[1,2,3,1,2]
after use append
list  = List[1,2,3]
list3 = List[1,2]

-9th-
list  = List[1,2,3]
list3 = List[1,2]
use nappend to list_extend
list_extend = List[1,2,3,1,2]
after use nappend
list  = List[1,2,3,1,2]
list3 = List[1,2]

-10th-
list          = List[1,2,3,1,2]
use reverse
list_reverse  = List[2,1,3,2,1]
list          = List[1,2,3,1,2]

-11th-
list          = List[1,2,3,1,2]
use nreverse
list_nreverse = List[2,1,3,2,1]
list          = List[2,1,3,2,1]

List[]
List[10,20,30]
List[]
List[]
List[10]
List[]
List[10]
List[10]
List[10,20]
List[]
List[10]
List[10,20]
List[]
List[10]
List[10]
List[10,20]
List[]
List[10]
List[20,10]
List[]
List[10]
List[20,10]

Discussion

This lab was not difficult to follow and very straight forward. The main point of this lab is learning about the concept of link list and making condensed effective codes which are short, simple and easy to understand.

Only oneproblem I have got was using nappend having 'xs' as 'nil'

• first codes made

Cons* nappend(Cons* xs, Cons* ys) {
  Cons* both = copy_list(ys);
  nth_cons(length(xs)-1, xs) -> tail = both;
  return xs;
}

What the nappend fuction do
1. create 'both' list and copy the list from 'ys'
2. find the last list of 'xs' and change 'tail' from 'nil' to 'both'
3. retrun xs
but when 'xs' is 'nil', this function always return empty array

• Fix the error

 add special codes for when 'xs' equals to 'nil'
 When 'xs' is 'nil', copy 'both' to 'xs' and return xs

• fianl codes fixed

Cons* nappend(Cons* xs, Cons* ys) {
  Cons* both = copy_list(ys);
  if ( xs == nil ) {
	 xs = both;
	  return xs;
  }
  nth_cons(length(xs)-1, xs) -> tail = both;
  return xs;
}

• Even simple codes, using many test cases is a good way to avoid from bugs.