Mark: 2 revision(s)

2008-11-03T05:19:36Z

2 revision(s)

New page

Lab 4 (Linked List (single))

--------------------------------------------------------------------------------------------------------------------

Task One: function int Length(cons*)

This function was verry hard for me (as I have missed the last four lectures : /, but after a nice spell on
wikipedia and a minute of tutorial help I was on my way (and 20 minutes trying to understand what a linked list was
:P) The linked lists once I understood them fell into place, and I stole large sections of the code from the already
existing print_list function in the file. My final code was this

int length(Cons* list ) { /* Hopefully works (Returns list length) */
int counter = 0;

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

It worked well, pleased with it and now I understand what a linked list is, I can move onto the rest of the tasks...

--------------------------------------------------------------------------------------------------------------------

Task Two: element_t first(Cons*) & 2nd & 3rd & 4th...

At first view it looked alot more logical to do a element nth than 4 functions to me but hay, thats the task, ironic
that the verry next task was a element nth but hay, such is life...

Anyhow I did my code (it was beutiful cleanly using 1/2 a screen of if statements to check for nil in a loop and if
a nil was found putting 0 in the return veriable...) then I was told that the code already converted nil to 0 and I
should delete most of the code, my if statements, my veriables... it was a sad moment :p but still worked like a
charm with the fat cut out... guess I should read the code more before I start next time huh

element_t first(Cons* list) { /* Hopefully gives the first element */

return list->head;
}

element_t second(Cons* list) { /* Hopefully gives the first element */
int counter;

for( counter = 1; counter != 2; counter++ ) {
list = list->tail;
}

return list->head;
}

This is my optomised code.

--------------------------------------------------------------------------------------------------------------------

Task Three: element_t nth(Cons*)

Well this was ALWAYS gona follow on behind the 4 function mamoth that was task two, but required one or two tweeks
and a additional imput veriable and presto, finshed... no big deal here.

element_t nth(int i, Cons* list) { /* Hopefully gives the first element */
int counter;

for( counter = 1; counter != i; counter++ ) {
list = list->tail;
}

return list->head;
}

There is nothing buch to say about this one, its task two with a different flavor...

--------------------------------------------------------------------------------------------------------------------

Task Four: Check Lists are Equal

This task just involved steeling my code from task one, with one minor complication... WTF do you do to optomise the
nil check...

int equal(Cons* list1, Cons* list2) { /* Hopefully works (Returns list length) */

for( ; (list1 != nil); list1 = list1->tail ) {
if (( list1->head != list2->head )) {
return 0;
}
list2 = list2->tail;
}
return 1;
}

This code is wrong, I knew it was wrong and I knew 100 ways to fix it... but none of them would fix it nicely...
You see it all works well if list1 and list2 are the same length... but what if list1 is longer or shorter than
list2?!?!? I can put in long winded if statements etc to check both are not at a nul value... but that would take
forever to wright (at least a minute!!!) and would slow the program... and that will NOT do!

So I just went...

int equal(Cons* list1, Cons* list2) { /* Hopefully works (Returns list length) */

for( ; (list1 != nil) | (list2 != nil); list1 = list1->tail ) {
if (( list1->head != list2->head )) {
return 0;
}
list2 = list2->tail;
}
return 1;
}

The key difference is in the for statement end check, (list1 != nil) | (list2 != nil) as apposed to (list1 != nil)
thus moving on if BOTH are not at an end, therefore hitting an inevitable difference in the element values (assuming
the list with extra elements has values put into the head element) not a verry big assumption in my opinion...

If the assumption proves false then it will either pleasntly reach the end with both the head value and the (my list
is already finshed I DONT HAVE A HEAD) value being equal and finsh or brake, im not sure which...
As it depends on what happens if you try to run on past the last value of a list->foot, what happens when you run
past that all important nil value? does it sit on nil or brake..? havent given it much thought though I think ill
ask.

--------------------------------------------------------------------------------------------------------------------

Task Five: Not completed, Been here for 3 hours so far and calling it quits (moral of the story dont miss a weaks
lectures and expect not to fall behind : /

Edit, space every CODE line not evey non code line... that wasted a good 10 minutes o_0

SE250:lab-4:mspe044 - Revision history

Mark: 2 revision(s)