为什么我的指针被锁定在一个范围内？

Question

pop函数好像总是段错误。

当我将指针变量传递给我前面的函数时，这些函数会相应地运行并且 "seem" 成功存储数据。但是，仔细检查后，数据丢失 and/or 损坏。即使是将 Stack 变量之一初始化为 NULL 这样简单的事情似乎也会失败。

我知道堆栈分配正确。我知道现在正在存储数据，但有一个警告。我必须将头指针传回我刚刚创建的堆栈（顺便说一句，我不喜欢这种方法）。

operators = stack_operators(Token *object);

这会导致更多问题和并发症，我宁愿避免。

if (NULL == (operator = stack_operators(&tree)))
{//this code works and succeeds
    puts("failed to stack operators.");
    puts("committing suicide now.");
    break;
}

print_stack(operator);//prints malloc()d stack to screen

同样的问题影响了我的 pop() 功能。具有讽刺意味的是，我成功释放了分配的 Stack 节点，但我的程序拒绝将下一个节点转移到前一个节点，因此出现 SIGSEGV 错误！这会导致发生双重释放或损坏错误。

我忽略了什么概念，将来如何避免这些类型的错误？

流行驱动程序

该程序重现了我的问题，而没有在第 143 行引起分段错误。第 136 和 140 行是发生数据丢失的地方。这发生在我的实际程序中，SIGSEGV 事件导致 Double Free SIGSEGV 事件。

#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#include <stdbool.h>

/* the Stack structure */
typedef struct stack_t {
    int object;
    struct stack_t * next;
} Stack;

typedef enum precedence_t { none, low, mid, hi } Precedence;  

//pop an item off of the stack
int pop(Stack * stack, int position);
//make a stack for the pop and push functions
Stack * stack_operators(const char ** tree, const int size);
Stack * stack_digits(const char ** tree, const int size);
//print tokens and stacks to screen
void print_token(const char ** tree, const int size);
void print_stack(Stack * stack);

//the token tree
const int SIZE = 4;

const char * data[5] = {
    "-",
    "123",
    "+",
    "54"
};

int main(void)
{
    Stack * digits = NULL, * operators = NULL;
    int value = 0;

    puts("Token List Value...");
    print_token(data, SIZE);

    puts("Converting token list to stack type...");
    puts("making digit stack...");
    digits = stack_digits(data, SIZE);

    puts("printing digit stack to screen:");
    print_stack(digits);

    puts("making operator stack...");
    operators = stack_operators(data, SIZE);

    puts("printing operator stack to screen:");
    print_stack(operators);

    puts("popping digits at position 0...");
    value = pop(digits, 0);
    printf("value = %d\n", value);

    puts("popping digits at position 0...");
    value = pop(digits, 0);
    printf("value = %d\n", value);

    puts("popping digits at position 0...");
    value = pop(digits, 0);//this is where the problem occurs
    printf("value = %d\n", value);

    return(0);
}

void print_token(const char ** tree, const int size)
{//print tokens to screen
    if (0 == size)
    {
        printf("the token tree has nothing to print.");
    }

    for (int count = 0; count < size; count++)
    {
        printf("token %0d: '%s'\n", (count + 1), tree[count]); 
    }

    putchar('\n');
}

void print_stack(Stack * stack)
{//print stack values to screen
    Stack * head = stack;

    if (NULL == stack)
    {
        puts("nothing in the stack to print.");
    }

    for (int i = 0; NULL != stack; i++)
    {
        if (ispunct(stack->object))
        {
            printf("stack: %d | value: '%c'\n", i, stack->object);
        }
        else
        {
            printf("stack: %d | value: '%d'\n", i, stack->object);
        }

        stack = stack->next;
    }

    stack = head;

    putchar('\n');
}

//Stack is the stack structure
//position is the location of the element to be popped
int pop(Stack * stack, const int position)
{//pop an object from the stack, free it, and return the its value
    int pos;
    int data = 0;
    Stack * previous = NULL;
    Stack * dump = NULL;
    Stack * head = stack;

    for (pos = 0; NULL != stack; pos++)
    {   
        if (pos != position)
        {
            previous = stack;
            stack = stack->next;
            continue;
        }

        data = stack->object;
        dump = stack;

        if (NULL == previous)
        {//first object on the stack
            stack = stack->next;//this line is supposed to cause a SEGFAULT
        }
        else
        {
            previous->next = stack->next; //stack does not retain pointer value
        }

        free(dump);//same stack is attempted to be freed, double free SIGSEGV

        break;      
    }

    if (0 < pos) { stack = head; }

    return data;
}

static Precedence token_precedence(char operator)
{//returns operator precedence
    switch (operator)
    {
        case '*':
        case '/':
            return mid; 
        case '+':
        case '-':
            return low;
        default:
            return none;
    }
}

//determines whether operator is unary or not
static bool isunary(const char ** token, int position)
{   //do NOT allow more than 2 consecutive + or - tokens
    //if there are, consider it to be a violation
    //if the last token is an operator, consider it to be a violation
    int previous = position - 1;
    Precedence precedence;

    if (0 == position)
    {
        if ('-' == token[position][0])
        {
            return true;
        }
    }

    if (previous <= 0) 
    {//too early to scan backwards
        return false;
    }

    precedence = token_precedence(token[previous][0]);

    if (low == precedence || mid == precedence)
    {
        if ('-' == token[position][0])
        {
            return true;
        }
    }

    return false;
}

