compare backward ll ints

This is a discussion on compare backward ll ints within the C Programming forums, part of the General Programming Boards category; Mmm...well I had another thread working on trying to compare reversed ints, but I decided to wipe that and try ...

  1. #1
    Registered User
    Join Date
    Jan 2010
    Posts
    104

    compare backward ll ints

    Mmm...well I had another thread working on trying to compare reversed ints, but I decided to wipe that and try again

    i want to compare two linked lists, each storing a digit, that goes backwards

    for example, the numbers 127 and 436

    linked list a stores 7->2->1, and 6->3->4

    my whole method is finished except for the last part where the numbers are same length starting with same digit so the number would be

    5496 and 5724

    if they are stored backwards, how do i compare them? ive tried a multitude of different ways but they are failing because of pointer issues with linked lists =/

    this is the method if you don't get what i mean

    Code:
    //compares p and q; if p is smaller, then return -1; if q is smaller, return 1
    //return 0 if its exactly the same
    int compare(struct integer* p, struct integer* q) {
       int count=1, count2=1;
       struct integer *ptest=p, *qtest=q;
       while(ptest->next!=NULL) {
          ptest=ptest->next;
          count++;            
       }
       printf("count p= %d\n",count);
       while(qtest->next!=NULL) {
          qtest=qtest->next;
          count2++;            
       }
       //PTEST AND QTEST ARE CURRENTLY POINTING TO LAST DIGIT OF P AND Q
       printf("count q= %d\n",count2);
       if(count<count2) {
          printf("p is less than q; returning -1\n");
          return -1;
       }
       else if(count>count2) {
          printf("q is less than p; returning 1\n");
          return 1;  
       }
       else {
          printf("p=%d and q are equal length; no return yet\n",ptest->digit);
          if(ptest->digit<qtest->digit) {
             printf("returning -1\n");
             return -1;               
          }
          else if(ptest->digit>qtest->digit) {
             printf("returning 1\n");
             return 1;  
          }
          else {
             
          }
          return 0;
       }
    }
    Last edited by Soulzityr; 02-16-2010 at 03:51 PM.

  2. #2
    Registered User
    Join Date
    Feb 2010
    Posts
    26
    If you want to compare the values in reverse order it is better to use double linked list instead of
    single linked list.
    In double linked list we can have previous and next pointers.So using previous pointer we can take the values in the node in reverse order.

  3. #3
    Registered User
    Join Date
    Oct 2008
    Location
    TX
    Posts
    2,047
    Either use a doubly-linked list or rewrite compare() as a recursive function to traverse the call stack backwards.

  4. #4
    Registered User
    Join Date
    Feb 2010
    Posts
    36

    Doubly-Linked-List

    Your algorithm is correct.The best way to do that is following.


    - Create a doubly linked list.

    - Store the integers in the doubly linked list

    - Call the compare function with passing two values

    - If the first node value itself less than or greater than the second,then simply returns the value according to your information such as -1,if the first one is less than the second,1 if second is greater than the first and 0 if both are equal.

    - If the first node value of both numbers are equal,then pass the next node value to compare function recursively until all the digits are compared.

    - compare function is called recursively when both the values aren't equal.

  5. #5
    Registered User
    Join Date
    Oct 2008
    Location
    TX
    Posts
    2,047
    Quote Originally Posted by vivekraj View Post
    - Create a doubly linked list.

    - Store the integers in the doubly linked list

    - Call the compare function with passing two values

    - If the first node value itself less than or greater than the second,then simply returns the value according to your information such as -1,if the first one is less than the second,1 if second is greater than the first and 0 if both are equal.

    - If the first node value of both numbers are equal,then pass the next node value to compare function recursively until all the digits are compared.

    - compare function is called recursively when both the values aren't equal.
    IBTD, either use a doubly linked list or code compare() recursively.
    It's an either-or proposition, they don't complement each other.

  6. #6
    Registered User
    Join Date
    Jan 2010
    Posts
    412
    There's no need for a doubly-linked list or recursion. You can compare the numbers as they are and store the result of the previous digit in a temporary variable. Although a doubly-linked list might be more efficient I think.

  7. #7
    Registered User
    Join Date
    Oct 2008
    Location
    TX
    Posts
    2,047
    Quote Originally Posted by _Mike View Post
    There's no need for a doubly-linked list or recursion. You can compare the numbers as they are and store the result of the previous digit in a temporary variable. Although a doubly-linked list might be more efficient I think.
    That's the best approach if it were an open-ended problem; however, the OP is constrained to a singly linked list and only recursion can resolve whether one string of digits is greater/less than or equal to another.

  8. #8
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,311
    Quote Originally Posted by itCbitC
    That's the best approach if it were an open-ended problem; however, the OP is constrained to a singly linked list and only recursion can resolve whether one string of digits is greater/less than or equal to another.
    I have not written a proof of concept myself, but after _Mike posted that statement I wanted to refute it, yet it seems that the idea is workable.

    Basically, you can determine which is less than the other by iteration by comparing the length of the singly linked lists. Therefore, the problem lies with linked lists of equal length. However, by keeping track of the current comparison if it is not equal, one can eventually compare linked lists of equal length.
    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

  9. #9
    Registered User
    Join Date
    Oct 2008
    Location
    TX
    Posts
    2,047
    Quote Originally Posted by laserlight View Post
    Basically, you can determine which is less than the other by iteration by comparing the length of the singly linked lists. Therefore, the problem lies with linked lists of equal length. However, by keeping track of the current comparison if it is not equal, one can eventually compare linked lists of equal length.
    Greater / less than cases aren't a problem; but when same length nos. are nearly equal, say 5496 and 5492. What then?

  10. #10
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,311
    Quote Originally Posted by itCbitC
    Greater / less than cases aren't a problem; but when same length nos. are nearly equal, say 5496 and 5492. What then?
    Using the algorithm I hinted at, comparing the linked list obtained from 5496 and that obtained from 5492:
    1. Initially, result = 0
    2. Since 6 > 2, result = 1
    3. Since 9 == 9, no change to result
    4. Since 4 == 4, no change to result
    5. Since 5 == 5, no change to result
    6. Both linked lists end at this point, therefore they are of the same length. Thus, final result = 1.
    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

  11. #11
    Registered User
    Join Date
    Jan 2010
    Posts
    412
    Yes laserlight is right, what I meant was something like this.
    Code:
    int compare(const struct integer* l, const struct integer* r)
    {
    	/* comparison value */
    	int comp = 0;
    
    	/* test for NULL pointers */
    	if(!l && !r) return 0;
    	if(!l) return 1;
    	if(!r) return -1;
    
    	while(1)
    	{
    		/* if both numbers are of equal length,
    		 * return the comparison value */
    		if(!l && !r) return comp;
    
    		/* test the length of the numbers */
    		if(l->next && !r->next) return -1;
    		if(!l->next && r->next) return 1;
    
    		/* compare digits */
    		if(l->digit < r->digit) comp = 1;
    		else if(l->digit > r->digit) comp = -1;
    
    		/* move to next digit */
    		l = l->next;
    		r = r->next;
    	}
    }
    Return values are:
    0 : numbers are equal
    -1 : l is the greater number
    1 : r is the greater number

    I made the assumption that integer is
    Code:
    struct integer
    {
    	int digit;
    	struct integer* next;
    };
    And that the numbers don't contain any leading zeroes. Negative numbers are not handled because it's not clear from the OP how they are stored.

  12. #12
    Registered User
    Join Date
    Oct 2008
    Location
    TX
    Posts
    2,047
    Quote Originally Posted by laserlight View Post
    Using the algorithm I hinted at, comparing the linked list obtained from 5496 and that obtained from 5492:
    1. Initially, result = 0
    2. Since 6 > 2, result = 1
    3. Since 9 == 9, no change to result
    4. Since 4 == 4, no change to result
    5. Since 5 == 5, no change to result
    6. Both linked lists end at this point, therefore they are of the same length. Thus, final result = 1.
    Gotcha! and just in case you were wondering here's my 2c
    Code:
    int cmprec(sll *p, sll *q)
    {
        int rc;
    
        if (p->next && q->next) rc = cmprec(p->next, q->next);
        else if (p->next && !q->next) return 1;
        else if (!p->next && q->next) return -1;
        else return 0;
    
        if (!rc) {
            if (p->d > q->d) return 1;
            else if (p->d < q->d) return -1;
            else return 0;
        }
        return rc;
    }

  13. #13
    Registered User
    Join Date
    Oct 2008
    Location
    TX
    Posts
    2,047
    @_Mike:

    I tried your program and it works only for digit strings that are equal; and no I didn't use numbers that were negative or had leading zeroes.
    Last edited by itCbitC; 02-25-2010 at 11:44 PM.

  14. #14
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,311
    Quote Originally Posted by itCbitC
    I tried your program and it works only for digit strings that are equal; and no I didn't use numbers that were negative or had leading zeroes.
    Tracing _Mike's code by inspection, it looks like it should work for digit linked lists that are not equal. Perhaps you can try this instead:
    Code:
    int compare(const struct integer* lhs, const struct integer* rhs)
    {
        int result = 0;
    
        while (lhs && rhs)
        {
            if (lhs->digit < rhs->digit)
            {
                result = -1;
            }
            else if (lhs->digit > rhs->digit)
            {
                result = 1;
            }
            /* Ignore equal digits. */
    
            lhs = lhs->next;
            rhs = rhs->next;
        }
    
        if (lhs)
        {
            return 1;
        }
        else if (rhs)
        {
            return -1;
        }
        else
        {
            return result;
        }
    }
    Last edited by laserlight; 02-26-2010 at 03:38 AM.
    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

  15. #15
    Registered User
    Join Date
    Jan 2010
    Posts
    412
    Quote Originally Posted by itCbitC View Post
    @_Mike:

    I tried your program and it works only for digit strings that are equal; and no I didn't use numbers that were negative or had leading zeroes.
    Hmm that's weird.
    Could you please give me an example of numbers which doesn't work so I can verify if I messed something up?

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

Similar Threads

  1. Pointer Mayhem
    By thomas41546 in forum C Programming
    Replies: 3
    Last Post: 05-11-2008, 10:25 AM
  2. how to handle ints and strings when writing to file
    By agentsmith in forum C Programming
    Replies: 11
    Last Post: 04-23-2008, 04:44 AM
  3. Reading int's from file to array HELP plz
    By GARiMTO in forum C Programming
    Replies: 3
    Last Post: 12-14-2007, 05:12 AM
  4. reading 3 ints from one line, then 3 from another
    By Tokay in forum C++ Programming
    Replies: 10
    Last Post: 11-13-2005, 08:42 PM
  5. compare strings not working
    By gtriarhos in forum C Programming
    Replies: 7
    Last Post: 09-29-2005, 12:51 PM

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