Mark: 1 revision(s)

2008-11-03T05:19:37Z

1 revision(s)

New page

<pre>
/*
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;

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 n = 0;
for( ; list != nil; list = list->tail ) {
n++;
}
return n;
}

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){
element_t element;
int l;
for(l=0; l<i; l++){
if (l != 0){
list = list->tail;
}
element = list->head;
}
return element;
}

int equal(Cons* list, Cons* list2){
int length_list = length(list);
int length_list2 = length(list2);
int l;

if (length_list != length_list2){
return 0;
}

for(l=0; l<length_list; l++){
if (l != 0){
list = list->tail;
list2 = list2->tail;
}
if (list->head != list2->head){
return 0;
}
}
return 1;
}

Cons* find(element_t element, Cons* list){
Cons* emptylist;
int length_list = length(list);
int l;

for(l=0; l<length_list; l++){
if (l != 0){
list = list->tail;
}
if (list->head == element){
return list;
}
}
return emptylist;
}

Cons* nappend(Cons* list, Cons* list2){

int length_list = length(list);
int l;

for(l=0; l<length_list; l++){
if (l != 0){
list = list->tail;
}
if (list->tail == nil){
list->tail = list2;
}
}
return list;
}

Cons* append(Cons* list, Cons* list2){

Cons* newlist;
int l;

newlist = list;
int length_list = length(newlist);

for(l=0; l<length_list; l++){
if (l != 0){
newlist = newlist->tail;
}
if (newlist->tail == nil){
newlist->tail = list2;
}
}
return list;
}

int main( ) {
Cons* list = cons(1,cons(2,cons(3,nil)));
Cons* list2 = cons(4,cons(5,cons(7,nil)));
Cons* list3 = cons(1, cons(2,cons(3,cons(4,nil))));
Cons* search;

print_list(list ); /* expect: List[1,2,3] */
printf("Length = %d\n", length( list )); /* should return 3 */
printf("%d\n",first(list));
printf("%d\n",second(list));
printf("%d\n", third(list));
printf("%d\n", fourth(list));
printf("%d\n", nth(1, list));
printf("%d\n", nth(2, list));
printf("%d\n", nth(0, list));

printf("\nEqual test:\n");
printf("%d\n", equal(list, list2));
printf("%d\n", equal(list, list3));
printf("%d\n", equal(list, list));
printf("%d\n", equal(list2, list3));

search = find(5, list2);
print_list( search );

return 0;
}

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( 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( 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] */

}

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

I hit a dead end at append and copy after about 1 and a half hours :(

SE250:lab-4:sbas046 - Revision history

Mark: 1 revision(s)