Adding values of two linked lists

[thomaselder84]

Hey everyone

I've got a link list filled with hexadecimal values. I call a method that allows the user to enter in hexadecimal values on a local link list. The numbers are added together. The result is stored on an additional local link list. Then, the native object link list connects its head and tail to it.

Problem I'm having is that the program crashes because of a memory read problem. I'm not sure if I end up with a dangling pointer or what. Please take a look and see if you can help.

Doing addition backwards, it would look something like this

48C5
923 <<<<<Does my code handle having a blank spot??
-------
DAF5

void LList::Addition(){

	LList Add;		//Local Object for elements to be added to     Native Object
	LList Result;   //Local Object for sum of Add elements and Native Object elements
	int num1;		//Decimal value of Native Object elements
	int num2;		//Decimal value of Add elements
	int carry;		//To be added to next set of values
	int sum;		//Result of addition
	element val;	//Hexadecimal value of sum
	
	listnode * temp1; 
	listnode * temp2;
	
	cout << "Enter hex to add: ";
	Add.ReadBackward();

	temp1 = head;	
	temp2 = Add.head;

	carry = 0;

//ARE THESE CONDITIONS CORRECT??
	while (temp1 != NULL || temp2 != NULL || carry != 0){
		
		num1 = AsciiConverter(temp1);	//Returns decimal value of hexadecimal
		num1 += carry;

		num2 = AsciiConverter(temp2);	//Returns decimal value of hexadecimal
		
		sum = (num1 + num2) % 16;		//Base-16 addition
		carry = (num1 + num2) / 16;

		//Convert back to ascii for hexadecimal character
		if (sum <= 9)
			val = sum + 48;
		else
			val = sum + 55;

		//Putting the hexadecimal characters on local link list
		Result.InsertTail(val);
		
		//Move to next element on link lists

//AT SOME POINT IN THE LOOP I THINK THIS IS WHERE I THINK THE PROBLEM IS. 
		temp1 = temp1->next;
		temp2 = temp2->next;

		}

	//Attach native object link list head and tail to local link list
	Steal(Result);

	}

int LList::AsciiConverter(listnode* node){

	int num;

	if (node != NULL)
		num = node->data;
	else
		num = 0;

	if (num >= 48 && num <= 57)
		num -= 48;
	else if (num >= 65 && num <= 70)
		num -= 55;
	else
		;

	return num;

	}

[fg109]

You are leaving out a lot of things that could be causing the problem. Have you tried using a debugger to narrow down the exact line of code which is causing the crash? Right now, it could be the lines you pointed out, but we don't know for sure.

while (temp1 != NULL || temp2 != NULL || carry != 0)

So your loop will still run if both temp1 == NULL and temp2 == NULL as long as carry != 0. That could be causing the problem, with you trying to do things with these pointers where they're not pointing at anything.

If that's not the problem, post the code for your Steal function.

[thomaselder84]

Let me try to explain my reasoning behind the while loop.

Addition from left to right

010110 carry
926 temp1
3149 + temp2
------------------
24001

In this example, temp1 reaches null, but there's still addition to do, temp2 reaches null, but there's still addition to do, then carry reaches 0. Exit loop. The way I have it setup might not work, but this is what I'm attempting to accomplish. Obviously there are a variety of list lengths the program could have to handle. In order for the program to know that the addition is complete, temp1 has to be null, temp2 has to be null, and carry has to be 0.

The Steal method was written in class and has been tested. That's not the problem.

[fg109]

From your code, I'm guessing that each node represents a single digit. Consider that you are trying to add two numbers, and one number is 1 digit longer than the other. Let's assume temp1 is the pointer for the list that holds the longer number.

Eventually, you'll have temp1 pointing at something, while temp2 is null.

		temp1 = temp1->next;
		temp2 = temp2->next;

In that case, what does the above code do? It reads the node pointed at by temp1, finds its next pointer, then copies it to temp1. That is fine.

But what about the next line? It tries to read the node pointed at by temp2, but temp2 is pointing at null! it cannot get the next pointer from that, so it is an illegal operation.

What you should is change the loop to while (temp1 != NULL && temp2 != NULL). After that loop, you should have two other loops while (temp1 != NULL) and while (temp2 != NULL). Only one of those later loops will run, and you'll just add the remaining digits of the longer number to result.

[thomaselder84]

Ok, I'll give it a shot and let you know how it goes. Thanks.

[thomaselder84]

That did it! Thank you so much. Great lesson learned. The only supplementation I had to make to your suggestion was to add this after the while loops.

if(carry != 0)
     Result.InsertTail(carry + 48);
else
     ;