Please help! I need a solution for this question

This is a discussion on Please help! I need a solution for this question within the C Programming forums, part of the General Programming Boards category; Consider a singly-linked list of nodes, where each node contains an integer and a pointer. a)Write an ITERATIVE function that ...

  1. #1
    Registered User
    Join Date
    May 2007
    Posts
    20

    Question Please help! I need a solution for this question

    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

  2. #2
    Deathray Engineer MacGyver's Avatar
    Join Date
    Mar 2007
    Posts
    3,211
    Quote Originally Posted by lastrial View Post
    I cannot think of any way to do this without using a counter.....any help will be appreciated
    Hint: Boolean toggle.

  3. #3
    Registered User
    Join Date
    May 2007
    Posts
    20

    hmmmmm....

    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;
    }

  4. #4
    Fear the Reaper...
    Join Date
    Aug 2005
    Location
    Toronto, Ontario, Canada
    Posts
    625
    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 % 2;
         }
    
         return flag
    }
    Teacher: "You connect with Internet Explorer, but what is your browser? You know, Yahoo, Webcrawler...?" It's great to see the educational system moving in the right direction

  5. #5
    Woof, woof! zacs7's Avatar
    Join Date
    Mar 2007
    Location
    Australia
    Posts
    3,459
    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

  6. #6
    Registered User
    Join Date
    May 2007
    Posts
    20
    I am not supposed to use a counter and code shown above uses it.

  7. #7
    Fear the Reaper...
    Join Date
    Aug 2005
    Location
    Toronto, Ontario, Canada
    Posts
    625
    No it does not, flag is always either 0 or 1.
    Teacher: "You connect with Internet Explorer, but what is your browser? You know, Yahoo, Webcrawler...?" It's great to see the educational system moving in the right direction

  8. #8
    Registered User
    Join Date
    May 2007
    Posts
    20
    Oh so...using flag++ doesn't fall under using a counter huh.....thanks for clearing that up. Thanks very much happy reaper.
    Last edited by lastrial; 05-13-2007 at 03:52 PM.

  9. #9
    Deathray Engineer MacGyver's Avatar
    Join Date
    Mar 2007
    Posts
    3,211
    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.
    Last edited by MacGyver; 05-13-2007 at 03:57 PM.

  10. #10
    Registered User
    Join Date
    May 2007
    Posts
    20
    Thanks verymuch guys I followed both the solutions......using mod and triggering....

  11. #11
    Captain Crash brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,244
    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);
    }

  12. #12
    Deathray Engineer MacGyver's Avatar
    Join Date
    Mar 2007
    Posts
    3,211
    /* Must be called with is_even == 1 */
    Are you sure?

  13. #13
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,781
    Are you sure?
    Perhaps more accurately: must be called with is_even != 0
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  14. #14
    Captain Crash brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,244
    Quote Originally Posted by MacGyver View Post
    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
    Last edited by brewbuck; 05-17-2007 at 12:41 PM.

  15. #15
    Deathray Engineer MacGyver's Avatar
    Join Date
    Mar 2007
    Posts
    3,211
    I must be blind today. You're correct.

Page 1 of 2 12 LastLast
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. another do while question
    By kbpsu in forum C++ Programming
    Replies: 3
    Last Post: 03-23-2009, 12:14 PM
  2. anyone know the solution?
    By heeroyung in forum C Programming
    Replies: 15
    Last Post: 09-30-2005, 06:46 AM
  3. Question for Alternative Solution in Program
    By Beast() in forum C Programming
    Replies: 14
    Last Post: 06-22-2004, 06:52 PM
  4. Question...
    By TechWins in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 07-28-2003, 09:47 PM
  5. opengl DC question
    By SAMSAM in forum Game Programming
    Replies: 6
    Last Post: 02-26-2003, 08:22 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21