I am very new and need some help with this code for college homework. I am trying to write the code for inserting a Node to the end of the list in C but something with creating the new node isn't working.
First, here is the code I received in the assignment:
typedef struct listNode {
int* dataPtr;
struct listNode* next;
}ListNode;
typedef struct list
{
ListNode* head;
ListNode* tail;
}List;
And:
List getList()
{
List res;
int size, num, i;
makeEmptyList(&res);
printf("Please enter the number of items to be entered:\n");
scanf("%d", &size);
printf("Please enter the numbers:\n");
for(i = 0; i < size; i++)
{
scanf("%d", &num);
insertDataToEndList(&res, num);
}
return res;
}
void main()
{
List lst1, lst2, mergedList;
lst1 = getList();
lst2 = getList();
mergedList = merge(lst1,lst2);
printf("Merged list:\n");
printList(&mergedList);
freeList(&lst1);
freeList(&lst2);
freeList(&mergedList);
}
And here is my attempt at writing the code for insertDataToEndList
:
// Add Node to end list
void insertDataToEndList(List* lst, int data)
{
ListNode* newTail;
newTail = createNewListNode(&data, NULL);
insertNodeToEndList(lst, newTail);
}
ListNode* createNewListNode(int* data, ListNode* next)
{
ListNode* res;
res = (ListNode*)malloc(sizeof(ListNode));
res->dataPtr = data;
res->next = next;
return res;
}
void insertNodeToEndList(List* lst, ListNode* tail)
{
if (isEmptyList(lst) == true)
lst->head = lst->tail = tail;
else
{
lst->tail->next = tail;
lst->tail = tail;
}
tail->next = NULL;
}
The problem is that when I print the two lists that have been input, the printed values are not at all what I had input.
Since the data
parameter of the insertDataToEndList
function is allocated on the stack, its address is no longer referencing allocated memory once that function returns. Yet you've saved this address in res->dataPtr = data;
. This will lead to undefined behaviour when you'll read the memory pointed to by that dataPtr
(e.g. when later you print that list or do the merge).
So don't use &data
. Instead pass data
to insertDataToEndList
with this call:
newTail = createNewListNode(data, NULL);
And then change insertDataToEndList
to fix this bug:
ListNode* createNewListNode(int data, ListNode* next) // First param is int
{
ListNode* res = malloc(sizeof(*res));
res->dataPtr = malloc(sizeof(int)); // Allocate the memory for the int
(*res->dataPtr) = data; // Copy the int
res->next = next;
return res;
}
Some other remarks:
Don't compare the result of isEmpty(lst)
with true
. Just do:
if (isEmptyList(lst))
Make sure you declare functions before you call them. So unless you had already declared the functions, you should move the insertDataToEndList
function definition below the other two functions it depends on.
The code you received shows several bad practices, and makes one doubt about the quality of the course material you are looking at. For instance:
void main()
is wrong, and like a comment says, it's "...an indication that you're using a textbook written by someone who doesn't know the C language very well.".freeList
function takes List*
argument, which suggests that the memory allocated for the list (not only its nodes) should be freed, yet this makes no sense, since the main
function has declared them as List
variables, so free
should not be called on the list itself. It would be more consistent if the involved lists would all be allocated on the heap.int
values in dynamically allocated memory for one int, is useless and a bad decision.