SE250:lab-4:bvic005

Lab 4

In this lab we had to impediment some functions to work with linked lists.

The first few functions posed no problems, so here is the code for them:

int length(Cons* list) {
	int length = 0;

	for( ; list != nil; list = list->tail ) {
		length++;
	}

	return length;
}

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) {
	int element;

	for (element = 0; element < i; element++) {
		list = list->tail;
	}

	return list->head;
}

The with the next function, it took me a short while to come up with the while loop to cope with different sized lists without calling the length function for each, but after that it was quite easy.

int equal(Cons* list1, Cons* list2) {

	while (!((list1 == nil) && (list2 == nil))) {
		if ( list1->head == list2->head ) {
			list1 = list1->tail;
			list2 = list2->tail;
		} else {
			return 0;
		}
	}

	return 1;
}

Find was implemented easily:

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

	return nil;
}

Copy_list was the first real hurdle. I quickly realized that it would be very easy if i had access to nappend, but as i had not written that as of yet(it was later in the worksheet), i decided to have a go at writing something relatively decent without using it.

After a bit of pondering, i implemented a version that seemed to work, apart from a bug in which if you passed it a nil list to copy, it would return a actual list, with 0 as the head, rather than just passing back THE nil list. I found that this was because of the necessity of processing the first element outside of the loop, which contains the nil-finding code. To get around this, i checked specifically for a nil list, and returned nil if it was found. Not the most elegant solution, but it worked.

Cons* copy_list(Cons* list) {
	Cons *newList, *currentElement, *previousElement;

	if (list == nil) {
		return list;
	} else {
		newList = cons(list->head, nil);
		list = list->tail;
		previousElement = newList;

		for ( ; list != nil; list = list->tail) {
			currentElement = cons(list->head, nil);
			previousElement->tail = currentElement;
			previousElement = currentElement;
		}

		return newList;
	}
}

Append was basically just copy_list, except that there where two lists to copy, and then they had to be linked.

Cons* append(Cons* list1, Cons* list2) {
	Cons *newList, *currentElement, *previousElement;

	if (list1 == nil) {
		return list2;
	} else {

		newList = cons(list1->head, nil);
		list1 = list1->tail;
		previousElement = newList;

		for ( ; list1 != nil; list1 = list1->tail) {
			currentElement = cons(list1->head, nil);
			previousElement->tail = currentElement;
			previousElement = currentElement;
		}

		for ( ; list2 != nil; list2 = list2->tail) {
			currentElement = cons(list2->head, nil);
			previousElement->tail = currentElement;
			previousElement = currentElement;
		}

		return newList;

	}

}

nappend was very easy to impilent. The only problem was passing in nil lists again, this time if the first list was a nil. This was fixed, once again, by the addition of a check for a nil first list.

Cons* nappend(Cons* list1, Cons* list2) {
	Cons *newList;

	if (list1 == nil) {
		return list2;
	} else {

		newList = list1;

		for ( ; list1->tail != nil; list1 = list1->tail);

		list1->tail = list2;

		return newList;

	}
}

Reverse was very easy, due to the fact that the cons function adds new elements to the start of the list:

Cons* reverse(Cons* list) {
	Cons* newList = nil;

	for ( ; list != nil; list = list->tail) {
		newList = cons(list->head, newList);
	}

	return newList;
}

nreverse was the hardest function by far. When i initially looked at it, i automatically assumed that you would have to start at the end, and swap the values with their opposite positions, which is impossible without creating any new elements, or at least copying the list into an array first. However, after a hint that you did not have to start at the ends and work your way in, rather that you could swap values closer together, i realised you could bubble your way through the list, moving entries to the start as you went(i would like to think i would have come up with this myself eventuallu, where it not for the hint :) ).

My initial implementation was slightly flawed, in that the last element in the reversed list ended up pointing to the second to last element, resulting in an infinite loop when you tried to print the list. This was fixed by forcing the last element to point to nil, as it should.

Cons* nreverse(Cons* list) {
	Cons *nextElement, *firstElement = list;

	list = list->tail;
	firstElement->tail = nil;

	while(list != nil) {
		nextElement = list->tail;

		list->tail = firstElement;
		firstElement = list;

		list = nextElement;
	}

	return firstElement;

}

Bvic005 00:43, 2 April 2008 (NZST)