таНоса терпит неудачу Катастрофический

Question

Я пытаюсь реализовать очереди в С. Coming из Java и других управляемых языков, я действительно борюсь с управлением памятью. Вот enqueue() функция:

int enqueue(Queue q, int value) { 

    Node newNode = malloc(sizeof(Node)); 
    /*newNode->value = value; 

    if (q->size == 0) 
     q->head = newNode; 
    else 
     q->head->next = &newNode; 

    q->size++;*/ 
} 

Я получаю эту ошибку:

malloc.c:3096: sYSMALLOc: Assertion `(old_top == (((mbinptr) (((char *) &((av)->bins[((1) - 1) * 2])) - __builtin_offsetof (struct malloc_chunk, fd)))) && old_size == 0) || ((unsigned long) (old_size) >= (unsigned long)((((__builtin_offsetof (struct malloc_chunk, fd_nextsize))+((2 * (sizeof(size_t))) - 1)) & ~((2 * (sizeof(size_t))) - 1))) && ((old_top)->size & 0x1) && ((unsigned long)old_end & pagemask) == 0)' failed. 

FWIW, вот остальная часть кода (это даже не так ли?):

typedef struct NodeStruct *Node; 
struct NodeStruct { 
    Node* prev; 
    Node* next; 
    int value; 
}; 

typedef struct QueueStruct *Queue; 
struct QueueStruct { 
    Node* head; 
    Node* tail; 
    int size; 
    int capacity; 
}; 

Queue newQueue(int size) { 
    Queue q = malloc(sizeof(Queue)); 

    q->capacity = size; 
    q->size = 0; 
    q->head = NULL; 
    q->tail = NULL; 

    return q; 
} 

void printQueue(Queue q) { 
    printf("Queue of size %d, capacity %d", q->size, q->capacity); 
}  

int main() { 
    Queue myQ = newQueue(10); 

    // this seems to work 
    printQueue(myQ); 
    // epic fail 
    enqueue(myQ, 5); 

    return 0; 
} 

Почему это происходит?

Answer 1

Следующая строка, вероятно, дает вам горе:

Node newNode = malloc(sizeof(Node)); 

Node является тип указателя, так что вы только выделить достаточно места для хранения указателя, а не весь NodeStruct. Я думаю, что вы хотите сделать, это:

Node newNode = malloc(sizeof(*newNode)); 

или

Node newNode = malloc(sizeof(NodeStruct)); 

Та же проблема существует для Queue, вы только выделенное пространство для хранения указателя, а не QueueStruct. Что-то еще, что я только что заметил, заключается в том, что в вашихи QueueStruct вы используете тип Node*, который на самом деле NodeStruct **, что, вероятно, не то, что вы хотите, так как Node уже указатель.

Answer 2

вы намолочено ваша куча

если вы на использование Linux электрический забор или Valgrind, чтобы выяснить, где вы пошли неправильно

редактировать: Вы имеете в виду

Queue q = malloc(sizeof(QueueStruct)); 

и то же самое для узла

Node n = malloc(sizeof(NodeStruct)); 

, и я согласен с другими - его очень в заблуждение называть указатель на NodeStruct узел. Лучше назвать его NodePtr или PNode и вызвать узел структуры.

Answer 3

Это часто считается плохим стилем в C, чтобы скрыть указатель в пределах typedef. Это потому, что вы нужно знать, что что-то является указателем его правильно использовать, в любом случае. (Например, даже непрозрачный тип FILE в стандартной библиотеке используется и пропускают вокруг как FILE *).

Это, кажется, привело вас в заблуждение - например, ваши next и prev членов на самом деле являются указателями на указатели, что на самом деле не так, как вы хотите. Я предлагаю:

typedef struct NodeStruct Node; 
typedef struct QueueStruct Queue; 

struct NodeStruct { 
    Node *prev; 
    Node *next; 
    int value; 
}; 

struct QueueStruct { 
    Node *head; 
    Node *tail; 
    int size; 
    int capacity; 
}; 

Queue *newQueue(int size) { 
    Queue *q = malloc(sizeof(Queue)); 

    q->capacity = size; 
    q->size = 0; 
    q->head = NULL; 
    q->tail = NULL; 

    return q; 
} 

int enqueue(Queue *q, int value) { 

    Node *newNode = malloc(sizeof(Node)); 

    newNode->value = value; 
    newNode->next = NULL; 

    if (q->size == 0) 
    { 
     newNode->prev = NULL; 
     q->tail = q->head = newNode; 
    } 
    else 
    { 
     newNode->prev = q->tail; 
     q->tail->next = newNode; 
     q->tail = newNode; 
    } 

    q->size++; 
    return 0; 
} 

void printQueue(Queue *q) { 
    printf("Queue of size %d, capacity %d\n", q->size, q->capacity); 
} 

int main() { 
    Queue *myQ = newQueue(10); 

    printQueue(myQ); 
    enqueue(myQ, 5); 

    return 0; 
}