Printing removes the value from my linked list.
As part of the assignment, I need to write two functions:
- a function that adds two natural numbers, represented as a linked list
- functions that print a number represented in the same way.
for some reason both functions work just fine, but when I try to use the print function as a result of the sum function, it changes the value of the sum at the beginning of the print function and prints Invalid value. when I use printf to print the same value in the master, no problem. my code is detailed below. any ideas?
void main()
{
int a[1] = { 1 },
b[1] = { 2 };
int * *pa, **pb;
List lst1, lst2;
List sum;
pa = (int * *) malloc(sizeof(int * )); * pa = &a[0];
pb = (int * *) malloc(sizeof(int * )); * pb = &b[0];
lst1 = arrToList(pa, 1);
lst2 = arrToList(pb, 1);
addNumbers(lst1, lst2, &sum);
//printf("%d\n",*(sum.head->dataPtr));
printNumber(sum);
}
//a function that recieves a number represented ad a list and prints it
void printNumber(List num)
{
ListNode * curr;
int currData,
i,
number;
if (isEmptyList(num) == TRUE)
printf("the input was an empty list, nothing to print");
else
{
i = 0;
number = 0;
curr = num.head;
while (curr != NULL)
{
currData = *(curr - >dataPtr);
number = number + currData * ((int) pow(10, i));
curr = curr - >next;
i++;
}
printf("%d \n", number);
}
}
// a function that sums in list
// representation two numbers,
// each represented as a list
void addNumbers(List n1, List n2, List * sum)
{
ListNode * currN1;
ListNode * currN2;
ListNode * currSum;
int currN1N2Sum; //stores the sum of the current digits in n1 and n2
int carrier,
prevCarrier; //current and previous carriers that carries +1 to the
next digit of sum
if the lst sum was bigger then 9
if ((isEmptyList(n1) == TRUE) || (isEmptyList(n2) == TRUE))
printf("bad input =(");
else
{
currN1 = n1.head;
currN2 = n2.head; * sum = createEmptyList();
carrier = 0;
prevCarrier = 0;
while ((currN1 != NULL) && (currN2 != NULL))
{
currN1N2Sum = *(currN1->dataPtr) + *(currN2->dataPtr) + prevCarrier;
if (currN1N2Sum > 9)
{
carrier = 1;
currN1N2Sum = currN1N2Sum - 10;
}
currSum = creatNewListNode( & currN1N2Sum, NULL);
insertNodeToEnd(sum, currSum);
prevCarrier = carrier;
carrier = 0;
currN1 = currN1 - >next;
currN2 = currN2 - >next;
} //while ((currL1!=NULL)&&(currL2!=NULL))
while (currN1 != NULL)
{
currN1N2Sum = *(currN1 - >dataPtr) + prevCarrier;
currN1 = currN1 - >next;
if (prevCarrier != 0) prevCarrier = 0;
}
while (currN2 != NULL)
{
currN1N2Sum = *(currN2 - >dataPtr) + prevCarrier;
currN2 = currN2 - >next;
if (prevCarrier != 0) prevCarrier = 0;
}
} // ! ((isEmptyList(n1)==TRUE)||(isEmptyList(n2)==TRUE))
}
here is the rest of the code:
typedef struct listNode{
int* dataPtr;
struct listNode* next;
} ListNode;
typedef struct list
{
ListNode* head;
ListNode* tail;
} List;
List createEmptyList()//creates and returns an empty linked list
{
List res;
res.head = res.tail = NULL;
return res;
}
Bool isEmptyList ( List lst )//checks if a given list is empty or not
{
if (lst.head == NULL && lst.tail == NULL)
return TRUE;
else
return FALSE;
}
void insertDataToEnd ( List * lst, int *dataPtr ) //inserts new data to the end of an existing linked list
{
ListNode * newTail;
newTail = creatNewListNode ( dataPtr, NULL );
insertNodeToEnd(lst,newTail);
}
void insertNodeToEnd ( List * lst, ListNode * newTail )//insert an existing node to an existing linked list
{
if (isEmptyList(*lst) == TRUE )
insertNodeToStart ( lst,newTail );
else
{
(*lst).tail -> next = newTail;
newTail->next = NULL;
(*lst).tail = newTail;
}
}
ListNode * creatNewListNode ( int * dataPtr, ListNode * next )//inserts new node in an existing linked list
{
ListNode * res;
res = (ListNode *) malloc (sizeof(ListNode));
res -> dataPtr = dataPtr;
res -> next = next;
return res;
}
void insertNodeToStart ( List * lst, ListNode * newHead )//inserts node to the begining of a given linked list
{
if ( isEmptyList( *lst ) == TRUE )
{
(*lst).head = newHead;
(*lst).tail = newHead;
newHead -> next = NULL;
}
else
{
newHead -> next = (*lst).head;
(*lst).head = newHead;
}
}
a source to share
Error in addNumbers function. When you add a node to hold the sum, you are passing a pointer to currN1N2Sum, which is a local variable (stored on the stack). When the addNumbers function completes, the local variable storage is released. The value found at this location will remain unchanged and appear to be valid until the store is reused.
This is why you got the impression that the addNumbers function is correct. When you call the printNumber function, the store is overwritten and you can find a different value.
This explains your mistake.
There is another problem with addNumbers. When you try to add two-digit numbers, the contents of currN1N2Sum will be overwritten with the new value.
What you need to do is allocate a buffer (malloc) and store the value contained in currN1N2Sum in it. Pass a pointer to the buffer to the new node.
By the way: you can change (* lst) .head in lst-> head. This will make your code more readable.
a source to share
We need to see some more code: how do you define the data structure for storing nodes, how to add nodes, etc.
The next line is suspicious:
number=number+currData*((int)pow(10,i));
Let's say you have 123 stored as 1, 2 and 3 nodes:
number = 0;
number = 0 + 1 * 1 = 1;
number = 1 + 2 * 10 = 21;
number = 21 + 3 * 100 = 321;
But if you store as 3, 2 and 1 node, you get:
number = 0;
number = 0 + 3 * 1 = 3;
number = 3 + 2 * 10 = 23;
number = 23 + 1 * 100 = 123;
It's your problem?
a source to share
I think you might be confusing things with pointer-wise ... The way you distribute the "sum" list in addNumbers seems very, very strange. (And I wouldn't be surprised if it breaks things ...)
Try to make these changes:
Basically:
List *sum;
<...>
addNumbers(lst1,lst2,sum); //Note the absence of the reference operator &
printNumbers(*sum);
(Alternatively, change printNumbers to accept (List *) instead of (List)).
Hope this helped XD
EDIT:
Try allocating "sum" before calling addNumbers ().
lst1 = arrToList(pa, 1);
lst2 = arrToList(pb, 1);
sum = createEmptyList();
I still think your data structures are a little weird: S
a source to share
You have a problem with createEmptyList. you declare there a list named res and return a structure, but the moment this function returns that structure is no longer valid. try using malloc (for struct) and then return a pointer to the caller. You use this function at the beginning with * sum.
This is a similar error that chmike found so that you better fix both.
a source to share