Нарушение прав записи (@ 0xCDCDCDCD) при переносе значений в начало очереди (связанный список)

Question

Я не уверен, почему, но когда код достигает queue->tail->next = newLink; в

void listQueueAddBack (struct Queue* queue, TYPE value) {
    /* FIXME: You will write this function */
    assert (queue != 0);
    struct Link* newLink = (struct Link*) malloc (sizeof (struct Link));
    assert (newLink != NULL);
    newLink->value = value;
    queue->tail->next = newLink;
    queue->tail = newLink;
}

, я получаю нарушение прав записи (адрес 0xCDCDCDCD).Я случайно передал нулевой указатель?Я все еще немного новичок в C, так что это опыт обучения для меня.

Я также возился с listQueueIsEmpty, так как у него было нарушение прав чтения, но я, кажется, прошел через это,Теперь я нахожусь в действительной части толчка.

Я не уверен, что это слишком много, но я не очень много знаю о том, что вызывает это, так что вот все полезные биты кодафайл.Я не хочу, чтобы другие делали мою домашнюю работу за меня, но если есть какие-то очень большие ошибки в коде, пожалуйста, дайте мне знать, так как это помогает мне учиться при работе с будущими проектами на Си.Я попытался свернуть это немного, поэтому никто не должен делать 100-метровую прокрутку, чтобы добраться до дна (это не слишком долго, но все же)

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

#ifndef TYPE
#define TYPE int
#endif

// Single link
struct Link {
    TYPE value;
    struct Link* next;
};

// Single linked list with head and tail pointers
struct Queue {
    struct Link* head;
    struct Link* tail;
};

// Stack with two Queue instances
struct Stack {
    struct Queue* q1;
    struct Queue* q2;
};

/**
    Internal func allocates the queue's sentinel. Sets sentinels' next to null,
    and queue's head and tail to the sentinel.
    param:  queue   struct LinkedList ptr
    pre:    queue is not null
    post:   queue sentinel not null
            sentinel next points to null
            head points to sentinel (always)
            tail points to sentinel (always point to last link unless empty)
 */
void listQueueInit(struct Queue* queue) 
{
    /* FIXME: You will write this function */
    assert(queue != 0);

    struct Link* sentinel = (struct Link*)malloc (sizeof (struct Link));
    assert (sentinel != 0);

    sentinel->next = 0;
    queue->head = sentinel;
    queue->tail = sentinel;
}

/**
    Allocates and initializes a queue.
    pre:    none
    post:   memory allocated for new struct Queue ptr
            queue init (call to _initQueue func)
    return: queue
 */
struct Queue* listQueueCreate() 
{

     /* FIXME: You will write this function */
    struct Queue* queue = (struct Queue*) malloc (sizeof (struct Queue));
    listQueueInit (queue);
    return queue;
}

/**
    Adds a new link with the given value to the back of the queue.
    param:  queue   struct Queue ptr
    param:  value   TYPE
    pre:    queue is not null
    post:   link is created with given value 
            link is added after the current last link (pointed to by queue tail)
 */

void listQueueAddBack (struct Queue* queue, TYPE value) 
{
    /* FIXME: You will write this function */
    assert (queue != NULL);
    assert (queue->tail != NULL);
    struct Link* newLink = (struct Link*) malloc (sizeof (struct Link));
    assert (newLink != NULL);
    newLink->value = value;
    newLink->next = NULL;
    queue->tail->next = newLink;
    queue->tail = newLink;
}

/**
    Returns the value of the link at the front of the queue.
    param:  queue   struct Queue ptr
    pre:    queue is not null
    pre:    queue is not empty (i.e., queue's head next pointer is not null)
    post:   none
    ret:    first link's value 
 */
TYPE listQueueFront(struct Queue* queue) 
{

   /* FIXME: You will write this function */
    assert (queue != NULL);
    assert (listQueueIsEmpty(queue) != 1);
    return ((queue->head)->next)->value;
}

/**
    Removes the link at the front of the queue and returns the value
    of the removed link.
    param:  queue   struct Queue ptr
    pre:    queue is not null
    pre:    queue is not empty (i.e., queue's head next pointer is not null)
    post:   first link is removed and freed (call to removeLink)
 */
