2

I have a program that utilizes linked lists (as structs) to store integer elements (essentially on a stack). The problem is, when I insert integers into an array accessed via a pointer and try to print it, the numbers are not the integers that were entered (looks like a pointer, although not sure, when I try to dereference it, I get errors in compiling). New to C and this is for a class assignment, so looking more for explanations specifically on pointers and guidance as to what I may be doing wrong. I am attaching the code I've done. For reference, the default size per node is 5 integers.

What running my code looks like:

what running my code looks like

What it should look like:

what it should look like

My guess is that the problem relies within the push/pop/top methods, although I did have some luck with using pointers in the make_node method, although then I got segmentation errors in the rest of the methods.

Thanks!

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "int_stack.h"

/* Structure definitions from header file - all methods defined there as well.
struct is_node {
    int *contents;            Pointer  to  memory  for  storing  up to node_capacity  ints
                              (this  has a fixed size  and is  determined  at  stack  creation)
    int next_index;           Index  of the  next  open  position  in the  array of  contents; starts  at 0
    struct is_node *next;     Pointer  to  subsequent  node in list (or NULL)
};

struct int_stack {
    int size;              Number  of  elements  currently  in  stack 
    int node_capacity;     Max  elements  per  node
    struct is_node *head;     First  node  with  stack  contents; the  contents
                              may be empty , but  head  should  never  be NULL
};
*/

struct is_node *make_node(int node_capacity);

/*
 * Creates a stack, assigning appropriate variables.
 */
struct int_stack *make_stack(int node_capacity) {
    struct int_stack *stack = NULL;
    stack = malloc(sizeof(struct int_stack));
    if (stack == NULL) {
        fprintf(stderr, "Memory error!\n");
        exit(-1);
    }
    stack->size = 0;
    stack->node_capacity = node_capacity;
    stack->head = make_node(node_capacity);
    return stack;
}

/*
 * Cleans up all memory used by the given stack.
 */
void free_stack(struct int_stack *stk) {
    struct is_node *curnode = stk->head;
    while (curnode != NULL) {
        struct is_node *nextnode = curnode->next;
        free(curnode);
        curnode = nextnode;
    }
    free(stk);  
}

/*
 * Resets the stack, but allows it to still be used.
 */
void reset_stack(struct int_stack *stk) {
    if (stk != NULL) {
        struct is_node *curnode = stk->head;
        while (curnode != NULL) {
            struct is_node *nextnode = curnode->next;
            free(curnode);
            curnode = nextnode;
        }
        stk->size = 0;
        stk->head = make_node(stk->node_capacity);
    } else {
        printf("Error: Stack is NULL. Cannot reset it.");
    }
}

/*
 * Prints the stack. Contents delimited with [] if node is at capacity
 * or (] if not.  The values of each node are seperated by commas.
 */
void print_stack(struct int_stack *stk) {
    int i;
    struct is_node *curnode = stk->head;

    /* Count number of nodes */
    int node_count = 1;
    while (curnode->next != NULL) {
        ++node_count;
        curnode = curnode->next;
    }

    /* Walk to end of stack and insert */
    while (node_count > 0) {
        curnode = stk->head;
        for (i = 1; i < node_count; ++i) {
            curnode = curnode->next;
        }

        if (curnode->next_index >= stk->node_capacity) {
            printf("[");
        } else {
            printf("(");
        }
        for (i = curnode->next_index - 1; i >= 0; --i) {
            if (i == 0) {
                printf("%d]", curnode->contents[i]);
            } else {
                printf("%d,", curnode->contents[i]);
            }
        }

        --node_count;
    }
    printf("\n");
}

/*
 * Lets the user know if the stack is empty
 */
int is_empty(struct int_stack *stk) {
    if(stk->size == 0) {
        return 1;
    }
    return 0;
}

/*
 * Pushes an int onto the stack
 */
void push(struct int_stack *stk, int v) {
    /* Walk to end of stack and insert */
    struct is_node *curnode = stk->head;
    while (curnode->next != NULL) {
        curnode = curnode->next;
    }
    if(curnode->next_index >= stk->node_capacity) {
        struct is_node *new_node = make_node(stk->node_capacity);
        new_node->contents[new_node->next_index] = v;
        new_node->next_index += 1;
        curnode->next = new_node;
    } else {
        curnode->contents[curnode->next_index] = v;
        curnode->next_index = curnode->next_index + 1;
    }
    stk->size += 1;
}

/*
 * Pulls the first int on the stack off the stack
 */
int pop(struct int_stack *stk) {
    if (!is_empty(stk)) {
        int top;
        struct is_node *prevnode = stk->head;
        struct is_node *curnode = stk->head;
        struct is_node *nextnode = stk->head->next;
        while (nextnode != NULL) {
            if (nextnode->next != NULL) {
                prevnode = curnode;
            }
            curnode = nextnode;
            nextnode = curnode->next;
        }
        top = curnode->contents[curnode->next_index - 1];
        curnode->next_index = curnode->next_index - 1;
        if (curnode->next_index == 0) {
            free(curnode);
            curnode = NULL;
            prevnode->next = NULL;
        }
        stk->size -= 1;
        return top;
    }
    return -1;
}

/*
 * Returns the top value from the stack. 
 */
int top(struct int_stack *stk) {
    struct is_node *curnode = stk->head;
    while (curnode->next != NULL) {
        curnode = curnode->next;
    }
    return curnode->contents[curnode->next_index - 1];
}

/*
 * Helper method for creating nodes in the stack.
 */
struct is_node *make_node(int node_capacity) {
    struct is_node *node = malloc(sizeof(struct is_node));
    if (node == NULL) {
        fprintf(stderr, "Memory error!\n");
        exit(-1);
    }
    node->next = NULL;
    node->next_index = 0;
    int node_contents[node_capacity];
    node->contents = node_contents;
    return node;
}
1
  • Ayeeeee, Prof. Sauppe would be proud. Commented Oct 31, 2017 at 21:17

1 Answer 1

1

make_node() sets node->contents to a local variable that will go out of scope as soon as the function ends. If you use contents outside the function you'll have undefined behavior.

Sign up to request clarification or add additional context in comments.

3 Comments

That's what I was afraid of. Would node->contents = *node_contents; be correct for passing along the pointer to this or how would I do that? Still new to C and pointers. If I try that, I get an error: " warning: assignment makes pointer from integer without a cast" when compiling. I read something about this being trying to assign an integer to a pointer but I believe it's the other way around. Isn't just the variable declaration technically a pointer to it?
You need to make sure that contents actually points to a big enough block of memory. You need to malloc that somewhere. :pointer from integer" would normally be caused by char* p = some_fn_that_returns_an_int() - it hints that you may be using a function before you've declared it. If an answer helps you please upvote and/or accept it.
Oh, perfect! I was missing the malloc. Things seem to be working well now, just have to touch up a few other parts of the codes to fix unexpected returns. I upvoted but my rep isn't high enough to publically affect the score or something. Says it was recorded. Thanks again!

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.