Преобразование связанного списка в очередь (перемещение узлов)

Question

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

typedef struct _listnode 
{ 
    int item; 
    struct _listnode *next; 
} ListNode; // You should not change the definition of ListNode 

typedef struct _linkedlist 
{ 
    int size; 
    ListNode *head; 
} LinkedList; // You should not change the definition of LinkedList 

typedef struct _queue 
{ 
    LinkedList ll; 
} Queue; 

И с помощью Епдиеего, DEQUEUE и isEmptyQueue, я должен создать очередь из связанного списка.

Поэтому логика, что я получил это:

Loop thru list size 
     enqueue linked list head node 
     removeNode to update linkedlist head node 

Является ли эта логика правильная? Мне нужно начало и спасибо заранее.

Так что я вышел с этим кодом, чтобы создать очередь из связанного списка:

Однако, он выходит из строя моей программы без сообщения об ошибке. Я попробовал с фиктивным значением enqueue (q, 1), и он все еще падает. Есть идеи?

Answer 1

Я думаю, что ваша логика верна, но я хотел бы добавить немного больше деталей, чтобы сделать его проще кодировать

Loop through the link list, selecting nodes one by one (until NULL) 
    select a node; 
    enqueue the value to the queue; 
    Free the memory of that enqueued node; 
    adjust the pointers to point to the next node in the linked list; 

Редактировать

Позволяет записать алгоритм в мелочах

while(head != NULL) 
//Loop to traverse the linked list, just as you would while displaying each node 

    enqueue(que, head->item); 
    //This function will work just like a normal enqueue() function 
    //It should take the item, and insert it in the queue and nothing else 
    //I would recommend use an array for the queue 

    temp = head;   //save the current node address to free later 
    head = head -> next; //go to next node in the linked list 
    free(temp);   //free the previous node 

Answer 2

По правде говоря, я ничего не понял.

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

Вот демонстративной программа

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

typedef struct _listnode 
{ 
    int item; 
    struct _listnode *next; 
} ListNode; // You should not change the definition of ListNode 

typedef struct _linkedlist 
{ 
    int size; 
    ListNode *head; 
} LinkedList; // You should not change the definition of LinkedList 


int insert(LinkedList *ll, int index, int value) 
{ 
    if (index < 0 || index > ll->size) return -1; 

    ListNode *tmp = malloc(sizeof(ListNode)); 

    tmp->item = value; 

    if (ll->head == NULL) 
    { 
     tmp->next = ll->head; 
     ll->head = tmp; 
    } 
    else 
    {   
     ListNode *current = ll->head; 

     while (--index) current = current->next; 
     tmp->next = current->next; 
     current->next = tmp; 
    } 

    ++ll->size; 

    return 0; 
} 

void list_output(const LinkedList *ll) 
{ 
    for (ListNode *current = ll->head; current != NULL; current = current->next) 
    { 
     printf("%d ", current->item); 
    } 

    printf("\n"); 
} 

typedef struct _queue 
{ 
    LinkedList ll; 
} Queue; 

void queue_output(const Queue *q) 
{ 
    list_output(&q->ll); 
}  

int main(void) 
{ 
    LinkedList lst = { 0, 0 }; 
    const int N = 10; 

    for (int i = 0; i < N; i++) insert(&lst, i, i); 

    list_output(&lst); 

    Queue q = { lst }; 

    lst = (LinkedList) { 0, 0 }; 

    queue_output(&q); 

    // call here the method that free allocated memory of the queue 

    return 0; 
} 

Его выход

0 1 2 3 4 5 6 7 8 9 
0 1 2 3 4 5 6 7 8 9  

То есть очередь в настоящее время является владельцем выделенных узлов. Список в свою очередь пуст.

Это означает, что вы действительно преобразовали список в очередь.

Если вы имеете в виду, чтобы скопировать элементы списка в очереди (это другая операция по сравнению с конвертерной операции), то логика следующая

Traverse список точно так же, как вы бы пройти его выход его элемента и вызов метода enqueue очереди для каждого значения данных узла списка

for (; head != NULL; head = head->next) 
{ 
    enqueue(que, head->x); 
} 

сам список будет неизменным.

Если вам нужно удалить узлы списка после операции копирования, когда вы можете вызвать метод списка, который выполняет эту операцию.

Учтите, что нет необходимости динамически выделять список или очередь.Например, декларация списка может выглядеть

typedef struct _linkedlist 
{ 
    int size; 
    ListNode *head; 
} LinkedList; // You should not change the definition of LinkedList 

LinkedList lst = { 0, 0 }; 

Это узлы списка, которые выделяются динамически.

То же самое верно для очереди.

Вы можете объявить очереди следующим образом

typedef struct _queue 
{ 
    LinkedList ll; 
} Queue; 

Queue q = { { 0, 0 } }; 

Если у вас есть список, то, чтобы преобразовать его в очередь это достаточно, чтобы написать

q.ll = lst; 
lst = (LinkedList) { 0, 0 }; 

Также этот метод

void enqueue(Queue *que, int x) 
{ 
    int counter = 0; 
    insert(&(que->l), counter++, x); 
} 

не имеет смысла. И, кроме того, в Очереди нет члена данных l. У него есть член данных ll

Вам нужно добавить узлы в очередь. Таким образом, вы должны использовать значение члена данных size очереди в качестве индекса, в который должен быть вставлен новый элемент.

Так метод должен выглядеть

void enqueue(Queue *que, int x) 
{ 
    insert(&que->ll, que->ll.size, x) ; 
} 

Answer 3

void createQFrmLl(LinkedList *ll, Queue * q) 
{ 
    while (ll->size) 
    { 
     enqueue(q, ll->head->item); <-- CHANGE done here (passing 'q' instead of &q) 
     removeNode(ll, 0); 
    } 
} 

Епдиеие() ожидает 'Queue *', но вы передаете 'Queue **', следовательно, внутри Епдиеие() разыменования q-> LL есть сбой, поскольку q - неправильный адрес памяти.