Очередь с использованием структур и динамического выделения памяти

Question

Мне поручено создать структуру данных очереди в C в виде связанного списка. Наш лектор дал нам большой объем кода для реализации стека, но мы должны адаптировать его для создания очереди. Код, который дал нам наш лектор, в итоге не компилируется и не выполняет сегментацию в той же точке, что и код, который я написал для очереди. Я очень плохо знаком с структурами, malloc и C в целом, поэтому я мог упустить что-то до боли очевидное.

Вот код, который я использую:

#include <stdio.h>
#include <stdlib.h>
struct node{
    int data;               //contains the actual data
    struct node *prev;      //pointer to previous node (Closer to front)
    struct node *next;      //pointer to next node (Closer to back)
};

typedef struct node *Nodepointer;

struct queue{
    Nodepointer front;
    Nodepointer back;
};

typedef struct queue *Queuepointer;

main(){
    Queuepointer myqueue;       //create a queue called myqueue
    init(myqueue);              //initialise the queue
    Nodepointer new = (Nodepointer)malloc(sizeof(struct node));
    myqueue->front = new;
}

int init(Queuepointer q){ 
    q = (Queuepointer)malloc(sizeof(struct queue));
    q->front = NULL;
    q->back = NULL;
}

Идея состоит в том, что структура очереди «содержит» первый и последний узлы в очереди, и когда узел создается, myqueue обновляется. Однако я даже не могу добраться до этой части (pop и push пишутся, но для краткости опущены). Код segfaulting в строке

myqueue->front = new;

со следующим выводом GDB:

Program received signal SIGSEGV, Segmentation fault.
0x08048401 in main () at queue.c:27
27  myqueue->front = new;

Есть идеи, что я делаю не так?

Answer 1

Когда вы звоните init:

int init(Queuepointer q){ 
    q = (Queuepointer)malloc(sizeof(struct queue));
    q->front = NULL;
    q->back = NULL;
}

Вы передаете указатель на очередь в функцию и инициализируете, где этот указатель указывает (в памяти) внутри функции. Установив q = ..., вы назначаете новое значение q.

К сожалению, вызывающая функция этого не видит. Вместо этого вам нужно передать указатель на указатель:

int init(Queuepointer * qp){ 
    Queuepointer q = (Queuepointer)malloc(sizeof(struct queue));
    q->front = NULL;
    q->back = NULL;
    // Set qp:
    *qp = q;
}

Затем измените вызывающую функцию:

init(&myqueue);

Answer 2

INIT (myqueue); по значению передает указатель на нераспределенную память. Следовательно, init ничего не делает для этого (вместо этого пишет случайные вещи в случайном месте).

Затем myqueue-> вещи делают это снова.

Вы должны были использовать указатель на указатель.

Init будет получать очередь ** и вызываться как init (& myqueue). Внутри * myqueue = () malloc материал

Кроме того, я рекомендую вас против этих typedefs. Они довольно плохой стиль.

Answer 3

Первая проблема, которую я вижу, состоит в том, что функция «init» записывает выделенный указатель в «q», который НЕ является вашей первоначальной «myqueue».Помните, что C передает свои аргументы по значению.Возможная коррекция (не идеальная, просто подсказка):

Queuepointer init(void)
    Queuepointer q; 
    q = (Queuepointer)malloc(sizeof(struct queue));
    q->front = NULL;
    q->back = NULL;
    return q;
}
`

И в "main":

myqueue = init ();

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

С уважением

Answer 4

int init(Queuepointer q){ 
    q = (Queuepointer)malloc(sizeof(struct queue));
    q->front = NULL;
    q->back = NULL;
}

Незначительный зазор, но ваша функция инициализации не имеет возвращаемого значения, поэтому, возможно, измените его на:

void init(Queuepointer *q) {

или

int init(Queuepointer * qp){ 
    Queuepointer q = (Queuepointer)malloc(sizeof(struct queue));
    q->front = NULL;
    q->back = NULL;
    *qp = q;
    if(q) {
        return 1;
    } else return 0;
}

Настройте в соответствии с тем, как вы хотите выполнитьпроверка ошибок.

Answer 5

Вы передаете myqueue по значению, поэтому при init () происходит выделение копии myqueue, а не myqueue.

Итак, правильная версия:

int init(Queuepointer* q){ 
    *q = (Queuepointer)malloc(sizeof(struct queue));
    *q->front = NULL;
    *q->back = NULL;
}

и вы можете вызвать init () из основного

init(&myqueue);