int listQueueIsEmpty (struct Queue* queue);
TYPE listQueueRemoveFront(struct Queue* queue) 
{
    /* FIXME: You will write this function */
    assert (queue != 0);
    assert (!listQueueIsEmpty(queue));
    struct Link* toDelete = queue->head->next;
    if (toDelete == queue->tail) {
        queue->tail = queue->head;
    }
    else {
        queue->head->next = toDelete->next;
    }
    return toDelete;
    free (toDelete);
}

/**
    Returns 1 if the queue is empty and 0 otherwise.
    param:  queue   struct Queue ptr
    pre:    queue is not null
    post:   none
    ret:    1 if queue head next pointer is null (empty); 
            otherwise 0 (not null; not empty)
 */
int listQueueIsEmpty(struct Queue* queue) 
{
    /* FIXME: You will write this function */
    assert (queue != NULL);
    assert (queue->tail != NULL);
    if ((queue->head)->next == NULL) {
        return 1;
    }
    else {
        return 0;
    }
}

/**
    Deallocates every link in the queue including the sentinel,
    and frees the queue itself.
    param:  queue   struct Queue ptr
    pre:    queue is not null
    post:   memory allocated to each link is freed
            " " sentinel " "
            " " queue " "
 */
void listQueueDestroy(struct Queue* queue) 
{

        assert(queue != NULL);
    while(!listQueueIsEmpty(queue)) {
        listQueueRemoveFront(queue);
    }
    free(queue->head);
    free(queue);
    queue = NULL;

}

/**
    Allocates and initializes a stack that is comprised of two 
    instances of Queue data structures.
    pre:    none
    post:   memory allocated for new struct Stack ptr
            stack q1 Queue instance init (call to queueCreate func)
            stack q2 Queue instance init (call to queueCreate func)
    return: stack
 */
struct Stack* listStackFromQueuesCreate() 
{
     /* FIXME: You will write this function */
    struct Stack* stack = (struct Stack*) malloc (sizeof (struct Stack));
    stack->q1 = listQueueCreate();
    stack->q2 = listQueueCreate();
    return (stack);
};

/**
    Deallocates every link in both queues contained in the stack,
    (inc.the sentinel), the queues themselves and the stack itself.
    param:  stack   struct Stack ptr
    pre:    stack is not null
    pre:    queues are not null
    post:   memory allocated to each link is freed along with the 
            two queues and stack themselves

    Note that I checked that q1 and q2 are not null in this function
    also when I could have just left the assertion to fail in queueDestroy
    if either were pointing to null, but I thought it best to be explicit,
    albeit slightly repetitive.
 */
void listStackDestroy(struct Stack* stack)
{
    assert(stack != NULL);
    assert(stack->q1 != NULL && stack->q2 != NULL);
    listQueueDestroy(stack->q1);
    listQueueDestroy(stack->q2);
    free(stack);
    stack = NULL;
}

/**
    Returns 1 if the stack is empty and 0 otherwise.
    param:  stack   struct Stack ptr
    pre:    stack is not null
    post:   none
    ret:    1 if q1 is empty; else, 0
 */
int listStackIsEmpty(struct Stack* stack)
{

    /* FIXME: You will write this function */
    assert (stack != NULL);
    if (listQueueIsEmpty (stack->q1)) {
        return 1;
    }
    else {
        return 0;
    }
}

/**
    This internal function swaps what q1 and q2 pointers, such that
    q1 points to q2 and q2 points to q1.
    param:  stack   struct LinkedList ptr
    param:  value   TYPE
    pre:    stack is not null
    post:   q1 points to the actual 'stack' with links
 */
void listSwapStackQueues(struct Stack* stack)
{
    /* FIXME: You will write this function */
    assert (stack != 0);
    struct Queue* temp = stack->q1;
    stack->q1 = stack->q2;
    stack->q2 = temp;
}

