SE250:lab-4:dcho040
Jump to navigation
Jump to search
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.