Thread: i'm having trouble with linked lists

  1. #1
    Registered User
    Join Date
    Jul 2006
    Posts
    12

    i'm having trouble with linked lists

    Hey guys. this is my first post. i have to write a program that takes the input of two integers and then subtracts the second from the first and displays this difference. The catch is that the integers can be of any size. and btw...this program has to be written in C. I'm using linked lists to do this problem, and have assigned each digit to a node. The digits are being stored in backwards order. I'm pasting my code here to show what i have accomplished so far. Basically, the only thing i'm having problems with is subtracting the two integers after storing them. Any ideas or help will be appreciated.

    Code:
    #include <stdio.h>
    
    typedef struct node
    {
      int digit;
      struct node *next;
    } NODE;
    
    typedef NODE *PNODE;
    
    PNODE create_node(int);
    PNODE insert_node(PNODE, PNODE);
    void display_number(PNODE);
    void free_list(PNODE);
    
    int main(void)
    {
      PNODE pFirst = NULL, pSecond = NULL, /*pSum = NULL*/ pTemp;
      char c;
    
      /* Read input from user. */
      printf("Enter first positive integer: ");
      while ((c = getchar()) != '\n') {
        pTemp = create_node(c - '0');
        pFirst = insert_node(pFirst, pTemp);
      }
      printf("Enter second positive integer: ");
      while ((c = getchar()) != '\n') {
        pTemp = create_node(c - '0');
        pSecond = insert_node(pSecond, pTemp);
      }
    
      /* Display Numbers */
      printf("Number1 = ");
      display_number(pFirst);
      printf("\n");
      
      printf("Number2 = ");
      display_number(pSecond);
      printf("\n");
      
      /* Free memory. */
      free_list(pFirst);
      free_list(pSecond);
    
      return 0;
    }
    
    /* Creates a node for given data and return pointer to it. */
    PNODE create_node(int x)
    {
      PNODE pTemp;
    
      pTemp = (PNODE) malloc (sizeof(NODE));
      if (pTemp == NULL)
        {
          printf("Out of memory, could not store number!\n");
          exit(1);
        }
      else
        {
          pTemp->digit = x;
          pTemp->next = NULL;
        }
    
      return pTemp;
    }
    
    /* Inserts node pNew into pList at the start of the list. */
    PNODE insert_node(PNODE pList, PNODE pNew)
    {
      pNew->next = pList;
      return pNew;
    }
    
    /* Display the number represented by the list. */
    void display_number(PNODE pList)
    {
      while (pList != NULL)
        {
          putchar('0' + pList->digit);
          pList = pList->next;
        }
    
      return;
    }
    
    /* Free memory associated with list. */
    void free_list(PNODE pList)
    {
      PNODE pTemp;
    
      while (pList != NULL)
        {
          pTemp = pList->next;
          free(pList);
          pList = pTemp;
        }
    
      return;
    }

  2. #2
    Registered User Tonto's Avatar
    Join Date
    Jun 2005
    Location
    New York
    Posts
    1,465
    To print the numbers forwards instead of backwards, you can recursively transverse the list until you reach the end, and then once you reach the end, print digits and return. All the recursive calls return to where you print the digit, as it percolates up the function frames on the call stack.

    Code:
    void display_number(PNODE pList)
    {
    	if(pList->next != NULL)
    		display_number(pList->next);
    
    	putchar(pList->digit + '0');
    }
    I guess, to make the subtraction work, you have several options, depending on any requirements.

    Code:
    switch(waystodoit)
    {
        case 1: You can make a method to reverse the linked list
        case 2: You can make a method to append to the linked list
            You can use elementary style borrow and carry logic on the linked list
            Or you can make a method to convert the list to an integer, and use the subtraction operator
    }
    That was wierd.

  3. #3
    Registered User
    Join Date
    Jul 2006
    Posts
    12
    lol...well that was an interesting way of giving me options. as for the display of the numbers, i just displayed the two ints for making sure they were getting stored properly...the actual output doesnt require me to display the numbers again, so i dont think it matters if i store them backwards or forwards. also, you say that i can use a method to convert the list to an integer, how can i do that? is there a function for that?

    Thanks

  4. #4
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    Storing the way you do at the moment, with the units at the head of the list is fine.

    Think about how you do subraction on paper, say
    42
    18 -

    First step is 2 - 8

    Once you understand borrowing (school maths should have taught you that), the rest is just navigating both lists a pair of digits at a time, and figuring out what to do when you reach the end of one of the lists (like you assume the other is padded with zeros).
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  5. #5
    Registered User Tonto's Avatar
    Join Date
    Jun 2005
    Location
    New York
    Posts
    1,465
    You would have to make a method to do that. But it is not difficult, just like an atoi to operate on a linked list instead of a c string.

    Code:
    subroutine, taking head node as arg, returning int
    {
            int return = 0
            while its not the end of the linked list
            {
                    do something to return value to um, yeah.
            }
    }
    If you are stumped, you can browse around http://www.google.com/search?q=atoi.c for some real source for atoi, which is the function which would do this (some implementations just use another function called strtol to do the conversion, but you may find some good source code). Another thing you could do, is convert your linked list into a null-terminated string, by dynamically allocating bytes * nodes in list, and then copy the values of the nodes into the dynamically allocated array, and then do atoi on that.

  6. #6
    Registered User
    Join Date
    Jul 2006
    Posts
    12
    Quote Originally Posted by Salem
    Storing the way you do at the moment, with the units at the head of the list is fine.

    Think about how you do subraction on paper, say
    42
    18 -

    First step is 2 - 8

    Once you understand borrowing (school maths should have taught you that), the rest is just navigating both lists a pair of digits at a time, and figuring out what to do when you reach the end of one of the lists (like you assume the other is padded with zeros).

    This is what i had in mind when i was trying to make the subtraction function. but how do i implement the borrowing of a digit and do the subtraction digit by digit...i'm confused

  7. #7
    Registered User Tonto's Avatar
    Join Date
    Jun 2005
    Location
    New York
    Posts
    1,465
    Is this homework and do you have to do it that way? It's definitely an interesting and good programming puzzle, but it's not the easiest way to do it. But if you are set on it, then you should figure out exactly what steps you take when you do subtraction, and then how you can apply the logic you used in those steps to the numbers in your linked list.

  8. #8
    Registered User
    Join Date
    Jul 2006
    Posts
    12
    Quote Originally Posted by Tonto
    Is this homework and do you have to do it that way? It's definitely an interesting and good programming puzzle, but it's not the easiest way to do it. But if you are set on it, then you should figure out exactly what steps you take when you do subtraction, and then how you can apply the logic you used in those steps to the numbers in your linked list.

    yea...this is homework. there isnt any required way that i have to do it except for storing the integers using linked lists, i think the subtraction can be done any way i want. what would be an easier way?

  9. #9
    Registered User Osaou's Avatar
    Join Date
    Nov 2004
    Location
    Stockholm, Sweden
    Posts
    69
    Borrowing would be the simplest way in your case I believe. =)
    If you know the algorithm it should be pretty straight forward. What was it you had problem with when trying to implement it?

  10. #10
    Registered User
    Join Date
    Jul 2006
    Posts
    12
    how do i subtract each digit by the other digit...and although i get the concept of borrowing logically, i'm not able to figure out how to put it in the program

  11. #11
    Registered User
    Join Date
    Mar 2006
    Posts
    725
    Code:
    switch(waystodoit)
    {
        case 1:
    That should be case 0, unless waystodoit is of a weird type which starts values at 1. And you forgot the default:



    If you want to do operations starting from the end of the linked list, I suggest you implement a doubly-linked list to avoid wasting time traversing the list twice.
    Code:
    #include <stdio.h>
    
    void J(char*a){int f,i=0,c='1';for(;a[i]!='0';++i)if(i==81){
    puts(a);return;}for(;c<='9';++c){for(f=0;f<9;++f)if(a[i-i%27+i%9
    /3*3+f/3*9+f%3]==c||a[i%9+f*9]==c||a[i-i%9+f]==c)goto e;a[i]=c;J(a);a[i]
    ='0';e:;}}int main(int c,char**v){int t=0;if(c>1){for(;v[1][
    t];++t);if(t==81){J(v[1]);return 0;}}puts("sudoku [0-9]{81}");return 1;}

  12. #12
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    Frankly, I'm staggered that someone could come up with a pretty nice looking linked list code as in your first post, yet comes over all helpless when trying to do something like subtraction.

    Code:
    a = list1->digit;
    b = list2->digit;
    result = a - b;
    if ( result < 0 ) { result += 10 ; borrow = 1; }
    list3->digit = result;
    Now put that into list traversal (you already know how to do that).
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  13. #13
    Registered User Osaou's Avatar
    Join Date
    Nov 2004
    Location
    Stockholm, Sweden
    Posts
    69
    And yeah, don't forget to take into account the borrowing when subtracting.

  14. #14
    Registered User
    Join Date
    Jul 2006
    Posts
    12
    i have written a subtract function with the borrowing thing included, but right now it works only if both the integers entered have the same number of digits, and the first number is larger than the second number. how do i pad the number with lesser digits with 0's? and how do i check for which number is greater?

    Code:
    PNODE sub_numbers(PNODE pFirst, PNODE pSecond)  
    {  
      PNODE pTemp, pDiff = NULL;  
      int borrow = FALSE;  
      int cur_digit;  
      
      /* Loop through both numbers to sub at once. */  
      while ((pFirst != NULL) || (pSecond != NULL))  
        {  
          if(borrow)
         { 
              pFirst->digit--;  
              borrow = FALSE;  
         } 
     
          if (pFirst->digit < pSecond->digit)  
         {  
            cur_digit = ((pFirst->digit + 10) - pSecond->digit);  
            borrow = TRUE;  
         }  
          if(pFirst->digit > pSecond->digit)  
         {  
            cur_digit = pFirst->digit - pSecond->digit;  
         }   
          if(pFirst->digit == pSecond->digit)  
         {  
            cur_digit = pFirst->digit - pSecond->digit;  
         }  
         
          /* Insert new digit into diff*/  
          pTemp = create_node(cur_digit);  
          pDiff = insert_node(pDiff, pTemp);  
      
          /* Update each pointer to next digit. */  
          if (pFirst != NULL)  
         pFirst = pFirst->next;  
          if (pSecond != NULL)  
         pSecond = pSecond->next;  
        }  
      
      
      return pDiff;  
    }

  15. #15
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    Getting closer
    Code:
    while ( pFirst || pSecond ) {
      int first = pFirst ? pFirst->digit : 0;
      int second = pSecond ? pSecond->digit : 0;
      int result = first - second - borrow;
      borrow = 0;
      if ( result < 0 ) {
        result += 10;
        borrow = 1;
      }
      // allocate & insert result as now
      // advance to next pair, as now
    }
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 7
    Last Post: 06-16-2006, 09:23 PM
  2. Linked Lists 101
    By The Brain in forum C++ Programming
    Replies: 5
    Last Post: 07-24-2004, 04:32 PM
  3. Map file formats and linked lists
    By Spitball in forum Game Programming
    Replies: 2
    Last Post: 03-04-2004, 11:32 PM
  4. need help w/ linked lists
    By MKashlev in forum C++ Programming
    Replies: 11
    Last Post: 08-05-2002, 08:57 PM
  5. doubly linked lists
    By qwertiop in forum C++ Programming
    Replies: 3
    Last Post: 10-03-2001, 06:25 PM