/**
    Adds a new link with the given value to the back of the Queue q2.
    Then while Queue q1 isn't empty, the first link of the queue is 
    dequeued/removed and added to the back of Queue q2, so that in
    the end, Queue q2 has the new order to represent the stack properly
    with the new value at the front of the queue.
    param:  stack   struct LinkedList ptr
    param:  value   TYPE
    pre:    stack is not null
    post:   new link is created w/ given value and added to end of q2
            the first link of q1 is removed and added to end of q2 until
            it's empty
            q1 and q2 are swapped
 */
void listStackPush(struct Stack* stack, TYPE value) 
{
    /* FIXME: You will write this function */
    assert (stack != NULL);
    listQueueAddBack (stack->q2, value);
    while (!listQueueIsEmpty(stack->q1))
    {
        TYPE valueTemp = listQueueRemoveFront (stack->q1);
        listQueueAddBack (stack->q2, valueTemp);
    }
    listSwapStackQueues (stack);
}

/**
    Removes the link at the top of the stack and returns its value.
    param:  stack   struct Stack ptr
    pre:    stack is not null
    pre:    stack is not empty
    post:   first link is removed and freed (call to removeLink)
    ret:    value of the removed link
 */
TYPE listStackPop(struct Stack* stack) 
{
    /* FIXME: You will write this function */
    assert (stack != 0);
    assert (!listQueueIsEmpty (stack->q1));
    return listQueueRemoveFront (stack->q1);
}

/**
    Returns the value of the link at the top of the stack.
    param:  stack   struct Stack ptr
    pre:    stack is not null
    pre:    stack is not empty
    post:   none
    ret:    first link's value 
 */
TYPE listStackTop(struct Stack* stack) 
{
    /* FIXME: You will write this function */
    assert (!listQueueIsEmpty (stack->q1));
    assert (stack != 0);
    return listQueueFront (stack->q1);
}

/**
    Used for testing the stack from queue implementation.
 */

void assertTrue(int pred, char* msg) 
{
    printf("%s: ", msg);
    if(pred)
        printf("\tPASSED\n");
    else
        printf("\tFAILED\n");
}

int main() 
{
    struct Stack* s = listStackFromQueuesCreate();
    assert(s);
    printf("\n-------------------------------------------------\n"); 
    printf("---- Testing stack from queue implementation ----\n");
    printf("-------------------------------------------------\n"); 
    printf("stack init...\n");
    assertTrue(listStackIsEmpty(s) == 1, "stackIsEmpty == 1");

    printf("\npushing 4, 5, -300...\n");
    listStackPush(s, 4);
    listStackPush(s, 5);
    listStackPush(s, -300);

    assertTrue(listStackIsEmpty(s) == 0, "stackIsEmpty == 0");
    assertTrue(listStackPop(s) == -300, "\npopping; val == -300");
    assertTrue(listStackPop(s) == 5, "popping; val == 5");
    assertTrue(listStackTop(s) == 4, "top val == 4\t");
    assertTrue(listStackPop(s) == 4, "popping; val == 4");
    assertTrue(listStackIsEmpty(s) == 1, "stackIsEmpty == 1");
    // listStackPop(s);     // should fail assert
    // listStackTop(s);     // should fail assert

    printf("\npushing 0-9...\n");
    for(int i = 0; i < 10; i++) {
        listStackPush(s, i);
    }
    assertTrue(listStackTop(s) == 9, "top val == 9\t");

    listStackDestroy(s);

    return 0;
}

~ - ~ - ~ -Edit 1- ~- ~ - ~

Обновленный код, приведенный выше, должен вернуться сейчас.

Кроме того, в настоящее время я использую Visual Studio 2019 для своего компилятора.В моем университете есть компилятор Unix, но я еще не тестировал его из-за необходимости сначала подключиться к VPN, а что нет.Я в конечном итоге протестирую его, я просто не делал этого кода.

~ - ~ - ~ -Edit 2- ~ - ~ - ~ снова добавил редактирование кода (на этот раз с исправленным возвращаемым дерпом)

извините за количество ошибок, я только сейчас вернулся к программированию на C, так как мне пришлось посещать некоторые классы в младшем колледже в действительно странном порядке, в основном из-за доступности классов, поскольку мои структуры данных обычно не моглине будет доступен до осени следующего года.Мне просто повезло, и я перешел в Uni и попал туда