//makes a stack for the given operators
Stack * stack_operators(const char ** tree, const int size)
{//initialize each stack with a value to be processed
    Stack * previous, * current, * head = NULL;

    for (int leaf = 0; leaf < size; leaf++)
    {
        if (!ispunct(tree[leaf][0]))
        {   
            continue;
        }

        if (isunary(tree, leaf))
        {
            continue;
        }

        if (NULL == (current = malloc(sizeof(Stack))))
        {//failed to allocate memory for the stack
            return NULL;
        }

        if (NULL == head)
        {//point to the head of the linked list
            head = current;
        }
        else
        {
            previous->next = current;
        }

        current->next = NULL;
        current->object = tree[leaf][0];
        previous = current;
    }

    return head;
}

//makes a stack for the given digits
Stack * stack_digits(const char ** tree, const int size)
{//initialize each stack with a value to be processed
    Stack * previous, * current, * head = NULL;

    for (int leaf = 0; leaf < size; leaf++)
    {
        if (ispunct(tree[leaf][0]))
        {
            if (!isunary(tree, leaf))
            {
                continue;
            }
        }

        if (NULL == (current = malloc(sizeof(Stack))))
        {//failed to allocate memory for the stack
            return NULL;
        }

        if (NULL == head)
        {
            head = current;
        }
        else
        {
            previous->next = current;
        }

        if (isunary(tree, leaf))
        {
            ++leaf;
            current->object = -(atoi(tree[leaf]));
        }
        else
        {
            current->object = atoi(tree[leaf]);
        }

        current->next = NULL;
        previous = current;
    }

    return head;
}

让我觉得这很奇怪的是，我的印象是指针应该允许我 "bend" 特定值的范围，以便我最终可以以某种方式改变或影响它。

下面的代码片段有趣的是 stack->next->object 不是空的，并且应该将下一个指针分配给当前堆栈项，但没有这样做。为什么会这样？

if (NULL == previous)
{//first object on the stack
    puts("in pop(), previous IS null...");
    if (NULL == stack->next)
    {
        puts("next stack IS null...");
    }
    else
    {
        printf("stack next object: %d\n", stack->next->object);
    }
    stack = stack->next;
}

这就是为什么程序员通常会使用类似结构类型的Item并将其包装在表示链表的Node类型结构中的原因吗？

Answer 1

    if (0 < pos) { stack = head; }

函数末尾的这一行实际上并没有做太多事情。您将指向数据的指针作为 stack 传递，但在 C 中，该指针本身是按值复制的。这意味着虽然数据指向同一个点，但指针本身是不同的。在函数的末尾，您修改了这个复制的值，当您从函数中 return 时，更改将丢失。如果要修改指针，就得传入一个指向那个指针的指针，比如Stack **stack，然后用

修改

    if (0 < pos) { *stack = head; }

请记住，C 中的所有内容都是按值传递的，因此如果您想修改任何内容（包括指针），请使用指向这些值的指针。

我不太确定这是否回答了您的问题，但该行似乎并没有太大作用。

Answer 2

鉴于您的 Stack 类型，您的 push 和 pop 函数可能是：

void push(Stack **s, int value)
{
    assert(s != 0);
    Stack *node = malloc(sizeof(*node));
    if (node == 0) { …handle memory allocation error… }
    node->next = *s;
    node->object = value;
    *s = node;
}

bool pop(Stack **s, int *value)
{
    assert(s != 0 && value != 0);
    if (*s == 0)
        return false;
    else
    {
        Stack *node = *s;
        *s = node->next;
        *value = node->object;
        free(node);
        return true;
    }
}

那么在main()中，你可以使用：

Stack *operands = 0;
push(&operands, 123);
push(&operands, 456);
push(&operands, 789);

int value;
while (pop(&operands, &value))
    printf("Popped: %d\n", value);
return(0);

将所有内容放入可执行文件中，我得到：

#include <assert.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>

/* For header */
typedef struct Stack Stack;

void push(Stack **s, int value);
bool pop(Stack **s, int *value);

/* Implementation only */
struct Stack
{
    int object;
    Stack *next;
};

void push(Stack **s, int value)
{
    assert(s != 0);
    Stack *node = malloc(sizeof(*node));
    if (node == 0)
    {
        fprintf(stderr, "Out of memory!\n");
        exit(1);
    }
    node->next = *s;
    node->object = value;
    *s = node;
}

bool pop(Stack **s, int *value)
{
    assert(s != 0 && value != 0);
    if (*s == 0)
        return false;
    else
    {
        Stack *node = *s;
        *s = node->next;
        *value = node->object;
        free(node);
        return true;
    }
}

int main(void)
{
    Stack *operands = 0;

    push(&operands, 123);
    push(&operands, 456);
    push(&operands, 789);

    int value;
    while (pop(&operands, &value))
        printf("Popped: %d\n", value);

    return(0);
}

运行的输出即：

Popped: 789
Popped: 456
Popped: 123

运行它在 valgrind 下也给了它一个干净的健康证明。还有其他处理内存不足情况的方法。

您可能还注意到描述堆栈接口的 header 不需要结构类型的详细信息；可以保持隐藏以供实施了解（仅）。这是一种封装形式。您可以将示例代码分成三个文件： stack.h 包含 typedef 和两个函数声明； stack.c 包括 stack.h 并且仅包含两个函数定义； main.c 包括 stack.h 并且仅包含 main() 函数。

为什么我的指针被锁定在一个范围内？

Why are my pointers locked within a scope?

c

pointers

memory-management

linked-list

data-structures