Reversing an Integer String Using Linked List

[Firestrider]

Can someone help me on how exactly to do this? I'm trying to read an integer string and each "digit" in the string is put at the front of the linked list (i.e. reverse order). When I print it out I want it to reverse again. I know I'm not implementing it right because when I run it the program will output a lot of numbers.

struct integer 
{
   int digit;
   struct integer* next;
};

struct integer* read_integer(char* stringInt)
{
   int index;
   struct integer* current = NULL;
   
   current = (struct integer*)(malloc(sizeof(struct integer)));
   
   for (index = 0; index < strlen(stringInt); index++)
   {
      current->digit = stringInt[index] - '0';
      current->next = (struct integer*)(malloc(sizeof(struct integer)));
      current = current->next;
   }
   
   return current;
}

void print(struct integer* p)
{
   while (p != NULL)
   {
      printf("%d", p->digit);
      p = p->next;
   }

 

[D H]

The list doesn't terminate. You are not setting current->last for the last element (least significant digit) of the list.

Another problem: What happens if you pass the empty string?

 

[Firestrider]

Oh I thought the list (loop) would terminate when the "integer" string reaches the null character. How can I terminate the list?

I'm not even sure if it's being stored correctly, is it?

 

[D H]

You missed my point. You are not setting the next pointer in the last element in your constructed list. 'malloc' returns a block of memory that is not initialized. In other words, the returned memory might contain random garbage.

This function is small enough and simple enough that you should be able to execute it by hand. I suggest you do so. Try it with the strings "1" and "12". Some questions you should ask yourself:
- How many times should you be calling 'malloc' for these test cases?
- How many times are you calling 'malloc' for these test cases?
- Are you setting every element of every one of these allocated chunks of memory?

 

[Firestrider]

Can you please explain this:

struct integer* read_integer(char* stringInt)
{
   struct integer* pInt = (struct integer*)(malloc(sizeof(struct integer)));

   pInt->digit = stringInt[0] - '0';
   pInt->next = (struct integer*)(malloc(sizeof(struct integer)));
   pInt = pInt->next;
   pInt->digit = stringInt[1] - '0';
   pInt->next = NULL;
   
   return pInt;
}

How can I make it so it will print out the whole list instead of the current digit?

Sorry, I'm just trying to understand it.

 

[Coin]

Hi Firestrider... I think you were closer the first time. I see only two flaws in the read_integer implementation in your first post.

1. The pInt->next = NULL; from your second attempt needs to be copied into your first attempt, it should be right after the for loop.

2. In order for the caller of read_integer to do anything with the list that is returned, you need to return a pointer to the first node in your list. However, both your implementations of read_integer return the LAST node in your list.

Consider what "current" is-- it is a pointer into the list. Over the course of your function you keep moving "current" forward so that it is always pointing to the last item in the list. When the function is done you want to cap the last item in the list with a next=NULL, and return the first item in the list.

 

[Firestrider]

Thanks for the help Coin! It seems to read and print the right number now, except there is some random numbers after the string. It is probably happening because I'm not freeing or allocating memory somewhere but I can't see it.

struct integer* read_integer(char* stringInt)
{
   int index;
   struct integer* current = (struct integer*)(malloc(sizeof(struct integer)));
   struct integer* front = NULL;
   
   front = current;
   
   for (index = 0; index < strlen(stringInt); index++)
   {
      current->digit = stringInt[index] - '0';
      current->next = (struct integer*)(malloc(sizeof(struct integer)));
      current = current->next;
   }
   current->next = NULL;
   
   return front;
}

void print(struct integer* p)
{
   while (p != NULL)
   {
      printf("%d", p->digit);
      p = p->next;
   }
}

 

[Coin]

Well, actually looking at what you've got there, one more thing-- if you look carefully at the for loop, you will realize that you always malloc() one more "struct integer" than you use, and the final malloc'd "struct integer" has an uninitialized "digit" value. This will cause there to be exactly one "random" number (of potentially up to 10 digits) after the correct numbers by the time the program is finished is finished.

 

[D H]

Walking this through with the string "1":

1. The initializer for the declaration of "current" allocates an integer structure.
2. For index=0,
   • current->digit is set to 1. (Correct)
   • current->next is set to a newly allocated structure. (Incorrect: You've already allocated one, and one is all you need for a one digit number.)
3. current->digit is not set. (Incorrect: You should always set every element of memory allocated via malloc.)
4. current->next is set to NULL (Correct, but this may not be the place to do this.)

In general, you always allocate one too many structures. For an empty string you allocate one structure, for a one-digit string you allocate two, for a two digit string you allocate three, and so on.

 

[Firestrider]

Ok seems to be working now, and I have it read in the integer string in reverse. What I'm having trouble doing is printing it in reverse again. I know the front of the list is returned and I have to go to the back of the list and print from the back to the front. Any hints on how to do this:

struct integer* read_integer(char* stringInt)
{
   int index;
   struct integer* current = (struct integer*)(malloc(sizeof(struct integer)));
   struct integer* front = NULL;
   
   front = current;
   
   for (index = 0; index < strlen(stringInt); index++)
   {
      current->digit = (int)(malloc(sizeof(int)));
      current->digit = stringInt[strlen(stringInt) - index - 1] - '0';
      if (index + 1 < strlen(stringInt))
         current->next = (struct integer*)(malloc(sizeof(struct integer)));
      else 
         current->next = NULL;
      current = current->next;
   }
   
   return front;
}

void print(struct integer* p)
{
   while (p != NULL)
   {
      printf("%d", p->digit);
      p = p->next;
   }
}

 

[Coin]

If this is for a homework problem, is it not likely that your instructor simply expected you to construct the list backward in the first place? Constructing a list such that each new node is added at the front is actually probably even easier than constructing it such that each node is added at the back.

Alternate answer:

printInteger(struct integer *p) { if (p) { printInteger(p->next); printf("%d", p->digit); } }

...but, this is a really bad idea and will probably irritate your instructor also.

 

[Firestrider]

Argh, this is hard.

I can't tell if the node is being added to the front or the back of the list. I think this is how it needs to be set up:

                                       print
                         <--add node     v
[X|int_n]<--[ |int_2]<--[ |int_1]<--[ |int_0]

Is there an easy way to count the nodes for each list? Or do you have to have a loop and counter until the pointer is NULL, ex:

while (p != NULL)
    {
       p = p->next;
       p_size++;
    }

 

[Firestrider]

Ok I seemed to fix print() and read_integer().

I now am working on the add() function for two linked lists. The problems I'm having with it are listed on the top in comments. I know the problem originates on how the loop executes, but I'm not sure how I can change it.

// ! CRASHES IF FIRST OPERAND IS BIGGER IN LENGTH!
// ! DIGIT WILL NOT DROP DOWN IF SECOND OPERAND IS BIGGER IN LENGTH!
// ! WILL NOT CARRY 1 ON MOST SIGNIFICANT DIGIT !
struct integer* add(struct integer* p, struct integer* q)
{
   // Initialization
   int carry = 0;
   struct integer* current_p = p;
   struct integer* current_q = q;
   struct integer* current_result;
   struct integer* result = NULL;
   struct integer* last;
   
   // Loop until the first operand reaches a NULL node
   while (current_p != NULL)
   {
      // Create a new node current_result to store the sum of p and q
      current_result = (struct integer*)(malloc(sizeof(struct integer)));
      current_result->digit = (current_p->digit + current_q->digit + carry)%10;
      carry = (current_p->digit + current_q->digit + carry)/10;
      
      // If this is the first node, initialize result to point to it
      if (result == NULL)
         result = current_result;
      // Else, attach the last node of the list to current_result
      else
         last->next = current_result;
      
      // Go to the next nodes in p and q, reset last node of list
      current_p = current_p->next;
      current_q = current_q->next;
      last = current_result;
   }
   
   // Set the last pointer of last node of list to return to NULL
   if (p != NULL)
      current_result->next = NULL;
   
   // Return a pointer to this new list
   return result;
}