Please help! I need a solution for this question

**lastrial** · 05-12-2007

Consider a singly-linked list of nodes, where each node contains an integer and a pointer.

a)Write an ITERATIVE function that returns TRUE (1) if the list has an EVEN number of nodes; otherwise return FALSE (0). Code in the language of your choice and include the declaration of your data structure. The prototype in C is:

int even(node_ptr p)

b) [10 points] Repeat using RECURSION.

c) State which solution is better and give a brief justification.

Special Note: Using a counter is not allowed (NO CREDIT will be assigned).

I cannot think of any way to do this without using a counter.....any help will be appreciated

**MacGyver** · 05-12-2007

Originally Posted by lastrial

I cannot think of any way to do this without using a counter.....any help will be appreciated

Hint: Boolean toggle.

**lastrial** · 05-13-2007

This what I have come up with.....donno where I goofed up

Code:

int counters (LIST L){
	int flag = 0;
	position p;
	p = L->head->next;	
		if (p){
	                            flag = 0;
		         p = p->next;
		              if (p){
			flag = 1;
			p = p->next;
			}
		return flag = 0; // if 2		

}//end if 1

 return flag;
}

**Happy_Reaper** · 05-13-2007

You would need a while loop instead of that if block.

Here's some pseudo-code :

Code:

int counters(LIST l){
     flag = 0; //  0 == even, 1== odd
     if(l != null)
        flag = 1;  //  Has at least one element
    
     while(l has next)
     {
            l = l.next
            flag++;
            flag = flag &#37; 2;
     }

     return flag
}

**zacs7** · 05-13-2007

If you want extra marks, check if the result is odd or even with bitwise ops (cause its faster than mod')

http://en.allexperts.com/q/C-1040/Bit-Operators.htm

**lastrial** · 05-13-2007

I am not supposed to use a counter and code shown above uses it.

**Happy_Reaper** · 05-13-2007

No it does not, flag is always either 0 or 1.

**lastrial** · 05-13-2007

Oh so...using flag++ doesn't fall under using a counter huh.....thanks for clearing that up. Thanks very much happy reaper.

**MacGyver** · 05-13-2007

He's modifying the flag after he increments it so it'll always be 0 or 1. That's what a boolean flag is.

Technically, you could just do flag = !flag if you just wanted to set flag from true to false or false to true.

**lastrial** · 05-17-2007

Thanks verymuch guys I followed both the solutions......using mod and triggering....

**brewbuck** · 05-17-2007

What the heck are people using mod for?

Iterative:

Code:

int even_or_odd(nodeptr p)
{
    int is_even = 1;
    while(p)
    {
        is_even = !is_even;
        p = p->next;
    }
    return is_even;
}

Recursive:

Code:

/* Must be called with is_even == 1 */
int even_or_odd(nodeptr p, int is_even)
{
    if(!p) return is_even;
    return even_or_odd(p->next, !is_even);
}

**MacGyver** · 05-17-2007

/* Must be called with is_even == 1 */

Are you sure?

**laserlight** · 05-17-2007

Are you sure?

Perhaps more accurately: must be called with is_even != 0

**brewbuck** · 05-17-2007

Originally Posted by MacGyver

Are you sure?

I really meant what Laserlight said. Any non-zero value is fine. For that matter, calling it with zero would also be fine, but the sense of the return code would be reversed (i.e. it would check for oddness instead of evenness, thus the name of the function "even_or_odd")

EDIT: Furthermore, you could look at the comment as an interface specification instead of a reflection of the implementation. Maybe the implementation of even_or_odd() changes in the future so that it really DOES require 1 (and only 1). But I decided to assert this restriction early on

**MacGyver** · 05-17-2007

I must be blind today. You're correct.

Thread: Please help! I need a solution for this question

Thread Tools

Search Thread

Display

Please help! I need a solution for this question

hmmmmm....

Similar Threads

another do while question

anyone know the solution?

Question for Alternative Solution in Program

Question...

opengl DC question