Answer 1

1. Существует одна проблема в обмене очередями:

   void listSwapStackQueues (struct Stack * stack) {/ * FIXME: Вы напишите эту функцию / assert (stack! =0);struct Queue temp = (struct Queue *) malloc (sizeof (struct Queue));temp = stack-> q1;stack-> q1 = stack-> q2;stack-> q2 = temp;бесплатно (темп);}

Это освобождает указатель stack->q1, что приводит к аннулированию заголовка списка и утечке памяти.Выполнение:

type *pnt = malloc(...); 
pnt = ...

всегда неправильно и приводит к утечке памяти.Просто поменяйте местами указатели, без всяких malloc и бесплатно:

void listSwapStackQueues(struct Stack* stack)
{
    assert (stack != 0);
    struct Queue* temp;
    temp = stack->q1;
    stack->q1 = stack->q2;
    stack->q2 = temp;
}

Тип указателя, переданный listQueueIsEmpty внутри listQueueRemoveFront внутри утверждения, недопустим:

ТИП listQueueRemoveFront (struct Queue * queue) {assert (listQueueIsEmpty (queue-> head));// неверно

Вы хотите пройти очередь, т.е.listQueueIsEmpty(queue), к функции.Также очередь списка должна , а не быть пустой при удалении, поэтому вы, вероятно, хотите отменить выражение:

TYPE listQueueRemoveFront(struct Queue* queue)
{
    assert (!listQueueIsEmpty(queue));

Также не забудьте переслать объявление функции, чтобы компилятор мог предупредить вас:

int listQueueIsEmpty(struct Queue* queue);
TYPE listQueueRemoveFront(struct Queue* queue)
{
    assert (!listQueueIsEmpty(queue));

В вашей функции listQueueRemoveFront нет оператора return.Таким образом, код недействителен и вызывает неопределенное поведение:

TYPE listQueueRemoveFront (struct Queue * queue) {// здесь нет возврата}

.. позже в Push ... TYPE valueTemp = listQueueRemoveFront (stack-> q1);

Не забудьте всегда компилировать с включенными предупреждениями (при gcc используйте -Wall -Wextra -Werror) и исправлять все предупреждения.При компиляции с включенными предупреждениями компилятор проясняет проблему:

1.c: In function ‘listQueueFront’:
1.c:98:13: warning: implicit declaration of function ‘listQueueIsEmpty’; did you mean ‘listQueueInit’? [-Wimplicit-function-declaration]
     assert (listQueueIsEmpty(queue) != 1);
             ^~~~~~~~~~~~~~~~
1.c: In function ‘listQueueRemoveFront’:
1.c:123:1: warning: control reaches end of non-void function [-Wreturn-type]
 }

Answer 2

В вашем коде более 1 проблемы. Но ваша конкретная проблема вызвана listSwapStackQueues.

Вы выделяете некоторое количество памяти для временной очереди, а затем назначаете указатель для этой памяти на q2. Затем вы используете free для освобождения памяти, оставляя q2 указывающим на то, чего больше нет.

На самом деле вам вообще не нужно выделять здесь память, поскольку, вероятно, все, что вам нужно, это поменять местами указатели. Все, что вам нужно сделать в этом случае:

struct Queue *temp = stack->q1;    
stack->q1 = stack->q2;
stack->q2 = temp;

Используете ли вы отладчик для отладки вашей программы? Если вы этого не сделаете, вы должны ознакомиться с одним. Поиск ошибок памяти, подобных этим, может быть затруднен без надлежащего отладчика.

Вы столкнетесь с большим количеством подобных проблем, поэтому важно иметь хороший отладчик. Если вы работаете в Windows, я бы порекомендовал просто приобрести Visual Studio, поскольку он бесплатный и довольно мощный.

EDIT:

Помимо ответов, данных другими, есть также следующее: Когда вы добавляете новые узлы в список, инициализируйте next как NULL. т.е. в вашей функции listQueueAddBack:

    struct Link* newLink = (struct Link*) malloc (sizeof (struct Link));
    assert (newLink != NULL);
    newLink->value = value;
    // Initialize next. 
    newLink->next = NULL;