C - Linked stack list
My goal with the following code was for the user to enter some integers, have these integers stored on the stack assigned to type nodes INT_NODE
, and then tie all those nodes together. Finally, I wanted to iterate over the list and print the item at each node (only the first 5 in the following code). However, when I entered some numbers, the program prints the first number I entered and then the last number I entered was repeated 4 times. For example, if I type 84 5 12 7 1 22 31[Enter]
and then click Ctrl+D
at the beginning of the next line to simulate EOF on this Mac, I get the following output; 84 31 31 31 31
... I cannot understand why this is being done.
I know that I could allocate nodes on the heap using malloc()
, and I already wrote a function for that. I'm just wondering if this can be done with a runtime stack.
In the following code, the type INT_NODE
is defined in the header "SortingAlgs.h"
as follows:
typedef struct INT_NODE {
int element;
struct INT_NODE *next;
} INT_NODE;
#include <stdio.h>
#include <stdlib.h>
#include "SortingAlgs.h"
int main(void) {
INT_NODE head = {-999999999};
int num;
INT_NODE *pCurrentNode = &head;
if (scanf("%d", &num) != EOF) {
head.element = num;
while (scanf("%d", &num) != EOF) {
INT_NODE newNode;
newNode.element = num;
newNode.next = NULL;
pCurrentNode->next = &newNode;
pCurrentNode = pCurrentNode->next;
}
}
int i;
for (pCurrentNode = &head, i = 0; i < 5;
pCurrentNode = pCurrentNode->next, i++)
printf("%d ", pCurrentNode->element);
printf("\n");
return 0;
}
source to share
To do this using a runtime stack, you can use one of the following values:
- Allocation of execution time across
alloca
. It's easy: just replacemalloc
withalloca
(and don't try to wrapalloca
in another function). However,alloca
this is not a standard feature. - A recursive function, where each level of recursion will contain a single list node (or a fixed number of list nodes). This has some serious limitations, but it technically meets your requirement to allocate all nodes on the stack.
- Preallocate a fixed number of nodes as a local array and hope that's enough for your list ... But I'm sure that's not what you meant.
What about it. What you have now is not viable and only leads to undefined behavior. Your list basically "consists" of INT_NODE
objects that have already expired. In practice, you tend to end up reusing the same memory location over and over again, effectively linking one node to itself.
Here's an example if implementation that keeps the entire list "on the stack" after a recursive approach. Of course, the list only exists as long as all recursive calls are "active". This limits the applicability of this method, but it uses
#include <stdlib.h>
#include <stdio.h>
typedef struct INT_NODE
{
int element;
struct INT_NODE *next;
} INT_NODE;
void print_list(const INT_NODE *head)
{
for (const INT_NODE *current = head; current != NULL; current = current->next)
printf("%d ", current->element);
printf("\n");
}
void build_list(INT_NODE *head, INT_NODE *last)
{
INT_NODE new = { 0 };
if (scanf("%d", &new.element) != 1)
{
print_list(head);
return;
}
if (head == NULL)
head = &new;
else
last->next = &new;
build_list(head, &new);
}
int main(void)
{
build_list(NULL, NULL);
}
source to share
I think the reason is variable scope. Enter 5, the program will allocate memory on the stack, but it will be returned. Enter 12, allocate the same memory, bring it back. so finally the next head pointer is the same memory, and the same next memory pointer on its own.
you can output more than 5. You might get 84 31 31 31 31 31 31 31 .....
source to share